binius_core/constraint_system/
system.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3use std::iter;
4
5use binius_utils::serialization::{DeserializeBytes, SerializationError, SerializeBytes};
6use bytes::{Buf, BufMut};
7
8use super::{
9	AndConstraint, BmulConstraint, ImulConstraint, Operand, ShiftVariant, ValueVec, ValueVecLayout,
10};
11use crate::{error::ConstraintSystemError, word::Word};
12
13/// The ConstraintSystem is the core data structure in Binius64 that defines the computational
14/// constraints to be proven in zero-knowledge. It represents a system of equations over 64-bit
15/// words that must be satisfied by a valid values vector [`ValueVec`].
16///
17/// # Clone
18///
19/// While this type is cloneable it may be expensive to do so since the constraint systems often
20/// can have millions of constraints.
21#[derive(Debug, Clone)]
22pub struct ConstraintSystem {
23	/// Description of the value vector layout expected by this constraint system.
24	pub value_vec_layout: ValueVecLayout,
25	/// The constants that this constraint system defines.
26	///
27	/// Those constants will be going to be available for constraints in the value vector. Those
28	/// are known to both prover and verifier.
29	pub constants: Vec<Word>,
30	/// List of AND constraints that must be satisfied by the values vector.
31	pub and_constraints: Vec<AndConstraint>,
32	/// List of IMUL constraints that must be satisfied by the values vector.
33	pub imul_constraints: Vec<ImulConstraint>,
34	/// List of BMUL constraints that must be satisfied by the values vector.
35	pub bmul_constraints: Vec<BmulConstraint>,
36}
37
38impl ConstraintSystem {
39	/// Serialization format version for compatibility checking
40	pub const SERIALIZATION_VERSION: u32 = 5;
41}
42
43impl ConstraintSystem {
44	/// Creates a new constraint system.
45	pub fn new(
46		constants: Vec<Word>,
47		value_vec_layout: ValueVecLayout,
48		and_constraints: Vec<AndConstraint>,
49		imul_constraints: Vec<ImulConstraint>,
50		bmul_constraints: Vec<BmulConstraint>,
51	) -> Self {
52		assert_eq!(constants.len(), value_vec_layout.n_const);
53		ConstraintSystem {
54			constants,
55			value_vec_layout,
56			and_constraints,
57			imul_constraints,
58			bmul_constraints,
59		}
60	}
61
62	/// Ensures that this constraint system is well-formed and ready for proving.
63	///
64	/// Specifically checks that:
65	///
66	/// - the value vec layout is [valid][`ValueVecLayout::validate`].
67	/// - every [shifted value index][super::ShiftedValueIndex] is canonical.
68	/// - referenced values indices are in the range.
69	/// - constraints do not reference values in the padding area.
70	/// - shifts amounts are valid.
71	pub fn validate(&self) -> Result<(), ConstraintSystemError> {
72		tracing::debug_span!("Validating constraint system");
73
74		// Validate the value vector layout
75		self.value_vec_layout.validate()?;
76
77		for (i, and) in self.and_constraints.iter().enumerate() {
78			for (operand, name) in iter::zip(&and.0, AndConstraint::OPERAND_NAMES) {
79				validate_operand(operand, &self.value_vec_layout, "and", i, name)?;
80			}
81		}
82		for (i, imul) in self.imul_constraints.iter().enumerate() {
83			for (operand, name) in iter::zip(&imul.0, ImulConstraint::OPERAND_NAMES) {
84				validate_operand(operand, &self.value_vec_layout, "imul", i, name)?;
85			}
86		}
87		for (i, bmul) in self.bmul_constraints.iter().enumerate() {
88			for (operand, name) in iter::zip(&bmul.0, BmulConstraint::OPERAND_NAMES) {
89				validate_operand(operand, &self.value_vec_layout, "bmul", i, name)?;
90			}
91		}
92
93		return Ok(());
94
95		fn validate_operand(
96			operand: &Operand,
97			value_vec_layout: &ValueVecLayout,
98			constraint_type: &'static str,
99			constraint_index: usize,
100			operand_name: &'static str,
101		) -> Result<(), ConstraintSystemError> {
102			for term in operand {
103				// check canonicity. SLL is the canonical form of the operand.
104				if term.amount == 0 && term.shift_variant != ShiftVariant::Sll {
105					return Err(ConstraintSystemError::NonCanonicalShift {
106						constraint_type,
107						constraint_index,
108						operand_name,
109					});
110				}
111				// Half-word (*32) variants cap at 32, full-width at 64.
112				let max_amount = term.shift_variant.max_amount();
113				if usize::from(term.amount) >= max_amount {
114					return Err(ConstraintSystemError::ShiftAmountTooLarge {
115						constraint_type,
116						constraint_index,
117						operand_name,
118						shift_amount: term.amount as usize,
119						max_amount,
120					});
121				}
122				// Check if the value index is out of bounds.
123				if value_vec_layout.is_committed_oob(term.value_index) {
124					return Err(ConstraintSystemError::OutOfRangeValueIndex {
125						constraint_type,
126						constraint_index,
127						operand_name,
128						value_index: term.value_index.0,
129						total_len: value_vec_layout.combined_len(),
130					});
131				}
132				// No value should refer to padding.
133				if value_vec_layout.is_padding(term.value_index) {
134					return Err(ConstraintSystemError::PaddingValueIndex {
135						constraint_type,
136						constraint_index,
137						operand_name,
138					});
139				}
140			}
141			Ok(())
142		}
143	}
144
145	/// [Validates][`Self::validate`] and prepares this constraint system for proving/verifying.
146	///
147	/// This function performs the following:
148	/// 1. Validates the value vector layout (including public input checks)
149	/// 2. Validates the constraints.
150	/// 3. Pads the AND, IMUL, and BMUL constraints to the next po2 size
151	pub fn validate_and_prepare(&mut self) -> Result<(), ConstraintSystemError> {
152		self.validate()?;
153
154		// Require all constraint types to have a power-of-two count. An empty IMUL (resp. BMUL)
155		// constraint set is kept at zero (rather than padded to a single dummy constraint) so the
156		// prover and verifier can skip the IntMul (resp. BinMul) reduction entirely — see
157		// `IOPProver::prove` / `IOPVerifier::verify`.
158		let and_target_size = self.and_constraints.len().next_power_of_two();
159		let imul_target_size = if self.imul_constraints.is_empty() {
160			0
161		} else {
162			self.imul_constraints.len().next_power_of_two()
163		};
164		let bmul_target_size = if self.bmul_constraints.is_empty() {
165			0
166		} else {
167			self.bmul_constraints.len().next_power_of_two()
168		};
169
170		self.and_constraints
171			.resize_with(and_target_size, AndConstraint::default);
172		self.imul_constraints
173			.resize_with(imul_target_size, ImulConstraint::default);
174		self.bmul_constraints
175			.resize_with(bmul_target_size, BmulConstraint::default);
176
177		Ok(())
178	}
179
180	#[cfg(test)]
181	fn add_and_constraint(&mut self, and_constraint: AndConstraint) {
182		self.and_constraints.push(and_constraint);
183	}
184
185	#[cfg(test)]
186	fn add_imul_constraint(&mut self, imul_constraint: ImulConstraint) {
187		self.imul_constraints.push(imul_constraint);
188	}
189
190	#[cfg(test)]
191	fn add_bmul_constraint(&mut self, bmul_constraint: BmulConstraint) {
192		self.bmul_constraints.push(bmul_constraint);
193	}
194
195	/// Returns the number of AND constraints in the system.
196	pub const fn n_and_constraints(&self) -> usize {
197		self.and_constraints.len()
198	}
199
200	/// Returns the number of IMUL  constraints in the system.
201	pub const fn n_imul_constraints(&self) -> usize {
202		self.imul_constraints.len()
203	}
204
205	/// Returns the number of BMUL constraints in the system.
206	pub const fn n_bmul_constraints(&self) -> usize {
207		self.bmul_constraints.len()
208	}
209
210	/// The total length of the [`ValueVec`] expected by this constraint system.
211	pub const fn value_vec_len(&self) -> usize {
212		self.value_vec_layout.combined_len()
213	}
214
215	/// Create a new [`ValueVec`] with the size expected by this constraint system.
216	pub fn new_value_vec(&self) -> ValueVec {
217		ValueVec::new(self.value_vec_layout.clone())
218	}
219}
220
221impl SerializeBytes for ConstraintSystem {
222	fn serialize(&self, mut write_buf: impl BufMut) -> Result<(), SerializationError> {
223		Self::SERIALIZATION_VERSION.serialize(&mut write_buf)?;
224
225		self.value_vec_layout.serialize(&mut write_buf)?;
226		self.constants.serialize(&mut write_buf)?;
227		self.and_constraints.serialize(&mut write_buf)?;
228		self.imul_constraints.serialize(&mut write_buf)?;
229		self.bmul_constraints.serialize(write_buf)
230	}
231}
232
233impl DeserializeBytes for ConstraintSystem {
234	fn deserialize(mut read_buf: impl Buf) -> Result<Self, SerializationError>
235	where
236		Self: Sized,
237	{
238		let version = u32::deserialize(&mut read_buf)?;
239		if version != Self::SERIALIZATION_VERSION {
240			return Err(SerializationError::InvalidConstruction {
241				name: "ConstraintSystem::version",
242			});
243		}
244
245		let value_vec_layout = ValueVecLayout::deserialize(&mut read_buf)?;
246		let constants = Vec::<Word>::deserialize(&mut read_buf)?;
247		let and_constraints = Vec::<AndConstraint>::deserialize(&mut read_buf)?;
248		let imul_constraints = Vec::<ImulConstraint>::deserialize(&mut read_buf)?;
249		let bmul_constraints = Vec::<BmulConstraint>::deserialize(read_buf)?;
250
251		if constants.len() != value_vec_layout.n_const {
252			return Err(SerializationError::InvalidConstruction {
253				name: "ConstraintSystem::constants",
254			});
255		}
256
257		Ok(ConstraintSystem {
258			value_vec_layout,
259			constants,
260			and_constraints,
261			imul_constraints,
262			bmul_constraints,
263		})
264	}
265}
266
267#[cfg(test)]
268mod tests {
269	use super::*;
270	use crate::constraint_system::{ShiftedValueIndex, ValueIndex, ValuesData};
271
272	pub(crate) fn create_test_constraint_system() -> ConstraintSystem {
273		let constants = vec![
274			Word::from_u64(1),
275			Word::from_u64(42),
276			Word::from_u64(0xDEADBEEF),
277		];
278
279		let value_vec_layout = ValueVecLayout {
280			n_const: 3,
281			n_inout: 2,
282			n_witness: 10,
283			n_internal: 3,
284			offset_inout: 4,   // Must be power of 2 and >= n_const
285			offset_witness: 8, // Must be power of 2 and >= offset_inout + n_inout
286			n_hidden_words: 8, // Must be power of 2 and >= offset_witness + n_witness
287			n_scratch: 0,
288		};
289
290		let and_constraints = vec![
291			AndConstraint::plain_abc(
292				vec![ValueIndex(0), ValueIndex(1)],
293				vec![ValueIndex(2)],
294				vec![ValueIndex(3), ValueIndex(4)],
295			),
296			AndConstraint::abc(
297				vec![ShiftedValueIndex::sll(ValueIndex(0), 5)],
298				vec![ShiftedValueIndex::srl(ValueIndex(1), 10)],
299				vec![ShiftedValueIndex::sar(ValueIndex(2), 15)],
300			),
301		];
302
303		let imul_constraints = vec![ImulConstraint([
304			vec![ShiftedValueIndex::plain(ValueIndex(0))],
305			vec![ShiftedValueIndex::plain(ValueIndex(1))],
306			vec![ShiftedValueIndex::plain(ValueIndex(2))],
307			vec![ShiftedValueIndex::plain(ValueIndex(3))],
308		])];
309
310		let bmul_constraints = vec![BmulConstraint([
311			vec![ShiftedValueIndex::plain(ValueIndex(0))],
312			vec![ShiftedValueIndex::plain(ValueIndex(1))],
313			vec![ShiftedValueIndex::plain(ValueIndex(2))],
314			vec![ShiftedValueIndex::plain(ValueIndex(3))],
315			vec![ShiftedValueIndex::plain(ValueIndex(4))],
316			vec![ShiftedValueIndex::sll(ValueIndex(0), 5)],
317		])];
318
319		ConstraintSystem::new(
320			constants,
321			value_vec_layout,
322			and_constraints,
323			imul_constraints,
324			bmul_constraints,
325		)
326	}
327
328	#[test]
329	fn test_constraint_system_serialization_round_trip() {
330		let original = create_test_constraint_system();
331
332		let mut buf = Vec::new();
333		original.serialize(&mut buf).unwrap();
334
335		let deserialized = ConstraintSystem::deserialize(&mut buf.as_slice()).unwrap();
336
337		// Check version
338		assert_eq!(ConstraintSystem::SERIALIZATION_VERSION, 5);
339
340		// Check value_vec_layout
341		assert_eq!(original.value_vec_layout, deserialized.value_vec_layout);
342
343		// Check constants
344		assert_eq!(original.constants.len(), deserialized.constants.len());
345		for (orig, deser) in original.constants.iter().zip(deserialized.constants.iter()) {
346			assert_eq!(orig, deser);
347		}
348
349		// Check and_constraints
350		assert_eq!(original.and_constraints.len(), deserialized.and_constraints.len());
351
352		// Check imul_constraints
353		assert_eq!(original.imul_constraints.len(), deserialized.imul_constraints.len());
354
355		// Check bmul_constraints
356		assert_eq!(original.bmul_constraints.len(), deserialized.bmul_constraints.len());
357	}
358
359	#[test]
360	fn test_constraint_system_version_mismatch() {
361		// Create a buffer with wrong version
362		let mut buf = Vec::new();
363		999u32.serialize(&mut buf).unwrap(); // Wrong version
364
365		let result = ConstraintSystem::deserialize(&mut buf.as_slice());
366		assert!(result.is_err());
367		match result.unwrap_err() {
368			SerializationError::InvalidConstruction { name } => {
369				assert_eq!(name, "ConstraintSystem::version");
370			}
371			_ => panic!("Expected InvalidConstruction error"),
372		}
373	}
374
375	#[test]
376	fn test_constraint_system_constants_length_mismatch() {
377		// Create valid components but with mismatched constants length
378		let value_vec_layout = ValueVecLayout {
379			n_const: 5, // Expect 5 constants
380			n_inout: 2,
381			n_witness: 10,
382			n_internal: 3,
383			offset_inout: 8,
384			offset_witness: 16,
385			n_hidden_words: 16,
386			n_scratch: 0,
387		};
388
389		let constants = vec![Word::from_u64(1), Word::from_u64(2)]; // Only 2 constants
390		let and_constraints: Vec<AndConstraint> = vec![];
391		let imul_constraints: Vec<ImulConstraint> = vec![];
392		let bmul_constraints: Vec<BmulConstraint> = vec![];
393
394		// Serialize components manually
395		let mut buf = Vec::new();
396		ConstraintSystem::SERIALIZATION_VERSION
397			.serialize(&mut buf)
398			.unwrap();
399		value_vec_layout.serialize(&mut buf).unwrap();
400		constants.serialize(&mut buf).unwrap();
401		and_constraints.serialize(&mut buf).unwrap();
402		imul_constraints.serialize(&mut buf).unwrap();
403		bmul_constraints.serialize(&mut buf).unwrap();
404
405		let result = ConstraintSystem::deserialize(&mut buf.as_slice());
406		assert!(result.is_err());
407		match result.unwrap_err() {
408			SerializationError::InvalidConstruction { name } => {
409				assert_eq!(name, "ConstraintSystem::constants");
410			}
411			_ => panic!("Expected InvalidConstruction error"),
412		}
413	}
414
415	#[test]
416	fn test_serialization_with_different_sources() {
417		let original = create_test_constraint_system();
418
419		// Test with Vec<u8> (memory buffer)
420		let mut vec_buf = Vec::new();
421		original.serialize(&mut vec_buf).unwrap();
422		let deserialized1 = ConstraintSystem::deserialize(&mut vec_buf.as_slice()).unwrap();
423		assert_eq!(original.constants.len(), deserialized1.constants.len());
424
425		// Test with bytes::BytesMut (another common buffer type)
426		let mut bytes_buf = bytes::BytesMut::new();
427		original.serialize(&mut bytes_buf).unwrap();
428		let deserialized2 = ConstraintSystem::deserialize(bytes_buf.freeze()).unwrap();
429		assert_eq!(original.constants.len(), deserialized2.constants.len());
430	}
431
432	/// Helper function to create or update the reference binary file for version compatibility
433	/// testing. This is not run automatically but can be used to regenerate the reference file
434	/// when needed.
435	#[test]
436	#[ignore] // Use `cargo test -- --ignored create_reference_binary` to run this
437	fn create_reference_binary_file() {
438		let constraint_system = create_test_constraint_system();
439
440		// Serialize to binary data
441		let mut buf = Vec::new();
442		constraint_system.serialize(&mut buf).unwrap();
443
444		// Write to reference file.
445		let test_data_path = std::path::Path::new("test_data/constraint_system_v5.bin");
446
447		// Create directory if it doesn't exist
448		if let Some(parent) = test_data_path.parent() {
449			std::fs::create_dir_all(parent).unwrap();
450		}
451
452		std::fs::write(test_data_path, &buf).unwrap();
453
454		println!("Created reference binary file at: {:?}", test_data_path);
455		println!("Binary data length: {} bytes", buf.len());
456	}
457
458	/// Test deserialization from a reference binary file to ensure version compatibility.
459	/// This test will fail if breaking changes are made without incrementing the version.
460	#[test]
461	fn test_deserialize_from_reference_binary_file() {
462		// The v5 format stores IMUL operands as `(a, b, lo, hi)`; the v4 format ordered them
463		// `(a, b, hi, lo)`. Older files are no longer compatible.
464		let binary_data = include_bytes!("../../test_data/constraint_system_v5.bin");
465
466		let deserialized = ConstraintSystem::deserialize(&mut binary_data.as_slice()).unwrap();
467
468		assert_eq!(deserialized.value_vec_layout.n_const, 3);
469		assert_eq!(deserialized.value_vec_layout.n_inout, 2);
470		assert_eq!(deserialized.value_vec_layout.n_witness, 10);
471		assert_eq!(deserialized.value_vec_layout.n_internal, 3);
472		assert_eq!(deserialized.value_vec_layout.offset_inout, 4);
473		assert_eq!(deserialized.value_vec_layout.offset_witness, 8);
474		assert_eq!(deserialized.value_vec_layout.n_hidden_words, 8);
475		assert_eq!(deserialized.value_vec_layout.n_scratch, 0);
476
477		assert_eq!(deserialized.constants.len(), 3);
478		assert_eq!(deserialized.constants[0].as_u64(), 1);
479		assert_eq!(deserialized.constants[1].as_u64(), 42);
480		assert_eq!(deserialized.constants[2].as_u64(), 0xDEADBEEF);
481
482		assert_eq!(deserialized.and_constraints.len(), 2);
483		assert_eq!(deserialized.imul_constraints.len(), 1);
484		assert_eq!(deserialized.bmul_constraints.len(), 1);
485
486		// Verify that the version is what we expect
487		// This is implicitly checked during deserialization, but we can also verify
488		// the file starts with the correct version bytes
489		let version_bytes = &binary_data[0..4]; // First 4 bytes should be version
490		let expected_version_bytes = 5u32.to_le_bytes(); // Version 5 in little-endian
491		assert_eq!(
492			version_bytes, expected_version_bytes,
493			"Binary file version mismatch. If you made breaking changes, increment ConstraintSystem::SERIALIZATION_VERSION"
494		);
495	}
496
497	#[test]
498	fn test_validate_rejects_padding_references() {
499		let mut cs = ConstraintSystem::new(
500			vec![Word::from_u64(1)],
501			ValueVecLayout {
502				n_const: 1,
503				n_inout: 1,
504				n_witness: 2,
505				n_internal: 2,
506				offset_inout: 4,
507				offset_witness: 8,
508				n_hidden_words: 8,
509				n_scratch: 0,
510			},
511			vec![],
512			vec![],
513			vec![],
514		);
515
516		// Add constraint that references padding (index 2 is padding between const and inout)
517		cs.add_and_constraint(AndConstraint::plain_abc(
518			vec![ValueIndex(0)], // valid constant
519			vec![ValueIndex(2)], // PADDING!
520			vec![ValueIndex(8)], // valid witness
521		));
522
523		let result = cs.validate_and_prepare();
524		assert!(result.is_err(), "Should reject constraint referencing padding");
525
526		match result.unwrap_err() {
527			ConstraintSystemError::PaddingValueIndex {
528				constraint_type, ..
529			} => {
530				assert_eq!(constraint_type, "and");
531			}
532			other => panic!("Expected PaddingValueIndex error, got: {:?}", other),
533		}
534	}
535
536	#[test]
537	fn test_validate_accepts_non_padding_references() {
538		let mut cs = ConstraintSystem::new(
539			vec![Word::from_u64(1), Word::from_u64(2)],
540			ValueVecLayout {
541				n_const: 2,
542				n_inout: 2,
543				n_witness: 4,
544				n_internal: 4,
545				offset_inout: 2,
546				offset_witness: 4,
547				n_hidden_words: 12,
548				n_scratch: 0,
549			},
550			vec![],
551			vec![],
552			vec![],
553		);
554
555		// Add constraint that only references valid non-padding indices
556		cs.add_and_constraint(AndConstraint::plain_abc(
557			vec![ValueIndex(0), ValueIndex(1)], // constants
558			vec![ValueIndex(2), ValueIndex(3)], // inout
559			vec![ValueIndex(4), ValueIndex(5)], // witness
560		));
561
562		cs.add_imul_constraint(ImulConstraint([
563			vec![ShiftedValueIndex::plain(ValueIndex(6))], // a: witness
564			vec![ShiftedValueIndex::plain(ValueIndex(7))], // b: witness
565			vec![ShiftedValueIndex::plain(ValueIndex(8))], // lo: internal
566			vec![ShiftedValueIndex::plain(ValueIndex(9))], // hi: internal
567		]));
568
569		let result = cs.validate_and_prepare();
570		assert!(
571			result.is_ok(),
572			"Should accept constraints with only valid references: {:?}",
573			result
574		);
575	}
576
577	#[test]
578	fn test_validate_rejects_out_of_range_indices() {
579		let mut cs = ConstraintSystem::new(
580			vec![Word::from_u64(1)],
581			ValueVecLayout {
582				n_const: 1,
583				n_inout: 1,
584				n_witness: 2,
585				n_internal: 2,
586				offset_inout: 4,
587				offset_witness: 8,
588				n_hidden_words: 8,
589				n_scratch: 0,
590			},
591			vec![],
592			vec![],
593			vec![],
594		);
595
596		// Add AND constraint that references an out-of-range index
597		cs.add_and_constraint(AndConstraint::plain_abc(
598			vec![ValueIndex(0)],  // valid constant
599			vec![ValueIndex(16)], // OUT OF RANGE! (total_len is 16, so max valid index is 15)
600			vec![ValueIndex(8)],  // valid witness
601		));
602
603		let result = cs.validate_and_prepare();
604		assert!(result.is_err(), "Should reject constraint with out-of-range index");
605
606		match result.unwrap_err() {
607			ConstraintSystemError::OutOfRangeValueIndex {
608				constraint_type,
609				operand_name,
610				value_index,
611				total_len,
612				..
613			} => {
614				assert_eq!(constraint_type, "and");
615				assert_eq!(operand_name, "b");
616				assert_eq!(value_index, 16);
617				assert_eq!(total_len, 16);
618			}
619			other => panic!("Expected OutOfRangeValueIndex error, got: {:?}", other),
620		}
621	}
622
623	#[test]
624	fn test_validate_rejects_out_of_range_in_imul_constraint() {
625		let mut cs = ConstraintSystem::new(
626			vec![Word::from_u64(1), Word::from_u64(2)],
627			ValueVecLayout {
628				n_const: 2,
629				n_inout: 2,
630				n_witness: 4,
631				n_internal: 4,
632				offset_inout: 2,
633				offset_witness: 4,
634				n_hidden_words: 12,
635				n_scratch: 0,
636			},
637			vec![],
638			vec![],
639			vec![],
640		);
641
642		// Add IMUL constraint with out-of-range index in 'hi' operand
643		cs.add_imul_constraint(ImulConstraint([
644			vec![ShiftedValueIndex::plain(ValueIndex(0))], // a: valid
645			vec![ShiftedValueIndex::plain(ValueIndex(1))], // b: valid
646			vec![ShiftedValueIndex::plain(ValueIndex(3))], // lo: valid
647			vec![ShiftedValueIndex::plain(ValueIndex(100))], // hi: WAY out of range!
648		]));
649
650		let result = cs.validate_and_prepare();
651		assert!(result.is_err(), "Should reject IMUL constraint with out-of-range index");
652
653		match result.unwrap_err() {
654			ConstraintSystemError::OutOfRangeValueIndex {
655				constraint_type,
656				operand_name,
657				value_index,
658				total_len,
659				..
660			} => {
661				assert_eq!(constraint_type, "imul");
662				assert_eq!(operand_name, "hi");
663				assert_eq!(value_index, 100);
664				assert_eq!(total_len, 16);
665			}
666			other => panic!("Expected OutOfRangeValueIndex error, got: {:?}", other),
667		}
668	}
669
670	#[test]
671	fn test_validate_rejects_out_of_range_in_bmul_constraint() {
672		let mut cs = ConstraintSystem::new(
673			vec![Word::from_u64(1)],
674			ValueVecLayout {
675				n_const: 1,
676				n_inout: 2,
677				n_witness: 4,
678				n_internal: 4,
679				offset_inout: 2,
680				offset_witness: 4,
681				n_hidden_words: 12,
682				n_scratch: 0,
683			},
684			vec![],
685			vec![],
686			vec![],
687		);
688
689		// Add BMUL constraint with out-of-range index in 'c_hi' operand
690		cs.add_bmul_constraint(BmulConstraint([
691			vec![ShiftedValueIndex::plain(ValueIndex(0))], // a_lo: valid const
692			vec![ShiftedValueIndex::plain(ValueIndex(2))], // a_hi: valid inout
693			vec![ShiftedValueIndex::plain(ValueIndex(3))], // b_lo: valid inout
694			vec![ShiftedValueIndex::plain(ValueIndex(4))], // b_hi: valid witness
695			vec![ShiftedValueIndex::plain(ValueIndex(5))], // c_lo: valid witness
696			vec![ShiftedValueIndex::plain(ValueIndex(100))], // c_hi: WAY out of range!
697		]));
698
699		let result = cs.validate_and_prepare();
700		assert!(result.is_err(), "Should reject BMUL constraint with out-of-range index");
701
702		match result.unwrap_err() {
703			ConstraintSystemError::OutOfRangeValueIndex {
704				constraint_type,
705				operand_name,
706				value_index,
707				total_len,
708				..
709			} => {
710				assert_eq!(constraint_type, "bmul");
711				assert_eq!(operand_name, "c_hi");
712				assert_eq!(value_index, 100);
713				assert_eq!(total_len, 16);
714			}
715			other => panic!("Expected OutOfRangeValueIndex error, got: {:?}", other),
716		}
717	}
718
719	#[test]
720	fn test_validate_checks_out_of_range_before_padding() {
721		// This test verifies that out-of-range checking happens before padding checking
722		// by using an index that is both out-of-range AND would be in a padding area if it were
723		// valid
724		let mut cs = ConstraintSystem::new(
725			vec![Word::from_u64(1)],
726			ValueVecLayout {
727				n_const: 1,
728				n_inout: 1,
729				n_witness: 2,
730				n_internal: 2,
731				offset_inout: 4,
732				offset_witness: 8,
733				n_hidden_words: 8,
734				n_scratch: 0,
735			},
736			vec![],
737			vec![],
738			vec![],
739		);
740
741		// Index 20 is out of range (>= 16)
742		// If it were in range, indices 2-3 and 6-7 would be padding
743		cs.add_and_constraint(AndConstraint::plain_abc(
744			vec![ValueIndex(0)],
745			vec![ValueIndex(20)], // out of range
746			vec![ValueIndex(8)],
747		));
748
749		let result = cs.validate_and_prepare();
750		assert!(result.is_err());
751
752		// Should get OutOfRangeValueIndex, not PaddingValueIndex
753		match result.unwrap_err() {
754			ConstraintSystemError::OutOfRangeValueIndex { .. } => {
755				// Good, out-of-range was detected first
756			}
757			other => panic!(
758				"Expected OutOfRangeValueIndex to be detected before padding check, got: {:?}",
759				other
760			),
761		}
762	}
763
764	#[test]
765	fn test_validate_rejects_half_word_shift_amount_out_of_range() {
766		let mut cs = ConstraintSystem::new(
767			vec![Word::from_u64(1)],
768			ValueVecLayout {
769				n_const: 1,
770				n_inout: 1,
771				n_witness: 2,
772				n_internal: 2,
773				offset_inout: 4,
774				offset_witness: 8,
775				n_hidden_words: 8,
776				n_scratch: 0,
777			},
778			vec![],
779			vec![],
780			vec![],
781		);
782
783		// A half-word (*32) shift may only use amounts < 32.
784		// 32 is out of range even though it is below the full-width bound of 64.
785		cs.add_and_constraint(AndConstraint::abc(
786			vec![ShiftedValueIndex {
787				value_index: ValueIndex(0),
788				shift_variant: ShiftVariant::Sll32,
789				amount: 32,
790			}],
791			vec![ShiftedValueIndex::plain(ValueIndex(8))],
792			vec![ShiftedValueIndex::plain(ValueIndex(8))],
793		));
794
795		match cs.validate_and_prepare().unwrap_err() {
796			ConstraintSystemError::ShiftAmountTooLarge {
797				constraint_type,
798				constraint_index,
799				operand_name,
800				shift_amount,
801				max_amount,
802			} => {
803				assert_eq!(constraint_type, "and");
804				assert_eq!(constraint_index, 0);
805				assert_eq!(operand_name, "a");
806				assert_eq!(shift_amount, 32);
807				assert_eq!(max_amount, 32);
808			}
809			other => panic!("Expected ShiftAmountTooLarge, got: {:?}", other),
810		}
811	}
812
813	#[test]
814	fn test_roundtrip_cs_and_witnesses_reconstruct_valuevec_with_scratch() {
815		// Layout with non-zero scratch. Public = 8, total committed = 16, scratch = 5
816		let layout = ValueVecLayout {
817			n_const: 2,
818			n_inout: 3,
819			n_witness: 4,
820			n_internal: 3,
821			offset_inout: 4,   // >= n_const and power of two
822			offset_witness: 8, // >= offset_inout + n_inout and power of two
823			n_hidden_words: 8,
824			n_scratch: 5, // non-zero scratch
825		};
826
827		let constants = vec![Word::from_u64(11), Word::from_u64(22)];
828		let cs = ConstraintSystem::new(constants, layout.clone(), vec![], vec![], vec![]);
829
830		// Build a ValueVec and fill both committed and scratch with non-zero data
831		let mut values = cs.new_value_vec();
832		let full_len = layout.combined_len() + layout.n_scratch;
833		for i in 0..full_len {
834			// Deterministic pattern
835			let val = Word::from_u64(0xA5A5_5A5A ^ (i as u64 * 0x9E37_79B9));
836			values[ValueIndex(i as u32)] = val;
837		}
838
839		// Split into public and non-public witnesses and serialize all artifacts
840		let public_data = ValuesData::from(values.public());
841		let non_public_data = ValuesData::from(values.non_public());
842
843		let mut buf_cs = Vec::new();
844		cs.serialize(&mut buf_cs).unwrap();
845
846		let mut buf_pub = Vec::new();
847		public_data.serialize(&mut buf_pub).unwrap();
848
849		let mut buf_non_pub = Vec::new();
850		non_public_data.serialize(&mut buf_non_pub).unwrap();
851
852		// Deserialize everything back
853		let cs2 = ConstraintSystem::deserialize(&mut buf_cs.as_slice()).unwrap();
854		let pub2 = ValuesData::deserialize(&mut buf_pub.as_slice()).unwrap();
855		let non_pub2 = ValuesData::deserialize(&mut buf_non_pub.as_slice()).unwrap();
856
857		// Reconstruct ValueVec from deserialized pieces
858		let reconstructed =
859			ValueVec::new_from_data(cs2.value_vec_layout, pub2.into_owned(), non_pub2.into_owned())
860				.unwrap();
861
862		// Ensure committed part matches exactly
863		assert_eq!(reconstructed.combined_witness(), values.combined_witness());
864
865		// Scratch is not serialized; reconstructed scratch should be zero-filled
866		let scratch_start = layout.combined_len();
867		let scratch_end = scratch_start + layout.n_scratch;
868		for i in scratch_start..scratch_end {
869			assert_eq!(
870				reconstructed[ValueIndex(i as u32)],
871				Word::ZERO,
872				"scratch index {i} should be zero"
873			);
874		}
875	}
876}
binius_core/constraint_system/system.rs

binius_core/constraint_system/
system.rs
