Accumulator using Bilinear maps

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: 1. Ability to remove indices from the accumulator. 1. Efficient witness generation (independent of the size of the accumulator) using knowledge of trapdoor

Accumulator from section 3.2 of the paper

API

  1. Accumulator is defined over group G1. To initialize a new Accumulator, call Accumulator::new.
  2. 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.
  3. For generating and querying entries which are added to the accumulator, a trait AccumulatorEntries is defined. For testing, an in-memory implementation is defined.

  4. For a sample of how an accumulator is setup, look at testing function setup_accumulator_for_testing.

  5. To add an index idx in the accumulator, use method Accumulator::add_index. The method returns a new accumulator and updates the state. Suppose accum is the accumulator before adding that index, state is an AccumulatorState and entries is an AccumulatorEntries, then this is how to add in index rust // 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);

  6. 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 index idx without using the trapdoor, use method Witness::for_index which iterates over the indices in state and gets the corresponding entries from entries.
    rust let witness = Witness::for_index(idx, &state, &entries);

    To generate a witness for index idx using the trapdoor rust // `cur_accum` is the accumulator without `idx`. let witness = Witness::for_index_using_trapdoor(idx, &cur_accum, &entries, &state, &trapdoor);

  7. To check whether an index idx is present in the accumulator, use method Accumulator::has_index. rust // `witness` is a `Witness` and `z` = e(g1, g2)^{gamma^{size+1}} accum_1.has_index(idx, &witness, &entries, &z);

  8. To update the witness after some elements have been added or removed, the old witness can be updated using Witness:update. rust // `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);

  9. To remove an index idx, use Accumulator::remove_index to get a new accumulator with the index removed. rust // indices are 1-based. `accum` has the index `idx` but `accum_1` does not let accum_1 = accum.remove_index(idx, &entries, &mut state);

  10. 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. rust let (new_accum, wit) = cur_accum.add_index_and_compute_witness(idx, &entries, &mut state, &trapdoor);

See the tests for detailed examples.

TODO: