Skip to main content

binius_verifier/protocols/shift/
wiring.rs

1// Copyright 2026 The Binius Developers
2
3use binius_core::constraint_system::{ConstraintSystem, InoutSegment, Operand};
4use binius_field::{BinaryField, FieldOps, util::FieldFn};
5use binius_math::{
6	line::extrapolate_line,
7	multilinear::{
8		eq::eq_ind_zero,
9		sparse::{
10			SparseBitVector, evaluate_sparse_b1_multilinear, evaluate_sparse_b1_multilinear_native,
11		},
12	},
13};
14use getset::{CopyGetters, Getters};
15
16use super::LOG_SHIFT_COUNT;
17use crate::reduction::{LOG_OPERANDS, log_constraint_point};
18
19/// The address bits below the word index: the operand column, then the inner and outer shift.
20const LOG_TERM_BITS: usize = LOG_OPERANDS + 2 * LOG_SHIFT_COUNT;
21
22/// The wiring matrix as two bit vectors, one per committed segment, with the widths of the point
23/// they are read at.
24///
25/// Each set bit is one operand term, at the address
26///
27/// ```text
28/// bits, low to high:  operand (LOG_OPERANDS) | inner shift (9) | outer shift (9) | word | constraint
29/// ```
30///
31/// A shift slot is [`Shift::index`](binius_core::constraint_system::Shift::index). The word index
32/// is relative to its segment, `log_public_words` wide for the public vector and
33/// `log_segment_words` wide for the hidden one. The constraint index is `log_constraint_point`
34/// wide. The operand column runs over each operation's operands in `[zero, bitand, intmul,
35/// binmul]` order. A term listed twice cancels.
36///
37/// The bit order is the order of the point the shift reduction evaluates the vectors at, so this
38/// is the one place that fixes the layout.
39///
40/// # The wiring multilinear
41///
42/// As a [`FieldFn`], this evaluates the two vectors joined on the segment selector:
43///
44/// ```text
45/// W = extrapolate_line(eq(0, r_y[log_public_words..]) · P(point_pub), H(point_hid), r_segment)
46///
47/// point_hid = operand_batch | r_s_inner | r_v_inner | r_s_outer | r_v_outer | r_y | r_x
48/// point_pub = the same with r_y cut to log_public_words
49/// ```
50///
51/// Its input is `r_segment` followed by `point_hid`. The public segment spans a prefix of the
52/// word-index space, so its point drops the coordinates above it, which read as zero.
53///
54/// The bit-index factors every shift scalar is scaled by are left out: they depend on prover
55/// messages, so [`check_eval`](super::check_eval) multiplies them in outside.
56#[derive(Debug, Clone, Getters, CopyGetters)]
57pub struct WiringInfo {
58	/// The terms whose word lies in the public segment.
59	#[getset(get = "pub")]
60	public_segment: SparseBitVector,
61	/// The terms whose word lies in the hidden segment.
62	#[getset(get = "pub")]
63	hidden_segment: SparseBitVector,
64	/// The word-index variables the public segment spans.
65	#[getset(get_copy = "pub")]
66	log_public_words: usize,
67	/// The word-index variables the shift reduction runs over, the wider of the two segments'
68	/// spans: the length of `r_y`.
69	#[getset(get_copy = "pub")]
70	log_segment_words: usize,
71	/// The constraint-index variables: the length of `r_x`.
72	#[getset(get_copy = "pub")]
73	log_constraint_point: usize,
74}
75
76impl WiringInfo {
77	/// Lays out the wiring matrix of `cs`, with its inout values in `inout`.
78	///
79	/// # Panics
80	///
81	/// Panics if the hidden address does not fit a `u64` index below `2^63`: that is,
82	/// `LOG_OPERANDS + 18 + log_constraint_point + log_segment_words < 64`, or
83	/// `log_constraint_point + log_segment_words ≤ 41`.
84	pub fn new(cs: &ConstraintSystem, inout: InoutSegment) -> Self {
85		let log_public_words = cs.log_public_words(inout);
86		let log_segment_words = cs.log_segment_words(inout);
87		let log_constraint_point = log_constraint_point(cs);
88		let log_words = [log_public_words, log_segment_words];
89		let log_lens = log_words.map(|log_words| LOG_TERM_BITS + log_words + log_constraint_point);
90		assert!(
91			log_lens[1] < u64::BITS as usize,
92			"the wiring address needs {} bits; at most 63 fit",
93			log_lens[1]
94		);
95
96		// Each operand term's segment and address, in the column order the reduction batches.
97		let n_public_words = cs.n_public_words(inout);
98		let mut indices = [Vec::new(), Vec::new()];
99		let mut push = |column: usize, constraint_index: usize, terms: &Operand| {
100			for term in terms {
101				let word = cs.word_offset(term.value_index);
102				let (segment, word) = if word < n_public_words {
103					(0, word)
104				} else {
105					(1, word - n_public_words)
106				};
107				let index = column as u64
108					| (term.inner().index() as u64) << LOG_OPERANDS
109					| (term.outer().index() as u64) << (LOG_OPERANDS + LOG_SHIFT_COUNT)
110					| (word as u64) << LOG_TERM_BITS
111					| (constraint_index as u64) << (LOG_TERM_BITS + log_words[segment]);
112				indices[segment].push(index);
113			}
114		};
115
116		/// Walks one operation, its operands at the columns from `first_column` on, and returns the
117		/// column after its last.
118		fn walk<C: AsRef<[Operand; ARITY]>, const ARITY: usize>(
119			first_column: usize,
120			constraints: &[C],
121			push: &mut impl FnMut(usize, usize, &Operand),
122		) -> usize {
123			for (constraint_index, constraint) in constraints.iter().enumerate() {
124				for (operand_index, terms) in constraint.as_ref().iter().enumerate() {
125					push(first_column + operand_index, constraint_index, terms);
126				}
127			}
128			first_column + ARITY
129		}
130
131		let column = walk(0, &cs.zero_constraints, &mut push);
132		let column = walk(column, &cs.and_constraints, &mut push);
133		let column = walk(column, &cs.imul_constraints, &mut push);
134		walk(column, &cs.bmul_constraints, &mut push);
135
136		let [public, hidden] = indices;
137		let [public_log_len, hidden_log_len] = log_lens;
138		Self {
139			public_segment: SparseBitVector::new(public_log_len, public),
140			hidden_segment: SparseBitVector::new(hidden_log_len, hidden),
141			log_public_words,
142			log_segment_words,
143			log_constraint_point,
144		}
145	}
146
147	/// Joins the two segments' evaluations at `r_segment`, each vector read by `eval`.
148	fn eval<E: FieldOps>(&self, vals: &[E], eval: impl Fn(&SparseBitVector, &[E]) -> E) -> E {
149		let (r_segment, point_hid) = vals.split_first().expect("the input leads with r_segment");
150		assert_eq!(point_hid.len(), self.hidden_segment.log_len());
151
152		let public_end = LOG_TERM_BITS + self.log_public_words;
153		let r_y_end = LOG_TERM_BITS + self.log_segment_words;
154		let point_pub = [&point_hid[..public_end], &point_hid[r_y_end..]].concat();
155		let public_eval =
156			eq_ind_zero(&point_hid[public_end..r_y_end]) * eval(&self.public_segment, &point_pub);
157		let hidden_eval = eval(&self.hidden_segment, point_hid);
158		extrapolate_line(public_eval, hidden_eval, r_segment.clone())
159	}
160}
161
162impl<F: BinaryField> FieldFn<F> for WiringInfo {
163	fn call<E: FieldOps<Scalar = F> + From<F>>(&self, vals: &[E]) -> E {
164		self.eval(vals, evaluate_sparse_b1_multilinear)
165	}
166
167	fn call_native(&self, vals: &[F]) -> F {
168		self.eval(vals, evaluate_sparse_b1_multilinear_native)
169	}
170}
171
172#[cfg(test)]
173mod tests {
174	use std::array;
175
176	use binius_core::{
177		ShiftVariant,
178		constraint_system::{
179			AndConstraint, BmulConstraint, ImulConstraint, Shift, ShiftedValueIndex, ValueIndex,
180			ValueSegment, ZeroConstraint,
181		},
182		word::Word,
183	};
184	use binius_field::Field;
185	use binius_math::{multilinear::eq::eq_ind_partial_eval_scalars, test_utils::random_scalars};
186	use rand::{RngExt, SeedableRng, rngs::StdRng};
187
188	use super::*;
189	use crate::config::B128;
190
191	/// A system whose terms read every value segment, through two shifts each.
192	///
193	/// IMUL is optional, so the columns after it only line up if an empty run is still skipped.
194	fn random_system(rng: &mut StdRng, with_imul: bool) -> ConstraintSystem {
195		let constants = vec![Word::ZERO, Word::ONE, Word::ALL_ONE];
196		let n_inout = 5;
197		let n_private = 12;
198		let term = |rng: &mut StdRng| {
199			let value_index = match rng.random_range(0..3) {
200				0 => ValueIndex::constant(rng.random_range(0..constants.len()) as u32),
201				1 => ValueIndex::inout(rng.random_range(0..n_inout) as u32),
202				_ => ValueIndex::private(rng.random_range(0..n_private) as u32),
203			};
204			let shift = |rng: &mut StdRng| Shift {
205				variant: [ShiftVariant::Sll, ShiftVariant::Sar, ShiftVariant::Rotr32]
206					[rng.random_range(0..3)],
207				amount: rng.random_range(0..Word::BITS) as u8,
208			};
209			ShiftedValueIndex::new(value_index, [shift(rng), shift(rng)])
210		};
211		let operand = |rng: &mut StdRng| (0..rng.random_range(0..3)).map(|_| term(rng)).collect();
212
213		ConstraintSystem {
214			zero_constraints: (0..5)
215				.map(|_| ZeroConstraint(array::from_fn(|_| operand(rng))))
216				.collect(),
217			and_constraints: (0..7)
218				.map(|_| AndConstraint(array::from_fn(|_| operand(rng))))
219				.collect(),
220			imul_constraints: if with_imul {
221				(0..3)
222					.map(|_| ImulConstraint(array::from_fn(|_| operand(rng))))
223					.collect()
224			} else {
225				Vec::new()
226			},
227			bmul_constraints: (0..3)
228				.map(|_| BmulConstraint(array::from_fn(|_| operand(rng))))
229				.collect(),
230			constants,
231			n_inout,
232			n_private,
233		}
234	}
235
236	/// The wiring multilinear as the tensor's defining sum: one weight table per axis, one product
237	/// per term.
238	///
239	/// The value axis is the full `r_y | r_segment` indicator, the hidden segment in its high half,
240	/// so it holds the padded reading against the builder's two cut segments.
241	fn contract(cs: &ConstraintSystem, inout: InoutSegment, vals: &[B128]) -> B128 {
242		let (&r_segment, point) = vals.split_first().unwrap();
243		let r_y_len = cs.log_segment_words(inout);
244		let (inner, rest) = point.split_at(LOG_OPERANDS + LOG_SHIFT_COUNT);
245		let (outer, rest) = rest.split_at(LOG_SHIFT_COUNT);
246		let (r_y, r_x) = rest.split_at(r_y_len);
247
248		let inner = eq_ind_partial_eval_scalars(inner);
249		let outer = eq_ind_partial_eval_scalars(outer);
250		let value = eq_ind_partial_eval_scalars(&[r_y, &[r_segment]].concat());
251		let constraint = eq_ind_partial_eval_scalars(r_x);
252
253		let hidden = 1 << r_y_len;
254		let address = |value_index: ValueIndex| {
255			let index = value_index.index() as usize;
256			match (value_index.segment(), inout) {
257				(ValueSegment::Constant, _) => index,
258				(ValueSegment::InOut, InoutSegment::Public) => cs.n_const() + index,
259				(ValueSegment::InOut, InoutSegment::Hidden) => hidden + index,
260				(ValueSegment::Private, InoutSegment::Public) => hidden + index,
261				(ValueSegment::Private, InoutSegment::Hidden) => hidden + cs.n_inout + index,
262				(ValueSegment::Scratch, _) => unreachable!(),
263			}
264		};
265
266		// Each operation's first operand column, named rather than accumulated.
267		let operations: [(usize, Vec<&[Operand]>); 4] = [
268			(0, cs.zero_constraints.iter().map(|c| &c.0[..]).collect()),
269			(1, cs.and_constraints.iter().map(|c| &c.0[..]).collect()),
270			(4, cs.imul_constraints.iter().map(|c| &c.0[..]).collect()),
271			(8, cs.bmul_constraints.iter().map(|c| &c.0[..]).collect()),
272		];
273		let mut acc = B128::ZERO;
274		for (first_column, constraints) in operations {
275			for (constraint_index, operands) in constraints.into_iter().enumerate() {
276				for (operand_index, terms) in operands.iter().enumerate() {
277					for term in terms {
278						let column = first_column + operand_index;
279						acc += constraint[constraint_index]
280							* inner[(term.inner().index() << LOG_OPERANDS) | column]
281							* outer[term.outer().index()]
282							* value[address(term.value_index)];
283					}
284				}
285			}
286		}
287		acc
288	}
289
290	#[test]
291	fn the_wiring_bits_evaluate_to_the_contracted_tensor() {
292		let mut rng = StdRng::seed_from_u64(31);
293		for with_imul in [false, true] {
294			let cs = random_system(&mut rng, with_imul);
295			for inout in [InoutSegment::Public, InoutSegment::Hidden] {
296				let wiring = WiringInfo::new(&cs, inout);
297				let vals = random_scalars::<B128>(&mut rng, 1 + wiring.hidden_segment().log_len());
298
299				let got = FieldFn::<B128>::call::<B128>(&wiring, &vals);
300				// A vacuous claim would let a broken layout pass unnoticed.
301				assert_ne!(got, B128::ZERO);
302				assert_eq!(got, contract(&cs, inout, &vals), "{inout:?}, imul: {with_imul}");
303				assert_eq!(got, FieldFn::<B128>::call_native(&wiring, &vals));
304			}
305		}
306	}
307
308	#[test]
309	fn a_repeated_term_cancels() {
310		// Two copies of one term sit at one address, and a bit set twice is clear.
311		let term = ShiftedValueIndex::new(ValueIndex::private(1), [Shift::srl(7), Shift::srl(3)]);
312		let mut cs = empty_system(0, 2);
313		cs.and_constraints = vec![AndConstraint([vec![term, term], vec![term], vec![]])];
314		let wiring = WiringInfo::new(&cs, InoutSegment::Public);
315		assert!(wiring.public_segment().indices().is_empty());
316		assert_eq!(wiring.hidden_segment().indices().len(), 1);
317	}
318
319	/// A system of `2^log_constraints` empty ZERO constraints over `2^log_words` private words.
320	fn empty_system(log_constraints: usize, log_words: usize) -> ConstraintSystem {
321		ConstraintSystem {
322			constants: Vec::new(),
323			n_inout: 0,
324			n_private: 1 << log_words,
325			zero_constraints: vec![ZeroConstraint::default(); 1 << log_constraints],
326			and_constraints: Vec::new(),
327			imul_constraints: Vec::new(),
328			bmul_constraints: Vec::new(),
329		}
330	}
331
332	#[test]
333	fn the_widest_address_that_fits_is_63_bits() {
334		let wiring = WiringInfo::new(&empty_system(15, 26), InoutSegment::Public);
335		assert_eq!(wiring.hidden_segment().log_len(), 63);
336	}
337
338	#[test]
339	#[should_panic(expected = "the wiring address needs 64 bits")]
340	fn a_system_whose_address_does_not_fit_is_rejected() {
341		let _ = WiringInfo::new(&empty_system(16, 26), InoutSegment::Public);
342	}
343}