Topic: Dual SNARK: How to make ZKP with trusted initilization trustless in some cases. (Read 2878 times)

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.

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.

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?
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?


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.


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

Some of the most efficient constructions available now for proving arbitrary programs in zero-knowledge are only secure in the CRS model— in English: They require a trusted initialization step where someone has to generate some magical numbers and if they cheat (e.g. by keeping the initial randomness) they can produce false proofs.

Systems with these properties are found in some of the papers at http://www.scipr-lab.org/ and in http://research.microsoft.com/apps/pubs/default.aspx?id=180286, both of which are currently using systems based on the GGPR'12 cryptosystem. They have really awesome performance, though— fast enough to actually be feasible to use on the prover, and almost as verification in a couple milliseconds with a few hundred bytes for the proof regardless of the size of the program being proven or how long it takes to run. But the requirement of a trusted initialization is unacceptable for some applications.  Ultimately we'll want systems which do not depend on the trusted initialization but they're less far along in development and may never be quite as efficient.

Some things we'd like to use these proofs systems for is a more powerful and efficient replacement for Bitcoin script. Instead of every node verifying your fancy script, instead the party creating the transaction runs the script themselves and provides the network with an efficient proof that you ran it faithfully and that it accepted. This avoids network load as being a disincentive to using fancy scripts and also has privacy advantages.

For example, say I want to pay you conditional on you publishing a solution to a— say— Sudoku puzzle. A script running under an efficient proof of knowledge system could verify an encrypted solution, and because it's zero-knowledge miners couldn't come along and replace the outputs like in a plain hash-locked transaction. You could use a CRS snark here where the payer computes the trusted initialization and then the payee cannot cheat— but the fact that the payer initialized it means the payer could double-spend race the redemption and get both the solution and their coin back.

There are a couple of ways of solving this, but I wanted to mention another one which is especially general:

In a two-party trade, just have both parties compute their own trusted initiations, then require the script provide proofs under each of them. Then so long as one side isn't cheating the transaction will behave faithfully.

This can be further optimized by instead requiring Person_A_snark&&Person_B_ECDSA_sig || Person_B_snark&&Person_A_ECDSA_sig... Cross signing using ECDSA is more efficient since the snark proofs are larger (and much slower to compute) than ECDSA signature, and this equally achieves the goal of not allowing either party to take advantage of a trapdoor.  (in particular, if you use hash compression to avoid ever even bothering to publish the verifier public keys for the untaken branches).

The same approach can be extended to more than two parties though the efficiency becomes less impressive (e.g. the prover must run the proof N-1 times to handle any party possibly conspiring with them, or N/2 if you only want a honest majority security) and sadly, it doesn't really work for broadcast payment sorts of application.