# Zero-Knowledge Proof of honest function execution - Is this possible?

Assume Alice and Bob share a well-known function $f(x)$. Bob asserts that he has a $y$ such that $f(y) = true$. Bob's $y$ is secret, but he is willing to share a hash of it. Alice wants to purchase $y$ from Bob, but only if she can be assured that $f(y) = true$ before the purchase happens.

I've studied Zero-Knowledge Proofs, but the examples I've seen seem to be focused on proving knowledge of a value without revealing the value itself. This seems different... Alice must somehow know that Bob executed $f(y) = true$ truthfully, without altering $f(x)$ or substituting a different value for $y$. Is this possible without a trusted third party?

• That depends on how the "purchase" is supposed to work. ​ If it's supposed to be with physical currency, then I can't think of any mathematical formalization of the problem. ​ If it's supposed to be with some electronic currency, then this is similar to fair exchange, and a semi-trusted third party is enough. ​ ​ ​ ​ – user991 Sep 12 '16 at 20:19

I am not totally clear on what the procedure for actually "buying" something in your protocol should be, but I'd point out that a (totally) fair exchange between Alice and Bob is impossible. This follows from the fact that no 2 party secure computation protocol can achieve fairness (impossibility result). In a nutshell: When Alice and Bob run a protocol to exchange some secrets, then one party can always abort as soon as it gets its result without letting the other party know their secret. As pointed out by Yehuda Lindell in the comments this is not true for all functionalities, see link in the comments.

Lets focus on how Bob can convince Alice that he has some secret $x$ that fulfills some predicate $f$.

In the case of arbitrary predicates $f$, like "I know a pre-image to a specific SHA-1 output", you can use something called zero knowledge using garbled circuits. This approach first appeared in the following paper: zero knowledge using garbled circuits. The high level idea is to use so called garbled circuits that are, in general, used for secure two party computation (which your problems is a special case of). For your setting, Alice is the verifier and Bob the prover. The protocol proceeds as follows:

1. Alice garbles a circuit representing the prediate $f$ and sends this circuit to Bob (note Alice has no input to that circuit).
2. Bob uses oblivious transfer to retrieve the wire input labels to the circuit that correspond to his input $x$.
3. Bob evaluates the circuit and commits to his output wire(s)
4. Alice "opens" the garbled circuit she sent in step 1 to convince Bob that she did not cheat by garbling some malicious circuit
5. Once Bob is convinced everything was Ok, he opens his commitment.

On a high level Bob cannot cheat because the only thing he is doing is retrieving some input wire labels, and running them through the circuit.

This may sound like a terribly slow approach, but it is actually not that bad and it strongly depends on what you want to do with it.

Garbled circuits, where only one party has an input are more efficient then the general garbled circuits (see Two halves make a whole in the "privacy-free garbling" section).

Another fairly efficient protocol was recently proposed ZKBoo. This protocol also does something similar to using garbled circuits. However, they focus on reducing the computational costs, but slightly increase the bandwidth overhead, which is already the bottleneck in all garbled circuit approaches.

For less general predicates there may be more direct and more efficient solutions.