Rondo: Scalable and Reconfiguration-Friendly Randomness Beacon

Rondo: Scalable and Reconfiguration-Friendly Randomness Beacon

Speakers: Xuanji Meng, Chinhai University

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=k9Ty7hKZq_I

Overview

In an increasingly decentralized digital landscape, the need for robust, unpredictable, and publicly verifiable randomness is paramount. This talk at NDSS25 introduces Rondo, a novel Distributed Randomness Beacon (DRB) protocol designed to address critical limitations in existing solutions, specifically concerning scalability and dynamic reconfiguration. Presented by Xuanji Meng from Chinhai University, Rondo offers a significant advancement in generating periodic random numbers for a wide array of decentralized applications and cryptographic protocols.

The core problem Rondo tackles is the inefficiency and rigidity of current DRBs. Many existing protocols suffer from prohibitively high communication costs that scale cubically with the number of participants, and they lack the flexibility for nodes to freely join or leave the system. Rondo aims to overcome these challenges by introducing innovative cryptographic primitives and a Byzantine Fault Tolerant (BFT) consensus mechanism, making it a highly efficient and adaptable solution for modern distributed systems.

This research is vital for the future of decentralized technologies. By providing a DRB that is both scalable and "reconfiguration-friendly" in a partially synchronous network, Rondo enables more secure lotteries, fairer validator selections in Proof-of-Stake blockchains like Ethereum, unbiased online voting systems, and stronger privacy-preserving protocols through zero-knowledge proofs. Its contributions lay foundational groundwork for more resilient and performant trustless environments.

Background

▶ Watch: Addressing scalability & reconfiguration challenges in randomness beacons (2:28)

The concept of a randomness beacon, a publicly verifiable source of unpredictable random numbers, was first formalized by Rabin in 1983. Since then, various approaches have been proposed to realize this concept in a distributed setting, leading to the development of Distributed Randomness Beacons (DRBs). These systems are crucial for ensuring fairness and security in environments where no single entity can be trusted to generate or control randomness.

Key applications of DRBs span several critical domains:

• Blockchain Smart Contracts: They enable secure lottery systems, fair validator selection processes (e.g., in Ethereum or Chainlink), and leader election mechanisms in Proof-of-Stake (PoS) blockchains.
• Online Voting Systems: DRBs can prevent bias and manipulation, ensuring the integrity of election outcomes.
• Zero-Knowledge Proofs (ZKPs): They provide public randomness necessary for constructing privacy-preserving protocols, enhancing the security and non-malleability of proofs.

Despite their fundamental importance and the advancements over the decades, existing DRB protocols face several significant challenges, particularly when deployed in large-scale, dynamic distributed systems:

1. High Message Complexity: Many protocols exhibit an O(N^3) communication cost, where N is the number of participants. This cubic scaling means that as the network grows, the communication overhead becomes astronomically cumbersome, severely limiting their practical scalability.
2. Lack of Dynamic Reconfiguration: Most existing solutions are designed for static sets of participants. They lack the property of dynamic reconfiguration, meaning nodes cannot easily join or leave the system without complex, often disruptive, re-initialization procedures. This rigidity is a major drawback for open, evolving decentralized networks.
3. Increased Latency: Inefficient underlying cryptographic operations and network delays contribute to higher latency. Approaches like threshold BLS signatures, while enhancing security, often involve computationally intensive aggregation overheads, slowing down the overall randomness generation process. These inefficiencies stem from fundamental cryptographic parameters and algorithms that are not optimized for large-scale, dynamic environments. The challenge, therefore, has been to design a DRB that is both scalable in terms of communication and computation, and flexible enough to accommodate dynamic changes in its participant set, all within a partially synchronous network model.

Key Findings

▶ Watch: Understanding Rondo's four-phase randomness generation workflow (5:15)

Rondo addresses the aforementioned challenges by introducing a suite of innovative components and protocols, achieving significant advancements in scalability, reconfigurability, and efficiency. The key findings and contributions presented in the talk are:

1. Asynchronous Verifiable Secret Sharing with Partial Output (AVSS-PoL): Rondo introduces a novel cryptographic primitive named AVSS-PoL. This primitive is specifically designed for efficiency, aiming to lower both computational and communication overheads compared to traditional Verifiable Secret Sharing (VSS) schemes. Its "partial output" characteristic is crucial for streamlining the verification process.

1. Rondo BFT: A Byzantine Fault Tolerant Consensus Protocol with Dynamic Reconfiguration: To enable the dynamic nature required by modern decentralized systems, Rondo integrates Rondo BFT. This is a Byzantine Fault Tolerant (BFT) consensus protocol that extends existing BFT frameworks, specifically building upon HotStuff. A core feature of Rondo BFT is its support for dynamic reconfiguration, allowing participants to join and leave the system freely without compromising security or requiring a system-wide restart.

1. Optimized Polynomial Commitments: Integral to the efficiency of AVSS-PoL, Rondo leverages optimized polynomial commitments. These are specialized cryptographic components used to efficiently commit to and verify polynomial evaluations. By optimizing these commitments, Rondo achieves higher throughput and significantly reduced latency in its operations, particularly in the verification phase of secret sharing.

1. High Throughput with Reduced Latency: Through the synergistic combination of AVSS-PoL and Rondo BFT, the Rondo protocol demonstrably achieves high throughput and reduced latency. Performance evaluations show that Rondo's throughput decreases only slightly as the number of participants increases, in stark contrast to traditional methods like Threshold BLS (TBLS) which experience dramatic performance drops. This confirms Rondo's superior scalability.

In summary, Rondo's key findings present a comprehensive solution to the long-standing problems of scalability and reconfigurability in distributed randomness beacons, making it a robust and practical choice for future decentralized applications.

Technical Deep Dive

▶ Watch: Rondo-BFD: Enabling dynamic reconfiguration for participants (6:30)

Rondo's architecture is meticulously designed to achieve its goals of scalability and reconfiguration-friendliness. The protocol operates in a partially synchronous network model and is structured around a four-phase workflow, underpinned by its novel cryptographic primitives.

Rondo's Main Protocol Workflow

The generation of a random number in Rondo involves a collaborative process among participants, structured into four distinct phases:

1. Commitment Phase: In this initial phase, each participant node generates its own piece of randomness, which serves as a secret. To ensure verifiability and contribute to the final collective randomness, these nodes then use Rondo's specialized AVSS-PoL (Asynchronous Verifiable Secret Sharing with Partial Output) mechanism to share their random secrets. This process involves broadcasting shares and associated verification data to other participants.

1. Validation Phase: Following the commitment, the receiving nodes must verify the correctness of the shared information. The "partial output" feature of AVSS-PoL is crucial here, allowing for an efficient verification process that ensures the integrity of the broadcasted secret shares without requiring full reconstruction at this stage. This step filters out any maliciously or erroneously shared secrets.

1. Agreement Phase: After individual validation, nodes need to reach a consensus on the set of valid secret shares. Any shares identified as incorrect or wrongly broadcast during the validation phase are effectively "aborted." The remaining, correctly shared secrets form the basis for the final randomness. This agreement is facilitated by Rondo BFT, which ensures that all honest nodes agree on the same set of valid contributions, even in the presence of Byzantine adversaries.

1. Reconstruction Phase: In the final phase, once agreement is reached on the valid secret shares, each node uses these shares to locally reconstruct the initial collective randomness. Because all honest nodes have agreed on the same set of shares, they will all reconstruct the same, unpredictable, and verifiable random number, which is then output as the beacon's randomness for that period.

Rondo BFT: The Consensus Engine

Rondo BFT is the backbone that enables dynamic reconfiguration and ensures Byzantine fault tolerance for the randomness beacon. It is an extension of HotStuff, a high-performance BFT consensus protocol known for its "chain-based" approach and linear view changes.

• Foundation on HotStuff: By building on HotStuff, Rondo BFT inherits properties like low latency and high throughput for reaching consensus. HotStuff's design allows for efficient agreement even with a significant fraction of malicious nodes (up to one-third of the participants).
• Dynamic Reconfiguration: The key innovation of Rondo BFT is its ability to support dynamic reconfiguration. This means nodes can join and leave the system freely without compromising the security or liveness of the randomness beacon. This is achieved by embedding membership changes within the consensus process itself, allowing the set of active participants to evolve over time. This flexibility is critical for open, permissionless, or large-scale distributed systems where node churn is expected.
• Byzantine Tolerance: Like its HotStuff foundation, Rondo BFT is Byzantine fault tolerant, meaning it can continue to operate correctly and securely even if a certain number of participant nodes behave maliciously (e.g., sending conflicting messages, withholding information).

AVSS-PoL (Breeze): Efficient Secret Sharing

The talk refers to the instantiation of AVSS-PoL as "Breeze." This primitive is central to Rondo's efficiency gains, particularly in reducing computational and communication overhead.

• Batch Polynomial Evaluations: Breeze significantly improves performance by employing batch polynomial evaluations techniques. Traditionally, verifying multiple polynomial commitments or shares would involve checking each one individually, a time-consuming process. Breeze, however, groups these evaluations, allowing them to be checked simultaneously in a "batch." This dramatically accelerates the verification procedure.
• Reduced Proof Size and Verification Speed: By batching, Breeze reduces the overall size of the cryptographic proofs that need to be transmitted and verified. This, in turn, directly improves verification speed and lowers the computational burden on individual nodes, all while maintaining the necessary security guarantees of verifiable secret sharing.
• Workflow of Breeze:

1. Dealer Shares Secrets: A dealer (the node generating the initial random secret) shares its secret by distributing shares to other participants along with verification data. This data is typically a set of cryptographic commitments that allow receivers to check the integrity of their shares.
2. Receiver Verification: Each receiver independently verifies the correctness of the share and verification data it received. If the validation is successful, the receiver responds with a signature, attesting to the validity of the share.
3. Certificate Collection: The original dealer collects these signatures. Once it gathers a sufficient number of valid signatures (typically corresponding to a threshold t out of N participants), it combines them into a certificate.
4. Broadcast Justification: This certificate is then broadcast to the network. The presence of a valid certificate, containing enough signatures, serves as public justification that the dealer correctly shared its secret, allowing the system to proceed to the agreement phase with confidence in the integrity of that particular secret contribution.

Randomness Requirements

During the Q&A, the speaker clarified the specific properties Rondo ensures for its output randomness, distinguishing them from classical pseudo-randomness:

• Bias Resistance: This property ensures that no participant, or coalition of participants below the Byzantine fault tolerance threshold, has the ability to bias the final output of the beacon. This is critical for applications like lotteries or validator selection where even a slight bias could be exploited.
• Unpredictability: This ensures that no participant can predict the output of the beacon in advance. This is a stronger requirement than merely being indistinguishable from random, as it focuses on the impossibility of foresight by any actor within the system, even those with internal knowledge.

These two properties are extra requirements built upon the fundamental properties of traditional random number generators, which stipulate that the output should be indistinguishable from a truly random string. Rondo's design specifically aims to achieve these enhanced properties in a distributed, adversarial environment.

Demo / Proof of Concept

▶ Watch: Breeze (AVSS-PO): Batch polynomial evaluation for efficiency (7:00)

While the talk did not feature a live, interactive demonstration, it presented compelling performance evaluation results that effectively serve as a proof of concept for Rondo's capabilities. These evaluations showcased the protocol's scalability and efficiency in a practical setting.

The speaker presented a figure that clearly illustrated Rondo's superior scalability compared to traditional methods, specifically Threshold BLS (TBLS)-based approaches. The graph demonstrated that Rondo's throughput—the rate at which it can generate random numbers—decreased only slightly as the number of participants (N) in the system increased. This indicates an efficient scaling behavior, likely approaching linear (O(N)) or sub-quadratic communication complexity, a significant improvement over the O(N^3) complexity of many prior protocols. In stark contrast, the throughput of TBLS-based methods dramatically dropped as N increased, highlighting their inherent limitations for larger distributed systems. This visual evidence strongly supports Rondo's claim of being a scalable randomness beacon.

Furthermore, the presentation included additional performance experiments that detailed the latency breakdown of Rondo's individual components. These breakdowns provide insights into where computational and communication overheads occur within the protocol's four phases (Commitment, Validation, Agreement, Reconstruction) and the underlying cryptographic operations (like AVSS-PoL). By analyzing these breakdowns, the researchers were able to confirm that their optimized components, particularly AVSS-PoL with batch polynomial evaluations, effectively reduce computational overheads and improve verification speeds, contributing to the overall low latency of the protocol.

These performance evaluations, depicted through clear figures and breakdowns, serve as a robust empirical demonstration of Rondo's efficiency, scalability, and practical viability, validating the theoretical advancements claimed by the protocol's design.

Defensive Implications

▶ Watch: Rondo's superior scalability demonstrated in performance evaluation (8:10)

Rondo's advancements in distributed randomness beacon technology have profound defensive implications for anyone building, securing, or auditing decentralized systems. The core benefit lies in providing a more resilient, efficient, and trustworthy source of public randomness, which is a fundamental building block for security in many applications.

1. Enhanced Security for Decentralized Applications: Defenders developing or deploying blockchain smart contracts, decentralized finance (DeFi) protocols, or online voting systems can leverage Rondo to ensure a more robust and unpredictable source of randomness. This directly translates to more secure lotteries, fairer validator selection processes, and verifiable, unbiased election outcomes. The bias resistance and unpredictability properties guaranteed by Rondo make these applications significantly harder to manipulate or exploit by malicious actors.

1. Improved Resilience to Participant Churn: The dynamic reconfiguration capability of Rondo BFT is a critical defensive feature. In real-world decentralized networks, nodes frequently join and leave. Traditional DRBs that lack this flexibility are brittle; changes in membership can lead to service disruptions, security vulnerabilities, or require complex, manual re-initialization processes. Rondo's ability to seamlessly accommodate node churn makes the underlying systems more resilient to network instability, node failures, or even targeted attacks aimed at disrupting the participant set. This reduces the attack surface related to membership changes.

1. Scalability Against Growth and Attacks: Rondo's high scalability, demonstrated by its minimal throughput degradation as N increases, means that systems relying on it can grow to accommodate a larger number of participants without suffering severe performance penalties. From a defensive perspective, this enables the deployment of DRBs in larger, more distributed networks, which inherently offers greater decentralization and thus better resistance to single points of failure or concentrated attacks. A more distributed system is harder to compromise.

1. Efficiency for Resource-Constrained Environments: The reduced computational and communication overheads, thanks to AVSS-PoL and optimized polynomial commitments, mean that Rondo can be implemented in environments with more constrained resources or where high transaction throughput is required. This efficiency allows defenders to maintain strong security guarantees without incurring prohibitive operational costs, making secure randomness generation more accessible and practical.

1. Foundation for Stronger Privacy Protocols: For systems employing zero-knowledge proofs (ZKPs), Rondo can provide the necessary public randomness with higher integrity and efficiency. This bolsters the security and non-malleability of privacy-preserving protocols, ensuring that the randomness used in setup or challenge phases cannot be influenced by adversaries, thereby strengthening the overall privacy guarantees.

In essence, defenders should view Rondo as a critical infrastructure upgrade for any decentralized system relying on shared, unpredictable randomness. By adopting or integrating Rondo's principles, they can build more secure, resilient, and scalable applications that are better equipped to withstand the complex threats present in adversarial distributed environments.

Key Takeaways

• Addresses Core DRB Challenges: Rondo provides a scalable and reconfiguration-friendly Distributed Randomness Beacon (DRB) protocol, directly tackling the high message complexity (O(N^3)) and rigidity of existing solutions.
• Novel Cryptographic Primitives: It introduces AVSS-PoL (Asynchronous Verifiable Secret Sharing with Partial Output) for efficient secret sharing and optimized polynomial commitments to reduce computational and communication overheads.
• Dynamic Reconfiguration via Rondo BFT: Rondo integrates Rondo BFT, a Byzantine Fault Tolerant consensus protocol built on HotStuff, which enables nodes to dynamically join and leave the system without compromising security.
• Superior Performance: Performance evaluations demonstrate Rondo's high scalability, with throughput decreasing only slightly as the number of participants increases, a significant improvement over traditional methods like Threshold BLS.
• Enhanced Security Properties: Rondo ensures crucial randomness properties like bias resistance and unpredictability, making it suitable for high-stakes applications requiring verifiable and unmanipulable randomness.
• Enables Robust Decentralized Applications: Rondo is a foundational component for securing and enhancing fairness in blockchain smart contracts, validator selection, online voting systems, and privacy-preserving protocols like zero-knowledge proofs.

About the Speaker(s)

Xuanji Meng is a researcher from Chinhai University. At NDSS25, he presented the new work "Rondo: Scalable and Reconfiguration-Friendly Randomness Beacon," highlighting his expertise in distributed systems, cryptography, and blockchain technologies. His research focuses on developing innovative solutions to fundamental challenges in decentralized environments, particularly concerning the efficiency and adaptability of core cryptographic primitives like randomness beacons.