Dear all,

I have been working on some constructions for cryptographic accumulators that optimise for quick insertion.

As a brief background, an accumulator is a data structure that maintains compact commitments to a potentially very large (and dynamic) set, while keeping proofs of membership short. Unsurprisingly, they are getting more popular, and one notable application in Bitcoin is to create light-weight full nodes that do not need to store the UTXO set (Utreexo accumulator[1]).

In this work, I focus on additive accumulators that supports adding new elements, but not removing them. My motivation is to support extending Script with access to an arbitrarily large portion of the blockchain history and state (e.g., past blocks, txids, or any more complex state obtained from them - with all due care). The additional storage and computation cost for nodes is small, and the cost (in additional bytesize) for any transaction that wishes to access state committed in the accumulator should be just slightly bigger than typical Merkle proofs.

I have focused on:
- An accumulator with insertion time O(1) and proof size O(log^2 n)
- A construction with insertion time O(log log n) and proof size O(log n log log n)