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

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

Почему важны выборы лидера

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

Альтернатива выборам в комитет

Выборы комитета — связанная проблема, цель которой — выбрать равномерно случайное подмножество валидаторов некоторого фиксированного размера. k. Эта функциональность полезна сама по себе, потому что в настройках блокчейна часто требуются подкомитеты, чтобы уменьшить размер набора валидаторов, чтобы ускорить выполнение консенсуса (среди многих примеров: Жеребьевка Алгоранда и Выбор комитета Ethereum). Но выборы комитетов также полезны для выборов лидера, позволяя валидаторам избежать повторного запуска протокола выборов лидера, если избранный лидер не явится. Если вместо лидера избирается комитет с фиксированным порядком, второй член комитета может стать лидером, если первый недоступен. 

Свойства хорошего протокола выборов

В протоколе выборов лидеров лидеры должны быть непредсказуемыми. Если злоумышленник узнает, кто является будущим лидером, он может запустить атаку типа «отказ в обслуживании» (DoS), чтобы помешать ему опубликовать блок. Затем злоумышленник может уничтожить следующего лидера и так далее, остановив блокчейн. Непредсказуемость также может быть усилена, чтобы гарантировать, что сам валидатор не узнает, когда он собирается вести, что может быть важно для предотвращения взяточничества.

Процесс выбора лидера должен обладать следующими тремя свойствами:

• Справедливость: каждый честный валидатор имеет вероятность 1/N быть избранным из числа N валидаторы (расплывчатое понятие теоретико-игровая справедливость позволяет построение выбора лидера даже при наличии злонамеренного большинства, хотя и с непостоянной нижней границей числа раундов).
• непредсказуемость: противник не узнает следующего лидера до некоторого времени T до объявления лидером следующего блока.
• Уникальность: в каждом слоте выбирается ровно один лидер.

Тайные выборы лидера

Выборы тайного лидера — это непредсказуемые выборы с T = 0. В этом процессе лидер никому не известен, пока он не опубликует блок. Это полностью исключает окно для DoS-атаки: до того, как лидер обнаружит себя, злоумышленник не знает, кого атаковать, что делает его лучшую стратегию случайным предположением. А после того, как лидер публикует свой блок, атаковать уже поздно, потому что лидер уже выполнил свою ответственность перед протоколом. 

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

Хотя это очень сильная модель злоумышленника, против нее были предложены средства защиты. Алгоранд предложил модель стираний, в котором лидер фактически способен стереть в своем слоте ключ, необходимый для подписи блока до транслирует это, поэтому на самом деле уже слишком поздно атаковать к тому времени, когда лидер предпримет какие-либо публичные действия. Таддеус Драйя, Цюанькуан С. Лю и Неха Нарула, трое исследователей из MIT Media Lab, предложило что лидер вычисляет VDF в своем блоке перед широковещательной передачей, гарантируя, что адаптивный злоумышленник не сможет создать альтернативный действительный блок вовремя, чтобы он был принят для желаемого слота.

Другие методы выборов 

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

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

Текущий выборы лидера в Эфириуме является хорошим примером. Каждый новый лидер вычисляет выходные данные проверяемой функции случайности (VRF) (подпись BLS на номере эпохи) и выполняет XOR значения в миксе. Стоимость микса в конце эпохи i определяет лидеров и подкомитеты на время эпохи i+2. Лидеры и их расписание предсказуемы на одну эпоху вперед (в настоящее время ~6.4 мин). Протокол подвержен атакам на справедливость, поскольку последний лидер может решить опубликовать или скрыть свой вклад в микс и, таким образом, немного повлиять на результат следующих выборов. Если последний  k лидеры вступают в сговор, они могут ввести k  немного предвзятости и сделать выбор злонамеренных пользователей более вероятным. Ethereum Foundation активно работает над более продвинутыми методами избрания лидеров, которые мы обсудим ниже.

Выборы лидера на основе VRF

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

Оценка VRF периодически заполняется выходными данными маяка случайности, чтобы сделать менее предсказуемым для самих валидаторов возможность увидеть, какие слоты они собираются занять. Это свойство не позволяет злоумышленнику, который незаметно скомпрометирует валидатор, узнать слот, когда валидатор станет лидером, и начать атаку, когда валидатор собирается объявить блок. Этот подход также помогает предотвратить взяточничество, когда валидатор доказывает внешним сторонам, что он будет лидером в конкретном слоте, и собирает взятки в обмен на выполнение какой-либо задачи в качестве лидера (например, блокирование транзакции).

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

Но самая большая оговорка с PLE заключается в том, что может быть избрано несколько лидеров, что требует какой-то процедуры разрешения ничьих. Связи представляют собой риск для консенсуса, поскольку валидатор с выигрышным входом может сообщить об этом только половине сети, что потенциально может вызвать разногласия у выбранного лидера. Кроме того, процессы разрешения разногласий могут занимать дополнительное время и общение, что снижает эффективность. Dfinity, более подробно обсуждается в первый пост из этой серии использует маяк случайности на основе VRF для избрания одного лидера; однако ради этого приходится жертвовать непредсказуемостью. В идеале любой процесс выбора лидера должен полностью исключать ничьи и при этом быть непредсказуемым, что приводит нас к Святому Граалю этой области исследований — Единым секретным выборам лидера.

Выборы единого тайного лидера 

Цель Выборы единого тайного лидера (SSLE) заключается в выборе уникального лидера из набора валидаторов при сохранении справедливости и непредсказуемости. Protocol Labs представила это понятие как исследовательская задача, и Дэн Боне, компьютерный ученый из Стэнфорда и консультант по крипто-исследованиям a16z, вместе с Сабой Эскандаряном, Люцианом Ханзликом и Николой Греко позже предложили формальное определение SSLE. Это свойство уникальности позволяет избежать рисков консенсуса и затрат на эффективность, связанных с процедурами разрешения конфликтов. В частности, Сара Азуви из Protocol Labs и Даниэль Каппеллетти из Туринского политехнического университета, показывать что при использовании SSLE по сравнению с PLE в протоколе с самой длинной цепочкой блоки могут быть завершены значительно быстрее (на 25 процентов быстрее, когда противник контролирует треть доли). Таким образом, разработка практичного протокола SSLE является важной проблемой.

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

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

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

Следующие два подхода перемешивают список по-разному. Чем проще, тем Предложение Ethereum SSLE, В которой n валидаторы отправляют свои одноразовые номера через Tor, чтобы отвязать идентификаторы валидаторов от их одноразовых номеров. После того, как все валидаторы зарегистрировались, список перемешивается с использованием общедоступного маяка случайности, и валидаторы становятся лидерами в порядке перетасованного списка. Хотя эта схема практична – выборы должны проводиться только один раз в n слоты — эта зависимость от Tor может быть нежелательной (как и в случае с опорой на безопасность любого внешнего протокола). Кроме того, он не совсем непредсказуем: после первого n-1 лидеры раскрываются, финал nth лидер известен.

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

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

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

Другие подходы к SSLE

Другой подход, основанный на перетасовке Адаптивная защита SSLE от DDH. Эта конструкция немного сложнее, но обеспечивает более сильное представление о безопасности, защищая от адаптивный противник в модели стираний Algorand. Этот злоумышленник является адаптивным в том смысле, что он может выбирать, какие валидаторы повреждать во время протокола, а не до его запуска. 

Еще одна проблема в SSLE — выбор каждого валидатора с вероятностью, пропорциональной его доле, а не равномерно случайным образом. Протоколы, основанные на перетасовке, могут наивно достичь этого, позволяя каждому валидатору регистрировать несколько одноразовых номеров: один одноразовый номер для каждой единицы доли, которой они владеют. Однако стоимость перетасовки увеличивается линейно с количеством единиц ставки. S, становясь очень дорогим даже для реалистичных распределений ставок. Элегантный SSLE на основе MPC подход имеет сложность, увеличивающуюся только с журналом S, а также устраняет необходимость в надежной настройке или маяке случайности. Однако по сравнению с подходами, основанными на перетасовке, требуется большее количество раундов общения (логарифмическое по количеству участников) на каждого избранного лидера.

Мы подвели итоги нашего анализа в этой удобной таблице.

	Справедливость	Непредсказуемость/ Секретность*	Уникальность
По-круговой	✓	✗	✓
Идеальная случайность-маяк	✓	✗	✓
Выборы лидера Ethereum (текущие)	✗	✗	✓
Выборы лидера на основе VRF (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Круговой маяк полностью предсказуем, но в остальных маяках ✗ означает, что понятие достигается до некоторой ограниченной степени: маяк идеальной случайности непредсказуем, но противник узнает выходные данные одновременно с избранным лидером, поэтому избранный лидер может быть атакован до того, как он объявит блок; Маяк Эфириума непредсказуем до ~6 минут и может быть слегка предвзят, чтобы повредить честности; Algorand выбирает несколько лидеров с небольшой вероятностью.

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

Миранда Христос является аспирантом в области компьютерных наук в Колумбийском университете, где она является членом теоретической группы и президентским научным сотрудником. Она также является стажером-исследователем в a16z crypto.

Жозеф Бонно является партнером по исследованиям в 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 для получения дополнительной важной информации.