Можно ли генерировать случайные числа, если мы не доверяем друг другу?

В этой статье я расскажу про генерацию псевдо-случайных чисел участниками, которые не доверяют друг другу. Как мы увидим ниже, реализовать “почти” хороший генератор достаточно просто, а вот очень хороший – сложно.

Зачем вообще нужно генерировать случайные числа участникам, не доверяющим друг другу? Одна из областей применения — это децентрализованные приложения. Например, приложение, которое принимает ставку от участника и либо удваивает сумму с вероятностью 49%, либо забирает с 51%, будет работать только если оно может непредвзято получить случайное число. Если злоумышленник может повлиять на результат работы генератора случайных чисел, и даже незначительно увеличить свой шанс получить выплату в приложении, он легко опустошит его.

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

  1. Он должен быть непредвзятым. Другими словами, ни один участник не должен каким-либо образом влиять на результат генератора случайных чисел.
  2. Он должен быть непредсказуемым. Другими словами, ни один участник не должен иметь возможность предугадать, какое число будет сгенерировано (или вывести какие-либо его свойства) до того, как оно будет сгенерировано.
  3. Протокол должен быть жизнеспособным, то есть устойчивым к тому, что какой-то процент участников отключатся от сети или намеренно попытаются остановить протокол.

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

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

RANDAO

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

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

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

Какие из свойств, которые мы описали выше, есть у RANDAO? Он непредсказуем, имеет ту же жизнеспособность, что и лежащий в его основе протокол консенсуса, но он является предвзятым. В частности, злоумышленник может наблюдать за сетью, и после того, как другие участники раскроют свои числа, он может вычислить их XOR, и решить, раскрывать или не раскрывать своё число, чтобы повлиять на результат. В то время как это не позволяет злоумышленнику единолично определить вывод генератора случайных чисел, это все еще дает ему 1 бит влияния. А если злоумышленники управляют несколькими участниками, то число контролируемых ими битов будет равно числу участников под их управлением.

Влияние злоумышленников можно сильно уменьшить, если требовать, что участники вскрывают числа по-порядку. Тогда злоумышленник сможет повлиять на исход только если он вскрывается последним. В то время как влияние значительно меньше, алгоритм все еще является предвзятым.

RANDAO + VDF

Один из вариантов, как сделать RANDAO непредвзятым, состоит в следующем: после того, как все числа вскрыты, и XOR посчитан, его результат подается на вход функции, которая занимает очень много времени, чтобы ее вычислить, но позволяет проверить правильность вычисления очень быстро.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Такая функция называется Verifiable Delay Function, или VDF. Если вычисление окончательного результата занимает больше времени, чем этап раскрытия чисел, то злоумышленник не сможет предсказать эффект от демонстрации или утаивания своего числа, а следовательно он потеряет возможность влиять на результат.

Разработка хороших VDF чрезвычайно сложна. В последнее время было сделано несколько прорывов, например этот и этот, которые сделали VDF более применимыми на практике, и Ethereum 2.0 в долгосрочной перспективе планирует использовать RANDAO с VDF в качестве источника случайных чисел. Помимо того факта, что этот подход непредсказуем и непредвзят, у него есть дополнительное преимущество, которое заключается в жизнеспособности, если хотя бы два участника доступны в сети (при условии, что используемый протокол консенсуса жизнеспособен при работе с таким небольшим количеством участников).

Самая большая сложность этого подхода заключается в такой настройке VDF, чтобы даже участник с очень дорогим специализированным оборудованием не смог вычислить VDF до окончания фазы раскрытия. В идеале алгоритм должен иметь даже значимый запас прочности, скажем, 10x. На рисунке ниже показана атака участника, имеющего специализированный ASIC, который позволяет ему запускать VDF быстрее, чем время, выделенное для раскрытия подтверждения RANDAO. Такой участник может по-прежнему вычислять конечный результат используя и не используя своё число, и после этого, на основе расчетов, выбирать, показывать его или нет.

Для упомянутого выше семейства VDF производительность специализированного ASIC может быть в 100+ раз выше, чем у обычного оборудования. Таким образом, если фаза раскрытия длится 10 секунд, то VDF, вычисляемая на такой ASIC, должна занимать более 100 секунд, чтобы иметь 10-кратный запас безопасности, и, таким образом, тот же VDF, вычисленный на обычном оборудовании, должен занять 100 x 100 секунд = ~ 3 часа.

Ethereum Foundation планирует решить эту проблему за счет создания собственных общедоступных бесплатных ASIC. Как только это произойдет, все другие протоколы также могут использовать преимущества этой технологии, но до тех пор подход RANDAO + VDF не будет столь же жизнеспособным для протоколов, которые не могут инвестировать в разработку своих собственных ASIC.

Много статей, видео и другой информации о VDF собрано на этом сайте.

Используем стирающие коды

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

Основная идея протокола заключается в следующем. Для простоты предположим, что в нем ровно 100 участников. Допустим также что у всех участников локально есть некоторый приватный ключ, и публичные ключи всех участников известны всем участникам:

  1. Каждый участник локально придумывает длинную строку, разбивает ее на 67 частей, создает стирающие коды для получения 100 долей, таких, что любых 67 достаточно для восстановления строки, назначает каждую из 100 долей одному из участников и шифрует их с помощью открытого ключа того же участника. Затем все закодированные доли публикуются.
  2. Участники используют некоторый консенсус, чтобы достичь согласия о закодированных наборах от конкретных 67 участников.
  3. Как только консенсус достигнут, каждый участник берет закодированные доли в каждом из 67 наборов, зашифрованные их открытым ключом, расшифровывает все такие доли и публикует все такие расшифрованные доли.
  4. Как только 67 участников выполнили шаг (3), все согласованные наборы могут быть полностью декодированы и восстановлены благодаря свойствам стирающих кодов, и окончательное число может быть получено как XOR начальных строк, с которых участники начали в (1).

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

Что происходит, если на шаге (1) один из участников отправил другим участникам закодированные доли, которые не являются корректным стирающим кодом некоторой строки? Без дополнительных изменений разные участники либо не смогут восстановить строку совсем, либо восстановят разные строки, что приведет к тому, что разные участники получат разное случайное число. Чтобы это предотвратить, можно сделать следующее: каждый участник, помимо закодированных долей, вычисляет также дерево меркла всех таких долей, и каждому участнику посылает как саму закодированную долю, так и корень дерева меркла, и доказательство включения доли в дерево меркла. В консенсусе на шаге (2) затем участники не просто соглашаются на множестве наборов, но на множестве конкретных корней таких деревьев (если некоторый участник отошел от протокола, и отправил разные корни дерева меркла разным участникам, и два таких корня показаны во время консенсуса, его строка не включается в результирующий набор). По итогу консенсуса мы будем иметь 67 закодированных строк и соответствующих им корней дерева меркла таких, что есть хотя бы 67 участников (не обязательно тех же кто предложили соответствующие строки), у которых для каждой из 67 строк есть сообщение с долей стирающего кода, и доказательство вхождения их доли в соответствующее дерево меркла.

Когда на шаге (4) участник расшифровывает 67 долей для некоторой строки, и пытается по ним восстановить оригинальную строку, возможен один из вариантов:

  1. Строка восстанавливается, и если ее затем закодировать стирающими кодами опять, и посчитать дерево меркла для посчитанных локально долей, корень совпадает с тем, на котором достигнут консенсус.
  2. Строка восстанавливается, но посчитанный локально корень не соответствует тому, на котором достигнут консенсус.
  3. Строка не восстанавливается.

Легко показать, что если хотя бы для одного участника выше случился вариант (1), то для всех участников случится вариант (1), и наоборот, если хотя бы для одного участника случился вариант (2) или (3), то для всех участников случится вариант (2) или (3). Таким образом, для каждой строки в наборе либо все участники успешно ее восстановят, либо все участники не смогут ее восстановить. Затем результирующее случайное число – это XOR только тех строк, которые участники смогли восстановить.

Пороговые подписи

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

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

Частое применение для BLS-подписей в протоколах блокчейна, помимо генерации случайных чисел, – это подписывание блоков в протоколах BFT. Скажем, 100 участников создают блоки, и блок считается окончательным, если 67 из них подписывают его. Все они могут представить свои части BLS-подписи и использовать некоторый консенсус-алгоритм, чтобы согласовать 67 из них, а затем объединить их в одну BLS-подпись. Любые 67 (или больше) частей могут быть использованы для создания итоговой подписи, которая будет зависеть от того, какие именно 67 подписей были объединены, и поэтому может различаться, но не смотря на то, что разный выбор 67-ми участников будет создавать разную подпись, любая такая подпись будет корректной подписью для блока. Остальным участникам затем достаточно получить по сети и проверить только одну подпись на каждый блок, вместо 67, что заметно понижает нагрузку на сеть.

Оказывается, что если закрытые ключи, которые используют участники, генерируются определенным образом, то независимо от того, какие 67 подписей (или больше, но никак не меньше) агрегированы, получающаяся в результате подпись будет одинаковой. Это может быть использовано в качестве источника случайности: участники сначала договариваются о некотором сообщении, которое они подпишут (это может быть вывод RANDAO или просто хэш последнего блока, на самом деле это не имеет значения, лишь бы оно каждый раз менялось и было согласованным), и создают для него BLS-подпись. Результат генерации будет непредсказуемым, пока 67 участников не предоставят свои части, а после этого выходные данные уже предопределены и не могут зависеть от действий любого участника.

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

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

Немного криптографии

Для того, чтобы понять, как работают пороговые подписи, надо понимать немного базовой криптографии. Мы будем использовать две концепции: скаляры, или просто числа, которые мы будем обозначать строчными буквами (x, y) и точки на эллиптической кривой, которые мы будем обозначать прописными буквами.

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

  1. Точки на эллиптической кривой можно складывать и умножать на скаляр (умножение на скаляр мы будем обозначать как xG, хотя нотация Gx тоже часто используется в литературе). Результат сложения и умножения на скаляр — это точка на эллиптической кривой.
  2. Зная только точку G и ее произведение со скаляром xG нельзя вычислить x.

Мы будем также использовать концепцию полинома p(x) степени k-1. В частности, мы будем использовать следующее свойство полиномов: если мы знаем значение p(x) для любых различных (и не имеем больше никакой информации о p(x)), мы можем вычислить p(x) для любого другого x.

Интересно, что для любого полинома p(x) и некоторой точки на кривой G, зная значение p(x)G для любых k различных значений x, можно также вычислить p(x)G для любой x.

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

Генератор случайных чисел на пороговых подписях

Допустим что n участников хотят сгенерировать случайное число, и мы хотим, чтобы участие любых k из них было достаточно чтобы сгенерировать число, но чтобы злоумышленники, которые контролируют k-1 или меньше участников, не могли предсказать или повлиять на сгенерированное число.

Допустим существует такой полином p(x) степени k-1, что первый участник знает p(1), второй знает p(2), и так далее (n-ый знает p(n)). Также допустим, что для некоторой заранее определенной точки G все знают p(x)G для всех значений x. Мы будем называть p(i) “приватной компонентой” i-ого участника (потому что только i-ый участник знает ее), и p(i)G “публичной компонентой” i-ого участника (потому что все участники знают ее). Как вы помните, знание p(i)G не достаточно чтобы восстановить p(i).

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

Как мы можем использовать такой полином, чтобы сгенерировать случайное число? Для начала нам нужно некоторая строка, которая прежде не использовалась как вход для генератора. В случае блокчейна хеш последнего блока h — хороший кандидат для такой строки. Пусть участники хотят создать случайное число, используя как seed. Сначала участники конвертируют h в точку на кривой используя любую заранее определенную функцию:

H = scalarToPoint(h)

Затем каждый участник i вычисляет и публикует Hi = p(i)H, что они могут сделать, потому что они знают p(i) и H. Раскрытие Hi не позволяет другим участникам восстановить приватную компоненту i-ого участника, и поэтому один набор приватных компонент можно использовать от блока к блоку. Таким образом, дорогой алгоритм создания полинома, описанный ниже, необходимо выполнить только однажды.

Когда k участников вскрыли Hi = p(i)H, все могут вычислить Hx = p(x)H для всех x благодаря свойству полиномов, которые мы обсудили в прошлом разделе. В этот момент все участники вычисляют H0 = p(0)H, и это и есть результирующее случайное число. Обратите внимание, что никто не знает p(0), и следовательно единственный способ посчитать p(0)H – это интерполяция p(x)H, что возможно только когда k значений p(i)H известны. Вскрытие любого меньшего количества p(i)H не дает никакой информации о p(0)H.

Генератор выше имеет все свойства, которые мы хотим: злоумышленники, контролирующие только k-1 участников, или меньше, не имеют никакой информации и влияния на вывод, в то время как любые k участников могут вычислить результирующее число, и любое подмножество из k участников всегда придут к одному и тому же результату для одного и того же seed.

Есть одна проблема, которую мы аккуратно обошли стороной выше. Чтобы интерполяция работала, важно чтобы значение Hi которое опубликовал каждый участник i действительно было равно p(i)H. Так как никто кроме i-ого участник не знает p(i), никто кроме i-ого участника не может проверить что Hi действительно посчитано правильно, и без какого-то криптографического доказательства корректности Hi злоумышленник может опубликовать любое значение в качестве Hiи произвольно влиять на вывод генератора случайных чисел:

Разные значения H_1, отправленные первым участником, приводят к разным результирующим H_0
Разные значения H_1, отправленные первым участником, приводят к разным результирующим H_0

Есть по меньшей мере два способа доказать корректность Hi, мы их рассмотрим после того, как разберем генерацию полинома.

Генерация полинома

В прошлом разделе мы допустили, что у нас есть такой полином p(x) степени k-1 что участник i знает p(i), и никто другой не имеет никакой информации об этом значении. В следующем разделе нам также будет необходимо чтобы для некоторой заранее определенной точки G все знали p(x)G для всех x.

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

Один возможный протокол генерации полинома следующий:

  1. Каждый участник i локально создает произвольный полином pi(x) степени k-1. Они затем посылают каждому участнику j значение pi(j), зашифрованное публичным ключом XjТаким образом только i-ый и j-ый участник знают pi(j). Участник i также публично анонсирует pi(j)G для всех j от 1 до k включительно.
  2. Все участники используют некоторый консенсус чтобы выбрать k участников, чьи полиномы будут использоваться. Так как некоторые участники могут быть оффлайн, мы не можем ждать пока все n участников опубликуют полиномы. Результат этого шага – множество Z состоящее из хотя бы k полиномов, созданных на шаге (1).
  3. Участники убеждаются, что известные им значения pi(j) соответствуют публично анонсированным pi(j)G. После этого шага в должны остаться только полиномы, для которых приватно переданные pi(j) соответствуют публично анонсированным pi(j)G.
  4. Каждый участник j вычисляет свою приватную компоненту p(j) как сумму pi(j) для всех i в Z. Каждый участник также вычисляет все значения p(x)G как сумму pi(x)G для всех i в Z.

Обратите внимание, что p(x) – это действительно полином степени k-1, потому что это сумма отдельных pi(x), каждый из которых – это полином степени k-1. Затем, обратите внимание, что в то время как каждый участник j знает p(j), у них нет никакой информации об p(x) для x ≠ j. Действительно, чтобы вычислить это значение, им необходимо знать все pi(x), и покуда участник j не знает хотя бы один из выбранных полиномов, у них нет достаточной информации об p(x).

Это весь процесс генерации полинома, который был необходим в прошлом разделе. Шаги 1, 2 и 4 выше имеют достаточно очевидную реализацию. А вот шаг 3 не такой тривиальный.

Конкретно, нам нужно уметь доказывать, что зашифрованные pi(j) действительно соответствуют опубликованным pi(j)G. Если мы не можем это доказать, злоумышленник i может послать мусор вместо pi(j) участнику j, и участник не сможет получить настоящее значение pi(j), и не сможет вычислить свою приватную компоненту.

Есть криптографический протокол, который позволяет создать дополнительное сообщение proofi(j), такое что любой участник, имея некоторое значение e, а также proofi(j) и pi(j)G, может локально убедиться, что e – это действительно pi(j), зашифрованное ключом участника j. К сожалению, размер такого доказательства невероятно большой, и учитывая что необходимо опубликовать O(nk) таких доказательств, использовать их для этой цели не получится.

Вместо того, чтобы доказывать, что pi(j) соответствует pi(j)G мы можем в протоколе генерации полинома отвести очень большой промежуток времени, во время которого все участники проверяют полученные зашифрованные pi(j), и если расшифрованное сообщение не соответствует публичному pi(j)G, они публикуют криптографическое доказательство того, что полученное ими зашифрованное сообщение неверно. Доказать, что сообщение не соответствует pi(G) намного проще, чем доказать, что оно соответствует. Следует отметить, что это требует, чтобы каждый участник появился в сети хотя бы раз за время, отведенное на создание таких доказательств, и полагается на предположение, что если они такое доказательство опубликовали, оно достигнет всех остальных участников за это же отведенное время.

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

Доказательства корректности H_i

Последняя часть, которую осталось обсудить, это как доказать корректность опубликованных Hi, а именно что Hi = p(i)H, без вскрытия p(i).

Вспомним, что значения H, G, p(i)G публичны и известны всем. Операция получения p(i) зная p(i)G и G называется дискретный логарифм, или dlog, и мы хотим доказать, что:

dlog(p(i)G, G) = dlog(HiH)

без разглашения p(i). Конструкции для таких доказательств существуют, например Schnorr Protocol.

С такой конструкцией, каждый участник вместе с Hi отправляет доказательство корректности согласно конструкции.

Когда случайное число сгенерировано, его часто нужно использовать участникам, отличным от тех, кто его сгенерировал. Таким участникам вместе с числом необходимо отправлять все Hi и сопутствующие доказательства.

Пытливый читатель может спросить: так как финальное случайное число – это H0, и p(0)G – это публичная информация, зачем нужно доказательство для каждого отдельного Hi, почему вместо этого не отправить доказательство того, что

dlog(p(0)G, G) = dlog(H0H)

Проблема, что с помощью Schnorr Protocol нельзя создать такое доказательство, потому что никто не знает значение p(0), необходимое для создания доказательства, и более того, весь генератор случайных чисел основан на том, что никто не знает это значение. Поэтому необходимо иметь все значения Hi и их индивидуальные доказательства, чтобы доказать корректность H0.

Однако, если бы на точках на эллиптических кривых была бы какая-то операция, которая семантически схожа с умножением, доказательство корректности H0 было бы тривиальным, мы бы просто убедились, что

H0 × G = p(0)G × H

Если выбранная кривая поддерживает elliptic curve pairings, такое доказательство работает. В этом случае H0 – это не только вывод генератора случайных чисел, который может проверить любой участник, который знает G, H и p(0)G. H0 – это еще и подпись на сообщении, которое использовалось как seed, подтверждающая, что k и участников подписали это сообщение. Таким образом, если seed – это хеш блока в протоколе блокчейна, то H0 – это одновременно мульти-подпись на блоке, и очень хорошее случайное число.

В заключение

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

Код протокола открыт, наша реализация написана на Rust, её можно найти тут.

Посмотреть как выглядит разработка под NEAR, и поэкспериментировать в онлайн-IDE можно здесь.

источник