Skip to main content

binius_spartan_verifier/
constraint_system.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use binius_field::Field;
5use binius_ip::libra::mask_buffer_dimensions;
6pub use binius_spartan_frontend::constraint_system::BlindingInfo;
7use binius_spartan_frontend::constraint_system::{
8	ConstraintSystem, MulConstraint, Operand, Witness, WitnessIndex,
9};
10use binius_utils::checked_arithmetics::{checked_log_2, log2_ceil_usize};
11
12/// A constraint system with blinding and power-of-two padding.
13///
14/// Wraps a [`ConstraintSystem`], adds dummy constraints for blinding, and pads the total
15/// number of constraints to a power of two (required by the prover's multilinear extension
16/// protocol).
17#[derive(Debug, Clone)]
18pub struct ConstraintSystemPadded<F: Field> {
19	inner: ConstraintSystem<F>,
20	precommit_len: usize,
21	private_len: usize,
22	blinding_info: BlindingInfo,
23	mul_constraints: Vec<MulConstraint<WitnessIndex>>,
24	/// Mask buffer dimensions (m_n, m_d) for the ZK mulcheck mask polynomial.
25	mask_dims: (usize, usize),
26}
27
28impl<F: Field> ConstraintSystemPadded<F> {
29	/// Create a new padded constraint system with blinding.
30	///
31	/// This:
32	/// 1. Adds dummy multiplication constraints for blinding (3 wires each: A * B = C)
33	/// 2. Pads the total constraint count to a power of two with `one * one = one` constraints
34	/// 3. Calculates the log_size based on witness requirements
35	/// 4. Computes mask buffer dimensions for the ZK mulcheck mask polynomial
36	pub fn new(cs: ConstraintSystem<F>, blinding_info: BlindingInfo) -> Self {
37		let mut mul_constraints = cs.mul_constraints().to_vec();
38
39		/// Adds dummy blinding constraints for a segment and returns its length with blinding.
40		fn add_blinding_constraints(
41			mul_constraints: &mut Vec<MulConstraint<WitnessIndex>>,
42			make_index: fn(u32) -> WitnessIndex,
43			n_circuit_wires: usize,
44			n_dummy_constraints: usize,
45		) -> usize {
46			let dummy_base = n_circuit_wires;
47			for i in 0..n_dummy_constraints {
48				let a = make_index((dummy_base + 3 * i) as u32);
49				let b = make_index((dummy_base + 3 * i + 1) as u32);
50				let c = make_index((dummy_base + 3 * i + 2) as u32);
51				mul_constraints.push(MulConstraint {
52					a: Operand::from(a),
53					b: Operand::from(b),
54					c: Operand::from(c),
55				});
56			}
57
58			n_circuit_wires + 3 * n_dummy_constraints
59		}
60
61		// Both committed segments have evaluations revealed in the clear, so both need dummy
62		// constraints to carry randomness into the wiring relation that masks them.
63		let precommit_len = add_blinding_constraints(
64			&mut mul_constraints,
65			WitnessIndex::precommit,
66			cs.n_precommit() as usize,
67			blinding_info.n_dummy_constraints,
68		);
69		let private_len = add_blinding_constraints(
70			&mut mul_constraints,
71			WitnessIndex::private,
72			cs.n_private() as usize,
73			blinding_info.n_dummy_constraints,
74		);
75
76		// Pad to next power of two with `one * one = one` constraints
77		let one_operand = Operand::from(cs.one_wire());
78		let current_len = mul_constraints.len();
79		mul_constraints.resize(
80			current_len.next_power_of_two(),
81			MulConstraint {
82				a: one_operand.clone(),
83				b: one_operand.clone(),
84				c: one_operand,
85			},
86		);
87
88		// Calculate mask buffer dimensions
89		let log_mul_constraints = checked_log_2(mul_constraints.len());
90		let mask_degree = 2; // quadratic composition
91		let mask_dims = mask_buffer_dimensions(log_mul_constraints, mask_degree);
92
93		Self {
94			inner: cs,
95			precommit_len,
96			private_len,
97			blinding_info,
98			mul_constraints,
99			mask_dims,
100		}
101	}
102
103	pub fn constants(&self) -> &[F] {
104		self.inner.constants()
105	}
106
107	pub const fn n_inout(&self) -> u32 {
108		self.inner.n_inout()
109	}
110
111	pub const fn n_precommit(&self) -> u32 {
112		self.inner.n_precommit()
113	}
114
115	pub const fn n_private(&self) -> u32 {
116		self.inner.n_private()
117	}
118
119	pub const fn log_public(&self) -> u32 {
120		self.inner.log_public()
121	}
122
123	pub const fn n_public(&self) -> u32 {
124		self.inner.n_public()
125	}
126
127	pub const fn one_wire(&self) -> WitnessIndex {
128		self.inner.one_wire()
129	}
130
131	/// The precommit segment's length with blinding: the entries past it are zero padding.
132	pub const fn precommit_len(&self) -> usize {
133		self.precommit_len
134	}
135
136	pub const fn log_precommit(&self) -> u32 {
137		log2_ceil_usize(self.precommit_len) as u32
138	}
139
140	pub const fn precommit_size(&self) -> usize {
141		1 << self.log_precommit() as usize
142	}
143
144	/// The private segment's length with blinding: the entries past it are zero padding.
145	pub const fn private_len(&self) -> usize {
146		self.private_len
147	}
148
149	pub const fn log_private(&self) -> u32 {
150		log2_ceil_usize(self.private_len) as u32
151	}
152
153	pub const fn private_size(&self) -> usize {
154		1 << self.log_private() as usize
155	}
156
157	pub const fn blinding_info(&self) -> &BlindingInfo {
158		&self.blinding_info
159	}
160
161	pub fn mul_constraints(&self) -> &[MulConstraint<WitnessIndex>] {
162		&self.mul_constraints
163	}
164
165	/// Returns the mask buffer dimensions (m_n, m_d) for the ZK mulcheck mask polynomial.
166	pub const fn mask_dims(&self) -> (usize, usize) {
167		self.mask_dims
168	}
169
170	pub fn validate(&self, witness: &Witness<F>) {
171		assert_eq!(witness.public().len(), 1 << self.log_public() as usize);
172		assert_eq!(witness.private().len(), self.private_size());
173
174		let operand_val = |operand: &Operand<WitnessIndex>| {
175			operand.wires().iter().map(|&idx| witness[idx]).sum::<F>()
176		};
177
178		for MulConstraint { a, b, c } in &self.mul_constraints {
179			assert_eq!(operand_val(a) * operand_val(b), operand_val(c));
180		}
181	}
182}
183
184#[cfg(test)]
185mod tests {
186	use std::collections::BTreeSet;
187
188	use binius_field::Ghash128b as B128;
189	use binius_spartan_frontend::{
190		circuit_builder::{CircuitBuilder, ConstraintBuilder},
191		compiler::compile,
192		constraint_system::WitnessSegment,
193	};
194
195	use super::*;
196
197	#[test]
198	fn every_committed_segment_reserves_room_for_its_dummy_constraints() {
199		// Any circuit will do: blinding is padding appended after whatever real wires exist.
200		let mut builder = ConstraintBuilder::<B128>::new();
201		let x = builder.alloc_inout();
202		let y = builder.alloc_inout();
203		builder.assert_eq(x, y);
204		let (cs, _layout) = compile(builder);
205
206		let n_precommit = cs.n_precommit() as usize;
207		let n_private = cs.n_private() as usize;
208
209		let info = BlindingInfo::default();
210		let padded = ConstraintSystemPadded::new(cs, info);
211
212		// Each segment is rounded up to a power of two, so its reserved size must still cover
213		// every real wire plus the 3 wires of each dummy constraint.
214		let blinding = 3 * info.n_dummy_constraints;
215		assert!(padded.precommit_size() >= n_precommit + blinding);
216		assert!(padded.private_size() >= n_private + blinding);
217	}
218
219	#[test]
220	fn every_committed_segment_masks_its_revealed_evaluations() {
221		// A revealed evaluation weights each wire by its coefficient in the wiring relation.
222		//
223		// That relation only ever sums over wires that appear in a multiplication constraint, so
224		// a wire in no constraint is weighted by zero and can mask nothing.
225		//
226		// So the dummy constraints' wires must all appear in one to mask the evaluations.
227
228		let mut builder = ConstraintBuilder::<B128>::new();
229		let x = builder.alloc_inout();
230		let y = builder.alloc_inout();
231		builder.assert_eq(x, y);
232		let (cs, _layout) = compile(builder);
233
234		let n_circuit = [cs.n_precommit() as usize, cs.n_private() as usize];
235		let info = BlindingInfo::default();
236		let padded = ConstraintSystemPadded::new(cs, info);
237
238		// Collect, per segment, the wire indices the constraints actually touch.
239		let mut in_support = [BTreeSet::new(), BTreeSet::new()];
240		for constraint in padded.mul_constraints() {
241			for operand in [&constraint.a, &constraint.b, &constraint.c] {
242				for wire in operand.wires() {
243					let slot = match wire.segment {
244						WitnessSegment::Precommit => 0,
245						WitnessSegment::Private => 1,
246						WitnessSegment::Public => continue,
247					};
248					in_support[slot].insert(wire.index as usize);
249				}
250			}
251		}
252
253		for (segment, n_circuit) in in_support.iter().zip(n_circuit) {
254			// The dummy constraints follow, and all three of their wires must appear, or the
255			// evaluations revealed for this segment have nothing masking them.
256			let dummy_constraint_base = n_circuit;
257			for offset in 0..3 * info.n_dummy_constraints {
258				assert!(
259					segment.contains(&(dummy_constraint_base + offset)),
260					"a dummy constraint wire never reached the wiring relation"
261				);
262			}
263		}
264	}
265}