Explanation of SNARKs. Mating elliptic curves (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).

A source

Previous articles:
')
Part 1: Explaining SNARKs. Homomorphic hiding and blind computation of polynomials (translation)
Part 2: Explaining SNARKs. Knowledge of the adopted coefficient and reliable blind calculation of polynomials (translation)
Part 3: Explaining SNARKs. From calculations to polynomials, the Pinocchio protocol and the pairing of elliptic curves (translation)

In a previous article, the Pinocchio protocol for zk-SNARK was considered. Two things remained to be disassembled: Homomorphic hiding (TOS), which supports both addition and multiplication, necessary for verification, and the transition from an interactive protocol to a non-interactive evidence system.

In this article it will be shown how using elliptic curves one can get a limited, but sufficient for our purposes, form of a HS, which supports multiplication. Further it will be shown that this limited form of the WAN is also sufficient to convert the protocol into the necessary non-interactive system.

We begin with an introduction to elliptic curves and an explanation of how they allow us to obtain the shape of the HS we need.

Elliptic curves and their pairing

Suppose p is a prime number greater than 3 and take some $$$u, v ∈ F_p$such that $$$4u ^ 3 + 27v ^ 2 ≠ 0$. Consider the equation:

$$$Y ^ 2 = X ^ 3 + u ⋅ X + v$

Elliptic curve C is a set of points. $$$(x, y)$that satisfy this equation. These curves give us an interesting way to build groups. The elements of the group will be points $$$(x, y) ∈ F ^ 2_p$which are on the curve, i.e., they satisfy the equation together with the special point O , which is necessary for technical reasons, is sometimes referred to as the “point at infinity” and serves as an element of identity, that is, the zero of the group.

You can ask "A set of points on what?". We mean the set of points with coordinates in the algebraic closure $$$F_p$. In addition, the curve has an affine and projective version. When we refer to the projective version, we also include the “point at infinity” O as an element of the curve.

Now the question is how to add up two points $$$P = (x_1, y_1), Q = (x_2, y_2)$to get the third one? The addition rule is obtained from some abstract object called the divisor class group of a curve. For our purposes, all you need to know about this group of divisor classes is that it imposes the following restriction on the definition of the addition operation: the sum of the points on any line must be zero, i.e. O

Let's consider what the rule of addition follows from this restriction. Look at the vertical line defined by the equation of the form. $$$X = c$. Suppose that this line intersects the curve at $$$P = (x_1, y_1)$. Since the equation of the curve is $$$Y ^ 2 = f (x)$, if a $$$(x1, y1)$is on a curve then there is a point $$$Q: = (x_1, - y_1)$. Moreover, since this is a vertical line, and an equation of a second order curve Y , we can be sure that these are the only points where the line and the curve intersect.



So we have the equation $$$P + Q = O$what means $$$P = - Q$In this way $$$Q$is the opposite to $$$P$in Group.

Now let's analyze the points $ inlineP $ inline and $ inlineQ $ inline, which do not have the first coordinates, i.e. $$$x_1 ≠ x_2$and see how to fold them. Draw a line through P and Q.


Since the curve is defined by a third-degree polynomial X and already crosses this (not vertical) line at two points, it is guaranteed to cross the line at the third point, which we denote $$$R = (x, y)$and does not cross the line at other points.

Therefore, we obtain $$$P + Q + R = O$what means $$$P + Q = - R$. We already know that $$$-R$is obtained from $$$R$using the turn of the second coordinate of $$$y$at $$$-y$.

Thus, the addition rule for our group is as follows: For the selected points P and Q , it is necessary to draw a line through them, and then take a “mirror” point for the third point of intersection of the line. This will be the result of addition.

We did not consider the case of adding P with itself. This is done using the line that is tangent to the curve at point P , and obtaining R, as the second point of intersection of this line with the curve.

This group is usually called $$$C (F_p)$because it consists of points on the $ inlineC $ inline curve with coordinates in $$$F_p$. But we will designate it further as $$$G_1$. For convenience, we assume that the number of elements in $$$G_1$Is a prime r different from p . This applies to many solutions, for example, on a curve that Zcash uses. In this case, any element $$$g∈ G_1$different from O generates $$$G_1$.

The smallest integer k such that r divides $$$p ^ k-1$called the degree of nesting curve. It is believed that if k is large enough, for example, at least 6, then the problem of discrete logarithm in $$$G_1$i.e. finding $$$α$and $$$g$of $$$α⋅g$is rather complicated. ( In the BN curves currently used in Zcash, $$$k = 12$).

Multiplicative group $$$F_ {p ^ k}$contains a subgroup of order r which is denoted $$$G_T$. We can see the points of the curve with coordinates in $$$F_ {p ^ k}$and not only in $$$F_p$. In accordance with the same addition rule, these points also form a group together with O , which is called $$$C (F_ {p ^ k})$. notice, that $$$C (F_ {p ^ k})$obviously contains $$$G_1$. Besides $$$G_1, C (F_ {p ^ k})$will contain an additional subgroup $$$G_2$order r (in fact, $$$r - 1$additional subgroups of order r ).

Fix the generators $$$g∈ G_1, h ∈ G_2$. It turns out that there is an effective map called Tate reduced pairing, which translates a pair of elements from $$$G_1$and $$$G_2$into the element of $$$G_T$such that

1. $$$Tate (g, h) = ξ$for generator ξ of $$$G_T$
2. For a given pair of items $$$a, b ∈ F_r$performed $$$Tate (a ⋅ g, b ⋅ h) = ξ ^ {ab}$

The definition of Tate goes a bit beyond the series of these articles and relies on concepts from algebraic geometry, more so on divisors.

In fact, Zcash pairing uses Ate optimal pairing , which is based on Tate's simplified pairing and can be calculated more efficiently than Tate .

For $$$a ∈ F_p$polynomial $$$(X- a) ^ r$takes the value zero to the degree $$$r$at point a , and nowhere else. For point $$$P∈ G_1$, divisors allow us to prove that there is a function $$$f_P$from the curve on $$$F_p$which also takes in some exact sense a zero to the power of r for P and nowhere else. $$$Tate (P, Q)$then defined as $$$f_P (Q) ^ {(p ^ k- 1) / r}$.

Here it may not be completely clear how this definition is associated with the specified properties. In fact, the proof that Tate is associated with these properties is quite complicated.

Defining$$ $ inline $ E_1 (x): = x ⋅ g, E_2 (x): = x ⋅ h, E (x): = x ⋅ ξ $ inline $ we get a weak version of the TOS, which supports both addition and multiplication: $$$E_1, E_2, E$are GEs that support addition, and knowing the hiding $$$E_1 (x), E_2 (y)$we can calculate $$$E (xy)$. In other words, if we have the “right” hiding x and y , we can get the (other) hiding xy . But for example, if we have a hide for $$$x, y, z$we won't be able to get the hide $$$xyz$.

Let's move on to discuss non-interactive evidence systems. We begin by explaining what we mean by "non-interactive."

Non-interactive evidence in the model of a common referencing string

The strongest and most intuitive definition of non-interactive evidence is probably the following: In order to prove a specific statement, the proving party sends a single message available to all parties without any prior exchange of messages, and anyone who reads this message will be convinced that the statement is true. In most cases this may not be possible to implement.

In terms of computational complexity theory, it can be shown that only languages ​​of the BPP complexity classes implement non-interactive proofs with zero disclosure in full. The type of statements that we need to prove in Zcash transactions, for example, “I know the original for the hash of this line,” corresponds to the complexity class NP , which, as we know, is much more than BPP .

We weaken the definition of non-interactive evidence in order to introduce the notion of a common referencing line - OSS (from the English CRS ). In the OSS model, before any evidence is constructed, there is an installation phase in which a line is created according to a certain random process and passed to all parties. This line is called OSS, and is then used to create and verify evidence. It is assumed that the random data used in the creation of the OSS, is unknown to either party, since knowledge of these data will allow to build false evidence.

Let's take a look at how, in the OSS model, you can convert a valid blind calculation protocol into a non-interactive evidence system. Since this protocol consists of several similar sub-protocols, it can be turned into a non-interactive evidence system in the same way.

Non-interactive calculation protocol

The non-interactive version of the calculation protocol initially consists in publishing Bob’s first message as OSS. Recall that the purpose of the protocol is to obtain homomorphic hiding $$$E (P (s))$for Alice's polynomial $$$P$for randomly selected $$$s ∈ F_p$.

Installation : Selected random $$$α ∈ F ^ * _ r, s ∈ F_r$and published by the OSS: $$$(E_1 (1), E_1 (s), ..., E_1 (s ^ d), E_2 (α), E_2 (αs), ..., E_2 (αs ^ d))$.

Proof . Alice calculates $$$a = E_1 (P (s))$and $$$b = E_2 (αP (s))$using elements of the OSS, and the fact that $$$E_1$and $$$E_2$support linear combinations.

Check : Accepting $$$x, y∈ F_p$for $$$a = E_1 (x)$and $$$b = E_2 (y)$, Bob computes $$$E (α x) = Tate (E_1 (x), E_2 (α))$and $$$E (y) = Tate (E_1 (1), E_2 (y))$, and checks their equality. (If they are equal, it means that $$$αx = y$.)

As shown in the previous sections, Alice can only create such $$$a, b$that will be checked if $$$a$is a hiding $$$P (s)$for polynomial $$$P$order d known to her. The main difference here is that Bob doesn't need to know $$$α$to test because it can use the pairing function to calculate $$$E (αx)$only from $$$E_1 (x)$and $$$E_2 (α)$. Consequently, he does not need to independently create and send the first message, and this message can simply be corrected in the OSS.

The images used were taken from this article and are used under a Creative Commons license .