13 ms·

Zero-Knowledge Contingent Payment

163 points by mazsa 11y ago

bramblerose 11y 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-c 11y 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
  - bramblerose 11y ago
    Thank you, that clarifies a lot.
  - jnbiche 11y 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 11y 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 11y 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.
    - stormbrew 11y ago
      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.
    - kanzure 11y ago
      > "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.
      - TylerE 11y ago
        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?
- Uptrenda 11y 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.
- ewillbefull 11y 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.
  - mkramlich 11y ago
    this is the clearest summary I've seen, thank you
agnuacc 11y ago
What does this mean for z.cash?
- nickodell 11y ago
  The technology has no relation to zcash, other than that both are cryptocurrencies.
  - CiPHPerCoder 11y 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.
    - ewillbefull 11y ago
      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.
- kushti 11y ago
  Electric Cash Company is getting a good promotion with this demo, at least
ryan-c 11y 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 11y 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 11y ago
    This roughly described distributed.net back around 1997.
dkopi 11y 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 11y ago
  But there will be many more non-obvious, non-sad uses for it.
  - ycmbntrthrwaway 11y ago
    And as usual with crypto technology, "bad guys" already have means to achieve their goals anyway. Cryptolockers already exist.
- hnmcs 11y 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-bitcoin-believer-who-gave-up.html http://www.nytimes.com/2016/01/17/business/dealbook/the-bitc...
  - nickodell 11y ago
    No, not scalable beyond that.
  - flatline 11y ago
    ~2.7 tps in practice, and shrinking as transaction sizes grow.
  - ikeboy 11y ago
    These transactions work fine with the lightning network, according to the author on reddit: https://www.reddit.com/r/Bitcoin/comments/47rk85/first_successful_zeroknowledge_contingent_payment/d0fbysd?context=3 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_Lightning_require_bigger_blocks_anyway.3F https://en.bitcoin.it/wiki/Scalability_FAQ#Doesn.E2.80.99t_L... and https://blockstream.com/2015/09/01/lightning-network/ https://blockstream.com/2015/09/01/lightning-network/
abhv 11y 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 11y 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.
  - abhv 11y 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 11y 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 https://eprint.iacr.org/2012/215.pdf
tommynicholas 11y 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.
- ewillbefull 11y ago
  Thanks! In this case, the Zcash team did build the first zero-knowledge contingent payment, but we performed it on the Bitcoin network.
  - tommynicholas 11y 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 11y 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_successful_zeroknowledge_contingent_payment/d0f69ml 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.
- ewillbefull 11y 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 https://github.com/akosba/jsnark). I'm building something in Rust called bellman (https://github.com/ebfull/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.
  - mkramlich 11y ago
    plus Zooko's team has started building as well
kushti 11y 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).
- nullc 11y 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.)
darawk 11y 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 11y ago
  You are missing something: the seller can see the program that evaluates the solution.
  - darawk 11y 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.
    - nullc 11y ago
      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")
      - darawk 11y ago
        Ah, of course, just fix the run time. I should have realized that. Thanks. Nice work!
ChemicalWarfare 11y ago
Both the seller and the buyer paid tx fees, correct?
- HappyTypist 11y 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%.
  - ChemicalWarfare 11y 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.
Manishearth 11y 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.txt 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.
- nullc 11y 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).

163 points by mazsa 11y 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-c 11y 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
- bramblerose 11y ago
  Thank you, that clarifies a lot.
- jnbiche 11y 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 11y 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 11y 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.
  - stormbrew 11y ago
    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.
  - kanzure 11y ago
    > "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.
    - TylerE 11y ago
      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?
Uptrenda 11y 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.
ewillbefull 11y 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.
- mkramlich 11y ago
  this is the clearest summary I've seen, thank you

agnuacc 11y ago

What does this mean for z.cash?

nickodell 11y ago
The technology has no relation to zcash, other than that both are cryptocurrencies.
- CiPHPerCoder 11y 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.
  - ewillbefull 11y ago
    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.
kushti 11y ago
Electric Cash Company is getting a good promotion with this demo, at least

ryan-c 11y 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 11y 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 11y ago
  This roughly described distributed.net back around 1997.

dkopi 11y 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 11y ago
But there will be many more non-obvious, non-sad uses for it.
- ycmbntrthrwaway 11y ago
  And as usual with crypto technology, "bad guys" already have means to achieve their goals anyway. Cryptolockers already exist.
hnmcs 11y 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-bitcoin-believer-who-gave-up.html http://www.nytimes.com/2016/01/17/business/dealbook/the-bitc...
- nickodell 11y ago
  No, not scalable beyond that.
- flatline 11y ago
  ~2.7 tps in practice, and shrinking as transaction sizes grow.
- ikeboy 11y ago
  These transactions work fine with the lightning network, according to the author on reddit: https://www.reddit.com/r/Bitcoin/comments/47rk85/first_successful_zeroknowledge_contingent_payment/d0fbysd?context=3 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_Lightning_require_bigger_blocks_anyway.3F https://en.bitcoin.it/wiki/Scalability_FAQ#Doesn.E2.80.99t_L... and https://blockstream.com/2015/09/01/lightning-network/ https://blockstream.com/2015/09/01/lightning-network/

abhv 11y 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 11y 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.
- abhv 11y 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 11y 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 https://eprint.iacr.org/2012/215.pdf

tommynicholas 11y 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.

ewillbefull 11y ago
Thanks! In this case, the Zcash team did build the first zero-knowledge contingent payment, but we performed it on the Bitcoin network.
- tommynicholas 11y 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 11y 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_successful_zeroknowledge_contingent_payment/d0f69ml 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.

ewillbefull 11y 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 https://github.com/akosba/jsnark). I'm building something in Rust called bellman (https://github.com/ebfull/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.
- mkramlich 11y ago
  plus Zooko's team has started building as well

kushti 11y 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).

nullc 11y 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.)

darawk 11y 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 11y ago
You are missing something: the seller can see the program that evaluates the solution.
- darawk 11y 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.
  - nullc 11y ago
    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")
    - darawk 11y ago
      Ah, of course, just fix the run time. I should have realized that. Thanks. Nice work!

ChemicalWarfare 11y ago

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

HappyTypist 11y 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%.
- ChemicalWarfare 11y 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.

Manishearth 11y 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.txt 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.

nullc 11y 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).