[−][src]Crate accumulator
Fast cryptographic accumulator and vector commitment library, originally written by Cambrian Technologies [GitHub].
Disclaimer: This library is intended to be productionquality code, but it has not been independentlyaudited for correctness or tested to a critical degree. As such, please treat this library as researchgrade for the time being.
Important Note
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 doublyaccumulated 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.
What is an accumulator?
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)
[Link], abbreviated
henceforth as LLX
.
What is a vector commitment?
A vector commitment (VC) is a closelyrelated primitive, distinguished from an accumulator in that it provides a positionbinding 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 workinprogress (WIP), and should be treated with even more skepticism than our accumulators.
Usage
// 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 publicfacing routines on accumulator
and
vector_commitment
. However, we also export internal modules for useful traits, types (such as
the 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 proofofconcept for stateless Bitcoin nodes!
Groups
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 RSA2048 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 RSA2048 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.
Performance
Most accumulator or vector commitment functions will bottleneck in hashing to large primes. To
alleviate this, we created a zeroallocation U256
type that uses the lowlevel mpn_
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.
Modules
group  Implementations for different mathematical groups, each of which satisfies our

hash  This module wraps 
proof  Succinct proofs over unknownorder groups. These proofs are used as building blocks for many of the cryptographic primitives in this library. 
uint  Zeroallocation U256 and U512 types built on GMP. We created this module specifically for our use case of implementing primality checking over 256bit integers, but it may be worth polishing a bit for more general use. 
util  Miscellaneous functions used throughout the library. 
Structs
Accumulator  A cryptographic accumulator. Wraps a single unknownorder group element and phantom data
representing the type 
MembershipProof  A succinct proof of membership (some element is in some accumulator). 
NonmembershipProof  A succinct proof of nonmembership (some element is not in some accumulator). 
VectorCommitment  A vector commitment, wrapping an underlying accumulator. The accumulator contains indices of an abstract vector where the corresponding bit is True. 
VectorProof  A vector commitment proof. 
Witness  A witness to one or more values in an accumulator, represented as an accumulator. 
Enums
AccError  The different types of accumulator errors. 
VCError  The different types of vector commitment errors. 