# Crate vb_accumulator

source ·## Expand description

## §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§

- Utilities for batch updates to the accumulators and witnesses.
- A dynamic positive accumulator based on construction 2, Fig. 2 in the paper Efficient Constructions of Pairing Based Accumulators
- Universal dynamic accumulator defined in section 6, Fig 3 of the paper Efficient Constructions of Pairing Based Accumulators
- Interfaces for persistent storage of accumulators
- 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:
- 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. - 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 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`

- Keys and setup parameters. Described in section 2 of the paper
- 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 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
- Elements generated for initializing a non-membership accumulator as mentioned in section 6 of the paper For each curve, they correspond to the
`x`

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