Paper 2024/641

Rondo: Scalable and Reconfiguration-Friendly Randomness Beacon

Xuanji Meng, Tsinghua University
Xiao Sui, Tsinghua University
Zhaoxin Yang, Tsinghua University
Kang Rong, Blockchain Platform Division, Ant Group
Wenbo Xu, Blockchain Platform Division, Ant Group
Shenglong Chen, Blockchain Platform Division, Ant Group
Ying Yan, Blockchain Platform Division, Ant Group
Sisi Duan, Tsinghua University
Abstract

We present Rondo, a scalable and reconfiguration-friendly distributed randomness beacon (DRB) protocol in the partially synchronous model. Rondo is the first DRB protocol that is built from batched asynchronous verifiable secret sharing (bAVSS) and meanwhile avoids the high $O(n^3)$ message cost, where $n$ is the number of nodes. Our key contribution lies in the introduction of a new variant of bAVSS called batched asynchronous verifiable secret sharing with partial output (bAVSS-PO). bAVSS-PO is a weaker primitive than bAVSS but allows us to build a secure and more scalable DRB protocol. We propose a bAVSS-PO protocol Breeze. Breeze achieves the optimal $O(n)$ messages for the sharing stage and allows Rondo to offer better scalability than prior DRB protocols. Additionally, to support the reconfiguration, we introduce Rondo-BFT, a dynamic and partially synchronous Byzantine fault-tolerant protocol inspired by Dyno (S\&P 2022). Unlike Dyno, Rondo-BFT provides a communication pattern that generates randomness beacon output periodically, making it well-suited for DRB applications. We implement our protocols and evaluate the performance on Amazon EC2 using up to 91 instances. Our evaluation results show that Rondo achieves higher throughput than existing works and meanwhile offers better scalability, where the performance does not degrade as significantly as $n$ grows.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. Network and Distributed System Security (NDSS)
Keywords
Randomness BeaconSecret SharingBFT
Contact author(s)
mxj21 @ mails tsinghua edu cn
suixiao @ mail tsinghua edu cn
zhaoxin_yang @ tsinghua edu cn
rongkang rong @ antgroup com
xuwenbo xwb @ antgroup com
shenglong chensl @ antgroup com
fuying yy @ antgroup com
duansisi @ tsinghua edu cn
History
2024-10-17: last of 2 revisions
2024-04-26: received
See all versions
Short URL
https://ia.cr/2024/641
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/641,
      author = {Xuanji Meng and Xiao Sui and Zhaoxin Yang and Kang Rong and Wenbo Xu and Shenglong Chen and Ying Yan and Sisi Duan},
      title = {Rondo: Scalable and Reconfiguration-Friendly Randomness Beacon},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/641},
      year = {2024},
      url = {https://eprint.iacr.org/2024/641}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.