waxwing on Nostr: Now applied this to aut-ct in a branch: https://github.com/AdamISZ/aut-ct/tree/delta ...
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).
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).
quoting nevent1q…rlevBeen 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...