Paper 2025/406

AsyRand: asynchronous distributed randomness beacon with reconfiguration

Abstract

Distributed randomness beacon protocols, which generate publicly verifiable randomness at regular intervals, are crucial for a wide range of applications. The publicly verifiable secret sharing (PVSS) scheme is a promising cryptographic primitive for implementing beacon protocols, such as Hydrand (S\&P'20), SPURT (S\&P'22), OptRand (NDSS'23) and GRandLine (CCS'24). However, two key challenges remain unresolved: asynchrony and reconfiguration. In this paper, we introduce the AsyRand beacon protocol to address these challenges. First, we incorporate a producer-consumer model to decouple the production and consumption of PVSS commitments, which are managed using queue data structures. Then, we leverages reliable broadcast (RBC) for message dissemination in a producer process and invents a t-validated asynchronous Byzantine agreement (t-VABA) protocol to consume PVSS commitments. Consequently, the producer and consumer processes can operate simultaneously and asynchronously, without the need for a global clock. Moreover, the producer-consumer model enables each party to detect potential faults in other parties by monitoring the queue states. When needed, honest parties can initiate a removal process for faulty parties via a t-VABA protocol. Also, a new party can leverage RBC protocol to request to join in without system restart. As an independent contribution, we propose a novel PVSS scheme based on the Sigma protocol and Fiat-Shamir heuristic. Regarding complexity, AsyRand achieves state-of-the-art performance with O(n^2) communication complexity, O(n) computation complexity, and O(n) verification complexity. Experimental results highlight the high performance of AsyRand compared to related works.