Crate vb_accumulator

Accumulators, based on bilinear map (pairings) and without them

vb_accumulator

Dynamic Positive and Universal accumulators according to the paper: Dynamic Universal Accumulator with Batch Update over Bilinear Groups

Implements

• a dynamic positive accumulator PositiveAccumulator, that supports membership proofs.
• a dynamic universal accumulator UniversalAccumulator, that supports membership and non-membership proofs.
• a zero knowledge proof of membership and non-membership in the accumulators with ProofProtocol as described in the paper. These are essentially proofs of knowledge of a weak-BB signature
• an alternate and more efficient protocol of zero knowledge proof of membership and non-membership based on a more efficient protocol for proving knowledge of a weak-BB signature. This isn’t described in the paper.
• keyed verification proofs of membership and non-membership where the verifier knows the secret key. Such accumulator don’t need pairings

Allows

• single and batch updates (additions, removals or both) to the accumulators.
• single and batch updates to the witness.

Both accumulators implement that trait Accumulator that contains the common functionality. Both MembershipWitness and NonMembershipWitness can be updated either using secret key or using public info published by accumulator manager called Omega. Most of the update logic is in the trait Witness which is implemented by both MembershipWitness and NonMembershipWitness. The implementation tries to use the same variable names as the paper and thus violate Rust’s naming conventions at places.

kb_accumulator

Dynamic Positive and Universal accumulators according to the paper: Efficient Constructions of Pairing Based Accumulators

Implements

• a dynamic positive accumulator KBPositiveAccumulator, that supports membership proofs. Based on construction 2 in the paper.
• a dynamic universal accumulator KBUniversalAccumulator, that supports membership and non-membership proofs. Based on construction 3 in the paper
• zero knowledge proofs of membership and non-membership in the accumulators. These are essentially proofs of knowledge of a BB signature and weak-BB signature.
• an alternate and more efficient protocol for membership and non-membership proofs
• keyed verification proofs of membership and non-membership where the verifier knows the secret key. Such accumulator don’t need pairings

Allows batch updates to the accumulator and the witness using the techniques from vb_accumulator

The implementation uses type-3 pairings compared to type-1 in the paper.

Modules

batch_utils

Utilities for batch updates to the accumulators and witnesses.

error

kb_positive_accumulator

A dynamic positive accumulator based on construction 2, Fig. 2 in the paper Efficient Constructions of Pairing Based Accumulators

kb_universal_accumulator

Universal dynamic accumulator defined in section 6, Fig 3 of the paper Efficient Constructions of Pairing Based Accumulators

persistence

Interfaces for persistent storage of accumulators

positive

Positive accumulator that support single as well as batched additions, removals and generating membership witness for single or multiple elements at once. Described in section 2 of the paper. Creating accumulator, adding/removing from it, creating and verifying membership witness:

prelude

proofs

Zero knowledge proof protocols for membership and non-membership witnesses from section 7 of the paper. The paper only describes the non-membership proof but the membership proof is similar with the relationships involving d omitted. See the documentation of relevant objects for more detail.

proofs_cdh

Alternate implementation of zero knowledge proof protocols for membership and non-membership witnesses. The protocol for proving membership is the protocol for proof of knowledge of weak-BB signature proposed by Camenisch et. al where the prover does not do pairings. The protocol for proving non-membership is an extension of this protocol as: Non membership witness is (C, d), accumulator value is V, non-member is y, secret key is alpha and public generators P and P_tilde satisfying the relation C*(y + alpha) + P*d = V.Both prover and verifier have access to a public generator Q such that discrete log of Q wrt P is not known.

proofs_keyed_verification

Proofs of membership and non-membership with keyed-verification, i.e. the verifier needs to know the secret key to verify the proofs. These are essentially keyed-verification proofs of knowledge of weak-BB signature. The protocols are as follows Accumulator = V, secret key = alpha, P and Q are generators of group G1 Membership protocol witness = C, member = y, C * (y + alpha) = V

setup

Keys and setup parameters. Described in section 2 of the paper

setup_keyed_verification

threshold

Accumulator update, witness generation and updated witness generation in a threshold setting, i.e. where the accumulator secret key alpha is split among many accumulator managers using Shamir secret sharing. The general idea is:

universal

Universal accumulator that support single as well as batched additions, removals and generating membership and non-membership witness for single or a multiple elements at once. Described in section 2 of the paper

universal_init_constants

Elements generated for initializing a non-membership accumulator as mentioned in section 6 of the paper For each curve, they correspond to the xs whose order is p_i^{e_i} in the factorisation p_1^{e_1} * p_2^{e_2} * .. * p_n^{e_n} of p-1 where p is the curve order Generated using the Sage file in this package

utils

witness

Protocols for updating single or a batch of membership and non-membership witnesses with and without using the secret key. Described in sections 2, 3 and 6 of the paper

Macros

initial_elements_for_bls12_381