Starknet FRI Verifier

The Fast Reed-Solomon Interactive Oracle Proofs of Proximity (FRI) is a cryptographic protocol that allows a prover to prove to a verifier (in an interactive, or non-interactive fashion) that a hash-based commitment (e.g. a Merkle tree of evaluations) of a vector of values represent the evaluations of a polynomial of some known degree. (That is, the vector committed is not just a bunch of uncorrelated values.) The algorithm is often referred to as a "low degree" test, as the degree of the underlying polynomial is expected to be much lower than the degree of the field the polynomial is defined over. Furthermore, the algorithm can also be used to prove the evaluation of a committed polynomial, an application that is often called FRI-PCS. We discuss both algorithms in this document, as well as how to batch multiple instances of the two algorithms.

For more information about the original construction, see Fast Reed-Solomon Interactive Oracle Proofs of Proximity. This document is about the specific instantiation of FRI and FRI-PCS as used by the StarkNet protocol.

Overview

We briefly give an overview of the FRI protocol, before specifying how it is used in the StarkNet protocol.

FRI

FRI is a protocol that works by successively reducing the degree of a polynomial, and where the last reduction is a constant polynomial of degree $0$ . Typically the protocol obtains the best runtime complexity when each reduction can halve the degree of its input polynomial. For this reason, FRI is typically described and instantiated on a polynomial of degree a power of $2$ .

If the reductions are "correct", and it takes $n$ reductions to produce a constant polynomial in the "last layer", then it is a proof that the original polynomial at "layer 0" was of degree at most $2^{n}$ .

In order to ensure that the reductions are correct, two mechanisms are used:

First, an interactive protocol is performed with a verifier who helps randomizing the halving of polynomials. In each round the prover commits to a "layer" polynomial.
Second, as commitments are not algebraic objects (as FRI works with hash-based commitments), the verifier query them in multiple points to verify that an output polynomial is consistant with its input polynomial and a random challenge. (Intuitively, the more queries, the more secure the protocol.)

Setup

To illustrate how FRI works, one can use sagemath with the following setup:

# We use the starknet field (https://docs.starknet.io/architecture-and-concepts/cryptography/p-value/)
starknet_prime = 2^251 + 17*2^192 + 1
starknet_field = GF(starknet_prime)
polynomial_ring.<x> = PolynomialRing(starknet_field)

# find generator of the main group
gen = starknet_field.multiplicative_generator()
assert gen == 3
assert starknet_field(gen)^(starknet_prime-1) == 1 # 3^(order-1) = 1

# lagrange theorem's gives us the orders of all the multiplicative subgroups
# which are the divisors of the main multiplicative group order (which, remember, is p - 1 as 0 is not part of it)
# p - 1 = 2^192 * 5 * 7 * 98714381 * 166848103
multiplicative_subgroup_order = starknet_field.order() - 1
assert list(factor(multiplicative_subgroup_order)) == [(2, 192), (5, 1), (7, 1), (98714381, 1), (166848103, 1)]

# find generator of subgroup of order 2^192
# the starknet field has high 2-adicity, which is useful for FRI and FFTs
# (https://www.cryptologie.net/article/559/whats-two-adicity)
gen2 = gen^( (starknet_prime-1) / (2^192) )
assert gen2^(2^192) == 1

# find generator of a subgroup of order 2^i for i <= 192
def find_gen2(i):
    assert i >= 0
    assert i <= 192
    return gen2^( 2^(192-i) )

assert find_gen2(0)^1 == 1
assert find_gen2(1)^2 == 1
assert find_gen2(2)^4 == 1
assert find_gen2(3)^8 == 1

Reduction

folding

A reduction in the FRI protocol is obtained by interpreting an input polynomial $p$ as a polynomial of degree $2 n$ and splitting it into two polynomials $g$ and $h$ of degree $n$ such that $p (x) = g (x^{2}) + x h (x^{2})$ .

Then, with the help of a verifier's random challenge $ζ$ , we can produce a random linear combination of these polynomials to obtain a new polynomial $g (x) + ζ h (x)$ of degree $n$ :

def split_poly(p, remove_square=True):
    assert (p.degree()+1) % 2 == 0
    g = (p + p(-x))/2 # <---------- nice trick!
    h = (p - p(-x))//(2 * x) # <--- nice trick!
    # at this point g and h are still around the same degree of p
    # we need to replace x^2 by x for FRI to (as we want to halve the degrees!)
    if remove_square:
        g = g.parent(g.list()[::2]) # <-- (using python's <!--CODE_BLOCK_33--> syntax)
        h = h.parent(h.list()[::2])
        assert g.degree() == h.degree() == p.degree() // 2
        assert p(7) == g(7^2) + 7 * h(7^2)
    else:
        assert g.degree() == h.degree() == p.degree() - 1
        assert p(7) == g(7) + 7 * h(7)
    return g, h

We can look at the following example to see how a polynomial of degree $7$ is reduced to a polynomial of degree $0$ in 3 rounds:

# p0(x) = 1 + 2x + 3x^2 + 4x^3 + 5x^4 + 6x^5 + 7x^6 + 8x^7
# degree 7 means that we'll get ceil(log2(7)) = 3 rounds (and 4 layers)
p0 = polynomial_ring([1, 2, 3, 4, 5, 6, 7, 8]) 

# round 1: moves from degree 7 to degree 3
h0, g0 = split_poly(p0)
assert h0.degree() == g0.degree() == 3
zeta0 = 3 # <-------------------- the verifier would pick a random zeta
p1 = h0 + zeta0 * g0 # <--------- the prover would send a commitment of p1
assert p0(zeta0) == p1(zeta0^2) # <- sanity check

# round 2: reduces degree 3 to degree 1
h1, g1 = split_poly(p1)
assert g1.degree() == h1.degree() == 1
zeta1 = 12 # <------------ the verifier would pick a random zeta
p2 = h1 + zeta1 * g1 # <-- the prover would send a commitment of p2
assert p1(zeta1) == p2(zeta1^2)
h2, g2 = split_poly(p2)
assert h2.degree() == g2.degree() == 0

# round 3: reduces degree 1 to degree 0
zeta2 = 3920 # <---------- the verifier would pick a random zeta
p3 = h2 + zeta2 * g2 # <-- the prover could send p3 in the clear
assert p2(zeta2) == p3
assert p3.degree() == 0

Queries

queries

In the real FRI protocol, each layer's polynomial would be sent using a hash-based commitment (e.g. a Merkle tree of its evaluations over a large domain). As such, the verifier must ensure that each commitment consistently represent the proper reduction of the previous layer's polynomial. To do that, they "query" commitments of the different polynomials of the different layers at points/evaluations. Let's see how this works.

Given a polynomial $p_{0} (x) = g_{0} (x^{2}) + x h_{0} (x^{2})$ and two of its evaluations at some points $v$ and $- v$ , we can see that the verifier can recover the two halves by computing:

$g_{0} (v^{2}) = \frac{p_{0} (v) + p_{0} (- v)}{2}$
$h_{0} (v^{2}) = \frac{p_{0} (v) - p_{0} (- v)}{2 v}$

Then, the verifier can compute the next layer's evaluation at $v^{2}$ as:

p_{1} (v^{2}) = g_{0} (v^{2}) + ζ_{0} h_{0} (v^{2})

We can see this in our previous example:

# first round/reduction
v = 392 # <-------------------------------------- fake sample a point
p0_v, p0_v_neg = p0(v), p0(-v) # <--------------- the 2 queries we need
g0_square = (p0_v + p0_v_neg)/2
h0_square = (p0_v - p0_v_neg)/(2 * v)
assert p0_v == g0_square + v * h0_square # <------ sanity check

In practice, to check that the evaluation on the next layer's polynomial is correct, the verifier would "query" the prover's commitment to the polynomial. These queries are different from the FRI queries (which enforce consistency between layers of reductions), they are evaluation queries or commitment queries and result in practice in the prover providing a Merkle membership proof (also called decommitment in this specification) to the committed polynomial.

As we already have an evaluation of $v^{2}$ of the next layer's polynomial $p_{1}$ , we can simply query the evaluation of $p_{1} (- v^{2})$ to continue the FRI query process on the next layer, and so on:

p1_v = p1(v^2) # <-------------------------------- query on the next layer
assert g0_square + zeta0 * h0_square == p1_v # <--- the correctness check

# second round/reduction
p1_v_neg = p1(-v^2) # <-- the 1 query we need
g1_square = (p1_v + p1_v_neg)/2 # g1(v^4)
h1_square = (p1_v - p1_v_neg)/(2 * v^2) # h1(v^4)
assert p1_v == g1_square + v^2 * h1_square # p1(v^2) = g1(v^4) + v^2 * h1(v^4)
p2_v = p2(v^4) # <-- query the next layer
assert p2(v^4) == g1_square + zeta1 * h1_square # p2(v^4) = g1(v^4) + zeta1 * h1(v^4)

# third round/reduction
p2_v_neg = p2(-v^4) # <-- the 1 query we need
g2_square = (p2_v + p2_v_neg)/2 # g2(v^8)
h2_square = (p2_v - p2_v_neg)/(2 * v^4) # h2(v^8)
assert p2_v == g2_square + v^4 * h2_square # p2(v^4) = g2(v^8) + v^4 * h2(v^8)
assert p3 == g2_square + zeta2 * h2_square # we already received p3 at the end of the protocol

Skipping FRI layers

skipped layers

Section 3.11.1 "Skipping FRI Layers" of the ethSTARK paper describes an optimization which skips some of the layers/rounds. The intuition is the following: if we removed the first round commitment (to the polynomial $p_{1}$ ), then the verifier would not be able to:

query $p_{1} (v^{2})$ to verify that layer
query $p 1 (- v^{2})$ to continue the protocol and get $g_{1}, h_{1}$

The first point is fine, as there's nothing to check the correctness of. To address the second point, we can use the same technique we use to compute $p 1 (v^{2})$ . Remember, we needed $p_{0} (v)$ and $p_{0} (- v)$ to compute $g_{0} (v^{2})$ and $h_{0} (v^{2})$ . But to compute $g_{0} (- v^{2})$ and $h_{0} (- v^{2})$ , we need the quadratic residues of $- v^{2}$ , that is $w$ , such that $w^{2} = - v^{2}$ , so that we can compute $g_{0} (- v^{2})$ and $h_{0} (- v^{2})$ from $p_{0} (w)$ and $p_{0} (- w)$ .

We can easily compute them by using $τ$ (tau), the generator of the subgroup of order $4$ :

tau = find_gen2(2)
assert tau.multiplicative_order() == 4

# so now we can compute the two roots of -v^2 as
assert (tau * v)^2 == -v^2
assert (tau^3 * v)^2 == -v^2

# and when we query p2(v^4) we can verify that it is correct
# if given the evaluations of p0 at v, -v, tau*v, tau^3*v
p0_tau_v = p0(tau * v)
p0_tau3_v = p0(tau^3 * v)
p1_v_square = (p0_v + p0_v_neg)/2 + zeta0 * (p0_v - p0_v_neg)/(2 * v)
p1_neg_v_square = (p0_tau_v + p0_tau3_v)/2 + zeta0 * (p0_tau_v - p0_tau3_v)/(2 * tau * v)
assert p2(v^4) == (p1_v_square + p1_neg_v_square)/2 + zeta1 * (p1_v_square - p1_neg_v_square)/(2 * v^2)

Last Layer Optimization

Section 3.11.2 "FRI Last Layer" of the ethSTARK paper describes an optimization which stops at an earlier round. We show this here by removing the last round.

At the end of the second round we imagine that the verifier receives the coefficients of $p_{2}$ ( $h_{2}$ and $g_{2}$ ) directly:

p2_v = h2 + v^4 * g2 # they can then compute p2(v^4) directly
assert g1_square + zeta1 * h1_square == p2_v # and then check correctness

Commitments

Commitments used in this specification are Merkle tree commitments of evaluations of a polynomial. In other words, the leaves of the Merkle tree are evaluations of a polynomial at distinct points.

We use a coset to evaluate the polynomial at the different points. This is for two reasons:

In FRI we can increase the size of the evaluated domain in the commitments, in order to decrease the number of queries needed to ensure high bit-security. (TODO: how do cosets help us here?)
As used in Starknet STARK (TODO: link to the STARK verifier specification), the layer 0 polynomial has to be computed as a rational polynomial that would lead to division by zero issues if evaluated in the original evaluation domain. As such we take a coset to avoid this issue.

As with what we specify in the rest of this document, we produce a coset of the same size as the evaluation domain (the domain which is used to produce the layer 0 polynomial in the Starknet STARK protocol).

# if we evaluate the polynomial on a set of size 8 (so the blowup factor is 1)
g = find_gen2(log(8,2))

coset = [3 * g^i for i in range(8)] 
poly8_evals = [p0(x) for x in coset] # <-- we would merklelify this as statement

FRI-PCS

Given a polynomial $f$ and an evaluation point $a$ , a prover who wants to prove that $f (a) = b$ can prove the related statement for some quotient polynomial $q$ of degree $d e g (f) - 1$ :

\frac{f (x) - b}{x - a} = q (x)

(This is because if $f (a) = b$ then $a$ should be a root of $f (x) - b$ and thus the polynomial can be factored in this way.)

Specifically, FRI-PCS proves that they can produce such a (commitment to a) polynomial $q$ .

Aggregating Multiple FRI Proofs

To prove that two polynomials $a$ and $b$ exist and are of degree at most $d$ , a prove simply prove that a random linear combination of $a$ and $b$ exists and is of degree at most $d$ .

TODO: what if the different polynomials are of different degrees?

TODO: we do not make use of aggregation here, the way the first layer polynomial is created is sort of transparent here, is it still worth having this section?

Protocol

The FRI protocol is split into two phases:

Commit phase
Query phase

Commit Phase

This should basically just absorb the commitments of every layer sent by the prover (potentially skipping layers)

#[derive(Drop, Copy, PartialEq, Serde)]
struct TableCommitmentConfig {
    n_columns: felt252, // TODO: gets divided by 2 at every step in FRI?
    vector: VectorCommitmentConfig,
}
struct VectorCommitmentConfig {
    height: felt252, // TODO: ?
    n_verifier_friendly_commitment_layers: felt252, // TODO: ?
}

The layer 0 polynomial is not part of the protocol, we assume that it comes from somewhere and that we can query evaluations of it in a coset $3 \cdot ω_{e}$ where $ω_{e}$ is the generator of the evaluation domain. In the Starknet STARK protocol it represents a blown up evaluation domain, that is, an evaluation domain that is a larger power of 2 than the evaluation domain used in the protocol.

A FRI proof looks like the following:

struct FriUnsentCommitment {
    // Array of size n_layers - 1 containing unsent table commitments for each inner layer.
    inner_layers: Span<felt252>,
    // Array of size 2**log_last_layer_degree_bound containing coefficients for the last layer
    // polynomial.
    last_layer_coefficients: Span<felt252>,
}

We process it in the following way:

Enforce that the first layer has a step size of 0 (cfg.fri_step_sizes[0] == 0). (Note that this is mostly to make sure that the prover is following the protocol correctly, as the second layer is never skipped in this standard.)
Go through each commitment in order in the inner_layers field and perform the following:
Absorb the commitment using the channel.
Produce a random challenge.
Absorb the last_layer_coefficients with the channel.
Check that the last layer's degree is correct (according to the configuration log_last_layer_degree_bound, see the Configuration section): 2^cfg.log_last_layer_degree_bound == len(unsent_commitment.last_layer_coefficients).
return all the random challenges.

Query Phase

FRI queries are generated once, and then refined through each reduction of the FRI protocol. The number of queries that is pseudo-randomly generated is based on configuration.

Each FRI query is composed of the following fields:

index: the index of the query in the layer's evaluations. Note that this value needs to be shifted before being used as a path in a Merkle tree commitment.
y_value: the evaluation of the layer's polynomial at the queried point.
x_inv_value: the inverse of the point at which the layer's polynomial is evaluated. This value is derived from the index as explained in the next subsection.

struct FriLayerQuery {
    index: felt252,
    y_value: felt252,
    x_inv_value: felt252,
}

That is, we should have for each FRI query for the layer $i + 1$ the following identity:

p_{i + 1} (1 / x_inv_value) = y_value

Or in terms of commitment, that the decommitment at path the path behind index is y_value.

See the Converting A Query to a Path section of the Merkle tree specification for more details.

Generating The First Queries

The generation of each FRI query goes through the same process:

Sample a random challenge from the channel.
Truncate the challenge to obtain the lower 128-bit chunk.
Reduce it modulo the size of the evaluation domain.

Finally, when all FRI queries have been generated, they are sorted in ascending order.

TODO: include how we provide the y_value and how we verify the first layer's evaluations still

TODO: also talk about how the first query is fixed to move away from the coset

Converting A Query To An Evaluation Point

A query $q$ (a value within $[0, 2^{n_{e}}]$ for $n_{e}$ the log-size of the blown-up evaluation domain) can be converted to an evaluation point in the following way.

First, compute the bit-reversed exponent:

q^{'} = bit_reverse (q \cdot 2^{64 - n_{e}})

Then compute the element of the blown-up evaluation domain in the coset (with $ω_{e}$ the generator of the evaluation domain):

3 \cdot ω_{e}^{q^{'}}

TODO: explain why not just do $3 \cdot ω_{e} q$

Verify A Layer's Query

TODO: refer to the section on the first layer evaluation stuff (external dependency)

Besides the last layer, each layer verification of a query happens by simply decommiting a layer's queries.

table_decommit(commitment, paths, leaves_values, witness, settings);

To verify the last layer's query, as the last layer polynomial is received in clear, simply evaluate it at the queried point 1/fri_layer_query.x_inv_value and check that it matches the expected evaluation fri_layer_query.y_value.

TODO: As explained in the section on Merkle Tree Decommitment, witness leaves values have to be given as well.

TODO: link to section on merkle tree

Computing the next layer's queries

Each reduction will produce queries to the next layer, which will expect specific evaluations.

The next queries are derived as:

index: index / coset_size
point: point^coset_size
value: FRI formula below

where coset_size is 2, 4, 8, or 16 depending on the layer (but always 2 for the first layer).

TODO: explain the relation between coset_size and the step size. coset_size = 2^step_size

The next evaluations expected at the queried layers are derived as:

Queries between layers verify that the next layer $p_{i + j}$ is computed correctly based on the currently layer $p_{i}$ . The next layer is either the direct next layer $p_{i + 1}$ or a layer further away if the configuration allows layers to be skipped. Specifically, each reduction is allowed to skip 0, 1, 2, or 3 layers (see the MAX_FRI_STEP constant).

TODO: why MAX_FRI_STEP=3?

no skipping:

given a layer evaluations at $\pm v$ , a query without skipping layers work this way:
we can compute the next layer's expected evaluation at $v^{2}$ by computing $p_{i + 1} (v^{2}) = \frac{p_{i} (v) + p_{i} (- v)}{2} + ζ_{i} \cdot \frac{p_{i} (v) - p_{i} (- v)}{2 v}$
we can then ask the prover to open the next layer's polynomial at that point and verify that it matches

1 skipping with $ω_{4}$ the generator of the 4-th roots of unity (such that $ω_{4}^{2} = - 1$ ):

$p_{i + 1} (v^{2}) = \frac{p_{i} (v) + p_{i} (- v)}{2} + ζ_{i} \cdot \frac{p_{i} (v) - p_{i} (- v)}{2 v}$
$p_{i + 1} (- v^{2}) = \frac{p_{i} (ω_{4} v) + p_{i} (- ω_{4} v)}{2} + ζ_{i} \cdot \frac{p_{i} (v) - p_{i} (- ω_{4} v)}{2 \cdot ω_{4} \cdot v}$
$p_{i + 2} (v^{4}) = \frac{p_{i + 1} (v^{2}) + p_{i + 1} (- v^{2})}{2} + ζ_{i}^{2} \cdot \frac{p_{i} (v^{2}) - p_{i} (- v^{2})}{2 \cdot v^{2}}$

as you can see, this requires 4 evaluations of p_{i} at $v$ , $- v$ , $ω_{4} v$ , $- ω_{4} v$ .

2 skippings with $ω_{8}$ the generator of the 8-th roots of unity (such that $ω_{8}^{2} = ω_{4}$ and $ω_{8}^{4} = - 1$ ):

$p_{i + 1} (v^{2}) = \frac{p_{i} (v) + p_{i} (- v)}{2} + ζ_{i} \cdot \frac{p_{i} (v) - p_{i} (- v)}{2 v}$
$p_{i + 1} (- v^{2}) = \frac{p_{i} (ω_{4} v) + p_{i} (- ω_{4} v)}{2} + ζ_{i} \cdot \frac{p_{i} (v) - p_{i} (- ω_{4} v)}{2 \cdot ω_{4} \cdot v}$
$p_{i + 1} (ω_{4} v^{2}) = \frac{p_{i} (ω_{8} v) + p_{i} (- ω_{8} v)}{2} + ζ_{i} \cdot \frac{p_{i} (ω_{8} v) - p_{i} (- ω_{8} v)}{2 ω_{8} v}$
$p_{i + 1} (- ω_{4} v^{2}) = \frac{p_{i} (ω_{8}^{3} v) + p_{i} (- ω_{8}^{3} v)}{2} + ζ_{i} \cdot \frac{p_{i} (ω_{8}^{3} v) - p_{i} (- ω_{8}^{3} v)}{2 \cdot ω_{8}^{3} \cdot v}$
$p_{i + 2} (v^{4}) = \frac{p_{i + 1} (v^{2}) + p_{i + 1} (- v^{2})}{2} + ζ_{i}^{2} \cdot \frac{p_{i + 1} (v^{2}) - p_{i + 1} (- v^{2})}{2 \cdot v^{2}}$
$p_{i + 2} (- v^{4}) = \frac{p_{i + 1} (ω_{4} v^{2}) + p_{i + 1} (- ω_{4} v^{2})}{2} + ζ_{i}^{2} \cdot \frac{p_{i + 1} (ω_{4} v^{2}) - p_{i + 1} (- ω_{4} v^{2})}{2 \cdot ω_{4} v^{2}}$
$p_{i + 3} (v^{8}) = \frac{p_{i + 2} (v^{4}) + p_{i + 2} (- v^{4})}{2} + ζ_{i}^{4} \cdot \frac{p_{i + 2} (v^{4}) - p_{i + 2} (- v^{4})}{2 \cdot v^{4}}$

as you can see, this requires 8 evaluations of p_{i} at $v$ , $- v$ , $ω_{4} v$ , $- ω_{4} v$ , $ω_{8} v$ , $- ω_{8} v$ , $ω_{8}^{3} v$ , $- ω_{8}^{3} v$ .

3 skippings with $ω_{16}$ the generator of the 16-th roots of unity (such that $ω_{16}^{2} = ω_{8}$ , $ω_{16}^{4} = ω_{4}$ , and $ω_{16}^{8} = - 1$ ):

$p_{i + 1} (v^{2}) = \frac{p_{i} (v) + p_{i} (- v)}{2} + ζ_{i} \cdot \frac{p_{i} (v) - p_{i} (- v)}{2 v}$
$p_{i + 1} (- v^{2}) = \frac{p_{i} (ω_{4} v) + p_{i} (- ω_{4} v)}{2} + ζ_{i} \cdot \frac{p_{i} (v) - p_{i} (- ω_{4} v)}{2 \cdot ω_{4} \cdot v}$
$p_{i + 1} (ω_{4} v^{2}) = \frac{p_{i} (ω_{8} v) + p_{i} (- ω_{8} v)}{2} + ζ_{i} \cdot \frac{p_{i} (ω_{8} v) - p_{i} (- ω_{8} v)}{2 ω_{8} v}$
$p_{i + 1} (- ω_{4} v^{2}) = \frac{p_{i} (ω_{8}^{3} v) + p_{i} (- ω_{8}^{3} v)}{2} + ζ_{i} \cdot \frac{p_{i} (ω_{8}^{3} v) - p_{i} (- ω_{8}^{3} v)}{2 \cdot ω_{8}^{3} \cdot v}$
$p_{i + 1} (ω_{8} v^{2}) = \frac{p_{i} (ω_{1} 6 v) + p_{i} (- ω_{1} 6 v)}{2} + ζ_{i} \cdot \frac{p_{i} (ω_{1} 6 v) - p_{i} (- ω_{1} 6 v)}{2 ω_{1} 6 v}$
$p_{i + 1} (- ω_{8} v^{2}) = \frac{p_{i} (ω_{1} 6^{5} v) + p_{i} (- ω_{1} 6^{5} v)}{2} + ζ_{i} \cdot \frac{p_{i} (ω_{1} 6^{5} v) - p_{i} (- ω_{1} 6^{5} v)}{2 ω_{1} 6^{5} v}$
$p_{i + 1} (ω_{8}^{3} v^{2}) = \frac{p_{i} (ω_{1} 6^{3} v) + p_{i} (- ω_{1} 6^{3} v)}{2} + ζ_{i} \cdot \frac{p_{i} (ω_{1} 6^{3} v) - p_{i} (- ω_{1} 6^{3} v)}{2 ω_{1} 6^{3} v}$
$p_{i + 1} (- ω_{8}^{3} v^{2}) = \frac{p_{i} (ω_{1} 6^{7} v) + p_{i} (- ω_{1} 6^{7} v)}{2} + ζ_{i} \cdot \frac{p_{i} (ω_{1} 6^{7} v) - p_{i} (- ω_{1} 6^{7} v)}{2 ω_{1} 6^{7} v}$
$p_{i + 2} (v^{4}) = \frac{p_{i + 1} (v^{2}) + p_{i + 1} (- v^{2})}{2} + ζ_{i}^{2} \cdot \frac{p_{i + 1} (v^{2}) - p_{i + 1} (- v^{2})}{2 \cdot v^{2}}$
$p_{i + 2} (- v^{4}) = \frac{p_{i + 1} (ω_{4} v^{2}) + p_{i + 1} (- ω_{4} v^{2})}{2} + ζ_{i}^{2} \cdot \frac{p_{i + 1} (ω_{4} v^{2}) - p_{i + 1} (- ω_{4} v^{2})}{2 \cdot ω_{4} v^{2}}$
$p_{i + 2} (ω_{4} v^{4}) = \frac{p_{i + 1} (ω_{8} v^{2}) + p_{i + 1} (- ω_{8} v^{2})}{2} + ζ_{i}^{2} \cdot \frac{p_{i + 1} (ω_{8} v^{2}) - p_{i + 1} (- ω_{8} v^{2})}{2 \cdot ω_{8} \cdot v^{2}}$
$p_{i + 2} (- ω_{4} v^{4}) = \frac{p_{i + 1} (ω_{8}^{3} v^{2}) + p_{i + 1} (- ω_{8}^{3} v^{2})}{2} + ζ_{i}^{2} \cdot \frac{p_{i + 1} (ω_{8}^{3} v^{2}) - p_{i + 1} (- ω_{8}^{3} v^{2})}{2 \cdot ω_{8}^{3} v^{2}}$
$p_{i + 3} (v^{8}) = \frac{p_{i + 2} (v^{4}) + p_{i + 2} (- v^{4})}{2} + ζ_{i}^{4} \cdot \frac{p_{i + 2} (v^{4}) - p_{i + 2} (- v^{4})}{2 \cdot v^{4}}$
$p_{i + 3} (- v^{8}) = \frac{p_{i + 2} (ω_{4} v^{4}) + p_{i + 2} (- ω_{4} v^{4})}{2} + ζ_{i}^{4} \cdot \frac{p_{i + 2} (ω_{4} v^{4}) - p_{i + 2} (- ω_{4} v^{4})}{2 \cdot ω_{4} v^{4}}$
$p_{i + 4} (v^{1} 6) = \frac{p_{i + 3} (v^{8}) + p_{i + 3} (- v^{8})}{2} + ζ_{i}^{8} \cdot \frac{p_{i + 3} (v^{8}) - p_{i + 3} (- v^{8})}{2 \cdot v^{8}}$

as you can see, this requires 16 evaluations of p_{i} at $v$ , $- v$ , $ω_{4} v$ , $- ω_{4} v$ , $ω_{8} v$ , $- ω_{8} v$ , $ω_{8}^{3} v$ , $- ω_{8}^{3} v$ , $ω_{1} 6 v$ , $- ω_{1} 6 v$ , $ω_{1} 6^{3} v$ , $- ω_{1} 6^{3} v$ , $ω_{1} 6^{5} v$ , $- ω_{1} 6^{5} v$ , $ω_{7} v$ , $- ω_{7} v$ .

TODO: reconcile with section on the differences with vanilla FRI

TODO: reconcile with constants used for elements and inverses chosen in subgroups of order $2^{i}$ (the $ω$ s)

Proof of work

In order to increase the cost of attacks on the protocol, a proof of work is added at the end of the commitment phase.

Given a 32-bit hash digest and a difficulty target of proof_of_work_bits, verify the 64-bit proof of work nonce by doing the following:

Produce a init_hash = hash_n_bytes(0x0123456789abcded || digest || proof_of_work_bits) (TODO: endianness)
Produce a hash = hash_n_bytes(init_hash || nonce) (TODO: endianness)
Enforce that the 128-bit high bits of hash start with proof_of_work_bits zeros (where proof_of_work_bits is enforced to be between 20 and 50 as discussed in the General Configuration section).

Full Protocol

The FRI flow is split into four main functions. The only reason for doing this is that verification of FRI proofs can be computationally intensive, and users of this specification might want to split the verification of a FRI proof in multiple calls.

The four main functions are:

fri_commit, which returns the commitment to every layers of the FRI proof.
fri_verify_initial, which returns the initial set of queries to verify the first reduction (Which is special as explained in the Notable Differences With Vanilla FRI section).
fri_verify_step, which takes a set of queries and returns another set of queries.
fri_verify_final, which takes the final set of queries and the last layer coefficients and returns the final result.

To retain context, functions pass around two objects:

struct FriVerificationStateConstant {
    // the number of layers in the FRI proof (including skipped layers) (TODO: not the first)
    n_layers: u32, 
    // commitments to each layer (excluding the first, last, and any skipped layers)
    commitment: Span<TableCommitment>, 
    // verifier challenges used to produce each (non-skipped) layer polynomial (except the first)
    eval_points: Span<felt252>, 
    // the number of layers to skip for each reduction
    step_sizes: Span<felt252>, 
    // the hash of the polynomial of the last layer
    last_layer_coefficients_hash: felt252, 
}
struct FriVerificationStateVariable {
    // a counter representing the current layer being verified
    iter: u32, 
    // the FRI queries for each (non-skipped) layer
    queries: Span<FriLayerQuery>, 
}

We give more detail to each function below.

fri_commit(channel).

Take a channel with a prologue (See the Channel section). A prologue contains any context relevant to this proof.
Produce the FRI commits according to the Commit Phase section.
Produce the proof of work according to the Proof of Work section.
Generate n_queries queries in the eval_domain_size according to the Generating Queries section.
Convert the queries to evaluation points following the Converting A Query To An Evaluation Point section, producing points.
Evaluate the first layer at the queried points using the external dependency (see External Dependencies section), producing values.
Produce the fri_decommitment as FriDecommitment { values, points }.

fri_verify_initial(queries, fri_commitment, decommitment). Takes the FRI queries, the FRI commitments (each layer's committed polynomial), as well as the evaluation points and their associated evaluations of the first layer (in decommitment).

Enforce that for each query there is a matching derived evaluation point and evaluation at that point on the first layer contained in the given decommitment.
Enforce that last layer has the right number of coefficients as expected by the FRI configuration (see the FRI Configuration section).
Compute the first layer of queries as FriLayerQuery { index, y_value, x_inv_value: 3 / x_value } for each x_value and y_value given in the decommitment
Initialize and return the two state objects

(
    FriVerificationStateConstant {
        n_layers: config.n_layers - 1,
        commitment: fri_commitment.inner_layers, // the commitments
        eval_points: fri_commitment.eval_points, // the challenges
        step_sizes: config.fri_step_sizes[1:], // the number of reduction at each steps
        last_layer_coefficients_hash: hash_array(last_layer_coefficients),
    },
    FriVerificationStateVariable { iter: 0, queries: fri_queries }
)

fri_verify_step(stateConstant, stateVariable, witness, settings).

enforce that stateVariable.iter <= stateConstant.n_layers
compute the next layer queries (TODO: link to section on that)
verify the queries
increment the iter counter
return the next queries and the counter

fri_verify_final(stateConstant, stateVariable, last_layer_coefficients).

enforce that the counter has reached the last layer from the constants (iter == n_layers)
enforce that the last_layer_coefficient matches the hash contained in the state (TODO: only relevant if we created that hash in the first function)
manually evaluate the last layer's polynomial at every query and check that it matches the expected evaluations.

fn fri_verify_final(
    stateConstant: FriVerificationStateConstant,
    stateVariable: FriVerificationStateVariable,
    last_layer_coefficients: Span<felt252>,
) -> (FriVerificationStateConstant, FriVerificationStateVariable) {
    assert(stateVariable.iter == stateConstant.n_layers, 'Fri final called at wrong time');
    assert(
        hash_array(last_layer_coefficients) == stateConstant.last_layer_coefficients_hash,
        'Invalid last_layer_coefficients'
    );

    verify_last_layer(stateVariable.queries, last_layer_coefficients);

    (
        stateConstant,
        FriVerificationStateVariable { iter: stateVariable.iter + 1, queries: array![].span(), }
    )
}

Overview

FRI

Setup

Reduction

Queries

Skipping FRI layers

Last Layer Optimization

Commitments

FRI-PCS

Aggregating Multiple FRI Proofs

Notable Differences With Vanilla FRI

External Dependencies

Hash Functions

Channel

Evaluations of the first FRI layer

Constants

Protocol constants

FRI constants

TODO: Step generators

Configuration

General configuration

FRI configuration