## zk-SNARKs

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

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.

## Computation

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.

## From Theory to Practice

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?

## One line, one operation

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:

## R1CS

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!

## QAP

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

## Hiding

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.

## Knowledge of coefficient

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.

## Homomorphic Hiding

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.

## Elliptic curves

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

## Pairing

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.