1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
use super::SumcheckRandomScalars;
use crate::base::{
map::{IndexMap, IndexSet},
polynomial::{
compute_rho_eval, compute_truncated_lagrange_basis_inner_product,
compute_truncated_lagrange_basis_sum,
},
scalar::Scalar,
};
use core::iter::IntoIterator;
/// Evaluations for different MLEs at the random point chosen for sumcheck
#[derive(Default)]
pub struct SumcheckMleEvaluations<'a, S: Scalar> {
/// The evaluation (at the random point generated by sumcheck) of an MLE `{x_i}` where
/// `x_i = 1` if `i < length;`
/// = 0, otherwise
pub chi_evaluations: IndexMap<usize, S>,
/// The evaluation (at the random point generated by sumcheck) of an MLE `{x_i}` where
/// `x_i = i` if `i < length;`
/// = 0, otherwise
pub rho_evaluations: IndexMap<usize, S>,
/// The evaluation (at the random point generated by sumcheck) of an MLE `{x_i}` where
/// `x_i = 1` if `i == 0;`
/// = 0, otherwise
pub singleton_chi_evaluation: S,
/// The evaluation (at the random point generated by sumcheck) of the MLE formed from entrywise random scalars.
///
/// This is used within sumcheck to establish that a given expression
/// is zero across all entries.
pub random_evaluation: S,
/// The evaluations (at the random point generated by sumcheck) of the first round mles that are evaluated by the inner product argument. These are batched together and checked by a single IPA.
pub first_round_pcs_proof_evaluations: &'a [S],
/// The evaluations (at the random point generated by sumcheck) of the final round mles that are evaluated by the inner product argument. These are batched together and checked by a single IPA.
pub final_round_pcs_proof_evaluations: &'a [S],
/// Evaluation (at the random point generated by sumcheck) of the function `rho_256` that is defined by `rho_256(x)` = x when 0 <= x < 256 and 0 otherwise.
pub rho_256_evaluation: Option<S>,
}
#[expect(
clippy::missing_panics_doc,
reason = "Assertions ensure preconditions are met, eliminating the possibility of panic."
)]
impl<'a, S: Scalar> SumcheckMleEvaluations<'a, S> {
/// Constructs the evaluations for the sumcheck MLEs.
///
/// # Inputs
/// - `evaluation_point` - the point, outputted by sumcheck, at which to evaluate the MLEs
/// - `sumcheck_random_scalars` - the random scalars used to batch the evaluations that are proven via IPA
/// - `first_round_pcs_proof_evaluations` - the evaluations of the first round MLEs that are proven via IPA
/// - `final_round_pcs_proof_evaluations` - the evaluations of the final round MLEs that are proven via IPA
pub fn new(
range_length: usize,
chi_evaluation_lengths: impl IntoIterator<Item = usize>,
rho_evaluation_lengths: impl IntoIterator<Item = usize>,
evaluation_point: &[S],
sumcheck_random_scalars: &SumcheckRandomScalars<S>,
first_round_pcs_proof_evaluations: &'a [S],
final_round_pcs_proof_evaluations: &'a [S],
) -> Self {
let rho_256_evaluation = if evaluation_point.len() < 8 {
None
} else {
let rho_256_intermediate = evaluation_point
.iter()
.take(8)
.rev()
.fold(S::ZERO, |acc, &x| acc * S::TWO + x);
Some(
evaluation_point
.iter()
.skip(8)
.fold(rho_256_intermediate, |acc, &x| acc * (S::ONE - x)),
)
};
assert_eq!(
evaluation_point.len(),
sumcheck_random_scalars.entrywise_point.len()
);
assert_eq!(range_length, sumcheck_random_scalars.table_length);
let random_evaluation = compute_truncated_lagrange_basis_inner_product(
range_length,
evaluation_point,
sumcheck_random_scalars.entrywise_point,
);
let unique_chi_evaluation_lengths: IndexSet<usize> =
chi_evaluation_lengths.into_iter().collect();
let chi_evaluations = unique_chi_evaluation_lengths
.iter()
.map(|&length| {
(
length,
compute_truncated_lagrange_basis_sum(length, evaluation_point),
)
})
.collect();
let rho_evaluations = rho_evaluation_lengths
.into_iter()
.map(|length| (length, compute_rho_eval(length, evaluation_point)))
.collect();
let singleton_chi_evaluation = compute_truncated_lagrange_basis_sum(1, evaluation_point);
Self {
chi_evaluations,
rho_evaluations,
singleton_chi_evaluation,
random_evaluation,
first_round_pcs_proof_evaluations,
final_round_pcs_proof_evaluations,
rho_256_evaluation,
}
}
}