Публічна випадковість і маяки випадковості

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

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

Бажані властивості

Генерування випадкових чисел, як відомо, складне завдання. Наприклад, сталося витік багатьох криптографічних ключів, оскільки вони покладався на несправний генератор випадкових чисел (для якої стіна Cloudflare лавові лампи послужив би творчим пом'якшенням). Це просто приватна випадковість, однак, де тільки одна сторона повинна створити та використовувати його.

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

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

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

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

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

Криптографічний ідеал: Randomness маяки

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

Такого ідеалізованого маяка випадковості, подібного до інших криптографічних абстракцій, таких як випадкові оракули або загальна групова модель, не існує в реальному світі. Але це корисна мета, до якої потрібно прагнути, і корисна модель для міркування про протоколи, які покладаються на публічну випадковість. 

Ми можемо розглянути кілька наближень ідеального маяка випадковості.

• Централізовані маяки: Найпростішим підходом до генерації хорошої випадковості є централізована третя сторона з такими службами, як Маяк випадковості NIST or random.org, який генерує випадковість з атмосферного шуму та акредитований для використання в азартних іграх. Ця залежність від третьої сторони повністю підриває філософію децентралізації. Справді, у наведеному вище прикладі ми маємо вірити, що відповідні організації генерують випадковість правильно, без будь-яких криптографічних доказів.
• Відображення фізичної випадковості: Багато традиційних лотерей покладаються на публічний показ, який може включати, наприклад, когось, хто простягає руку до контейнера з кульками для пінг-понгу з різними номерами. На жаль, ними часто легко маніпулювати. Наприклад, певні кульки можна помістити в морозилку та селектору можна сказати вибрати холодні.
• Природні маяки: поширеною ідеєю є використання випадкових природних явищ, таких як погода чи космічне фонове випромінювання, як маяк. На жаль, усі запропоновані джерела не забезпечують однозначного консенсусу. Різні спостерігачі побачать дещо різні значення, що вимагає повторного залучення довіреної сторони для проведення офіційних вимірювань з усіма недоліками централізованого маяка.
• Напівцентралізовані маяки: Кращим підходом було б отримати випадковість із Заголовки блоків Bitcoin безпосередньо або з ціни закриття акцій, що легше публічно перевірити, і важче будь-якій одній стороні повністю контролювати. Проте тонкі атаки все ще існують на обох proof-of-work blockchain випадковість та випадковість курсу акцій. За допомогою заголовків блокчейну, наприклад, майнери можуть відмовитися від блоків, заголовки яких створюють значення маяка, яке їм не подобається. Або вони можуть вирішити розірвати зв’язки, коли будуть знайдені два блоки, що стикаються, на основі бажаного вихідного сигналу маяка.

Децентралізовані маяки випадковості (DRB)

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

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

Класичний підхід: протоколи фіксації та виявлення

Дуже простого двораундового протоколу достатньо для DRB в оптимістичному випадку. У 1 турі кожен учасник i генерує випадкове значення r_i і публікує криптографічне зобов'язання c_i=Здійснити (r_i). У цьому додатку зобов’язання може бути просто хеш-функцією, наприклад SHA-256. Після того, як зобов’язання кожного учасника опубліковано, вони заблоковані на свій вибір r_i, але зобов’язання не розкривають жодної інформації про внески інших учасників. У раунді 2 кожен учасник «відкриває свої зобов’язання» шляхом публікації r_i. Потім усі випадкові значення об’єднуються, наприклад, шляхом їх XOR або (бажано) хешування їх конкатенації.

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

Блокчейни пропонують природний засіб вирішення цієї проблеми: від кожного учасника можна вимагати покласти частину коштів на умовне депонування, які конфіскуються, якщо вони не розкриють свій випадковий внесок. Саме таким був підхід класика РАНДАО маяк на Ethereum. Недоліком цього підходу є те, що вихідні дані все одно можуть бути упередженими, що може бути вигідним у фінансовому плані для зловмисника, якщо гроші на депонуванні менші, ніж сума грошей, що залежить від результату маяка. Кращий захист від упереджених атак вимагає розміщення більше монет у депозитному депонуванні.

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

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

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

Можливі кілька інших механізмів відновлення, але всі вони мають однакові обмеження. Якщо є N учасників, і ми хочемо стійкості, якщо будь-яка група до f вузлів випадає, то має бути так, що будь-яка група з Nf учасники можуть підрахувати кінцевий результат. Але це також означає зловмисну ​​коаліцію Nf учасники можуть заздалегідь передбачити результат шляхом приватного моделювання механізму відновлення. Це також може статися під час першого раунду протоколу, протягом якого така коаліція може змінити свій власний вибір випадковості та упередити результат. 

Іншими словами, це означає будь-яку коаліцію Nf вузли повинні містити принаймні один чесний вузол. За простою алгеброю, Nf > f, так f < N/2, і ці протоколи за своєю суттю вимагають чесної більшості. Це істотна відмінність від оригінальної моделі безпеки commit-reveal, яка вимагає лише f<N (хоча б один чесний учасник).

Ці протоколи також часто вимагають значних витрат на зв’язок для обміну додатковою інформацією PVSS між усіма вузлами під час кожного запуску протоколу. Дослідницьке співтовариство виконало значну роботу над цією проблемою за останні кілька років, включно з дослідницькими пропозиціями RandShare, Вискоблювати, SecRand, ТРАВИабо Альбатрос, але, здається, ніхто не бачив розгортання в реальному світі.

Протоколи на основі випадкових функцій, які можна перевірити

Розуміючи, що група в Nf учасники можуть обчислити випадкове значення маяка у наведеному вище протоколі, що призводить до дещо простішого підходу: обмінюватися довгостроковим секретним ключем між N сторони та попросіть їх використовувати його для оцінки a випадкова функція, що перевіряється (VRF). Секретний ключ надається через a t-з-N порогова схема, так що будь-який t учасники можуть обчислити VRF (але менша коаліція не може). для t=Nf, це забезпечує таку саму стійкість до f шкідливі вузли як протоколи фіксації-виявлення-відновлення, розглянуті вище.

ДІФІНІТ піонером цього підходу як частину їхнього протоколу консенсусу з використанням порогових підписів BLS (які функціонують як VRF). Автономний дрант Маяк випадковості використовує, по суті, той самий підхід, з набором учасників, які підписують порогове значення BLS і лічильник у кожному раунді. The Ліга ентропії це відкритий екземпляр drand, що створює випадкові дії кожні 30 секунд, використовуючи 16 вузлів-учасників (станом на вересень 2022 року), якими керують компанії та університетські дослідницькі групи. 

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

Як описано вище, просте підписання значення лічильника не додає нової випадковості за раунд, тому, якщо достатня кількість ключів учасників буде скомпрометована, протокол буде передбачуваним у кожному майбутньому раунді.

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

Ethereum's Маяк ланцюга наразі використовує VRF на основі BLS: пропонент кожного раунду додає до суміші значення VRF. Це економить раунд спілкування порівняно з парадигмою фіксації-виявлення (припускається, що довгостроковий відкритий ключ BLS зареєстровано один раз), хоча ця конструкція успадковує деякі застереження підходу фіксації-виявлення, включаючи можливість зміщення виводу маяка шляхом припинення виведення .

Протоколи на основі функцій затримки, які можна перевірити

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

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

Ще більш елегантний однораундовий протокол можливий із сучасними VDF: повністю відмовтеся від зобов’язань. Кожен учасник може просто опублікувати свій довільний внесок r_i, а кінцевий результат – це комбінація внесків кожного учасника, пропущена через VDF. Часова затримка в обчисленні VDF гарантує, що ніхто не може вибрати своє зобов’язання таким чином, щоб упередити кінцевий результат. Цей підхід був запропонований як Юникорн Ар'єном Ленстрою та Бенджаміном Весоловським у 2015 році, і це дійсно було ключовим мотивуючим додатком у розробка VDF.

Цей підхід знайшов певне практичне застосування. Чіа реалізує версію цього як частину свого консенсусного протоколу, використовуючи VDF з повторюваним квадратом у групах класів. Starkware реалізовано а доказ концепції маяка на основі VDF за допомогою VDF на основі SNARK. Ethereum також плани to use такий підхід, створення спеціальної ASIC для обчислення VDF для генерації випадковості на консенсусному рівні.

***

Загальнодоступна випадковість є важливим компонентом багатьох протоколів, але нам досі не вистачає жодного стандартного DRB, який би забезпечував високий рівень безпеки. Дизайнерський простір великий, і можливі багато гібридів і комбінацій вищезазначених підходів. Наприклад, можна поєднати протокол на основі VRF з протоколом на основі VDF, що додає свіжу ентропію, наприклад, як запропоновано RandRunner. Beacon Chain Ethereum наразі використовує VRF, хоча в майбутньому він може додати VDF, щоб усунути можливість упередженості від атак із блокуванням.

Також залишається відкритим питання, коли прийнятні протоколи чесної більшості. Для відносно невеликої, перевіреної групи учасників – як-от Ліга Ентропії – припущення чесної більшості є розумним. З іншого боку, протоколи, які вимагають лише одного чесного учасника, мають невід’ємну перевагу – більша кількість учасників може лише покращити безпеку. Це означає, що ці протоколи потенційно можуть бути розгорнуті з відкритою участю без дозволу.

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

***

Джозеф Бонно є дослідницьким партнером 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.