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}