Crate vb_accumulator

Accumulators based on bilinear map (pairings)

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

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

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