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

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.

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

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

Thank you, that clarifies a lot.

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.

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.

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.

This seems very hindsight driven to me. I didn't realize how powerful the internet could be for news until Di died and I heard about it online something like a half hour before my parents confirmed it on TV. My mother didn't trust the internet for film information until imdb had existed for many years, still relying on yearly Leonard Maltin books all the time.

Obviousness doesn't tend to come until something compels it. But in the meantime, people who recognize it before others do are working to profit off that difference.

> "why would I use Bitcoin when I can use existing payment methods?"

Bitcoin can be used for other reasons beyond payment system transactions; for example, a bunch of coins are stored in cold wallets, as a physical store of value which cannot be confiscated. Market fluctuations still happen but that's unrelated to physical coin storage.

I've never believed this line of logic at all. You really think in a serious shit-hits-the-fan scenario (be it natural disaster, government takeover, whatever) you are going to have reliable internet connectivity?

During relatively low intensity conflicts mobile networks usually work, e.g. in Syria or Ukraine. I think it's the most common scenario in the modern time for shit-hits-the-fan.

http://www.al-monitor.com/pulse/zh/originals/2015/04/aleppo-...

http://dlca.logcluster.org/display/public/DLCA/3.4+Ukraine+T...

Yeah, I expect sneakernet to work pretty well. A few weeks is way better than nothing. Also, you don't need to use an active internet connection to make reliable zero-confirmation transactions (see lightning network, although it's true that monitoring for confirmations requires internet data- so you have to set the timeouts to be way way into the future, which is reasonable and not unexpected).

How on earth does that work? Forget double spends, here come the quadruple and quintuple spends!

Zero-conf is fundamentally broken.

> Zero-conf is fundamentally broken.

Yep. Double-spending zero-conf transactions can work as long as you are using a payment channel (where the other side is receiving each transaction). That's how the "payment channel" concepts work.

If the s hits the fan, the only currency is guns and ammo.

No, it's just that there probably aren't any use-cases you would or should care about. Some fans seem hell-bent on showing that everything should use btc and that's as silly as thinking Visa or US $20 bills are the only solution we need.

But for people who want non-refundable payments, or scriptable m-of-n payment rules, etc, it's almost the only game in town.

One benefit is not having all of your online purchases tracked by your credit card company, which can produce further benefit for you down the road when insurance companies and whoever else is unable to purchase meaningful data about you to exploit you.

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.

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.

This roughly described distributed.net back around 1997.

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

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.

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

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/

Additionally, lightning actually uses the HTLC (Hashed Timelock Contract) transaction style that is used by ZKCPs. I believe it is used to extend lightning channels to multiple hops.

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

No, not scalable beyond that.

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

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

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

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.

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

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

Here are commitments to an encrypted and-gate:

a333e6e99e94fad05473f31ea377060a d967b456aa43ede06840994d5ce8547c 8ad297f72e49a1a6a48d343ec40661ae 88d626c9c58efd6d144f585e1fa6f436

Lets assume that the rest of the circuit gives us encrypted bits, 0 and 0 for the two inputs.

So I reveal this to you: echo -n "0,0,1,bcxbxewrewtererwre" | md5sum - 8ad297f72e49a1a6a48d343ec40661ae

Which is the third entry in the table, and we see the correct encrypted output for this gate is 1 (assuming my table was actually an encrypted and-gate table).

You still have idea if in1/in2/out are are zero or one. I could tell you that in1's encryption key was 1 (so now you know that in1 was one), and you still don't know if In2/out are zero or one.

Making any more more sense?

Sort of, but not exactly:

> So I reveal this to you: echo -n "0,0,1,bcxbxewrewtererwre" | md5sum - 8ad297f72e49a1a6a48d343ec40661ae

what is 1 in 0,0,1? the encrypted output?

Since this salted hash must be verifiable, I must know the bcx... string, and I can brute force all 8 possible pairs of numbers to get the gate. Isn't this a problem?

> and we see the correct encrypted output for this gate is 0

Where did the zero come from?

> what is 1 in 0,0,1? the encrypted output?

Yes, the encrypted output.

> Since this salted hash must be verifiable, I must know the bcx... string, and I can brute force all 8 possible pairs of numbers to get the gate. Isn't this a problem?

I tell you it when I give you the table entry. You have the commitments, go ahead and tell me the rest of the gate if you think you can brute force it. (You can't-- the nonces are per table entry).

> Where did the zero come from?

From the third field in the table entry.

Edit: HN won't let me respond to you, but the fact that it's the Nth entry is irrelevant; I called out the number so you'd see if was one of the values that were committed to. Sorry for adding confusion.

> the nonces are per table entry

Ah, I see.

> The output.

But you just said that the output was zero?

Perhaps I'm missing something here, you got the output as 1 from "0,0,1", and you got the output as 0 from "it being the third entry in the table"

(additionally, how does it being the third entry tell you anything? This isn't an AND gate, this is an encrypted-and-shuffled AND gate, so you might have three outputs that are 1 instead of three 0 outputs, and they might be shuffled anyhow)

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

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

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.

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

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

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.

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.

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.

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

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.

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.

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.

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?

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

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.

The amount of execution time is a simple public parameter of the system.

These schemes require reducing the verification program to a circuit in advance, so its execution time is already fixed by virtue of that translation.

(In practice the existing implementation is not using constant time cryptography; and so it could have timing/cache/EMI side-channels; but this is "just engineering")

Ah, of course, just fix the run time. I should have realized that. Thanks.

Nice work!

What does this mean for z.cash?

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

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.

In this particular ZKCP case we use zk-SNARKs because they're fast and they exist, but theoretically we do not need their "non-interactivity" properties.

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

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

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

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.