Zero-Knowledge Contingent Payment
bitcoincore.org
bitcoincore.org
# 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_CHECKSIGThe 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.
The benefits of the internet were pretty clear and obvious. The benefits of Bitcoin are neither clear nor obvious.
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.
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.
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.
http://www.al-monitor.com/pulse/zh/originals/2015/04/aleppo-...
http://dlca.logcluster.org/display/public/DLCA/3.4+Ukraine+T...
But for people who want non-refundable payments, or scriptable m-of-n payment rules, etc, it's almost the only game in town.
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.
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.
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.
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.
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.
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...
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/
* 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.
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.
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).
But the encryption scheme has only two possible inputs; can't this be brute forced?
Perhaps an example would help me understand here.
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?
> 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?
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.
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)
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).
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.)
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.
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.
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.
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.
The CRS issue is that off-chain, a malicious Verifier (buyer) may learn about the witness, i.e., either enc key or solution.
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.)
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?
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.
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")
Nice work!