← Cloudflare Randomness Beacon / randomness-beacon / cryptographic-background

Генерация случайности

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

Сначала мы рассмотрим криптографию на основе спариваний (PBC), которая приобрела значительную популярность и используется во многих современных протоколах консенсуса и доказательствах с нулевым разглашением, таких как zk-SNARKs. Затем мы покажем, как drand использует PBC на этапе генерации маяка случайности для пороговых подписей Боне-Линна-Шахама (BLS). Наконец, мы расскажем, как drand объединяет сгенерированные пороговые подписи BLS в цепочку случайности.

Криптография на основе спариваний строится на билинейных группах (𝔾1,𝔾2,𝔾𝑡), где 𝔾1, 𝔾2, а также 𝔾𝑡 являются циклическими группами простого порядка 𝑝 с генераторами 𝑔1, 𝑔2, а также 𝑔𝑡, соответственно, и операция спаривания 𝑒:𝔾1×𝔾2→𝔾𝑡 со следующими свойствами:

• Билинейность: ∀𝑎,𝑏∈ℤ∗𝑝,∀𝑃∈𝔾1,∀𝑄∈𝔾2, имеем 𝑒(𝑎𝑃,𝑏𝑄)=𝑒(𝑃,𝑄)𝑎𝑏

• Невырожденность: 𝑒≠1

• Вычислимость: Существует эффективный алгоритм для вычисления 𝑒. В настоящее время drand использует кривую Баррето-Линн-Скотт BLS12-381.

Для генерации публично проверяемой, несмещенной распределенной случайности drand использует пороговые подписи Boneh-Lynn-Shacham (BLS). Сначала мы опишем обычные подписи BLS, а затем их пороговый вариант.

Подписи BLS представляют собой короткие подписи, основанные на билинейных спариваниях и состоящие всего из одного элемента в 𝔾1. Они детерминированы в том смысле, что зависят только от сообщения и ключа подписывающей стороны, в отличие от других схем подписи, таких как ECDSA, которым для безопасности требуется новое случайное значение для каждого подписываемого сообщения. Другими словами, любые две подписи BLS на одном и том же сообщении, созданные одним и тем же ключом, идентичны. В drand это свойство используется для достижения беспристрастности при генерации случайности.

Схема подписи BLS состоит из следующих подпроцедур.

Чтобы сгенерировать пару ключей, подписывающая сторона сначала выбирает закрытый ключ, 𝑥∈ℤ∗𝑝, случайным образом, а затем вычисляет соответствующий открытый ключ как 𝑋=𝑔𝑥2∈𝔾2.

Пусть 𝐻:{0,1}∗→𝔾1 обозначает криптографическую хеш-функцию, которая отображает произвольные битовые строки в элементы 𝔾1. Чтобы вычислить подпись BLS 𝜎 над сообщением 𝑚, подписывающая сторона вычисляет 𝜎=𝑥𝐻(𝑚)∈𝔾1.

Чтобы проверить, что подпись BLS 𝜎 над сообщением 𝑚 действительна, проверяющий убеждается, что 𝑒(𝐻(𝑚),𝑋)=𝑒(𝜎,𝑔2) выполняется с использованием открытого ключа подписавшего 𝑋.

Обратите внимание, что это уравнение выполняется для действительных подписей, поскольку 𝑒(𝐻(𝑚),𝑋)=𝑒(𝐻(𝑚),𝑔𝑥2)=𝑒(𝐻(𝑚),𝑔2)𝑥=𝑒(𝑥𝐻(𝑚),𝑔2)=𝑒(𝜎,𝑔2).

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

𝑛 участников выполняют 𝑡-of-𝑛 DKG для настройки коллективного открытого ключа, 𝑆∈𝔾2, и доли закрытого ключа 𝑠𝑖∈ℤ∗𝑝 неизвестного коллективного закрытого ключа, 𝑠, как описано выше.

Чтобы подписать сообщение, 𝑚, каждый 𝑖 использует свою долю закрытого ключа, 𝑠𝑖, чтобы создать частичную подпись BLS, 𝜎𝑖=𝑠𝑖𝐻(𝑚).

Чтобы проверить корректность частичной подписи, 𝜎𝑖, на 𝑚, проверяющий использует долю открытого ключа, 𝑆𝑖, сгенерированную во время DKG, и проверяет, что 𝑒(𝐻(𝑚),𝑆𝑖)=𝑒(𝜎𝑖,𝑔2) выполняется.

Чтобы восстановить коллективную подпись BLS, 𝜎 на 𝑚, проверяющий сначала собирает 𝑡 различных и корректных частичных подписей BLS, 𝜎𝑖, на 𝑚 с последующей интерполяцией Лагранжа.

Чтобы проверить коллективную подпись BLS, 𝜎, проверяющий убеждается, что 𝑒(𝐻(𝑚),𝑆)=𝑒(𝜎,𝑔2) выполняется, где 𝑆 является коллективным открытым ключом.

Благодаря свойствам интерполяции Лагранжа значение 𝜎 не зависит от подмножества 𝑡 корректных частичных подписей, 𝜎𝑖, выбранных при восстановлении подписи. Кроме того, интерполяция Лагранжа также гарантирует, что ни одно множество из менее чем 𝑡 подписантов могут предсказать или сместить 𝜎.

Таким образом, пороговая подпись BLS, 𝜎, обладает всеми свойствами, необходимыми для публично проверяемой, беспристрастной, непредсказуемой и распределенной случайности.

В приведенном выше 𝔾1 и 𝔾2 можно поменять местами. Это влияет на относительный размер открытого ключа и подписей. Первые цепочки drand строятся, как описано выше, с подписями на 𝔾2 и открытые ключи на 𝔾1. Размер подписи составляет 96 байт, а размер открытого ключа составляет 48 байт.

Некоторые приложения предпочитают более короткие подписи ценой увеличения открытого ключа. Поэтому в некоторых маяках drand подписи находятся в 𝔾1 и открытый ключ на 𝔾2. Такое изменение называется 𝔾1/𝔾2 swap.

Маяк случайности drand работает дискретными раундами, 𝑟. В каждом раунде маяки drand, настроенные на использование цепочечной случайности, генерируют новое случайное значение с помощью пороговых подписей BLS, связанных в цепочку случайности. Чтобы продолжить эту цепочку случайности, каждый участник drand, 𝑖, создаёт в раунде 𝑟 частичную подпись BLS, 𝜎𝑟𝑖 над сообщением 𝑚=𝐻(𝑟∥𝜎𝑟−1) где, 𝜎𝑟−1 обозначает (полную) пороговую подпись BLS из раунда 𝑟−1 и 𝐻, криптографическую хеш-функцию.

Как только не менее 𝑡 участников разослали свои частичные подписи, 𝜎𝑟𝑖, на 𝑚, любой может восстановить полную пороговую подпись BLS, 𝜎𝑟 который соответствует случайному значению раунда 𝑟. После этого узлы drand переходят к раунду 𝑟+1 и повторяет процесс.

Для раунда 𝑟=0, участники drand подписывают семя, зафиксированное во время настройки drand. Этот процесс гарантирует, что каждое новое случайное значение зависит от всех ранее сформированных подписей. Поскольку подпись детерминирована, злоумышленник также не может разветвить цепочку и представить две различные подписи 𝜎𝑟 и 𝜎′𝑟 в заданном раунде 𝑟 создать несогласованность в системах, использующих публичную случайность.

Маяки drand также можно настроить на использование несвязанной случайности. Чтобы продолжить эту цепочку случайности, каждый участник drand 𝑖, создаёт в раунде 𝑟 частичную подпись BLS, 𝜎𝑟𝑖 над сообщением 𝑚=𝐻(𝑟) где 𝐻 криптографическую хеш-функцию.

Этот процесс позволяет заранее вычислить сообщение 𝑚 для раунда 𝑟=i.