Paper 2021/1698

Efficient Random Beacons with Adaptive Security for Ungrindable Blockchains

Aggelos Kiayias, Cristopher Moore, Saad Quader, and Alexander Russell


We describe and analyze a simple protocol for $n$ parties that implements a randomness beacon: a sequence of high entropy values, continuously emitted at regular intervals, with sub-linear communication per value. The algorithm can tolerate a $(1 - \epsilon)/2$ fraction of the $n$ players to be controlled by an adaptive adversary that may deviate arbitrarily from the protocol. The randomness mechanism relies on verifiable random functions (VRF), modeled as random functions, and effectively stretches an initial $\lambda$-bit seed to an arbitrarily long public sequence so that (i) with overwhelming probability in $k$--the security parameter--each beacon value has high min-entropy conditioned on the full history of the algorithm, and (ii) the total work and communication required per value is $O(k)$ cryptographic operations. The protocol can be directly applied to provide a qualitative improvement in the security of several proof-of-stake blockchain algorithms, rendering them safe from ``grinding'' attacks.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Coin-flippingblockchain protocolpseudorandomness
Contact author(s)
alexander russell @ uconn edu
2021-12-30: received
Short URL
Creative Commons Attribution


      author = {Aggelos Kiayias and Cristopher Moore and Saad Quader and Alexander Russell},
      title = {Efficient Random Beacons with Adaptive Security for Ungrindable Blockchains},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1698},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.