I'm looking for a data structure similar to a dynamic accumulator that has the following properties:

  • Small size: ideally under 100 bytes for the accumulator, and also under 100 bytes for witnesses
  • Constant-time updates (add, remove) that can be performed publicly
  • Constant witnesses - meaning, a witness for a value in the accumulator does not need to be recomputed when the accumulator is updated

Is there such a data structure out there?

One potential simplification: all accumulated values are 3-tuples $(P,d,S)$, where $P$ is a public key, $d$ is some arbitrary data, and $S$ is a BLS signature of $P||d$ which can be verified against $P$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.