Skip to main content

binius_verifier/protocols/shift/
verify.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::iter;
5
6use binius_core::word::Word;
7use binius_field::{BinaryField, field::FieldOps, util::FieldFn};
8use binius_ip::{
9	channel::IPVerifierChannel,
10	sumcheck::{SumcheckOutput, verify as verify_sumcheck},
11};
12use binius_math::{
13	BinarySubspace,
14	inner_product::inner_product,
15	line::extrapolate_line,
16	multilinear::{eq::eq_ind_partial_eval_scalars, evaluate::evaluate_inplace_scalars},
17	univariate::EvaluationDomain,
18};
19use binius_utils::checked_arithmetics::log2_ceil_usize;
20use getset::Getters;
21use itertools::chain;
22
23use super::{
24	LOG_SHIFT_COUNT, SHIFT_LOG_VARS, WiringInfo, error::Error, shift_ind::evaluate_shift_inds,
25};
26
27/// Evaluates the bit-level multilinear extension of a word slice at the point `r_j ++ r_y`.
28///
29/// The multilinear has `Word::LOG_BITS + r_y.len()` variables: the low variables index the
30/// bit within a word and the high variables index the word. Words past `words.len()` (up to
31/// `2^r_y.len()`) are treated as zero.
32///
33/// ## Preconditions
34///
35/// * `r_j` has exactly `Word::LOG_BITS` entries
36/// * `words` has at most `2^r_y.len()` entries
37pub fn evaluate_words_mle<F, E>(words: &[Word], r_j: &[E], r_y: &[E]) -> E
38where
39	F: BinaryField,
40	E: FieldOps<Scalar = F> + From<F>,
41{
42	assert_eq!(r_j.len(), Word::LOG_BITS); // precondition
43	assert!(words.len() <= 1 << r_y.len()); // precondition
44
45	let r_j_tensor = eq_ind_partial_eval_scalars(r_j);
46	let r_y_tensor = eq_ind_partial_eval_scalars(r_y);
47	iter::zip(words, r_y_tensor)
48		.map(|(word, weight)| {
49			let word_eval = (0..Word::BITS)
50				.filter(|bit| (word.as_u64() >> bit) & 1 == 1)
51				.map(|bit| &r_j_tensor[bit])
52				.sum::<E>();
53			weight * word_eval
54		})
55		.sum()
56}
57
58/// Output of the shift reduction verification protocol.
59///
60/// Contains all the challenge points, evaluation claims, and random coefficients
61/// produced during the shift reduction protocol. These values are used for subsequent
62/// verification steps including PCS verification.
63#[derive(Debug, Getters)]
64pub struct VerifyOutput<F> {
65	/// The challenges whose equality indicator weights each operand column in the batch (length
66	/// `log2_ceil` of the column count).
67	pub operand_batch_challenges: Vec<F>,
68	/// Challenge point for the witness bit index (length `Word::LOG_BITS`).
69	pub r_j: Vec<F>,
70	/// Challenge point for the inner shift's amount variables (length `Word::LOG_BITS`).
71	pub r_s_inner: Vec<F>,
72	/// Challenge point for the inner shift's variant variables (length
73	/// `LOG_SHIFT_VARIANT_COUNT`).
74	pub r_v_inner: Vec<F>,
75	/// Challenge point for the outer shift's amount variables (length `Word::LOG_BITS`).
76	pub r_s_outer: Vec<F>,
77	/// Challenge point for the outer shift's variant variables (length
78	/// `LOG_SHIFT_VARIANT_COUNT`).
79	pub r_v_outer: Vec<F>,
80	/// Challenge point for the word index variables (length `log_segment_words`).
81	pub r_y: Vec<F>,
82	/// Challenge point for the bit index of the intermediate word, where the two shift indicators
83	/// meet (length `Word::LOG_BITS`).
84	pub r_k: Vec<F>,
85	/// Challenge point for the output bit index the oblong weights attach to (length
86	/// `Word::LOG_BITS`).
87	pub r_i: Vec<F>,
88	/// Challenge for the witness's segment selector variable.
89	pub r_segment: F,
90	/// Final evaluation claim from the sumcheck.
91	pub eval: F,
92	/// The claimed witness evaluation at the challenge point.
93	#[getset(get = "pub")]
94	pub witness_eval: F,
95}
96
97impl<F> VerifyOutput<F> {
98	/// Returns the challenge point for bit index variables.
99	///
100	/// This corresponds to the first `Word::LOG_BITS` variables
101	/// in the witness encoding, indexing individual bits within words.
102	pub fn r_j(&self) -> &[F] {
103		&self.r_j
104	}
105
106	/// Returns the challenge point for word index variables.
107	///
108	/// This corresponds to `log_word_count` variables indexing
109	/// the words in the witness vector.
110	pub fn r_y(&self) -> &[F] {
111		&self.r_y
112	}
113}
114
115/// Verifies the shift protocol with a single sumcheck.
116///
117/// # Protocol Overview
118/// 1. **Sampling Phase**: Samples the challenge vector whose equality indicator batches the operand
119///    columns' evaluation claims.
120/// 2. **Sumcheck**: Verifies the batched evaluation claim over all `SHIFT_LOG_VARS +
121///    log_word_count` variables of the claim, degree 2 in each. A shifted value index names two
122///    shifts applied in sequence, and the rounds peel them from the output end inward: the outer
123///    shift's variant and amount, then the inner shift's, then the bit position within a word, then
124///    the intermediate word's bit index where the two shift indicators meet, then the output bit
125///    index, and last the word index — the order the prover's phases need.
126/// 3. **Challenge Splitting**: Splits the challenge point into its per-slot shift runs, its three
127///    bit-index runs and `r_y`
128/// 4. **Monster Multilinear Verification**: Checks that the claim the sumcheck reduced to matches
129///    the product of its five factors, for AND constraints (bitand), IMUL constraints (intmul) and
130///    BMUL constraints (binmul)
131///
132/// # Parameters
133/// - `log_segment_words`: The word-index variables each value segment spans, the wider of the two
134/// - `operand_claims`: One evaluation per operand column, in the flat column order [`WiringInfo`]
135///   lays the terms out in. The point they are claimed at is [`check_eval`]'s to read
136/// - `channel`: Interactive channel for challenge sampling and message reading
137///
138/// # Returns
139/// Returns [`VerifyOutput`] containing the final challenges and witness evaluation,
140/// or an error if verification fails.
141///
142/// # Errors
143/// - Returns `Error::VerificationFailure` if monster multilinear evaluations don't match expected
144///   values
145/// - Propagates sumcheck verification errors
146pub fn verify<F, C>(
147	log_segment_words: usize,
148	operand_claims: &[C::Elem],
149	channel: &mut C,
150) -> Result<VerifyOutput<C::Elem>, Error>
151where
152	F: BinaryField,
153	C: IPVerifierChannel<F>,
154{
155	// SOUNDNESS: the prover draws the same number of challenges at the same place.
156	let operand_batch_challenges = channel.sample_many(log2_ceil_usize(operand_claims.len()));
157
158	// A claim is weighted by the equality indicator of the operand axis at its column. The axis is
159	// padded to a cube; the columns past the last claim name nothing.
160	let operand_weights = eq_ind_partial_eval_scalars(&operand_batch_challenges);
161	let eval = inner_product(
162		operand_claims.iter().cloned(),
163		operand_weights[..operand_claims.len()].iter().cloned(),
164	);
165
166	// The sumcheck runs over the witness as well: the public segment in the low half-cube and
167	// the hidden segment in the high half-cube, selected by the top word-index variable. Each
168	// half spans the wider of the two segments, which the prover zero-pads the shorter one up
169	// to, so a public segment longer than the hidden one draws the extra word-index challenges.
170	let log_word_count = log_segment_words + 1;
171
172	let SumcheckOutput {
173		eval,
174		challenges: mut point,
175	} = verify_sumcheck(SHIFT_LOG_VARS + log_word_count, 2, eval, channel)?;
176
177	// Reverse the challenges into the evaluation point, whose coordinates then run in increasing
178	// order of significance: the word index, the output bit index, the intermediate bit index, the
179	// witness bit index, then the inner shift slot and the outer one. The rounds bind them in the
180	// opposite order — the outer shift first, the word index last — which is what admits the
181	// prover's phases, and which peels the two shifts from the output end inward.
182	point.reverse();
183	debug_assert_eq!(point.len(), SHIFT_LOG_VARS + log_word_count);
184	// Where each run starts, counting up from the word index. `split_off` cuts from the top, so
185	// the runs come off in decreasing significance.
186	let bit_indices = log_word_count + Word::LOG_BITS * 3;
187	let inner_slot = bit_indices + LOG_SHIFT_COUNT;
188	let r_v_outer = point.split_off(inner_slot + Word::LOG_BITS);
189	let r_s_outer = point.split_off(inner_slot);
190	let r_v_inner = point.split_off(bit_indices + Word::LOG_BITS);
191	let r_s_inner = point.split_off(bit_indices);
192	let r_j = point.split_off(log_word_count + Word::LOG_BITS * 2);
193	let r_k = point.split_off(log_word_count + Word::LOG_BITS);
194	let r_i = point.split_off(log_word_count);
195	let mut r_y = point;
196	let r_segment = r_y.pop().expect("log_word_count >= 1");
197
198	let witness_eval = channel.recv_one()?;
199
200	Ok(VerifyOutput {
201		operand_batch_challenges,
202		r_j,
203		r_y,
204		r_segment,
205		r_s_inner,
206		r_v_inner,
207		r_s_outer,
208		r_v_outer,
209		r_k,
210		r_i,
211		eval,
212		witness_eval,
213	})
214}
215
216/// Validates the evaluation claims from the shift reduction protocol.
217///
218/// After the shift reduction protocol completes, this function checks that the
219/// prover-provided witness evaluation is consistent with the expected values.
220/// It reads the wiring multilinear's evaluation from the prover and verifies the final equation
221/// relating the witness and monster evaluations.
222///
223/// # Protocol Details
224///
225/// The function verifies that:
226/// ```text
227/// eval = trace_eval * monster_eval
228/// ```
229///
230/// where `monster_eval` is the prover's claimed wiring evaluation — the AND, IMUL and BMUL
231/// constraint polynomials summed — scaled by the sumcheck's two bit-index factors, the Lagrange
232/// weights and the interpolated shift indicators, both at `r_i`.
233///
234/// That claim is not checked here. It comes back as a [`WiringEvalClaim`], holding the function
235/// that evaluates the wiring multilinear from public-channel-derived values together with the
236/// claimed value it must equal, for the caller to discharge however it opens claims.
237///
238/// `trace_eval` is the witness evaluation reconstructed from its two segments:
239/// ```text
240/// trace_eval = (1 - r_segment) * public_eval + r_segment * witness_eval
241/// ```
242///
243/// `public_eval` is the public segment over the shift's whole index space — `r_j` over the bit
244/// within a word and all of `r_y` over the word — so it already carries the zero-padding above the
245/// segment's own length. Tying it to the public values is the caller's job: the caller reads it
246/// from the prover and reduces it onto the packed public segment, so a prover that used different
247/// public values fails there rather than here.
248///
249/// `r_x` is the constraint point every padded operation matrix is claimed at. Only the point enters
250/// here; the evaluation claims at it are [`verify`]'s to batch.
251///
252/// `wiring` is the wiring multilinear the returned claim is about.
253///
254/// # Panics
255///
256/// Panics if `wiring` is laid out over a different point than `output` and `r_x` form, since it
257/// would then name a different polynomial.
258///
259/// # Errors
260///
261/// - `Error::VerificationFailure` if the evaluation equation doesn't hold
262/// - Propagates errors from reading the wiring evaluation off the channel
263#[allow(clippy::too_many_arguments)]
264pub fn check_eval<'a, F, C>(
265	wiring: &'a WiringInfo,
266	public_eval: C::Elem,
267	r_x: &[C::Elem],
268	subspace: &BinarySubspace<F>,
269	r_zhat_prime: &C::Elem,
270	output: &VerifyOutput<C::Elem>,
271	channel: &mut C,
272) -> Result<WiringEvalClaim<'a, C::Elem>, Error>
273where
274	F: BinaryField,
275	C: IPVerifierChannel<F>,
276	C::Elem: FieldOps<Scalar = F> + From<F>,
277{
278	let VerifyOutput {
279		operand_batch_challenges,
280		eval,
281		r_j,
282		r_s_inner,
283		r_v_inner,
284		r_s_outer,
285		r_v_outer,
286		r_y,
287		r_segment,
288		r_k,
289		r_i,
290		witness_eval,
291	} = output;
292
293	// Three of the sumcheck's five factors are the verifier's to evaluate from the bit-index
294	// challenges alone: the Lagrange weights of the univariate challenge at `r_i`, and the two
295	// shift indicators, one per slot of a term's shift sequence. The indicators chain through the
296	// intermediate word — the outer one carries the output bit down to `r_k`, the inner one carries
297	// `r_k` down to the witness bit — which is what makes a sequence of two shifts one index entry.
298	let l_tilde_eval = evaluate_inplace_scalars(subspace.lagrange_evals(r_zhat_prime), r_i);
299	let outer_ind_eval =
300		evaluate_inplace_scalars(&mut evaluate_shift_inds(r_i, r_k, r_s_outer)[..], r_v_outer);
301	let inner_ind_eval =
302		evaluate_inplace_scalars(&mut evaluate_shift_inds(r_k, r_j, r_s_inner)[..], r_v_inner);
303	let shift_ind_eval = outer_ind_eval * inner_ind_eval;
304
305	// The wiring multilinear's evaluation comes from the prover, as a claim the verifier could
306	// compute for itself. Checking it against the constraint system is left to the caller, which is
307	// handed the function that computes it below.
308	let wiring_eval = channel.recv_public_claim()?;
309
310	// The three bit-index factors scale every shift scalar of the wiring multilinear; they multiply
311	// the claim out here rather than entering the function, which keeps its input free of `r_i` and
312	// `r_k`.
313	let monster_eval = l_tilde_eval * shift_ind_eval * wiring_eval.clone();
314
315	// The flat input the caller checks the claim with. Every entry is a public-channel-derived
316	// element: `r_segment`, then the point the hidden vector is read at, whose bit order is the
317	// order `WiringInfo` lays a term's address out in.
318	assert_eq!(r_y.len(), wiring.log_segment_words());
319	assert_eq!(r_x.len(), wiring.log_constraint_point());
320	let inputs: Vec<C::Elem> = chain!(
321		iter::once(r_segment),
322		operand_batch_challenges,
323		r_s_inner,
324		r_v_inner,
325		r_s_outer,
326		r_v_outer,
327		r_y,
328		r_x,
329	)
330	.cloned()
331	.collect();
332	assert_eq!(inputs.len(), 1 + wiring.hidden_segment().log_len());
333	let claim = WiringEvalClaim {
334		eval_fn: wiring,
335		inputs,
336		claimed: wiring_eval,
337	};
338
339	// Reconstruct the witness evaluation from its two segments.
340	let trace_eval = extrapolate_line(public_eval, witness_eval.clone(), r_segment.clone());
341
342	// Check if the reconstructed trace value is satisfying.
343	//
344	// The protocol could compute the committed-half value instead of reading it from the prover.
345	// This would require inverting a random element, however, making the protocol incomplete
346	// with negligible probability. As a matter of taste, we read the value from the prover.
347	let expected_eval = trace_eval * monster_eval;
348	channel.assert_zero(expected_eval - eval)?;
349
350	Ok(claim)
351}
352
353/// The prover's wiring multilinear evaluation, with what it takes to check it.
354///
355/// [`check_eval`] reads the evaluation from the prover and closes the shift reduction with it,
356/// leaving this behind: the claimed value, and the function and inputs that recompute it from the
357/// wiring matrix. The holder discharges the claim by evaluating the function and requiring the
358/// two to agree.
359///
360/// Both discharges below evaluate the same function; they differ in where. A verifier holding
361/// values checks it in the field, and one building a circuit checks it in constraints — which is
362/// why the function is kept rather than a value, and why the claimed value sits beside it rather
363/// than folded into it.
364///
365/// Dropping a claim drops a check, so it is `#[must_use]`.
366#[must_use]
367#[derive(Debug)]
368pub struct WiringEvalClaim<'a, E> {
369	/// Evaluates the wiring multilinear from `inputs`.
370	pub eval_fn: &'a WiringInfo,
371	/// The flat input `eval_fn` reads.
372	pub inputs: Vec<E>,
373	/// The evaluation the prover claims, which `eval_fn` must return.
374	pub claimed: E,
375}
376
377impl<F: BinaryField> WiringEvalClaim<'_, F> {
378	/// Discharges the claim in the field: evaluates the wiring multilinear and compares.
379	///
380	/// This is the discharge for a verifier holding values rather than wires, and it takes
381	/// [`FieldFn::call_native`]'s accelerated path.
382	pub fn check_native(self) -> Result<(), Error> {
383		if self.eval_fn.call_native(&self.inputs) == self.claimed {
384			Ok(())
385		} else {
386			Err(Error::VerificationFailure)
387		}
388	}
389}
390
391impl<'a, E> WiringEvalClaim<'a, E> {
392	/// Exports the claim instead of discharging it.
393	///
394	/// Discharging evaluates the wiring multilinear, which reads every operand term of the system.
395	/// Inside a circuit that cost tracks the inner system.
396	/// So a circuit that pays it can never verify a proof of itself.
397	///
398	/// Exporting hands the claim out whole instead.
399	/// It is settled once, natively, where the cost is ordinary.
400	///
401	/// The claim is short.
402	/// Every section of its input is a challenge vector over a padded log-sized index.
403	/// So the input length is logarithmic in the constraint count.
404	///
405	/// # Correctness
406	///
407	/// Nothing is verified here.
408	/// Nothing is verified later either, unless a holder settles the claim.
409	/// A dropped claim is an unchecked constraint.
410	pub fn defer(self) -> DeferredWiringClaim<E> {
411		DeferredWiringClaim {
412			inputs: self.inputs,
413			claimed: self.claimed,
414		}
415	}
416}
417
418/// A wiring claim that was exported rather than discharged.
419///
420/// Holding one is owing a check.
421///
422/// Settling it needs only the [`WiringInfo`] the claim is about, which is public data.
423/// So it can run far from the verifier that raised the claim.
424///
425/// ```text
426///   verify -> claim -> export -> travels as public values -> settled natively at the root
427/// ```
428#[must_use = "a deferred wiring claim that nobody discharges is an unchecked constraint"]
429#[derive(Debug, Clone, PartialEq, Eq)]
430pub struct DeferredWiringClaim<E> {
431	/// The point the wiring multilinear is claimed to be evaluated at.
432	pub inputs: Vec<E>,
433	/// The evaluation the prover claims.
434	pub claimed: E,
435}
436
437impl<F: BinaryField> DeferredWiringClaim<F> {
438	/// Settles the claim against the wiring matrix it is about.
439	///
440	/// The matrix must be the one the claim was raised over.
441	/// A different one names a different polynomial.
442	/// The check would then be meaningless rather than wrong, so the caller owes that pairing.
443	///
444	/// # Errors
445	///
446	/// Returns an error when the evaluation disagrees with the claim.
447	pub fn check(&self, wiring: &WiringInfo) -> Result<(), Error> {
448		if wiring.call_native(&self.inputs) == self.claimed {
449			Ok(())
450		} else {
451			Err(Error::VerificationFailure)
452		}
453	}
454}
455
456impl<E> WiringEvalClaim<'_, E> {
457	/// Discharges the claim over `channel`'s elements: evaluates the wiring multilinear there and
458	/// asserts it equals the claimed value.
459	///
460	/// This is the discharge for a channel carrying elements as wires, where the evaluation becomes
461	/// a sub-circuit and the comparison an assertion within it. A holder with another way to open a
462	/// claim — a sparse-polynomial argument, say — reads the fields instead.
463	pub fn check_symbolic<F, C>(self, channel: &mut C) -> Result<(), Error>
464	where
465		F: BinaryField,
466		C: IPVerifierChannel<F, Elem = E>,
467		E: FieldOps<Scalar = F> + From<F>,
468	{
469		let Self {
470			eval_fn,
471			inputs,
472			claimed,
473		} = self;
474		let wiring_eval = FieldFn::<F>::call::<E>(eval_fn, &inputs);
475		channel.assert_zero(wiring_eval - claimed)?;
476		Ok(())
477	}
478}
479
480#[cfg(test)]
481mod tests {
482	use binius_field::Field;
483	use binius_math::test_utils::random_scalars;
484	use rand::{RngExt, SeedableRng, rngs::StdRng};
485
486	use super::*;
487	use crate::config::B128;
488
489	#[test]
490	fn test_evaluate_words_mle_matches_naive() {
491		let mut rng = StdRng::seed_from_u64(0);
492		let log_words = 3;
493		// A non-power-of-two word count exercises the implicit zero padding.
494		let words = (0..(1 << log_words) - 3)
495			.map(|_| Word::from_u64(rng.random()))
496			.collect::<Vec<_>>();
497		let r_j = random_scalars::<B128>(&mut rng, Word::LOG_BITS);
498		let r_y = random_scalars::<B128>(&mut rng, log_words);
499
500		// Naive reference: sum the full bit-level eq tensor over every set bit.
501		let full_point = [r_j.clone(), r_y.clone()].concat();
502		let full_tensor = eq_ind_partial_eval_scalars(&full_point);
503		let mut expected = B128::ZERO;
504		for (word_index, word) in words.iter().enumerate() {
505			for bit in 0..Word::BITS {
506				if (word.as_u64() >> bit) & 1 == 1 {
507					expected += full_tensor[(word_index << Word::LOG_BITS) | bit];
508				}
509			}
510		}
511
512		assert_eq!(evaluate_words_mle::<B128, B128>(&words, &r_j, &r_y), expected);
513	}
514}