As we now know, a zk-SNARK is a succinct and easily verifiable proof that a defined computation was performed. What we need to know at this point is what kind of “computation” we can handle, and how we can express it.
To do that, we’ll introduce a tiny little bit of complexity theory, i.e. the theory that classifies computational problems according to their difficulty.
I’m now going to offer some definitions using the same informal and unassuming style I’ve always used. These definitions are not really necessary to understand what a zk-Snark is and how it works, but they are terms that are widely used in the specific literature, so it might be useful to have a rough idea of their meaning, should you want to do some more investigation and learning. (For the experts: as usual, suggestions and corrections are appreciated!)
A problem is an abstract question to answer. A problem is solved by performing an algorithm that executes some defined steps. An instance of the problem is a specific, numeric, defined case of that abstract problem, and can be represented as data input to the problem’s algorithm. The algorithm can be encoded in different representations, and in particular in a binary alphabet (“0”s and “1”s). Thanks to this fact, we can consider just “decision problems”, i.e. problems whose output is either a 0 (false) or a 1 (true); this will not limit our scope, as for computations with output longer than 1 bit, we can have one decision problem for each bit.
Again, in our list of definitions, if our alphabet is {0,1}, we can see a decision problem as a formal “language” on this alphabet. Members of this language are the instances of that problems whose output is yes, and the non-members are the instances whose output is no.
So, as just said, we’ll only consider functions that only output 0 or 1, and call them “problems”. We want to measure how hard it is to solve a given problem. For a specific implementation of a function, we can count the number of steps it takes to compute the result for a specific input, and measure that in the size n of the input.
With all the above in mind, we can look at two classes of problems: P and NP.
P is the class of problems that can be coded as programs that run in polynomial time, i.e. at most nc steps, for some c. Even if c can be quite large, P is the class of “feasible” problems, i.e. that can be calculated in a sensible time by the computers available today. Usually, if we have to calculate a formula, we typically end up in P.
When instead we want to perform a search, we likely end up in another class of problems, called NP. This class includes all the problems for which, if we already know a solution W to an instance P of the problem, there is a program that can verify in polynomial-time that W is indeed a solution to P. W is called a “witness”.
We know from the literature that we can create a Snark for all problems in the NP class, and that thanks to the existence of NP-complete problems. An NP-complete problem is a problem for which there is a way to map, in polynomial-time, any NP-problem to it. This mapping is called “reduction”; we can see it as a compiler that encodes the generic NP problem to this NP-complete language.
To sum up and to go back to our zk-Snark world, we’ll see that there is a nice NP-complete problem for which we know how to provide proof that it was executed, without disclosing any specific information about the run computation. We know that we’ll be able to reduce any NP problem to it, so we’ll be able to prove any of them in zero-knowledge.