Subnostr

Update: I can prove ownership of one of the taproot txos from block 85000 to block 155000 on signet - of which there are approx 48000 - with a 16kB proof, and it can be verified in about 1.5s on my laptop (have reason to believe this could go below 0.5s). That's cool, but what's really cool is if I go from 48000 to 1M+, the verification time barely changes at all - perhaps 0.1s longer, something like that.

Also, because we are including the ECDSA signature in the circuit, we can easily add other (simple) conditions by just writing more constraints. (Why ECDSA if taproot? because bip340 is pubkey-prefixed, so you would need SHA2 in the circuit, which is probably impractical. If you just want to prove ownership, ECDSA works fine and does not have this requirement, as long as you don't accept random message hashes - that is not sound.).

Reply to this note

Please Login to reply.

Discussion

waxwing 2y ago

(see my earlier 11 Jan post on spartan-ecdsa if you are both interested and confused by that). I might write up a gist with some advice on how to work with that in case anyone else wants to run with this stuff).

A difficulty is that you really need to build big (full, not sparse) merkle trees efficiently. If/when you do, the proving time is not too bad - 8 seconds in this test of 48K keys. The number of constraints in the circuit varies ~ logarithmically with the size of the keyset (because the merkle proof does), and so the proving time should do roughly the same (the prover is O(n) in the size of the statement). In my testing I don't actually see a difference, i.e. i still get 8 seconds up to 100k keys and above, I think this is a detail of how spartan/sparc works but at least it's safe to say, it won't be *worse* than logarithmic.

It remains to be seen whether linkability can be added here (i think, yes: include a DLEQ in the circuit, as in my earlier post, since they use secq, you can define another generator H, then take the poseidon hash of the new P2 as a token a la podle). Probably not a huge number of extra constraints, but the hashing is not clear...

Erik 2y ago

You gave up on the curve trees path?

Erik 2y ago

I kinda wish Utreexo uses an algebraic hash function, but at the same time it's less efficient outside zk world, and people would probably use more outside zk proofs, so it's a tricky tradeoff

waxwing 2y ago

Oh interesting thought, I see .. i haven't spent any time looking into utreexo but I wouldn't be surprised if you're on to something there.

Erik 2y ago

Yeah. The gents from zero sync are doing Utreexo with algebraic hash function, and looks like you can verify Merkle proofs inside a stark proving system.

My though was to make the proof and outpoint private inputs in the program, so it's privacy preserving.

waxwing 2y ago

Good question, not really; last year I got a bit stuck when i realised there was no implementation of secq, but now there is. I think curve trees *is* going to be concretely more efficient for this specific use case, but i was really impressed to see you can use a generic ZKP system to do the sane thing, without any trusted setup. It could have broader implications, maybe.