Explanation of SNARKs. Homomorphic hiding and blind computation of polynomials (translation)

Hi, Habr! I present to your attention the translation of ZCash blog articles, which describe the mechanism of the evidence system with zero disclosure of SNARKs used in the ZCash cryptocurrency (and not only).

My previous translations are from this area. I advise you first to familiarize yourself with them in order to better understand what will be discussed:

• Introduction to zk-SNARKs with examples (translation)
• Quadratic arithmetic programs: from mud to riches (translation)

In this part, we consider the homomorphic concealment and blind computation of polynomials. Go…

Homomorphic Hiding

The designs of zk-SNARKs include a harmonious combination of several components. To fully understand how these components work together, it will take plenty of time.
')
If I had to choose only one component, the role of which is most noticeable, then I would single out the Homomorphic Hiding (HH). In this part of the article we will explain what a HS is, and then we will give an example of why it is useful and analyze how it works.

Homomorphic concealment is not a term formally used in cryptography, and is introduced here for didactic purposes. By properties, it is similar, but weaker, than the well-known concept of a “ commitment scheme ”. The difference is that the CG is a function that defines the argument, while the obligation uses additional randomness. As a result, homomorphic concealments essentially “hide most of x”, while commitments “hide every x”.

HS $$$E (x)$the numbers x is a function that satisfies the following properties:

• For most x, with a known value $$$E (x)$finding x is a difficult task.
• Different argument values ​​result in different function values. Therefore, if $$$x ≠ y$then $$$E (x) ≠ E (y)$
• If anyone knows $$$E (x)$and $$$E (y)$, then it can generate the HS from arithmetic operations for x and y . For example, it can calculate $$$E (x + y)$knowing $$$E (x)$and $$$E (y)$.

A simple example of why a TOS is useful for evidence with zero disclosure: suppose Alice wants to prove to Bob that she knows the numbers x, y such that $$$x + y = 7$(Of course, it is not particularly interesting to know such x and y , but this is a good example for explaining the concept).

1. Alice sends $$$E (x)$and $$$E (y)$Bob.
2. Bob calculates $$$E (x + y)$from these values ​​(he can do this because $$$E$is gs).
3. Bob also calculates $$$E (7)$and now checks whether $$$E (x + y) = E (7)$. He accepts Alice’s evidence only if equality is fulfilled.

Because different argument values $$$E$correspond to different concealments (function values $$$E$. Note translator), Bob really only accepts the proof if Alice sent the hide for $$$x, y$such that $$$x + y = 7$. Bob, on the other hand, doesn't get the value. $$$x, y$, because he has access only to their hide.

Yet Bob received some information about $$$x$and $$$y$. For example, he may choose random $$$x '$and check whether the equality holds $$$x = x '$by calculation $$$E (x ')$. For this reason, the above protocol is not really a Zero-Knowledge protocol, and is used here only to clarify the schema. In fact, as we will see later, the TOS is ultimately used in SNARKs to mask the verifier’s requests, and not the proving secrets.

Now let's look at an example of how such hiding is arranged. In fact, we cannot build them for regular integers with regular additions, instead we need to consider finite groups :

Let n be some integer. When spelled $$$A \ mod \ n$for integer A , it means taking the remainder of dividing A by n . For example, $$$9 \ mod \ 7 = 2$and $$$13 \ mod \ 12 = 1$. You can also use $$$mod \ n$to define the addition operation on the set {0, ..., n - 1} . First, the usual addition is performed, but then $$$(mod \ n)$to the result to get the number included in the set {0, ..., n - 1} . Sometimes $$$(mod \ n)$is written to the right of the expression, specifying that this type of addition is used. For example, $$$2 + 3 = 1 \ (mod \ 4)$. We will call the set of elements {0, ..., n - 1} together with the operation of addition the group $$$Z_n$.

For the prime number p , you can use $$$mod \ n$, to define the multiplication operation on the set {1, ..., p - 1} , so that the result of the multiplication also always belongs to the set {1, ..., p - 1} . This is achieved by simply multiplying the integers, and then applying to the result $$$mod \ p$. For example, $$$2 ⋅ 4 = 1 \ (mod \ 7)$.

When p is not simple, it is problematic to determine the multiplication in this way. One of the problems is that the multiplication result can be zero, even if both arguments are not zero. For example, when p = 4 , we can get $$$2 * 2 = 0 \ (mod \ 4)$.

A set of elements along with this operation is called a group $$$Z ^ * _ p$. This group has the following useful properties:

1. This is a cyclic group. This means that there is some element g in $$$Z ^ * _ p$called a generator such that all the elements $$$Z ^ * _ p$can be written as $$$g ^ a$for some a from the set {0, ..., p - 2} , where $$$g ^ 0 = 1$
2. Discrete logarithm should be hard to accomplish for $$$Z ^ * _ p$. This means that when p is large enough, and the element h of $$$Z ^ * _ p$, it is difficult to find an integer a from the set {0, ..., p - 2} , such that $$$g ^ a = h \ (mod \ p)$
3. Since the degrees are added when multiplying elements with the same base, we obtain for a, b from the set {0, ..., p - 2} : $$$g ^ a * g ^ b = g ^ {a + b \ (mod \ p-1)}$

Using these properties, we now construct a homomorphic hiding that “supports addition”, which means that it is possible to calculate $$$E (x + y)$knowing $$$E (x)$and $$$E (y)$. Suppose the argument x is for $$$E$belongs to a group $$$Z_ {p-1}$therefore it is in the range {0, ..., p - 2} . Define $$$E (x) = g ^ x$for each such x , and prove that $$$E$is HS: it follows from the first property that it is different $$$x '$of $$$Z_ {p-1}$will correspond to different values ​​of the function. From the second property it follows that for $$$E (x) = g ^ x$hard to find x ; Finally, using the third property, for given $$$E (x)$and $$$E (y)$we can calculate $$$E (x + y)$as $$$E (x + y) = g ^ {x + y \ mod \ p-1} = E (x) E (y)$.

Blind calculation of polynomials

Now let's remember what the concept of a polynomial is, introduce the concept of “blind computation” of a polynomial and how it is implemented with the help of homomorphic concealment (HS). In the following, we will see that “blind computation” is the central tool in SNARK constructions.

Denote by $$$F_p$field size p , i.e. elements $$$F_p$belong to the set {0, ..., p - 1} , where addition and multiplication operations are performed with $$$mod \ n$as explained above.

Polynomials and linear combinations

Recall that a polynomial P of order d on the field $$$F_p$is an expression of the form:

$$$P (X) = a_0 + a_1 * X + a_2⋅ X ^ 2 + ... + a_d⋅ X ^ d$

for some $$$a_0, ..., a_d ∈ F_p$,

We can calculate the P point value $$$s ∈ F_p$substituting s as X , and calculating the resulting sum:

$$$P (s) = a_0 + a_1⋅ s + a_2⋅ s ^ 2 + ... + a_d⋅ s ^ d$

For who knows what $$$P$meaning $$$P (s)$is a linear combination of values $$$1, s, ..., s ^ ​​d$where a linear combination is a “weighted sum”, in the case of $$$P (s)$"Weights" are $$$a_0, ..., a_d$

Above, we have defined a TOS from $$$E$as $$$E (x) = g ^ x$where g is a generator of a group with a heavy discrete logarithm problem. We mentioned that this GS "supports addition" in the sense that $$$E (x + y)$can be calculated knowing $$$E (x)$and $$$E (y)$. Note also that it "supports linear combinations." This means that for given $$$a, b, E (x), E (y)$we can calculate $$$E (a x + b y)$This can easily be shown:
$$$E (ax + by) = g ^ {ax + by} = g ^ {ax} * g ^ {by} = (g ^ x) ^ a * (g ^ y) ^ b = E (x) ^ a * E (y) ^ b$

Blind calculation of polynomials

Suppose Alice has a polynomial P of order d , and Bob has the value $$$s ∈ F_p$which he chose randomly. Bob wants to know $$$E (P (s))$i.e. value of HS P at s . There are two easy ways to do this:

• Alice sends P to Bob, and he calculates $$$E (P (s))$myself.
• Bob sends s to Alice and she calculates $$$E (P (s))$and sends it to bob.

However, in the case of a blind calculation, we want Bob to know $$$E (P (s))$without receiving $$$P$- which excludes the first option. And most importantly, we do not want Alice to know s , which excludes the second option.

The main reason we don’t want to send $$$P$Bob, simply is that he is great - he contains $$$(d + 1)$elements, where d ~ 2000000 in the current Zcash protocol. In essence, this is due to the “limited” part of SNARK.

Using the GE, we can perform a blind calculation as follows:

1. Bob sends Alice to hide $$$E (1), E (s), ..., E (s ^ d)$
2. Alice calculates $$$E (P (s))$of items sent in the first stage and sends $$$E (P (s))$Bob. (Alice can do this because $$$E$supports linear combinations, and $$$P (s)$is a linear combination $$$1, s, ..., s ^ ​​d$)
   

Of course, it’s true that the sequence of hiding that Bob sends to Alice is as long as the polynomial itself, but it turns out that this sequence can be “hard coded” in the system parameters, and Alice’s messages will differ for each SNARK evidence

Note that only the hide were sent, and Alice did not recognize s , and Bob did not recognize P.

In fact, the hide property guarantees only that s cannot be obtained, given the knowledge $$$E (s)$. At the same time, we also need that s cannot be obtained, knowing the sequence $$$E (s), ..., E (s ^ d)$, which potentially contains much more information about s . The solution to this problem follows from the D-order Diffie – Hellman solution, which is used in several SNARK security proofs. (complexity of discrete logarithm. Approx. translator)

Why is this useful?

The following sections will take a closer look at how blind computations are used in SNARK. If we talk about, then the verifier has an idea of ​​the "correct" polynomial and wants to check what the prover knows. When a proving performs blind computations at a random point not known to them both, it ensures that the proving will give the wrong answer with a high probability if their polynomial is incorrect. This, in turn, is based on the Schwarz-Zippel lemma that “different polynomials are different at most points”.

Part 2. Explanation of SNARKs. Knowledge of the accepted coefficient and reliable blind calculation of polynomials