Paper 2025/406

AsyRand: An Asynchronous Randomness Beacon via Look-Ahead Agreement

Liang Zhang, Hong Kong University of Science and Technology
Binyang Hou, Fudan University
Zhengxuan Guo, Hong Kong University of Science and Technology
Haibin Kan, Fudan University
Jiheng Zhang, Hong Kong University of Science and Technology
Moti Yung, Google LLC and Columbia University
Abstract

Asynchronous randomness beacons must preserve agreement and sustain output generation despite Byzantine faults while preventing adversarial bias. We present $\mathsf{AsyRand}$, a publicly verifiable randomness beacon that combines publicly verifiable secret sharing (PVSS) with local-coin asynchronous binary agreement (ABA). Its Producer-Consumer design overlaps PVSS preparation with beacon generation and consumes one accepted PVSS object per output. Column agreement amortizes coordination across multiple outputs. Its look-ahead agreement fixes the successor column's accepted contributions before current contributions are revealed, while recent-contributor exclusion ensures an honest contribution in every $f+1$ consecutive outputs, where $f$ bounds the number of Byzantine parties. Under a production window $\ge2$, every fixed epoch completes with probability one. These mechanisms, together with PVSS secrecy and beacon chaining, provide unpredictability and bias resistance for fixed targets at least $f+1$ epochs ahead. The communication complexity is $O(n^2)$ per output in the optimistic case. We instantiate $\mathsf{AsyRand}$ using ALBATROSS PVSS (Cascudo et al., ASIACRYPT'20) and WaterBear Quadratic-ABA (Zhang et al., Usenix Security'23). Experiments with 16--121 parties across eight regions show that $\mathsf{AsyRand}$ achieves higher throughput than our implementations of GRandLine (Bacho et al., CCS'24) and SPURT (Das et al., S\&P'22). In the fault-free case, at 121 parties, $\mathsf{AsyRand}$ achieves $1.66\times$ and $14.03\times$ their respective throughput.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
PVSSdistributed randomness beaconRBCABA
Contact author(s)
briliasm @ gmail com
25113050255 @ m fudan edu cn
zguocd @ connect ust hk
hbkan @ fudan edu cn
jiheng @ ust hk
motiyung @ gmail com
History
2026-11-03: last of 12 revisions
2025-03-03: received
See all versions
Short URL
https://ia.cr/2025/406
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2025/406,
      author = {Liang Zhang and Binyang Hou and Zhengxuan Guo and Haibin Kan and Jiheng Zhang and Moti Yung},
      title = {{AsyRand}: An Asynchronous Randomness Beacon via Look-Ahead Agreement},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/406},
      year = {2025},
      url = {https://eprint.iacr.org/2025/406}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.