International Association
for Cryptologic Research

Deployments of cryptographic protocols with thousands of participants are becoming more and more common. In these large-scale, permissionless settings, communication complexity is often a limiting factor. In practice, two tools are commonly used to address this challenge: committee sampling and gossip networks. Committee sampling reduces complexity by restricting most of the communication to a small, randomly sampled committee of participants. Gossip protocols replace a fully connected communication network (which is impractical on an Internet scale) with a sparse communication graph. Existing committee-sampling protocols either require a setup assumption (which is problematic in a fully decentralized setting) or have high communication complexity themselves. In this work, we construct a communication-efficient setup-free protocol for committee sampling. Our starting point is the protocol of Andrychowicz and Dziembowski (CRYPTO'15), who showed how to construct a setup-free random beacon based on proofs-of-work (PoWs) in the random-oracle model (ROM). Our protocol works in a similar setting, and samples a committee in which parties are chosen proportionally to their resource expenditure. We improve upon their construction in two ways: (1) we construct a formal framework for general resource proofs (RPs), and use it to generalize from PoWs to a larger class of resources, and (2) for a subset of RPs (including PoWs), we construct a much more efficient committee-sampling protocol that requires subquadratic communication. Our protocol is designed in the ROM and makes use of VDFs, as well as gossip techniques in the spirit of Cohen, Loss, and Moran (FC'24).