1
$\begingroup$

I have been going through the lectures in ZKP MOOC here youtube series.

I am trying to understand the zk-STARKs discussed in video ZKP MOOC Lecture 8: FRI-based Polynomial Commitments and Fiat-Shamir. In this video, the lecturer discusses zk-STARK protocol. The polynomial is chosen, a merkle tree is constructed over nth roots to unity. The folding phase is run over multiple iterations to get zero degree values.

After the folding phase is done with 2 polynomials left at the end (constant values, each of degree 0), what does the verifier send as part of the query ? It has been mentioned that verifier V picks about {λ/ log (1/ρ)} entries of each folded vector and confirming each in a prescribed linear combination of relevant 2 entries of previous vector. What does this sentence mean ? What does the prover respond to the verifier query along with the authentication path ? In the same example, can someone please explain how verification is done in FRI based polynomial commitments ? I mean values/parameters exchanged during verification step ? Or please provide a reference where I can get more clear explanation.

How does the verifier verifies exactly whether folding phase has been executed by the prover correctly in FRI ?

Thank you.

$\endgroup$

1 Answer 1

3
$\begingroup$

FRI is not a polynomial commitment scheme per se, although it can be coerced into that interface. What FRI is in exact terms, is an interactive protocol for establishing that committed codeword has low degree. It works for a specific class of Reed-Solomon codes. You can think of a Reed-Solomon codeword as the set of evaluations of some low-degree polynomial $f(X)$ on a large enough domain $D$. So you can identify codewords with low-degree polynomials and vice versa.

In order for FRI to work, the domain $D$ has to have a special structure: it must be either a) a subgroup of order $n$, or b) a coset of this subgroup. The code length $n$, which coincides with the size of the domain and the cardinality of the subgroup or coset, must be a power of 2.* So $D$ can be described as $D = \{\varrho \cdot \omega^i \, | \, i \in \mathbb{Z} \}$ where $\omega$ is a primitive $n$ th root of unity (or equivalently, a generator of the subgroup of order $n$), and $\varrho$ is an offset that does not live in this group and determines the coset. The maximum degree of polynomials is $k-1 < n$, and an important quantity for determining security or query complexity is the rate $\rho = \frac{k}{n}$.

FRI is usually defined, described, and analyzed from an information-theoretical point of view, which hides the fact that Merkle trees are involved at all. In this perspective, the prover sends codewords and the verifier reads those codewords only in a small number of points of his chosing. The BCS transform shrinks communication complexity by using Merkleization in the "obvious" way. Instead of sending whole codewords, the prover now only sends their Merkle roots. Instead of reading the codewords in select locations directly, the verifier now queries the prover who responds with the codeword's value in the queried location along with a Merkle authentication path that certifies that it belongs to the tree defined by the root that was sent earlier. The verifier needs to verify that this authentication path is valid, in addition to everything he was already checking. As it simplifies explication and analysis, this answer will likewise adopt the information-theoretical point of view, i.e., before applying the BCS transform.

The FRI protocol consists of two phases, the folding phase and the query phase. We assume that the first codeword has already been sent by the prover before the protocol starts.

Folding phase. The folding phase consists of $r$ rounds. Let $\mathbf{c} = [c_i]_{i=0}^{n-1}$ be the polynomial that the receiver received in the previous round, or the very first codeword that was sent before the protocol started. In every round, the verifier sends a random scalar $\alpha$ drawn uniformly at random from a large enough field. The prover responds by sending the codeword $[2^{-1} \cdot (1 + \alpha \cdot \omega^{-i}) \cdot c_i + 2^{-1} \cdot (1 - \alpha \cdot \omega^{-i}) \cdot c_{i+n/2 \mod n}]_{i=0}^{n/2}$ where the indices wrap around modulo $n/2$. Note that this codeword corresponds to the polynomial $f_E(X) + \alpha \cdot f_O(X)$ where $f_E(X^2) = \frac{f(X) - f(-X)}{2}$ and $f_O(X^2) = \frac{f(X)+ f(-X)}{-2X}$ and where $f(X)$ is the polynomial associated with $\mathbf{c}$. So the length of the codeword drops by half, but so does the maximum degree. And the new domain has a generator $\omega^2$. This process continues for many rounds with fresh $\alpha$'s. In principle this phase can continue until the working polynomial is a constant but in practice it is beneficial to halt this phase a small number of rounds before reaching this point.

Query phase. At this point, the verifier has received a whole bunch of codewords. How does he verify that the prover computed them integrally using the right folding formula everywhere? This is where the colinearity test comes into play. The verifier samples an index $a_i$ from the range $[0;n-1]$ and let $b_i = a_i + n/2 \mod n$ and $c_i = \min(a_i, b_i)$. We can use this to test the consistency between $\mathbf{c}_0$ (the very first codeword that was sent before the folding phase) and $\mathbf{c}_1$ (the first codeword to be sent in the folding phase). The verifier queries $\mathbf{c}_0$ in $a_i$ and $b_i$, and queries $\mathbf{c}_1$ in $c_i$, and let the answers be $a_y, b_y,$ and $c_y$. If the folding was computed integrally, then the points $(\omega^{a_i}, a_y), (\omega^{b_i}, b_y), (\alpha, c_y)$ must lie on the same line. So see this, take the Lagrange interpolant between the first two points: $a_y \cdot \frac{X - \omega^{b_i}}{\omega^{a_i} - \omega^{b_i}} + b_y \cdot \frac{X - \omega^{a_i}}{\omega^{b_i} - \omega^{a_i}}$ and evaluate it in $\alpha$ (and assume wlog that $a_i < b_i$) to obtain $a_y \cdot \frac{\alpha - \omega^{b_i}}{\omega^{a_i}(1-\omega^{n/2})} + b_y \cdot \frac{\alpha - \omega^{a_i}}{-\omega^{a_i}(1 - \omega^{n/2})} = a_y \cdot \frac{\alpha \cdot \omega^{-a_i} + 1}{2} + b_y \cdot \frac{\alpha\cdot\omega^{-a_i} - 1}{2}$ which matches exactly with how the folding is defined. So the verifier tests this relation. This test shows that with some reasonable probability, $\mathbf{c}_1$ was computed correctly from $\mathbf{c}_0$. The verifier can check the same relation between $\mathbf{c}_2$ and $\mathbf{c}_1$ by reusing $c_y$: set $a_i = c_i$ and $a_y = c_y$ and compute the remaining values in the same way. In this way, one index sampled from $[0;n-1]$ percolates downwards and allows the verifier to verify the correct folding of $r-1$ pairs of codewords. Of course, the verifier needs to repeat this verifier needs to repeat this whole process $t$ times to maximize the probability of catching a cheating prover. This number $t$ of colinearity checks dominates the communication complexity of the protocol and how it is set determines (in a way that dominates over other contributing factors) the protocol's soundness.

For a more in-depth explanation I refer to the Anatomy of a STARK tutorial, part 3.

*: Some projects, such as Polygon Miden, actually allow small factors different from 2, such as 3 or even 5, but covering this case will complicate the explication.

$\endgroup$
2
  • $\begingroup$ Thank you so much $\endgroup$ Feb 16 at 4:46
  • $\begingroup$ Hi, I tried the understand the working of the protocol for one round of FRI. The example is here. The verification fails. Can you please check the example and correct it if some computation has gone wrong. I tried to check myself several times but I always fail to find the mistake. $\endgroup$ Mar 13 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.