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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
use alloc::vec::Vec;
use p3_challenger::{FieldChallenger, GrindingChallenger};
use p3_field::{ExtensionField, Field};
use p3_multilinear_util::point::Point;
use serde::{Deserialize, Serialize};
use crate::SumcheckError;
use crate::strategy::Basis;
/// Sumcheck polynomial data
///
/// Stores the polynomial evaluations for sumcheck rounds in a compact format.
/// Each round stores two evaluations: `[h(0), h(inf)]` in the evaluation
/// basis (`h(1)` derived as `claimed_sum - h(0)`), or `[s(1), s(inf)]` in the
/// projective basis (`s(0)` derived as `claimed_sum - s(inf)`).
#[derive(Default, Serialize, Deserialize, Clone, Debug)]
pub struct SumcheckData<F, EF> {
/// Polynomial evaluations for each sumcheck round.
///
/// Each entry is `[h(0), h(inf)]`:
/// - `h(0)` is the constant term.
/// - `h(inf)` is the leading coefficient (evaluation at infinity).
///
/// `h(1)` is derived as `claimed_sum - h(0)` by the verifier.
///
/// Length: folding_factor
pub polynomial_evaluations: Vec<[EF; 2]>,
/// PoW witnesses for each sumcheck round
/// Length: folding_factor
pub pow_witnesses: Vec<F>,
}
impl<F, EF> SumcheckData<F, EF> {
/// Returns the polynomial evaluations `[h(0), h(inf)]` for each round.
#[must_use]
pub fn polynomial_evaluations(&self) -> &[[EF; 2]] {
&self.polynomial_evaluations
}
/// Returns the number of rounds stored in this proof data.
#[must_use]
pub const fn num_rounds(&self) -> usize {
self.polynomial_evaluations.len()
}
/// Commits polynomial coefficients to the transcript and returns a challenge.
///
/// This helper function handles the Fiat-Shamir interaction for a sumcheck round.
///
/// # Arguments
///
/// * `challenger` - Fiat-Shamir transcript.
/// * `c_a` - Finite-point value: `h(0)` (evaluation) or `s(1)` (projective).
/// * `c_inf` - Leading coefficient `h(inf)` / `s(inf)`.
/// * `pow_bits` - PoW difficulty (0 to skip grinding).
///
/// # Returns
///
/// The sampled challenge `r`.
///
/// The two values are recorded and absorbed verbatim; which basis defines
/// them is the caller's business, and must match the [`Basis`] the
/// verifier later passes to [`Self::verify_rounds`].
pub fn observe_and_sample<Challenger, BF>(
&mut self,
challenger: &mut Challenger,
c_a: EF,
c_inf: EF,
pow_bits: usize,
) -> EF
where
BF: Field,
EF: ExtensionField<BF>,
F: Clone,
Challenger: FieldChallenger<BF> + GrindingChallenger<Witness = F>,
{
// Record the polynomial coefficients in the proof.
self.polynomial_evaluations.push([c_a, c_inf]);
// Absorb coefficients into the transcript.
//
// Two of the quadratic's three values cross the wire; the verifier
// derives the third from the basis-dependent round identity.
challenger.observe_algebra_slice(&[c_a, c_inf]);
// Optional proof-of-work to increase prover cost.
//
// This makes it expensive for a malicious prover to "mine" favorable challenges.
if pow_bits > 0 {
self.pow_witnesses.push(challenger.grind(pow_bits));
}
// Sample the verifier's challenge for this round.
challenger.sample_algebra_element()
}
/// Verifies standard sumcheck rounds and extracts folding randomness from the transcript.
///
/// # Arguments
///
/// * `challenger` - Fiat-Shamir transcript.
/// * `claimed_sum` - Running claim, folded in place to `h(r)` after each round.
/// * `expected_rounds` - Protocol-fixed number of rounds this proof must carry.
/// * `pow_bits` - PoW difficulty (0 to skip grinding).
///
/// # Returns
///
/// A `Point` of folding randomness values, one per round.
///
/// # Errors
///
/// Returns `RoundCountMismatch` if the proof does not carry exactly `expected_rounds` rounds.
///
/// The folding-challenge count is derived from the proof itself.
/// A wrong count would desync Fiat-Shamir rather than reject, so it is bound here.
pub fn verify_rounds<Challenger>(
&self,
challenger: &mut Challenger,
claimed_sum: &mut EF,
expected_rounds: usize,
pow_bits: usize,
basis: Basis,
) -> Result<Point<EF>, SumcheckError>
where
F: Field,
EF: ExtensionField<F>,
Challenger: FieldChallenger<F> + GrindingChallenger<Witness = F>,
{
// Bind the round count to the protocol-fixed value before folding anything.
//
// Centralizing the check here makes the safe path the only path:
// every caller is forced to declare how many rounds it expects.
if self.polynomial_evaluations.len() != expected_rounds {
return Err(SumcheckError::RoundCountMismatch {
expected: expected_rounds,
actual: self.polynomial_evaluations.len(),
});
}
let mut randomness = Vec::with_capacity(self.polynomial_evaluations.len());
// Grinding pushes one witness per round;
//
// Reject upfront if the proof is short so the loop below cannot panic on out-of-bounds indexing.
if pow_bits > 0 && self.pow_witnesses.len() != self.polynomial_evaluations.len() {
return Err(SumcheckError::PowWitnessCountMismatch {
expected: self.polynomial_evaluations.len(),
actual: self.pow_witnesses.len(),
});
}
for (i, &[c_a, c_inf]) in self.polynomial_evaluations.iter().enumerate() {
// Observe only the sent polynomial evaluations; their meaning is
// basis-dependent ([h(0), h(inf)] or [s(1), s(inf)]).
challenger.observe_algebra_slice(&[c_a, c_inf]);
// Verify PoW (only if pow_bits > 0)
if pow_bits > 0 && !challenger.check_witness(pow_bits, self.pow_witnesses[i]) {
return Err(SumcheckError::InvalidPowWitness);
}
// Sample the challenge and reconstruct h(r); the basis-dependent
// round identity supplies the third quadratic value (shared with
// the prover via Basis::reduce_claim).
let r: EF = challenger.sample_algebra_element();
*claimed_sum = basis.reduce_claim(c_a, c_inf, r, *claimed_sum);
randomness.push(r);
}
Ok(Point::new(randomness))
}
}
/// Verify the final sumcheck rounds.
///
/// This is a free function because the caller may not have a `SumcheckData` at all when `rounds == 0`.
///
/// # Returns
///
/// A `Point` of folding randomness values.
pub fn verify_final_sumcheck_rounds<F, EF, Challenger>(
final_sumcheck: Option<&SumcheckData<F, EF>>,
challenger: &mut Challenger,
claimed_sum: &mut EF,
rounds: usize,
pow_bits: usize,
basis: Basis,
) -> Result<Point<EF>, SumcheckError>
where
F: Field,
EF: ExtensionField<F>,
Challenger: FieldChallenger<F> + GrindingChallenger<Witness = F>,
{
if rounds == 0 {
return Ok(Point::new(Vec::new()));
}
let sumcheck = final_sumcheck.ok_or(SumcheckError::MissingSumcheckData {
expected_rounds: rounds,
})?;
// `verify_rounds` binds the round count to `rounds`.
sumcheck.verify_rounds(challenger, claimed_sum, rounds, pow_bits, basis)
}