Fast cryptographic accumulator and vector commitment library, originally written by Cambrian Technologies [GitHub].
Disclaimer: This library is intended to be production-quality code, but it has not been independently-audited for correctness or tested to a critical degree. As such, please treat this library as research-grade for the time being.
To ensure correspondence between accumulator methods and logical set operations in your application, you must ensure that no element is accumulated twice. In particular, deleting a doubly-accumulated element will remove only one "copy" of it from the accumulator, meaning that its membership can still be verified. Hence, an accumulator without this invariant can be viewed as a multiset.
An accumulator is a cryptographic primitive which functions essentially as a secure decentralized set. It allows parties to maintain consensus on a set of values via a succinct binding commitment as well as to issue efficiently verifiable (non)membership proofs for elements of interest, all without requiring any party to store the entire set.
Similarly to a Merkle tree, the accumulator stores its state commitment in constant space. A notable difference, however, is that its inclusion and exclusion proofs also take up constant space, and can be verified in constant time. For a far more detailed discussion of accumulators as implemented here, see Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains (Boneh, Bünz, and Fisch 2018) [Link].
Throughout our code, we refer to this paper as
BBF. We also refer to another paper, Universal
Accumulators with Efficient Nonmembership Proofs (Li, Li, Xue 2007)
A vector commitment (VC) is a closely-related primitive, distinguished from an accumulator in that it provides a position-binding commitment to state. That is, a VC allows parties to prove or disprove that a certain element exists at a certain position.
(Think VC : Vector :: Accumulator : Set.)
Our vector commitment implementation is a work-in-progress (WIP), and should be treated with even more skepticism than our accumulators.
// A very basic example. use accumulator::Accumulator; use accumulator::group::Rsa2048; let acc = Accumulator::<Rsa2048, &'static str>::empty(); // Accumulate "dog" and "cat". The `add_with_proof` method returns the new accumulator state // and a proof that you accumulated "dog" and "cat". let (acc, proof) = acc.add_with_proof(&["dog", "cat"]); // A network participant who sees (acc, proof, and ["dog", "cat"]) can verify that the update // was formed correctly ... assert!(acc.verify_membership_batch(&["dog", "cat"], &proof)); // ... and trying to verify something that has not been accumulated will fail. assert!(!acc.verify_membership(&"cow", &proof));
Typical users of this library will access public-facing routines on
vector_commitment. However, we also export internal modules for useful traits, types (such as
Rsa2048 group), and specialized procedures. Use internal components at your own risk.
You can find a more interesting application of our library here, where we create a proof-of-concept for stateless Bitcoin nodes!
Accumulator and vector commitment operations take place over algebraic groups with certain cryptographic properties. We provide implementations for two suitable groups: (1) an RSA group with the RSA-2048 modulus and (2) an ideal class group with a fixed discriminant generated by OpenSSL.
The RSA group is fast but relies on the security of the RSA-2048 modulus and needs trusted setup if using a different modulus. The class group is slower but eliminates the need for a trusted setup. For more on class groups, please visit this thorough explainer by contributor Michael Straka.
Most accumulator or vector commitment functions will bottleneck in hashing to large primes. To
alleviate this, we created a zero-allocation
U256 type that uses the low-level
functions in GMP. Our
hash_to_prime uses this type internally.
Class groups are currently not performant for any meaningful use case. A pull request is in the works to drastically improve their performance using techniques learned from the Chia VDF competition.
Implementations for different mathematical groups, each of which satisfies our
This module wraps
Succinct proofs over unknown-order groups. These proofs are used as building blocks for many of the cryptographic primitives in this library.
Zero-allocation U256 and U512 types built on GMP. We created this module specifically for our use case of implementing primality checking over 256-bit integers, but it may be worth polishing a bit for more general use.
Miscellaneous functions used throughout the library.
A cryptographic accumulator. Wraps a single unknown-order group element and phantom data
representing the type
A succinct proof of membership (some element is in some accumulator).
A succinct proof of nonmembership (some element is not in some accumulator).
A vector commitment, wrapping an underlying accumulator. The accumulator contains indices of an abstract vector where the corresponding bit is True.
A vector commitment proof.
A witness to one or more values in an accumulator, represented as an accumulator.
The different types of accumulator errors.
The different types of vector commitment errors.