Вибори лідера за допомогою маяків випадковості та інших стратегій

Вибори лідера в блокчейні спрямовані на вибір учасника, який визначатиме наступний блок, який буде додано до блокчейну. Як правило, один валідатор вибирається на слот із набору валідаторів і отримує право продовжити ланцюжок новим блоком у цьому слоті. (Ми припускаємо, що валідатори зберігають точний час і узгоджують поточний номер слоту.) У цій статті ми досліджуємо стратегії для рандомізовані вибори лідера у консенсусних протоколах. (Щоб дізнатися більше про випадковість у цілому, перегляньте нашу попередню статтю, Публічна випадковість і маяки випадковості, Де ми розглянули автономні протоколи для генерації публічно перевірених і непередбачуваних випадковостей.) 

Чому вибори лідера важливі

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

Альтернатива виборів комісії

Вибір комітету є спорідненою проблемою, метою якої є вибір рівномірно випадкової підмножини валідаторів деякого фіксованого розміру k. Ця функція корисна сама по собі, тому що підкомітети часто потрібні в налаштуваннях блокчейну, щоб зменшити розмір набору валідатора, щоб консенсус працював швидше (серед багатьох прикладів: Сортування Альгорана та Вибір комітету Ethereum). Але вибори комітету також корисні для виборів лідера, дозволяючи валідаторам уникнути повторного запуску протоколу виборів лідера, якщо обраний лідер не з’являється. Якщо замість лідера обрано комітет із фіксованим порядком, другий член комітету може стати лідером, якщо перший відсутній. 

Властивості хорошого виборчого протоколу

У протоколі виборів керівників лідери мають бути непередбачуваними. Якщо зловмисник дізнається, хто є майбутнім лідером, він може розпочати проти нього атаку типу «відмова в обслуговуванні» (DoS), щоб завадити йому опублікувати блок. Потім зловмисник може знищити наступного лідера і так далі, призводячи до зупинки блокчейну. Непередбачуваність також може бути посилена, щоб гарантувати, що валідатор сам не дізнається, коли він збирається керувати, що може бути важливим для запобігання хабарництву.

Процес виборів лідера повинен мати наступні три властивості:

• справедливість: кожен чесний валідатор має ймовірність 1/N бути обраним з набору N валідатори (розслаблене поняття теоретико-ігрова справедливість дозволяє формування виборів лідера навіть за наявності зловмисної більшості, хоча й з непостійною нижньою межею кількості турів).
• Непередбачуваність: супротивник не дізнається наступного лідера до певного часу T до того, як лідер оголосить наступний блок.
• Унікальність: у кожному слоті вибирається рівно один лідер.

Таємні вибори лідера

Таємні вибори лідера - це непередбачувані вибори T = 0. У цьому процесі лідер нікому не відомий, поки він не опублікує блок. Це повністю усуває вікно для DoS-атаки: перш ніж лідер виявить себе, зловмисник не знає, кого атакувати, роблячи свою найкращу стратегію випадковим припущенням. А після того, як лідер публікує свій блок, атакувати вже пізно, тому що лідер вже виконав свою відповідальність перед протоколом. 

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

Хоча це дуже сильна модель зловмисника, проти неї запропоновано засоби захисту. Альгоранд запропонував стирає модель, в якому лідер фактично може стерти ключ, необхідний для підписання блоку в його слоті перед тим транслюючи це, тому справді занадто пізно атакувати до того часу, коли лідер вчинить будь-яку публічну дію. Тадеус Драйя, Куанцюан С. Лю та Неха Нарула, троє дослідників із медіа-лабораторії MIT, запропонований що лідер обчислює VDF для свого блоку перед трансляцією, гарантуючи, що адаптивний зловмисник не зможе вчасно створити альтернативний дійсний блок, щоб він був прийнятий для бажаного слота.

Інші способи виборів 

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

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

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

Вибори лідера на базі VRF

Інший підхід, започаткований Algorand, Є Вибори лідера на базі VRF, який включає в себе кожен валідатор, який приватно обчислює вихідні дані VRF і перевіряє, чи є вихідні дані нижче порогового значення. Ця процедура вже відфільтровує більшість валідаторів, оскільки поріг вибрано таким чином, що падіння нижче його малоймовірне. Кілька валідаторів, що залишилися, показують свої вихідні дані VRF, і обирається той, який має найнижче значення VRF. Цей підхід забезпечує ідеальну непередбачуваність (або таємність), але не гарантує унікальності. Деякі валідатори можуть не отримувати повідомлення від усіх потенційних лідерів і можуть припустити, що на виборах виграв не той лідер, через що ці валідатори відходять від основного ланцюга. 

Оцінка VRF періодично заповнюється виходом маяка випадковості, щоб самим валідаторам було менш передбачувано бачити, які слоти вони збираються вести. Ця властивість запобігає зловмиснику, який мовчки скомпрометував валідатор, дізнатися слот, коли валідатор стане лідером, і розпочати атаку, коли валідатор збирається оголосити про блокування. Цей підхід також допомагає запобігти хабарницьким атакам, коли валідатор доводить зовнішнім сторонам, що він буде лідером у певному слоті, і збирає хабарі в обмін на виконання певного завдання як лідер (наприклад, блокування транзакції).

Такі підходи, коли кількість обраних лідерів є випадковою величиною, називаються Імовірнісні вибори лідера (PLE). PLE може призвести до того, що лідери не будуть обрані для певного місця. Це еквівалентно обранню лідера, який є зловмисним або офлайн, оскільки слот зрештою буде пропущено, що зменшить ефективність протоколу консенсусу.

Але найбільше застереження щодо PLE полягає в тому, що може бути обрано кілька лідерів, що потребує певної процедури визначення результатів. Зв’язки створюють ризик для консенсусу, оскільки валідатор із виграшним входом може повідомити про це лише половині мережі, що потенційно може спричинити незгоду в обраному лідері. Крім того, процеси вирішення зв’язків можуть потребувати додаткового часу та спілкування, що негативно впливає на ефективність. Dfinity, більш детально розглянуто в перший пост цієї серії використовує маяк випадковості на основі VRF для обрання єдиного лідера; однак для цього він жертвує непередбачуваністю. В ідеалі будь-який процес вибору лідера має повністю уникати зв’язків і залишатися непередбачуваним, що веде нас до святого Грааля цієї галузі досліджень – Єдиних таємних виборів лідера.

Єдині таємні вибори лідера 

Мета Єдині таємні вибори лідера (SSLE) полягає у виборі унікального лідера з набору валідаторів, зберігаючи справедливість і непередбачуваність. Protocol Labs представили поняття як a проблема дослідження, а Ден Боне, комп’ютерний науковець із Стенфордського університету та радник із криптодосліджень a16z разом із Сабою Ескандаріаном, Люсіаном Ганзліком і Ніколою Греко пізніше запропонували формальне визначення SSLE. Ця властивість унікальності дозволяє уникнути консенсусних ризиків і витрат на ефективність, пов’язаних із процедурами встановлення зв’язків. Зокрема, Сара Азуві з Protocol Labs і Даніель Каппеллетті з Політехнічного університету Туріна, Показувати що коли SSLE використовується порівняно з PLE у протоколі з найдовшим ланцюгом, блоки можуть бути завершені значно швидше (на 25 відсотків швидше, коли супротивник контролює третину частки). Таким чином, розробка практичного протоколу SSLE є важливою проблемою.

У найбільш поширеному підході, який ми назвемо на основі перемішування (використовується як в оригінальному документі SSLE, так і в пропозиція Ethereum SSLE), кожен валідатор реєструє a нунцій що виглядає випадковим, але вони можуть довести, що належить їм. Потім одноразові номери складаються в список. Список перемішується таким чином, що одноразові номери від’єднуються від валідаторів, які їх подали; тобто, враховуючи перетасований список, жоден супротивник не може визначити, який валідатор подав який nonce. Потім вибирається індекс списку відповідно до публіки маяк випадковості, а лідер виявляє себе, доводячи, що одноразовий номер у цьому індексі перемішаного списку належить їм. 

Оскільки вибрано лише один індекс, протокол на основі перемішування завжди виводить a створеного керівник. Оскільки випадковий маяк створений для рівномірного виведення випадкових значень, протокол також ярмарок: кожен валідатор має рівні шанси бути обраним. Крім того, якщо перетасування виконано належним чином (тобто рівномірно у випадковому порядку) і одноразові номери стають неможливими для ідентичності валідаторів, цей протокол також досягає непередбачуваність.

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

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

Замість використання Tor оригінальний документ SSLE має реєстрацію кожного валідатора для вибору в послідовності, додаючи його nonce до списку, перемішуючи список і повторна рандомізація нестандарти. Така повторна рандомізація означає, що кожен одноразовий номер відображається в новому рядку, який не можна зв’язати, щоб валідатор, якому він належить, усе ще міг підтвердити право власності на повторно рандомізований одноразовий номер. Повторна рандомізація робить так, що супротивник не може визначити, на якій позиції опинився якийсь конкретний nonce після перемішування, припускаючи, що принаймні один перемішувач чесний.

Хоча цей послідовний підхід до перетасування з оригінальної статті SSLE дозволяє уникнути покладення на Tor і досягти формальних властивостей SSLE, він дорогий: щоразу, коли новий валідатор реєструється, він повинен опублікувати весь перетасований список у блокчейні, повторно рандомізувати всі nonces і надати доказ того, що вони робили це чесно, що призводить до лінійної кількості комунікацій на валідатор. З незмінним набором валідаторів це має бути зроблено (амортизовано) один раз за вибори, оскільки лідер повторно реєструється після того, як він розкриє доказ для nonce. Стаття дає регульований компроміс між ефективністю та передбачуваністю: замість цього ми можемо перетасувати лише меншу підмножину списку, зменшуючи вартість, якщо ми бажаємо дозволити невелику передбачуваність. Досягти хорошого балансу між ефективністю та безпекою є складним завданням, і, як наслідок, протоколи SSLE ще не знайшли широкого використання на практиці. 

Зручно, що цей підхід послідовного перетасування також можна використовувати для вирішення проблеми виборів комітету, використовуючи випадковий маяк для вибору k окремих індексів зі списку як членів комітету. Це приємне досягнення, оскільки підходи на основі VRF не вирішують проблему тривіально, оскільки працює ймовірнісний протокол на основі VRF k рази можуть вибрати різний розмір комітету залежно від випадковості. 

Інші підходи до SSLE

Ще один підхід, заснований на перемішуванні Адаптивно захищений SSLE від DDH. Ця конструкція є дещо складнішою, але забезпечує сильнішу ідею безпеки, захищаючи від адаптивний супротивник в моделі стирань Альгорана. Цей супротивник є адаптивним, оскільки він може вибирати, які валідатори пошкодити під час протоколу, а не до початку протоколу. 

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

***

Ми підсумували наш аналіз у цій зручній таблиці.

	справедливість	Непередбачуваність/ Секретність*	Унікальність
Кругової	✓	✗	✓
Ідеальний маяк випадковості	✓	✗	✓
Вибори лідера Ethereum (поточні)	✗	✗	✓
Вибори лідера на основі VRF (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* Цифровий маяк є повністю передбачуваним, але в решті маяків ✗ означає, що поняття досягнуто до певної обмеженої міри: маяк ідеальної випадковості є непередбачуваним, але супротивник дізнається результат одночасно з обраним лідером, отже, обраний лідер може бути атакований до того, як оголосить про блокування; Маяк Etherum є непередбачуваним до ~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.