Rubato: Efficient Post-Quantum Asynchronous Distributed Randomness Beacon With Integrated Consensus

Distributed randomness beacons are essential for distributed systems (e.g., blockchain and MPC), providing un biased and unpredictable shared randomness. However, implementations in asynchronous networks often suffer from poor scal ability, low throughput, and high resource consumption when deployed as independent protocols. The state-of-the-art HashRand (CCS'24) achieves high throughput and low computational in tensity using only lightweight post-quantum cryptographic primitives for an independent asynchronous beacon. Building further on this, we propose Rubato, a low-overhead, high-throughput beacon protocol that leverages lightweight batched Asynchronous Complete Secret Sharing with Byzantine Atomic Broadcast-based state machine replication (via our tailored RubatoSMR). Rubato reduces communication complexity by an O(clogn) factor compared to HashRand and resolves the circular dependency between beacon and BAB-SMR in asynchronous settings. Experiments on AWSdemonstrate that Rubato achieves ideal overall performance in scalability, resource usage, and throughput; for instance, at n = 121nodes, it produces an average of 174 beacons per minute, with RubatoSMR further optimizing memory and bandwidth consumption.