binius_ip/sumcheck/
infinity.rs1use binius_field::{Field, field::FieldOps};
22use binius_math::univariate::evaluate_univariate;
23
24use crate::{
25 channel::IPVerifierChannel,
26 sumcheck::{BatchSumcheckOutput, Error, RoundCoeffs, RoundProof, SumcheckOutput},
27};
28
29pub fn verify<F, C>(
40 n_vars: usize,
41 degree: usize,
42 mut sum: C::Elem,
43 channel: &mut C,
44) -> Result<SumcheckOutput<C::Elem>, Error>
45where
46 F: Field,
47 C: IPVerifierChannel<F>,
48{
49 let mut challenges = Vec::with_capacity(n_vars);
50 for _round in 0..n_vars {
51 let round_proof = RoundProof(RoundCoeffs(channel.recv_many(degree)?));
52 let challenge = channel.sample();
53
54 sum = round_proof.recover_infinity(sum).evaluate(&challenge);
55 challenges.push(challenge);
56 }
57
58 Ok(SumcheckOutput {
59 eval: sum,
60 challenges,
61 })
62}
63
64pub fn batch_verify<F, C>(
71 n_vars: usize,
72 degree: usize,
73 sums: &[C::Elem],
74 channel: &mut C,
75) -> Result<BatchSumcheckOutput<C::Elem>, Error>
76where
77 F: Field,
78 C: IPVerifierChannel<F>,
79{
80 let batch_coeff = channel.sample();
81 let sum = evaluate_univariate(sums, &batch_coeff);
82
83 let SumcheckOutput { eval, challenges } = verify::<F, C>(n_vars, degree, sum, channel)?;
84
85 Ok(BatchSumcheckOutput {
86 batch_coeff,
87 eval,
88 challenges,
89 })
90}
91
92pub fn to_mle_point<F: FieldOps>(point: &[F]) -> (Vec<F>, Vec<F>) {
107 let mut scales = Vec::with_capacity(point.len() + 1);
108 scales.push(F::one());
109 let sigma = point
110 .iter()
111 .map(|rho_j| {
112 let one_plus_rho = F::one() + rho_j;
113 let scale = scales.last().expect("scales starts non-empty").clone() * &one_plus_rho;
114 scales.push(scale);
115 rho_j.clone() * one_plus_rho.invert_or_zero()
116 })
117 .collect();
118 (sigma, scales)
119}
120
121#[cfg(test)]
122mod tests {
123 use binius_field::arch::OptimalB128 as B128;
124 use binius_math::{
125 multilinear::{
126 eq::eq_ind_partial_eval_scalars,
127 hypercube::{InfCube, eq_ind_partial_eval_scalars as monomials},
128 },
129 test_utils::random_scalars,
130 };
131 use rand::prelude::*;
132
133 use super::*;
134
135 #[test]
136 fn recover_infinity_round_trips() {
137 let mut rng = StdRng::seed_from_u64(0);
138 for degree in 1..=4 {
139 let coeffs = RoundCoeffs(random_scalars::<B128>(&mut rng, degree + 1));
140 let sum = coeffs[0] + coeffs[degree];
142 assert_eq!(coeffs.clone().truncate().recover_infinity(sum), coeffs);
143 }
144 }
145
146 #[test]
147 fn to_mle_point_matches_the_monomial_evaluation() {
148 let mut rng = StdRng::seed_from_u64(0);
149 let n_vars = 4;
150 let point = random_scalars::<B128>(&mut rng, n_vars);
151 let (sigma, scales) = to_mle_point(&point);
152 for k in 0..=n_vars {
153 let u = random_scalars::<B128>(&mut rng, 1 << k);
154 let dot = |basis: Vec<B128>| u.iter().zip(basis).map(|(u, b)| *u * b).sum::<B128>();
155 let monomial_eval = dot(monomials::<InfCube, B128>(&point[..k]));
156 let mle_eval = dot(eq_ind_partial_eval_scalars(&sigma[..k]));
157 assert_eq!(monomial_eval, scales[k] * mle_eval, "k={k}");
158 }
159 }
160}