Based on the paper An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials. Modified to work with type-3 pairings. Adds 2 features not mentioned in the paper:
- Ability to remove indices from the accumulator.
- Efficient witness generation (independent of the size of the accumulator) using knowledge of trapdoor
Accumulator from section 3.2 of the paper
-
Accumulator is defined over group G1. To initialize a new Accumulator, call
Accumulator::new
. -
To track which indices are present in the accumulator so that they are not accidentally added again or removed when they were not present and to update witness, a trait
AccumulatorState
is defined. For testing, an in-memory implementation is present. -
For generating and querying entries which are added to the accumulator, a trait
AccumulatorEntries
is defined. For testing, an in-memory implementation is defined. -
For a sample of how an accumulator is setup, look at testing function
setup_accumulator_for_testing
. -
To add an index
idx
in the accumulator, use methodAccumulator::add_index
. The method returns a new accumulator and updates thestate
. Supposeaccum
is the accumulator before adding that index,state
is anAccumulatorState
andentries
is anAccumulatorEntries
, then this is how to add in index// indices are 1-based. `accum` does not have the index `idx` but `accum_1` does let accum_1 = accum.add_index(idx, &entries, &mut state);
-
To check presence of a value in an accumulator, a
Witness
is needed. To generate a witness, there are 2 methods, the slower one does not require a trapdoor and has complexity proportional to the size of the accumulator but the faster one using the trapdoor has constant asymptotic complexity.
To generate a witness for indexidx
without using the trapdoor, use methodWitness::for_index
which iterates over the indices instate
and gets the corresponding entries fromentries
.let witness = Witness::for_index(idx, &state, &entries);
To generate a witness for index
idx
using the trapdoor// `cur_accum` is the accumulator without `idx`. let witness = Witness::for_index_using_trapdoor(idx, &cur_accum, &entries, &state, &trapdoor);
-
To check whether an index
idx
is present in the accumulator, use methodAccumulator::has_index
.// `witness` is a `Witness` and `z` = e(g1, g2)^{gamma^{size+1}} accum_1.has_index(idx, &witness, &entries, &z);
-
To update the witness after some elements have been added or removed, the old witness can be updated using
Witness:update
.// `witness_old` is the old witness which is being updated, `added` and `removed` are the `HashSet`s of added and removed indices. let witness_updated = witness_old.update(added, removed, &entries);
-
To remove an index
idx
, useAccumulator::remove_index
to get a new accumulator with the index removed.// indices are 1-based. `accum` has the index `idx` but `accum_1` does not let accum_1 = accum.remove_index(idx, &entries, &mut state);
-
If the entry updating the accumulator has access to trapdoor, there is a convenience method to add an index and efficiently compute the witness as well.
let (new_accum, wit) = cur_accum.add_index_and_compute_witness(idx, &entries, &mut state, &trapdoor);
See the tests for detailed examples.
- Signature to prove knowledge of accumulated value.
- Check if for signatures, BBS+ can be avoided and PS can be used instead.
- Check if tradeoffs possible by switching groups G1 and G2.
- Convert asserts to errors