Skip to main content

binius_spartan_frontend/
constraint_system.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::{
5	cmp::Ordering,
6	collections::HashMap,
7	mem,
8	ops::{Index, IndexMut},
9};
10
11use binius_field::Field;
12use binius_utils::checked_arithmetics::log2_ceil_usize;
13use smallvec::{SmallVec, smallvec};
14
15#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
16pub enum WireKind {
17	Constant,
18	InOut,
19	/// A wire whose value is a pure function of public-derivable inputs (constants, inout, and
20	/// other derived wires). Derived wires live in the public segment and emit no constraint; the
21	/// verifier recomputes them itself via the `InstanceGenerator`.
22	Derived,
23	Precommit,
24	Private,
25}
26
27impl WireKind {
28	/// The witness segment a wire of this kind lives in: constants, inout, and derived wires occupy
29	/// the public segment; precommit and private wires occupy their own segments.
30	pub const fn segment(self) -> WitnessSegment {
31		match self {
32			WireKind::Constant | WireKind::InOut | WireKind::Derived => WitnessSegment::Public,
33			WireKind::Precommit => WitnessSegment::Precommit,
34			WireKind::Private => WitnessSegment::Private,
35		}
36	}
37
38	/// Returns whether this wire kind lives in the public segment: its value is determined once the
39	/// public inputs (constants and inout) are known, so the verifier can recompute it without any
40	/// secret data.
41	///
42	/// Shared by all `CircuitBuilder` implementations so they make identical derived-vs-private
43	/// decisions. The output of a binary op (or hint) is [`WireKind::Derived`] iff every input is
44	/// public, and [`WireKind::Private`] otherwise.
45	pub fn is_public(self) -> bool {
46		self.segment() == WitnessSegment::Public
47	}
48}
49
50#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
51pub struct ConstraintWire {
52	pub(crate) kind: WireKind,
53	pub(crate) id: u32,
54}
55
56impl ConstraintWire {
57	/// Creates a constraint wire referencing an inout wire by ID.
58	///
59	/// TODO: This is not ideal, and instead we should use some sort of allocator.
60	pub const fn inout(id: u32) -> Self {
61		Self {
62			kind: WireKind::InOut,
63			id,
64		}
65	}
66
67	/// The wire's ID, its index among the wires of its kind.
68	pub const fn id(&self) -> u32 {
69		self.id
70	}
71
72	/// Creates a constraint wire referencing a precommit wire by ID.
73	pub const fn precommit(id: u32) -> Self {
74		Self {
75			kind: WireKind::Precommit,
76			id,
77		}
78	}
79}
80
81#[derive(Debug, Clone)]
82pub struct Operand<W>(SmallVec<[W; 4]>);
83
84impl<W> Default for Operand<W> {
85	fn default() -> Self {
86		Operand(SmallVec::new())
87	}
88}
89
90impl<W: Copy + Ord> Operand<W> {
91	pub fn new(mut term: SmallVec<[W; 4]>) -> Self {
92		term.sort_unstable();
93
94		let has_duplicate_wire = term.windows(2).any(|w| w[0] == w[1]);
95		let term = if has_duplicate_wire {
96			term.chunk_by(|a, b| a == b)
97				.flat_map(|group| {
98					// Group is a slice of wires that are all equal. We want to return an empty
99					// iterator if the group is even length and a singleton iterator otherwise.
100					let last_even_idx = group.len() / 2 * 2;
101					group[last_even_idx..].iter().copied()
102				})
103				.collect()
104		} else {
105			term
106		};
107
108		Self(term)
109	}
110
111	pub fn len(&self) -> usize {
112		self.0.len()
113	}
114
115	pub fn is_empty(&self) -> bool {
116		self.0.is_empty()
117	}
118
119	pub fn wires(&self) -> &[W] {
120		&self.0
121	}
122
123	pub fn merge(&mut self, rhs: &Self) -> (Operand<W>, Operand<W>) {
124		// Classic merge algorithm for sorted vectors, but where duplicate items cancel out.
125		let lhs = mem::take(&mut self.0);
126		let dst = &mut self.0;
127
128		let mut lhs_iter = lhs.into_iter().peekable();
129		let mut rhs_iter = rhs.0.iter().copied().peekable();
130
131		let mut additions = Operand::default();
132		let mut removals = Operand::default();
133
134		loop {
135			match (lhs_iter.peek(), rhs_iter.peek()) {
136				(Some(next_lhs), Some(next_rhs)) => {
137					match next_lhs.cmp(next_rhs) {
138						Ordering::Equal => {
139							// Advance both iterators, but don't push the wires because they cancel.
140							let wire = lhs_iter.next().expect("peek returned Some");
141							let _ = rhs_iter.next().expect("peek returned Some");
142
143							removals.0.push(wire);
144						}
145						Ordering::Less => dst.push(lhs_iter.next().expect("peek returned Some")),
146						Ordering::Greater => {
147							let wire = rhs_iter.next().expect("peek returned Some");
148							additions.0.push(wire);
149							dst.push(wire);
150						}
151					}
152				}
153				(Some(_), None) => dst.push(lhs_iter.next().expect("peek returned Some")),
154				(None, Some(_)) => {
155					let wire = rhs_iter.next().expect("peek returned Some");
156					additions.0.push(wire);
157					dst.push(wire);
158				}
159				(None, None) => break,
160			}
161		}
162
163		(additions, removals)
164	}
165}
166
167impl<W> From<W> for Operand<W> {
168	fn from(value: W) -> Self {
169		Operand(smallvec![value])
170	}
171}
172
173#[derive(Debug, Clone)]
174pub struct MulConstraint<W> {
175	pub a: Operand<W>,
176	pub b: Operand<W>,
177	pub c: Operand<W>,
178}
179
180#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
181pub enum WitnessSegment {
182	/// The public segment contains constant and input/output witness values.
183	Public,
184	/// The precommit segment contains values committed in a separate oracle before the private
185	/// segment. These are zero-knowledge hidden but not prunable or rearrangeable.
186	Precommit,
187	/// The private segment contains the remaining witness values, which are hidden from the
188	/// verifier.
189	Private,
190}
191
192#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
193pub struct WitnessIndex {
194	pub segment: WitnessSegment,
195	pub index: u32,
196}
197
198impl WitnessIndex {
199	pub const fn public(index: u32) -> Self {
200		Self {
201			segment: WitnessSegment::Public,
202			index,
203		}
204	}
205
206	pub const fn precommit(index: u32) -> Self {
207		Self {
208			segment: WitnessSegment::Precommit,
209			index,
210		}
211	}
212
213	pub const fn private(index: u32) -> Self {
214		Self {
215			segment: WitnessSegment::Private,
216			index,
217		}
218	}
219}
220
221pub struct Witness<F> {
222	public: Vec<F>,
223	precommit: Vec<F>,
224	private: Vec<F>,
225}
226
227impl<F> Witness<F> {
228	pub const fn new(public: Vec<F>, precommit: Vec<F>, private: Vec<F>) -> Self {
229		Self {
230			public,
231			precommit,
232			private,
233		}
234	}
235
236	pub fn public(&self) -> &[F] {
237		&self.public
238	}
239
240	pub fn precommit(&self) -> &[F] {
241		&self.precommit
242	}
243
244	pub fn private(&self) -> &[F] {
245		&self.private
246	}
247}
248
249impl<F> Index<WitnessIndex> for Witness<F> {
250	type Output = F;
251
252	fn index(&self, index: WitnessIndex) -> &Self::Output {
253		match index.segment {
254			WitnessSegment::Public => &self.public[index.index as usize],
255			WitnessSegment::Precommit => &self.precommit[index.index as usize],
256			WitnessSegment::Private => &self.private[index.index as usize],
257		}
258	}
259}
260
261impl<F> IndexMut<WitnessIndex> for Witness<F> {
262	fn index_mut(&mut self, index: WitnessIndex) -> &mut Self::Output {
263		match index.segment {
264			WitnessSegment::Public => &mut self.public[index.index as usize],
265			WitnessSegment::Precommit => &mut self.precommit[index.index as usize],
266			WitnessSegment::Private => &mut self.private[index.index as usize],
267		}
268	}
269}
270
271/// A constraint system with multiplication constraints over witness indices.
272///
273/// Contains multiplication constraints of the form `A * B = C` where A, B, C are operands
274/// (XOR combinations of witness values). Constraints directly reference [`WitnessIndex`]
275/// positions in the witness array.
276///
277/// This struct does not guarantee power-of-two constraint counts or witness size.
278#[derive(Debug, Clone)]
279pub struct ConstraintSystem<F: Field> {
280	constants: Vec<F>,
281	n_inout: u32,
282	n_precommit: u32,
283	n_private: u32,
284	log_public: u32,
285	mul_constraints: Vec<MulConstraint<WitnessIndex>>,
286	one_wire_index: u32,
287}
288
289impl<F: Field> ConstraintSystem<F> {
290	/// Create a new constraint system.
291	pub const fn new(
292		constants: Vec<F>,
293		n_inout: u32,
294		n_precommit: u32,
295		n_private: u32,
296		log_public: u32,
297		mul_constraints: Vec<MulConstraint<WitnessIndex>>,
298		one_wire_index: u32,
299	) -> Self {
300		Self {
301			constants,
302			n_inout,
303			n_precommit,
304			n_private,
305			log_public,
306			mul_constraints,
307			one_wire_index,
308		}
309	}
310
311	pub fn constants(&self) -> &[F] {
312		&self.constants
313	}
314
315	pub const fn n_inout(&self) -> u32 {
316		self.n_inout
317	}
318
319	pub const fn n_precommit(&self) -> u32 {
320		self.n_precommit
321	}
322
323	pub const fn n_private(&self) -> u32 {
324		self.n_private
325	}
326
327	pub const fn log_public(&self) -> u32 {
328		self.log_public
329	}
330
331	pub const fn n_public(&self) -> u32 {
332		1 << self.log_public
333	}
334
335	pub fn mul_constraints(&self) -> &[MulConstraint<WitnessIndex>] {
336		&self.mul_constraints
337	}
338
339	pub const fn one_wire(&self) -> WitnessIndex {
340		WitnessIndex {
341			segment: WitnessSegment::Public,
342			index: self.one_wire_index,
343		}
344	}
345
346	/// Validate that a witness satisfies all multiplication constraints.
347	pub fn validate(&self, witness: &Witness<F>) {
348		let operand_val = |operand: &Operand<WitnessIndex>| {
349			operand.wires().iter().map(|&idx| witness[idx]).sum::<F>()
350		};
351
352		for MulConstraint { a, b, c } in &self.mul_constraints {
353			assert_eq!(operand_val(a) * operand_val(b), operand_val(c));
354		}
355	}
356}
357
358/// Random padding appended to a committed segment.
359///
360/// The padding masks the evaluations of the segment sent in the clear. (The codeword symbols FRI
361/// opens are hidden by the ZK pad in the BaseFold layer.)
362/// Every committed segment carries the same amount, so each is padded on its own.
363#[derive(Debug, Clone, Copy)]
364pub struct BlindingInfo {
365	/// The number of random dummy multiplication constraints that must be added.
366	pub n_dummy_constraints: usize,
367}
368
369/// Dummy multiplication constraints appended to every committed segment.
370///
371/// A wire in no constraint has coefficient zero in the wiring relation.
372/// So no count of plain dummy wires masks a value the relation reveals.
373///
374/// The three wires of a dummy constraint do sit in a constraint, so they reach the relation.
375///
376/// # Why this value
377///
378/// Everything verification publishes touches a committed segment only through that segment's
379/// three operand contributions `(A_S, B_S, C_S)`. The operand evaluations are those plus the
380/// other segments' shares, and the segment's own batched claim is `A_S + lambda * B_S +
381/// lambda^2 * C_S`, already in their span. So three values need masking, not four.
382///
383/// One dummy constraint cannot mask them. Its wires contribute `(alpha * a, alpha * b,
384/// alpha * a * b)`, because the prover pins the third wire to the product of the other two.
385/// Its share of `C_S` is therefore fixed by its shares of `A_S` and `B_S`, and a verifier
386/// holding all three recovers a relation among the real wires.
387///
388/// Two constraints break that: `a` and `b` of each are free, and the distribution they induce
389/// on `(A_S, B_S, C_S)` is statistically close to uniform.
390const N_DUMMY_CONSTRAINTS: usize = 2;
391
392impl Default for BlindingInfo {
393	fn default() -> Self {
394		Self {
395			n_dummy_constraints: N_DUMMY_CONSTRAINTS,
396		}
397	}
398}
399
400#[derive(Debug, Clone)]
401pub struct WitnessLayout<F: Field> {
402	pub(crate) constants: Vec<F>,
403	n_inout: u32,
404	n_derived: u32,
405	n_precommit: u32,
406	n_private: u32,
407	log_public: u32,
408	log_precommit: u32,
409	log_private: u32,
410	derived_index_map: HashMap<u32, u32>,
411	private_index_map: HashMap<u32, u32>,
412}
413
414impl<F: Field> WitnessLayout<F> {
415	pub fn sparse(
416		constants: Vec<F>,
417		n_inout: u32,
418		n_precommit: u32,
419		derived_alive: &[bool],
420		private_alive: &[bool],
421	) -> Self {
422		let n_constants = constants.len() as u32;
423		let log_precommit = log2_ceil_usize(n_precommit as usize) as u32;
424
425		// Derived wires occupy the public segment after constants and inout. Only derived wires
426		// referenced by a surviving constraint need a slot; intermediates that feed only other
427		// derived wires are computed inline by the generators and get no slot.
428		let derived_index_map = derived_alive
429			.iter()
430			.enumerate()
431			.filter(|(_, alive)| **alive)
432			.enumerate()
433			.map(|(new_idx, (id, _))| (id as u32, new_idx as u32))
434			.collect::<HashMap<_, _>>();
435
436		let n_derived = derived_index_map.len() as u32;
437		let n_public = n_constants + n_inout + n_derived;
438		let log_public = log2_ceil_usize(n_public as usize) as u32;
439
440		let private_index_map = private_alive
441			.iter()
442			.enumerate()
443			.filter(|(_, alive)| **alive)
444			.enumerate()
445			.map(|(new_idx, (id, _))| (id as u32, new_idx as u32))
446			.collect::<HashMap<_, _>>();
447
448		let n_private = private_index_map.len() as u32;
449		let log_private = log2_ceil_usize(n_private as usize) as u32;
450
451		Self {
452			constants,
453			n_inout,
454			n_derived,
455			n_precommit,
456			n_private,
457			log_public,
458			log_precommit,
459			log_private,
460			derived_index_map,
461			private_index_map,
462		}
463	}
464
465	pub fn with_blinding(self, info: BlindingInfo) -> Self {
466		// Both committed segments carry the same blinding: 3 wires per dummy constraint, which
467		// mask the evaluations sent in the clear.
468		//
469		// Keep this in sync with the padded constraint system in the verifier crate.
470		let blinding_size = 3 * info.n_dummy_constraints;
471
472		let total_precommit = self.n_precommit as usize + blinding_size;
473		let log_precommit = log2_ceil_usize(total_precommit) as u32;
474
475		let total_private = self.n_private as usize + blinding_size;
476		let log_private = log2_ceil_usize(total_private) as u32;
477
478		Self {
479			log_precommit,
480			log_private,
481			..self
482		}
483	}
484
485	pub const fn public_size(&self) -> usize {
486		1 << self.log_public as usize
487	}
488
489	pub const fn precommit_size(&self) -> usize {
490		1 << self.log_precommit as usize
491	}
492
493	pub const fn private_size(&self) -> usize {
494		1 << self.log_private as usize
495	}
496
497	pub const fn n_constants(&self) -> usize {
498		self.constants.len()
499	}
500
501	pub const fn n_inout(&self) -> usize {
502		self.n_inout as usize
503	}
504
505	pub const fn n_derived(&self) -> usize {
506		self.n_derived as usize
507	}
508
509	pub const fn n_precommit(&self) -> usize {
510		self.n_precommit as usize
511	}
512
513	pub const fn n_private(&self) -> usize {
514		self.n_private as usize
515	}
516
517	pub const fn log_public(&self) -> u32 {
518		self.log_public
519	}
520
521	pub const fn log_precommit(&self) -> u32 {
522		self.log_precommit
523	}
524
525	pub const fn log_private(&self) -> u32 {
526		self.log_private
527	}
528
529	pub fn get(&self, wire: &ConstraintWire) -> Option<WitnessIndex> {
530		match wire.kind {
531			WireKind::Constant => {
532				assert!((wire.id as usize) < self.constants.len());
533				Some(WitnessIndex::public(wire.id))
534			}
535			WireKind::InOut => {
536				assert!(wire.id < self.n_inout);
537				Some(WitnessIndex::public(self.constants.len() as u32 + wire.id))
538			}
539			WireKind::Derived => self.derived_index_map.get(&wire.id).map(|&derived_idx| {
540				WitnessIndex::public(self.constants.len() as u32 + self.n_inout + derived_idx)
541			}),
542			WireKind::Precommit => {
543				assert!(wire.id < self.n_precommit);
544				Some(WitnessIndex::precommit(wire.id))
545			}
546			WireKind::Private => self
547				.private_index_map
548				.get(&wire.id)
549				.map(|&id| WitnessIndex::private(id)),
550		}
551	}
552}
553
554#[cfg(test)]
555mod tests {
556	use smallvec::smallvec;
557
558	use super::*;
559
560	#[test]
561	fn test_wires_added_mod2() {
562		// Create 4 wires with different kinds to ensure proper sorting
563		let w = [
564			ConstraintWire {
565				kind: WireKind::Constant,
566				id: 0,
567			},
568			ConstraintWire {
569				kind: WireKind::InOut,
570				id: 0,
571			},
572			ConstraintWire {
573				kind: WireKind::Private,
574				id: 0,
575			},
576			ConstraintWire {
577				kind: WireKind::Private,
578				id: 1,
579			},
580		];
581
582		// Input sequence: w[0], w[2], w[2], w[3], w[3], w[1], w[2], w[1], w[3], w[3]
583		// Counts: w[0]=1, w[1]=2, w[2]=3, w[3]=4
584		// After mod 2: w[0]=1, w[1]=0, w[2]=1, w[3]=0
585		let input = smallvec![w[0], w[2], w[2], w[3], w[3], w[1], w[2], w[1], w[3], w[3]];
586		let operand = Operand::new(input);
587
588		// Expected result: w[0], w[2] (sorted)
589		assert_eq!(operand.wires(), &[w[0], w[2]]);
590	}
591
592	#[test]
593	fn test_sorting_when_no_duplicates() {
594		// Create 4 wires with different kinds to ensure proper sorting
595		let w = [
596			ConstraintWire {
597				kind: WireKind::Constant,
598				id: 0,
599			},
600			ConstraintWire {
601				kind: WireKind::InOut,
602				id: 0,
603			},
604			ConstraintWire {
605				kind: WireKind::Private,
606				id: 0,
607			},
608			ConstraintWire {
609				kind: WireKind::Private,
610				id: 1,
611			},
612		];
613
614		// Input sequence: w[2], w[3], w[0], w[1]
615		let input = smallvec![w[2], w[3], w[0], w[1]];
616		let operand = Operand::new(input);
617
618		// Expected result: w[0], w[1], w[2], w[3] (sorted by WireKind then ID)
619		assert_eq!(operand.wires(), &[w[0], w[1], w[2], w[3]]);
620	}
621
622	#[test]
623	fn test_merge() {
624		// Create 4 wires with different kinds to ensure proper sorting
625		let w = [
626			ConstraintWire {
627				kind: WireKind::Constant,
628				id: 0,
629			},
630			ConstraintWire {
631				kind: WireKind::InOut,
632				id: 0,
633			},
634			ConstraintWire {
635				kind: WireKind::Private,
636				id: 0,
637			},
638			ConstraintWire {
639				kind: WireKind::Private,
640				id: 1,
641			},
642		];
643
644		// Test case 1: merge([w[0]], [])
645		let mut lhs = Operand(smallvec![w[0]]);
646		let rhs = Operand(smallvec![]);
647		let (additions, removals) = lhs.merge(&rhs);
648		assert_eq!(lhs.wires(), &[w[0]]);
649		assert_eq!(additions.wires(), &[]);
650		assert_eq!(removals.wires(), &[]);
651
652		// Test case 2: merge([], [w[0]])
653		let mut lhs = Operand(smallvec![]);
654		let rhs = Operand(smallvec![w[0]]);
655		let (additions, removals) = lhs.merge(&rhs);
656		assert_eq!(lhs.wires(), &[w[0]]);
657		assert_eq!(additions.wires(), &[w[0]]);
658		assert_eq!(removals.wires(), &[]);
659
660		// Test case 3: merge([w[0]], [w[0]])
661		let mut lhs = Operand(smallvec![w[0]]);
662		let rhs = Operand(smallvec![w[0]]);
663		let (additions, removals) = lhs.merge(&rhs);
664		assert_eq!(lhs.wires(), &[]);
665		assert_eq!(additions.wires(), &[]);
666		assert_eq!(removals.wires(), &[w[0]]);
667
668		// Test case 4: merge([w[0]], [w[1]])
669		let mut lhs = Operand(smallvec![w[0]]);
670		let rhs = Operand(smallvec![w[1]]);
671		let (additions, removals) = lhs.merge(&rhs);
672		assert_eq!(lhs.wires(), &[w[0], w[1]]);
673		assert_eq!(additions.wires(), &[w[1]]);
674		assert_eq!(removals.wires(), &[]);
675
676		// Test case 5: merge([w[0]], [w[0], w[1]])
677		let mut lhs = Operand(smallvec![w[0]]);
678		let rhs = Operand(smallvec![w[0], w[1]]);
679		let (additions, removals) = lhs.merge(&rhs);
680		assert_eq!(lhs.wires(), &[w[1]]);
681		assert_eq!(additions.wires(), &[w[1]]);
682		assert_eq!(removals.wires(), &[w[0]]);
683
684		// Test case 6: merge([w[0], w[2]], [w[1], w[3]])
685		let mut lhs = Operand(smallvec![w[0], w[2]]);
686		let rhs = Operand(smallvec![w[1], w[3]]);
687		let (additions, removals) = lhs.merge(&rhs);
688		assert_eq!(lhs.wires(), &[w[0], w[1], w[2], w[3]]);
689		assert_eq!(additions.wires(), &[w[1], w[3]]);
690		assert_eq!(removals.wires(), &[]);
691
692		// Test case 7: merge([w[0], w[2]], [w[0], w[1], w[2], w[3]])
693		let mut lhs = Operand(smallvec![w[0], w[2]]);
694		let rhs = Operand(smallvec![w[0], w[1], w[2], w[3]]);
695		let (additions, removals) = lhs.merge(&rhs);
696		assert_eq!(lhs.wires(), &[w[1], w[3]]);
697		assert_eq!(additions.wires(), &[w[1], w[3]]);
698		assert_eq!(removals.wires(), &[w[0], w[2]]);
699	}
700}