Рандомізація в блокчейн-консенсусі — використання криптографічно захищених джерел випадковості в протоколах блокчейн-консенсусу. Випадковість застосовується для вибору виробників блоків, формування комітетів, випадкового впорядкування транзакцій та інших дій, від яких залежить безпека і децентралізація мережі.Choi K., Manoj A., Bonneau J. SoK: Distributed Randomness Beacons. In: 2023 IEEE Symposium on Security and Privacy (SP). IEEE, 2023. Сучасні протоколи розглядають рандомізацію як окремий криптографічний ресурс — публічний маяк випадковості (randomness beacon), від якого залежать гарантії стійкості до адаптивних атак.Bonneau J., Bünz B., Christ M., Efron Y. How Much Public Randomness Do Modern Consensus Protocols Need? In: 7th Conference on Advances in Financial Technologies (AFT 2025). LIPIcs, vol. 354, 2025.

Формально вихід маяка в раунді t можна розглядати як випадкову змінну , де — параметр безпеки. Вимоги до такого джерела включають наближену рівномірність, непередбачуваність значення до моменту його публікації та обмежену можливість зміщення (bias) для обчислювального противника.

Теоретичні основи рандомізації в блокчейн-консенсусі У класичній задачі візантійської угоди випадковість використовується як «спільна монетка» (common coin) для розбиття симетрії між вузлами та випадкового вибору лідера. Інтуїтивно це означає, що всі чесні учасники час від часу отримують спільний випадковий біт, на який не може істотно вплинути супротивник.

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

де — незначна (negligible) функція від параметра безпеки.

У блокчейн-протоколах такі абстрактні вимоги проявляються в конкретних задачах:

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

Просту модель ідеального протоколу Proof-of-stake можна описати так. Нехай у вузла i частка (стейк) дорівнює , а сумарний стейк усіх учасників дорівнює

Тоді ймовірність того, що у фіксованому слоті саме вузол i буде обраний лідером, дорівнює

де — подія «вузол i обрано лідером слота». У реальних протоколах (Algorand, Ouroboros тощо) цей ідеальний вибір реалізують за допомогою криптографічних примітивів (наприклад, VRF), які моделюють доступ до чесного маяка випадковості.

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

У багатьох протоколах цього недостатньо: інші учасники мають мати змогу перевірити, що вузол справді використав належну функцію, а не підтасував результат. Для цього застосовують верифіковані випадкові функції (VRF, англ. verifiable random function). Інтуїтивно VRF — це псевдовипадкова функція, вихід якої супроводжується криптографічним доказом коректності й може бути перевірений будь-ким за публічним ключем власника.Li Z., Tan T.G., Szalachowski P., Sharma V., Zhou J. Post-Quantum VRF and its Applications in Future-Proof Blockchain System. CoRR abs/2109.02012, 2021.

Формально VRF задається парою алгоритмів (процедур):

обчислення (оцінка функції): ; перевірка: .

Тут:

— секретний ключ вузла; — відповідний публічний ключ; — публічний вхід (наприклад, номер слоту, ідентифікатор раунду чи хеш попереднього блоку); — псевдовипадковий вихід VRF; — криптографічний доказ того, що обчислено коректно.

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

У протоколах Proof-of-stake VRF часто використовується для реалізації приватної лотереї. Типовий крок виглядає так:Gilad Y., Hemo R., Micali S., Vlachos G., Zeldovich N. Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In: Proc. 26th ACM Symposium on Operating Systems Principles (SOSP 2017). ACM, 2017.Kiayias A., Russell A., David B., Oliynykov R. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In: Advances in Cryptology – CRYPTO 2017. LNCS 10401. Springer, 2017.

кожен валідатор самостійно обчислює , де задається протоколом (наприклад, номером слоту); інтерпретує як число на відрізку (потрібне лише фіксоване зіставлення «рядок бітів → число»); перевіряє, чи потрапляє у певний інтервал. Якщо так, вузол «виграв» лотерею й має право пропонувати блок або входити до комітету; якщо ні — залишається пасивним у цьому раунді; у разі виграшу вузол публікує й саме значення , і доказ ; інші учасники мережі перевіряють їх за допомогою .

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

Позначення означає, що описує число «успіхів» у незалежних випробуваннях, де кожне окреме випробування має імовірність успіху . У реалізації Algorand значення , отримане з VRF, порівнюється з кумулятивними ймовірностями цього розподілу: відрізок розбивається на інтервалів, кожному значенню відповідає інтервал довжини , і за тим, у який інтервал потрапив , визначається кількість голосів вузла.Algorand Cryptographic Sortition. Lecture notes, 2019.

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

Схеми commit–reveal і RANDAO У колективних схемах типу commit–reveal випадковість генерується не одним вузлом, а групою учасників. Ідея полягає в тому, щоб кожен учасник додав власний внесок у спільне випадкове значення так, щоб до завершення протоколу супротивник не міг передбачити результат і змінити його заднім числом.Bünz B., Goldfeder S., Bonneau J. Proofs-of-delay and randomness beacons in Ethereum. IEEE Security & Privacy on the Blockchain Workshop (IEEE S&B), 2017.

Нехай:

— криптографічна геш-функція; символ означає конкатенацію (склеювання) бітових рядків; символ означає побітову операцію «виключне АБО» (XOR).

Для n учасників базова схема commit–reveal працює в два етапи.

1. Фаза зобов’язань (commit). Кожен учасник випадково обирає секретне значення та обчислює зобов’язання (комітмент)

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

2. Фаза розкриття (reveal) та агрегації. Далі кожен учасник публікує своє секретне значення . Інші учасники перевіряють, що

тобто що він дійсно розкрив те, до чого раніше «прив’язався». Якщо перевірка пройшла успішно, усі коректно розкриті значення об’єднуються в одне спільне випадкове значення, наприклад:

RANDAO як ітеративний commit–reveal.

Різновидом схеми commit–reveal є RANDAO — протокол, у якому випадковість накопичується від раунду до раунду. Нехай — поточний стан спільного випадкового значення (маяка) в раунді t. У раунді бере участь валідатор, обраний за деяким консенсусним правилом (наприклад, за стейком).

Типовий крок RANDAO можна описати так:

На попередньому етапі валідатор локально обирає випадкове значення і публікує лише зобов’язання (аналог фази commit). Коли настає його черга оновлювати маяк, він розкриває . Інші учасники перевіряють, що оприлюднене відповідає раніше опублікованому комітменту. Після успішної перевірки стан маяка оновлюється за правилом

У Ethereum 2.0 RANDAO використовується як один із компонентів для побудови seeds випадковості, на основі яких обираються пропоненти блоків і комітети валідаторів у beacon chain.Edgington B. 2.9.3 Randomness. У: Ethereum 2.0 Book (eth2book.info), онлайн-документація.

Водночас така конструкція має типовий недолік, відомий як «атака останнього розкривача». Учасник, який розкриває своє значення останнім, може оцінити, як саме його вплине на , і вирішити взагалі не розкривати , якщо результат його не влаштовує. Це дає йому певну можливість зміщувати розподіл або принаймні уникати небажаних для себе значень.Son D.H. та ін. RANDAO-based RNG: Last Revealer Attacks in Ethereum Consensus. arXiv:2403.09541, 2024. У практичних системах для пом’якшення цієї проблеми вводять додаткові штрафи за невиконання обов’язків валідатора, поєднують RANDAO з іншими джерелами випадковості або застосовують більш складні розподілені маяки.

Маяки випадковості (randomness beacons) і порогові підписи Маяк випадковості (randomness beacon) — це сервіс, який у фіксовані моменти часу публікує випадкові значення разом із доказом їхньої коректності. Важливим класом є розподілені маяки на основі порогових BLS-підписів: n вузлів спільно володіють секретним ключем s, який розподілено на частки . Для повідомлення m кожен вузол обчислює частковий підпис

а агрегований підпис від будь-якої кворумної множини T вузлів дорівнює

Публічне значення маяка визначається як

де — агрегований підпис на фіксованому повідомленні, прив’язаному до раунду t. Жоден окремий учасник не може передбачити до обчислення кворумного підпису.How do Randomness Beacons based on Threshold Signatures work? Офіційний блог NEAR Protocol, 25 лютого 2020 р.Filecoin Foundation. Filecoin Features: Distributed Randomness & Leader Elections. Filecoin.io Blog, 10 серпня 2020 р.

Використання в PoW, PoS та BFT-протоколах У системах Proof-of-work випадковість випливає з процесу пошуку nonce: майнер успішно знаходить блок, коли хеш менший за цільову складність. Ймовірність успіху пропорційна обчислювальній потужності, що емпірично визначає випадковий розподіл блоків між майнерами.Bünz B., Goldfeder S., Bonneau J. Proofs-of-delay and randomness beacons in Ethereum. IEEE Security & Privacy on the Blockchain Workshop (IEEE S&B), 2017.

У протоколах Proof-of-stake (Algorand, Ouroboros) імовірність того, що валідатор i стане лідером слота або членом комітету, задається його часткою в сумарному стейку; конкретна реалізація базується на VRF і / або виходах маяка випадковості.Gilad Y., Hemo R., Micali S., Vlachos G., Zeldovich N. Algorand: Scaling Byzantine Agreements for Cryptocurrencies. In: Proc. 26th ACM Symposium on Operating Systems Principles (SOSP 2017). ACM, 2017.Kiayias A., Russell A., David B., Oliynykov R. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In: Advances in Cryptology – CRYPTO 2017. LNCS 10401. Springer, 2017.Li Z., Tan T.G., Szalachowski P., Sharma V., Zhou J. Post-Quantum VRF and its Applications in Future-Proof Blockchain System. CoRR abs/2109.02012, 2021. У BFT-протоколах маяки випадковості використовують для випадкового вибору лідера раунду або підмножини вузлів, що виконують дорогі кроки протоколу (наприклад, колективне підписання або повторне шифрування).

Ризики та атаки на джерела випадковості