An Analysis of Verifiable Randomness in Web3 (Аналіз перевіреної випадковості в Web3)

5 min readMar 9, 2024

Оригінал статті тут.

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

Зміст
1.Перевірена випадковість у Web3
2. Що таке “Перевірна” або “Добра” випадковість?
3. Аналіз парадигми ”зобов’язання-розкриття” (commit-reveal)
— Неможливість та Обхід
— Уразливість у Pyth VRF
4. Висновок

Перевірена випадковість у Web3

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

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

Що таке “Перевірна” або “Добра” випадковість?

У нашому попередньому блозі ми стверджували, що перевірена або «хороша» випадковість, яка призводить до генерації дійсно випадкового числа, це:

Непередбачувана (Unpredictable) випадковість: ніхто не може обчислити число заздалегідь.
Неупереджена (Unbiasable) випадковість: випадкове число не може бути зміщеним, щоб певні числа з’явилися з більшою ймовірністю, ніж інші (наприклад, число завжди парне або завжди непарне).
Випадковість, що підлягає публічній перевірці (Publicly verifiable): будь-хто може переконатися, що випадкове число згенеровано правильно.

У нашому документі про Розподілену перевірену випадкову функцію (Distributed Verifiable Random Function, dVRF) ми обговорювали, що протокол обслуговування випадковості Supra dVRF задовольняє трьом наведеним вище властивостям і, отже, забезпечує хорошу випадковість. Тепер головне питання:

Як визначити, чи протокол служби випадковості генерує перевірену «хорошу» випадковість чи «погану» (тобто неперевірену) випадковість?

У серії блогів ми досліджуватимемо, як генерувати та споживати перевірену випадковість у просторі Web3. Починаючи з публікації, ми зануримося в протоколи обслуговування випадковості, які використовують схеми зобов’язання-розкриття. Ми будемо посилатися на більш широке поняття зобов’язання-розкриття як парадигму зобов’язання-розкриття (commit-reveal).

Аналіз парадигми ”зобов’язання-розкриття” (commit-reveal)

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

У простій парадигмі зобов’язання-розкриття постачальник випадковості та користувач зобов’язані до випадкових значень x та s, використовуючи функцію хешування H. Після обміну зобов’язаннями постачальник і користувач розкривають x та s один одному. Користувач та постачальник перевіряють розкриті значення відповідно до зобов’язань. Якщо зобов’язання перевіряються, вони обчислюють випадковість rand=H(x, s). Ми проілюструємо цю парадигму нижче:

Оскільки користувач отримує x від постачальника після обміну зобов’язаннями, користувач може заздалегідь обчислити вихід. Це фундаментальний недолік конструкції, оскільки користувач може продовжити/зупинити протокол на кроці 4, якщо результат є сприятливим/несприятливим. Це дозволить користувачеві максимізувати свій прибуток. Постачальник не може завершити виконання без отримання s від користувача, оскільки s залишається секретним. Отже, результат може бути необ’єктивним.

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

Неможливість та Обхід

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

Однак у просторі Web3 користувач і постачальник можуть отримати доступ до смарт-контрактів. Смарт-контракти діють як довірена сторона для виконання правильних обчислень публічних цінностей. Служба випадковості використовує смарт-контракти для створення непередбачуваної, неупередженої випадковості, яку можна перевірити публічно.

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

Уразливість у Pyth VRF

Протокол PythVRF діє в парадигмі зобов’язання-розкриття, де постачальник спочатку зобов’язується до послідовності випадкових значень (x1, x2,…xN) у смарт-контракті Entropy (Entropy Smart Contract, SC). SC зберігає ці зобов’язання.

Користувач ініціює запит, вибираючи випадкове значення s. Користувач зобов’язується до s як c і потім надсилає c в SC. SC зберігає c та присвоює унікальний порядковий номер — reqid (позначений як i в PythVRF), користувачу. Користувач надсилає reqid постачальнику через HTTP-запит і отримує xreqid. Користувач розкриває (s, xreqid) у смарт-контракті Entropy.

SC перевіряє xreqid (відносно збережених зобов’язань) та c, після чого він обчислює випадковість rand. Протокол PythVRF можна візуалізувати нижче:

Зловмисник атакує протокол, попередньо обчислюючи rand=H(s, xreqid), як тільки він отримує xreqid від постачальника. Якщо результат сприятливий, то користувач продовжує протокол, в іншому випадку він перериває його. Це дозволяє користувачу максимізувати свої шанси на перемогу в онлайн-лотереї, де випадковість користувача береться до уваги при визначенні переможців.

За допомогою Supra використовується клан вузлів замість одного вузла. Внаслідок цього одиночні вузли не можуть впливати на випадкові результати або переривати їх, оскільки жоден з них не може передбачити результат наперед. Клієнт не може запобігти завантаженню вихідних даних у мережу після того, як він ініціював запит випадковості.

Висновок

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

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

Оригінал статті: