Xuanji Meng (Tsinghua University), Xiao Sui (Shandong 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)

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.

View More Papers

A Field Study to Uncover and a Tool to...

Leon Kersten (Eindhoven University of Technology), Kim Beelen (Eindhoven University of Technology), Emmanuele Zambon (Eindhoven University of Technology), Chris Snijders (Eindhoven University of Technology), Luca Allodi (Eindhoven University of Technology)

Read More

Silence False Alarms: Identifying Anti-Reentrancy Patterns on Ethereum to...

Qiyang Song (Institute of Information Engineering, Chinese Academy of Sciences; School of Cyber Security, University of Chinese Academy of Sciences), Heqing Huang (Institute of Information Engineering, Chinese Academy of Sciences), Xiaoqi Jia (Institute of Information Engineering, Chinese Academy of Sciences; School of Cyber Security, University of Chinese Academy of Sciences), Yuanbo Xie (Institute of Information…

Read More

Automatic Insecurity: Exploring Email Auto-configuration in the Wild

Shushang Wen (School of Cyber Science and Technology, University of Science and Technology of China), Yiming Zhang (Tsinghua University), Yuxiang Shen (School of Cyber Science and Technology, University of Science and Technology of China), Bingyu Li (School of Cyber Science and Technology, Beihang University), Haixin Duan (Tsinghua University; Zhongguancun Laboratory), Jingqiang Lin (School of Cyber…

Read More

LAMP: Lightweight Approaches for Latency Minimization in Mixnets with...

Mahdi Rahimi (KU Leuven), Piyush Kumar Sharma (University of Michigan), Claudia Diaz (KU Leuven)

Read More