binius_core/protocols/sumcheck/
univariate_zerocheck.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use binius_field::{util::inner_product_unchecked, Field, TowerField};
4use binius_math::{CompositionPoly, EvaluationDomainFactory, IsomorphicEvaluationDomainFactory};
5use binius_utils::{bail, sorting::is_sorted_ascending};
6use tracing::instrument;
7
8use super::{
9	error::{Error, VerificationError},
10	verify::BatchVerifyStart,
11	zerocheck::ZerocheckClaim,
12};
13use crate::{
14	fiat_shamir::{CanSample, Challenger},
15	transcript::VerifierTranscript,
16};
17
18#[derive(Debug)]
19pub struct BatchZerocheckUnivariateOutput<F: Field> {
20	pub univariate_challenge: F,
21	pub batch_verify_start: BatchVerifyStart<F>,
22}
23
24/// Univariatized domain size.
25///
26/// Note that composition over univariatized multilinears has degree $d (2^n - 1)$ and
27/// can be uniquely determined by its evaluations on $d (2^n - 1) + 1$ points. We however
28/// deliberately round this number up to $d 2^n$ to be able to use additive NTT interpolation
29/// techniques on round evaluations.
30pub const fn domain_size(composition_degree: usize, skip_rounds: usize) -> usize {
31	composition_degree << skip_rounds
32}
33
34/// For zerocheck, we know that a honest prover would evaluate to zero on the skipped domain.
35pub const fn extrapolated_scalars_count(composition_degree: usize, skip_rounds: usize) -> usize {
36	composition_degree.saturating_sub(1) << skip_rounds
37}
38
39/// Verify a batched zerocheck univariate round.
40///
41/// Unlike `batch_verify`, all round evaluations are on a univariate domain of predetermined size,
42/// and batching happens over a single round. This method batches claimed univariatized evaluations
43/// of the underlying composites, checks that univariatized round polynomial agrees with them on
44/// challenge point, and outputs sumcheck claims for `batch_verify` on the remaining variables.
45#[instrument(skip_all, level = "debug")]
46pub fn batch_verify_zerocheck_univariate_round<F, Composition, Challenger_>(
47	claims: &[ZerocheckClaim<F, Composition>],
48	skip_rounds: usize,
49	transcript: &mut VerifierTranscript<Challenger_>,
50) -> Result<BatchZerocheckUnivariateOutput<F>, Error>
51where
52	F: TowerField,
53	Composition: CompositionPoly<F>,
54	Challenger_: Challenger,
55{
56	// Check that the claims are in descending order by n_vars
57	if !is_sorted_ascending(claims.iter().map(|claim| claim.n_vars()).rev()) {
58		bail!(Error::ClaimsOutOfOrder);
59	}
60
61	let max_n_vars = claims.first().map(|claim| claim.n_vars()).unwrap_or(0);
62	let min_n_vars = claims.last().map(|claim| claim.n_vars()).unwrap_or(0);
63
64	if max_n_vars - min_n_vars > skip_rounds {
65		bail!(VerificationError::IncorrectSkippedRoundsCount);
66	}
67
68	let max_domain_size = claims
69		.iter()
70		.map(|claim| {
71			domain_size(claim.max_individual_degree(), skip_rounds + claim.n_vars() - max_n_vars)
72		})
73		.max()
74		.unwrap_or(0);
75	let zeros_prefix_len = (1 << (skip_rounds + min_n_vars - max_n_vars)).min(max_domain_size);
76
77	let mut batch_coeffs = Vec::with_capacity(claims.len());
78	let mut max_degree = 0;
79	for claim in claims {
80		let next_batch_coeff = transcript.sample();
81		batch_coeffs.push(next_batch_coeff);
82		max_degree = max_degree.max(claim.max_individual_degree() + 1);
83	}
84
85	let round_evals = transcript
86		.message()
87		.read_scalar_slice(max_domain_size - zeros_prefix_len)?;
88	let univariate_challenge = transcript.sample();
89
90	let evaluation_domain = EvaluationDomainFactory::<F>::create(
91		&IsomorphicEvaluationDomainFactory::<F::Canonical>::default(),
92		max_domain_size,
93	)?;
94
95	let lagrange_coeffs = evaluation_domain.lagrange_evals(univariate_challenge);
96	let sum = inner_product_unchecked::<F, F>(
97		round_evals,
98		lagrange_coeffs[zeros_prefix_len..].iter().copied(),
99	);
100
101	let batch_verify_start = BatchVerifyStart {
102		batch_coeffs,
103		sum,
104		max_degree,
105		skip_rounds,
106	};
107
108	let output = BatchZerocheckUnivariateOutput {
109		univariate_challenge,
110		batch_verify_start,
111	};
112
113	Ok(output)
114}
binius_core/protocols/sumcheck/univariate_zerocheck.rs

binius_core/protocols/sumcheck/
univariate_zerocheck.rs
