Gas-Efficient Decentralized Random Beacons

Decentralized random number generation is a widely-studied problem in the blockchain community and much attention has been paid to the so-called on-chain random beacons, i.e. smart contracts that generate randomness which can in turn be used in other contracts. Following the classical methodology of RANDAO, most on-chain beacons receive inputs from a large number n of participants and then aggregate them to compute a final random output. The aggregation is done in a manner that ensures the final output is uniformly random as long as at least one of the participants acts honestly. While being highly successful in providing security guarantes such as unpredictability and tamper-resistance, a major downside of these beacons is their cost. Since every participant has to call a function in the smart contract to provide their input, the total gas usage to generate a single random number is at least Ω(n). In this work, we propose a novel protocol that offloads most of the on-chain communication between the participants and the smart contract to an alternative off-chain communication with a dealer. This leads to a gas-efficient on-chain random beacon with only O(1) gas usage per generated output. Crucially, our protocol is trustless and the dealer is unable to predict or tamper with the result. We maintain the same security guarantees as previous on-chain beacons, while significantly reducing the gas usage. We also show that our protocol is secure even if all but one of the participants, potentially including the dealer, are dishonest.