Skip to main content

​
FRI Verifier

In this section, we describe the implementation of the FRI verifier in S-two, continuing the example from the technical overview and prover documentation. The verifier’s role is to check that all folding steps have been performed correctly by the prover. The FriVerifier struct verifies the FRI proof generated by the prover. 
pub struct FriVerifier<MC: MerkleChannel> {
    config: FriConfig,
    // TODO(andrew): The first layer currently commits to all input polynomials. Consider allowing
    // flexibility to only commit to input polynomials on a per-log-size basis. This allows
    // flexibility for cases where committing to the first layer, for a specific log size, isn't
    // necessary. FRI would simply return more query positions for the "uncommitted" log sizes.
    first_layer: FriFirstLayerVerifier<MC::H>,
    inner_layers: Vec<FriInnerLayerVerifier<MC::H>>,
    last_layer_domain: LineDomain,
    last_layer_poly: LinePoly,
    /// The queries used for decommitment. Initialized when calling
    /// [`FriVerifier::sample_query_positions()`].
    queries: Option<Queries>,
}
The main components are:
  • config: The FriConfig containing protocol parameters.
  • first_layer: The first layer verifier, which checks Merkle decommitments for all initial circle polynomials (i.e., h0h_0, h1h_1, h2h_2).
  • inner_layers: A vector of inner layer verifiers, each corresponding to a folding round and its Merkle decommitment (i.e., two layers, corresponding to g0g_0 and g1g_1).
  • last_layer_domain: The “line” domain for the final layer polynomial (i.e., I2I_2).
  • last_layer_poly: The final “line” polynomial g2g_2 sent in clear by the prover.
  • queries: The set of queries used for spot-checking the folding identities.

​
Initialization

The commit function initializes the FriVerifier using the FRI proof, the Fiat-Shamir channel, and protocol parameters. It sets up the verifier for the query phase. 
    pub fn commit(
        channel: &mut MC::C,
        config: FriConfig,
        proof: FriProof<MC::H>,
        column_bounds: Vec<CirclePolyDegreeBound>,
    ) -> Result<Self, FriVerificationError> {
        assert!(column_bounds.is_sorted_by_key(|b| Reverse(*b)));

        MC::mix_root(channel, proof.first_layer.commitment);

        let max_column_bound = column_bounds[0];
        let column_commitment_domains = column_bounds
            .iter()
            .map(|bound| {
                let commitment_domain_log_size = bound.log_degree_bound + config.log_blowup_factor;
                CanonicCoset::new(commitment_domain_log_size).circle_domain()
            })
            .collect();

        let first_layer = FriFirstLayerVerifier {
            column_bounds,
            column_commitment_domains,
            proof: proof.first_layer,
            folding_alpha: channel.draw_secure_felt(),
        };

        let mut inner_layers = Vec::new();
        let mut layer_bound = max_column_bound.fold_to_line();
        let mut layer_domain = LineDomain::new(Coset::half_odds(
            layer_bound.log_degree_bound + config.log_blowup_factor,
        ));

        for (layer_index, proof) in proof.inner_layers.into_iter().enumerate() {
            MC::mix_root(channel, proof.commitment);

            inner_layers.push(FriInnerLayerVerifier {
                degree_bound: layer_bound,
                domain: layer_domain,
                folding_alpha: channel.draw_secure_felt(),
                layer_index,
                proof,
            });

            layer_bound = layer_bound
                .fold(FOLD_STEP)
                .ok_or(FriVerificationError::InvalidNumFriLayers)?;
            layer_domain = layer_domain.double();
        }

        if layer_bound.log_degree_bound != config.log_last_layer_degree_bound {
            return Err(FriVerificationError::InvalidNumFriLayers);
        }

        let last_layer_domain = layer_domain;
        let last_layer_poly = proof.last_layer_poly;

        if last_layer_poly.len() > (1 << config.log_last_layer_degree_bound) {
            return Err(FriVerificationError::LastLayerDegreeInvalid);
        }

        channel.mix_felts(&last_layer_poly);

        Ok(Self {
            config,
            first_layer,
            inner_layers,
            last_layer_domain,
            last_layer_poly,
            queries: None,
        })
    }
The inputs are as follows:
  • channel: The Fiat-Shamir channel for randomness and transcript hashing.
  • config: The FriConfig with protocol parameters.
  • proof: The FriProof struct containing Merkle decommitments and the last layer polynomial.
  • column_bounds: The degree bounds for each committed circle polynomial, in descending order.
At a high level, it proceeds as follows:
  1. Initializes the first layer verifier with the Merkle decommitments for circle polynomials h0h_0, h1h_1, h2h_2, their respective domains H0H_0, H1H_1, H2H_2, their degree bounds, and folding randomness λ0\lambda_0.
  2. Initializes each inner layer verifier with its Merkle decommitment, domain, degree bounds, and folding randomness. For our example:
    • The first inner FRI verifier layer will store decommitments for g0g_0, its domain I0I_0, degree bound, and folding randomness λ1\lambda_1.
    • Similarly, the second inner FRI verifier layer will store decommitments for g1g_1, its domain I1I_1, degree bound, and folding randomness λ2\lambda_2.
  3. Stores the last layer polynomial g2g_2 and its domain I2I_2.
  4. Initializes the queries as None and prepares the verifier for the query phase.
  5. Outputs the FriVerifier struct.

​
Query generation

The function sample_query_positions uses the Fiat-Shamir channel to generate random query positions for checking the folding equations. It maps each domain size to its respective query positions, ensuring that queries are adapted to the domain of each polynomial. 
    pub fn sample_query_positions(&mut self, channel: &mut MC::C) -> BTreeMap<u32, Vec<usize>> {
        let column_log_sizes = self
            .first_layer
            .column_commitment_domains
            .iter()
            .map(|domain| domain.log_size())
            .collect::<BTreeSet<u32>>();
        let max_column_log_size = *column_log_sizes.iter().max().unwrap();
        let queries = Queries::generate(channel, max_column_log_size, self.config.n_queries);
        let query_positions_by_log_size =
            get_query_positions_by_log_size(&queries, column_log_sizes);
        self.queries = Some(queries);
        query_positions_by_log_size
    }
}
It takes the following input:
  • &mut self: This will be used to update the queries in FriVerifier, which was initialized to None.
  • channel: The Fiat-Shamir channel.
At a high level, it proceeds as follows:
  1. Samples n_queries random positions on the largest domain using the channel.
  2. Returns a mapping from domain log sizes to their respective query positions using the function query_positions_by_log_size.
Suppose s=1s=1 query is sampled at P0=(x0,y0)∈H0P_0 = (x_0, y_0) \in H_0. The function computes the corresponding positions P1=π(P0)P_1 = \pi(P_0) in H1H_1 and P2=π(P1)P_2 = \pi(P_1) in H2H_2, mapping each to the correct domain size.

​
Verification

The function decommit verifies the FriVerifier after it has been initialized with the FriProof by verifying the Merkle decommitments and folding equations for all layers. It ensures that the prover’s folding steps were performed correctly and that the final polynomial is close to the expected polynomial space. 
    pub fn decommit(
        mut self,
        first_layer_query_evals: ColumnVec<Vec<SecureField>>,
    ) -> Result<(), FriVerificationError> {
        let queries = self.queries.take().expect("queries not sampled");
        self.decommit_on_queries(&queries, first_layer_query_evals)
    }

    fn decommit_on_queries(
        self,
        queries: &Queries,
        first_layer_query_evals: ColumnVec<Vec<SecureField>>,
    ) -> Result<(), FriVerificationError> {
        let first_layer_sparse_evals =
            self.decommit_first_layer(queries, first_layer_query_evals)?;
        let inner_layer_queries = queries.fold(CIRCLE_TO_LINE_FOLD_STEP);
        let (last_layer_queries, last_layer_query_evals) =
            self.decommit_inner_layers(&inner_layer_queries, first_layer_sparse_evals)?;
        self.decommit_last_layer(last_layer_queries, last_layer_query_evals)
    }
It takes the following as input:
  • mut self: The FriVerifier struct after initialization using the commit function.
  • first_layer_query_evals: The evaluations of the circle polynomials at the sampled query points.
It proceeds as follows:
  1. First Layer Verification:
    • Verifies Merkle decommitments for h0h_0, h1h_1, h2h_2 at the queried points P0P_0, P1P_1, and P2P_2, respectively.
    • Extracts the necessary evaluations for folding into the next layer.
  2. Inner Layer Verification:
    • For each inner layer, verifies Merkle decommitments for g0g_0, g1g_1 at the folded query points x0x_0 and x1x_1, respectively.
    • Checks the following two folding equations using the folding randomness and the evaluations from previous layers.
    g0(x0)=λ02⋅(h0(x0,y0)+h0(x0,−y0)2+λ0⋅h0(x0,y0)−h0(x0,−y0)2⋅y0)\begin{aligned} g_0(x_0) &= \lambda_0^2 \cdot \left( \frac{h_0(x_0,y_0) + h_0(x_0,-y_0)}{2} + \lambda_0 \cdot \frac{h_0(x_0,y_0) - h_0(x_0,-y_0)}{2 \cdot y_0} \right) \end{aligned} g1(x1)=g0(x0)+g0(−x0)2+λ1⋅g0(x0)−g0(−x0)2⋅x0+λ12⋅(h1(x1,y1)+h1(x1,−y1)2+λ1⋅h1(x1,y1)−h1(x1,−y1)2⋅y1)\begin{aligned} g_1(x_1) &= \frac{g_{0}(x_{0}) + g_{0}(-x_{0})}{2} + \lambda_1 \cdot \frac{g_{0}(x_{0}) - g_{0}(-x_{0})}{2 \cdot x_{0}} \\ &\quad + \lambda_1^2 \cdot \left( \frac{h_1(x_1,y_1) + h_1(x_1,-y_1)}{2} + \lambda_1 \cdot \frac{h_1(x_1,y_1) - h_1(x_1,-y_1)}{2 \cdot y_1} \right) \end{aligned} where P0=(x0,y0)P_0 = (x_0, y_0) and P1=π((x0,y0))=(x1,y1)P_1 = \pi((x_0, y_0)) = (x_1, y_1).
  3. Last Layer Verification:
    • Checks that the final polynomial g2g_2 matches the evaluations at the last layer’s query positions.
  4. Returns success if all checks pass; otherwise, returns an error indicating which layer failed.