Skip to main content

binius_verifier/protocols/
zero.rs

1// Copyright 2026 The Binius Developers
2
3//! The Zero reduction.
4//!
5//! A ZERO constraint asserts that one constraint array vanishes. Because the constraint is linear,
6//! the polynomial whose vanishing is at stake is the array's oblong-multilinearization `d_hat`
7//! itself, rather than a product of witness multilinears. A multilinear that vanishes on the cube
8//! is the zero polynomial, so a single evaluation at a point the prover could not predict certifies
9//! the constraints outright.
10//!
11//! The reduction therefore carries no prover message and no sumcheck round. Its whole output is the
12//! claim
13//!
14//! ```text
15//! d_hat(r_zhat_prime, rho) = 0
16//! ```
17//!
18//! which joins the BitAnd, IntMul and BinMul claims in the batch the shift reduction consumes. The
19//! shift reduction, running against the committed witness, is what certifies it: a violated ZERO
20//! constraint makes the true batched evaluation differ from the claimed one, and its final check
21//! fails.
22
23/// Builds the constraint point the Zero reduction closes at.
24///
25/// The reduction runs directly after the BitAnd sumcheck and evaluates at the constraint half of
26/// the point that sumcheck has just produced, `r_x_star`: `rho` is its
27/// length-`log_zero_constraints` prefix. The sumcheck runs over the longest of the AND, IMUL and
28/// BMUL arrays, so fresh challenges from `sample` extend `r_x_star` only when the ZERO array is
29/// longer still. The prover and verifier derive it identically, so `sample` draws the same
30/// challenges at the same point in both transcripts.
31///
32/// Asked for `max(r_x_star.len(), log_zero_constraints)` coordinates instead, it returns the
33/// unified constraint point every operation is claimed at a prefix of, `rho` included. It draws the
34/// same challenges either way.
35///
36/// `sample` stands in for the channel: the prover and verifier channel traits are unrelated, so one
37/// function can only reach both through a closure.
38///
39/// Every coordinate of `rho` is uniform and independent — those inherited from the BitAnd sumcheck
40/// are its per-round verifier challenges — so the soundness bound is plain Schwartz-Zippel on a
41/// polynomial the witness commitment pinned down before the first challenge was drawn. The
42/// reduction's *input* zerocheck challenges would serve too, but they open with the deterministic
43/// Rijndael coordinates, which carry no randomness and would need absorbing by a separate
44/// F_2-independence argument first.
45///
46/// Sharing the point with the BitAnd reduction is sound despite the resulting correlation: the Zero
47/// bound appeals only to the marginal distribution of the challenges it consumes, which reuse
48/// leaves untouched. What it does require is that every challenge be drawn after the witness is
49/// committed, which the phase ordering guarantees.
50pub fn reduction_point<F: Clone>(
51	r_x_star: &[F],
52	log_zero_constraints: usize,
53	mut sample: impl FnMut() -> F,
54) -> Vec<F> {
55	// Each set is padded to a power-of-two row count independently, so a ZERO set with more rows
56	// than every AND, IMUL and BMUL set runs past `r_x_star` and samples the rest.
57	(0..log_zero_constraints)
58		.map(|i| r_x_star.get(i).map_or_else(&mut sample, F::clone))
59		.collect()
60}
61
62#[cfg(test)]
63mod tests {
64	use super::*;
65
66	/// Panics if called: a point that fits inside the BitAnd point must sample nothing.
67	fn unused_sample() -> u32 {
68		panic!("no challenge should be sampled");
69	}
70
71	#[test]
72	fn test_reduction_point_truncates_when_zero_set_is_smaller() {
73		let bitand = [1u32, 2, 3, 4, 5];
74		assert_eq!(reduction_point(&bitand, 3, unused_sample), vec![1, 2, 3]);
75	}
76
77	#[test]
78	fn test_reduction_point_extends_when_zero_set_is_larger() {
79		let bitand = [1u32, 2, 3];
80		let mut extra = [7u32, 8].into_iter();
81		assert_eq!(
82			reduction_point(&bitand, 5, || extra.next().expect("two extra challenges")),
83			vec![1, 2, 3, 7, 8]
84		);
85	}
86
87	#[test]
88	fn test_reduction_point_of_equal_sets_is_the_bitand_point() {
89		let bitand = [1u32, 2, 3, 4];
90		assert_eq!(reduction_point(&bitand, 4, unused_sample), bitand.to_vec());
91	}
92
93	#[test]
94	fn test_reduction_point_of_an_empty_zero_set_is_empty() {
95		let bitand = [1u32, 2, 3, 4];
96		assert!(reduction_point(&bitand, 0, unused_sample).is_empty());
97	}
98}