Deletion is possible in this scheme. It requires running the extended gcd algorithm (should be cheap) and two exponentiations for every participant to update their witnesses. Deleting from the accumulator means just replacing it by the witness.
I'll have to work through it then. I wasn't aware of how one could remove an n-th root without knowing the group order, which seemed to be what prior schemes required. Hm. Maybe the fact that the value being removed can be public is what makes it work.
Yes, this would be using Merkle trees, right? But if my math is correct, the witness proofs it requires are larger than the transactions. I'm not sure if ordering the tree is necessary (and you would then need to rebalance it) or do you just propose to put the elements in the order they are inserted? Instead of zeroing out the transactions one could also put the new outputs in the freed spaces to avoid the trees from growing too deep or becoming unbalanced, but still the proofs are quite large.
A hashtree constructed out of 32 byte hashes with 4 billion entries would be 32 levels deep-- so the size compares very favorably with an RSA accumulator + witnesses with equivalent security.
A significant portion of the proofs are also the first couple levels of the tree, which could be cached to avoid retransmitting them-- and such caching could be negotiated on a peer to peer basis. For example, if nodes cached the first 16 levels of the tree (2 MBs of data) a tree membership/update proof for a 2^32 tree would be 512 bytes.
No balancing is required, which is why I mentioned insertion ordered. You can incrementally build an insertion ordered tree with log(n) memory (you just remember the leading edge of the tree, and as levels fill you ripple up to the root). A search tree can be used instead, but it would require proofs for both outputs and inputs.
If you don't think 2^32 coins is enough, you can pick numbers arbitrarily large... e.g. 2^51 entries, with a 500MB cache, requires 928 byte proofs. Because of the log factor the cost is _essentially_ a constant in a physically limited world, so its just a question of if that constant is low enough.
I don't see why Merkle Trees are smaller than the RSA accumulator, but probably you assumed that deletion is not possible and you need a list of spent TXO. I think you just need the accumulator (fixed size, about 400 bytes) and as witness proof another value with all inputs deleted per block. Per transaction you also need the witness for all inputs (another 400 bytes), but this doesn't have to be stored. With Merkle-Trees you need a single hash for the accumulator, but the witness proofs of the transactions need also be included to check the updates and merging them doesn't save much. Even assuming a depth of only 24 (16 million UTXOs; we currently have more) you need 768 bytes for a single witness of a single transaction input assuming 256 bit hashes.
See my figures above. The zerocoin membership witnesses are about 40kbytes in size for 80 bit security, so I may have been overestimating the size of the accumulator updates... but even if we assume that they're 400 bytes then that puts them into the same ballpark as the TXO proofs with top of the tree caching. And, of course, verifying hundreds of thousands per second on a conventional CPU is not a big deal...
As you wrote, instead of RSA you just need a group of unknown order. But "unknown order" means that it is infeasible to compute the order. Are there any other group besides RSA with this property? AFAIK for elliptic curves it is expensive but not infeasible to compute the order.
For EC the order computation is quartic in the size of the field (via the SEA algorithm) unless the curve has special structure which allows it to be computed faster; so it's not really possible to get a reasonably efficient EC group where the order is cryptographically infeasible to compute. But class groups of imaginary quadratic orders are believed strong in this respect, but there hasn't been that much work or analysis for cryptosystems based on ideals; so I'm unsure of how useful they'd be...
https://www.cdc.informatik.tu-darmstadt.de/reports/TR/TI-03-11.nfc_survey_03.pdfAnother way to address the trusted setup with the RSA schemes is to use a UFO, but this means you end up with a field tens of KB in size just to get 80 bit security.
