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

Hello, Habr! I present to you the translation of ZCash blog articles, which describe the mechanism of operation of the zero-disclosure evidence system SNARKs used in ZCash cryptocurrency (and not only).

My previous translations 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 rags to riches (translation)

In this part, we look at homomorphic hiding 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 enough 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 GS is, and then we will give an example of why it is useful and we will analyze how it is arranged.

Homomorphic concealment is not a term formally used in cryptography, and is introduced here for didactic purposes. In terms of properties, it is similar, but weaker than the well-known concept of “ obligation scheme ”. The difference is that the HS is a function that defines the argument, while the obligation takes extra randomness. As a result, homomorphic hides essentially “hide the majority of x”, while obligations “hide every x”.

HS $$ numbers x is a function satisfying the following properties:

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

A simple example of why GS is useful for zero-knowledge proofs: suppose Alice wants to prove to Bob that she knows the numbers x, y such that $$(Of course, this is not particularly interesting, to know such x and y , but this is a good example to explain the concept).

1. Alice sends $$ and $$ To bob.
2. Bob is calculating $$ of these values ​​(he can do this because $$ is HS).
3. Bob also calculates $$ and now checks if $$. He accepts Alice's proof only if equality holds.

Since the different values ​​of the arguments $$ correspond to different hides (function values $$. Note translator), Bob really only accepts proof if Alice sent the hide for$$such that $$. Bob, on the other hand, gets no value$$, since he only has access to their hides.

Yet Bob got some information about $$ and $$. For example, he may choose random$$ and check if equality holds $$ calculation $$. For this reason, the above protocol is not really a Zero-Knowledge protocol, and is used here only to explain the scheme. In fact, as we will see later, the HS is ultimately used in SNARKs to mask the verifier’s requests, not the evidential secrets.

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

Let n be some integer. When is it written$$for an integer A , it means taking the remainder of dividing A by n . For instance,$$ and $$. You can also use$$to determine the addition operation on the set {0, ..., n - 1} . Normal addition is done first, but then applied$$to the result to get the number in the set {0, ..., n - 1} . Sometimes$$is written to the right of the expression, specifying that this type of addition is used. For instance,$$. We will call the set of elements {0, ..., n - 1} together with the addition operation the group$$.

For prime p , you can use$$to determine the operation of multiplication on the set {1, ..., p - 1} , so that the result of the multiplication also always enters the set {1, ..., p - 1} . This is achieved by the usual multiplication of integers, and then applying to the result$$. For instance,$$.

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

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

1. This is a cyclic group. This means that there exists some element g in$$called a generator such that all elements $$ can be written as $$for some a from the set {0, ..., p - 2} , where$$
2. Discrete logarithms must be hard to do for $$. This means that when p is large enough and an element h from$$, then it is difficult to find an integer a from the set {0, ..., p - 2} such that$$
3. Since the degrees add up when multiplying elements with the same base, we get for a, b from the set {0, ..., p - 2} :$$

Using these properties, we now construct a homomorphic hiding that “supports addition”, which means that it can be calculated $$ knowing $$ and $$. Suppose the argument x for$$ belongs to the group $$therefore it is in the range {0, ..., p - 2} . Define$$for each such x , and prove that$$ is a GS: from the first property it follows that different $$ of $$different function values ​​will correspond. From the second property it follows that for$$it is difficult to find x . Finally, using the third property, for given$$ and $$we can calculate $$ as $$.

Blind polynomial computation

Now let's recall what the concept of a polynomial is, introduce the concept of “blind computation” of a polynomial, and how it is realized using homomorphic concealment (HS). We will see later that blind computing is the central tool in SNARK constructs.

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

Polynomials and linear combinations

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

$$

for some $$,

We can calculate the value of P point$$substituting s as X , and calculating the resulting amount:

$$

For one who knows what $$, value $$ is a linear combination of values $$ where the linear combination is understood as the "weighted sum", in the case $$ “Weights” are $$

Above we determined the HS from $$ as $$, where g is the generator of a group with a difficultly performed discrete logarithm problem. We mentioned that this GS “supports addition” in the sense that$$ can be calculated knowing $$ and $$. We also note that it “supports linear combinations”. This means that for given$$we can calculate $$This can be easily shown:
$$

Blind polynomial computation

Suppose Alice has a polynomial P of order d , and Bob has a value$$which he randomly selected. Bob wants to know$$, i.e. value of HS P at point s . There are two easy ways to do this:

• Alice sends P to Bob and he calculates$$ myself.
• Bob sends s to Alice and she figures$$ and sends it to Bob.

However, in the case of blind computing, we want Bob to find out $$ without receiving $$- which excludes the first option. And most importantly, we don’t want Alice to recognize s , which excludes the second option.

The main reason we don’t want to send $$ Bob, just consists in the fact that he is big - he contains $$elements where d ~ 2,000,000 in the current Zcash protocol. In essence, this is due to the "limited" part of SNARK.

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

1. Bob sends hiding to Alice $$
2. Alice calculates $$ of the items sent in the first step and sends $$To bob. (Alice can do this because$$ supports linear combinations, and $$ is a linear combination $$)
   

Of course, it is true that the sequence of concealments 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 proof

Please note that only hide were sent, while Alice did not recognize s , and Bob did not recognize P .

In fact, the hiding property only guarantees that s cannot be obtained, with knowledge$$. Moreover, we also need that s cannot be obtained, knowing the sequence$$, which potentially contains much more information about s . The solution to this problem follows from the Diffie-Hellman d-order solution, which is used in several SNARK security proofs. (the complexity of discrete logarithms. Note translator)

Why is this useful?

The following sections will examine in more detail how blind computing is used in SNARK. Speaking roughly, the verifier has the idea of ​​a “correct” polynomial and wants to verify that the prover knows it. When the prover performs blind calculations at a random point not known to both of them, this ensures that the prover 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 adopted coefficient and reliable blind calculation of polynomials