binius_verifier/ring_switch.rs
1// Copyright 2025 Irreducible Inc.
2
3use binius_field::{BinaryField, ExtensionField, FieldOps, PackedField};
4use binius_ip::channel::IPVerifierChannel;
5use binius_math::{
6 multilinear::{
7 eq::{eq_ind_partial_eval_scalars, eq_ind_zero},
8 eq_prefix::eq_ind_prefix_eval_tensor_algebra,
9 evaluate::evaluate_inplace_scalars,
10 },
11 tensor_algebra::TensorAlgebra,
12};
13
14use crate::config::B1;
15
16#[derive(Debug, thiserror::Error)]
17pub enum Error {
18 #[error("channel: {0}")]
19 Channel(#[from] binius_ip::channel::Error),
20}
21
22/// Output of ring-switching verification.
23pub struct RingSwitchVerifyOutput<F: FieldOps> {
24 /// The row-batching challenges (expanded via eq_ind).
25 pub eq_r_double_prime: Vec<F>,
26 /// The verified sumcheck claim for BaseFold.
27 pub sumcheck_claim: F,
28}
29
30/// Verify the ring-switching reduction.
31///
32/// Takes the expected evaluation claim and eval point, and:
33/// 1. Receives s_hat_v from prover via channel
34/// 2. Verifies the partial evaluation matches the expected claim
35/// 3. Samples row-batching challenges
36/// 4. Computes the sumcheck claim for BaseFold
37///
38/// Returns the eq_r_double_prime (for final check) and sumcheck claim.
39///
40/// ## Arguments
41///
42/// * `evaluation_claim` - the expected evaluation of the B1 polynomial
43/// * `eval_point` - the evaluation point from shift reduction
44/// * `channel` - the verifier channel for receiving/sampling
45///
46/// ## Preconditions
47///
48/// * `eval_point.len()` must equal `log_witness_elems + log_packing` where log_packing is the
49/// base-2 log of the extension degree of F over B1
50pub fn verify<F, C>(
51 evaluation_claim: C::Elem,
52 eval_point: &[C::Elem],
53 channel: &mut C,
54) -> Result<RingSwitchVerifyOutput<C::Elem>, Error>
55where
56 F: BinaryField + PackedField<Scalar = F>,
57 C: IPVerifierChannel<F>,
58 C::Elem: FieldOps<Scalar = F> + From<F>,
59{
60 let log_packing = F::LOG_DEGREE;
61 let (eval_point_low, _eval_point_high) = eval_point.split_at(log_packing);
62
63 // Receive s_hat_v
64 let s_hat_v = channel.recv_many(1 << log_packing)?;
65
66 // Verify partial eval matches expected claim
67 let computed_claim = evaluate_inplace_scalars(s_hat_v.clone(), eval_point_low);
68 channel.assert_zero(evaluation_claim - computed_claim)?;
69
70 // Basis transpose
71 let s_hat_u = TensorAlgebra::<B1, C::Elem>::new(s_hat_v).transpose();
72
73 // Sample r_double_prime
74 let r_double_prime = channel.sample_many(log_packing);
75 let eq_r_double_prime = eq_ind_partial_eval_scalars(&r_double_prime);
76
77 // Compute sumcheck claim
78 let sumcheck_claim = evaluate_inplace_scalars(s_hat_u.elems, &r_double_prime);
79
80 Ok(RingSwitchVerifyOutput {
81 eq_r_double_prime,
82 sumcheck_claim,
83 })
84}
85
86/// Evaluate the ring switching equality indicator at a given point.
87///
88/// The ring switching equality indicator is the multilinear function $A$ from [DP24],
89/// Construction 3.1, generalized to an oracle of `n_pack` entries rather than a power of two
90/// (binius.xyz#128, §Ring-Switching): its cell factor is the prefix indicator
91/// $\mathrm{eq}_{<n}(z, y)$, so $A$ vanishes above the oracle. It is evaluated succinctly by
92/// computing that indicator over the tensor algebra, where the first components live in the
93/// vertical subring and the later components live in the horizontal subring. Then we apply
94/// row-batching to the tensor algebra element.
95///
96/// `z_vals` may have more coordinates than `query`, when the claim spans a wider word-index space
97/// than the oracle. The oracle is zero there, so those surplus coordinates contribute
98/// $c = \prod_j (1 - z_j)$. The row-batching map is only $\mathbb{F}_2$-linear, so $c$ enters
99/// through the vertical subring rather than as a scalar on the result.
100///
101/// ## Arguments
102///
103/// * `n_pack` - the oracle's length
104/// * `z_vals` - the vertical evaluation point
105/// * `query` - the horizontal evaluation point, over the oracle's variables
106/// * `expanded_row_batch_query` - the scaling elements for row-batching
107///
108/// ## Pre-conditions
109///
110/// * `z_vals` has at least as many components as `query`
111/// * `n_pack` is at most `2^query.len()`
112/// * the length of `expanded_row_batch_query` must equal `FE::DEGREE`
113///
114/// [DP24]: <https://eprint.iacr.org/2024/504>
115pub fn eval_rs_eq<F>(n_pack: usize, z_vals: &[F], query: &[F], expanded_row_batch_query: &[F]) -> F
116where
117 F: FieldOps<Scalar: BinaryField>,
118{
119 assert!(z_vals.len() >= query.len()); // pre-condition
120 assert_eq!(expanded_row_batch_query.len(), F::Scalar::DEGREE,); // pre-condition
121
122 let (z_vals, surplus) = z_vals.split_at(query.len());
123 eq_ind_prefix_eval_tensor_algebra::<B1, F>(n_pack, z_vals, query)
124 .scale_vertical(&eq_ind_zero(surplus))
125 .fold_vertical(expanded_row_batch_query)
126}