### OptRand: Optimistically responsive distributed random beacons

##### Abstract

Public random beacons publish random numbers at regular intervals, which anyone can obtain and verify. The design of public distributed random beacons has been an exciting research direction with significant implications for blockchains, voting, and beyond. Distributed random beacons, in addition to being bias-resistant and unpredictable, also need to have low communication overhead and latency, high resilience to faults, and ease of reconfigurability. Existing synchronous random beacon protocols sacrifice one or more of these properties. In this work, we design an efficient unpredictable synchronous random beacon protocol, OptRand, with quadratic (in the number n of system nodes) communication complexity per beacon output. First, we innovate by employing a novel combination of bilinear pairing based publicly verifiable secret-sharing and non-interactive zero-knowledge proofs to build a linear (in n) sized publicly verifiable random sharing. Second, we develop a state machine replication protocol with linear-sized inputs that is also optimistically responsive, i.e., it can progress responsively at actual network speed during optimistic conditions, despite the synchrony assumption, and thus incur low latency. In addition, we present an efficient reconfiguration mechanism for OptRand that allows nodes to leave and join the system. Our experiments show our protocols perform significantly better compared to state-of-the-art protocols under optimistic conditions and on par with state-of-the-art protocols in the normal case. We are also the first to implement a reconfiguration mechanism for distributed beacons and demonstrate that our protocol continues to be live during reconfigurations.

Note: This is the full version of the paper presented at NDSS 2023.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. NDSS
DOI
10.14722/ndss.2023.24832
Keywords
Random Beacons
Contact author(s)
abhatk @ purdue edu
nxs4564 @ rit edu
aniket @ purdue edu
kartik @ cs duke edu
History
2023-01-16: last of 3 revisions
See all versions
Short URL
https://ia.cr/2022/193

CC BY

BibTeX

@misc{cryptoeprint:2022/193,
author = {Adithya Bhat and Nibesh Shrestha and Aniket Kate and Kartik Nayak},
title = {OptRand: Optimistically responsive distributed random beacons},
howpublished = {Cryptology ePrint Archive, Paper 2022/193},
year = {2022},
doi = {10.14722/ndss.2023.24832},
note = {\url{https://eprint.iacr.org/2022/193}},
url = {https://eprint.iacr.org/2022/193}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.