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