Zero-Knowledge Contingent Payment

https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/

by mazsa • 10 years ago

163 63 10 years ago

bramblerose2• 10 years ago

It's unfortunate that most bitcoin-related posts require the reader to have a lot of in-depth knowledge about the details of how bitcoin transactions work. As somewhat-interested-person, I can /just/ figure out what the gist of the story is ('Alice can show she knows the answer and can then transfer the answer in an atomic payment'), but it's completely unclear to me how either part works. The "The buyer makes his payment to the following ScriptPubkey" section is maybe the worst offender in that respect -- apparently that script is supposed to be obvious, but it's not clear to me what it does /at all/.

ryan-c3• 10 years ago

Here's my attempt at explanatory comments - the ScriptPubkey is a program (written in Bitcoin Script) which is attached to an output of a Bitcoin transaction - parameters must be provided that make it return "true".

    # Compute the SHA256 of the value on the top of the stack (spender input),
    # then add the result to the top of the stack
    OP_SHA256
    # Check whether this value is equal to Y, the hash of the key under which
    # the solution was encrypted. 
    <Y> OP_EQUAL
    # If the correct key was provided, add the seller's public key to the stack
    OP_IF
      <Seller Pubkey>
    # Otherwise, if it has been 100 blocks or more, add the buyer's public key
    # to the stack so they may refund themselves if the seller does not complete
    # the protocol 
    OP_ELSE
      <block_height+100> OP_CHECKLOCKTIMEVERIFY OP_DROP
      <Buyer Pubkey>
    OP_ENDIF
    # Verify the signature against the public key on the top of the stack
    OP_CHECKSIG

bramblerose2• 10 years ago

Thank you, that clarifies a lot.

jnbiche• 10 years ago

Good explanation. By way of background, I'll add that Bitcoin Script runs on a stack machine, similar to Forth (except Script is non-Turing complete).

ptrincr• 10 years ago

Yep, very true. However the Internet itsself was a mystery to most people during its early life. The technology was refined, made more user friendly and opened up to the masses.

The same happened with Bitcoin (as a payment method) and I'm pretty sure someone will find way to make this simple enough for the layman to use.

ssharp• 10 years ago

This drum keeps getting pounded, but a cogent answer to the question "why would I use Bitcoin when I can use existing payment methods?" has yet to be given.

The benefits of the internet were pretty clear and obvious. The benefits of Bitcoin are neither clear nor obvious.

Uptrenda• 10 years ago

Believe me - it's not just you. Bitcoin has always been like this. You'll have one smart guy who says something fairly interesting but somehow they never go into enough detail for anyone else to be able to reproduce their results. Because of this - if you want to be able to do anything interesting working by yourself is still the best way to do it.

Coincidentally: I was actually working on using ZKPs before this was posted and I had a hell of time even getting the library installed (Snarkfront.) In the end I resorted to emailing one of the devs who managed to get it to work since I'm probably one of less than 50 people world-wide who have ever used Snarklib before - (a group that would probably include Greg Maxwell too.) So yes - the bleeding edge stuff unfortunately does require a lot of time to master but sometime in the future I hope to post some proper documentation and put a virtual machine online so normal devs can play with this stuff without having to waste hours.

ewillbefull5• 10 years ago

The simple explanation -- which I unfortunately left out of my slides but did elaborate on during my talk -- is that Bitcoin has a way for you to send money to someone contingent on them producing the preimage of a SHA256 hash. The remainder of the script allows you to get your money back if the person doesn't have or doesn't provide the preimage within a certain amount of time.

If you use a zero-knowledge proof to enforce that the preimage of the hash is a key which unlocks some data you want, this becomes a powerful tool for building exotic protocols or performing risky transactions. It also doesn't cost much on the Bitcoin side of things.

agnuacc• 10 years ago

What does this mean for z.cash?

nickodell2• 10 years ago

The technology has no relation to zcash, other than that both are cryptocurrencies.

CiPHPerCoder• 10 years ago

Also, which might be confusing for users: Both zcash and ZKCP get to check the "zero-knowledge" box, although zcash's innovation is called a zk-SNARK and is otherwise unrelated to this protocol.

kushti2• 10 years ago

Electric Cash Company is getting a good promotion with this demo, at least

ryan-c3• 10 years ago

This is really cool. I got to watch Sean Bowe's side of the transaction at FC'16 in person. I think I saw somewhere that a faucet that pays for sudoku solutions is being worked on.

From reading up on this a little (and confirming with Sean), it seems that before the payment is committed the solution must already be available, so this may not be a good protocol for expensive to produce, bespoke solutions that are only of interest to a single buyer. If, for example, I wanted to buy the factorization of a 768 bit RSA modulus, someone working on a solution for me would have the risk of me not paying - I still would not get the solution, but they'd be out the computation costs.

Jtsummers• 10 years ago

if multiple people can submit solutions, first one getting paid, then you could do this mining style.

Multiple people submit computational power to the problem. First one to it gets the reward, if no one does it goes back to you. Time limited and searchers only have to submit as much CPU time as they're willing to.

However, I don't know this system well enough to know if that's feasible.

jzwinck• 10 years ago

This roughly described distributed.net back around 1997.

dkopi• 10 years ago

"ZKCP is a transaction protocol that allows a buyer to purchase information from a seller using Bitcoin in a manner which is private, scalable, secure, and which doesn’t require trusting anyone: the expected information is transferred if and only if the payment is made. The buyer and seller do not need to trust each other or depend on arbitration by a third party."

One obvious, and sad use for this is Cryptolockers. I prove that I have the key to decrypt your files, you prove that you have the BTC to pay for it.

hyperbovine• 10 years ago

But there will be many more non-obvious, non-sad uses for it.

ycmbntrthrwaway• 10 years ago

And as usual with crypto technology, "bad guys" already have means to achieve their goals anyway. Cryptolockers already exist.

hnmcs• 10 years ago

scalable

But not scalable beyond BitCoin's ~7 transactions per second, right?

Asking because I read this last month:

http://www.nytimes.com/2016/01/17/business/dealbook/the-bitc...

nickodell2• 10 years ago

No, not scalable beyond that.

flatline• 10 years ago

~2.7 tps in practice, and shrinking as transaction sizes grow.

ikeboy• 10 years ago

These transactions work fine with the lightning network, according to the author on reddit: https://www.reddit.com/r/Bitcoin/comments/47rk85/first_succe...

So this can scale as much as lightning can. See https://en.bitcoin.it/wiki/Scalability_FAQ#Doesn.E2.80.99t_L... and https://blockstream.com/2015/09/01/lightning-network/

ryan-c3• 10 years ago

I'm not sure this is actually useful to cryptolockers. They could use it to sell the private key to a particular public key, but I don't think they can prove that

* That public key was used to encrypt the files

* Even if they can prove that, prove that the files (aside from maybe one or two samples) will decrypt to the originals.

joosters• 10 years ago

Cryptolockers already provide a very simple proof to their 'customers': they offer to decrypt one file of the victim's choice, for free.

abhv2• 10 years ago

This is a technical question for Gregory or the other authors. When the verifier (i.e. buyer) produces the public parameters for the SNARK (or any NIZK for that matter), the protocol may no longer be zero-knowledge.

The protocol is ZK because there exists a simulator which can produce an indistinguishable setup, and simulate proofs. This does not mean that if you allow any V* to produce a CRS, the simulator can still simulate.

I cannot think of an explicit attack off-hand, but wonder how you deal with this.

9mit3t2m9h9a• 10 years ago

A person who monitors transactions and immediately submits a competing transaction with ridiculously high transaction fee (50% of the payoff) may have a chance to induce miners to include his illicit transaction in the new block instead of the legitimate payment.

Maybe illicit CRS can be a problem for some kinds of checks, but I guess you could feed first Linux kernel commits in the 2016 to some randomness extractor to get something that is harder to manipulate freely.

abhv2• 10 years ago

I believe it is not possible to submit a competing transaction to spend, the identity of the seller (via seller's public key) is included in the script.

The CRS issue is that off-chain, a malicious Verifier (buyer) may learn about the witness, i.e., either enc key or solution.

ianmiers• 10 years ago

Hi (not one of the authors on this, but one of the Zerocash/ZCash authors and a co-worker of Sean's)

This isn't the case with SNARKs, they are zero-knowledge no matter what. For a generic zero-knowledge proof, what you point out is completely true. You are not guaranteed zero-knowledge if the CRS is maliciously generated.

For SNARKS, the proofs become zero-knowledge simply by the prover adding in randomness to his proof. This holds even if the verifier generates the CRS maliciously. Indeed, the original use of SNARKS was for verifiable computation where this was exactly what was done. See section 1.2,3.2, and 4.4 of [0]. In particular, note the last paragraph of 4.4 where the verifier is generating the CRS.

(The point you raise about the simulator is a complex one. Zero-knowledge is an existential statement that there can exist such a simulator, therefor all proofs even when there clearly isn't one are zero-knowledge. The verifier can create a CRS and not tell anyone the information needed to simulate, but that information still exists and we could still, in theory, construct a simulator using it. Therefor the thing is zero-knowledge in both theory and practice. This is not always the case with all proof systems.)

[0]https://eprint.iacr.org/2012/215.pdf

nullc6• 10 years ago

See Theorem 6 of the GGPR'12 paper, its on page 26. https://eprint.iacr.org/2012/215 which addresses the rerandomization of the proofs in the prover that result in them being a uniform sample of all acceptable proofs.

tommynicholas2• 10 years ago

Zcash is super interesting, and to me, a demonstration of how exciting cryptography is. Learning about Zero Knowledge Proofs and Homomorphic Encryption is something I would encourage every young aspiring founder with any interest in math to start right now.

ewillbefull5• 10 years ago

Thanks! In this case, the Zcash team did build the first zero-knowledge contingent payment, but we performed it on the Bitcoin network.

tommynicholas2• 10 years ago

The Bitcoin network remains an extremely valuable innovation sandbox. It is, perhaps, its biggest long term value if you're a Bitcoin fan but pessimist (as I am).

Rauchg• 10 years ago

A lot of (manual) work went into making this simple demo happen.

These are some interesting reflections on the present state of the tech by Gregory Maxwell:

https://www.reddit.com/r/Bitcoin/comments/47rk85/first_succe...

I suspect there's a great opportunity here for startups. The theory is sound, and tooling (UX) needs to be built around it.

ewillbefull5• 10 years ago

I think the tooling will improve significantly this year and you should see people able to build protocols with zkSNARKs soon -- without spending days figuring out how everything works.

Ahmed Kosba has been working on jSnark (https://github.com/akosba/jsnark).

I'm building something in Rust called bellman (https://github.com/ebfull/bellman) which should make it easier to construct circuits safely and build these proofs easier, but it's in its early stages.

kushti2• 10 years ago

This is huge!

To improve efficiency, Pedersen Commitment(i.e. g^Ex*h^r) or exponentiation g^Ex (so 1-2 exponentiations in a finite group) could be used instead of SHA256.

Con: new opcode is needed

Pros: efficiency, and PC / exponent could be proven itself in ZK in a very efficient way via Sigma protocols(can't imagine an useful example though).

nullc6• 10 years ago

Proving _knowledge_ or simple properties about the pre-image doesn't get you much of anything interesting.

In this protocol the prover proves something that makes the preimage valuable to the verifier. This generally puts into the land of ZKP for general computation; and in that land, facts about pedersen commitment are not more efficient to prove than SHA256.

(except with exceptional parameter selection... e.g. constructing a EC group out of the field created by the SNARK constructions' group.)

darawk3• 10 years ago

Forgive my ignorance, as I did read through everything you posted, but i'm not sure I fully understand how such a system avoids an attack of this form:

function check (bits) { sleep(bits) return false }

Where 'sleep' may be replaced by some appropriately long-running, arbitrary computation (since presumably these proof programs are not allowed to actually wait). Obviously for input data as complex as a sudoku answer the sleep would be near-infinitely long, but you could surely extract at least several bits of the answer in this way and thereby iteratively extract the whole thing, no?

Is there some mitigation for this that i'm missing?

cjg• 10 years ago

You are missing something: the seller can see the program that evaluates the solution.

darawk3• 10 years ago

Of course, but if the seller has to manually inspect the program for every transaction, is this really all that useful?

There are a myriad of ways to leak timing information from something like this, and to mask them amongst legitimate-seeming computations.

It seems like if you're having to rely on manual program inspection, then you've already lost.

ChemicalWarfare2• 10 years ago

Both the seller and the buyer paid tx fees, correct?

HappyTypist• 10 years ago

Tx fees are always paid by the buyer, but technically money is nominal and who pays it doesn't matter. Visa charging merchants 3% is exactly the same as them charging consumers 3% or splitting them 1.5%.

ChemicalWarfare2• 10 years ago

Both of the txs referenced in the writeup have tx fees so I'm just making sure I'm seeing it right :) There's a pretty real possibility of btc tx fees going up if the volume grows and block size stays the same especially once mining fees get halved so if as a seller I have to pay tx fees that is something the protocol description should mention.

Manishearth4• 10 years ago

Could someone provide a better explanation (or a link to one) of the ZKP verifiable execution thing linked to in the post? https://people.xiph.org/~greg/simple_verifyable_execution.tx...

The notation is a bit weird, and I think I'm missing things here.

Some confusions:

- Are the AND gates actual AND gates which take in two bits and output one, or programming AND operations which operate on a couple of bytes at once?

- Why is the hash of the and gate encryption keys not reversible? At max the key is only a few bytes large, which is easy to brute force. If I'm interpreting these as actual AND gates, it's a three bit key, which will neither be unique nor have a shred of security.

- "I use the resulting super-commitment to select a random permutation of the encrypted gates.": What happened here? Were they just sorted by the superhash? Was the hash used as a seed in a PRNG? Would just shuffling them any which way be okay, or does the shuffle have to be such that the person the gates are sent to can verify that the shuffling was done "correctly"? This seems like a key point which was glossed over.

- I'm not entirely sure what role the revealing of the gates plays here. I assume that because of the deterministic shuffling above, it's a nontrivial problem to do any jiggery-pokery with the nonrevealed gates without changing the shuffle order (and thus changing which gates are the ones not revealed)?

I sort of see how this works; but I'm not convinced that it's secure.

nullc6• 10 years ago

The "and gate" are encrypted and-gates: a table which maps encrypted bits to encrypted output bits. The encrypted values can be large enough to make bruteforcing the hash infeasible to view the rest of the table infeasable. (In the text "We can create an encrypted version of the gate by picking an encryption key for each wire in/out).

Revealing the gates serves the purpose of convincing you that the gates in use are actually ANDs and not (say) gates that all return true.

What happened here? Were they just sorted by the superhash? Was the hash used as a seed in a PRNG? Would just shuffling them any which way be okay, or does the shuffle have to be such that the person the gates are sent to can verify that the shuffling was done "correctly"? This seems like a key point which was glossed over.

As it says, "E.g. I use that hash to initialize a random shuffle on the gates." It needs to be a deterministic scheme set in advance with random ordering based on the collection of encrypted gates so that the prover cannot take the subset of gates that would be used in a critical part and make just those invalid. In one sense it doesn't matter how the shuffle is done so long as the prover can't use knowledge of it to cheat without being caught-- e.g. in an interactive protocol the verifier picking the shuffle works fine.

And indeed, the goal of using the hash is so that the prover can't efficiently exploit knowledge of the order to adapatively cheat. (e.g. make all his gates return true, except for the ones that are going to get revealed).

Manishearth4• 10 years ago

The "and gate" are encrypted and-gates: a table which maps encrypted bits to encrypted output bits.

But the encryption scheme has only two possible inputs; can't this be brute forced?

Perhaps an example would help me understand here.

Zero-Knowledge Contingent Payment

Related Stories