random beacons are crucial components in blockchain consensus, secure multiparty computation, and decentralized applications, providing high-quality randomness for these applications. However, random beacon services operated by a single organization face centralization issues and cannot be fully trusted by mission-critical applications due to possible breaches and collusion. Asynchronous distributed random beacon protocols are proposed as a promising alternative to such centralized services, since they can generate high-quality randomnesses that are unbiased and unpredictable for critical applications in the adversarial asynchronous Internet. However, they either suffer from expensive communication overhead or lack accommodation for efficient dynamic participation. To address these issues, we propose a practical asynchronous random beacon protocol that can be efficiently reconfigured to support rotations of participating nodes, reducing the reconfiguration’s communication complexity from O(λn3) to O(λ κn2), where λ is the cryptography security parameter, n is the size of nodes in the network, and κ is the small size of a any-trust sub-committee (which approximates a constant number about several dozens). We also demonstrate the performance and security of our scheme through thorough analysis and extensive experiments.
distributed random beacon; asynchronous multi-party protocol; fault-tolerance system; threshold cryptosystem reconfiguration