NDSS 2025 – Rondo: Scalable And Reconfiguration-Friendly Randomness Beacon

The paper introduces Rondo, a scalable and reconfiguration-friendly distributed randomness beacon (DRB) protocol. Rondo operates in a partially synchronous model and utilizes batched asynchronous verifiable secret sharing (bAVSS). It avoids the high message cost typically associated with DRB protocols, achieving better scalability. The core innovation is the introduction of a new bAVSS variant called batched asynchronous verifiable secret sharing with partial output (bAVSS-PO). A protocol named Breeze implements bAVSS-PO, achieving optimal message complexity for the sharing stage. To support reconfiguration, Rondo incorporates Rondo-BFT, a dynamic Byzantine fault-tolerant protocol inspired by Dyno. Rondo-BFT periodically generates randomness beacon output, making it suitable for DRB applications. The authors implemented and evaluated their protocols on Amazon EC2 with up to 91 instances. Evaluation results demonstrate that Rondo outperforms existing works in terms of throughput and scalability. The Network and Distributed System Security Symposium (NDSS) is a platform fostering research exchange in network and distributed system security. The NDSS symposium is the source for this content. The NDSS Symposium publishes content on the organization's YouTube channel.