Zero Knowledge Contingent Payment

It's 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 far-out ones:

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.