The first successful Zero-Knowledge Contingent Payment

I am happy to announce the first successful Zero-Knowledge Contingent Payment (ZKCP) on the Bitcoin network.

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.

Imagine a movie-style “briefcase swap” (one party with a briefcase full of cash, another containing secret documents), but without the potential scenario of one of the cases being filled with shredded newspaper and the resulting exciting chase scene.

An example application would be the owners of a particular make of e-book reader cooperating to purchase the DRM master keys from a failing manufacturer, so that they could load their own documents on their readers after the vendor’s servers go offline. This type of sale is inherently irreversible, potentially crosses multiple jurisdictions, and involves parties whose financial stability is uncertain–meaning that both parties either take a great deal of risk or have to make difficult arrangement. Using a ZKCP avoids the significant transactional costs involved in a sale which can otherwise easily go wrong.

In today’s transaction I purchased a solution to a 16x16 Sudoku puzzle for 0.10 BTC from Sean Bowe, a member of the Zcash team, as part of a demonstration performed live at Financial Cryptography 2016 in Barbados. I played my part in the transaction remotely from California.

The transfer involved two transactions:

8e5df5f792ac4e98cca87f10aba7947337684a5a0a7333ab897fb9c9d616ba9e 200554139d1e3fe6e499f6ffb0b6e01e706eb8c897293a7f6a26d25e39623fae

Almost all of the engineering work behind this ZKCP implementation was done by Sean Bowe, with support from Pieter Wuille, myself, and Madars Virza.

See the slides from the live demo.

Background

I first proposed the ZKCP protocol in 2011 in an article on the Bitcoin Wiki as an example of how tremendously powerful the existing primitives in Bitcoin Script already were.

Zero Knowledge Proofs

My ZKCP protocol required as a building block a zero-knowledge proof for arbitrary programs. Many kind of specialized zero-knowledge proofs exist: common digital signatures are an example, as are the range proofs in Confidential Transaction.

A zero-knowledge proof for general computation is a cryptographic system which lets a person run an arbitrary program with a mixture of public and secret inputs and prove to others that this specific program accepted the inputs, without revealing anything more about its operation or the secret inputs.

If this seems like impossible magic, for educational purposes I came up with a very simple but inefficient ZKP system that uses nothing fancier than boolean circuits and cryptographic hashes, or see Matthew Green’s Graph coloring ZKP example.

As my initial write-up on ZKCP noted, no such system was readily available in 2011 but they were believed to be possible, especially under specific constraints that would have worked for ZKCP.

In 2012 Gennaro, Gentry, Parno, and Raykova published a paper (“Quadratic Span Programs and Succinct NIZKs without PCPs”) which described an especially efficient construction. Since then, several groups have continued to advance this work, creating compilers, performance improvements, and most critically, practical tools like libsnark. The GGPR’12 cryptosystem requires a trusted setup, but for the ZKCP application this is no real limitation since the buyer can perform it. Because of this work, ZKCP can now become a practical tool.

Further reading:

GGPR’12 paper Microsoft Verifiable Computing group SCIPR Lab Libsnark

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.

How ZKCP works

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 picks a random encryption key and encrypts the information the buyer wishes to buy.

Using the ZKP system, the seller proves a composite statement:

Ex is an encryption of an input that satisfies the Buyer’s program. Y is the sha256 hash of the decryption key for Ex.

The seller sends Ex, Y, the proof, and his pubkey to the buyer. Once the buyer’s computer verifies the proof, the buyer knows that if he learns the input to SHA256 that yields hash Y, he can decrypt his answer.

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 buyer makes his payment to the following ScriptPubkey:

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. To avoid tying up the buyer’s funds forever, if the seller does not collect his payment within (e.g.) a day the buyer can reclaim the payment.

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. If he doesn’t, the buyer gets his funds back.

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#7601. This wallet support is used by the sudoku ZKCP client and server available at https://github.com/zcash/pay-to-sudoku.

The buyer’s program can be arbitrarily long and complex without adding any additional burden to Bitcoin’s blockchain–the only impact would be the increased time required for setup and proving, which all happens external to Bitcoin. No one outside of the buyer or seller learns anything about the buyer’s program (that is, they do not learn the nature of the information being sold).

Limitations and alternatives

This approach is much more scalable and private than conducting smart contracts inside the blockchain, and it isn’t subject to being held back by any performance or functionality limitations in Bitcoin’s smart contracting.

There are two primary restrictions of this approach. First, that it is interactive: the buyer can’t simply make a broadcast offer and have any interested seller accept the payment without back and forth communication. 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 SHA256 and the Sudoku constraints, and takes about 20 seconds to execute on a laptop. (The verification of the proof takes only a few milliseconds.)

One alternative to ZKCP is Peter Todd’s 2014 “paypub” protocol. 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.

In general I think that “trustless” smart contracts like these have the most value where either there are frequent automated transactions of very low value – such that the overhead of traditional methods of conflict resolution deprives the participants of meaningful access to justice–or for very high value exchanges where the speed, unreliability (especially across jurisdictions), or lack of privacy of traditional conflict resolution would be unacceptable.

I look forward to the exciting applications people will find for them as the technology becomes increasingly practical.

Gregory Maxwell