HeadStart: Efficiently Verifiable and Low-Latency Participatory Randomness Generation at Scale

—Generating randomness by public participation allows participants to directly contribute randomness and verify the result’s security. Ideally, the difficulty of participating in such activities should be as low as possible to reduce the computational burden of being a contributor. However, existing randomness generation protocols are unsuitable for this scenario because of scalability or usability issues. Hence, this paper presents HeadStart, a participatory randomness protocol designed for public participation at scale. HeadStart allows contributors to verify the result on commodity devices efficiently and provides a parameter L that can make the result-publication latency L times lower. Additionally, we propose two implementation improvements to speed up the verification further and reduce the proof size. The verification complexity of HeadStart is only O ( L × polylog ( T ) + log C ) for a contribution phase lasting for time T with C contributions.