[−][src]Crate accumulator

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.

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 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.

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 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.

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 public-facing 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 proof-of-concept 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 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.

Performance

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 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 `UnknownOrderGroup` trait. They can be used with the accumulator and vector commitment structures, or standalone if you have a custom application.
hash	This module wraps `blake2b_rfc` into a convenient hashing interface (`GeneralHasher`) and exports the generalized `hash` function. Also exported is `hash_to_prime`, which works by repeatedly `hash`ing a value together with an incrementing nonce until the output is prime.
proof	Succinct proofs over unknown-order groups. These proofs are used as building blocks for many of the cryptographic primitives in this library.
uint	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.
util	Miscellaneous functions used throughout the library.

Structs

Accumulator	A cryptographic accumulator. Wraps a single unknown-order group element and phantom data representing the type `T` being hashed-to-prime and accumulated.
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.