Zero Knowledge Contingent Payment

It's possible to make payments using Bitcoin which are released if and only if some knowledge is disclosed by the payee and to do this in a trustless manner where neither the payer or payee can cheat. This is accomplished using the combination of a hash-locked transaction and a bitcoin-external protocol to set things up so that the data revealed in the hashlock release is the data they need.

Protocol outline

Hash locked transactions

Its possible to author a payment in the existing Bitcoin system that requires the redeemer to provide a "secret" which hashes to a specified value. The 0.01 output here with the SHA256 opcode is an example of such a transaction. "To collect these funds your transaction must provide a value that hashes to this other value."

Used directly, like in the above example, this is insecure: Once you've published the spending transaction another node could just drop your transaction and use the password in a new transaction that pays him instead.

So— the advice is that you shouldn't use a password alone, you should require a signature and a password. But then what is the use of that?

There are a couple uses but I'll give an example here of one of the more impressive and and far-out ones:

Zero knowledge proof to binding

Let H() be a complicated computer program. For some H(X)=Y you want to know some X that gives you a particular Y.

Say I happen to _know_ some X that answers your question... and I'd like to sell it to you. But we don't trust each other at all, and because we're computer geeks we have no friends who can act as trusted mediators. Can we make this exchange using Bitcoin with zero trust? The answer turns out to be yes.

Here are some examples of what H() could be:

• H() could be a password hashing algorithm and you're looking for the password that gives you a particular hash in order to crack it.
• Perhaps H() is a complicated program that decides if a piece of music is one you would find beautiful (i.e. Y is a true/false output)
• H() could be a program that verifies possession of a valid machine readable travel document issued to a particular person. In this case, you would be able to define a payment to someone based on some arbitrary attributes about them, such as their name + date of birth, or perhaps by providing a photo of their face that's then matched against the travel document using the Eigenfaces algorithm. There would be no need to obtain a public key from them ahead of time meaning that, for example, you could send money to someone who was only just born and doesn't yet have a wallet.
• H() could be a program that interprets another program on some secret input and yields true if the input data manages to put the program into a corrupted state. This would allow security researchers to sell exploits to software developers so they can be fixed, but in an anonymous and low trust way.

A zero-knowledge proof lets someone prove a mathematical fact to another person without teaching them anything about the fact itself. It has been proven that you can convert any computer program into a zero-knowledge proof (this is referred to mathematically as PSPACE⊂IP ). So, using a zero-knowledge proof I could prove to you that I know some X such that H(X)=Y ... which is helpful but it's not enough because you could pay me and I could not tell you the answer (or I could tell you and then you don't pay). Here is where the password locked transactions come in.

First I encrypt X with random key K, Ex=AES(X,K). then I construct the program:

Program(K,Ex,H()) =>  [Ex,Hk,Y] {
  Hk=SHA256(K);
  Y=H(UNAES(Ex,K));
  return [Ex,Hk,Y];
}

In English: The program takes the encrypted solution and the key to decrypt it, and outputs the encrypted solution, the hash of the decryption key, and the result of running the program on the solution.

I convert that program into a zero knowledge proof. Externally to Bitcoin I tell you Ex,Hk,Y and then prove that I executed the program faithfully.

You then form a Bitcoin payment which requires both my public key and password K. In order to redeem this transaction I must disclose K, the key you need to decrypt Ex and give you your solution. So neither of us can cheat, so no trust is required.

The first ZKCP was performed on the Bitcoin network in 2016, after waiting almost 5 years for sufficiently powerful general purpose ZKPs to become practically available.

But what if they're just anti-social and don't redeem the txn?

If you're concerned that they might rather leave the funds unspent rather than disclose their password, perhaps an effort to extort you, you could construct the payment so that it can alternatively be spent by a "refund transaction" which has a signature from both you and the other party.

You first create the ZKP payment transaction which requires (Password+Their_signature) OR (Their signature plus Your signature). You keep this transaction private. You then write a new transaction, the refund transaction, which spends the payment back to you but has an nlocktime set in the future (e.g. 1000 blocks from now). You sign it, and give it to the other party to sign. He is able to sign it without actually seeing the payment transaction (he only sees its hash). When he returns it, you then release the payment transaction. If he does not redeem the payment transaction before the locktime expires you transmit the refund and recover it yourself. Because of the locktime you are unable to steal the payment back right after sending it to him.

Alternatively, you could construct the payment as an anyone can pay transaction where the output is greater than the input you provide. You would give him this transaction, then he would add funds of his own and announce it and wait for it to be mined before announcing the key in the transaction spending it. This way he could not lock up your funds without locking up funds of his own.

Further mproving privacy

Many other transaction types also use the same hash locked pattern, but privacy can be further improved: A ZK-payment can be transformed using the CoinSwap approach where they payer first pays into an ordinary 2-of-2 escrow+refund with the payee. The then would perform the ZK-payment transactions described above externally to the Bitcoin network, and if everything goes through without cheating the payer just signs a 2-of-2 release to pay the payee directly, without disclosing to the network that a hashlocked transaction was used. If the payer fails to release the escrow directly, the payee can just release it by announcing the hashlock and hashlock redeem.