Why do you say "because it's zero-knowledge miners couldn't come along and replace the outputs like in a plain hash-locked transaction" ? If I understand this paragraph (and your last comment in this post) correctly, the payer has to specify a specific payee that can redeem the coins (rather than allowing anyone who knows a solution to the Sudoku puzzle to redeem the coins) ? If so, this can be done outside the snark, as we normally do in Bitcoin by requiring the ScriptSig input-script to provide a signature for a specified address/pubkey of the payee, in order to prevent miners from replacing the output. Is there any beneficial reason to enforce the payee's identity inside the snark, as you seem to imply here?
Perhaps not. I probably picked a poor example— and perhaps there isnt one— to describe a motivation for doing this. Really when the payee is designated I think you can almost always completely remove the proving process from the cryptocurrency.
Also, if I understand correctly then the protocol here isn't non-interactive, i.e. the payee sends to the payer via a private channel an encrypted solution s0 encrypted under symmetric key k0, and then the payer broadcasts the snark transaction that should reveal (in the clear) k0, so that only the payer will know the solution?
It's inherently interactive but it could potentially be asynchronous.
Let me expand the idea further so that the application is more clear. Say we make our SNARK circuit a universal circuit (like vntinyram) which takes a hash of the program as a public input (and the program itself as a private input). Lets also assume that you and I are members of a trading club which frequently trades puzzle solutions for coins amongst its members.
Every member of the trading club compiles and the tinyram circuit and produces a ECDSA private key. They publish the verifier key and public keys to all the members of the club and (via some sibyl resistant process) the club produces a hash-tree over these verifier keys and the public keys which everyone in the club agrees is correct.
Now I can form a transaction which offers a coin to someone who can produce either dual SNARK proofs (or SNARK+sig), such one snark is mine, and the other is any which is not mine in the list (by providing the verification key and proving membership in the set committed in the transaction).
(If you don't-dual snark, and replace the hashtree with a ring signature of all the club members except me (or turn the hashtree approach into a ring signature by running selection and blinding in zero knowledge), then the identity of the redeeming party can be private and unknown even to me.)
In any case in this example there was interaction, but it was all in a setup phase, and the redemption can be asynchronous and one-shot.
If my understanding above wasn't way off, then isn't it enough here to require the payee to provide his digital signature (in additional to the proof that passes the snark verification), and because the payer cannot produce a signature for the corresponding pubkey of the payee, he cannot double-spend by providing a false proof (that he can produce because he knows the snark initialization), at least until some nlocktime expired where he'd spend the output via a transaction that the payee already signed for him.
Maybe, though this has weakness when you want an 'nlocktime' rule which is more complex than nlocktime. E.g. transaction pays you if you present a receipt from your bank that the payment went through, it refunds to me if I can present proof from my bank that the transaction was reversed... then only after some very long timeout does the nlocktime come into play.
It seems to me that for non-interactive proofs (as in CoinWitness), the need to avoid a trusted initialization cannot be overcome. And on the other hand, trusted initialization isn't really an issue in interactive ZK proof scenarios? But please elaborate on any observations that I could be missing here...
I agree. Though I'm not sure if non-interactive is the quite the right criteria it fails, I think it fails publicly verifiable (yes, the CRS schemes are 'publicly verifiable', but only with trust that is not really acceptable). The interactive schemes are often easy in part because there is a designated verifier.
I don't seek to say that trusted init can replace non-trusted, it really cannot for many things. I'm just exploring the space that tools with trusted initialization can be applied.