waxwing on Nostr: Reached an initial waypoint with the aut-ct (anonymous usage tokens from curve trees) ...
Reached an initial waypoint with the aut-ct (anonymous usage tokens from curve trees) project. It should now be easy to install and test; see the README:
https://github.com/AdamISZ/aut-ct
70-100ms verification time for 48K signet keys on my laptop. Generates a key image, a DLEQ proof and a Curve Tree proof. It's organized as a small RPC server (the API currently consists of only one call - "verify") and a client. Make the proof with the autct binary first then make the rpc verify call - for me it takes between 70 and 100ms for that larger keyset, or for smaller test ones. There'll be very little variation in timing in practice; I will try up to maybe 200K later.
Also contacted the paper authors to check a couple of minor points, which were fine. I'm quite optimistic about this, in that I now am fairly convinced this is a practical way to do what I previously called "RIDDLE" (see e.g. https://reyify.com/blog/little-riddle ) with much larger keysets - even the whole taproot utxo set, in the extreme. In that earlier construction, while the proofs were compact (1kB), the verification scaled linearly with the keyset size so it created a realistic limit. With Curve Trees we still have 2-3kB which is absolutely fine, but verification time is in the tens of milliseconds, and barely changes much when moving to 100k-1M range (which is completely impractical with the previous GK14/Triptych-based construction in that blog post).
If anyone could test the install-then-worked-example from the README and report back, I'd appreciate it.
https://github.com/AdamISZ/aut-ct
70-100ms verification time for 48K signet keys on my laptop. Generates a key image, a DLEQ proof and a Curve Tree proof. It's organized as a small RPC server (the API currently consists of only one call - "verify") and a client. Make the proof with the autct binary first then make the rpc verify call - for me it takes between 70 and 100ms for that larger keyset, or for smaller test ones. There'll be very little variation in timing in practice; I will try up to maybe 200K later.
Also contacted the paper authors to check a couple of minor points, which were fine. I'm quite optimistic about this, in that I now am fairly convinced this is a practical way to do what I previously called "RIDDLE" (see e.g. https://reyify.com/blog/little-riddle ) with much larger keysets - even the whole taproot utxo set, in the extreme. In that earlier construction, while the proofs were compact (1kB), the verification scaled linearly with the keyset size so it created a realistic limit. With Curve Trees we still have 2-3kB which is absolutely fine, but verification time is in the tens of milliseconds, and barely changes much when moving to 100k-1M range (which is completely impractical with the previous GK14/Triptych-based construction in that blog post).
If anyone could test the install-then-worked-example from the README and report back, I'd appreciate it.