Случайные числа и децентрализованные сети: практическое применение16.04.2019 17:02

Введение

«Генерация случайных чисел слишком важна, чтобы оставлять её на волю случая»
Роберт Кавью, 1970

Эта статья посвящена практическому применению решений, использующих коллективную генерацию случайных чисел в недоверенной среде. Если кратко — как и для чего используется рандом в блокчейнах, и немного про то, как отличить «хороший» рандом от «плохого». Генерация действительно случайного числа является крайне непростой проблемой даже на отдельном компьютере, и давно изучается криптографами. Ну, а в децентрализованных сетях генерация случайных чисел еще более сложна и важна.

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

Генерация случайных чисел

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

Чтобы завершить краткий ликбез, добавлю, что генерация случайных чисел даже на одном устройстве — один из столпов обеспечения безопасности наших с вами данных, сгенерированные псевдослучайные числа используются при установлении защищенных соединений в различных сетях, для генерации криптографических ключей, для балансировки нагрузки, контроля целостности, и еще для множества применений. Безопасность многих протоколов зависит от возможности сгенерировать надежный, непредсказуемый извне рандом, сохранить его, и не раскрывать его до следующего шага протокола, иначе безопасность будет поставлена под угрозу. Атака на генератор псевдослучайных значений является крайне опасной и ставит под угрозу сразу все ПО, использующее генерацию рандомов.

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

Рандом в блокчейнах

В первую очередь я буду говорить про блокчейны с поддержкой смарт-контрактов, именно они могут в полной мере использовать возможности, предоставляемые качественным неоспоримым рандомом. Далее, для краткости, я буду называть эту технологию »Publicly Verifiable Random Beacons» или PVRB. Так как блокчейны — это сети, информацию в которой может проверить любой участник, ключевой частью названия является «Publicly Verifiable», т.е. любой желающий может при помощи вычислений получить доказательство того, что полученное число, размещенное в блокчейне, обладает такими свойствами:

Результат должен иметь доказуемо равномерное распределение, т.е основан на доказуемо стойкой криптографии.
Невозможно контролировать ни один из битов результата. Как следствие, результат не может быть заранее предсказан.
Нельзя саботировать протокол генерации за счет неучастия в протоколе или путем перегрузки сети атакующими сообщениями
Все вышеперечисленное должно быть стойким к сговорам допустимого числа нечестных участников протокола (например ⅓ участников).

Любая возможность сговорившейся минорной группы участников произвести даже контролируемый чётный/нечётный рандом — дыра в безопасности. Любая возможность группы остановить выдачу рандома — дыра в безопасности. В общем, проблем много, и эта задачка не из легких…

Кажется, что наиболее важное применение для PVRB, это различные игры, лотереи, и вообще любые виду gambling-а на блокчейне. Действительно, это важное направление, но у рандома в блокчейнах есть применения и поважнее. Рассмотрим их.

Алгоритмы консенсуса

PVRB для организации сетевого консенсуса играет огромное значение. Транзакции в блокчейнах защищены электронной подписью, поэтому «атака на транзакцию» это всегда включение/исключение транзакции в блок (или в несколько блоков). А главной задачей алгоритма консенсуса является договориться о порядке этих транзакций и о порядке блоков, которые включают в себя эти транзакции. Также, необходимым свойством для реальных блокчейнов является финальность — возможность сети договориться о том, что цепочка до финализированного блока является окончательной, и никогда не будет исключена из за появления нового форка. Обычно, чтобы договориться о том, что блок является валидным и, главное, финальным, требуется собрать подписи с большинства производителей блоков (далее BP — block-producers), что требует как минимум доставить цепочку блоков на все BP, а подписи распространить между всеми BP. При росте числа BP, количество необходимых сообщений в сети экспоненциально растет, поэтому, алгоритмы консенсуса, требующие финальность, используемые например в pBFT-консенсусе Hyperledger, не работают с нужной скоростью, начиная уже с нескольких десятков BP, требуя огромного числа соединений.

Если в сети имеется неоспоримый и честный PVRB, то, даже в самом простом приближении, можно на основании него выбирать одного из block producers и назначать его «лидером» в течение одного раунда протокола. Если у нас есть N block producer-ов, из которых M: M > 1/2 N являются честными, не цензурируют транзакции и не строят форки цепочки с целью проведения атаки «double spend», то использование равномерно распределенного неоспоримого PVRB позволит выбирать честного лидера с вероятностью M / N (M / N > 1/2). Если каждому лидеру назначить собственный временной интервал, в течение которого он может произвести блок и провалидировать цепочку, и эти интервалы равны по времени, то цепочка блоков честных BP будет длиннее, чем цепочка, сформированная зловредными BP, и алгоритм консенсуса, полагающийся на длину цепочки, попросту отбросит «плохую». Этот принцип выделения равных квантов времени каждому BP впервые был применен в Graphene (предшественнике EOS), и позволяет большинство блоков закрывать одной подписью, что очень сильно снижает сетевую нагрузку и позволяет этому консенсусу работать крайне быстро и устойчиво. Тем не менее, сети EOS сейчас приходится использовать специальные блоки (Last Irreversible Block), которые подтверждаются подписями 2/3 BP. Эти блоки служат для обеспечения финальности (невозможности появления форка цепочки, начинающегося раньше последнего Last Irreversible Block).

Также, в реальных имплементациях, схема протокола сложнее — голосования за предлагаемые блоки проводятся в несколько этапов, чтобы поддерживать работу сети в случае пропуска блоков и проблем с сетью, но даже с учетом этого, алгоритмы консенсуса с использованием PVRB требуют существенно меньше сообщений между BP, что позволяет сделать их быстрее, чем традиционный PВFT, или различные его модификации.

Наиболее яркий представитель таких алгоритмов: Ouroboros от команды Cardano, который, как объявлено, обладает математически доказуемой стойкостью к наличию сговора среди BP.

В Ouroboros PVRB используется для определения так называемого «BP schedule» — расписания, согласно которому каждому BP назначается свой временной слот для публикации блока. Большим преимуществом использования PVRB является полное «равноправие» BP (согласно размерам их балансов). Честность PVRB гарантирует, что зловредные BP не могут контролировать расписание временных слотов, и, поэтому не могут манипулировать цепочкой, заранее подготавливая и анализируя форки цепочки, а для выбора форка достаточно полагаться просто на длину цепочки, не оперируя хитрыми способами вычисления «полезности» BP и «веса» его блоков.

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

Масштабирование и балансировка нагрузки

PVRB может принести серьезную пользу также в задачах для снижения нагрузки, масштабирования платежей. Для начала имеет смысл ознакомиться со статьей Ривеста «Electronic Lottery Tickets as Micropayments». Общая суть такова, что вместо того чтобы делать 100 платежей по 1c от плательщика получателю, можно сыграть в честную лотерею с призом 1$ = 100c, где плательщик при каждом платеже в 1c передает банку один из 100 своих «лотерейных билетов». Один из этих билетов выигрывает банку 1$, и именно этот билет получатель может фиксировать в блокчейне. Самое важное, что остальные 99 билетов передаются между получателем и плательщиком без всякого внешнего участия, по приватному каналу и с любой нужной скоростью. Хорошее описание протокола на базе этой схемы в сети Emercoin можно прочитать здесь.

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

Выбор случайного участника крайне важен также для протоколов шардинга, целью которых является горизонтальное масштабирование цепочки блоков, позволяя разным BP процессить лишь свой scope транзакций. Это крайне сложная задача, особенно в вопросах безопасности при объединении шардов. Честный выбор случайного BP с целью назначения его ответственных за конкретный шард, как и в алгоритмах консенсуса — также задача PVRB. В централизованных системах шарды назначаются балансировщиком, он просто вычисляет хеш от запроса и отправляет необходимому исполнителю. В блокчейнах, возможность влиять на это назначение может вести к атаке на консенсус. Например, содержимое транзакций может контролироваться атакующим, он может контролировать какие транзакции попадают в контролируемый им шард и манипулировать цепочкой блоков в нем. Обсуждение проблемы использования случайных чисел для задач шардинга в Ethereum можно почитать здесь
Шардинг — это одна из самых амбициозных и серьезных задач в области блокчейн, ее решение позволит строить децентрализованные сети фантастической производительности и объема. PVRB — это лишь один из важных блоков, для ее решения.

Игры, экономические протоколы, арбитраж

Роль случайных чисел в игровой индустрии сложно переоценить. Явное использование в онлайн казино, и неявное при расчете эффектов того или иного действия игрока — всё это крайне сложные проблемы для децентрализованных сетей, где нет возможности положиться на центральный источник случайности. Но, случайный выбор может решать и многие экономические проблемы и помогать строить более простые и эффективные протоколы. Предположим в нашем протоколе имеют место диспуты насчет оплаты каких нибудь недорогих услуг, и эти диспуты происходят достаточно редко. В этом случае, если есть неоспоримый PVRB, клиенты и продавцы могут договориться о случайном разрешении диспутов, но с заданной вероятностью. К примеру с вероятностью 60% побеждает клиент, а с вероятностью 40% — продавец. Такой, с первой точки зрения абсурдный, подход позволяет автоматически решать диспуты с точно предсказуемой долей выигрышей/проигрышей, устраивающий обе стороны без всякого участия третьей стороны и ненужной траты времени. Более того, соотношение вероятностей может быть динамическим и зависеть от некоторых глобальных переменных. К примеру, если у компании дела идут хорошо, отмечается низкое число диспутов и высокая доходность, компания может автоматически сдвигать вероятность разрешения диспута в сторону клиент-ориентированности, к примеру 70/30 или 80/20, и наоборот, если диспуты отнимают много средств и являются мошенническими или неадекватными, можно сдвигать вероятность в другую сторону.

Большое количество интересных децентрализованных протоколов, таких как token currated registries, prediction markets, bonding curves и многие другие представляют собой экономические игры, в которых награждается хорошее поведение, и штрафуется плохое. В них часто встречаются проблемы безопасности, защиты от которых противоречат друг другу. То, что защищено от атаки «китов» с миллиардами токенов («big stake»), уязвимо к атакам тысячами аккаунтов с небольшими балансами («sybil stake»), и меры, принимаемые против одной атаки, например нелинейные комиссии, созданные для того, чтобы сделать работу большим стейком невыгодной, обычно дискредитируются другой атакой. Так как речь идет об экономической игре, соответствующие статистические веса можно рассчитать заранее, и просто заменить комиссии на рандомизированные с соответствующим распределением. Такие вероятностные комиссии реализуются крайне просто, если в блокчейне есть надежный источник рандома и не требуют никаких сложных вычислений, осложняя жизнь и китам и sybil-ам.
При этом необходимо продолжать помнить, что контроль над единственным битом в этом рандоме позволяет обманывать, уменьшая и увеличивая вероятности вдвое, так что честный PVRB — важнейшая составляющая таких протоколов.

Где найти правильный рандом?

В теории, честный случайный выбор в децентрализованных сетях позволяет обеспечить доказуемую безопасность почти любого протокола от сговора. Обоснование довольно простое — если сеть договаривается об одном бите 0 или 1, и среди участников менее половины являются нечестными, то, при достаточном количестве итераций, сеть гарантированно придет к консенсусу относительно этого бита с фиксированной вероятностью. Просто потому что честный рандом будет выбирать 51 из 100 участников в 51% случаев. Но это в теории, т.к. в реальных сетях, для обеспечения такого уровня безопасности, как в статьях, требуется множество сообщений между хостами, сложная многоходовая криптография, а любое усложнение протокола сразу же добавляет новые вектора атак.
Именно поэтому мы пока не видим в блокчейнах доказанно стойкого PVRB, который использовался бы уже достаточно времени, чтобы пройти испытания настоящими приложениями, множественными аудитами, нагрузками, и конечно, же, реальными атаками, без которых трудно назвать продукт по настоящему безопасным.

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