Bitcoin Forum
March 28, 2024, 10:20:33 PM *
News: Latest Bitcoin Core release: 26.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Dual SNARK: How to make ZKP with trusted initilization trustless in some cases.  (Read 2876 times)
gmaxwell (OP)
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
March 15, 2014, 12:01:02 PM
 #1

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.
"I'm sure that in 20 years there will either be very large transaction volume or no volume." -- Satoshi
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1711664433
Hero Member
*
Offline Offline

Posts: 1711664433

View Profile Personal Message (Offline)

Ignore
1711664433
Reply with quote  #2

1711664433
Report to moderator
1711664433
Hero Member
*
Offline Offline

Posts: 1711664433

View Profile Personal Message (Offline)

Ignore
1711664433
Reply with quote  #2

1711664433
Report to moderator
1711664433
Hero Member
*
Offline Offline

Posts: 1711664433

View Profile Personal Message (Offline)

Ignore
1711664433
Reply with quote  #2

1711664433
Report to moderator
iddo
Sr. Member
****
Offline Offline

Activity: 360
Merit: 251


View Profile
March 16, 2014, 08:56:08 AM
 #2

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.

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?

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.

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...
gmaxwell (OP)
Moderator
Legendary
*
expert
Offline Offline

Activity: 4158
Merit: 8343



View Profile WWW
March 16, 2014, 08:25:45 PM
 #3

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.

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

Quote
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.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!