Is it possible to reduce the tail's file of accumulators for large data set

Question

I am working on a proof of concept around cryptographic accumulators. The following is my understanding so far

1. delta : the current size of the tails file in the accumulator.

2. witness : the current value of the accumulator when the entry of your number was made.

3. index : the actual index that is added to the accumulator.

4. tails file :list of all witnesses.

When an index is added to the accumulator, the witness and delta are shared with the prover.

When the prover wants to prove to a verifier that the index is part of the accumulator he updates the witness using the delta(and tails file) and shares the updated witness with the verifier which allows for verification.

My question is: Wouldn't the tails file become very large as the number of entries increase slowing down the process of proof and verification?

Is there a solution to this?

Answer 1

I've read a little about this area years ago. The naive example of an accumulator is simply multiplying primes together into the accumulator, which can then be checked for their presence simply by division. This obviously results in persistent growth of the accumulator.

I looked for an accumulator that addressed the endless growth issue, but I was never able to find one. However, I was more concerned about the increasing storage capacity required. It seems unlikely to me that one could exist, for they store information after all. It would be magical if it could continuously store information without growing in size.

However, as far as time complexity is concerned, it may be a different matter. The name of what you want would be something like "constant time cryptographic accumulator." For example, a bloom filter allows -- at increasing risk of false positives, but never with false negatives -- for O(1) membership querying on a set of recorded values, which means that time to (probabilistically) determine membership or (with certainty) a lack thereof doesn't grow with the number of elements added.

I would probably look for an accumulator built on a bloom filter if I were worried about time to query and could accept a small risk of false positives.