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 circuit_outputs =
63 (circuit_outputs[0], circuit_outputs[1], circuit_outputs[2], circuit_outputs[3]);
64 let (final_eval_claim, gkr_lagrange_kernel_rand) = gkr_before_last_proof.verify_virtual_bus(
65 composition_polys.clone(),
66 final_layer_proof,
67 &circuit_outputs,
68 &mut transcript,
69 );
70
71 // the final verification step is composed of:
72 // 1. Querying the oracles for the openings at the evaluation point. This will be done by the
73 // (outer) STARK prover using:
74 // a. The Lagrange kernel (auxiliary) column at the evaluation point.
75 // b. An extra (auxiliary) column to compute an inner product between two vectors. The first
76 // being the Lagrange kernel and the second being (\sum_{j=0}^3 mls[j][i] * \lambda_i)_{i\in\{0,..,n\}}
77 // 2. Evaluating the composition polynomial at the previous openings and checking equality with
78 // the claimed evaluation.
79
80 // 1. Querying the oracles
81
82 let FinalEvaluationClaim {
83 evaluation_point,
84 claimed_evaluation,
85 polynomial,
86 } = final_eval_claim;
87
88 // The evaluation of the EQ polynomial can be done by the verifier directly
89 let eq = (0..gkr_lagrange_kernel_rand.len())
90 .map(|i| {
91 gkr_lagrange_kernel_rand[i] * evaluation_point[i]
92 + (BaseElement::ONE - gkr_lagrange_kernel_rand[i])
93 * (BaseElement::ONE - evaluation_point[i])
94 })
95 .fold(BaseElement::ONE, |acc, term| acc * term);
96
97 // These are the queries to the oracles.
98 // They should be provided by the prover non-deterministically
99 let left_num_eval = mls[0].evaluate(&evaluation_point);
100 let right_num_eval = mls[1].evaluate(&evaluation_point);
101 let left_den_eval = mls[2].evaluate(&evaluation_point);
102 let right_den_eval = mls[3].evaluate(&evaluation_point);
103
104 // The verifier absorbs the claimed openings and generates batching randomness
105 let mut query = vec![left_num_eval, right_num_eval, left_den_eval, right_den_eval];
106 transcript.reseed(Rpo256::hash_elements(&query));
107 let lambdas: Vec<BaseElement> = vec![
108 transcript.draw().unwrap(),
109 transcript.draw().unwrap(),
110 transcript.draw().unwrap(),
111 ];
112 let batched_query =
113 query[0] + query[1] * lambdas[0] + query[2] * lambdas[1] + query[3] * lambdas[2];
114
115 // The prover generates the Lagrange kernel
116 let mut rev_evaluation_point = evaluation_point;
117 rev_evaluation_point.reverse();
118 let lagrange_kernel = EqPolynomial::new(rev_evaluation_point).evaluations();
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
125 // The prover generates the additional auxiliary column for the inner product
126 let mut running_sum_col = vec![BaseElement::ZERO; tmp_col.len() + 1];
127 running_sum_col[0] = BaseElement::ZERO;
128 for i in 1..(tmp_col.len() + 1) {
129 running_sum_col[i] = running_sum_col[i - 1] + tmp_col[i - 1] * lagrange_kernel[i - 1];
130 }
131
132 // Boundary constraint to check correctness of openings
133 assert_eq!(batched_query, *running_sum_col.last().unwrap());
134
135 // 2) Final evaluation and check
136 query.push(eq);
137 let verifier_computed = polynomial.composer.evaluate(&query);
138
139 assert_eq!(verifier_computed, claimed_evaluation);
140}
141
142pub fn generate_logup_witness<E: FieldElement>(trace_len: usize) -> Vec<MultiLinear<E>> {
143 let num_variables_ml = trace_len;
144 let num_evaluations = 1 << num_variables_ml;
145 let num_witnesses = 1;
146 let (p, q) = generate_logup_data::<E>(num_variables_ml, num_witnesses);
147 let numerators: Vec<Vec<E>> = p.chunks(num_evaluations).map(|x| x.into()).collect();
148 let denominators: Vec<Vec<E>> = q.chunks(num_evaluations).map(|x| x.into()).collect();
149
150 let mut mls = vec![];
151 for i in 0..2 {
152 let ml = MultiLinear::from_values(&numerators[i]);
153 mls.push(ml);
154 }
155 for i in 0..2 {
156 let ml = MultiLinear::from_values(&denominators[i]);
157 mls.push(ml);
158 }
159 mls
160}
161
162pub fn generate_logup_data<E: FieldElement>(
163 trace_len: usize,
164 num_witnesses: usize,
165) -> (Vec<E>, Vec<E>) {
166 use rand::distributions::Slice;
167 use rand::Rng;
168 let n: usize = trace_len;
169 let num_w: usize = num_witnesses; // This should be of the form 2^k - 1
170 let rng = rand::rngs::StdRng::seed_from_u64(0);
171
172 let t_table: Vec<u32> = (0..(1 << n)).collect();
173 let mut m_table: Vec<u32> = (0..(1 << n)).map(|_| 0).collect();
174
175 let t_table_slice = Slice::new(&t_table).unwrap();
176
177 // Construct the witness columns. Uses sampling with replacement in order to have multiplicities
178 // different from 1.
179 let mut w_tables = Vec::new();
180 for _ in 0..num_w {
181 let wi_table: Vec<u32> =
182 rng.clone().sample_iter(&t_table_slice).cloned().take(1 << n).collect();
183
184 // Construct the multiplicities
185 wi_table.iter().for_each(|w| {
186 m_table[*w as usize] += 1;
187 });
188 w_tables.push(wi_table)
189 }
190
191 // The numerators
192 let mut p: Vec<E> = m_table.iter().map(|m| E::from(*m as u32)).collect();
193 p.extend((0..(num_w * (1 << n))).map(|_| E::from(1_u32)).collect::<Vec<E>>());
194
195 // Construct the denominators
196 let mut q: Vec<E> = t_table.iter().map(|t| E::from(*t)).collect();
197 for w_table in w_tables {
198 q.extend(w_table.iter().map(|w| E::from(*w)).collect::<Vec<E>>());
199 }
200 (p, q)
201}