Explanation of SNARKs. Knowledge of the adopted coefficient and reliable blind calculation 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).

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

In this article, we will look at the test for the adopted coefficient and the blind computation of verifiable polynomials. Go…

In the previous article, we saw how Alice can blindly calculate hiding $$$E (P (s))$its polynomial P is of order d , at the point s belonging to Bob. We called this a “blind” calculation, since Alice does not get the value s in the calculation process.
')
However, there is something missing in this protocol. The fact that Alice can calculate $$$E (P (s))$does not guarantee that she will really send $$$E (P (s))$Bob, and not some other value.

Thus, we need a way to “get” Alice to correctly follow the protocol. In the article we will explain in detail how to achieve this. Let's first consider and explain the principle of operation of the main tool needed for this. We call it the “Knowledge of Coefficient (KC) Test).

As before, we denote by g the generator of the group G of order $$$| G | = p$where discrete logarithm is a hard task. For convenience, starting from this place we will work with our group additively, and not multiplicatively. That is, for$$ $ inline $ α ∈ F_p, α⋅g $ inline $ denotes the addition of α times the copy of g .

Coefficient knowledge test

For $$$α ∈ F ^ * _ p$will call a couple of elements $$$(a, b)$at $$$G$" $$$α$- pair "if $$$a, b ≠ 0$and $$$b = α ⋅ a$.

$$$F ^ * _ p$denotes nonzero elements $$$F_p$. This is the same as $$$Z ^ * _ p$described in the previous article .

Testing is as follows.

1. Bob picks a random number $$$α ∈ F ^ * _ p$and number $$$a ∈ G$. It calculates $$$b = α ⋅ a$
2. He sends Alice a "request" in the form of a pair $$$(a, b)$. notice, that $$$(a, b)$is an α-pair.
3. Now Alice must respond to the request with another pair. $$$(a ', b')$. This is also an α-pair.
4. Bob accepts Alice’s answer only if $$$(a ', b')$is really an α-pair (since he knows α, he can verify that $$$b '= α ⋅ a'$).
   

Now let's think about when Alice can successfully answer the call? Suppose she knows α . In this case, she can simply choose any a ' from G and calculate $$$b '= α ⋅ a'$and then return the new α-pair $$$(a ', b')$.

However, since the only information about α is contained in the expression $$$α⋅a$and the group G has a complex discrete logarithm problem, we believe that Alice will not be able to find $$$α$.

So, how can she successfully answer a query without knowing α ?

The easy way to do this is this: Alice just chooses some $$$γ∈ F ^ * _ p$and responds with a pair$$ $ inline $ (a ', b') = (γ⋅ a, γ⋅ b) $ inline $

In this case, we have:

$$$ inline $ b '= γ⋅ b = γα ⋅ a = α (γ⋅ a) = α ⋅ a' $ inline $

So a couple $$$(a ', b')$is α- pair, as required.

Note that if Alice responded using this option, she knows what the ratio of a to a ' is equal to. That is, she knows such a coefficient $$$γ$so that $$$a '= γ⋅ a$.

Knowledge of the accepted coefficient (ZPK - The Knowledge of Coefficient Assumption (KCA)) states that this is always the case:

ZPK: If Alice returns the correct answer $$$(a ', b')$to Bob's request $$$(a, b)$it is more likely regardless of the choice of bob $$$a, \ α$She knows the coefficient $$$γ$so that $$$a '= γ⋅ a$.

In the literature, this is usually called “knowledge about the accepted exponent,” since it has traditionally been used for multiplicative groups .

The Knowledge Test and Adopted Factor will be important tools in the next part of the article.

What does Alice know mean?

You may wonder how we can formulate a ZPK in a specific mathematical expression? In particular, how do we formulate the notion that "Alice knows" $$$γ$in mathematical definition?

This is done something like this: we say that besides Alice, we have another side, which we call Alice Extractor. Alice’s extractor has access to Alice’s inner state.

Now we can formulate the ZPK as follows: every time Alice successfully responds $$$α$-pair $$$(a ', b')$Alice Extractor returns $$$γ$such that $$$a '= γ⋅ a$.

The complete formal definition of a PEL is determined by the Extractor "somewhat weaker" and instead it signals the likelihood of a successful response from Alice, rather than deducing $$$γ$which is insignificant in this case

How to make a blind calculation of verifiable polynomials

Further, based on the previous material, we will develop a protocol for reliable blind calculation of polynomials, which will be defined below. The following sections (and articles) will show how this protocol can be used to build SNARKs, so have some more patience to learn SNARKs :).

Suppose that Alice has a polynomial P of order d , and Bob has a point $$$s ∈ F_p$which he chose randomly. We want to create a protocol that would allow Bob to learn $$$E (P (s))$i.e. Hiding P at s , with two additional properties:

1. Confidentiality: Alice does not recognize s , and Bob does not recognize P.
   
2. Credibility: The probability that Alice sends a value $$$E (P (s))$not for a polynomial P of order d , which is known to her, and at the same time Bob accepts it - is negligible.

This is called a blind calculation of a polynomial. The protocol in the previous article gave us only the first paragraph, but not the second. To obtain validity, we need an extended version of the knowledge about the adopted coefficient (ZPK).

The validity and confidentiality properties are useful together, because they make Alice decide which polynom P to use without seeing the value s . This, in a sense, obliges Alice to "answer with a polynomial", without seeing the "point query" s . This logic will become clearer later.

In full formal proof, some things are described more subtly. For example, the fact that Alice does get some information about s before deciding on her polynomial P. For example, she gets a hide $$$s, ..., s_d$

Advanced ZPK

ZPK, in the form that we defined above, sounds like this: if Bob gives Alice some $$$α$-pair $$$(a, b = α ⋅ a)$and then Alice generates another $$$α$-pair $$$(a ', b')$, then she knows the value of c to $$$a '= c ⋅ a$. In other words, Alice knows the relationship between a ' and a .

Now suppose that instead of one, Bob sends several to Alice $$$α$-pair $$$(a_1, b_1), ..., (a_d, b_d)$(for the same $$$α$). And now again, Alice, having received these pairs, must generate other others. $$$α$-pairs $$$(a ', b')$. It is important that Alice should do this, and she does not know the meaning $$$α$.

As described above, Alice can create $$$α$-pair in a simple way. To do this, take one of the pairs. $$$(a_i, b_i)$received from bob and multiply both elements by some $$$c ∈ F ^ * _ p$. If a $$$(a_i, b_i)$was $$$α$- pair, then $$$(c ⋅ a_i, c ⋅ b_i)$will also $$$α$-pair But can Alice generate $$$α$-pairs for more received $$$α$-pair? And is it possible to get a new one? $$$α$-pair using several received at once $$$α$-pair?

Answer: Yes. For example, Alice can choose two values. $$$c_1, c_2∈ F_p$and calculate a pair$$ $ inline $ (a ', b') = (c_1⋅ a_1 + c_2⋅ a_2, c_1⋅ b_1 + c_2⋅ b_2) $ inline $ . Simple transformations show that for any $$$a '$, non-zero, this is also $$$α$- pair:

$$$ inline $ b '= c_1⋅ b_1 + c_2⋅ b_2 = c_1α⋅ a_1 + c_2α⋅ a_2 = α (c_1 a_1 + c_2 a_2) = α⋅ a' $ inline $

In the more general case, Alice can take any linear combination of the received d pairs. To do this, select any $$$c_1, ..., c_d∈ F_p$and determine $$$(a ', b') = (Σ ^ d_ {i = 1} c_ia_i, Σ ^ d_ {i = 1} c_ib_i)$.

Note that if Alice uses this strategy to generate her $$$α$-pair, she will know some linear relationship between $$$a '$and $$$a_1, ..., a_d$. I mean, she knows $$$c_1, ..., c_d$such that $$$a '= Σ ^ d_ {i = 1} c_i⋅a_i$.

Extended ZPK claims, in essence, that this is the only way Alice can generate $$$α$-pair That way, when it is successfully generated, Alice will know a linear relationship between $$$a '$and $$$a_1, ..., a_d$. More formally, assume that G is a group of size p with generator g , described additively at the beginning of the article. Knowledge of the accepted coefficient of order d (d-) in G can be written as follows:

d-ZPK: Suppose that Bob chooses random $$$α ∈ F ^ * _ p$and $$$s ∈ F_p$and sends to Alice $$$α$-pairs$$ $ inline $ (g, α ⋅ g), (s g, α s g), ..., (s ^ d⋅ g, αs ^ d⋅ g) $ inline $ . Suppose then that Alice answers another $$$α$-pair $$$(a ', b')$. Then, with high probability, Alice knows $$$c_0, ..., c_d∈ F_p$such that $$$Σ ^ d_ {i = 0} c_is ^ i⋅ g = a '$.

D-KCA (d-ZPK) was presented in the journal Jens Groth.

Note that in $$$d-ZPK$Bob does not send a random set $$$α$-pair, and sends a set with a certain "polynomial structure". We will see the benefit of this in the protocol below.

Valid blind calculation protocol

Suppose our HS (homomorphic hiding) is a mapping $$$E (x) = x ⋅ g$for generator g of G , described above.

For simplicity, we present the protocol for this particular E :

1. Bob picks a random $$$α ∈ F ^ * _ p$and sends Alice to hide $$$g, ​​s ⋅ g, ..., s ^ ​​d⋅ g$(for $$$1, s, ..., s ^ ​​d$), and also hide$$ $ inline $ α ⋅ g, α s ⋅ g, ..., α s ^ d⋅ g $ inline $ (for $$$α, αs, ..., αs ^ d$).
2. Alice calculates $$$a = P (s) ⋅ g$and $$$b = α P (s) ⋅ g$using the items sent in the first stage, and sends them to Bob.
3. Bob checks that $$$b = α ⋅ a$and accepts the answer if and only if this equality holds.

First, note that the coefficients obtained $$$P$, $$$P (s) ⋅ g$are a linear combination $$$g, ​​s ⋅ g, ..., s ^ ​​d⋅g$and $$$α P (s) ⋅ g$, but $$$αP (s) ⋅ g$is a linear combination$$ $ inline $ α ⋅ g, α s ⋅ g, ..., α s ^ d⋅ g $ inline $ . Thus, similar to the protocol in the previous article, Alice can actually calculate these values ​​from Bob's messages for the P polynomial she knows.

Secondly, according to d-ZPK, if Alice sends $$$a, b$such that $$$b = α ⋅ a$, she almost certainly knows such $$$c_0, ..., c_d∈ F_p$, what $$$a = Σ ^ d_ {i = 0} c_is ^ i⋅ g$. In this case $$$a = P (s) ⋅ g$for polynomial $$$P (X) = Σ ^ d_ {i = 0} c_i⋅ X ^ i$famous Alice. In other words, the probability that Bob will accept the answer in step 3 and at the same time Alice does not know such a polynomial P is negligible.

Summarizing all this, using d-ZPK, we developed a protocol for reliable blind calculation of polynomials. In the following articles we will see how this mechanism is used in the construction of SNARK.

Next article: Explaining SNARKs. From calculations to polynomials, Pinocchio protocol and conjugation of elliptic curves (translation)