6
$\begingroup$

My understanding is that Zk-SNARKs (and zero-knowledge proofs in general) can be used to prove that a polynomial-time computation has a certain output, while keeping one or more of the inputs to that computation hidden.

For example, say you have a string h which is the output of a fixed hash function. If you know an input x which hashes to h, you could use a Zk-SNARK to prove you know x in zero knowledge (i.e. without revealing x). Equivalently, given a verification function like this:

verify(x,h):
    return hash(x) == h

you're essentially proving that you know inputs to verify which make it return true, without revealing all of those inputs.

So, here's my question. Suppose you have a secret poly-time, single-argument function f. Given a public input x and a public output y, could you use a Zk-SNARK to prove in zero knowledge that f(x)=y? I.e., given the function

verify(f,x,y):
    return f(x) == y

could you still construct a proof showing that verify returns true while keeping f secret? The difference between this situation and the above one is that now you're proving something about a verify function that is itself running an arbitrary function, rather than one which simply does some fixed calculations to check things--and this seems like a pretty significant difference to me.

It seems like this should be possible in theory, because if f is poly-time then f(x)=y is still an NP statement (although I may be wrong about that)--but I'm wondering if it's possible in practice with today's Zk-SNARKs.

The way I phrased my question, I guess knowledge of such a function is trivial, because if the prover knew y in advance, they could just define f to return y. So to make things more interesting, you could imagine a situation where the prover commits to f in advance, and the proof is expanded to verify that the f used to compute y matches the commitment.

$\endgroup$
1
$\begingroup$

Yes. Express $f$ as a (say, Boolean) circuit. If $f$ is poly-time it will have a number of gates that is polynomial in the input size. A universal circuit $U$ is a Boolean circuit that evaluates any circuit up to bounded size (see e.g. this eprint from 2017 by Günther, Kiss and Schneider). The input to $U$ will be bits representing the structure of the circuit of $f$. Since $U$ is just another Boolean circuit, it can also be represented as a QAP as in the Pinocchio paper, or whatever the zk-SNARK uses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.