Сколько стоит перенос живой сети на постквантовые подписи

От редакции NodeTimes.

Постквантовая подпись от одного до трёх порядков больше заменяемой эллиптической кривой (elliptic-curve signature), и счёт за это приходит не в виде криптографии, а в виде пространства блоков, комиссий и вычислительной работы для проверки. Следовательно, сеть сталкивается с выбором между тремя ресурсами, которые нельзя расходовать одновременно: размером блока, частотой блоков и агрегацией. Это сторона затрат миграции, а не вопрос о том, что сломается, и числа смоделированы для сети в целом, а не измерены на одной конкретной.

Подписи стали больше по замыслу

Постквантовые подписи велики, потому что схемы основаны на других сложных задачах, а размер следует из конструкции, а не из ошибки в реализации.

ML-DSA (module-lattice signatures): семейство схем, стандартизированное в FIPS 204, чьи подписи являются векторами над кольцом многочленов, поэтому их размер растёт вместе с размерностью и модулем, а не с точкой кривой. SLH-DSA (stateless hash-based signatures): семейство, стандартизированное в FIPS 205, где подпись содержит путь аутентификации хеш-дерева и поэтому состоит из множества небольших хеш-значений вместо одного алгебраического объекта. FN-DSA: схема на основе Falcon, чьи подписи наиболее компактны среди трёх семейств подписей NIST, поскольку её конструкция использует структуру, которую модульно-решёточная схема не использует тем же образом.

Причина, по которой ни одна из них не уменьшается, структурная:

• Подпись решётки – это вектор, и вектор должен поместиться в подпись; уменьшение его означает ослабление параметров, а не сжатие кодировки.
• Хеш-подпись содержит путь, который доказывает, что одноразовый ключ принадлежит опубликованному корню, и этот путь имеет столько элементов, сколько уровней у дерева.
• Хеш-схемы жертвуют размером ради аргумента безопасности, который не предполагает ничего, кроме хеш-функции, именно поэтому размер не падает.

Что это значит для цепочки, заключается не только в байтах. В сети proof-of-stake подпись делает производителя блока подотчётным, поэтому её размер на транзакцию умножается на каждое действие проверки, выполняемое сетью, и форма этого умножения является тем, о чём идёт речь в остальной части этой статьи. Более широкий контекст того, какие цепочки сталкиваются с этим и как они различаются, содержится в руководстве по постквантовым блокчейнам.

Размеры, схема за схемой

Различия между постквантовыми схемами больше, чем разница между любой из них и классической подписью, поэтому выбор схемы важнее выбора миграции.

Каждое число в этой таблице – это размер спецификации, а не измерение, сделанное на живой цепочке. Два фактора делают диапазоны широкими. Во-первых, у каждого семейства есть наборы параметров, которые торгуют размером в обмен на уровень безопасности, и разброс внутри самого ML-DSA составляет от 2420 байт для ML-DSA-44 до 4627 для ML-DSA-87. Во-вторых, открытый ключ – это отдельная строка расходов от подписи, и зависит ли он от каждой транзакции, зависит от модели учётной записи, а не от схемы.

Наиболее компактным выбором является вариант на основе Falcon, и его размер – причина, по которой несколько сетей рассматривают его в первую очередь; компромисс заключается в более деликатной реализации и процедуре подписывания, которую сложнее сделать правильно, чем модульно-решёточную схему. Откуда происходит эта конструкция, изложено в материалах о Falcon, а алгебра за большим семейством – в объяснении о решёточных схемах.

Что стоит подпись внутри блока

Внутри блока подпись – это не фиксированная стоимость, это доля каждой транзакции, и эта доля решает, сколько транзакций помещается.

Арифметика стоит того, чтобы сделать её один раз, на открытом воздухе. Подпись secp256k1, схема ECDSA, взлом и замена которой описаны в объяснении о том, как квантовые компьютеры ломают ECDSA, занимает около 64 байт транзакции, и в нескольких дизайнах открытый ключ может быть восстановлен из неё, поэтому ничего другого не должно передаваться. Ни одна стандартизированная постквантовая схема не предлагает такого восстановления, поэтому открытый ключ должен передаваться вместе с транзакцией или запрашиваться в состоянии, и это рычаг за всем счётом. Замена этого на подпись ML-DSA-65 добавляет 3309 байт в ту же транзакцию, и если открытый ключ несётся вместе, его 1952 байта идут с ним: около 5261 байта вместо 64.

Передвижение ключа – единственный самый большой доступный рычаг, и это вопрос о модели учётной записи:

• Цепь на основе учётных записей с ключом в состоянии: открытый ключ хранится один раз на аккаунт, и транзакция несёт только подпись, поэтому стоимость на транзакцию примерно в пятьдесят раз превышает классическую, а не в восемьдесят.
• Подпись, несущаяся в транзакции без поиска в состоянии: ключ путешествует каждый раз, и та же оплата оплачивает оба объекта.
• Агрегированный пакет: многие подписи заменяются одним объектом, что нарушает линейную зависимость между размером и количеством транзакций, ценой механизма агрегации.

Затем следует собственная цена протокола за байты. Там, где calldata стоит фиксированное количество газа за ненулевой байт, подпись взимается как любые другие данные: при 16 газе за ненулевой байт одна только подпись ML-DSA-65 составляет около 53 000 газа до того, как транзакция выполнит что-либо. По сравнению с полом протокола в 21 000 газа за обычный перевод, одна только подпись стоит около двух с половиной обычных переводов, и фиксированный лимит газа блока превращает это соотношение в показатель мощности.

Агрегация, и почему стандарты не дают её

Агрегация заменяет множество подписей одним объектом, и ни одна из стандартизированных схем постквантовых подписей не предоставляет её нативно.

Классические подписи BLS агрегируются, потому что схема живёт в группе, где две подписи можно умножить в одну: подписи на одно сообщение сворачиваются в один объект, требующий одного спаривания для проверки, тогда как подписи на разные сообщения сохраняют каждое спаривание, поэтому экономия через реальный пакет – это фактор, а не константа.

Постквантовые семейства не имеют такой ручки: подпись решётки – это вектор, а хеш-подпись – это набор хеш-значений, и нет операции, при которой сто из них сворачиваются в одну. Агрегация поэтому должна быть построена поверх подписей, а не внутри них, обычно как рекурсивный STARK: система доказательств проверяет пакет подписей, и проверка этого доказательства сама по себе доказуема, так что доказательства многих пакетов складываются в один короткий объект.

• Что покупает доказательство: один короткий объект в цепи вместо одной подписи на транзакцию, и стоимость проверки, которая растёт гораздо медленнее, чем пакет.
• Что это стоит: доказывающий, который должен быть запущен и доверен для живучести, время доказывания, которое растёт с пакетом, и новый режим отказа, если доказывающий перестаёт публиковать.
• Что это не может исправить: подпись всё ещё должна существовать вне цепи, чтобы быть доказанной, поэтому агрегация перемещает затраты, а не удаляет их.

Последствие для сети – это вопрос расписания, а не технический: агрегация – правильный ответ для пропускной способности, но она требует системы доказательств, которая сама является предметом активных исследований, поэтому практический порядок – сначала сделать примитивы заменяемыми, а затем добавить агрегацию там, где уже существует структура пакета.

Стоимость верификации

Верификация – вторая узкая точка: большая подпись – это больше данных для разбора и больше работы для каждого валидатора, и два этих показателя не растут с одинаковой скоростью.

Разбор – это часть, которую легко недооценить. Подпись, которая в пятьдесят раз больше, – это также подпись, которую необходимо распространять, декодировать и хешировать, и каждый валидатор делает это для каждой транзакции. Подпись решётки быстро верифицируется после разбора, потому что операция – это арифметика коротких векторов над небольшим кольцом; хеш-подпись верифицируется путём повторного вычисления пути дерева, что дешево на хеш, но суммируется, когда путь длинный. Примечания к дизайну стандартов представляют размер как цену конструкции, которая предполагает очень мало о математике противника.

Три бюджета движутся вместе, и сеть, которая наблюдает только за одним из них, будет удивлена другим:

• Пропускная способность: распространение блоков и трафик пиров, которые растут вместе с подписью, а не с количеством транзакций.
• CPU: разбор и верификация подписи на каждом узле, которые растут вместе с обоими.
• Состояние: сохранённые открытые ключи, если модель учётной записи хранит их, что превращает стоимость на транзакцию в постоянную.

Что сеть может реально выбрать

У сети есть четыре рычага, и каждый из них тратит другой ресурс: параметры, агрегацию, отдельный тип вывода и отложенную миграцию.

1. Наборы параметров: выберите наименьший набор, соответствующий цели безопасности, что уменьшает подпись без изменения архитектуры. Обратимо, дёшево для начала и ограничено разбросом внутри одного семейства схем.
2. Агрегация: замените множество подписей одним доказательством, что является единственным рычагом, нарушающим линейную зависимость между размером и количеством транзакций. Дорого по сложности и зависит от доказывающего, который должен продолжать работать.
3. Отдельный тип вывода: дайте постквантовым подписям свой собственный способ быть потраченными, так что существующие выводы сохраняют свой размер, и только новые платят. Обратимо в том смысле, что цепь может прекратить их создание, сложно обратить в том смысле, что они остаются в состоянии.
4. Отложенная миграция: сохранить классическую схему настолько долго, насколько сохраняется предположение, и потратить время на интерфейсы, которые делают следующий шаг возможным. Бесплатно сегодня, дорого в том смысле, что предположение не находится под контролем сети.

Порядок между этими рычагами – это фактически решение, и оно зависит от того, какого ресурса сети не хватит первым. Цепь, чьи блоки малы, исчерпывает пространство и нуждается в агрегации или новом типе вывода; цепь, чьи валидаторы уже заняты выполнением, замечает счёт за верификацию первым. Выбор между ними – это то место, где миграция перестаёт быть криптографическим проектом и становится планом мощности, а история того, как стандарты пришли к этим размерам, содержится в отчёте о процессе NIST.

Частые вопросы

Насколько больше постквантовая подпись?

В общих решёточных схемах подпись в десятки раз больше классической: ML-DSA начинается с 2420 байт против около 64 для подписи secp256k1.

Размер, а не уровень безопасности, создаёт проблему сети, потому что каждая транзакция несёт его.

Можно ли агрегировать подписи?

Да, но не самими стандартизированными схемами: агрегация должна быть построена поверх, обычно как доказательство, которое проверяет пакет подписей.

Классическая агрегация BLS – это свойство схемы, чего именно не предлагают постквантовые семейства.

Увеличивает ли большая подпись комиссию каждой транзакции?

Да, там, где комиссии взимаются за пространство, занимаемое транзакцией, потому что доля подписи в этом пространстве резко растёт.

То, пропорционально ли увеличение размеру подписи, зависит от модели учётной записи: ключ, хранящийся в состоянии, оплачивается один раз, а не за каждую транзакцию.

Верификация тоже дороже?

Не для самой проверки: дополнительная стоимость – это разбор, распространение и хеширование большего объекта на каждом валидаторе. Подпись решётки быстро верифицируется после разбора, и только хеш-семейство платит за длинный путь аутентификации.

Счёт приходит в виде пропускной способности и CPU для обработки большего количества данных на каждом валидаторе, а не как более медленная проверка или стоимость хранения.

Что должна делать сеть первой?

Решить, какой ресурс она намерена потратить: параметры, агрегацию, отдельный тип вывода или время.

Это решение определяет всё последующее, потому что четыре рычага не аддитивны: агрегация меняет модель мощности, тогда как параметры только перемещаются внутри неё.