Bitcoin zero knowledge clouds
Since then, several groups have continued to advance this work, creating compilers, performance improvements, and most critically, practical tools like libsnark. Because of this work, ZKCP can now become a practical tool. Because these efficient ZKPs are cutting-edge technology which depend on new strong cryptographic assumptions, their security is not settled yet. But in applications like ZKCP where our only alternatives are third-party trust, they can be used in ways which are a strict improvement over what we could do without them.
If you accept the existence of the zero-knowledge proof system as a black box, the rest of the ZKCP protocol is quite simple. The buyer first creates a program that can decide whether the input it is given is the data the buyer wants to buy.
This program only verifies the information, it does not produce it—the buyer does not even have to have any idea how to produce it. For example, it is easy to write a program to verify that a Sudoku solution is correct, but harder to write a Sudoku solver, Sudoku is NP-complete.
The buyer here only needs to write the solution verifier. The buyer performs the trusted setup for the proof system and sends the resulting setup information over to the seller. The seller sends Ex, Y, the proof, and his pubkey to the buyer. So the buyer initially wanted to buy an input for his program, but now he would be just as happy to buy the preimage of a hash.
As it turns out, Bitcoin already provides a way to sell hash preimages in a secure manner. The effect of this payment is that the seller can collect it if he provides the hash preimage of Y and a signature with his key. As a result, when the seller collects his payment he is forced to reveal the information that the buyer needs in order to decrypt the answer. This ScriptPubkey is also the same as would be used for a cross-chain atomic swap or a lightning payment channel.
Wallet support for these transactions has been implemented for Bitcoin Core in PR This wallet support is used by the sudoku ZKCP client and server available at https: There are two primary restrictions of this approach. First, that it is interactive: And second, that the ZKP system, while fast enough to be practical, is still not very fast. For example, in our demo the ZKP system proves 5 executions of SHA and the Sudoku constraints, and takes about 20 seconds to execute on a laptop.
The seller sends Ex, Y, the proof, and his pubkey to the buyer. So the buyer initially wanted to buy an input for his program, but now he would be just as happy to buy the preimage of a hash. As it turns out, Bitcoin already provides a way to sell hash preimages in a secure manner.
The effect of this payment is that the seller can collect it if he provides the hash preimage of Y and a signature with his key. As a result, when the seller collects his payment he is forced to reveal the information that the buyer needs in order to decrypt the answer. This ScriptPubkey is also the same as would be used for a cross-chain atomic swap or a lightning payment channel.
Wallet support for these transactions has been implemented for Bitcoin Core in PR This wallet support is used by the sudoku ZKCP client and server available at https: There are two primary restrictions of this approach.
First, that it is interactive: And second, that the ZKP system, while fast enough to be practical, is still not very fast. For example, in our demo the ZKP system proves 5 executions of SHA and the Sudoku constraints, and takes about 20 seconds to execute on a laptop.
The verification of the proof takes only a few milliseconds. In Paypub, instead of using a zero-knowledge proof the buyer is shown a random subset of the data they are attempting to buy, and the seller is forced to unlock the rest when they collect their payment. Paypub avoids the complexity of dealing with a zero-knowledge proof— and also allowing the exchange of information that only humans can verify—, but at the cost of some vulnerability to cheating, and only being usable with a relatively large set of randomly verifiable information.
I look forward to the exciting applications people will find for them as the technology becomes increasingly practical. The first successful Zero-Knowledge Contingent Payment. The transfer involved two transactions: See the slides from the live demo. Background I first proposed the ZKCP protocol in in an article on the Bitcoin Wiki as an example of how tremendously powerful the existing primitives in Bitcoin Script already were.
The seller picks a random encryption key and encrypts the information the buyer wishes to buy. Using the ZKP system, the seller proves a composite statement: