FROST: гибкие оптимизированные для округления пороговые сигнатуры Шнорра

Автор: Даниэль Чжоу

FROST — это протокол подписи Шнорра с оптимальным пороговым значением. Здесь мы расскажем, почему Coinbase решила использовать FROST, что такое FROST и что мы обнаружили при оценке FROST.

Почему FROST?

Чтобы повысить эффективность систем подписи пороговых значений Coinbase , мы решили изучить протокол подписи Шнорра с пороговым значением FROST, который имеет следующие преимущества по сравнению с другими протоколами пороговой подписи на основе Шнорра [GJKR03, SS01]:

Низкая сложность раунда как при распределенном генерировании ключей, так и при подписании фазы. Фаза генерации распределенного ключа может быть завершена в 2 раунда. Фаза подписи может быть завершена менее или равной 3 раундам в зависимости от того, используем ли мы роль агрегатора подписей и этап предварительной обработки. То есть

• подписание в один раунд с помощью агрегатора доверенных подписей и этап предварительной обработки.
• Подписание в два этапа с помощью агрегатора доверенных подписей, но без этапа предварительной обработки.
• Трехэтапное подписание без доверенного агрегатора подписей и без этапа предварительной обработки.

Параллельная безопасность. Фаза подписания безопасна при одновременном выполнении. То есть параллельно может выполняться неограниченное количество операций с подписью. В отличие от других протоколов пороговой подписи Шнорра, существуют существующие протоколы пороговой подписи на основе Шнорра, такие как [GJKR03, SS01], которые имеют такую ​​же сложность раунда, но страдают от ограниченного параллелизма для защиты от атаки Драйверса и др. [DEF19]. Эта атака изначально была предложена в настройке n -out-of- n Шнорра с несколькими сигнатурами, но она также применяется аналогичным образом в пороговом значении t -out-of- n с такими же параметрами для противника, который контролирует до t-1 участников. Мы отсылаем читателей к разделу 2.6 проекта FROST для получения более подробной информации. Чтобы предотвратить эту атаку без ограничения параллелизма, FROST связывает ответ каждого участника с определенным сообщением, а также набор участников и их набор точек эллиптической кривой (EC), используемых для этой конкретной операции подписи. При этом объединение ответов по разным сообщениям или парам точек EC приводит к недействительной сигнатуре, предотвращая такие атаки, как атаки Drijvers и др.

Защита от нечестного большинства. FROST защищен от злоумышленников, которые контролируют до t-1 подписывающих лиц на этапе подписания.

Простые криптографические строительные блоки и предположения. FROST основан на пороговой схеме совместного использования секрета Шамира и проверяемых Фельдманом схемах разделения секрета и полагается только на допущение дискретного логарифма.

Как работает FROST?

Прежде чем мы расскажем, как работает FROST сначала напомним, как работает автономная подпись Шнорра.

Алгоритм цифровой подписи Шнорра представляет собой тройку алгоритмов: (KeyGen, Sign, Verify) .

Пусть G будет групповым генератором циклической группы с простым порядком p, и пусть H будет криптографической хэш-функцией, отображающей поле Z ₚ * . Подпись Шнорра создается над сообщением m с помощью следующих шагов:

KeyGen -> (sk, vk)

• Случайная выборка секретного ключа sk sig
  • Случайная выборка секретного одноразового номера k true / false
    • Разобрать sig = (z ‘, c’)
    • R ‘= z * G -c * vk
    • c ‘= H (m, R’)
    • Вернуть true, если c = c ‘, в противном случае вернуть false.

    Мы вызываем (sk, vk) секретный и проверочный ключи соответственно. Мы называем m подписываемое сообщение и sig цифровой подписью Шнорра.

    FROST — это пороговый протокол подписи Шнорра, который содержит два важных компонента. Во-первых, n участников запускают протокол генерации распределенного ключа (DKG) для генерации общего ключа проверки; в конце каждый участник получает общий секретный ключ и общий ключ проверки. После этого любой участник t-out-of-n может запустить протокол пороговой подписи для совместной генерации действительной подписи Шнорра. На рисунке ниже схематично показано, как работает FROST в случае t = 3 и n = 5 .

    (3, 5) — FROST Обзор пороговой подписи DKG +

    В следующем контексте мы представляем более подробную техническую информацию о генерации распределенных ключей FROST и пороговой подписи.

    FROST — распределенная генерация ключей (DKG). Секретный ключ подписи в подписи Шнорра — это элемент в поле Z ₚ. Цель этого этапа — создать долговременные общие секретные ключи и общий ключ проверки. Этот этап проводится n участниками. FROST строит свою собственную фазу генерации ключей на основе DKG Педерсена [GJKR03], в которой он использует в качестве подпрограмм как совместное использование секрета Шамира, так и поддающиеся проверке схемы совместного использования секрета Фельдмана. Кроме того, FROST также требует, чтобы каждый участник продемонстрировал знание своего секрета, отправив другим участникам доказательство с нулевым разглашением, которое само по себе является подписью Шнорра. Этот дополнительный шаг защищает от атак с использованием мошеннических ключей в настройках, где t ≥ n / 2 .

    В конце протокола DKG, объединенный ключ проверки vk создается. Кроме того, каждый участник P ᵢ имеет значение (i, sk ᵢ ) , которое является их долговременным общим секретным ресурсом и общим ключом проверки vk ᵢ = sk ᵢ * G . Общий ключ подтверждения участника P ᵢ vk ᵢ используется другими участниками для проверки правильности общих подписей P ᵢ на этапе подписания, в то время как ключ проверки vk используется внешними сторонами для проверки подписей, выданных группой.

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

    Наша реализация немного адаптирована из черновика FROST. В нашей реализации мы решили не использовать роль агрегатора сигнатур. Вместо этого каждый участник является агрегатором подписей. Этот дизайн более безопасен: все участники протокола проверяют, что вычислили другие, для достижения более высокого уровня безопасности и снижения риска. В отличие от других библиотек с открытым исходным кодом, насколько нам известно, мы первыми реализовали FROST без роли агрегатора сигнатур. Кроме того, мы решили не выполнять (одноразовую) стадию предварительной обработки, чтобы ускорить реализацию. На этапе предварительной обработки каждый участник подготавливает фиксированное количество пар точек EC для дальнейшего использования, которое выполняется за один раз для нескольких этапов порогового подписания. Однако мы рассматриваем этот этап как дополнительный раунд и готовим только одну пару баллов EC, что означает, что мы запускаем его каждый раз для каждого этапа подписания порогового значения. Более подробно, есть два основных различия между нашей реализацией и исходным черновиком.

    Во-первых, агрегатор подписей, как описано в черновике, проверяет сообщения, которые транслируются соавторами, и вычисляет окончательную подпись. В нашей реализации мы не используем такую ​​роль. Вместо этого каждый участник просто выполняет широковещательную рассылку вместо агрегатора подписей, выполняющего координацию. Обратите внимание, что FROST может быть создан без такого агрегатора сигнатур, как подчеркивается в черновике. Кроме того, реализация его децентрализованным способом больше подходит для подхода Coinbase многосторонних вычислений .

    Во-вторых, протокол в черновике использует предварительную стадию предварительной обработки. до подписания, где каждый участник P ᵢ пробует порядковый номер, скажем Q , одноразовых одноразовых идентификаторов (d ᵢⱼ , e ᵢⱼ ) , вычисляет и транслирует пары общедоступных точек (D ᵢⱼ = d ᵢⱼ * G, E ᵢⱼ = e ᵢⱼ * G) для дальнейшего использования в последующих раундах подписания, где j = 1… .Q . Этот этап предварительной обработки является универсальным. То есть каждый участник может подготовить фиксированное количество пар точек EC, скажем Q , и передать их агрегатору подписей, после чего агрегатор подписей распространяет эти пары точек EC среди всех участников для дальнейшего использования. Как только эти пары точек EC будут израсходованы, эти участники должны запустить еще один этап предварительной обработки. Поскольку мы решили не использовать такую ​​роль агрегатора подписей в нашей реализации, мы решили вместо этого позволить каждому участнику генерировать одну пару точек EC (D ᵢ , E ᵢ ) . Следовательно, в нашей реализации нет этапа предварительной обработки, и, следовательно, в нашей пороговой фазе подписания есть 3 раунда вместо 2. Также обратите внимание, что будет ли наша реализация содержать этап предварительной обработки или нет, просто зависит от того, сколько пар точек EC генерируется в раунде подписания. 1. Если каждый участник генерирует Q количество пар точек EC в первом раунде подписания, то этот раунд можно рассматривать как этап предварительной обработки, и наша реализация становится протоколом подписания с двумя раундами.

    Мы описываем, как работают эти три раунда подписания, и даем некоторые технические детали.

    Раунд подписания 1. Каждый участник P ᵢ начинает с создания одной частной пары nonce (d ᵢ , e ᵢ ) и соответствующая пара точек EC (D ᵢ , E ᵢ ) и транслирует эту пару очков всем остальным участникам. Каждый участник сохраняет эти пары полученных баллов EC для использования в дальнейшем. Раунды подписания 2 и 3 — это фактические операции, в которых участники t-out-of-n сотрудничают для создания действительной подписи Шнорра.

    Раунд подписания 2. Создание действительной подписи Шнорра. подпись, все участники t работают вместе, чтобы выполнить этот раунд. Основной метод этого раунда — это аддитивное разделение секретов t-out-of-t. Этот метод создает секретный одноразовый номер k = SUM (k ᵢ ) , который является тем же значением, сгенерированным в однопартийном алгоритме подписи Шнорра, и каждый k ᵢ — это доля, рассчитанная участником P ᵢ. Для этого каждый участник готовит набор пар точек ЭК B = (D ₁ , E ₁ ) …… (D ₜ , E ₜ ) , полученное в первом раунде, а затем вычисляет k ᵢ = d ᵢ + e ᵢ * r ᵢ, где r ᵢ = H (i, m, B) и H — хэш-функция, выходные данные которой находятся в поле Z ₚ. Вычисление r ᵢ важно, поскольку оно работает как значение привязки для каждого участника, чтобы предотвратить атаку подделки. Затем каждый участник вычисляет обязательство R ᵢ = D ᵢ + E ᵢ * r ᵢ так, чтобы оно связывало message m , набор подписывающих участников и EC каждого участника указывает на каждый общий ресурс подписи, так что общие подписи для одного сообщения не могут использоваться для другого. Это предотвращает атаку подделки, поскольку злоумышленники не могут комбинировать общие подписи в разных операциях подписи или переставлять набор подписывающих лиц или опубликованные точки для каждого подписавшего. Тогда обязательство для группы подписывающих будет просто R = SUM (R ᵢ ) . Как и в однопартийных подписях Шнорра, каждый участник вычисляет вызов c = H (m, R) .

    Вычислив вызов c , каждый участник участник может вычислить ответ z ᵢ на вызов, используя одноразовые одноразовые идентификаторы (d ᵢ , e ᵢ ) и долгосрочные секретные доли sk ᵢ, которые равны t-out-of-n (степень t-1 ) Шамир секретные доли долговременного ключа группы sk . Одно из основных наблюдений, которые использует FROST, заключается в том, что если k ᵢ являются аддитивными долями k , то каждое k ᵢ / L ᵢ — t-out-of-n доли Шамира k , где L ᵢ — коэффициент Лагранжа для участника P ᵢ. То есть L ᵢ = prod (i / (j-i)), где j = 1,…, t, j ≠ i. Это наблюдение является результатом работы Бенало и Лейхтера [BL88] и работы Крамера, Дамгаарда и Ишаи [CDI05]. Они представляют собой неинтерактивный механизм, позволяющий участникам локально преобразовать дополнительные доли, созданные с помощью конструкции совместного использования секретов Бенало и Лейхтера t-out-of-n, в полиномиальную форму Шамира. FROST использует простейший случай преобразования t-out-of-t. Таким образом, k ᵢ / L ᵢ + sk ᵢ * c — это степень t-1 Shamir секретные доли правильного ответа z = k + sk * c для простой (однопартийной) подписи Шнорра. Снова используя конверсию доли и значение, вычисленное каждым участником (а именно, k ᵢ = d ᵢ + e ᵢ * r ᵢ), получаем, что z ᵢ = d ᵢ + e ᵢ * r ᵢ + L ᵢ * sk ᵢ * c — t-out-of-t дополнительные доли z . В конце раунда подписания 2 каждый участник передает z ᵢ другим участникам.

    Раунд подписания 3. После получения z ᵢ от всех остальных участников , каждый участник проверяет соответствие этих отчетных z ᵢ со своей парой баллов ЭК (D ᵢ , E ᵢ ) и их общий ключ подтверждения vk ᵢ. Это можно сделать, проверив уравнение z ᵢ * G = R ᵢ + c * L ᵢ * vk ᵢ. Когда все z ᵢ действительны, каждый участник вычисляет z = SUM (z ᵢ ) и выводит (z, c) в качестве последней подписи Шнорра. Эта подпись будет должным образом проверена для любой стороны, не знающей, что FROST использовался для создания подписи, и может проверить ее с помощью стандартного уравнения односторонней проверки Шнорра с vk в качестве ключа проверки. Как мы уже упоминали, в нашей реализации мы не используем роль агрегатора сигнатур. Таким образом, каждый участник работает как агрегатор подписей. Поэтому мы позволяем каждому участнику самопроверять свою собственную подпись перед ее выводом.

    Проблемы реализации

    Мы упомянули некоторые известные реализации FROST: две реализации Rust — один от ZCash Foundation, а другой от frost-dalek — но они не подходят для нашего технологического стека. Одна реализация Golang принадлежит группе Taurus, но, к сожалению, эта реализация Go не готова к производственному использованию и не подвергалась внешнему аудиту. В результате мы решили реализовать протокол собственными силами.

    Одна из особенностей подписи FROST заключается в том, что каждый участник должен знать коэффициенты Лагранжа для каждого участника, чтобы вычислить z ᵢ . Это необычно для других протоколов пороговой подписи, которые используют проверяемое совместное использование секретов Фельдманом в качестве подпротокола, поэтому существует несколько существующих библиотек Go для поддержки ЭТОГО. Большинство существующих библиотек поддерживают создание секретных долей, полиномов и их интерполяцию, но не поддерживают вычисление коэффициента Лагранжа. Чтобы восполнить этот технический пробел, мы реализовали коэффициенты Лагранжа участников с учетом произвольных t идентификаторов участников в качестве входных данных. Перед запуском протокола порогового подписания он принимает входные идентификаторы участников t и генерирует все коэффициенты Лагранжа. Как предполагает черновик FROST, мы назначаем эти коэффициенты каждому участнику перед подписанием, чтобы повысить производительность.

    Резюме

    FROST — это гибкая, оптимизированная для раунда схема пороговой подписи Шнорра, которая минимизирует сеть накладные расходы на создание подписей Шнорра при установке порогового значения при одновременном обеспечении неограниченного параллелизма операций подписи и только порогового количества подписывающих участников. Мы представляем FROST, выделяем его функции и описываем его в полностью децентрализованном подходе (то есть без какого-либо стороннего агрегатора подписей). В этом посте рассказывается о том, что Coinbase обнаружила при оценке и внедрении протокола FROST, и мы с нетерпением ждем возможности добавить его в наш набор сервисов пороговой подписи.

    Если вас интересует передовая криптография, Coinbase нанимает.

    FROST: Flexible Round-Optimized Schnorr Threshold Signatures изначально был опубликован в блоге Coinbase на Medium, где люди продолжают разговор, выделяя эту историю и отвечая на нее.