Автор: Blockstream Team
Компиляция: Saoirse, Foresight News
Исследовательское подразделение Blockstream опубликовало полный аналитический отчет по решеточным подписям для Биткойна. В этой статье резюмируется содержание исследования, ключевые выводы и соответствующие рекомендации. Полный отчет можно найти по ссылке.
Цифровые подписи — это ядро механизма авторизации транзакций в Биткойне. Сегодня эту функцию выполняют подписи Шнорра (Schnorr) и ECDSA, стоимость которых крайне низка. В 1994 году Питер Шор доказал, что квантовый компьютер достаточной мощности может взломать оба типа подписей. Хотя вопрос о том, когда такие машины появятся, остается предметом широких дискуссий, необходимо разработать жизнеспособный план внедрения постквантовых подписей до того, как проблема станет реальностью.
Схемы подписей на основе решеток являются популярными кандидатами на замену существующих подписей. Решеточная криптография имеет более чем вековую историю исследований, и ее криптографические применения развиваются почти три десятилетия. В рамках постквантовой криптографии решеточные подписи обладают множеством преимуществ: общий размер открытого ключа и подписи может составлять менее 1,6 килобайта, а их алгебраическая структура в будущем может поддерживать мультиподписи, пороговые подписи и компактные доказательства.
В данном отчете исследуются три схемы: Dilithium, Falcon и Hawk. Для читателей, не знакомых с решеточной криптографией, мы объясняем принципы проектирования каждой схемы, подробно описываем алгоритмы и проводим анализ с точки зрения безопасности, производительности и практического развертывания (например, генерации ключей в кошельках). Какие из этих трех схем действительно можно внедрить в сеть Биткойна?
Критерии оценки
Выбор схемы подписи для Биткойна имеет свои ограничения. Наша оценка строится вокруг четырех ключевых критериев:
- Стоимость в цепочке (ончейн): Одним из наиболее важных показателей является общий размер открытого ключа и подписи. При расходовании выхода (output) открытый ключ и подпись записываются в цепочку, и полным узлам необходимо загружать и хранить каждый байт. Также критически важны затраты на верификацию: каждую подпись должны проверять все узлы сети; медленная верификация создает нагрузку на всю сеть.
- Сложность реализации: Способность безопасно реализовать схему имеет первостепенное значение. Если для проектирования требуются операции с плавающей запятой или точная гауссовская выборка, ошибка в реализации или атака по сторонним каналам, такая как анализ времени выполнения (timing attack), может привести к утечке секретного ключа. Сложность реализации — это фактор, который нельзя игнорировать для плавного перехода.
- Риски развертывания: При реальной интеграции в Биткойн возникают различные практические препятствия: выбор хеш-функции на уровне консенсуса (большинство кандидатов используют SHAKE, Биткойн использует SHA-256), воспроизводимость результатов подписи на разных платформах, а также соответствие процедуры подписания ограничениям памяти аппаратных кошельков.
- Потенциал развития: Подавляющее большинство биткойн-кошельков используют иерархический детерминированный механизм BIP-32: из одного главного открытого ключа можно вывести бесконечное количество дочерних открытых ключей без доступа к секретному ключу. В настоящее время стандартизированные постквантовые схемы подписей изначально не поддерживают эту функцию, поэтому мы исследуем затраты на ее добавление; также рассматриваем различные нестандартные варианты схем, которые могут принести дополнительные выгоды.
Какой уровень безопасности выбрать?
Прежде чем сравнивать размеры, необходимо определить целевой уровень безопасности, и этот выбор не так прост, как кажется. 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", история исследований которых относительно короче.
Незадолго до окончательной подготовки отчета Стажникас и Вайс из Anthropic обнаружили структурный изъян в конструкции решетки Hawk: фактическая размерность проблемы SVP, необходимой для восстановления ключа, вдвое меньше, чем предполагали разработчики. Оценочный уровень безопасности восстановления ключа для предлагаемых параметров был значительно ослаблен. Исследователи провели полную сквозную атаку на восстановление ключа для тестовых параметров HAWK-256, используемых для криптоанализа; даже после атаки официально предложенные HAWK-512 и HAWK-1024 все еще не могут быть реально взломаны. Команда Hawk подтвердила эффективность атаки и отозвала схему из процесса NIST; команда заявила, что если исправить уязвимость, удвоив параметры, то первоначальное преимущество Hawk в размере будет полностью утеряно.
Отчет по-прежнему содержит раздел о Hawk, поскольку данная атака направлена на конкретные алгебраические свойства числовых полей и не отрицает полностью эту парадигму проектирования. Пока неясно, может ли перепроектирование избежать уязвимости. Случай Hawk также наглядно подтверждает наши доводы в пользу консервативного запаса прочности: даже схема с отличным размером, высокой скоростью, прошедшая несколько раундов стандартизации, может значительно потерять в оценочном уровне безопасности из-за одной статьи.
Сводная таблица схем
Все схемы в приведенной выше таблице (включая SPHINCS+) являются безсостоятельными (stateless): подписывающему не нужно хранить историю предыдущих подписей. Состоятельные (stateful) хеш-подписи, такие как XMSS, могут иметь меньший размер подписи, но требуют поддержания состояния подписания; подробное сравнение можно найти в тематическом отчете по хеш-подписям.
Остаются многочисленные препятствия для внедрения
У Falcon отсутствует пригодная схема генерации ключей. В настоящее время единственная публично известная схема генерации BIP-32-стиля для Falcon выполняет перерандомизацию базиса секретного ключа, что резко увеличивает верхнюю границу нормы подписи, и подпись в цепочке раздувается примерно до 23,7 КБ. Кроме того, параметры этой схемы не соответствуют ее собственным условиям безопасности, и если исправить эту проблему, размер еще больше возрастет. В настоящее время не существует работоспособной реализации генерации открытых ключей для Falcon, и это, пожалуй, самая ценная нерешенная проблема, поднятая в отчете.
Стандарт Falcon еще не окончательный. Хотя NIST выбрал Falcon, черновой вариант FN-DSA еще официально не опубликован. После завершения стандартизации появятся проверенные реализации, тестовые векторы и поддержка на аппаратном уровне. Широкое внедрение снизит риски и сложность интеграции на уровне консенсуса Биткойна. Мы рекомендуем дождаться официального выпуска FN-DSA, так как до этого Falcon все еще находится в стадии разработки.
Вариант Falcon-WS: Этот вариант ослабляет внутренние параметры, компенсируя это отбраковкой (rejection sampling). Общий размер для уровня 1 сжимается до 1114 байт, для уровня 5 — до 2387 байт, что еще меньше по сравнению с оригинальным Falcon. Это направление представляет исследовательскую ценность, но не войдет в официальный стандарт и требует дополнительного криптоанализа. Уже обнаружено, что доказательство сильной стойкости к подделке для его производных схем имеет изъян (обычная стойкость к подделке не затрагивается).
Появится ли в будущем более совершенная схема? Помимо вышеупомянутых схем, серия Fiat-Shamir изначально появилась в BLISS 2013 года, а последняя работа Гартнера на конференции CRYPTO 2025, основанная на зрелых предположениях, теоретически может иметь размер, сопоставимый с Falcon. Основная причина сложности инженерной реализации этой серии — проблемы безопасности реализации: BLISS был взломан через сторонние каналы из-за непостоянного времени выполнения гауссовской выборки; последующие схемы не полностью устранили эту уязвимость, и последняя работа также указывает на повышенную сложность защиты этапа выборки. Пока проблема не решена, такие схемы имеют лишь теоретический интерес и не подходят для развертывания.
Решеточные и хеш-подписи могут дополнять друг друга. Решеточные подписи могут быть компонентом гибридных схем. Например, в SHRINCS безсостоятельный путь восстановления в настоящее время использует подписи SPHINCS+ размером в несколько КБ; замена их на подпись Falcon (или Falcon-WS) уменьшает размер, ускоряет верификацию и значительно снижает затраты на редко используемый путь восстановления, не затрагивая путь повседневного использования.
Выводы исследования
Преимущества и недостатки кандидатов на основе решеток довольно ясны: Hawk выбыл из конкурса после атаки команды Anthropic; Dilithium проще всего реализовать и является единственной схемой, имеющей исследовательскую базу для генерации ключей, но его размер неудобен для ончейн-затрат Биткойна; Falcon сочетает компактный размер, быструю верификацию и зрелые предположения безопасности; его главный недостаток — операции с плавающей запятой на стороне подписания — уже имеет возможное инженерное решение. Если бы сейчас пришлось выбирать схему решеточных подписей для Биткойна, мы бы выбрали Falcon-1024.
На данный момент наша точка зрения совпадает с выводами отчета по хеш-подписям: консервативный краткосрочный путь по-прежнему — это хеш-подписи, имеющие наиболее зрелые предположения безопасности и самый низкий риск, что подходит для переходного периода. После официального утверждения FN-DSA, появления стабильной спецификации, проверенных кодовых баз и поддержки аппаратных кошельков, Falcon предложит значительные улучшения по сравнению с чистыми хеш-подписями; также возможна гибридная реализация, позволяющая двум системам подписей дополнять друг друга.
