Researchers replace recurring randomness beacons in blockchains

Researchers Damiano Abram, Marshall Ball, Juan Garay and Aggelos Kiayias propose replacing recurring public randomness beacons in permissionless consensus with d-wise independent distributed samplers combined with a common random string (CRS). The paper was accepted for presentation at Crypto 2026.

The University of Edinburgh lists the manuscript under the title “Permissionless consensus from a common random string.” Crypto 2026 runs in Santa Barbara from Aug. 17 through Aug. 20. The Edinburgh record indicates the manuscript was embargoed until Aug. 20 at 00:00 BST.

The paper addresses how permissionless systems can reach Byzantine agreement when participants are not known in advance, there is no public-key infrastructure, and only an upper bound on participant numbers is assumed. The authors present the distributed samplers as a replacement for a service that periodically emits fresh public randomness.

The distributed samplers are d-wise independent and are intended to keep multiple protocol executions secure without a recurring external beacon. The construction requires a shared setup: a common random string made available at the start of the protocol. The paper states the CRS does not need a particular structure and does not require a precise sampling time. Security of the samplers relies on the decisional Diffie-Hellman (DDH) and learning with errors (LWE) assumptions.

The authors combine the samplers with proofs of work based on fine-grained complexity assumptions to build multi-verifier signatures of work, which the consensus protocol uses to verify computational effort. The paper notes the new design replaces the recurring-beacon dependency in an earlier 2024 construction that used proofs of work and fine-grained assumptions.

The manuscript is theoretical. Public materials do not provide a numeric corruption threshold, exact synchrony or communication assumptions, resource costs, experimental results, or performance benchmarks. The public record does not describe the protocol as ready for deployment or as an upgrade for live networks, and it does not provide data to support direct comparisons with operational security models of deployed systems.