waxwing on Nostr: Now applied this to aut-ct in a branch: Proving is now down to 1-2 seconds even for ...
Now applied this to aut-ct in a branch:
https://github.com/AdamISZ/aut-ct/tree/deltaProving 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).
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...
Published at
2024-10-24 16:37:28Event JSON
{
"id": "fc24a805a15291c48f70c70a2a405f618e648cd781bed6f895bc507f8d5b8eaa",
"pubkey": "675b84fe75e216ab947c7438ee519ca7775376ddf05dadfba6278bd012e1d728",
"created_at": 1729787848,
"kind": 1,
"tags": [
[
"e",
"0894afa9cba5e7c20c4a307926b01b6ce7c4854d573b8871652a5c2259b85d5c",
"",
"mention"
],
[
"p",
"675b84fe75e216ab947c7438ee519ca7775376ddf05dadfba6278bd012e1d728",
"",
"mention"
],
[
"r",
"https://github.com/AdamISZ/aut-ct/tree/delta"
]
],
"content": "Now applied this to aut-ct in a branch:\n\nhttps://github.com/AdamISZ/aut-ct/tree/delta\n\nProving 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).\n\nSo currently it's:\n1-3 minutes to start up a server (which can be left running as long as you use the same curve tree)\n1-2 seconds to do a single curve tree inclusion proof\n50ms to verify a proof.\n\nThis 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).\n\nnostr:nevent1qqsq39904896te7zp39rq7fxkqdkee7ys4x4wwugw9jj5hpztxu96hqpz4mhxue69uhhyetvv9ujuerpd46hxtnfduhsygr8twz0ua0zz64eglr58rh9r898wafhdh0stkklhf3830gp9cwh9qpsgqqqqqqs8xrlev",
"sig": "472787aed58189057e4168e2795977c1288bfa9b1ecb83055e01c127af87d018b29344f0f57a9fd8e901abfde14baa905640be436277e0754539939b94d29626"
}
