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
[ Cryptology ePrint archive ]