I have good news. I think the batched accumulator impossibility result referenced above can be worked around in our context of batched transactions. In short, we can setup batched transactions so that the \log{n \choose m} bits can be derived from communication that occurs during the construction of the batched transactions, bypassing data availability concerns raised by Camacho’s proof.
Camacho’s proof distinguishes the “manager” and the “user”. Instead I distinguish three entities and use blockchain terminology:
- The “senders”: users making accumulator deletions as part of a given batched transaction.
- The “hodlers”: users not making accumulator deletions as part of a given batched transaction. (So Camacho’s “user” is the union of senders and hodlers.)
- The “batcher”: the entity that prepares the batched transaction and the witness update data. This is Camacho’s “manager”. It can be a concrete entity (e.g. a third party helper) or an abstract entity (e.g. the senders performing a multi-party computation among themselves).
The key idea is to build the batched transaction so that the senders know which of their UTXOs are being spent. (This is something we’d probably want anyway, for sanity.) To guarantee that, the SNARK/STARK in my original post can be extended to prove that the spenders know they are spenders. If the batcher is a third party, this can be done by proving ownership of digital signatures from the senders giving their blessing for a given “template” batched transaction. Similarly if batching is done with an MPC, then the MPC needs to produce such a proof somehow.
Now let’s go back to Camacho’s proof. Given a batched transaction (which is very sublinear in size) it is now possible for the senders and hodlers to reconstruct the set of deletions, even before the batched transaction is confirmed onchain. Indeed, by construction senders know that their UTXOs were spent in the batched transaction, and this information was communicated offchain. And hodlers know that their UTXOs were not spent, because they know they didn’t participate in building the batched transaction in the first place.
Another way to think of this is that the witness update data can be split into two parts. One part is private and offchain, for the spenders, without public data availability requirements. The other part requires public data availability, for the hodlers. Camacho’s proof applies to both parts in aggregate, and so breaks down for us purposes.
It seems hope is restored that a fancy accumulator scheme may yield sublinear data availability after all. 