testudo/src/product_tree.rs
src/product_tree.rsRaw
1#![allow(dead_code)]
2use crate::poseidon_transcript::PoseidonTranscript;
3
4use super::dense_mlpoly::DensePolynomial;
5use super::dense_mlpoly::EqPolynomial;
6use super::math::Math;
7use super::scalar::Scalar;
8use super::sumcheck::SumcheckInstanceProof;
9use super::transcript::ProofTranscript;
10use ark_serialize::*;
11use ark_std::One;
12
13#[derive(Debug)]
14pub struct ProductCircuit {
15 left_vec: Vec<DensePolynomial>,
16 right_vec: Vec<DensePolynomial>,
17}
18
19impl ProductCircuit {
20 fn compute_layer(
21 inp_left: &DensePolynomial,
22 inp_right: &DensePolynomial,
23 ) -> (DensePolynomial, DensePolynomial) {
24 let len = inp_left.len() + inp_right.len();
25 let outp_left = (0..len / 4)
26 .map(|i| inp_left[i] * inp_right[i])
27 .collect::<Vec<Scalar>>();
28 let outp_right = (len / 4..len / 2)
29 .map(|i| inp_left[i] * inp_right[i])
30 .collect::<Vec<Scalar>>();
31
32 (
33 DensePolynomial::new(outp_left),
34 DensePolynomial::new(outp_right),
35 )
36 }
37
38 pub fn new(poly: &DensePolynomial) -> Self {
39 let mut left_vec: Vec<DensePolynomial> = Vec::new();
40 let mut right_vec: Vec<DensePolynomial> = Vec::new();
41
42 let num_layers = poly.len().log_2();
43 let (outp_left, outp_right) = poly.split(poly.len() / 2);
44
45 left_vec.push(outp_left);
46 right_vec.push(outp_right);
47
48 for i in 0..num_layers - 1 {
49 let (outp_left, outp_right) = ProductCircuit::compute_layer(&left_vec[i], &right_vec[i]);
50 left_vec.push(outp_left);
51 right_vec.push(outp_right);
52 }
53
54 ProductCircuit {
55 left_vec,
56 right_vec,
57 }
58 }
59
60 pub fn evaluate(&self) -> Scalar {
61 let len = self.left_vec.len();
62 assert_eq!(self.left_vec[len - 1].get_num_vars(), 0);
63 assert_eq!(self.right_vec[len - 1].get_num_vars(), 0);
64 self.left_vec[len - 1][0] * self.right_vec[len - 1][0]
65 }
66}
67
68pub struct DotProductCircuit {
69 left: DensePolynomial,
70 right: DensePolynomial,
71 weight: DensePolynomial,
72}
73
74impl DotProductCircuit {
75 pub fn new(left: DensePolynomial, right: DensePolynomial, weight: DensePolynomial) -> Self {
76 assert_eq!(left.len(), right.len());
77 assert_eq!(left.len(), weight.len());
78 DotProductCircuit {
79 left,
80 right,
81 weight,
82 }
83 }
84
85 pub fn evaluate(&self) -> Scalar {
86 (0..self.left.len())
87 .map(|i| self.left[i] * self.right[i] * self.weight[i])
88 .sum()
89 }
90
91 pub fn split(&mut self) -> (DotProductCircuit, DotProductCircuit) {
92 let idx = self.left.len() / 2;
93 assert_eq!(idx * 2, self.left.len());
94 let (l1, l2) = self.left.split(idx);
95 let (r1, r2) = self.right.split(idx);
96 let (w1, w2) = self.weight.split(idx);
97 (
98 DotProductCircuit {
99 left: l1,
100 right: r1,
101 weight: w1,
102 },
103 DotProductCircuit {
104 left: l2,
105 right: r2,
106 weight: w2,
107 },
108 )
109 }
110}
111
112#[allow(dead_code)]
113#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
114pub struct LayerProof {
115 pub proof: SumcheckInstanceProof,
116 pub claims: Vec<Scalar>,
117}
118
119#[allow(dead_code)]
120impl LayerProof {
121 pub fn verify(
122 &self,
123 claim: Scalar,
124 num_rounds: usize,
125 degree_bound: usize,
126 transcript: &mut PoseidonTranscript,
127 ) -> (Scalar, Vec<Scalar>) {
128 self
129 .proof
130 .verify(claim, num_rounds, degree_bound, transcript)
131 .unwrap()
132 }
133}
134
135#[allow(dead_code)]
136#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
137pub struct LayerProofBatched {
138 pub proof: SumcheckInstanceProof,
139 pub claims_prod_left: Vec<Scalar>,
140 pub claims_prod_right: Vec<Scalar>,
141}
142
143#[allow(dead_code)]
144impl LayerProofBatched {
145 pub fn verify(
146 &self,
147 claim: Scalar,
148 num_rounds: usize,
149 degree_bound: usize,
150 transcript: &mut PoseidonTranscript,
151 ) -> (Scalar, Vec<Scalar>) {
152 self
153 .proof
154 .verify(claim, num_rounds, degree_bound, transcript)
155 .unwrap()
156 }
157}
158
159#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
160pub struct ProductCircuitEvalProof {
161 proof: Vec<LayerProof>,
162}
163
164#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
165pub struct ProductCircuitEvalProofBatched {
166 proof: Vec<LayerProofBatched>,
167 claims_dotp: (Vec<Scalar>, Vec<Scalar>, Vec<Scalar>),
168}
169
170impl ProductCircuitEvalProof {
171 #![allow(dead_code)]
172 pub fn prove(
173 circuit: &mut ProductCircuit,
174 transcript: &mut PoseidonTranscript,
175 ) -> (Self, Scalar, Vec<Scalar>) {
176 let mut proof: Vec<LayerProof> = Vec::new();
177 let num_layers = circuit.left_vec.len();
178
179 let mut claim = circuit.evaluate();
180 let mut rand = Vec::new();
181 for layer_id in (0..num_layers).rev() {
182 let len = circuit.left_vec[layer_id].len() + circuit.right_vec[layer_id].len();
183
184 let mut poly_C = DensePolynomial::new(EqPolynomial::new(rand.clone()).evals());
185 assert_eq!(poly_C.len(), len / 2);
186
187 let num_rounds_prod = poly_C.len().log_2();
188 let comb_func_prod = |poly_A_comp: &Scalar,
189 poly_B_comp: &Scalar,
190 poly_C_comp: &Scalar|
191 -> Scalar { (*poly_A_comp) * poly_B_comp * poly_C_comp };
192 let (proof_prod, rand_prod, claims_prod) = SumcheckInstanceProof::prove_cubic(
193 &claim,
194 num_rounds_prod,
195 &mut circuit.left_vec[layer_id],
196 &mut circuit.right_vec[layer_id],
197 &mut poly_C,
198 comb_func_prod,
199 transcript,
200 );
201
202 transcript.append_scalar(&claims_prod[0]);
203 transcript.append_scalar(&claims_prod[1]);
204
205 // produce a random challenge
206 let r_layer = transcript.challenge_scalar();
207 claim = claims_prod[0] + r_layer * (claims_prod[1] - claims_prod[0]);
208
209 let mut ext = vec![r_layer];
210 ext.extend(rand_prod);
211 rand = ext;
212
213 proof.push(LayerProof {
214 proof: proof_prod,
215 claims: claims_prod[0..claims_prod.len() - 1].to_vec(),
216 });
217 }
218
219 (ProductCircuitEvalProof { proof }, claim, rand)
220 }
221
222 pub fn verify(
223 &self,
224 eval: Scalar,
225 len: usize,
226 transcript: &mut PoseidonTranscript,
227 ) -> (Scalar, Vec<Scalar>) {
228 let num_layers = len.log_2();
229 let mut claim = eval;
230 let mut rand: Vec<Scalar> = Vec::new();
231 //let mut num_rounds = 0;
232 assert_eq!(self.proof.len(), num_layers);
233 for (num_rounds, i) in (0..num_layers).enumerate() {
234 let (claim_last, rand_prod) = self.proof[i].verify(claim, num_rounds, 3, transcript);
235
236 let claims_prod = &self.proof[i].claims;
237 transcript.append_scalar(&claims_prod[0]);
238 transcript.append_scalar(&claims_prod[1]);
239
240 assert_eq!(rand.len(), rand_prod.len());
241 let eq: Scalar = (0..rand.len())
242 .map(|i| {
243 rand[i] * rand_prod[i] + (Scalar::one() - rand[i]) * (Scalar::one() - rand_prod[i])
244 })
245 .product();
246 assert_eq!(claims_prod[0] * claims_prod[1] * eq, claim_last);
247
248 // produce a random challenge
249 let r_layer = transcript.challenge_scalar();
250 claim = (Scalar::one() - r_layer) * claims_prod[0] + r_layer * claims_prod[1];
251 let mut ext = vec![r_layer];
252 ext.extend(rand_prod);
253 rand = ext;
254 }
255
256 (claim, rand)
257 }
258}
259
260impl ProductCircuitEvalProofBatched {
261 pub fn prove(
262 prod_circuit_vec: &mut Vec<&mut ProductCircuit>,
263 dotp_circuit_vec: &mut Vec<&mut DotProductCircuit>,
264 transcript: &mut PoseidonTranscript,
265 ) -> (Self, Vec<Scalar>) {
266 assert!(!prod_circuit_vec.is_empty());
267
268 let mut claims_dotp_final = (Vec::new(), Vec::new(), Vec::new());
269
270 let mut proof_layers: Vec<LayerProofBatched> = Vec::new();
271 let num_layers = prod_circuit_vec[0].left_vec.len();
272 let mut claims_to_verify = (0..prod_circuit_vec.len())
273 .map(|i| prod_circuit_vec[i].evaluate())
274 .collect::<Vec<Scalar>>();
275 let mut rand = Vec::new();
276 for layer_id in (0..num_layers).rev() {
277 // prepare paralell instance that share poly_C first
278 let len = prod_circuit_vec[0].left_vec[layer_id].len()
279 + prod_circuit_vec[0].right_vec[layer_id].len();
280
281 let mut poly_C_par = DensePolynomial::new(EqPolynomial::new(rand.clone()).evals());
282 assert_eq!(poly_C_par.len(), len / 2);
283
284 let num_rounds_prod = poly_C_par.len().log_2();
285 let comb_func_prod = |poly_A_comp: &Scalar,
286 poly_B_comp: &Scalar,
287 poly_C_comp: &Scalar|
288 -> Scalar { (*poly_A_comp) * poly_B_comp * poly_C_comp };
289
290 let mut poly_A_batched_par: Vec<&mut DensePolynomial> = Vec::new();
291 let mut poly_B_batched_par: Vec<&mut DensePolynomial> = Vec::new();
292 for prod_circuit in prod_circuit_vec.iter_mut() {
293 poly_A_batched_par.push(&mut prod_circuit.left_vec[layer_id]);
294 poly_B_batched_par.push(&mut prod_circuit.right_vec[layer_id])
295 }
296 let poly_vec_par = (
297 &mut poly_A_batched_par,
298 &mut poly_B_batched_par,
299 &mut poly_C_par,
300 );
301
302 // prepare sequential instances that don't share poly_C
303 let mut poly_A_batched_seq: Vec<&mut DensePolynomial> = Vec::new();
304 let mut poly_B_batched_seq: Vec<&mut DensePolynomial> = Vec::new();
305 let mut poly_C_batched_seq: Vec<&mut DensePolynomial> = Vec::new();
306 if layer_id == 0 && !dotp_circuit_vec.is_empty() {
307 // add additional claims
308 for item in dotp_circuit_vec.iter() {
309 claims_to_verify.push(item.evaluate());
310 assert_eq!(len / 2, item.left.len());
311 assert_eq!(len / 2, item.right.len());
312 assert_eq!(len / 2, item.weight.len());
313 }
314
315 for dotp_circuit in dotp_circuit_vec.iter_mut() {
316 poly_A_batched_seq.push(&mut dotp_circuit.left);
317 poly_B_batched_seq.push(&mut dotp_circuit.right);
318 poly_C_batched_seq.push(&mut dotp_circuit.weight);
319 }
320 }
321 let poly_vec_seq = (
322 &mut poly_A_batched_seq,
323 &mut poly_B_batched_seq,
324 &mut poly_C_batched_seq,
325 );
326
327 // produce a fresh set of coeffs and a joint claim
328 let coeff_vec = transcript.challenge_vector(claims_to_verify.len());
329 let claim = (0..claims_to_verify.len())
330 .map(|i| claims_to_verify[i] * coeff_vec[i])
331 .sum();
332
333 let (proof, rand_prod, claims_prod, claims_dotp) = SumcheckInstanceProof::prove_cubic_batched(
334 &claim,
335 num_rounds_prod,
336 poly_vec_par,
337 poly_vec_seq,
338 &coeff_vec,
339 comb_func_prod,
340 transcript,
341 );
342
343 let (claims_prod_left, claims_prod_right, _claims_eq) = claims_prod;
344 for i in 0..prod_circuit_vec.len() {
345 transcript.append_scalar(&claims_prod_left[i]);
346 transcript.append_scalar(&claims_prod_right[i]);
347 }
348
349 if layer_id == 0 && !dotp_circuit_vec.is_empty() {
350 let (claims_dotp_left, claims_dotp_right, claims_dotp_weight) = claims_dotp;
351 for i in 0..dotp_circuit_vec.len() {
352 transcript.append_scalar(&claims_dotp_left[i]);
353 transcript.append_scalar(&claims_dotp_right[i]);
354 transcript.append_scalar(&claims_dotp_weight[i]);
355 }
356 claims_dotp_final = (claims_dotp_left, claims_dotp_right, claims_dotp_weight);
357 }
358
359 // produce a random challenge to condense two claims into a single claim
360 let r_layer = transcript.challenge_scalar();
361
362 claims_to_verify = (0..prod_circuit_vec.len())
363 .map(|i| claims_prod_left[i] + r_layer * (claims_prod_right[i] - claims_prod_left[i]))
364 .collect::<Vec<Scalar>>();
365
366 let mut ext = vec![r_layer];
367 ext.extend(rand_prod);
368 rand = ext;
369
370 proof_layers.push(LayerProofBatched {
371 proof,
372 claims_prod_left,
373 claims_prod_right,
374 });
375 }
376
377 (
378 ProductCircuitEvalProofBatched {
379 proof: proof_layers,
380 claims_dotp: claims_dotp_final,
381 },
382 rand,
383 )
384 }
385
386 pub fn verify(
387 &self,
388 claims_prod_vec: &[Scalar],
389 claims_dotp_vec: &[Scalar],
390 len: usize,
391 transcript: &mut PoseidonTranscript,
392 ) -> (Vec<Scalar>, Vec<Scalar>, Vec<Scalar>) {
393 let num_layers = len.log_2();
394 let mut rand: Vec<Scalar> = Vec::new();
395 //let mut num_rounds = 0;
396 assert_eq!(self.proof.len(), num_layers);
397
398 let mut claims_to_verify = claims_prod_vec.to_owned();
399 let mut claims_to_verify_dotp: Vec<Scalar> = Vec::new();
400 for (num_rounds, i) in (0..num_layers).enumerate() {
401 if i == num_layers - 1 {
402 claims_to_verify.extend(claims_dotp_vec);
403 }
404
405 // produce random coefficients, one for each instance
406 let coeff_vec = transcript.challenge_vector(claims_to_verify.len());
407
408 // produce a joint claim
409 let claim = (0..claims_to_verify.len())
410 .map(|i| claims_to_verify[i] * coeff_vec[i])
411 .sum();
412
413 let (claim_last, rand_prod) = self.proof[i].verify(claim, num_rounds, 3, transcript);
414
415 let claims_prod_left = &self.proof[i].claims_prod_left;
416 let claims_prod_right = &self.proof[i].claims_prod_right;
417 assert_eq!(claims_prod_left.len(), claims_prod_vec.len());
418 assert_eq!(claims_prod_right.len(), claims_prod_vec.len());
419
420 for i in 0..claims_prod_vec.len() {
421 transcript.append_scalar(&claims_prod_left[i]);
422 transcript.append_scalar(&claims_prod_right[i]);
423 }
424
425 assert_eq!(rand.len(), rand_prod.len());
426 let eq: Scalar = (0..rand.len())
427 .map(|i| {
428 rand[i] * rand_prod[i] + (Scalar::one() - rand[i]) * (Scalar::one() - rand_prod[i])
429 })
430 .product();
431 let mut claim_expected: Scalar = (0..claims_prod_vec.len())
432 .map(|i| coeff_vec[i] * (claims_prod_left[i] * claims_prod_right[i] * eq))
433 .sum();
434
435 // add claims from the dotp instances
436 if i == num_layers - 1 {
437 let num_prod_instances = claims_prod_vec.len();
438 let (claims_dotp_left, claims_dotp_right, claims_dotp_weight) = &self.claims_dotp;
439 for i in 0..claims_dotp_left.len() {
440 transcript.append_scalar(&claims_dotp_left[i]);
441 transcript.append_scalar(&claims_dotp_right[i]);
442 transcript.append_scalar(&claims_dotp_weight[i]);
443
444 claim_expected += coeff_vec[i + num_prod_instances]
445 * claims_dotp_left[i]
446 * claims_dotp_right[i]
447 * claims_dotp_weight[i];
448 }
449 }
450
451 assert_eq!(claim_expected, claim_last);
452
453 // produce a random challenge
454 let r_layer = transcript.challenge_scalar();
455
456 claims_to_verify = (0..claims_prod_left.len())
457 .map(|i| claims_prod_left[i] + r_layer * (claims_prod_right[i] - claims_prod_left[i]))
458 .collect();
459
460 // add claims to verify for dotp circuit
461 if i == num_layers - 1 {
462 let (claims_dotp_left, claims_dotp_right, claims_dotp_weight) = &self.claims_dotp;
463
464 for i in 0..claims_dotp_vec.len() / 2 {
465 // combine left claims
466 let claim_left = claims_dotp_left[2 * i]
467 + r_layer * (claims_dotp_left[2 * i + 1] - claims_dotp_left[2 * i]);
468
469 let claim_right = claims_dotp_right[2 * i]
470 + r_layer * (claims_dotp_right[2 * i + 1] - claims_dotp_right[2 * i]);
471
472 let claim_weight = claims_dotp_weight[2 * i]
473 + r_layer * (claims_dotp_weight[2 * i + 1] - claims_dotp_weight[2 * i]);
474 claims_to_verify_dotp.push(claim_left);
475 claims_to_verify_dotp.push(claim_right);
476 claims_to_verify_dotp.push(claim_weight);
477 }
478 }
479
480 let mut ext = vec![r_layer];
481 ext.extend(rand_prod);
482 rand = ext;
483 }
484 (claims_to_verify, claims_to_verify_dotp, rand)
485 }
486}