However while it wasn't too hard to get basic toy examples to compile and run, there are a lot of nasty details here. You need to include the signature verification in the ZK proof, here they used ECDSA not Schnorr (and they converted it into a format suitable for the R1CS), not a huge deal, but then there's the part that's quite demanding: how to include a merkle tree inclusion proof inside the circuit; they are using the Poseidon "ZK-friendly" hash function for this ( https://www.poseidon-hash.info/ ), so to do this kind of work properly you kind of have to really understand the intricacies of that hash function.
Whichever way you look at it, it's a very promising area, things have come a long way in a few years. In particular the circom library(**) makes it pretty easy to build at least "basic" snarks, using groth16 (spartan does *not* use that construction, though, groth16 is super efficient but has a per-circuit trusted setup ceremony - undesirable, for some things!).
** docs.circom.io
Also, AFAICT (haven't really got into this properly), this project uses SpartanNIZK specifically, and that does *not* have sublinear verification time (it has a cost component linear in the size of the R1CS, specifically), which is probably the single most crucial property if you want, as I do, to be able to publish "I own one of a huge number of keys" proofs. Groth16 has constant (very fast) verification time irrespective of circuit complexity, which means for some applications, the trusted setup is probably the better choice.
What is the overarching goal here?
TLDR: proving ownership of one out of 1 million utxos, means 1 million keys, with a proof size that is reasonably compact, and a verification time that is reasonably quick (hence we talk about "sublinear", i.e. less than O(n)).
Not TLDR: you can see work I did previously to find schemes that are at least close to this here: https://reyify.com/blog/little-riddle , and the referenced earlier blog posts. These aren't, probably, fast enough in verification. Then there's also the idea of using Curve Trees which I discussed in a post here on nostr in some detail, recently. This is another approach (at least, I *think* it is), but now I think about it, we *might* still get stuck with linear verif time here too.
And your question about motivation: I think anti-sybil is going to prove to be a crucial property for these anonymous systems using bitcoin (most importantly, Lightning: see, jamming attacks). I discussed this a fair bit in this talk: https://pretalx.com/adopting-bitcoin-2022/talk/RVFS9C/
As I keep studying this, I'm finding a lot of interesting things. In outline, you can prove that you own a public key by providing a signature on an agreed message, and that the key is one of a set of ~ 100 million (merkle tree depth 26 say, though it matters little if you vary between 20-30); you hash the pubkey using Poseidon, which is particularly friendly to zkps because it only requires a few hundred constraints in the circuit. Then for the signature, you use ECDSA - a fascinating detail here (I'm not sure if anyone considered this), is that because BIP340Schnorr uses key-prefixing you can't make the message hash ("e") be a *public* input to the circuit (that SHA2 hash would have to be calculated in zero knowledge, which is a lot more expensive than Poseidon), whereas with ECDSA, by a trivial algebraic manipulation, you can convert the verification to a form like a*B + C = D, where the nonce-point R and the msghash are public inputs. It's still a significant expense, because you're doing (only 1) curve addition and multiplication, but with the use of secq as the base field, and with some fairly basic optimizations, it ends up being reasonable. For this case, I am getting about a 16kB size proof and about 1.5 seconds of verification time *using javascript/wasm, not rust or C*, and, on a laptop. Considering that is for a proof of, easily, the anon set of the *entire utxo set of bitcoin*, then at least in theory, this is a very impressive achievement.
Doh, ignore the reference to groth16, i forgot that that requires pairings.
