Paper 2023/1755

Random Beacons in Monte Carlo: Efficient Asynchronous Random Beacon without Threshold Cryptography

Akhil Bandarupalli, Purdue University West Lafayette
Adithya Bhat, Visa Research
Saurabh Bagchi, Purdue University West Lafayette
Aniket Kate, Purdue University West Lafayette, Supra Research
Michael Reiter, Duke University

Regular access to unpredictable and bias-resistant randomness is important for applications such as blockchains, voting, and secure distributed computing. Distributed random beacon protocols address this need by distributing trust across multiple nodes, with the majority of them assumed to be honest. Numerous applications across the blockchain space have led to the proposal of several distributed random beacon protocols, with some already implemented. However, many current random beacon systems rely on threshold cryptographic setups or exhibit high computational costs, while others expect the network to be partial or bounded synchronous. To overcome these limitations, we propose HashRand, a computation and communication-efficient asynchronous random beacon protocol that only demands secure hash and pairwise secure channels to generate beacons. HashRand has a per-node amortized communication complexity of $\mathcal{O}(\lambda n \log(n))$ bits per beacon. The computational efficiency of HashRand is attributed to the two orders of magnitude lower time of a one-way Hash computation compared to discrete log exponentiation. Interestingly, besides reduced overhead, HashRand achieves Post-Quantum security by leveraging the secure Hash function against quantum adversaries, setting it apart from other random beacon protocols that use discrete log cryptography. In a geo-distributed testbed of $n=136$ nodes, HashRand produces 78 beacons per minute, which is at least 5x higher than Spurt [IEEE S\&P'22]. We also demonstrate the practical utility of HashRand by implementing a Post-Quantum secure Asynchronous SMR protocol, which has a response rate of over 135k transactions per second at a latency of $2.3$ seconds over a WAN for $n=16$ nodes.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2024
Random BeaconHash functionAsynchronous protocolByzantine Fault Tolerance
Contact author(s)
abandaru @ purdue edu
haxolotl research @ gmail com
sbagchi @ purdue edu
aniket @ purdue edu
michael reiter @ duke edu
2024-07-05: last of 2 revisions
2023-11-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Akhil Bandarupalli and Adithya Bhat and Saurabh Bagchi and Aniket Kate and Michael Reiter},
      title = {Random Beacons in Monte Carlo: Efficient Asynchronous Random Beacon without Threshold Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1755},
      year = {2023},
      doi = {10.1145/3658644.3670326},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.