Paper 2025/406
AsyRand: An Asynchronous Randomness Beacon via Look-Ahead Agreement
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
-
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}
}