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