Запровадження
"Генерація випадкових чисел надто важлива, щоб залишати її на волю випадку"
Роберт Кав'ю, 1970
Ця стаття присвячена практичному застосуванню рішень, що використовують колективну генерацію випадкових чисел у недовіреному середовищі. Якщо коротко - як і для чого використовується рандом в блокчейнах, і трохи про те, як відрізнити "добрий" рандом від "поганого". Генерація справді випадкового числа є вкрай непростою проблемою навіть на окремому комп'ютері і давно вивчається криптографами. Ну а в децентралізованих мережах генерація випадкових чисел ще складніша і важливіша.
Саме в мережах, де учасники не довіряють один одному, можливість згенерувати безперечне випадкове число дозволяє ефективно вирішувати безліч найважливіших завдань та значно покращити вже існуючі схеми. Причому азартні ігри та лотереї тут зовсім не є метою номер один, як спочатку може здатися недосвідченому читачеві.
Генерація випадкових чисел
Комп'ютери не вміють самі робити випадкові числа, для цього їм потрібна допомога ззовні. Комп'ютер може мати деяке випадкове значення використовуючи, наприклад, руху мишею, кількість використаної пам'яті, паразитні струми на контактах процесора і багато інших джерел, званих джерелами ентропії. Самі ці значення зовсім випадкові, оскільки перебувають у певному діапазоні чи мають передбачуваний характер змін. Щоб перетворити такі числа справді випадкове число в заданому діапазоні, до них застосовують криптоперетворення, щоб з нерівномірно розподілених значень джерела ентропії отримати рівномірно розподілені псевдовипадкові значення. Отримані значення називають псевдовипадковими, оскільки вони є істинно випадковими, а детерміністично виготовлені з ентропії. Будь-який хороший криптоалгоритм, зашифровуючи дані виробляє шифротексти, які статистично повинні бути не відрізняються від випадкової послідовності, так що для виробництва рандома можна брати джерело ентропії, який забезпечує лише хорошу неповторність і непередбачуваність значень навіть у невеликих діапазонах, решту роботи з розсіювання результуючому значенні візьме він алгоритм шифрування.
Щоб завершити короткий лікнеп, додам, що генерація випадкових чисел навіть на одному пристрої – один із стовпів забезпечення безпеки наших з вами даних, згенеровані псевдовипадкові числа використовуються при встановленні захищених з'єднань у різних мережах, для генерації криптографічних ключів, для балансування навантаження, контролю цілісності, і ще для багатьох застосувань. Безпека багатьох протоколів залежить від можливості згенерувати надійний, непередбачуваний ззовні рандом, зберегти його і не розкривати його до наступного кроку протоколу, інакше безпека буде поставлена під загрозу. Атака на генератор псевдовипадкових значень є вкрай небезпечною і ставить під загрозу відразу все, що використовує генерацію рандомів.
Все це ви повинні знати, якщо проходили базовий курс криптографії, тому продовжимо про децентралізовані мережі.
Рандом у блокчейнах
В першу чергу я говоритиму про блокчейни з підтримкою смарт-контрактів, саме вони можуть повною мірою використовувати можливості, що надаються якісним незаперечним рандомом. Далі, для стислості, я називатиму цю технологію “Publicly Verifiable Random Beacons” чи PVRB. Оскільки блокчейни — це мережі, інформацію у якій може перевірити будь-який учасник, ключовою частиною назви є “Publicly Verifiable”, тобто. будь-який бажаючий може за допомогою обчислень отримати доказ того, що отримане число, розміщене в блокчейні, має такі властивості:
- Результат повинен мати доведено рівномірний розподіл, тобто заснований на стійкій криптографії, що доводиться.
- Неможливо контролювати жоден із бітів результату. Як наслідок, результат не може бути наперед передбачений.
- Не можна саботувати протокол генерації за рахунок неучасті в протоколі або шляхом навантаження мережі атакуючими повідомленнями
- Все перелічене вище має бути стійким до змов допустимого числа нечесних учасників протоколу (наприклад 1/3 учасників).
Будь-яка можливість мінорної групи учасників, що змовилася, зробити навіть контрольований парний/непарний рандом — дірка в безпеці. Будь-яка можливість групи зупинити видачу рандому — дірка у безпеці. Загалом проблем багато, і це завдання не з легких ...
Здається, що найбільш важливе застосування для 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 ВР. Ці блоки служать для забезпечення фінальності (неможливість появи форка ланцюжка, що починається раніше останнього Last Irreversible Block).
Також, у реальних імплементаціях, схема протоколу складніша — голосування за запропоновані блоки проводяться в кілька етапів, щоб підтримувати роботу мережі у разі пропуску блоків та проблем з мережею, але навіть з урахуванням цього, алгоритми консенсусу з використанням PVRB вимагають суттєво менше повідомлень між BP, що дозволяє зробити їх швидше, ніж традиційний PВFT, чи різні його модифікації.
Найяскравіший представник таких алгоритмів: від команди Cardano, який, як оголошено, має математично доведену стійкість до наявності змови серед BP.
У Ouroboros PVRB використовується визначення так званого “BP schedule” — розкладу, за яким кожному BP призначається свій тимчасовий слот для публікації блоку. Великою перевагою використання PVRB є повне “рівноправність” BP (відповідно до розмірів їх балансів). Чесність PVRB гарантує, що шкідливі BP не можуть контролювати розклад тимчасових слотів, і тому не можуть маніпулювати ланцюжком, заздалегідь готуючи та аналізуючи форки ланцюжка, а для вибору форка достатньо покладатися просто на довжину ланцюжка, не оперуючи хитрими способами "ваги" його блоків.
Загалом у всіх випадках, коли в децентралізованій мережі потрібно вибрати випадкового учасника, майже завжди найкращим вибором буде PVRB, а не детерміністичний варіант на основі, наприклад, хеша блоку. Без PVRB можливість вплинути на вибір учасника веде до появи атак, у яких атакуючий може, вибираючи з кількох варіантів майбутнього, вибирати наступного корумпованого учасника або відразу кількох, щоб забезпечити більш вагому частку у прийнятті рішення. Використання PVRB дискредитує ці типи атак.
Масштабування та балансування навантаження
PVRB може принести серйозну користь також у завданнях зниження навантаження, масштабування платежів. Для початку має сенс ознайомитися з Рівеста "Electronic Lottery Tickets as Micropayments". Загальна суть така, що замість того, щоб робити 100 платежів по 1c від платника одержувачу, можна зіграти в чесну лотерею з призом 1$ = 100c, де платник при кожному платежі в 1c передає банку один із 100 своїх "лотерейних квитків". Один із цих квитків виграє банку 1$, і саме цей квиток одержувач може фіксувати у блокчейні. Найважливіше, що решта 99 квитків передаються між одержувачем та платником без жодної зовнішньої участі, приватним каналом та з будь-якою потрібною швидкістю. Хороший опис протоколу на базі цієї схеми у мережі Emercoin можна прочитати .
Ця схема має кілька проблем, наприклад одержувач може перестати обслуговувати платника відразу ж після отримання виграшного квитка, але для безлічі особливих застосувань, на кшталт похвилинної тарифікації або електронних підписок на сервіси, їх можна знехтувати. Головною ж вимогою, звичайно, є чесність лотереї, що проводиться, а для її проведення абсолютно необхідний PVRB.
Вибір випадкового учасника вкрай важливий також для протоколів шардингу, метою яких є горизонтальне масштабування ланцюжка блоків, що дозволяє різним BP процесувати лише свій scope транзакцій. Це дуже складне завдання, особливо у питаннях безпеки при об'єднанні шардів. Чесний вибір випадкового ВР з метою призначення його відповідальних за конкретний шард, як і в алгоритмах консенсусу, — також завдання 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: їх зараз кілька, кожна має свій набір важливих властивостей та особливостей у реалізації, і за кожною стоїть гарна ідея. Рандом займається не так багато команд, і досвід кожної з них вкрай важливий для всіх інших. Сподіваємося, що наша інформація дозволить решті команд рухатися швидше, з урахуванням досвіду попередників.
Джерело: habr.com