Why are zk-SNARKs possible, in layman's terms

Question

zk-SNARK: Zero-Knowledge Succinct Non-interactive Argument of Knowledge

From the Ethereum blog:

One natural use case for the technology is in identity systems. For example, suppose that you want to prove to a system that you are (i) a citizen of a given country, and (ii) over 19 years old. Suppose that your government is technologically progressive, and issues cryptographically signed digital passports, which include a person’s name and date of birth as well as a private and public key. You would construct a function which takes a digital passport and a signature signed by the private key in the passport as input, and outputs 1 if both (i) the date of birth is before 1996, (ii) the passport was signed with the government’s public key, and (iii) the signature is correct, and outputs 0 otherwise. You would then make a zero-knowledge proof showing that you have an input that, when passed through this function, returns 1, and sign the proof with another private key that you want to use for your future interactions with this service. The service would verify the proof, and if the proof is correct it would accept messages signed with your private key as valid.

I bolded the parts which seem impossible to me intuitively. I found some research papers with very technical explanations, which I don't understand. Could someone explain why this is possible, in layman's terms? Intuitively it seems like there would be plenty of ways for the client to alter the program code in order to produce output which could be used to fake their identity.

Some documentation and code

Answer 1

Take it back a step, and consider a more simple zero knowledge proof.

A digital signature on an email can be thought of as a very specific, narrow example, of a zero knowledge proof. I (the 'prover') provide a message M, and a digital signature over M (hash of M, encrypted with my private key) to you.

You (the verifier) can hash M for yourself, decrypt my provided signature with my public key, and compare, and if they match, you've confirmed my signature. What you just did is verify the arithmetic "proof" I provided of the following NP statements:

I know the private key Q which corresponds with public key P I used Q to sign message M

You are now convinced that I know Q, without me having to reveal Q to you. All I had to do was give you proof I know Q, in the form of inputs (message M and its signature) and the function, which when fed those inputs, compares correctly.

That's a zero knowledge proof.

Conceptually, now replace "I know the private key Q" with "The government private key has signed a statement saying I am of legal age". The same logic applies.

With that idea of the "zk" part in mind, the "magic" of the "snark" part is that this can be generalized to any computable NP statement expressed logically as an arithmetic circuit.

In neither of these cases can the "client alter the program code." I find the digital signature analogy useful to keep in mind when trying to understand these.

Answer 2

When you have eliminated the impossible, whatever remains, however improbable, must be the truth. (Sherlock Holmes)

If I find you in my dorm room and the door and windows are intact, I can only conclude that you somehow learned the entry code, because I do not know of any other way by which you could have entered my room without breaking the door or windows.

A ZK-SNARK for a function $f$ is similar: if you present a proof for the result $1$ which can pass the verification procedure, it necessarily means that you must know an $x$ such that $f(x) = 1$. This is because we do not know of any (efficient) way to generate such a proof if you do not know such a value $x$. In fact, we have a proof that being able to do this would imply being able to solve certain mathematical problems which are believed to be hard (you can think of factoring integers, although the problems used to construct SNARKs are more complicated). So when you say

Intuitively it seems like there would be plenty of ways for the client to alter the program code in order to produce output which could be used to fake their identity.

... there may or may not be, but we do not know of any and we consider it very unlikely (i.e., impossible, for all practical purposes).

Answer 3

I wanted to take a stab at laymen's terms for this...

zk-SNARK protocols provide proof that a specified algorithm (or circuit) was run against some data. I want to prove I know public w and private x such that f(x, w) = 1, but I don't want to give you x. I input x and w into f and f spits out 1, while the zk-SNARK part of the protocol will generate a signature that says I just did all that with that public input and that output, so I must have a valid private input.

Another practical application I've seen described is that you want to know the mayoral candidate's DNA is not among the database of DNA found at crime scenes. The candidate naturally does not want to give everyone his DNA, so how can we know he's not in that database? You could design a zk-SNARK protocol where there is an algorithm that checks the input DNA against the database and outputs 1 if match and 0 if no match. You let the cops run that algorithm in private and then they come forward and present a zk-SNARK proof that shows they ran the algorithm and got output 0--this would reliably prove that the cops checked the database for his DNA and the output was no match.

So I think of it is as proof that I went through the circuit.

I found this very helpful: https://media.consensys.net/introduction-to-zksnarks-with-examples-3283b554fc3b

and this perhaps too cute tweet is helpful as well: https://twitter.com/ChrisLundkvist/status/799807876982251520

Intuitively it seems like there would be plenty of ways for the client to alter the program code in order to produce output which could be used to fake their identity.

Well...I'm still working my way through Vitalik Buterin's paper that so far does a good job describing what's going on under the hood. As I have begun to understand it, it's kind of like this:

Take the function f and turn it into a special circuit where each operation is like a gate, with a special encoding. When the operations are run together the compounded encodings of each gate can be converted to form some polynomial that is difficult to guess--anything that runs through the operations in order will have generated that polynomial, and anything that did something different or went out of step will not be able to generate that polynomial.

An analogue in meatspace might be one of those scavenger hunts where each clue builds on the last, so you need to get each point in order. If you get to the end, you get a key that locks a lockbox. If you give that locked lockbox to someone, it doesn't matter what you put in it, you've proven that you went through all the steps to get there. Only in this analogy, think of each of those clues as a computer operation.

The polynomial generated by going through the circuit is then used to create a public and private key pair. When you run your input through the circuit the zk-SNARK protocol will give you a proof $\pi$ that has encrypted your private input and public input with the private key for that function. This is your proof that you went through the function with those inputs.

I'm sure I'm missing key parts of this so I'd welcome corrections. As someone trying to learn what's going on w/ zk-SNARKs, I can attest that many people do not succeed in explaining it well.

Answer 4

Amendig the previous answer by fkraiem, let me focus on an example returning $1$.

Schnorr verification equation could be rewritten: $$g^{r} h^{-c} a^{-1} = 1$$ for a group generator $g$, Prover response $r$, Verifier challenge $c$, initial message of Prover $a$ and public key $h$ such that $h = g^x$ for some private key $x$. With this protocol, Prover calculates $r = x c + b$ and $a = g^b$ so that Verifier cant learn $x$ from data received.

Point is, without "knowing" the secret $x$, Prover can produce satisfying response with only negligible probability, defined by cardinality of challenge set, which could be the group order.

In this example, $1$ is group identity.