(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...