miden-crypto/src/gkr/sumcheck/tests.rs
src/gkr/sumcheck/tests.rsRaw
1use alloc::sync::Arc;
2use rand::{distributions::Uniform, SeedableRng};
3use winter_crypto::RandomCoin;
4use winter_math::{fields::f64::BaseElement, FieldElement};
5
6use crate::{
7 gkr::{
8 circuit::{CircuitProof, FractionalSumCircuit},
9 multivariate::{
10 compute_claim, gkr_composition_from_composition_polys, ComposedMultiLinears,
11 ComposedMultiLinearsOracle, CompositionPolynomial, EqPolynomial, GkrComposition,
12 GkrCompositionVanilla, LogUpDenominatorTableComposition,
13 LogUpDenominatorWitnessComposition, MultiLinear, MultiLinearOracle,
14 ProjectionComposition, SumComposition,
15 },
16 sumcheck::{
17 prover::sum_check_prove, verifier::sum_check_verify, Claim, FinalEvaluationClaim,
18 FullProof, Witness,
19 },
20 },
21 hash::rpo::Rpo256,
22 rand::RpoRandomCoin,
23};
24
25#[test]
26fn gkr_workflow() {
27 // generate the data witness for the LogUp argument
28 let mut mls = generate_logup_witness::<BaseElement>(3);
29
30 // the is sampled after receiving the main trace commitment
31 let alpha = rand_utils::rand_value();
32
33 // the composition polynomials defining the numerators/denominators
34 let composition_polys: Vec<Vec<Arc<dyn CompositionPolynomial<BaseElement>>>> = vec![
35 // left num
36 vec![Arc::new(ProjectionComposition::new(0))],
37 // right num
38 vec![Arc::new(ProjectionComposition::new(1))],
39 // left den
40 vec![Arc::new(LogUpDenominatorTableComposition::new(2, alpha))],
41 // right den
42 vec![Arc::new(LogUpDenominatorWitnessComposition::new(3, alpha))],
43 ];
44
45 // run the GKR prover to obtain:
46 // 1. The fractional sum circuit output.
47 // 2. GKR proofs up to the last circuit layer counting backwards.
48 // 3. GKR proof (i.e., a sum-check proof) for the last circuit layer counting backwards.
49 let seed = [BaseElement::ZERO; 4];
50 let mut transcript = RpoRandomCoin::new(seed.into());
51 let (circuit_outputs, gkr_before_last_proof, final_layer_proof) =
52 CircuitProof::prove_virtual_bus(composition_polys.clone(), &mut mls, &mut transcript);
53
54 let seed = [BaseElement::ZERO; 4];
55 let mut transcript = RpoRandomCoin::new(seed.into());
56
57 // run the GKR verifier to obtain:
58 // 1. A final evaluation claim.
59 // 2. Randomness defining the Lagrange kernel in the final sum-check protocol. Note that this
60 // Lagrange kernel is different from the one used by the STARK (outer) prover to open the MLs
61 // at the evaluation point.
62 let (final_eval_claim, gkr_lagrange_kernel_rand) = gkr_before_last_proof.verify_virtual_bus(
63 composition_polys.clone(),
64 final_layer_proof,
65 &circuit_outputs,
66 &mut transcript,
67 );
68
69 // the final verification step is composed of:
70 // 1. Querying the oracles for the openings at the evaluation point. This will be done by the
71 // (outer) STARK prover using:
72 // a. The Lagrange kernel (auxiliary) column at the evaluation point.
73 // b. An extra (auxiliary) column to compute an inner product between two vectors. The first
74 // being the Lagrange kernel and the second being (\sum_{j=0}^3 mls[j][i] * \lambda_i)_{i\in\{0,..,n\}}
75 // 2. Evaluating the composition polynomial at the previous openings and checking equality with
76 // the claimed evaluation.
77
78 // 1. Querying the oracles
79
80 let FinalEvaluationClaim {
81 evaluation_point,
82 claimed_evaluation,
83 polynomial,
84 } = final_eval_claim;
85
86 // The evaluation of the EQ polynomial can be done by the verifier directly
87 let eq = (0..gkr_lagrange_kernel_rand.len())
88 .map(|i| {
89 gkr_lagrange_kernel_rand[i] * evaluation_point[i]
90 + (BaseElement::ONE - gkr_lagrange_kernel_rand[i])
91 * (BaseElement::ONE - evaluation_point[i])
92 })
93 .fold(BaseElement::ONE, |acc, term| acc * term);
94
95 // These are the queries to the oracles.
96 // They should be provided by the prover non-deterministically
97 let left_num_eval = mls[0].evaluate(&evaluation_point);
98 let right_num_eval = mls[1].evaluate(&evaluation_point);
99 let left_den_eval = mls[2].evaluate(&evaluation_point);
100 let right_den_eval = mls[3].evaluate(&evaluation_point);
101
102 // The verifier absorbs the claimed openings and generates batching randomness lambda
103 let mut query = vec![left_num_eval, right_num_eval, left_den_eval, right_den_eval];
104 transcript.reseed(Rpo256::hash_elements(&query));
105 let lambdas: Vec<BaseElement> = vec![
106 transcript.draw().unwrap(),
107 transcript.draw().unwrap(),
108 transcript.draw().unwrap(),
109 ];
110 let batched_query =
111 query[0] + query[1] * lambdas[0] + query[2] * lambdas[1] + query[3] * lambdas[2];
112
113 // The prover generates the Lagrange kernel as an auxiliary column
114 let mut rev_evaluation_point = evaluation_point;
115 rev_evaluation_point.reverse();
116 let lagrange_kernel = EqPolynomial::new(rev_evaluation_point).evaluations();
117
118 // The prover generates the additional auxiliary column for the inner product
119 let tmp_col: Vec<BaseElement> = (0..mls[0].len())
120 .map(|i| {
121 mls[0][i] + mls[1][i] * lambdas[0] + mls[2][i] * lambdas[1] + mls[3][i] * lambdas[2]
122 })
123 .collect();
124 let mut running_sum_col = vec![BaseElement::ZERO; tmp_col.len() + 1];
125 running_sum_col[0] = BaseElement::ZERO;
126 for i in 1..(tmp_col.len() + 1) {
127 running_sum_col[i] = running_sum_col[i - 1] + tmp_col[i - 1] * lagrange_kernel[i - 1];
128 }
129
130 // Boundary constraint to check correctness of openings
131 assert_eq!(batched_query, *running_sum_col.last().unwrap());
132
133 // 2) Final evaluation and check
134 query.push(eq);
135 let verifier_computed = polynomial.composer.evaluate(&query);
136
137 assert_eq!(verifier_computed, claimed_evaluation);
138}
139
140pub fn generate_logup_witness<E: FieldElement>(trace_len: usize) -> Vec<MultiLinear<E>> {
141 let num_variables_ml = trace_len;
142 let num_evaluations = 1 << num_variables_ml;
143 let num_witnesses = 1;
144 let (p, q) = generate_logup_data::<E>(num_variables_ml, num_witnesses);
145 let numerators: Vec<Vec<E>> = p.chunks(num_evaluations).map(|x| x.into()).collect();
146 let denominators: Vec<Vec<E>> = q.chunks(num_evaluations).map(|x| x.into()).collect();
147
148 let mut mls = vec![];
149 for i in 0..2 {
150 let ml = MultiLinear::from_values(&numerators[i]);
151 mls.push(ml);
152 }
153 for i in 0..2 {
154 let ml = MultiLinear::from_values(&denominators[i]);
155 mls.push(ml);
156 }
157 mls
158}
159
160pub fn generate_logup_data<E: FieldElement>(
161 trace_len: usize,
162 num_witnesses: usize,
163) -> (Vec<E>, Vec<E>) {
164 use rand::distributions::Slice;
165 use rand::Rng;
166 let n: usize = trace_len;
167 let num_w: usize = num_witnesses; // This should be of the form 2^k - 1
168 let rng = rand::rngs::StdRng::seed_from_u64(0);
169
170 let t_table: Vec<u32> = (0..(1 << n)).collect();
171 let mut m_table: Vec<u32> = (0..(1 << n)).map(|_| 0).collect();
172
173 let t_table_slice = Slice::new(&t_table).unwrap();
174
175 // Construct the witness columns. Uses sampling with replacement in order to have multiplicities
176 // different from 1.
177 let mut w_tables = Vec::new();
178 for _ in 0..num_w {
179 let wi_table: Vec<u32> =
180 rng.clone().sample_iter(&t_table_slice).cloned().take(1 << n).collect();
181
182 // Construct the multiplicities
183 wi_table.iter().for_each(|w| {
184 m_table[*w as usize] += 1;
185 });
186 w_tables.push(wi_table)
187 }
188
189 // The numerators
190 let mut p: Vec<E> = m_table.iter().map(|m| E::from(*m as u32)).collect();
191 p.extend((0..(num_w * (1 << n))).map(|_| E::from(1_u32)).collect::<Vec<E>>());
192
193 // Construct the denominators
194 let mut q: Vec<E> = t_table.iter().map(|t| E::from(*t)).collect();
195 for w_table in w_tables {
196 q.extend(w_table.iter().map(|w| E::from(*w)).collect::<Vec<E>>());
197 }
198 (p, q)
199}