binius_core/constraint_system/
mod.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3pub mod channel;
4mod common;
5pub mod error;
6pub mod exp;
7mod prove;
8pub mod validate;
9mod verify;
10
11#[cfg(test)]
12mod tests;
13
14use binius_field::{BinaryField128b, TowerField};
15use binius_macros::{DeserializeBytes, SerializeBytes};
16use binius_utils::{SerializationMode, SerializeBytes};
17use channel::Flush;
18use digest::{Digest, Output};
19use exp::Exp;
20pub use prove::prove;
21pub use verify::verify;
22
23use crate::{
24	constraint_system::error::Error,
25	oracle::{ConstraintSet, OracleId, SymbolicMultilinearOracleSet},
26};
27
28/// Contains the 3 things that place constraints on witness data in Binius
29/// - virtual oracles
30/// - polynomial constraints
31/// - channel flushes
32///
33/// As a result, a ConstraintSystem allows us to validate all of these
34/// constraints against a witness, as well as enabling generic prove/verify
35#[derive(Debug, Clone, SerializeBytes, DeserializeBytes)]
36#[deserialize_bytes(eval_generics(F = BinaryField128b))]
37pub struct ConstraintSystem<F: TowerField> {
38	pub oracles: SymbolicMultilinearOracleSet<F>,
39	pub table_constraints: Vec<ConstraintSet<F>>,
40	pub non_zero_oracle_ids: Vec<OracleId>,
41	pub flushes: Vec<Flush<F>>,
42	pub exponents: Vec<Exp<F>>,
43	pub channel_count: usize,
44	pub table_size_specs: Vec<TableSizeSpec>,
45}
46
47impl<F: TowerField> ConstraintSystem<F> {
48	/// Returns the hash digest of this constraint system.
49	///
50	/// This assumes that the constraint system should be serializable.
51	pub fn digest<Hash: Digest>(&self) -> Output<Hash> {
52		let mut buf = Vec::new();
53		self.serialize(&mut buf, SerializationMode::CanonicalTower)
54			.expect("the constraint system should be serializable");
55		Hash::digest(&buf)
56	}
57
58	/// Checks whether the table sizes assigned by prover matches the specification of this
59	/// constraint system.
60	pub fn check_table_sizes(&self, table_sizes: &[usize]) -> Result<(), Error> {
61		if table_sizes.len() != self.table_size_specs.len() {
62			return Err(Error::TableSizesLenMismatch {
63				expected: self.table_size_specs.len(),
64				got: table_sizes.len(),
65			});
66		}
67		for (table_id, (&table_size, table_size_spec)) in table_sizes
68			.iter()
69			.zip(self.table_size_specs.iter())
70			.enumerate()
71		{
72			match table_size_spec {
73				TableSizeSpec::PowerOfTwo => {
74					if !table_size.is_power_of_two() {
75						return Err(Error::TableSizePowerOfTwoRequired {
76							table_id,
77							size: table_size,
78						});
79					}
80				}
81				TableSizeSpec::Fixed { log_size } => {
82					if table_size != 1 << log_size {
83						return Err(Error::TableSizeFixedRequired {
84							table_id,
85							size: table_size,
86						});
87					}
88				}
89				TableSizeSpec::Arbitrary => (),
90			}
91		}
92		Ok(())
93	}
94}
95
96/// Constraint system proof that has been serialized into bytes
97#[derive(Debug, Clone)]
98pub struct Proof {
99	pub transcript: Vec<u8>,
100}
101
102impl Proof {
103	pub fn get_proof_size(&self) -> usize {
104		self.transcript.len()
105	}
106}
107
108pub type TableId = usize;
109
110/// A category of the size specification of a table.
111///
112/// Tables can have size restrictions, where certain columns, specifically structured columns,
113/// are only allowed for certain size specifications.
114#[derive(Debug, Copy, Clone, SerializeBytes, DeserializeBytes)]
115pub enum TableSizeSpec {
116	/// The table size may be arbitrary.
117	Arbitrary,
118	/// The table size may be any power of two.
119	PowerOfTwo,
120	/// The table size must be a fixed power of two.
121	Fixed { log_size: usize },
122}