Been expecting this, it arrived today:
https://eprint.iacr.org/2024/1647
Curve Trees without permissible points, which i am expecting will significantly improve performance (and have better security). Also some batxhinh amortization type improvements.
Now renamed 'Curve Forests' :) still reading...
umm batching 😄
2x speedups for proving, 3x speedups for verification and 60%
reduction in proof size is great. I don't understand how does it improve security.
The end of section 3 explains; the math there has a small error but it's easily fixed and doesn't affect the main point. Not only is it easier to reduce the forgery to a discrete log break using their new algo, but more importantly, there's no way to create things like DOS by deliberately crafting entries in the leaves (the set of keys) that will take an unreasonable amount of time to pre-process, as was technically possible in the old system (not an issue for most use cases, but for their v-cash use case, it would be). More generally, they're claiming security in scenarios where the accumulator is constructed maliciously, though that doesn't apply to the kinds of use cases we care about.
I don't think the proving and verifying speedups are necessarily significant, especially if they only apply to batching. I will check in a bit more detail though. Basically this is important from my pov because it can make the pre-processing step faster and also make the code simpler. The preprocessing of say 0.5M keys is very nontrivial!
Now applied this to aut-ct in a branch:
https://github.com/AdamISZ/aut-ct/tree/delta
Proving is now down to 1-2 seconds even for large trees like 500K, but this is more from me fixing inefficiencies in my code; the real advantage of their new technique for me is just that they made the algorithms much simpler, *and* we have an easy way to batch proofs now (though I haven't done it).
So currently it's:
1-3 minutes to start up a server (which can be left running as long as you use the same curve tree)
1-2 seconds to do a single curve tree inclusion proof
50ms to verify a proof.
This already usable for the kind of 'satoshi millionaire' proofs like the one in my blog post, with sets of 500K or so and even larger, but for some long running system which wants to update the curve tree with new utxos all the time, like lightning it should be possible to get rid of most of that startup cost by using an 'accumulator update' method as discussed in the paper(s).
