On-chain accumulator with O(log log n) update cost

[bigspider]

In multi-party contracts where several parties are allowed to "optimistically" update the state of the contract, the challenge period might be problematic, as it would normally prevent other parties to further update the state until a relatively long delay.

A solution might be to chain the optimistic updates: each update records both the new state, and a hash of the previous one). A challenger should challenge the oldest invalid update. (Note: such contracts might need a way to preventing a party from spamming the optimistic update mechanism and preventing other parties to ever start a challenge)

This works in principle, but doesn't scale: the cost of challenging a state that has been optimistically updated $h$ times is equal to $h$ hashes.

Merkle trees could be used as accumulators, bringing the cost down to $O(\log h)$ to start the fraud proof, but increasing the optimistic update cost to $O(\log h)$ instead of a constant.

This draft describes an append-only accumulator that would cost a single write in a vector of size $\log h$, and which should therefore cost $O(\log \log h)$ (in practice, less than 6 hashes in total) if implemented in a MATT contract.

TODO: is it worth it? Maybe the simpler solution with Merkle trees is good enough in practice.