The Multiopen Argument

1. Why this chapter exists

A halo2 verifier wants to check evaluations of dozens of polynomials at a handful of points. Running an IPA opening per polynomial would be both slow and large. The multiopen argument groups the polynomials by their query points, linearly combines them with verifier challenges, and runs a single IPA on the collapsed result. The argument is small in code, large in consequences: the only critical CVE-class fix in halo2's history landed here.

2. Definitions

Definition (Polynomial query). A triple $(p, x, e)$ where $p$ is a committed polynomial, $x$ is the point at which it is opened, and $e = p(x)$ is the claimed evaluation.

Definition (Multiopen instance). A finite list of polynomial queries. The prover and verifier both walk this list using the same canonical order; any reordering must be agreed on by both sides (this is what the soundness fix below is about).

Definition (Point set, commitment-keyed grouping). Group the queries first by the set of points $X = \{x_1, \dots, x_m\}$ at which a given polynomial is opened, and then by the polynomial commitment. The "rotation set" for a polynomial is the multiset of points at which it is opened.

Definition (Quotient polynomial $q$). For each polynomial $p$ opened at points $X$, define the quotient $q(X) = (p(X) - r(X)) / Z_X(X)$ where $r$ is the polynomial that interpolates the $(x_i, e_i)$ pairs and $Z_X(X) = \prod_{x_i \in X} (X - x_i)$. The multiopen argument reduces to the IPA opening of a single random linear combination of all such $q$'s.

3. The code

3.1 Module structure and challenges

halo2_proofs/src/poly/multiopen.rs

//! This module contains an optimisation of the polynomial commitment opening
//! scheme described in the [Halo][halo] paper.
//!
//! [halo]: https://eprint.iacr.org/2019/1021

use std::collections::{BTreeMap, BTreeSet};
use std::hash::Hash;

use indexmap::IndexMap;

use super::*;
use crate::{arithmetic::CurveAffine, transcript::ChallengeScalar};

mod prover;
mod verifier;

pub use prover::create_proof;
pub use verifier::verify_proof;

#[derive(Clone, Copy, Debug)]
struct X1 {}
/// Challenge for compressing openings at the same point sets together.
type ChallengeX1<F> = ChallengeScalar<F, X1>;

#[derive(Clone, Copy, Debug)]
struct X2 {}
/// Challenge for keeping the multi-point quotient polynomial terms linearly independent.
type ChallengeX2<F> = ChallengeScalar<F, X2>;

#[derive(Clone, Copy, Debug)]
struct X3 {}
/// Challenge point at which the commitments are opened.
type ChallengeX3<F> = ChallengeScalar<F, X3>;

#[derive(Clone, Copy, Debug)]
struct X4 {}
/// Challenge for collapsing the openings of the various remaining polynomials at x_3
/// together.
type ChallengeX4<F> = ChallengeScalar<F, X4>;

Four named challenges, in order of use:

• $x_1$: collapses queries that share the same point set.
• $x_2$: keeps the per-point-set quotient polynomials linearly independent.
• $x_3$: the eventual opening point.
• $x_4$: collapses the remaining openings at $x_3$ before the final IPA.

The order matters: each is squeezed from the transcript only after all the commitments it depends on have been written. Re-read this when chasing a multiopen verifier mismatch.

3.2 Query types

halo2_proofs/src/poly/multiopen.rs

/// A polynomial query at a point
#[derive(Debug, Clone)]
pub struct ProverQuery<'a, C: CurveAffine> {
    /// point at which polynomial is queried
    pub point: C::Scalar,
    /// coefficients of polynomial
    pub poly: &'a Polynomial<C::Scalar, Coeff>,
    /// blinding factor of polynomial
    pub blind: commitment::Blind<C::Scalar>,
}

/// A polynomial query at a point
#[derive(Debug, Clone)]
pub struct VerifierQuery<'r, 'params: 'r, C: CurveAffine> {
    /// point at which polynomial is queried
    point: C::Scalar,
    /// commitment to polynomial
    commitment: CommitmentReference<'r, 'params, C>,
    /// evaluation of polynomial at query point
    eval: C::Scalar,
}

impl<'r, 'params: 'r, C: CurveAffine> VerifierQuery<'r, 'params, C> {
    /// Create a new verifier query based on a commitment
    pub fn new_commitment(commitment: &'r C, point: C::Scalar, eval: C::Scalar) -> Self {
        VerifierQuery {
            point,
            eval,
            commitment: CommitmentReference::Commitment(commitment),
        }
    }

    /// Create a new verifier query based on a linear combination of commitments
    pub fn new_msm(
        msm: &'r commitment::MSM<'params, C>,
        point: C::Scalar,
        eval: C::Scalar,
    ) -> Self {
        VerifierQuery {
            point,
            eval,
            commitment: CommitmentReference::MSM(msm),
        }
    }
}

#[allow(clippy::upper_case_acronyms)]
#[derive(Copy, Clone, Debug)]
enum CommitmentReference<'r, 'params: 'r, C: CurveAffine> {
    Commitment(&'r C),
    MSM(&'r commitment::MSM<'params, C>),
}

impl<'r, 'params: 'r, C: CurveAffine> PartialEq for CommitmentReference<'r, 'params, C> {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (&CommitmentReference::Commitment(a), &CommitmentReference::Commitment(b)) => {
                std::ptr::eq(a, b)
            }
            (&CommitmentReference::MSM(a), &CommitmentReference::MSM(b)) => std::ptr::eq(a, b),
            _ => false,
        }
    }
}

impl<'r, 'params: 'r, C: CurveAffine> Eq for CommitmentReference<'r, 'params, C> {}

impl<'r, 'params: 'r, C: CurveAffine> Hash for CommitmentReference<'r, 'params, C> {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        match *self {
            CommitmentReference::Commitment(a) => std::ptr::hash(a, state),
            CommitmentReference::MSM(a) => std::ptr::hash(a, state),
        }
    }
}

#[derive(Debug)]
struct CommitmentData<F, T: PartialEq> {
    commitment: T,
    set_index: usize,

ProverQuery carries the actual polynomial coefficients; the prover needs them. VerifierQuery carries only the commitment reference and the claimed evaluation; the verifier only ever sees those.

3.3 The prover

halo2_proofs/src/poly/multiopen/prover.rs

/// Create a multi-opening proof
pub fn create_proof<
    'a,
    I,
    C: CurveAffine,
    E: EncodedChallenge<C>,
    R: RngCore,
    T: TranscriptWrite<C, E>,
>(
    params: &Params<C>,
    mut rng: R,
    transcript: &mut T,
    queries: I,
) -> io::Result<()>
where
    I: IntoIterator<Item = ProverQuery<'a, C>> + Clone,
{
    let x_1: ChallengeX1<_> = transcript.squeeze_challenge_scalar();
    let x_2: ChallengeX2<_> = transcript.squeeze_challenge_scalar();

    let (poly_map, point_sets) = construct_intermediate_sets(queries).ok_or_else(|| {
        io::Error::new(
            io::ErrorKind::InvalidInput,
            "queries iterator contains mismatching evaluations",
        )
    })?;

    // Collapse openings at same point sets together into single openings using
    // x_1 challenge.
    let mut q_polys: Vec<Option<Polynomial<C::Scalar, Coeff>>> = vec![None; point_sets.len()];
    let mut q_blinds = vec![Blind(C::Scalar::ZERO); point_sets.len()];

    {
        let mut accumulate =
            |set_idx: usize, new_poly: &Polynomial<C::Scalar, Coeff>, blind: Blind<C::Scalar>| {
                if let Some(poly) = &q_polys[set_idx] {
                    q_polys[set_idx] = Some(poly.clone() * *x_1 + new_poly);
                } else {
                    q_polys[set_idx] = Some(new_poly.clone());
                }
                q_blinds[set_idx] *= *x_1;
                q_blinds[set_idx] += blind;
            };

        for commitment_data in poly_map.into_iter() {
            accumulate(
                commitment_data.set_index,        // set_idx,
                commitment_data.commitment.poly,  // poly,
                commitment_data.commitment.blind, // blind,
            );
        }
    }

    let q_prime_poly = point_sets
        .iter()
        .zip(q_polys.iter())
        .fold(None, |q_prime_poly, (points, poly)| {
            let mut poly = points
                .iter()
                .fold(poly.clone().unwrap().values, |poly, point| {
                    kate_division(&poly, *point)
                });
            poly.resize(params.n as usize, C::Scalar::ZERO);
            let poly = Polynomial {
                values: poly,
                _marker: PhantomData,
            };

            if q_prime_poly.is_none() {
                Some(poly)
            } else {
                q_prime_poly.map(|q_prime_poly| q_prime_poly * *x_2 + &poly)
            }
        })
        .unwrap();

    let q_prime_blind = Blind(C::Scalar::random(&mut rng));
    let q_prime_commitment = params.commit(&q_prime_poly, q_prime_blind).to_affine();

    transcript.write_point(q_prime_commitment)?;

    let x_3: ChallengeX3<_> = transcript.squeeze_challenge_scalar();

    // Prover sends u_i for all i, which correspond to the evaluation
    // of each Q polynomial commitment at x_3.
    for q_i_poly in &q_polys {
        transcript.write_scalar(eval_polynomial(q_i_poly.as_ref().unwrap(), *x_3))?;
    }

    let x_4: ChallengeX4<_> = transcript.squeeze_challenge_scalar();

    let (p_poly, p_poly_blind) = q_polys.into_iter().zip(q_blinds).fold(
        (q_prime_poly, q_prime_blind),
        |(q_prime_poly, q_prime_blind), (poly, blind)| {
            (
                q_prime_poly * *x_4 + &poly.unwrap(),
                Blind((q_prime_blind.0 * &(*x_4)) + &blind.0),
            )
        },
    );

The prover's flow:

1. Bucket the queries by point set; within each bucket, compute a linear combination of polynomials using powers of $x_1$.
2. Compute the per-bucket quotient $q = (p - r) / Z_X$ using kate_division.
3. Combine all $q$'s using powers of $x_2$ into a single $f$.
4. Commit to $f$.
5. Squeeze $x_3$; evaluate $f$ at $x_3$ and write the evaluations of every $p$ at every $x_i$.
6. Squeeze $x_4$; collapse all the openings at $x_3$ into one final IPA opening.

3.4 The verifier

halo2_proofs/src/poly/multiopen/verifier.rs

use ff::Field;

use super::super::{
    commitment::{Guard, Params, MSM},
    Error,
};
use super::{
    construct_intermediate_sets, ChallengeX1, ChallengeX2, ChallengeX3, ChallengeX4,
    CommitmentReference, Query, VerifierQuery,
};
use crate::arithmetic::{eval_polynomial, lagrange_interpolate, CurveAffine};
use crate::transcript::{EncodedChallenge, TranscriptRead};

/// Verify a multi-opening proof
pub fn verify_proof<
    'r,
    'params: 'r,
    I,
    C: CurveAffine,
    E: EncodedChallenge<C>,
    T: TranscriptRead<C, E>,
>(
    params: &'params Params<C>,
    transcript: &mut T,
    queries: I,
    mut msm: MSM<'params, C>,
) -> Result<Guard<'params, C, E>, Error>
where
    I: IntoIterator<Item = VerifierQuery<'r, 'params, C>> + Clone,
{
    // Sample x_1 for compressing openings at the same point sets together
    let x_1: ChallengeX1<_> = transcript.squeeze_challenge_scalar();

    // Sample a challenge x_2 for keeping the multi-point quotient
    // polynomial terms linearly independent.
    let x_2: ChallengeX2<_> = transcript.squeeze_challenge_scalar();

    let (commitment_map, point_sets) =
        construct_intermediate_sets(queries).ok_or(Error::OpeningError)?;

    // Compress the commitments and expected evaluations at x together.
    // using the challenge x_1
    let mut q_commitments: Vec<_> = vec![
        (params.empty_msm(), C::Scalar::ONE); // (accumulator, next x_1 power).
        point_sets.len()];

    // A vec of vecs of evals. The outer vec corresponds to the point set,
    // while the inner vec corresponds to the points in a particular set.
    let mut q_eval_sets = Vec::with_capacity(point_sets.len());
    for point_set in point_sets.iter() {
        q_eval_sets.push(vec![C::Scalar::ZERO; point_set.len()]);
    }

    {
        let mut accumulate = |set_idx: usize, new_commitment, evals: Vec<C::Scalar>| {
            let (q_commitment, x_1_power) = &mut q_commitments[set_idx];
            match new_commitment {
                CommitmentReference::Commitment(c) => {
                    q_commitment.append_term(*x_1_power, *c);
                }
                CommitmentReference::MSM(msm) => {
                    let mut msm = msm.clone();
                    msm.scale(*x_1_power);
                    q_commitment.add_msm(&msm);
                }
            }
            for (eval, set_eval) in evals.iter().zip(q_eval_sets[set_idx].iter_mut()) {
                *set_eval += (*eval) * (*x_1_power);
            }
            *x_1_power *= *x_1;
        };

        // Each commitment corresponds to evaluations at a set of points.
        // For each set, we collapse each commitment's evals pointwise.
        // Run in order of increasing x_1 powers.
        for commitment_data in commitment_map.into_iter().rev() {
            accumulate(
                commitment_data.set_index,  // set_idx,
                commitment_data.commitment, // commitment,
                commitment_data.evals,      // evals

The verifier mirrors the prover step by step, replacing "polynomial" with "commitment + evaluation" everywhere, and runs the final IPA verifier on the collapsed claim.

3.5 The 2025 soundness fix (halo2_proofs 0.3.1)

halo2_proofs/CHANGELOG.md

## [0.3.1] - 2025-07-07
### Security
`halo2_proofs` uses a multiopen argument in its proofs, which takes the sequence
of circuit queries and evaluations, and groups them into query sets for proof
efficiency. The previous implementation had a bug where two queries within the
sequence could provide the same evaluation point and commitment, but different
evaluations. A vulnerable circuit with a bug resulting in such a sequence of
evaluations is unsound, but a verifier for this circuit would previously not
reject these proofs.

The multiopen logic has been updated to detect and reject this case; both provers
and verifiers now return an error instead. The multiopen logic now also uses the
`indexmap` crate to further reduce its complexity.

The bug was found by Suneal from zkSecurity.

The pre-0.3.1 multiopen code grouped queries by (point, commitment) using a hash map that did not detect when the same (point, commitment) pair was inserted twice with two different evaluations. A buggy circuit could submit (C, x, e_1) and (C, x, e_2) with $e_1 \neq e_2$; the verifier accepted both. The fix has three parts:

1. The multiopen code now uses indexmap::IndexMap to preserve insertion order deterministically.
2. Both prover and verifier explicitly check that no (point, commitment) pair is inserted twice with conflicting evaluations. The mismatch returns Error::OpeningError.
3. The corresponding test in halo2_proofs/tests/plonk_api.rs was extended to lock the new behaviour.

The bug was reported by Suneal at zkSecurity. Note: the impacted proofs were only insecure when the prover was already buggy; a correct circuit was never affected. The fix is still a hard requirement because it preserves soundness against adversarial provers.

4. Failure modes

• Inserting (commitment, point, evaluation) triples in non-deterministic order. Pre-0.3.1, this changed proof bytes silently. Post-0.3.1, it returns Error::OpeningError on the prover side; do not catch this error.
• Sharing a query type between prover and verifier without rerunning the bucketing. The verifier rebuilds the buckets from scratch using the same (point, commitment) keys. If your prover deduplicated the queries but your verifier did not, you will get a verifier mismatch.
• Forgetting kate_division on a non-monic divisor. kate_division assumes division by $X - b$. The multiopen prover uses it on the polynomial $Z_X(X)$ that is not $X - b$; the prover instead uses an explicit division by evaluating $Z_X$ on the extended domain and inverting pointwise. Read the prover code carefully before extending it.

5. Spec pointers

• Halo paper, eprint 2019/1021, section "Polynomial commitments" includes the original multiopen construction.
• The Halo 2 Book Multipoint opening argument chapter derives the same construction with worked notation.
• The zkSecurity write-up of the 2025 disclosure (search "zkSecurity halo2 multiopen"); the GitHub advisory is GHSA-fmqx-q3p4-mrj9.

6. Exercises

1. Open halo2_proofs/src/poly/multiopen.rs and find each of the four challenge type aliases $x_1, x_2, x_3, x_4$. Map each to the step in section 3.3 above.
2. Read halo2_proofs/CHANGELOG.md's 0.3.1 entry. Identify the version's full security text and note the role indexmap plays in the fix.
3. Write a small Rust harness that asks create_proof to open the same (point, commitment) twice with different evaluations. Confirm that the current code returns Error::OpeningError. (Hint: the easiest way is to construct two ProverQuery values directly and call create_proof from poly::multiopen with them.)
4. The prover commits to a single polynomial $f$ that combines every bucket. Why does this give a proof size of $O(\log n)$ in $n$ rather than $O((\text{number of buckets}) \log n)$?

Answers in the code

• Exercise 1: $x_1$ at line ~22, $x_2$ at line ~27, $x_3$ at line ~32, $x_4$ at line ~37 in halo2_proofs/src/poly/multiopen.rs.
• Exercise 4: combining the per-bucket quotient polynomials into a single $f$ collapses everything to one polynomial of degree $\leq n$; only one IPA opening is required.

7. Further reading

• The Halo 2 Book chapter on the multipoint opening argument.
• The halo2 GitHub Security Advisory GHSA-fmqx-q3p4-mrj9 for the full disclosure timeline.