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.
The function hh() needs to have some other good properties, e.g. it must be “collision-resistant”, i.e. different x’s are always mapped to different y’s. Also, the function hh() should also “preserve” equations of arithmetic expressions into the mapped space, i.e, if for instance we only know the hidings hh(x1), hh(x2), hh(x3) of three variables x1, x2, x3, and some coefficients a, b, c of arbitrary value, we can calculate the hiding of a*x1+b*x2+c*x3 as a function of hh(x1), hh(x2), hh(x3), a, b, c. The name “homomorphic” comes from this last property, as the mapping preserves the algebraic structure.
The example typically presented to clarify the homomorphic property uses the exponentiation function as hh(x). In fact if hh(x) = ex, then y= hh(a*x1+b*x2+c*x3) = e(a*x1+b*x2+c*x3) = e(a*x1) * e(b*x2) * e(c*x3) = hh(x1)a * hh(x2)b * hh(x3)c
Now, this function is “homomorphic”, but not really hiding, as if y=hh(x)=ex, we can know x from y by calculating the logarithm base e of y.
To create the above “hiding”, we need first to restrict our x values to only integers between 1 and a value p-2, where p is both big and a prime number. This set of numbers is mathematically defined as a “finite field”. This is an important name and concept: all the variables we use in our circuits must belong to a finite field, and so we will calculate all the constraints of our circuits using these numbers. In our circuits, if we recall the first post on computation, we can only use additions and multiplications “modulo p”.
Having moved from the real number to a finite field, we can redefine our y=hh() function as y=Gx, where G is a number in the finite field just defined.The set of possible y will be a subset of our finite field: y will always be calculated “modulo p”. This set of all the possible values of y, when x belongs to the defined field, is a “cyclic group”, which means that all values of y can be calculated from the generator G: G0=1, G1=G, G2, G3, …
Ok, with this y=hh(x)=Gx, we have “homomorphic hiding”! But unfortunately, this hh(x) is not the function that we are really going to use in our zk-Snarks. We need something more powerful!
The point is that, not only do we want that our equations calculated in P: [C(P) - A(P)*B(P)] = Z(P) * H(P) is preserved in the hidings, and that, without knowing the points P and u*P, the prover can calculate the above and the other equations in the hidings, and that the prover can prove that he used the circuit’s polynomials and the same w values to calculate the proof, but we also need to be able to verify that the equations hold, without revealing w. The time has come to meet elliptic curves that support pairing!