International Association for Cryptologic Research

International Association
for Cryptologic Research


Benedikt Bünz


Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains
Dan Boneh Benedikt Bünz Ben Fisch
We present batching techniques for cryptographic accumulators and vector commitments in groups of unknown order. Our techniques are tailored for distributed settings where no trusted accumulator manager exists and updates to the accumulator are processed in batches. We develop techniques for non-interactively aggregating membership proofs that can be verified with a constant number of group operations. We also provide a constant sized batch non-membership proof for a large number of elements. These proofs can be used to build the first positional vector commitment (VC) with constant sized openings and constant sized public parameters. As a core building block for our batching techniques we develop several succinct proof systems in groups of unknown order. These extend a recent construction of a succinct proof of correct exponentiation, and include a succinct proof of knowledge of an integer discrete logarithm between two group elements. We circumvent an impossibility result for Sigma-protocols in these groups by using a short trapdoor-free CRS. We use these new accumulator and vector commitment constructions to design a stateless blockchain, where nodes only need a constant amount of storage in order to participate in consensus. Further, we show how to use these techniques to reduce the size of IOP instantiations, such as STARKs. The full version of the paper is available online [BBF18b].
Verifiable Delay Functions 📺
We study the problem of building a verifiable delay function (VDF). A $$\text {VDF}$$VDFrequires a specified number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified. $$\text {VDF}$$VDFs have many applications in decentralized systems, including public randomness beacons, leader election in consensus protocols, and proofs of replication. We formalize the requirements for $$\text {VDF}$$VDFs and present new candidate constructions that are the first to achieve an exponential gap between evaluation and verification time.