Class Groups for Cryptographic Accumulators

Late last year Benedikt Bunz and Ben Fisch, both PhD students at Stanford University, released a paper along with Dan Boneh titled “Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains”. In it they use some basic group theory to build a dynamic accumulator, which allows for storing and deleting elements in addition to the use of both membership and non-membership proofs. It can be used to create a vector commitment data structure analogous to Merkle trees, with the main difference being that it allows for constant-sized inclusion proofs, where a Merkle tree has $O(\log n)$ sized inclusion proofs where $n$ is the number of elements being stored.

Posted