Accumulators, scalability of UTXO blockchains, and data availability

Turns out I was wrong regarding batching for the RSA accumulator. The reason is that when batch adding elements b_1, ..., b_m, the bit size of the update exponent b_1 * ... * b_m grows linearly with m. (The exponent can be reduced modulo the trapdoor ϕ(N) — Euler’s totient — but that’s of no use to us.) Using an RSA accumulator may still be significantly more appropriate than a Merkle accumulator, especially in the stateless client paradigm, but without batching for witness updates I cannot see how to achieve sub-linearity of bandwidth and computation.

On this note, this paper places an (obvious) lower bound on the bit size of batch deletions. The data needed to communicate m deletions within a set of n elements to update all witnesses is of size at least \log{n \choose m} bits, and this data needs to be publicly available. The worst case occurs when m = n/2, in which case O\big(\log{n \choose n/2}\big) = O(n).

The dream of finding the scalability holy grail is not lost but we know that the data that needs to be made available by the transaction sender for batch deletions of all witnesses in the worst case is at least O(n). This means we need to solve data availability, even in the simple UTXO model, for bandwidth scalability.

2 Likes