Публичная случайность и маяки случайности

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

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

Желаемые свойства

Генерация случайных чисел — заведомо тонкая задача. Например, многие криптографические ключи утекли из-за того, что они полагался на неисправный генератор случайных чисел (для чего стена Cloudflare лавовые лампы послужило бы творческим смягчением). Это просто частная случайность, однако, когда только одна сторона должна создать и использовать его.

Общественная случайность, напротив, представляет собой многосторонний процесс, что значительно усложняет его. Хороший протокол для создания публичной случайности должен обладать следующими свойствами безопасности:

• Беспристрастный: ни злоумышленник, ни коалиция злоумышленников не должны иметь возможности повлиять на вывод. 
• Надежные: Злоумышленник не должен помешать выходу протокола.
• проверяемый: Любой может легко проверить вывод протокола и должен видеть тот же вывод, что и все остальные.
• Непредсказуемый: Если протокол выдает вывод вовремя T₁, никто не должен быть в состоянии предсказать что-либо о выводе раньше некоторого времени. T₀<T₁, в идеале с T₀ очень близко к T₁.

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

В дополнение к этим свойствам протокол должен быть эффективным для запуска и создания большого количества случайных битов. (На практике приложениям часто бывает достаточно создать 128 случайных битов, используя их для заполнения генератора псевдослучайных чисел [PNRG] для вывода большего количества битов по мере необходимости. Однако непредсказуемость должна сохраняться для каждого отдельного бита вывода, чтобы его можно было использовать для таких таких приложений, как лотереи или распределение ресурсов.) В идеале протокол также должен быть эффективным с точки зрения затрат на связь и вычисления.

Различные протоколы могут достигать этих свойств в разных условиях. Например, некоторые протоколы могут быть беспристрастными для любой коалиции f₁ злонамеренные узлы и непредсказуемы любой коалицией f₂<f₁ вредоносные узлы. Существуют также различные степени предвзятости. Например, в некоторых протоколах участник может смещать вывод на «один бит», то есть он может выбирать между одним из двух возможных выходов. Другие атаки могут позволить им полностью исправить вывод. Однако, как правило, мы вообще не хотим мириться с какой-либо предвзятостью (или предсказуемостью).

Криптографический идеал: Rмаяки

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

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

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

• Централизованные маяки: Самый простой подход к созданию хорошей случайности — через централизованную третью сторону с такими услугами, как Маяк случайности NIST or random.org, который генерирует случайность из атмосферного шума и аккредитован для использования в азартных играх. Эта зависимость от третьей стороны полностью подрывает философию децентрализации. Действительно, в приведенном выше примере мы должны верить, что соответствующие организации правильно генерируют случайность без каких-либо криптографических доказательств.
• Дисплеи физической случайности: Многие традиционные лотереи полагаются на публичную демонстрацию, которая может включать, например, то, что кто-то тянется к контейнеру с шариками для пинг-понга с разными номерами на них. К сожалению, ими часто легко манипулировать. Например, некоторые шарики можно положить в морозилку и селектору можно сказать выбрать холодные.
• Природные маяки: распространенная идея состоит в том, чтобы использовать случайные природные явления, такие как погода или космическое фоновое излучение, в качестве маяка. К сожалению, все предложенные источники не дают четкого консенсуса. Разные наблюдатели увидят немного разные значения, что требует повторного введения доверенной стороны для проведения официальных измерений со всеми недостатками централизованного маяка.
• Полуцентрализованные маяки: Лучшим подходом было бы получить случайность от Заголовки биткойн-блоков прямо или из цены закрытия акций, что легче публично проверить и сложнее полностью контролировать какой-либо одной стороне. Тем не менее, тонкие атаки все еще существуют на обоих случайность блокчейна с доказательством работы и случайность курса акций. Например, с помощью заголовков блокчейна майнеры могут удерживать блоки, заголовки которых создают значение маяка, которое им не нравится. Или они могут разорвать связи, когда будут найдены два сталкивающихся блока, основываясь на предпочитаемых ими выходных данных маяка.

Децентрализованные маяки случайности (DRB)

Естественным подходом к проблемам централизованных маяков является разработка децентрализованного криптографического протокола для создания общедоступной случайности. Эта проблема чем-то похожа на разработку децентрализованных протоколов консенсуса, только сложнее. Мало того, что все участники должны согласиться с выводом (случайность), но для злонамеренного участника протокола должно быть невозможно предвзято или предсказать вывод.

Протоколы, предназначенные для имитации маяка случайности, называются распределенными маяками случайности (DRB). (Другие названия включают «распределенное подбрасывание монеты».) Эта проблема изучается десятилетиями. знаменитые результаты невозможности, доказанные в 1980-х годах, но интерес возродился в эпоху блокчейна. DRB можно использовать для обеспечения случайности в цепочке, что станет ключевым компонентом честных, безопасных и прозрачных приложений в цепочке.

Классический подход: протоколы Commit-Reveal

В оптимистичном случае для DRB достаточно очень простого двухраундового протокола. В 1 туре каждый участник i генерирует случайное значение r_i и публикует криптографическое обязательство c_i=Совершить(r_i). В этом приложении обязательство может быть просто хеш-функцией, такой как SHA-256. После того, как обязательство каждого участника опубликовано, они ограничиваются своим выбором. r_i, но обязательства не раскрывают никакой информации о вкладах других участников. Во втором раунде каждый участник «открывает свое обязательство», публикуя r_i. Затем все случайные значения объединяются, например, с помощью операции XOR или (предпочтительнее) хеширования их конкатенации.

Этот протокол прост и выдает случайный сигнал маяка, пока хотя бы один из участников выбирает свою r_i случайно. К сожалению, он страдает классическим недостатком: когда все участники, кроме одного, раскрыли свое случайное значение, последний участник может вычислить предполагаемый результат маяка. Если им это не нравится, они могут отказаться публиковать свое значение, прервав протокол. Игнорирование вклада ошибочного участника не решает проблему, потому что это по-прежнему дает злоумышленнику выбор между двумя выходными сигналами маяка (один рассчитывается с их вкладом, а другой — без).

Блокчейны предлагают естественное решение этой проблемы: от каждого участника могут потребовать положить часть средств на условное депонирование, которые будут конфискованы, если они не раскроют свой случайный вклад. Это был именно тот подход, которого придерживался классик. РАНДАО маяк на Эфириуме. Недостатком этого подхода является то, что выходные данные все еще могут быть смещенными, что может быть выгодно злоумышленнику с финансовой точки зрения, если деньги на условном депонировании меньше, чем сумма денег, зависящая от результата маяка. Лучшая защита от предвзятых атак требует размещения большего количества монет на условном депонировании.

Протоколы фиксации-раскрытия-восстановления

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

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

Возможны несколько других механизмов восстановления, но все они имеют одно и то же ограничение. Если есть N участников, и нам нужна устойчивость, если какая-либо группа до f узлов выпадает, то должно быть так, что любая группа Нф участники могут вычислить окончательный результат. Но это также означает злонамеренную коалицию Нф участники могут заранее предсказать результат, в частном порядке моделируя механизм восстановления. Это также может произойти во время первого раунда протокола, в течение которого такая коалиция может изменить свой собственный выбор случайности и исказить результат. 

Иными словами, это означает любую коалицию Нф узлы должны включать хотя бы один честный узел. По простой алгебре Нф > ф, так f < N/2, и эти протоколы по своей сути требуют честного большинства. Это существенное отличие от исходной модели безопасности фиксации-раскрытия, которая требует только f<N (минимум один честный участник).

Эти протоколы также часто требуют значительных затрат на связь для обмена дополнительной информацией PVSS между всеми узлами при каждом запуске протокола. Исследовательское сообщество проделало значительную работу по этой проблеме за последние несколько лет, с исследовательскими предложениями, включая RandShare, скрести, секранд, ТРАВЫили Альбатрос, но, похоже, ни один из них не видел реального развертывания.

Поддающиеся проверке протоколы на основе случайных функций

Понимая, что группа Нф участники могут вычислить случайное значение маяка в приведенном выше протоколе, что приводит к несколько более простому подходу: обмен долгосрочным секретным ключом между N сторон и попросить их использовать его для оценки проверяемая случайная функция (ВРФ). Секретный ключ передается через t-снаружи-N пороговая схема, так что любая t участники могут вычислить VRF (но меньшая коалиция не может). За t=Нф, это обеспечивает такую ​​же устойчивость к f вредоносных узлов в качестве описанных выше протоколов фиксации-раскрытия-восстановления.

DFINITY был пионером в этом подходе как часть их консенсусного протокола с использованием пороговых сигнатур BLS (которые функционируют как VRF). Автономный дранд Маяк случайности использует по существу тот же подход с набором пороговых участников BLS, подписывающих счетчик в каждом раунде. Лига энтропии представляет собой экземпляр drand с открытым исходным кодом, производящий случайность каждые 30 секунд с использованием 16 участвующих узлов (по состоянию на сентябрь 2022 г.), которым управляют различные компании и исследовательские группы университетов. 

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

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

Цепная связь VRF комбинаты этот подход (с использованием НСЕК5 VRF) с внешним источником случайности, указанным сторонами, запрашивающими случайность, на практике обычно это недавний заголовок блокчейна. Затем эти данные передаются через VRF, который управляется либо одной стороной, либо пороговым значением для группы.

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

Поддающиеся проверке протоколы на основе функции задержки

Наконец, многообещающим новым направлением является использование криптографии на основе времени, в частности проверяемых функций задержки (VDFs). Этот подход обещает обеспечить хорошую эффективность и надежность связи с устойчивостью к N-1 вредоносные узлы. 

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

С современными VDF возможен еще более элегантный одноэтапный протокол: полностью отказаться от обязательств. Каждый участник может просто опубликовать свой случайный вклад r_i, а окончательный результат представляет собой комбинацию вкладов каждого участника, пропущенных через VDF. Временная задержка при вычислении VDF гарантирует, что никто не сможет выбрать свое обязательство таким образом, чтобы исказить конечный результат. Такой подход был предложен как ЮНИКОРН Арьен Ленстра и Бенджамин Весоловски в 2015 году, и действительно было ключевым мотивирующим приложением в разработка VDF.

Этот подход нашел некоторое практическое применение. Чиа реализует версию этого как часть своего консенсусного протокола, используя VDF с повторным возведением в квадрат в группах классов. Starkware реализовал экспериментальный маяк на основе VDF с использованием VDF на основе SNARK. Эфириум также планирует использовать этот подход, создание специальной ASIC для вычисления VDF для генерации случайности на уровне консенсуса.

Публичная случайность является важным компонентом многих протоколов, но нам по-прежнему не хватает стандартного DRB, обеспечивающего высокий уровень безопасности. Пространство дизайна велико, и возможны многие гибриды и комбинации вышеперечисленных подходов. Например, можно комбинировать протокол на основе VRF с протоколом на основе VDF, что добавляет новую энтропию, например, как это было предложено Раннер. Beacon Chain Ethereum в настоящее время использует VRF, хотя в будущем она может добавить VDF, чтобы исключить возможность предвзятости из-за атак с блокировкой.

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

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

Жозеф Бонно является партнером по исследованиям в a16z crypto. Его исследования сосредоточены на прикладной криптографии и безопасности блокчейна. Он читал курсы по криптовалюте в Мельбурнском университете, Нью-Йоркском университете, Стэнфорде и Принстоне, получил докторскую степень в области компьютерных наук в Кембриджском университете и степень бакалавра/магистра в Стэнфорде.

Валерия Николаенко является партнером по исследованиям в a16z crypto. Ее исследования сосредоточены на криптографии и безопасности блокчейна. Она также работала над такими темами, как дальнобойные атаки в протоколах консенсуса PoS, схемы подписи, постквантовая безопасность и многосторонние вычисления. Она имеет докторскую степень в области криптографии Стэнфордского университета под руководством профессора Дэна Боне и работала над блокчейном Diem в составе основной исследовательской группы.

Редактор: Тим Салливан

Мнения, выраженные здесь, принадлежат отдельным цитируемым сотрудникам AH Capital Management, LLC («a16z») и не являются мнением a16z или ее аффилированных лиц. Определенная информация, содержащаяся здесь, была получена из сторонних источников, в том числе от портфельных компаний фондов, управляемых a16z. Хотя информация взята из источников, считающихся надежными, a16z не проводила независимую проверку такой информации и не делает никаких заявлений о неизменной точности информации или ее уместности в данной ситуации. Кроме того, этот контент может включать стороннюю рекламу; a16z не просматривал такие рекламные объявления и не поддерживает какой-либо рекламный контент, содержащийся в них.

Этот контент предоставляется только в информационных целях и не может рассматриваться как юридическая, деловая, инвестиционная или налоговая консультация. Вы должны проконсультироваться со своими советниками по этим вопросам. Ссылки на любые ценные бумаги или цифровые активы предназначены только для иллюстративных целей и не представляют собой инвестиционную рекомендацию или предложение предоставить консультационные услуги по инвестициям. Кроме того, этот контент не предназначен и не предназначен для использования какими-либо инвесторами или потенциальными инвесторами, и ни при каких обстоятельствах на него нельзя полагаться при принятии решения об инвестировании в какой-либо фонд, управляемый a16z. (Предложение инвестировать в фонд a16z будет сделано только в меморандуме о частном размещении, договоре о подписке и другой соответствующей документации любого такого фонда, и их следует читать полностью.) Любые инвестиции или портфельные компании, упомянутые, упомянутые или описанные не являются репрезентативными для всех инвестиций в транспортные средства, управляемые a16z, и нет никаких гарантий, что инвестиции будут прибыльными или что другие инвестиции, сделанные в будущем, будут иметь аналогичные характеристики или результаты. Список инвестиций, сделанных фондами, управляемыми Andreessen Horowitz (за исключением инвестиций, в отношении которых эмитент не предоставил разрешение на публичное раскрытие информации a16z, а также необъявленных инвестиций в публично торгуемые цифровые активы), доступен по адресу https://a16z.com/investments. /.

Диаграммы и графики, представленные в нем, предназначены исключительно для информационных целей, и на них не следует полагаться при принятии каких-либо инвестиционных решений. Прошлые показатели не свидетельствуют о будущих результатах. Содержание говорит только по состоянию на указанную дату. Любые прогнозы, оценки, прогнозы, цели, перспективы и/или мнения, выраженные в этих материалах, могут быть изменены без предварительного уведомления и могут отличаться или противоречить мнениям, выраженным другими. Пожалуйста, посетите https://a16z.com/disclosures для получения дополнительной важной информации.