Автор: Команда Blockstream
Перевод: Saoirse, Foresight News
Исследовательский отдел Blockstream опубликовал полный отчёт об исследовании подписей на основе решёток для биткоина. В данной статье представлены ключевые выводы и рекомендации из исследования,полный отчёт доступен по ссылке.
Цифровые подписи — это основной механизм авторизации транзакций в биткоине. На сегодняшний день схемы подписей Schnorr и ECDSA выполняют эту функцию с минимальными затратами. В 1994 году Шор доказал, что квантовый компьютер достаточной мощности сможет взломать эти схемы подписей. Хотя вопрос о том, когда появятся такие машины, остаётся предметом широких дискуссий, нам необходимо разработать план развёртывания постквантовых подписей ещё до того, как проблема станет актуальной.
Схемы подписей на основе решёток являются популярными кандидатами на замену существующих подписей. Криптография на основе решёток имеет более чем столетнюю историю исследований, а её криптографические применения развиваются почти тридцать лет. В постквантовой криптографии подписи на основе решёток обладают рядом преимуществ: общий размер открытого ключа и подписи может составлять менее 1,6 килобайта, а их алгебраическая структура в будущем может позволить реализацию мультиподписей, пороговых подписей и компактных доказательств.
В данном отчёте исследуются три схемы: Dilithium, Falcon и Hawk. Для читателей, незнакомых с криптографией на решётках, мы объясняем подходы к проектированию каждой схемы, подробно описываем алгоритмы и анализируем их с точки зрения безопасности, производительности и практического развёртывания (например, вывод ключей в кошельках). Какие из этих трёх схем можно реально развернуть в блокчейне биткоина?
Критерии оценки
Выбор схемы подписи для биткоина имеет свои ограничения. Наша оценка сосредоточена на четырёх основных критериях:
- Стоимость в блокчейне: Одним из наиболее важных показателей является общий размер открытого ключа и подписи. При трате выходов (outputs) открытый ключ и подпись записываются в блокчейн, и полным узлам необходимо загружать и хранить каждый байт. Также критически важны затраты на верификацию: каждая подпись должна проверяться всеми узлами сети, медленная верификация создаёт нагрузку на всю сеть.
- Сложность реализации: Крайне важно, можно ли схему безопасно реализовать. Если в дизайне требуются операции с плавающей запятой или тонкая выборка по гауссовскому распределению, ошибки в реализации или такие атаки по сторонним каналам, как анализ времени исполнения, могут привести к утечке ключей. Для обеспечения плавного перехода сложность реализации является фактором, который нельзя игнорировать.
- Риски развёртывания: При реальной интеграции в биткоин возникают различные практические препятствия: выбор хеш-функции на уровне консенсуса (большинство кандидатов используют SHAKE, биткоин использует SHA‐256), воспроизводимость результатов подписи на разных платформах и соответствие программы подписи ограничениям памяти аппаратных кошельков.
- Потенциал развития: Подавляющее большинство биткоин-кошельков используют BIP‐32 иерархические детерминированные (HD) механизмы: из одного мастер-ключа можно вывести бесконечное количество дочерних открытых ключей, не касаясь закрытого ключа. В настоящее время стандартизированные постквантовые схемы подписей изначально не поддерживают эту функцию, поэтому мы исследуем, какую цену придётся заплатить за её добавление; также мы рассматриваем различные нестандартные варианты схем, которые, возможно, могут принести больше пользы.
Какой уровень безопасности выбрать?
Прежде чем сравнивать размеры, необходимо определить целевой уровень безопасности, и этот выбор не так прост, как кажется. NIST делит уровни безопасности на 1–5; чем выше уровень, тем выше безопасность, но тем больше размер соответствующих ключей и подписей.
Мы считаем, что биткоин должен использовать как минимум уровень безопасности 3. Выходы биткоина могут оставаться не потраченными десятилетиями, и если прогресс в криптоанализе снизит реальный уровень безопасности схемы, активы окажутся заблокированными ослабленными ключами, подвергаясь долгосрочному риску. Предположения криптографии на решётках подвергались открытому криптоанализу почти тридцать лет, что дольше, чем история исследований эллиптических кривых на момент их принятия биткоином. Однако сложная алгебраическая структура решёток всё ещё оставляет множество возможностей для будущих атак, и мы не должны делать ставку на безопасность в отдалённом будущем, полностью полагаясь на неё.
Крупные игроки делают аналогичный выбор. Протокол PQ3 в iMessage от Apple полностью отказывается от параметров решётки 1-го уровня, используя на протяжении всего процесса параметры 3-го и 5-го уровней; Cloudflare в развёртывании постквантового TLS использует ML‐KEM‐768 (уровень 3), заявляя, что хотя уровень 1 сейчас выглядит безопасным, необходимо оставить запас прочности для криптоанализа на десятилетия вперёд. А временной горизонт безопасности биткоина ещё больше.
Повышение уровня безопасности требует затрат. Например, переход Dilithium с уровня 2 на уровень 3 увеличит общий размер примерно на 1,5 килобайта. В отчёте сравниваются параметры для всех уровней безопасности, и читатели могут самостоятельно взвесить компромиссы. Случай с Hawk доказывает, что консервативные соображения безопасности — это не просто теория.
Подробный разбор кандидатов
Dilithium: простая схема
Dilithium стандартизирован NIST как ML‐DSA в стандарте FIPS 204. Он переносит парадигму «коммитмент-вызов-ответ» подписей Шнорра в арифметику модулярных решёток.
Его главная особенность — простота. Все вычисления в Dilithium являются целочисленными: операции в кольце, умножение матриц на векторы, хеширование, округление; нет операций с плавающей запятой и не требуется выборка по дискретному гауссовскому распределению. Проще написать безопасную реализацию с постоянным временем выполнения. Это также наиболее широко внедряемый кандидат, интегрированный в OpenSSL, BoringSSL, AWS‐LC и Apple CryptoKit.
Цена — относительно большой размер. ML‐DSA‐65 с уровнем безопасности 3 имеет открытый ключ размером 1952 байта и подпись 3309 байт, что в сумме составляет 5261 байт, что примерно в 55 раз больше, чем суммарный размер нативных открытого/закрытого ключей и подписи в биткоине, и является самым большим среди трёх схем на том же уровне безопасности.
Самая ценная для биткоина особенность Dilithium: это единственная из трёх схем, которая близка к реализации вывода ключей в стиле BIP‐32. Конструкция перерандомизируемых ключей DilithiumRK позволяет генерировать дочерние ключи из родительского, используя только публичную информацию. В отчёте анализируются три варианта, включая наш предложенный DilithiumRKS, где логика вывода полностью находится внутри программного обеспечения кошелька, а в блокчейне требуется только стандартный верификатор для обработки обычных подписей ML‐DSA. Однако ни один из них ещё не готов к производственному развёртыванию: два варианта требуют модификации верификатора, а самому DilithiumRKS не хватает полного доказательства устойчивости к подделке; все схемы полагаются на общую для всей сети матрицу, что, хотя формально безопасно в предположении Module‐LWE, привязывает безопасность всех ключей к одному экземпляру. Мы считаем, что на данном этапе вывод открытых ключей на основе Dilithium является лишь доказательством концепции и не может быть использован в реальных развёртываниях.
Falcon: компактная схема
Falcon выбран NIST, его стандартизированное название — FN‐DSA. Он самый компактный из трёх. Falcon‐512 с уровнем безопасности 1 имеет общий размер открытого ключа и подписи 1563 байта; Falcon‐1024 с уровнем 5 — 3073 байта. Falcon‐1024 с более высоким запасом прочности по размеру даже меньше, чем Dilithium 3-го уровня.
Falcon использует другой подход, чем Dilithium: модель хеш-подписи на основе NTRU-решётки. Закрытый ключ подписывающей стороны — это короткий базис решётки; сообщение хешируется и отображается в точку пространства, подписывающий использует короткий базис, чтобы найти вектор в решётке, близкий к этой точке. Точка и этот соседний вектор вместе образуют подпись; верификация проверяет только, что вектор принадлежит решётке и находится достаточно близко. Сложность реализации заключается в поиске вектора без утечки информации о базисе. Ранние схемы GGH и NTRUSign выбирали ближайшую точку решётки напрямую, и каждая подпись раскрывала часть геометрической информации. Falcon использует фреймворк GPV, осуществляя выборку соседнего вектора из гауссовского распределения, что доказуемо делает выходные данные выборки независимыми от базиса, устраняя риск утечки, но значительно повышая сложность реализации сэмплера.
Сэмплер — слабое место Falcon с инженерной точки зрения. Он работает в комплексной частотной области Фурье и требует вычислений с плавающей запятой. Различные процессоры, компиляторы и опции оптимизации компиляции приводят к несовпадению результатов с плавающей запятой. Это не просто проблема совместимости, а угроза безопасности: доказательство безопасности GPV требует, чтобы подписывающая сторона никогда не выдавала два разных коротких вектора для одного и того же дайджеста; как только подпись становится детерминированной, различия в округлении с плавающей запятой на разных платформах нарушают это условие. Существуют возможные решения: детерминированный Falcon может использовать целочисленную эмуляцию вместо аппаратной плавающей запятой, производя полностью идентичные подписи на всех платформах. Цена — снижение скорости подписи примерно в 15 раз и скорости генерации ключей примерно в 2 раза.
Важно, что этап верификации не затрагивается: верификация Falcon полностью использует целочисленные операции, детерминирована и является самой быстрой среди кандидатов. Эта асимметричная характеристика очень удобна для биткоина: подпись создаётся кошельком один раз при трате, а каждая подпись должна быть проверена всеми полными узлами сети. Замедление этапа подписи в 15 раз — это низкочастотные затраты, и, по нашему мнению, разумный компромисс в обмен на воспроизводимость на разных платформах и целочисленные вычисления. Поэтому проблема с плавающей запятой — это препятствие, которое можно преодолеть инженерными средствами, а не фатальный недостаток.
Два замечания: из-за структурных ограничений у Falcon нет параметров 3-го уровня, можно выбрать только 1-й или 5-й. Исходя из соображений запаса прочности, мы рекомендуем Falcon‐1024. Во-вторых, подписание потребляет много памяти: сэмплер для параметра 1024 полагается на предварительно вычисленное дерево, занимающее около 90 килобайт памяти. Аппаратные кошельки могут динамически перестраивать это дерево по ветвям, сокращая использование памяти до 16 килобайт, но время подписания удваивается. Замедление подписания на аппаратных устройствах — это реальная стоимость, но она приемлема.
Hawk: потерпевшая неудачу схема
Цель Hawk — объединить преимущества двух других схем: подпись Hawk‐512 составляет всего 555 байт, что меньше, чем у Falcon; сторона подписания использует только целочисленные операции, минимальное использование памяти — всего 6 килобайт. Это также единственный оставшийся кандидат на основе решёток в третьем раунде конкурса дополнительных подписей NIST, и отчёт подробно описывает эту схему.
Цена — предположения о безопасности. Она не полагается на десятилетиями изучавшиеся проблемы NTRU и SIS, а использует проблему изоморфизма решёток и предположение one‐more‐SVP, история исследования которых относительно невелика.
Незадолго до завершения отчёта Straznickas и Weis из Anthropic обнаружили структурный изъян в построении решётки Hawk: фактическая размерность задачи SVP, необходимой для восстановления ключа, составляет лишь половину от предполагаемой разработчиками. Запас безопасности для восстановления ключа в предложенных параметрах был значительно ослаблен. Исследователи провели полную атаку на восстановление ключа для параметра HAWK‐256, используемого для криптоанализа; даже после атаки официально предложенные HAWK‐512 и HAWK‐1024 по-прежнему не могут быть взломаны на практике. Команда Hawk подтвердила эффективность атаки и отозвала схему из процесса NIST; команда заявила, что если исправить уязвимость, удвоив параметры, то главное преимущество Hawk — компактный размер — будет полностью потеряно.
Отчёт всё же сохраняет раздел о Hawk, поскольку эта атака направлена на алгебраические свойства конкретного числового поля, а не полностью опровергает данный подход к проектированию. Неясно, можно ли избежать уязвимости при перепроектировании. Случай с Hawk также наглядно подтверждает наше стремление сохранять консервативный запас прочности: даже схема с отличным размером, хорошей скоростью, прошедшая несколько раундов стандартизации, может серьёзно потерять в предполагаемом уровне безопасности из-за одной научной статьи.
Сравнительная таблица схем
Все схемы в таблице выше (включая SPHINCS+) являются подписями без состояния (stateless): подписывающей стороне не нужно записывать прошлые подписи. Хеш-подписи с состоянием (stateful), такие как XMSS, могут иметь меньший размер подписи, но требуют поддержания состояния подписи; подробное сравнение см. вспециальном отчёте о хеш-подписях.
Остаётся множество препятствий для внедрения
Для Falcon нет пригодной схемы вывода ключей. В настоящее время единственная опубликованная схема вывода ключей для Falcon в стиле BIP‐32 выполняет перерандомизацию базиса закрытого ключа, что резко увеличивает верхнюю границу нормы подписи, и подпись в блокчейне раздувается примерно до 23,7 килобайт. Более того, параметры этой схемы не соответствуют её собственным условиям безопасности, и если исправить эту проблему, размер ещё больше возрастёт. В настоящее время не существует работоспособной реализации вывода открытых ключей для Falcon, что является, пожалуй, самой ценной нерешённой проблемой, поднятой в отчёте.
Стандарт Falcon ещё не завершён. Хотя NIST выбрал Falcon, проект FN‐DSA ещё не опубликован официально. Завершение стандартизации принесёт прошедшие аудит реализации, тестовые векторы и поддержку на аппаратном уровне. Широкое внедрение снизит риски и сложность интеграции на уровне консенсуса биткоина. Мы рекомендуем дождаться официального выпуска FN‐DSA; до этого Falcon остаётся в состоянии изменений.
Вариант Falcon‐WS: Этот вариант ослабляет внутренние параметры, компенсируя это отбраковкой (rejection sampling), общий размер для 1-го уровня сжимается до 1114 байт, для 5-го — до 2387 байт, что ещё меньше по сравнению с оригинальным Falcon. Это направление представляет исследовательскую ценность, но не будет включено в официальный стандарт и требует дополнительного криптоанализа. Исследования уже выявили изъян в доказательстве сильной устойчивости к подделке (strong unforgeability) для его производной схемы (обычная устойчивость к подделке не затрагивается).
Появится ли в будущем более совершенная схема? Помимо вышеупомянутых схем, серия Fiat‐Shamir изначально появилась в 2013 году как BLISS; новейшая работа Gärtner, представленная на конференции CRYPTO 2025, основана на зрелых предположениях и на бумаге имеет размеры, сопоставимые с Falcon. Коренная причина сложностей с практической реализацией этой серии — проблемы безопасности реализации: BLISS был взломан через сторонний канал из-за непостоянного времени выборки по Гауссу; последующие схемы не устранили эту проблему полностью, а в новейшей работе отмечается, что защита этапа выборки стала ещё сложнее. Пока проблема не решена, такие схемы представляют лишь теоретический интерес и не подходят для развёртывания.
Подписи на основе решёток и хеш-подписи могут дополнять друг друга. Подписи на основе решёток могут быть компонентом гибридных схем. Например, в SHRINCS путь восстановления без состояния (stateless recovery path) в настоящее время использует подпись SPHINCS+ размером в несколько килобайт; замена её на подпись Falcon (или Falcon‐WS) даст меньший размер и более быструю верификацию, значительно снизив низкочастотные затраты на путь восстановления, при этом обычный путь использования не пострадает.
Выводы исследования
Ранжирование кандидатов на основе решёток по достоинствам и недостаткам довольно очевидно: Hawk выбыл из конкурса после атаки команды Anthropic; Dilithium проще всего реализовать и является единственной схемой, имеющей исследовательскую базу для вывода ключей, но его размер недружелюбен к стоимости в блокчейне биткоина; Falcon сочетает компактный размер, быструю верификацию и зрелые предположения о безопасности; его главный недостаток — вычисления с плавающей запятой на стороне подписания — уже имеет可行ные инженерные решения. Если бы прямо сейчас нужно было выбрать схему подписи на основе решёток для биткоина, мы бы выбрали Falcon‐1024.
На текущий момент наша позиция совпадает с выводами отчёта о хеш-подписях: консервативный краткосрочный путь — это всё ещё хеш-подписи, имеющие самые зрелые предположения о безопасности и наименьший риск, они подходят в качестве переходного решения. После официального завершения FN‐DSA, появления стабильных спецификаций, прошедших аудит кодовых баз и поддержки аппаратных кошельков, Falcon предложит значительные улучшения по сравнению с чистыми хеш-подписями; также можно использовать гибридное развёртывание, позволяя двум системам подписей дополнять друг друга.
