Paper 2025/1041

Rubato: Provably Post-Quantum Secure and Batched Asynchronous Randomness Beacon

Abstract

Distributed randomness beacons are essential for distributed systems (e.g., blockchain and MPC), providing unbiased and unpredictable shared randomness. However, implementations in asynchronous networks often suffer from poor scalability, 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 intensity 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(c \log n)$ factor compared to HashRand and resolves the circular dependency between beacon and BAB-SMR in asynchronous settings. Experiments on AWS demonstrate that Rubato achieves ideal overall performance in scalability, resource usage, and throughput; for instance, at $n=121$ nodes, it produces an average of 174 beacons per minute, with RubatoSMR further optimizing memory and bandwidth consumption.