Private input (exo_compute) examples

[jimouris]

Hello,

I am trying to understand how to provide private inputs to proofs so they can become zero-knowledge (as in issue #5). I have read the exo_compute.txt and also exo_compute_example.c, however, it is not very clear how to use the exo notation.

For instance, in the exo_compute_example.c, the public inputs are in values array and exo0_inputs is initialized with those values (line 19), and then the exo_compute method is called (line 24). After that, all the computation take place in the theTranscript[0].value variable. Is that value encrypted by the exo_compute method, and thus became private?

It is not very clear, and I could not found any other references about how exo_compute, works. It would be very helpful if you can provide an example (such as base_2_log.c also written using exo_compute for preserving the privacy of the input (uint32_t a in that example).

Thanks in advance, Dimitris

[maxhowald]

In general, the purpose of exo_compute() is to allow the prover to set a specified set of variables (the output parameter of the exo_compute() function) to any value.

The zero-knowledge property of the underlying SNARK protocol provides a guarantee that the verifier does not learn anything about these variables (and any others) other than what is implied by the output.

In exo_compute_example, the call to exo_compute allows the prover to set theTranscript however it likes. However, because of the comparison in line 27, a prover that wants to produce a valid proof should fill theTranscript with a sorted list.

For a computation like base_2_log, one could use exo_compute to write a computation which outputs the logarithm of a prover-provided value, but the verifier could learn the prover's input by simply exponentiating the returned output.

A more realistic use case for exo_compute might be to enable the prover to prove it knows the preimage to a verifier-chosen hash, without revealing anything about that preimage to the verifier.

In this case, the verifier's input to the computation would include the hash, and the pseudocode of the compute function would be:

exo_compute(input_hash, preimage)
prover_hash = sha_1(preimage)
if prover_hash == input_hash {
   output->prover_knows_preimage = 1;
}

Where preimage is an uninitialized array and sha_1 is a function that returns the SHA-1 hash of its input. In this case, the prover would look for an executable which should look up the preimage the prover knows for the provided hash, and the end-to-end guarantee about what the verifier can learn about the preimage comes from the zero-knowledge property of the SNARK plus the preimage resistance of the SHA-1 hash function.

[jimouris]

Thank you for the thorough answer, but I still have some issues unresolved concerning the syntax.

In exo_compute_example.c:

• I understand that the prover fills theTranscript with whatever array she likes.
• However, in line 24 (exo_compute(exo0_inputs,lens,theTranscript,0);), the exo_compute function also takes as an argument the exo_inputs array (which is initialized with the input->values) and its length. input->values array seems that is not used at all, as well as exo_inputs.

Similarly, in the sha_1 example that you provided, the exo_compute takes as the first argument the input_hash (the one chosen by the verifier) and as a second the uninitialized preimage that the prover will fill. I cannot understand why the input_hash is necessary to be provided in the exo_compute function.

Thank you very much for your time.

[kwantam]

I cannot understand why the input_hash is necessary to be provided in the exo_compute function.

You can think of exo_compute as giving the Prover an oracle from which to request advice. In the hash example, the oracle takes as a query a SHA-1 digest and returns a corresponding preimage. So the reason input_hash is necessary is just that the oracle would otherwise have no idea what preimage to return.

(Of course, in this case presumably the "oracle" just consults a lookup table, i.e., it can't answer all queries. But that's beside the point---surely it can't answer a question that isn't asked!)

[jimouris]

@kwantam Thanks for the clarification, I think I understood it.

I have created a pull request (#27) that demonstrates the use-case proposed by @maxhowald using SHA256 algorithm.