Привет, Хабр!

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

Зачем вообще нужно генерировать случайные числа участникам, не доверяющим друг другу? Одна из областей применения -- это децентрализованные приложения. Например, приложение, которое принимает ставку от участника и либо удваивает сумму с вероятностью 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 участников не предоставят свои части, а после этого выходные данные уже предопределены и не могут зависеть от действий любого участника.

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

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

В заключение

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

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

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

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

До скорых встреч!