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.
waxwing /
npub1va…knuu7
2024-02-29 04:13:59
Author Public Key
npub1vadcfln4ugt2h9ruwsuwu5vu5am4xaka7pw6m7axy79aqyhp6u5q9knuu7Published at
2024-02-29 04:13:59Event JSON
{
"id": "d86035d58f8ecf9dd44170e5767f64b9c4ca4a1b34a83637585bc06f65507cd3",
"pubkey": "675b84fe75e216ab947c7438ee519ca7775376ddf05dadfba6278bd012e1d728",
"created_at": 1709180039,
"kind": 1,
"tags": [
[
"r",
"https://github.com/AdamISZ/aut-ct"
],
[
"r",
"https://reyify.com/blog/little-riddle"
]
],
"content": "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:\n\nhttps://github.com/AdamISZ/aut-ct\n\n70-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.\n\nAlso 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).\n\nIf anyone could test the install-then-worked-example from the README and report back, I'd appreciate it.",
"sig": "883e08773b18d236244c64ef2a8477e94aff2b9b517657e15ed74a75de616707f0c0cedbc04f0c59962a1b6fc33f80319ea4412144ea77c14da1d831d2641b5e"
}