Чи можна генерувати випадкові числа, якщо ми не довіряємо одне одному? Частина 1

Привіт, Хабре!

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

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

Коли ми розробляємо розподілений протокол генерації випадкових чисел, ми хочемо, щоб він мав три властивості:

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

2. Він має бути непередбачуваним. Іншими словами, жоден учасник не повинен мати можливість передбачити, скільки буде згенеровано (або вивести будь-які його властивості) до того, як воно буде згенеровано.

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

У цій статті ми розглянемо два підходи: RANDAO + VDF і підхід, заснований на пральних кодах. У наступній частині ми докладно розберемо підхід, що базується на порогових підписах.

Але для початку давайте розберемо простий і часто використовуваний алгоритм, який життєздатний, непередбачуваний, але упереджений.

РАНДАО

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

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

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

Які з властивостей, які ми описали вище, має RANDAO? Він непередбачуваний, має ту ж життєздатність, що і протокол консенсусу, що лежить в його основі, але він є упередженим. Зокрема, зловмисник може спостерігати за мережею, і після того, як інші учасники розкриють свої числа, він може обчислити їх XOR, і вирішити, розкривати чи не розкривати число, щоб вплинути на результат. У той час, як це не дозволяє зловмиснику одноосібно визначити висновок генератора випадкових чисел, це все ще дає йому 1 біт впливу. А якщо зловмисники керують кількома учасниками, то кількість контрольованих ними бітів буде дорівнює кількості учасників під їх керуванням.

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

RANDAO + VDF

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

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Така функція називається Verifiable Delay Function або VDF. Якщо обчислення остаточного результату займає більше часу, ніж етап розкриття чисел, то зловмисник зможе передбачити ефект від демонстрації чи приховування свого числа, отже він втратить можливість проводити результат.

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

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

Для згаданого вище сімейства VDF продуктивність спеціалізованого ASIC може бути в 100 разів вище, ніж у звичайного обладнання. Таким чином, якщо фаза розкриття триває 10 секунд, то VDF, що обчислюється на такий ASIC, повинна займати більше 100 секунд, щоб мати 10-кратний запас безпеки, і, таким чином, той самий VDF, обчислений на звичайному устаткуванні, повинен зайняти 100 x 100 секунд = ~3 години.

Ethereum Foundation планує вирішити цю проблему завдяки створенню власних загальнодоступних безкоштовних ASIC. Як тільки це відбудеться, всі інші протоколи також можуть використовувати переваги цієї технології, але доти підхід RANDAO + VDF не буде настільки ж життєздатним для протоколів, які не можуть інвестувати в розробку своїх власних ASIC.

Багато статей, відео та іншої інформації про VDF зібрано на цьому сайті.

Використовуємо пральні коди

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

Основна ідея протоколу ось у чому. Для простоти припустимо, що у ньому рівно 100 учасників. Допустимо також, що у всіх учасників локально є певний приватний ключ, і публічні ключі всіх учасників відомі всім учасникам:

1. Кожен учасник локально вигадує довгий рядок, розбиває його на 67 частин, створює пральні коди для отримання 100 часток, таких, що будь-яких 67 достатньо для відновлення рядка, призначає кожну зі 100 часток одному з учасників і шифрує їх за допомогою відкритого ключа того ж учасника. Потім усі закодовані частки публікуються.

2. Учасники використовують певний консенсус для досягнення згоди про закодовані набори від конкретних 67 учасників.

3. Щойно консенсус досягнуто, кожен учасник бере закодовані частки у кожному з 67 наборів, зашифровані їх відкритим ключем, розшифровує такі частки і публікує такі розшифровані частки.

4. Як тільки 67 учасників виконали крок (3), усі узгоджені набори можуть бути повністю декодовані та відновлені завдяки властивостям стиральних кодів, і остаточне число може бути отримано як XOR початкових рядків, з яких учасники почали (1).

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

Що відбувається, якщо на кроці (1) один із учасників відправив іншим учасникам закодовані частки, які не є коректним стираючим кодом деякого рядка? Без додаткових змін різні учасники або не зможуть відновити рядок зовсім, або відновлять різні рядки, що призведе до того, що учасники отримають різне випадкове число. Щоб запобігти цьому, можна зробити таке: кожен учасник, крім закодованих часток, обчислює також дерево меркла всіх таких часток, і кожному учаснику посилає як саму закодовану частку, і корінь дерева меркла, і доказ включення частки в дерево меркла. У консенсусі на кроці (2) потім учасники не просто погоджуються на безлічі наборів, але на безлічі конкретних коренів таких дерев (якщо деякий учасник відійшов від протоколу, і відправив різні коріння дерева тьмяніли різним учасникам, і два таких кореня показані під час консенсусу, його рядок не включається до результуючого набору). За підсумком консенсусу ми матимемо 67 закодованих рядків і відповідних їм коренів дерева тьмяніло таких, що є хоча б 67 учасників (не обов'язково тих же хто запропонували відповідні рядки), у яких для кожного з 67 рядків є повідомлення з часткою прального коду, і доказ входження їх частки у відповідне дерево меркла.

Коли на кроці (4) учасник розшифровує 67 часток для деякого рядка, і намагається по них відновити оригінальний рядок, можливий один із варіантів:

1. Рядок відновлюється, і якщо її потім закодувати стираючими кодами знову, і порахувати дерево меркла для порахованих локально часток, корінь збігається з тим, на якому досягнуто консенсусу.

2. Рядок відновлюється, але порахований локально корінь не відповідає тому, на якому досягнуто консенсусу.

3. Рядок не відновлюється.

Легко показати, що якщо хоча б для одного учасника вийшов варіант (1), то для всіх учасників станеться варіант (1), і навпаки, якщо хоча б для одного учасника стався варіант (2) або (3), то для всіх учасників трапиться варіант (2) або (3). Таким чином, для кожного рядка в наборі або всі учасники успішно його відновлять або всі учасники не зможуть його відновити. Потім результуюче випадкове число – це XOR лише рядків, які учасники змогли відновити.

Порогові підписи

Інший підхід до випадковості полягає у використанні про порогових підписів BLS. Генератор випадкових чисел, заснований на порогових підписах, має такі самі гарантії, як і описаний вище алгоритм на основі стиральних кодів, але має значно меншу асимптотику кількості повідомлень, що пересилаються по мережі на кожне згенероване число.

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

Часте застосування для BLS-підписів у протоколах блокчейну, крім генерації випадкових чисел, – це підпис блоків у протоколах BFT. Скажімо, 100 учасників створюють блоки, і блок вважається остаточним, якщо 67 із них підписують його. Всі вони можуть представити свої частини BLS-підписи та використовувати певний консенсус-алгоритм, щоб узгодити 67 з них, а потім об'єднати їх в один BLS-підпис. Будь-які 67 (або більше) частин можуть бути використані для створення підсумкового підпису, який залежатиме від того, які саме 67 підписів були об'єднані, і тому може відрізнятися, але не дивлячись на те, що різний вибір 67 учасників буде створювати різний підпис , будь-який такий підпис буде коректним підписом для блоку. Решта учасників потім достатньо отримати по мережі і перевірити тільки один підпис на кожен блок, замість 67, що помітно знижує навантаження на мережу.

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

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

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

На закінчення

Ця стаття – перша в серії технічних статей у блозі БЛИЗЬКО. NEAR – це блокчейн протокол та платформа для розробки децентралізованих додатків з акцентом на простоту розробки та простоту використання для кінцевих користувачів.

Код протоколу відкритий, наша реалізація написана на Rust, її можна знайти тут.

Подивитися як виглядає розробка під NEAR, та поекспериментувати в онлайн-IDE можна тут.

Стежити за всіма новинами російською можна в групі у телеграмі і в групі на ВКонтакті, а англійською в офіційному твіттері.

До зустрічі!

Джерело: habr.com