You are looking at a specific version 20181210:211743 of this paper. See the latest version.

Paper 2018/1188

Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains

Dan Boneh and Benedikt Bünz and Ben Fisch

Abstract

We present batching techniques for cryptographic accumulators and vector commitments in groups of unknown order. Our techniques are tailored for decentralized 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 a positional vector commitment with constant sized openings and constant sized public parameters. As a core building block for our batching techniques we develop several succinct proofs for groups of unknown order. These include a proof that an exponentiation was done correctly and a zero-knowledge proof of knowledge of an integer discrete logarithm between two group elements. We use these new constructions to design a stateless blockchain, where nodes only need a constant storage. Further we show that our vector commitment can be used to significantly reduce the size of IOP instantiations, such as STARKs.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
accumulatorszero knowledgecommitmentsRSA
Contact author(s)
benedikt @ cs stanford edu
History
2021-05-20: last of 9 revisions
2018-12-10: received
See all versions
Short URL
https://ia.cr/2018/1188
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.