Cryptology ePrint Archive: Report 2021/1698

Efficient Random Beacons with Adaptive Security for Ungrindable Blockchains

Aggelos Kiayias and Cristopher Moore and Saad Quader and Alexander Russell

Abstract: 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.

Category / Keywords: cryptographic protocols / Coin-flipping; blockchain protocol; pseudorandomness

Date: received 28 Dec 2021

Contact author: alexander russell at uconn edu

Available format(s): PDF | BibTeX Citation

Version: 20211230:171316 (All versions of this report)

Short URL: ia.cr/2021/1698