ETAAcademy-ZKMeme: 45. Plonky3

title

Plonky3: A Deep Dive into Scalable zk-SNARKs of FRI and UniStark

Plonky3 is an advanced zero-knowledge succinct non-interactive argument of knowledge (zk-SNARK) system designed for scalable and efficient cryptographic proof generation. At its core, Plonky3 aims to make zk-SNARKs more scalable by introducing many key components, two of which are FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) that streamlines the polynomial commitment process, and UniStark, a recursive proving system that allows for faster verification and ensures the scalability of zero-knowledge proofs.

1.FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) in Plonky3

In Plonky3, FRI optimizes the commitment scheme using techniques such as polynomial folding, batching, and low-degree extensions (LDE), all of which significantly enhance performance and minimize computation overhead during proof generation. Let's break down the purpose and operations of the main files:

two_adic_pcs.rs: This file handles polynomials aligned with powers of two. It implements the Polynomial Commitment Scheme (PCS) trait, providing the necessary functions for committing, opening, and verifying polynomial data. The main methods—commit, open, and verify—are foundational to the FRI process and allow the prover and verifier to efficiently interact with polynomial commitments.
proof.rs: This file defines the structure of the proof objects generated by the prover during different phases of the FRI protocol, including the commit phase and query-answering phase. The structures in proof.rs are essential for maintaining the integrity of the proof as it is passed between the prover and verifier.
verifier.rs: In the verifier.rs file, the most important function here is verify_query, which handles the verification of the queries returned by the prover, ensuring that the commitments and proofs align with the expected results.
fold_even_odd.rs: Previously used in Plonky3’s folding process for polynomials, this file has been deprecated in recent versions.
config.rs: This configuration file holds key parameters for the FRI protocol, such as FriConfig and FriGenericConfig. These configurations include critical values like the blowup factor (used in low-degree extensions), the number of queries, and the bits required for proof-of-work. Additionally, mmcs (Merkle Matrix Commitment Scheme) is defined here, which is a customized commitment system used for batch polynomial commitments.

1.1 Polynomial Commitment Scheme (PCS) in FRI: Code Structure

The Polynomial Commitment Scheme (PCS) shows the code structure implemented in FRI, which handles matrix folding, polynomial commitments, and verification across multiple rounds, specifically, the folding techniques, Merkle tree generation, and the batch processing that enables FRI's efficiency.

Before any batch processing occurs, the original data is organized into multiple rounds, where each round consists of matrices with different heights or polynomials of varying degrees. Each round commits into a Merkle tree. Horizontally folding the matrices involves folding matrices of the same height together. For example, when folding a matrix $p(x)$, it requires committing at every fold. After folding, the polynomials of the same degree are reorganized into matrices with a width of two, allowing for simultaneous opening and verification of two values ( i.e., $p_1(-x)$ and $p_1(x)$, one positive and one negative).

1.1.1 The `babybear_fri_pcs` and `m31_fri_pcs` Modules

The babybear_fri_pcs module uses the BabyBear domain, while the m31_fri_pcs module uses the m31 domain. These modules follow the same structure but operate over different finite fields.

Selection of types: The types for the field elements, challenges, and permutations are chosen first.
PCS generation: The get_pcs function generates the PCS (Polynomial Commitment Scheme).
Blowup factors: Two blowup modules are implemented—blowup_1 and blowup_2—which correspond to blowup factors of 1 and 2, respectively. When the blowup factor is set to 2, the Low Degree Extension (LDE) expands by a factor of 4. Depending on the blowup factor (either 1 or 2), different tests are run using the make_tests_for_pcs! macro.

Code

mod babybear_fri_pcs {
    use super::*;

    type Val = BabyBear;
    type Challenge = BinomialExtensionField<Val, 4>;

    type Perm = Poseidon2<Val, Poseidon2ExternalMatrixGeneral, DiffusionMatrixBabyBear, 16, 7>;
    type MyHash = PaddingFreeSponge<Perm, 16, 8, 8>;
    type MyCompress = TruncatedPermutation<Perm, 2, 8, 16>;

    type ValMmcs =
        MerkleTreeMmcs<<Val as Field>::Packing, <Val as Field>::Packing, MyHash, MyCompress, 8>;
    type ChallengeMmcs = ExtensionMmcs<Val, Challenge, ValMmcs>;

    type Dft = Radix2DitParallel;
    type Challenger = DuplexChallenger<Val, Perm, 16, 8>;
    type MyPcs = TwoAdicFriPcs<Val, Dft, ValMmcs, ChallengeMmcs>;

    fn get_pcs(log_blowup: usize) -> (MyPcs, Challenger) {
        let perm = Perm::new_from_rng_128(
            Poseidon2ExternalMatrixGeneral,
            DiffusionMatrixBabyBear::default(),
            &mut seeded_rng(),
        );
        let hash = MyHash::new(perm.clone());
        let compress = MyCompress::new(perm.clone());

        let val_mmcs = ValMmcs::new(hash, compress);
        let challenge_mmcs = ChallengeMmcs::new(val_mmcs.clone());

        let fri_config = FriConfig {
            log_blowup,
            num_queries: 10,
            proof_of_work_bits: 8,
            mmcs: challenge_mmcs,
        };

        let pcs = MyPcs::new(Dft {}, val_mmcs, fri_config);
        (pcs, Challenger::new(perm.clone()))
    }

    mod blowup_1 {
        make_tests_for_pcs!(super::get_pcs(1));
    }
    mod blowup_2 {
        make_tests_for_pcs!(super::get_pcs(2));
    }
}

1.1.2 The `macro_rules!` for Generating Matrices

The macro_rules! in pcs.rs generates tests dynamically with various matrix dimensions, degrees, and rounds, since PCS tests need to handle various rounds (each containing matrices of different heights) of polynomials efficiently.

A round here represents a data structure containing matrices of varying heights. In these tests, the log heights are aligned with powers of two to maintain computational efficiency.

Code

// Set it up so we create tests inside a module for each pcs, so we get nice error reports
// specific to a failing PCS.

macro_rules! make_tests_for_pcs {
    ($p:expr) => {
        #[test]
        fn single() {
            let p = $p;
            for i in 3..6 {
                $crate::do_test_fri_pcs(&p, &[&[i]]);
            }
        }

        #[test]
        fn many_equal() {
            let p = $p;
            for i in 5..8 {
                $crate::do_test_fri_pcs(&p, &[&[i; 5]]);
                println!("{i} ok");
            }
        }

        #[test]
        fn many_different() {
            let p = $p;
            for i in 3..8 {
                let degrees = (3..3 + i).collect::<Vec<_>>();
                $crate::do_test_fri_pcs(&p, &[&degrees]);
            }
        }

        #[test]
        fn many_different_rev() {
            let p = $p;
            for i in 3..8 {
                let degrees = (3..3 + i).rev().collect::<Vec<_>>();
                $crate::do_test_fri_pcs(&p, &[&degrees]);
            }
        }

        #[test]
        fn multiple_rounds() {
            let p = $p;
            $crate::do_test_fri_pcs(&p, &[&[3]]);
            $crate::do_test_fri_pcs(&p, &[&[3], &[3]]);
            $crate::do_test_fri_pcs(&p, &[&[3], &[2]]);
            $crate::do_test_fri_pcs(&p, &[&[2], &[3]]);
            $crate::do_test_fri_pcs(&p, &[&[3, 4], &[3, 4]]);
            $crate::do_test_fri_pcs(&p, &[&[4, 2], &[4, 2]]);
            $crate::do_test_fri_pcs(&p, &[&[2, 2], &[3, 3]]);
            $crate::do_test_fri_pcs(&p, &[&[3, 3], &[2, 2]]);
            $crate::do_test_fri_pcs(&p, &[&[2], &[3, 3]]);
        }
    };
}

1.1.3 The `do_test_fri_pcs` Function

The core function for testing FRI-based PCS is do_test_fri_pcs. Let’s break down its key steps:

Generating domains and polynomials: Based on the log degrees of each round log_degrees_by_round, the domains_and_polys_by_round generates polynomials where each log degree dictates the height of the matrix (or the degree of the polynomial).
Committing to polynomials: Using PCS, the matrices (or polynomials) are committed by commits_by_round and supports committing multiple matrices (polynomials) in a single round.
Verifier challenges: The challenge points zeta and points_by_round for opening the polynomials are generated, while each column of the matrix can be viewed as a polynomial, and the PCS opens the data by open(data_and_points, &mut p_challenger).
Verification: Finally, the proof is verified, ensuring that the commitments made by the prover match the verifier’s expectations by pcs.verify.

Code

fn do_test_fri_pcs<Val, Challenge, Challenger, P>(
    (pcs, challenger): &(P, Challenger),
    log_degrees_by_round: &[&[usize]],
) where
    P: Pcs<Challenge, Challenger>,
    P::Domain: PolynomialSpace<Val = Val>,
    Val: Field,
    Standard: Distribution<Val>,
    Challenge: ExtensionField<Val>,
    Challenger: Clone + CanObserve<P::Commitment> + FieldChallenger<Val>,
{
    let num_rounds = log_degrees_by_round.len();
    let mut rng = seeded_rng();

    let mut p_challenger = challenger.clone();

    let domains_and_polys_by_round = log_degrees_by_round
        .iter()
        .map(|log_degrees| {
            log_degrees
                .iter()
                .map(|&log_degree| {
                    let d = 1 << log_degree;
                    // random width 5-15
                    let width = 5 + rng.gen_range(0..=10);
                    (
                        pcs.natural_domain_for_degree(d),
                        RowMajorMatrix::<Val>::rand(&mut rng, d, width),
                    )
                })
                .collect_vec()
        })
        .collect_vec();

    let (commits_by_round, data_by_round): (Vec<_>, Vec<_>) = domains_and_polys_by_round
        .iter()
        .map(|domains_and_polys| pcs.commit(domains_and_polys.clone()))
        .unzip();
    assert_eq!(commits_by_round.len(), num_rounds);
    assert_eq!(data_by_round.len(), num_rounds);
    p_challenger.observe_slice(&commits_by_round);

    let zeta: Challenge = p_challenger.sample_ext_element();

    let points_by_round = log_degrees_by_round
        .iter()
        .map(|log_degrees| vec![vec![zeta]; log_degrees.len()])
        .collect_vec();
    let data_and_points = data_by_round.iter().zip(points_by_round).collect();
    let (opening_by_round, proof) = pcs.open(data_and_points, &mut p_challenger);
    assert_eq!(opening_by_round.len(), num_rounds);

    // Verify the proof.
    let mut v_challenger = challenger.clone();
    v_challenger.observe_slice(&commits_by_round);
    let verifier_zeta: Challenge = v_challenger.sample_ext_element();
    assert_eq!(verifier_zeta, zeta);

    let commits_and_claims_by_round = izip!(
        commits_by_round,
        domains_and_polys_by_round,
        opening_by_round
    )
    .map(|(commit, domains_and_polys, openings)| {
        let claims = domains_and_polys
            .iter()
            .zip(openings)
            .map(|((domain, _), mat_openings)| (*domain, vec![(zeta, mat_openings[0].clone())]))
            .collect_vec();
        (commit, claims)
    })
    .collect_vec();
    assert_eq!(commits_and_claims_by_round.len(), num_rounds);

    pcs.verify(commits_and_claims_by_round, &proof, &mut v_challenger)
        .unwrap()
}

1.2 Detailed Functionality of `two_adic_pcs.rs`

The two_adic_pcs.rs module implements a Polynomial Commitment Scheme (PCS) tailored to operate over a power-of-two aligned domain. This alignment allows for optimized low-degree extensions, bit-reversal ordering, and efficient matrix handling in a two-adic setting.

The three core functionalities provided by this PCS implementation are encapsulated in the PCS trait: commit, open, and verify. Each of these methods contributes to various stages of polynomial handling, from committing polynomials to verifying their evaluations.

1.2.1: `commit` Function

The commit function is responsible for generating a cryptographic commitment to a set of polynomials, encapsulated in matrices. Each matrix is paired with a corresponding domain, and the goal is to ensure that the commitments are aligned with the domain size.

Key Steps:

Input Arguments: The function accepts evaluations, which are a collection of matrix-domain pairs. Each matrix represents evaluations of a polynomial, and the domain determines the degree and size constraints of that matrix.
Domain-Size Consistency: It first checks if the height of each matrix corresponds to the size of the domain, ensuring that the number of evaluations matches the expected degree constraints.
Low-Degree Extension (LDE): For each matrix, the function computes the low-degree extension (LDE) over a coset using self.dft.coset_lde_batch. This extension maps the matrix into a higher-dimensional space, enabling robust commitments even when the degree is extended.
Bit-Reversing: After LDE, the rows of each matrix are bit-reversed using bit_reverse_rows, which arranges evaluations at $x$ and $-x$ in an alternating fashion. This rearrangement is crucial for efficient evaluation in later stages.
Commitment Using MMCs: The resulting matrices, post-extension and bit-reversal, are committed using multi-message commitments (MMCs), producing a cryptographic commitment that serves as the public representation of the polynomial.

Code

    fn commit(
        &self,
        evaluations: Vec<(Self::Domain, RowMajorMatrix<Val>)>,
    ) -> (Self::Commitment, Self::ProverData) {
        let ldes: Vec<_> = evaluations
            .into_iter()
            .map(|(domain, evals)| {
                assert_eq!(domain.size(), evals.height());
                let shift = Val::generator() / domain.shift;
                // Commit to the bit-reversed LDE.
                self.dft
                    .coset_lde_batch(evals, self.fri.log_blowup, shift)
                    .bit_reverse_rows()
                    .to_row_major_matrix()
            })
            .collect();

        self.mmcs.commit(ldes)
    }

1.2.2: `open` Function

The open function plays a pivotal role in computing quotient polynomials. Given a set of polynomials and evaluation points, it produces the batched quotient polynomial values for a verifier to check. The quotient polynomial $q(x)$ is computed as:

$$ q(x_i) = \sum_{k=0}^{w_l-1} \alpha^k \cdot \frac{f_k(x_i) - y_k}{x_i - z} $$

Where:

$f_k(x_i)$ represents the $k$-th polynomial evaluated at $x_i$.
$y_k = f_k(z)$ is the value of $f_k$ at the opening point $z$.
$\alpha$ is a random challenge used to batch multiple evaluations into a single quotient.

Optimizations for Efficiency:

Pre-computation of Inverses: To avoid repeated calculations, the function precomputes $\frac{1}{x_i - z}$ over the largest domain. These precomputed values are reused across smaller domains by simple truncation, leveraging the power-of-two structure of the domain sizes.
Batching of Alpha Powers: Instead of recalculating powers of $\alpha$ for each polynomial individually, these powers are computed once for the largest matrix width and then reused with an offset for subsequent computations. This reduces the computational overhead of extension field multiplications.
Combination of Alpha and Evaluation Values: For each matrix, the function accumulates the quotient polynomial values by combining the precomputed alpha powers, evaluation values $f_k(x_i)$, and the precomputed inverses. This batching process is optimized to minimize expensive extension field multiplications.

Code

    fn open(
        &self,
        // For each round,
        rounds: Vec<(
            &Self::ProverData,
            // for each matrix,
            Vec<
                // points to open
                Vec<Challenge>,
            >,
        )>,
        challenger: &mut Challenger,
    ) -> (OpenedValues<Challenge>, Self::Proof) {
        /*

        A quick rundown of the optimizations in this function:
        We are trying to compute sum_i alpha^i * (p(X) - y)/(X - z),
        for each z an opening point, y = p(z). Each p(X) is given as evaluations in bit-reversed order
        in the columns of the matrices. y is computed by barycentric interpolation.
        X and p(X) are in the base field; alpha, y and z are in the extension.
        The primary goal is to minimize extension multiplications.

        - Instead of computing all alpha^i, we just compute alpha^i for i up to the largest width
        of a matrix, then multiply by an "alpha offset" when accumulating.
              a^0 x0 + a^1 x1 + a^2 x2 + a^3 x3 + ...
            = a^0 ( a^0 x0 + a^1 x1 ) + a^2 ( a^0 x2 + a^1 x3 ) + ...
            (see `alpha_pows`, `alpha_pow_offset`, `num_reduced`)

        - For each unique point z, we precompute 1/(X-z) for the largest subgroup opened at this point.
        Since we compute it in bit-reversed order, smaller subgroups can simply truncate the vector.
            (see `inv_denoms`)

        - Then, for each matrix (with columns p_i) and opening point z, we want:
            for each row (corresponding to subgroup element X):
                reduced[X] += alpha_offset * sum_i [ alpha^i * inv_denom[X] * (p_i[X] - y[i]) ]

            We can factor out inv_denom, and expand what's left:
                reduced[X] += alpha_offset * inv_denom[X] * sum_i [ alpha^i * p_i[X] - alpha^i * y[i] ]

            And separate the sum:
                reduced[X] += alpha_offset * inv_denom[X] * [ sum_i [ alpha^i * p_i[X] ] - sum_i [ alpha^i * y[i] ] ]

            And now the last sum doesn't depend on X, so we can precompute that for the matrix, too.
            So the hot loop (that depends on both X and i) is just:
                sum_i [ alpha^i * p_i[X] ]

            with alpha^i an extension, p_i[X] a base

        */

        // Batch combination challenge
        let alpha: Challenge = challenger.sample_ext_element();

        let mats_and_points = rounds
            .iter()
            .map(|(data, points)| {
                (
                    self.mmcs
                        .get_matrices(data)
                        .into_iter()
                        .map(|m| m.as_view())
                        .collect_vec(),
                    points,
                )
            })
            .collect_vec();
        let mats = mats_and_points
            .iter()
            .flat_map(|(mats, _)| mats)
            .collect_vec();

        let global_max_height = mats.iter().map(|m| m.height()).max().unwrap();
        let log_global_max_height = log2_strict_usize(global_max_height);

        // For each unique opening point z, we will find the largest degree bound
        // for that point, and precompute 1/(X - z) for the largest subgroup (in bitrev order).
        let inv_denoms = compute_inverse_denominators(&mats_and_points, Val::generator());

        let mut all_opened_values: OpenedValues<Challenge> = vec![];

        let mut reduced_openings: [_; 32] = core::array::from_fn(|_| None);
        let mut num_reduced = [0; 32];

        for (mats, points) in mats_and_points {
            let opened_values_for_round = all_opened_values.pushed_mut(vec![]);
            for (mat, points_for_mat) in izip!(mats, points) {
                let log_height = log2_strict_usize(mat.height());
                let reduced_opening_for_log_height = reduced_openings[log_height]
                    .get_or_insert_with(|| vec![Challenge::zero(); mat.height()]);
                debug_assert_eq!(reduced_opening_for_log_height.len(), mat.height());

                let opened_values_for_mat = opened_values_for_round.pushed_mut(vec![]);
                for &point in points_for_mat {
                    let _guard =
                        info_span!("reduce matrix quotient", dims = %mat.dimensions()).entered();

                    // Use Barycentric interpolation to evaluate the matrix at the given point.
                    let ys = info_span!("compute opened values with Lagrange interpolation")
                        .in_scope(|| {
                            let (low_coset, _) =
                                mat.split_rows(mat.height() >> self.fri.log_blowup);
                            interpolate_coset(
                                &BitReversalPerm::new_view(low_coset),
                                Val::generator(),
                                point,
                            )
                        });

                    let alpha_pow_offset = alpha.exp_u64(num_reduced[log_height] as u64);
                    let reduced_ys: Challenge = dot_product(alpha.powers(), ys.iter().copied());

                    info_span!("reduce rows").in_scope(|| {
                        mat.dot_ext_powers(alpha)
                            .zip(reduced_opening_for_log_height.par_iter_mut())
                            // This might be longer, but zip will truncate to smaller subgroup
                            // (which is ok because it's bitrev)
                            .zip(inv_denoms.get(&point).unwrap().par_iter())
                            .for_each(|((reduced_row, ro), &inv_denom)| {
                                *ro += alpha_pow_offset * (reduced_row - reduced_ys) * inv_denom
                            })
                    });

                    num_reduced[log_height] += mat.width();
                    opened_values_for_mat.push(ys);
                }
            }
        }

        let fri_input = reduced_openings.into_iter().rev().flatten().collect_vec();

        let g: TwoAdicFriGenericConfigForMmcs<Val, InputMmcs> =
            TwoAdicFriGenericConfig(PhantomData);

        let fri_proof = prover::prove(&g, &self.fri, fri_input, challenger, |index| {
            rounds
                .iter()
                .map(|(data, _)| {
                    let log_max_height = log2_strict_usize(self.mmcs.get_max_height(data));
                    let bits_reduced = log_global_max_height - log_max_height;
                    let reduced_index = index >> bits_reduced;
                    let (opened_values, opening_proof) = self.mmcs.open_batch(reduced_index, data);
                    BatchOpening {
                        opened_values,
                        opening_proof,
                    }
                })
                .collect()
        });

        (all_opened_values, fri_proof)
    }

1.2.3: `verify` Function

The verify function ensures that the polynomial evaluations committed to by the prover are valid by checking the provided proof against the original commitment.

Steps:

Initialization of Reduced Openings: A BTreeMap is initialized to store batched quotient polynomial openings, keyed by the logarithmic height of each matrix.

The first step in handling FRI proofs involves setting up a data structure to manage the polynomial opening data. A mutable BTreeMap is initialized to store tuples keyed by the log_height of each matrix. These tuples will contain:

The accumulated batched parameter, represented as powers of alpha.
The accumulated batched quotient polynomial opened values.

This structure will be updated iteratively through the processing of multiple rounds of polynomial data. The core logic for calculating the quotient polynomials’ openings across all rounds follows the formula:

$$ q_d(x)={\sum_{k}\sum_{j}\alpha^{k+j }\cdot \frac{p_{jk}(x) - y_{jk}}{x-z_k} }_{d\in S} $$

Here, the indices are defined as:

$k \in [1,t]$, where $t$ is the number of open points.
$j \in [1,m]$, where $m$ is the number of polynomials.
$d$ is the degree of the polynomial, $p_{jk}$, which is opened at the $k_{th}$ open point with a degree $d$.

This calculation is crucial for batching the quotient polynomials' opened values across multiple rounds.

Iterating Over Rounds: The function iterates over each round’s proof and commitment data, verifying the batched quotient polynomial openings. For each matrix in the round, the verifier checks that the evaluation of the polynomial at a given point matches the values provided by the prover.
Closure for Matrix Verification: The key logic for verification is encapsulated in a closure that iterates over all matrices and computes the accumulated quotient polynomial values.

Code

    fn verify(
        &self,
        // For each round:
        rounds: Vec<(
            Self::Commitment,
            // for each matrix:
            Vec<(
                // its domain,
                Self::Domain,
                // for each point:
                Vec<(
                    // the point,
                    Challenge,
                    // values at the point
                    Vec<Challenge>,
                )>,
            )>,
        )>,
        proof: &Self::Proof,
        challenger: &mut Challenger,
    ) -> Result<(), Self::Error> {
        // Batch combination challenge
        let alpha: Challenge = challenger.sample_ext_element();

        let log_global_max_height = proof.commit_phase_commits.len() + self.fri.log_blowup;

        let g: TwoAdicFriGenericConfigForMmcs<Val, InputMmcs> =
            TwoAdicFriGenericConfig(PhantomData);

        verifier::verify(&g, &self.fri, proof, challenger, |index, input_proof| {
            // TODO: separate this out into functions

            // log_height -> (alpha_pow, reduced_opening)
            let mut reduced_openings = BTreeMap::<usize, (Challenge, Challenge)>::new();

            for (batch_opening, (batch_commit, mats)) in izip!(input_proof, &rounds) {
                let batch_heights = mats
                    .iter()
                    .map(|(domain, _)| domain.size() << self.fri.log_blowup)
                    .collect_vec();
                let batch_dims = batch_heights
                    .iter()
                    // TODO: MMCS doesn't really need width; we put 0 for now.
                    .map(|&height| Dimensions { width: 0, height })
                    .collect_vec();

                let batch_max_height = batch_heights.iter().max().expect("Empty batch?");
                let log_batch_max_height = log2_strict_usize(*batch_max_height);
                let bits_reduced = log_global_max_height - log_batch_max_height;
                let reduced_index = index >> bits_reduced;

                self.mmcs.verify_batch(
                    batch_commit,
                    &batch_dims,
                    reduced_index,
                    &batch_opening.opened_values,
                    &batch_opening.opening_proof,
                )?;
                for (mat_opening, (mat_domain, mat_points_and_values)) in
                    izip!(&batch_opening.opened_values, mats)
                {
                    let log_height = log2_strict_usize(mat_domain.size()) + self.fri.log_blowup;

                    let bits_reduced = log_global_max_height - log_height;
                    let rev_reduced_index = reverse_bits_len(index >> bits_reduced, log_height);

                    // todo: this can be nicer with domain methods?

                    let x = Val::generator()
                        * Val::two_adic_generator(log_height).exp_u64(rev_reduced_index as u64);

                    let (alpha_pow, ro) = reduced_openings
                        .entry(log_height)
                        .or_insert((Challenge::one(), Challenge::zero()));

                    for (z, ps_at_z) in mat_points_and_values {
                        for (&p_at_x, &p_at_z) in izip!(mat_opening, ps_at_z) {
                            let quotient = (-p_at_z + p_at_x) / (-*z + x);
                            *ro += *alpha_pow * quotient;
                            *alpha_pow *= alpha;
                        }
                    }
                }
            }

            // Return reduced openings descending by log_height.
            Ok(reduced_openings
                .into_iter()
                .rev()
                .map(|(log_height, (_alpha_pow, ro))| (log_height, ro))
                .collect())
        })
        .expect("fri err");

        Ok(())
    }
}

1.3 Vertical Folding in the FRI Protocol: A Prover and Verifier Perspective

In the Fast Reed-Solomon Interactive Oracle Proof of Proximity (FRI) protocol, both the prover and verifier must handle numerous polynomials, their evaluations, and corresponding proofs. One of the key processes within this interaction is vertical folding, which plays a crucial role in the efficient proof of polynomial degrees and the batching of quotient polynomials.

1.3.1 Prover’s Input, Folding and Batching

The prover in FRI handles a batch of polynomials and needs to evaluate them over specific points, compute quotient polynomials, and perform folding. The prover's input consists of the following elements:

Inputs: The prover starts with a batch of polynomials ${p_j(X)}^{m}_{j=1}$, their evaluations after a low-degree extension (LDE), and a set of open points ${z_{jk}}^{t_j}_{k=0}$. The prover commits to these evaluated polynomials in each round ${Commit_r}_{r\in \text{all rounds}}$.
Batched Quotient Polynomial: For each distinct degree $d$, the prover computes a batched quotient polynomial as follows:

This results in a set of batched quotient polynomials for all degrees $d \in S$.
Folding and Batching:
- Initialization: Set $f = q_{dm}$, where $dm$ is the highest degree.
- Commitment: Use MMCS to commit $f$ as a matrix.
- Folding: Fold $f$ as $f = f_e + \beta f_o$, where $f_e$ and $f_o$ are the even and odd parts of the polynomial, and $\beta$ is a random challenge.
- Batching: Update $f$ by adding the next quotient polynomial, $q_d$.
- Repeat: Continue folding and batching until $f$ becomes a constant polynomial.

At the end of the process, the prover has:

Commitments to intermediate polynomials ${C_{f_d}}_{d \in S}$.
A final constant polynomial $f_c$.

This prepares the prover to answer the verifier's queries efficiently, providing opening proofs for verification.

Code

#[instrument(name = "commit phase", skip_all)]
fn commit_phase<G, Val, Challenge, M, Challenger>(
    g: &G,
    config: &FriConfig<M>,
    inputs: Vec<Vec<Challenge>>,
    challenger: &mut Challenger,
) -> CommitPhaseResult<Challenge, M>
where
    Val: Field,
    Challenge: ExtensionField<Val>,
    M: Mmcs<Challenge>,
    Challenger: FieldChallenger<Val> + CanObserve<M::Commitment>,
    G: FriGenericConfig<Challenge>,
{
    let mut inputs_iter = inputs.into_iter().peekable();
    let mut folded = inputs_iter.next().unwrap();
    let mut commits = vec![];
    let mut data = vec![];

    while folded.len() > config.blowup() {
        let leaves = RowMajorMatrix::new(folded, 2);
        let (commit, prover_data) = config.mmcs.commit_matrix(leaves);
        challenger.observe(commit.clone());

        let beta: Challenge = challenger.sample_ext_element();
        // We passed ownership of `current` to the MMCS, so get a reference to it
        let leaves = config.mmcs.get_matrices(&prover_data).pop().unwrap();
        folded = g.fold_matrix(beta, leaves.as_view());

        commits.push(commit);
        data.push(prover_data);

        if let Some(v) = inputs_iter.next_if(|v| v.len() == folded.len()) {
            izip!(&mut folded, v).for_each(|(c, x)| *c += x);
        }
    }

    // We should be left with `blowup` evaluations of a constant polynomial.
    assert_eq!(folded.len(), config.blowup());
    let final_poly = folded[0];
    for x in folded {
        assert_eq!(x, final_poly);
    }
    challenger.observe_ext_element(final_poly);

    CommitPhaseResult {
        commits,
        data,
        final_poly,
    }
}

1.3.2 Vertical Folding in the Verifier

The verifier's task is to validate the prover's folded polynomials and opening proofs. The vertical folding process for the verifier follows these steps:

Verifier Input: The verifier receives the prover’s commitments ${Commit_r}_{r \in \text{all rounds}}$, all input and query opened values, and the sample query index $\delta$.
Initialize Folding: The verifier initializes the folded evaluation $e = 0$.
Batching: The verifier batches the folded evaluation by setting $e = e + q_d(\delta)$ for each degree $d$, ensuring the degree of $q_d(\delta)$ matches the current degree of $e$.
Check Openings: The verifier checks the opening of $e$ by comparing the computed value with the prover's opening proof.
Folding: The verifier computes the next folded evaluation using the current $e$, the folding parameter $\beta$, the query index $\delta$, and the sibling value corresponding to the current fold.
Iteration: Steps 2–5 are repeated for the number of iterations corresponding to the logarithm of the degree.

Finally, the verifier arrives at a final folded evaluation $e_{\text{final}}$ and checks its equality with the constant polynomial $f_c$ sent by the prover.

Code

fn verify_query<'a, G, F, M>(
    g: &G,
    config: &FriConfig<M>,
    mut index: usize,
    steps: impl Iterator<Item = CommitStep<'a, F, M>>,
    reduced_openings: Vec<(usize, F)>,
    log_max_height: usize,
) -> Result<F, FriError<M::Error, G::InputError>>
where
    F: Field,
    M: Mmcs<F> + 'a,
    G: FriGenericConfig<F>,
{
    let mut folded_eval = F::zero();
    let mut ro_iter = reduced_openings.into_iter().peekable();

    for (log_folded_height, (&beta, comm, opening)) in izip!((0..log_max_height).rev(), steps) {
        if let Some((_, ro)) = ro_iter.next_if(|(lh, _)| *lh == log_folded_height + 1) {
            folded_eval += ro;
        }

        let index_sibling = index ^ 1;
        let index_pair = index >> 1;

        let mut evals = vec![folded_eval; 2];
        evals[index_sibling % 2] = opening.sibling_value;

        let dims = &[Dimensions {
            width: 2,
            height: 1 << log_folded_height,
        }];
        config
            .mmcs
            .verify_batch(
                comm,
                dims,
                index_pair,
                &[evals.clone()],
                &opening.opening_proof,
            )
            .map_err(FriError::CommitPhaseMmcsError)?;

        index = index_pair;

        folded_eval = g.fold_row(index, log_folded_height, beta, evals.into_iter());
    }

    debug_assert!(index < config.blowup(), "index was {}", index);
    debug_assert!(
        ro_iter.next().is_none(),
        "verifier reduced_openings were not in descending order?"
    );

    Ok(folded_eval)
}

2.Uni-STARK: Overview of Prover and Verifier Roles in Plonky3

The Uni-STARK system in Plonky3 generally follows the structure of STARKs as mentioned before. Below is a step-by-step breakdown of the process, which includes committing to trace and quotient polynomials, opening them for verification, and the eventual query phase for proof validation.

2.1. Commit Phase

The commit phase involves committing to both the trace polynomials and the quotient polynomials:

Step 1: Commit to Trace Polynomials

First, we calculate the trace, which could be something like a Fibonacci sequence. The trace table consists of several columns, each representing a trace polynomial. After performing a low-degree extension (LDE), these trace polynomials are committed to.
- The trace table is represented as a RowMajorMatrix<Val<SC>>. The trace polynomials are committed over a multiplicative subgroup called the trace domain. To prevent the quotient polynomial from being computed over the same domain (which would result in the quotient being zero), the pcs.commit function offsets the trace domain to a coset and performs the commitment over the LDE combined with a bit-reversal technique.

Step 2: Commit to the Quotient Polynomial

The quotient polynomial is computed by applying the constraints to the trace polynomials (like Fibonacci recurrence rules) and then dividing the result by a zero polynomial $Z(X)$ to form the quotient polynomial.
- A coset corresponding to the trace domain is selected, with the size of the coset group being $\log(\text{degree}) + \log(\text{quotient degree})$.
- The trace on the quotient domain represents the trace polynomials on that domain. Transitioning from the trace domain to the quotient domain involves shifting by the coset's offset. For example, converting a polynomial from the original domain to the coset involves a shift $x \mapsto gx$, where $g$ is the coset generator.
- Quotient values are calculated, and the degrees of the quotient polynomials are aligned using a random $\alpha$. In Plonky3, the degree of the trace polynomial is usually less than the quotient polynomial degree, but here the quotient polynomial degree equals $\log(\text{degree}) + \log(\text{quotient degree})$.
- Using the get_evaluations_on_domain function from two_adic_pcs.rs, LDE evaluations are performed. The number of rows needed is adjusted based on the quotient domain, and bit-reversed rows are processed from the Merkle tree or from previous trace commitments to match the larger quotient degree.

Key formulas include:

$C_0(X) = a(X) + b(X) - b(gX)$ (enforcing the first transition constraint)
$C_1(X) = a(gX) - b(X)$ (enforcing the second transition constraint)
$q_0(X) = \frac{C_0(X)}{Z_H(X)}$ and $q_1(X) = \frac{C_1(X)}{Z_H(X)}$

To align degrees, a random $\alpha$ is used, producing modified quotient polynomials $q_0'(X)$ and $q_1'(X)$. These are combined to form $Q(X) = q_0'(X) + q_1'(X)$, where the domain is on a coset.

Step 3: Splitting the Quotient Polynomial into Chunks

To optimize the FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) protocol, the quotient polynomial is split into chunks. These smaller quotient polynomials are of the same degree as the trace polynomial.
- For example, suppose we have a multiplicative subgroup of order 6, and we want to split the quotient polynomial into two smaller polynomials. This splitting is done by evaluating $Q(X)$ at generators $w^2$ and $w^4$, where $w$ is a two-adic generator.
- The quotient polynomial is split as $Q(z) = Q_1(z^S) + z \cdot Q_2(z^S)$, where evaluations take place at domain generators shifted by cosets.

After splitting, each chunk is committed individually as follows: - $Q_1(X)$ and $Q_2(X)$ are committed using their low-degree extensions. - A Merkle tree is constructed from the commitment matrices of the quotient polynomial chunks, and the final commitment is recorded.

In the Fiat–Shamir phase, random challenge points $\zeta$ and $\zeta_{\text{next}}$ are used to verify that the committed trace and quotient polynomials satisfy the required constraint relationships. The pcs.open function retrieves the necessary proofs for verification, ensuring consistency between the commitments and the actual trace polynomials.

Code

    let degree = trace.height();
    let log_degree = log2_strict_usize(degree);

    let log_quotient_degree = get_log_quotient_degree::<Val<SC>, A>(air, 0, public_values.len());
    let quotient_degree = 1 << log_quotient_degree;

    let pcs = config.pcs();
    let trace_domain = pcs.natural_domain_for_degree(degree);

    let (trace_commit, trace_data) =
        info_span!("commit to trace data").in_scope(|| pcs.commit(vec![(trace_domain, trace)]));

    // Observe the instance.
    challenger.observe(Val::<SC>::from_canonical_usize(log_degree));
    // TODO: Might be best practice to include other instance data here; see verifier comment.

    challenger.observe(trace_commit.clone());
    challenger.observe_slice(public_values);
    let alpha: SC::Challenge = challenger.sample_ext_element();

    let quotient_domain =
        trace_domain.create_disjoint_domain(1 << (log_degree + log_quotient_degree));

    let trace_on_quotient_domain = pcs.get_evaluations_on_domain(&trace_data, 0, quotient_domain);

    let quotient_values = quotient_values(
        air,
        public_values,
        trace_domain,
        quotient_domain,
        trace_on_quotient_domain,
        alpha,
    );
    let quotient_flat = RowMajorMatrix::new_col(quotient_values).flatten_to_base();
    let quotient_chunks = quotient_domain.split_evals(quotient_degree, quotient_flat);
    let qc_domains = quotient_domain.split_domains(quotient_degree);

    let (quotient_commit, quotient_data) = info_span!("commit to quotient poly chunks")
        .in_scope(|| pcs.commit(izip!(qc_domains, quotient_chunks).collect_vec()));
    challenger.observe(quotient_commit.clone());

    let commitments = Commitments {
        trace: trace_commit,
        quotient_chunks: quotient_commit,
    };

    let zeta: SC::Challenge = challenger.sample();
    let zeta_next = trace_domain.next_point(zeta).unwrap();

2.2 Opening Phase

The opening phase allows the prover to reveal specific evaluations of the trace and quotient polynomials to the verifier:

2.2.1 Constructing the Opening Proof

When the verifier receives the proof, it needs to verify that the trace and quotient polynomials satisfy the constraints at random points, typically denoted as $\zeta$ and $\zeta_{\text{next}}$, which are sampled in an extension field. Since the committed trace polynomials are over the base field, $\zeta$ does not belong to the original multiplicative subgroup over which the trace polynomials were committed.

Step 1: Opening the Trace Polynomial

To ensure that the trace polynomial satisfies the given constraints, we need to "open" the trace polynomial at the points $\zeta$ and $\zeta_{\text{next}}$.
Since the trace polynomials at $\zeta$ and $\zeta_{\text{next}}$ have the same degree, we can linearly combine them into a reduced polynomial, $\text{reduce}_0(X)$, which simplifies further computations.

Step 2: Opening the Quotient Polynomial

Similarly, we open the quotient polynomial at $\zeta$. Here, we compute two quotient-related polynomials, $ldt_2(X)$ and $ldt_3(X)$, which represent quotient polynomials over different chunks (since the quotient polynomial has been split into chunks).
The quotient chunks at $\zeta$ are combined into a reduced polynomial $\text{reduce}_1(X)$. This polynomial also has the same degree as $\text{reduce}_0(X)$, allowing the two reduced polynomials to be tested together.

2.2.2. Low-Degree Testing of the Reduced Polynomials

Once the reduced polynomials $\text{reduce}_0(X)$ and $\text{reduce}_1(X)$ are constructed, they undergo a low-degree test to verify that both polynomials have a degree lower than a specified threshold.

Steps for Low-Degree Testing:

Opening the Trace Polynomial:
- Open the trace polynomial at points $\zeta$ and $\zeta_{\text{next}}$, as well as the quotient polynomial chunks $Q_1(X)$ and $Q_2(X)$ at $\zeta$.
- These openings yield intermediate values used to compute the reduced polynomials.
Constructing the Reduced Polynomial:
- Compute the reduced trace polynomial:
where $ldt_0(X)$ and $ldt_0'(X)$ are the Lagrange polynomials formed from the trace evaluations at $\zeta$ and $\zeta_{\text{next}}$. - Similarly, compute the reduced quotient polynomial:

where $ldt_2(X)$ and $ldt_3(X)$ are Lagrange polynomials derived from quotient evaluations.
Performing the Low-Degree Test:
- Both reduced polynomials $\text{reduce}_0(X)$ and $\text{reduce}_1(X)$ undergo a low-degree test to verify their degree bounds.

Code

    let (opened_values, opening_proof) = info_span!("open").in_scope(|| {
        pcs.open(
            vec![
                (&trace_data, vec![vec![zeta, zeta_next]]),
                (
                    &quotient_data,
                    // open every chunk at zeta
                    (0..quotient_degree).map(|_| vec![zeta]).collect_vec(),
                ),
            ],
            challenger,
        )
    });
    let trace_local = opened_values[0][0][0].clone();
    let trace_next = opened_values[0][0][1].clone();
    let quotient_chunks = opened_values[1].iter().map(|v| v[0].clone()).collect_vec();
    let opened_values = OpenedValues {
        trace_local,
        trace_next,
        quotient_chunks,
    };
    Proof {
        commitments,
        opened_values,
        opening_proof,
        degree_bits: log_degree,
    }

2.3. Query Phase: Verifying Constraints

In the query phase, the verifier confirms that the trace polynomial at $\zeta$ and $\zeta_{\text{next}}$, along with the quotient polynomial, satisfy the constraints. This involves several steps:

Step 1: Verifying $Q(\zeta)$

The verifier checks if the trace polynomial at $\zeta$ and $\zeta_{\text{next}}$ satisfies the constraints by applying the transition rules, allowing the calculation of $Q(\zeta)$.
The quotient polynomial values $Q_1(\zeta)$ and $Q_2(\zeta)$ are combined to reconstruct $Q(\zeta)$. The verifier then compares the reconstructed $Q(\zeta)$ to the expected result. If they match, the constraints are satisfied.
In the code, this is done by folding the constraints and comparing the results:

if folded_constraints = sels.inv_zeroifier != quotient { ... }

Step 2: Addressing ZPS and Domain Shifts

The process of reconstructing $Q(\zeta)$ introduces a potential Zero-Polynomial Shift (ZPS) problem. When using Lagrange interpolation to reconstruct $Q(\zeta)$, errors can occur due to domain shrinking.
For example, $Q(X) = Q_1(X^2) + X \cdot Q_1(-X^2)$ has a smaller domain, so additional corrections are needed to account for the missing elements from the other coset domains. This is handled by computing a ZPS correction factor to adjust for these domain shifts.

The Lagrange interpolants are adjusted as follows:

$$ zps[i] = \prod_{j \neq i} \frac{\left(\frac{x}{\text{shift}_j}\right)^n - 1}{\left(\frac{\text{shift}_i}{\text{shift}_j}\right)^n - 1} $$

The verifier then uses this ZPS correction to verify the consistency of the trace and quotient evaluations at $\zeta$ and $\zeta_{\text{next}}$, ensuring that all domain shifts are correctly handled.

Code

pcs.verify(
        vec![
            (
                commitments.trace.clone(),
                vec![(
                    trace_domain,
                    vec![
                        (zeta, opened_values.trace_local.clone()),
                        (zeta_next, opened_values.trace_next.clone()),
                    ],
                )],
            ),
            (
                commitments.quotient_chunks.clone(),
                quotient_chunks_domains
                    .iter()
                    .zip(&opened_values.quotient_chunks)
                    .map(|(domain, values)| (*domain, vec![(zeta, values.clone())]))
                    .collect_vec(),
            ),
        ],
        opening_proof,
        challenger,
    )
    .map_err(VerificationError::InvalidOpeningArgument)?;

    let zps = quotient_chunks_domains
        .iter()
        .enumerate()
        .map(|(i, domain)| {
            quotient_chunks_domains
                .iter()
                .enumerate()
                .filter(|(j, _)| *j != i)
                .map(|(_, other_domain)| {
                    other_domain.zp_at_point(zeta)
                        * other_domain.zp_at_point(domain.first_point()).inverse()
                })
                .product::<SC::Challenge>()
        })
        .collect_vec();

    let quotient = opened_values
        .quotient_chunks
        .iter()
        .enumerate()
        .map(|(ch_i, ch)| {
            ch.iter()
                .enumerate()
                .map(|(e_i, &c)| zps[ch_i] * SC::Challenge::monomial(e_i) * c)
                .sum::<SC::Challenge>()
        })
        .sum::<SC::Challenge>();

    let sels = trace_domain.selectors_at_point(zeta);

    let main = VerticalPair::new(
        RowMajorMatrixView::new_row(&opened_values.trace_local),
        RowMajorMatrixView::new_row(&opened_values.trace_next),
    );

    let mut folder = VerifierConstraintFolder {
        main,
        public_values,
        is_first_row: sels.is_first_row,
        is_last_row: sels.is_last_row,
        is_transition: sels.is_transition,
        alpha,
        accumulator: SC::Challenge::zero(),
    };
    air.eval(&mut folder);
    let folded_constraints = folder.accumulator;

    // Finally, check that
    //     folded_constraints(zeta) / Z_H(zeta) = quotient(zeta)
    if folded_constraints * sels.inv_zeroifier != quotient {
        return Err(VerificationError::OodEvaluationMismatch);
    }

Conclusion

As demand for zk-SNARKs continues to grow, Plonky3's blend of FRI and UniStark technologies positions it as a cutting-edge tool for scaling cryptographic proofs, enabling faster, more secure, and more efficient decentralized ecosystems.

Plonky3

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

45_Plonky3.md

45_Plonky3.md

ETAAcademy-ZKMeme: 45. Plonky3

Plonky3: A Deep Dive into Scalable zk-SNARKs of FRI and UniStark

1.FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) in Plonky3

1.1 Polynomial Commitment Scheme (PCS) in FRI: Code Structure

1.1.1 The `babybear_fri_pcs` and `m31_fri_pcs` Modules

1.1.2 The `macro_rules!` for Generating Matrices

1.1.3 The `do_test_fri_pcs` Function

1.2 Detailed Functionality of `two_adic_pcs.rs`

1.2.1: `commit` Function

Key Steps:

1.2.2: `open` Function

Optimizations for Efficiency:

1.2.3: `verify` Function

Steps:

1.3 Vertical Folding in the FRI Protocol: A Prover and Verifier Perspective

1.3.1 Prover’s Input, Folding and Batching

1.3.2 Vertical Folding in the Verifier

2.Uni-STARK: Overview of Prover and Verifier Roles in Plonky3

2.1. Commit Phase

2.2 Opening Phase

2.2.1 Constructing the Opening Proof

2.2.2. Low-Degree Testing of the Reduced Polynomials

2.3. Query Phase: Verifying Constraints

Conclusion

Files

45_Plonky3.md

Latest commit

History

45_Plonky3.md

File metadata and controls

ETAAcademy-ZKMeme: 45. Plonky3

Plonky3: A Deep Dive into Scalable zk-SNARKs of FRI and UniStark

1.FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) in Plonky3

1.1 Polynomial Commitment Scheme (PCS) in FRI: Code Structure

1.1.1 The babybear_fri_pcs and m31_fri_pcs Modules

1.1.2 The macro_rules! for Generating Matrices

1.1.3 The do_test_fri_pcs Function

1.2 Detailed Functionality of two_adic_pcs.rs

1.2.1: commit Function

Key Steps:

1.2.2: open Function

Optimizations for Efficiency:

1.2.3: verify Function

Steps:

1.3 Vertical Folding in the FRI Protocol: A Prover and Verifier Perspective

1.3.1 Prover’s Input, Folding and Batching

1.3.2 Vertical Folding in the Verifier

2.Uni-STARK: Overview of Prover and Verifier Roles in Plonky3

2.1. Commit Phase

2.2 Opening Phase

2.2.1 Constructing the Opening Proof

2.2.2. Low-Degree Testing of the Reduced Polynomials

2.3. Query Phase: Verifying Constraints

Conclusion

1.1.1 The `babybear_fri_pcs` and `m31_fri_pcs` Modules

1.1.2 The `macro_rules!` for Generating Matrices

1.1.3 The `do_test_fri_pcs` Function

1.2 Detailed Functionality of `two_adic_pcs.rs`

1.2.1: `commit` Function

1.2.2: `open` Function

1.2.3: `verify` Function