A possible cryptographic implementation of a zero-knowledge proving system is a “zk-SNARK”, and as far as I know it’s the oldest practical implementation of a zero-knowledge system.

The “Pinocchio” protocol is I believe the first practical, usable implementation of a zk-Snark, a result that comes after a few decades of academic work carried out by a number of extremely brilliant people.

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.

We want to give proof of having executed a defined computation, and that this computation will have to belong to a specific class of problems. How do we express the computation that we need to prove?

Now that we have expressed the computation in this language, we need to “unroll” it, by writing it as a sequence of lines, all of them following this format:

We now have the computation that we want to prove, nicely expressed as a sequence of lines that simply assign the result of the multiplication of sums of variables to a new variable: great!

A quick recap of some of the previous posts, before we move ahead. We have a defined computation and we want to prove that we did run it. 

Before introducing the cryptographic tools we need, just a brief recap of some of my previous posts. We can express an instance of a problem as three vectors of polynomials, and a solution to that computation as a vector of values.

If you read and spent some time on the previous posts on the blog, you should know that a proof will be the hidings of A(P), B(P), C(P), and H(P), all calculated in the hidden space by using the hidings of the “building block” polynomials.

In some of my previous posts, we used a “one-way function”, y=hh(x). Being a one-way function, we know that it is practically impossible to guess x knowing only the function and y.

We’ll need to brush up on some maths here, and we’ll start from a definition: the set of points (X,Y) that satisfies the equation y^2 = x^3 + A*x + B is an elliptic curve. 

Let’s look at the tools that we’ve covered so far to build a homomorphic hiding mapping. We have a finite field of order p, where p is a prime number, and a group of points (x,y), whose coordinates belong to the same finite field.