testudo/src/nizk/mod.rs
src/nizk/mod.rsRaw
1#![allow(clippy::too_many_arguments)]
2use super::commitments::{Commitments, MultiCommitGens};
3use super::errors::ProofVerifyError;
4use super::group::CompressedGroup;
5use super::math::Math;
6use super::random::RandomTape;
7use super::scalar::Scalar;
8use super::transcript::{AppendToTranscript, ProofTranscript};
9use merlin::Transcript;
10use serde::{Deserialize, Serialize};
11
12mod bullet;
13use bullet::BulletReductionProof;
14
15#[derive(Serialize, Deserialize, Debug)]
16pub struct KnowledgeProof {
17 alpha: CompressedGroup,
18 z1: Scalar,
19 z2: Scalar,
20}
21
22impl KnowledgeProof {
23 fn protocol_name() -> &'static [u8] {
24 b"knowledge proof"
25 }
26
27 pub fn prove(
28 gens_n: &MultiCommitGens,
29 transcript: &mut Transcript,
30 random_tape: &mut RandomTape,
31 x: &Scalar,
32 r: &Scalar,
33 ) -> (KnowledgeProof, CompressedGroup) {
34 transcript.append_protocol_name(KnowledgeProof::protocol_name());
35
36 // produce two random Scalars
37 let t1 = random_tape.random_scalar(b"t1");
38 let t2 = random_tape.random_scalar(b"t2");
39
40 let C = x.commit(&r, gens_n).compress();
41 C.append_to_transcript(b"C", transcript);
42
43 let alpha = t1.commit(&t2, gens_n).compress();
44 alpha.append_to_transcript(b"alpha", transcript);
45
46 let c = transcript.challenge_scalar(b"c");
47
48 let z1 = x * c + t1;
49 let z2 = r * c + t2;
50
51 (KnowledgeProof { alpha, z1, z2 }, C)
52 }
53
54 pub fn verify(
55 &self,
56 gens_n: &MultiCommitGens,
57 transcript: &mut Transcript,
58 C: &CompressedGroup,
59 ) -> Result<(), ProofVerifyError> {
60 transcript.append_protocol_name(KnowledgeProof::protocol_name());
61 C.append_to_transcript(b"C", transcript);
62 self.alpha.append_to_transcript(b"alpha", transcript);
63
64 let c = transcript.challenge_scalar(b"c");
65
66 let lhs = self.z1.commit(&self.z2, gens_n).compress();
67 let rhs = (c * C.decompress().expect("Could not decompress C")
68 + self
69 .alpha
70 .decompress()
71 .expect("Could not decompress self.alpha"))
72 .compress();
73
74 if lhs == rhs {
75 Ok(())
76 } else {
77 Err(ProofVerifyError)
78 }
79 }
80}
81
82#[derive(Serialize, Deserialize, Debug)]
83pub struct EqualityProof {
84 alpha: CompressedGroup,
85 z: Scalar,
86}
87
88impl EqualityProof {
89 fn protocol_name() -> &'static [u8] {
90 b"equality proof"
91 }
92
93 pub fn prove(
94 gens_n: &MultiCommitGens,
95 transcript: &mut Transcript,
96 random_tape: &mut RandomTape,
97 v1: &Scalar,
98 s1: &Scalar,
99 v2: &Scalar,
100 s2: &Scalar,
101 ) -> (EqualityProof, CompressedGroup, CompressedGroup) {
102 transcript.append_protocol_name(EqualityProof::protocol_name());
103
104 // produce a random Scalar
105 let r = random_tape.random_scalar(b"r");
106
107 let C1 = v1.commit(&s1, gens_n).compress();
108 C1.append_to_transcript(b"C1", transcript);
109
110 let C2 = v2.commit(&s2, gens_n).compress();
111 C2.append_to_transcript(b"C2", transcript);
112
113 let alpha = (r * gens_n.h).compress();
114 alpha.append_to_transcript(b"alpha", transcript);
115
116 let c = transcript.challenge_scalar(b"c");
117
118 let z = c * (s1 - s2) + r;
119
120 (EqualityProof { alpha, z }, C1, C2)
121 }
122
123 pub fn verify(
124 &self,
125 gens_n: &MultiCommitGens,
126 transcript: &mut Transcript,
127 C1: &CompressedGroup,
128 C2: &CompressedGroup,
129 ) -> Result<(), ProofVerifyError> {
130 transcript.append_protocol_name(EqualityProof::protocol_name());
131 C1.append_to_transcript(b"C1", transcript);
132 C2.append_to_transcript(b"C2", transcript);
133 self.alpha.append_to_transcript(b"alpha", transcript);
134
135 let c = transcript.challenge_scalar(b"c");
136 let rhs = {
137 let C = C1.decompress().unwrap() - C2.decompress().unwrap();
138 (c * C + self.alpha.decompress().unwrap()).compress()
139 };
140
141 let lhs = (self.z * gens_n.h).compress();
142
143 if lhs == rhs {
144 Ok(())
145 } else {
146 Err(ProofVerifyError)
147 }
148 }
149}
150
151#[derive(Serialize, Deserialize, Debug)]
152pub struct ProductProof {
153 alpha: CompressedGroup,
154 beta: CompressedGroup,
155 delta: CompressedGroup,
156 z: [Scalar; 5],
157}
158
159impl ProductProof {
160 fn protocol_name() -> &'static [u8] {
161 b"product proof"
162 }
163
164 pub fn prove(
165 gens_n: &MultiCommitGens,
166 transcript: &mut Transcript,
167 random_tape: &mut RandomTape,
168 x: &Scalar,
169 rX: &Scalar,
170 y: &Scalar,
171 rY: &Scalar,
172 z: &Scalar,
173 rZ: &Scalar,
174 ) -> (
175 ProductProof,
176 CompressedGroup,
177 CompressedGroup,
178 CompressedGroup,
179 ) {
180 transcript.append_protocol_name(ProductProof::protocol_name());
181
182 // produce five random Scalar
183 let b1 = random_tape.random_scalar(b"b1");
184 let b2 = random_tape.random_scalar(b"b2");
185 let b3 = random_tape.random_scalar(b"b3");
186 let b4 = random_tape.random_scalar(b"b4");
187 let b5 = random_tape.random_scalar(b"b5");
188
189 let X = x.commit(&rX, gens_n).compress();
190 X.append_to_transcript(b"X", transcript);
191
192 let Y = y.commit(&rY, gens_n).compress();
193 Y.append_to_transcript(b"Y", transcript);
194
195 let Z = z.commit(&rZ, gens_n).compress();
196 Z.append_to_transcript(b"Z", transcript);
197
198 let alpha = b1.commit(&b2, gens_n).compress();
199 alpha.append_to_transcript(b"alpha", transcript);
200
201 let beta = b3.commit(&b4, gens_n).compress();
202 beta.append_to_transcript(b"beta", transcript);
203
204 let delta = {
205 let gens_X = &MultiCommitGens {
206 n: 1,
207 G: vec![X.decompress().unwrap()],
208 h: gens_n.h,
209 };
210 b3.commit(&b5, gens_X).compress()
211 };
212 delta.append_to_transcript(b"delta", transcript);
213
214 let c = transcript.challenge_scalar(b"c");
215
216 let z1 = b1 + c * x;
217 let z2 = b2 + c * rX;
218 let z3 = b3 + c * y;
219 let z4 = b4 + c * rY;
220 let z5 = b5 + c * (rZ - rX * y);
221 let z = [z1, z2, z3, z4, z5];
222
223 (
224 ProductProof {
225 alpha,
226 beta,
227 delta,
228 z,
229 },
230 X,
231 Y,
232 Z,
233 )
234 }
235
236 fn check_equality(
237 P: &CompressedGroup,
238 X: &CompressedGroup,
239 c: &Scalar,
240 gens_n: &MultiCommitGens,
241 z1: &Scalar,
242 z2: &Scalar,
243 ) -> bool {
244 let lhs = (P.decompress().unwrap() + c * X.decompress().unwrap()).compress();
245 let rhs = z1.commit(&z2, gens_n).compress();
246
247 lhs == rhs
248 }
249
250 pub fn verify(
251 &self,
252 gens_n: &MultiCommitGens,
253 transcript: &mut Transcript,
254 X: &CompressedGroup,
255 Y: &CompressedGroup,
256 Z: &CompressedGroup,
257 ) -> Result<(), ProofVerifyError> {
258 transcript.append_protocol_name(ProductProof::protocol_name());
259
260 X.append_to_transcript(b"X", transcript);
261 Y.append_to_transcript(b"Y", transcript);
262 Z.append_to_transcript(b"Z", transcript);
263 self.alpha.append_to_transcript(b"alpha", transcript);
264 self.beta.append_to_transcript(b"beta", transcript);
265 self.delta.append_to_transcript(b"delta", transcript);
266
267 let z1 = self.z[0];
268 let z2 = self.z[1];
269 let z3 = self.z[2];
270 let z4 = self.z[3];
271 let z5 = self.z[4];
272
273 let c = transcript.challenge_scalar(b"c");
274
275 if ProductProof::check_equality(&self.alpha, &X, &c, &gens_n, &z1, &z2)
276 && ProductProof::check_equality(&self.beta, &Y, &c, &gens_n, &z3, &z4)
277 && ProductProof::check_equality(
278 &self.delta,
279 &Z,
280 &c,
281 &MultiCommitGens {
282 n: 1,
283 G: vec![X.decompress().unwrap()],
284 h: gens_n.h,
285 },
286 &z3,
287 &z5,
288 )
289 {
290 Ok(())
291 } else {
292 Err(ProofVerifyError)
293 }
294 }
295}
296
297#[derive(Debug, Serialize, Deserialize)]
298pub struct DotProductProof {
299 delta: CompressedGroup,
300 beta: CompressedGroup,
301 z: Vec<Scalar>,
302 z_delta: Scalar,
303 z_beta: Scalar,
304}
305
306impl DotProductProof {
307 fn protocol_name() -> &'static [u8] {
308 b"dot product proof"
309 }
310
311 pub fn compute_dotproduct(a: &[Scalar], b: &[Scalar]) -> Scalar {
312 assert_eq!(a.len(), b.len());
313 (0..a.len()).map(|i| a[i] * b[i]).sum()
314 }
315
316 pub fn prove(
317 gens_1: &MultiCommitGens,
318 gens_n: &MultiCommitGens,
319 transcript: &mut Transcript,
320 random_tape: &mut RandomTape,
321 x_vec: &[Scalar],
322 blind_x: &Scalar,
323 a_vec: &[Scalar],
324 y: &Scalar,
325 blind_y: &Scalar,
326 ) -> (DotProductProof, CompressedGroup, CompressedGroup) {
327 transcript.append_protocol_name(DotProductProof::protocol_name());
328
329 let n = x_vec.len();
330 assert_eq!(x_vec.len(), a_vec.len());
331 assert_eq!(gens_n.n, a_vec.len());
332 assert_eq!(gens_1.n, 1);
333
334 // produce randomness for the proofs
335 let d_vec = random_tape.random_vector(b"d_vec", n);
336 let r_delta = random_tape.random_scalar(b"r_delta");
337 let r_beta = random_tape.random_scalar(b"r_beta");
338
339 let Cx = x_vec.commit(&blind_x, gens_n).compress();
340 Cx.append_to_transcript(b"Cx", transcript);
341
342 let Cy = y.commit(&blind_y, gens_1).compress();
343 Cy.append_to_transcript(b"Cy", transcript);
344
345 let delta = d_vec.commit(&r_delta, gens_n).compress();
346 delta.append_to_transcript(b"delta", transcript);
347
348 let dotproduct_a_d = DotProductProof::compute_dotproduct(&a_vec, &d_vec);
349
350 let beta = dotproduct_a_d.commit(&r_beta, gens_1).compress();
351 beta.append_to_transcript(b"beta", transcript);
352
353 let c = transcript.challenge_scalar(b"c");
354
355 let z = (0..d_vec.len())
356 .map(|i| c * x_vec[i] + d_vec[i])
357 .collect::<Vec<Scalar>>();
358
359 let z_delta = c * blind_x + r_delta;
360 let z_beta = c * blind_y + r_beta;
361
362 (
363 DotProductProof {
364 delta,
365 beta,
366 z,
367 z_delta,
368 z_beta,
369 },
370 Cx,
371 Cy,
372 )
373 }
374
375 pub fn verify(
376 &self,
377 gens_1: &MultiCommitGens,
378 gens_n: &MultiCommitGens,
379 transcript: &mut Transcript,
380 a: &[Scalar],
381 Cx: &CompressedGroup,
382 Cy: &CompressedGroup,
383 ) -> Result<(), ProofVerifyError> {
384 assert_eq!(gens_n.n, a.len());
385 assert_eq!(gens_1.n, 1);
386
387 transcript.append_protocol_name(DotProductProof::protocol_name());
388 Cx.append_to_transcript(b"Cx", transcript);
389 Cy.append_to_transcript(b"Cy", transcript);
390 self.delta.append_to_transcript(b"delta", transcript);
391 self.beta.append_to_transcript(b"beta", transcript);
392
393 let c = transcript.challenge_scalar(b"c");
394
395 let mut result = c * Cx.decompress().unwrap() + self.delta.decompress().unwrap()
396 == self.z.commit(&self.z_delta, gens_n);
397
398 let dotproduct_z_a = DotProductProof::compute_dotproduct(&self.z, &a);
399 result &= c * Cy.decompress().unwrap() + self.beta.decompress().unwrap()
400 == dotproduct_z_a.commit(&self.z_beta, gens_1);
401
402 if result {
403 Ok(())
404 } else {
405 Err(ProofVerifyError)
406 }
407 }
408}
409
410pub struct DotProductProofGens {
411 n: usize,
412 pub gens_n: MultiCommitGens,
413 pub gens_1: MultiCommitGens,
414}
415
416impl DotProductProofGens {
417 pub fn new(n: usize, label: &[u8]) -> Self {
418 let (gens_n, gens_1) = MultiCommitGens::new(n + 1, label).split_at(n);
419 DotProductProofGens { n, gens_n, gens_1 }
420 }
421}
422
423#[derive(Debug, Serialize, Deserialize)]
424pub struct DotProductProofLog {
425 bullet_reduction_proof: BulletReductionProof,
426 delta: CompressedGroup,
427 beta: CompressedGroup,
428 z1: Scalar,
429 z2: Scalar,
430}
431
432impl DotProductProofLog {
433 fn protocol_name() -> &'static [u8] {
434 b"dot product proof (log)"
435 }
436
437 pub fn compute_dotproduct(a: &[Scalar], b: &[Scalar]) -> Scalar {
438 assert_eq!(a.len(), b.len());
439 (0..a.len()).map(|i| a[i] * b[i]).sum()
440 }
441
442 pub fn prove(
443 gens: &DotProductProofGens,
444 transcript: &mut Transcript,
445 random_tape: &mut RandomTape,
446 x_vec: &[Scalar],
447 blind_x: &Scalar,
448 a_vec: &[Scalar],
449 y: &Scalar,
450 blind_y: &Scalar,
451 ) -> (DotProductProofLog, CompressedGroup, CompressedGroup) {
452 transcript.append_protocol_name(DotProductProofLog::protocol_name());
453
454 let n = x_vec.len();
455 assert_eq!(x_vec.len(), a_vec.len());
456 assert_eq!(gens.n, n);
457
458 // produce randomness for generating a proof
459 let d = random_tape.random_scalar(b"d");
460 let r_delta = random_tape.random_scalar(b"r_delta");
461 let r_beta = random_tape.random_scalar(b"r_delta");
462 let blinds_vec = {
463 let v1 = random_tape.random_vector(b"blinds_vec_1", 2 * n.log2());
464 let v2 = random_tape.random_vector(b"blinds_vec_2", 2 * n.log2());
465 (0..v1.len())
466 .map(|i| (v1[i], v2[i]))
467 .collect::<Vec<(Scalar, Scalar)>>()
468 };
469
470 let Cx = x_vec.commit(&blind_x, &gens.gens_n).compress();
471 Cx.append_to_transcript(b"Cx", transcript);
472
473 let Cy = y.commit(&blind_y, &gens.gens_1).compress();
474 Cy.append_to_transcript(b"Cy", transcript);
475
476 let blind_Gamma = blind_x + blind_y;
477 let (bullet_reduction_proof, _Gamma_hat, x_hat, a_hat, g_hat, rhat_Gamma) =
478 BulletReductionProof::prove(
479 transcript,
480 &gens.gens_1.G[0],
481 &gens.gens_n.G,
482 &gens.gens_n.h,
483 x_vec,
484 a_vec,
485 &blind_Gamma,
486 &blinds_vec,
487 );
488 let y_hat = x_hat * a_hat;
489
490 let delta = {
491 let gens_hat = MultiCommitGens {
492 n: 1,
493 G: vec![g_hat],
494 h: gens.gens_1.h,
495 };
496 d.commit(&r_delta, &gens_hat).compress()
497 };
498 delta.append_to_transcript(b"delta", transcript);
499
500 let beta = d.commit(&r_beta, &gens.gens_1).compress();
501 beta.append_to_transcript(b"beta", transcript);
502
503 let c = transcript.challenge_scalar(b"c");
504
505 let z1 = d + c * y_hat;
506 let z2 = a_hat * (c * rhat_Gamma + r_beta) + r_delta;
507
508 (
509 DotProductProofLog {
510 bullet_reduction_proof,
511 delta,
512 beta,
513 z1,
514 z2,
515 },
516 Cx,
517 Cy,
518 )
519 }
520
521 pub fn verify(
522 &self,
523 n: usize,
524 gens: &DotProductProofGens,
525 transcript: &mut Transcript,
526 a: &[Scalar],
527 Cx: &CompressedGroup,
528 Cy: &CompressedGroup,
529 ) -> Result<(), ProofVerifyError> {
530 assert_eq!(gens.n, n);
531 assert_eq!(a.len(), n);
532
533 transcript.append_protocol_name(DotProductProofLog::protocol_name());
534 Cx.append_to_transcript(b"Cx", transcript);
535 Cy.append_to_transcript(b"Cy", transcript);
536
537 let Gamma = Cx.decompress().unwrap() + Cy.decompress().unwrap();
538
539 let (g_hat, Gamma_hat, a_hat) = self
540 .bullet_reduction_proof
541 .verify(n, a, transcript, &Gamma, &gens.gens_n.G)
542 .unwrap();
543
544 self.delta.append_to_transcript(b"delta", transcript);
545 self.beta.append_to_transcript(b"beta", transcript);
546
547 let c = transcript.challenge_scalar(b"c");
548
549 let c_s = &c;
550 let beta_s = self.beta.decompress().unwrap();
551 let a_hat_s = &a_hat;
552 let delta_s = self.delta.decompress().unwrap();
553 let z1_s = &self.z1;
554 let z2_s = &self.z2;
555
556 let lhs = ((Gamma_hat * c_s + beta_s) * a_hat_s + delta_s).compress();
557 let rhs = ((g_hat + gens.gens_1.G[0] * a_hat_s) * z1_s + gens.gens_1.h * z2_s).compress();
558
559 assert_eq!(lhs, rhs);
560
561 if lhs == rhs {
562 Ok(())
563 } else {
564 Err(ProofVerifyError)
565 }
566 }
567}
568
569#[cfg(test)]
570mod tests {
571 use super::*;
572 use rand::rngs::OsRng;
573 #[test]
574 fn check_knowledgeproof() {
575 let mut csprng: OsRng = OsRng;
576
577 let gens_1 = MultiCommitGens::new(1, b"test-knowledgeproof");
578
579 let x = Scalar::random(&mut csprng);
580 let r = Scalar::random(&mut csprng);
581
582 let mut random_tape = RandomTape::new(b"proof");
583 let mut prover_transcript = Transcript::new(b"example");
584 let (proof, committed_value) =
585 KnowledgeProof::prove(&gens_1, &mut prover_transcript, &mut random_tape, &x, &r);
586
587 let mut verifier_transcript = Transcript::new(b"example");
588 assert!(proof
589 .verify(&gens_1, &mut verifier_transcript, &committed_value)
590 .is_ok());
591 }
592
593 #[test]
594 fn check_equalityproof() {
595 let mut csprng: OsRng = OsRng;
596
597 let gens_1 = MultiCommitGens::new(1, b"test-equalityproof");
598 let v1 = Scalar::random(&mut csprng);
599 let v2 = v1;
600 let s1 = Scalar::random(&mut csprng);
601 let s2 = Scalar::random(&mut csprng);
602
603 let mut random_tape = RandomTape::new(b"proof");
604 let mut prover_transcript = Transcript::new(b"example");
605 let (proof, C1, C2) = EqualityProof::prove(
606 &gens_1,
607 &mut prover_transcript,
608 &mut random_tape,
609 &v1,
610 &s1,
611 &v2,
612 &s2,
613 );
614
615 let mut verifier_transcript = Transcript::new(b"example");
616 assert!(proof
617 .verify(&gens_1, &mut verifier_transcript, &C1, &C2)
618 .is_ok());
619 }
620
621 #[test]
622 fn check_productproof() {
623 let mut csprng: OsRng = OsRng;
624
625 let gens_1 = MultiCommitGens::new(1, b"test-productproof");
626 let x = Scalar::random(&mut csprng);
627 let rX = Scalar::random(&mut csprng);
628 let y = Scalar::random(&mut csprng);
629 let rY = Scalar::random(&mut csprng);
630 let z = x * y;
631 let rZ = Scalar::random(&mut csprng);
632
633 let mut random_tape = RandomTape::new(b"proof");
634 let mut prover_transcript = Transcript::new(b"example");
635 let (proof, X, Y, Z) = ProductProof::prove(
636 &gens_1,
637 &mut prover_transcript,
638 &mut random_tape,
639 &x,
640 &rX,
641 &y,
642 &rY,
643 &z,
644 &rZ,
645 );
646
647 let mut verifier_transcript = Transcript::new(b"example");
648 assert!(proof
649 .verify(&gens_1, &mut verifier_transcript, &X, &Y, &Z)
650 .is_ok());
651 }
652
653 #[test]
654 fn check_dotproductproof() {
655 let mut csprng: OsRng = OsRng;
656
657 let n = 1024;
658
659 let gens_1 = MultiCommitGens::new(1, b"test-two");
660 let gens_1024 = MultiCommitGens::new(n, b"test-1024");
661
662 let mut x: Vec<Scalar> = Vec::new();
663 let mut a: Vec<Scalar> = Vec::new();
664 for _ in 0..n {
665 x.push(Scalar::random(&mut csprng));
666 a.push(Scalar::random(&mut csprng));
667 }
668 let y = DotProductProofLog::compute_dotproduct(&x, &a);
669 let r_x = Scalar::random(&mut csprng);
670 let r_y = Scalar::random(&mut csprng);
671
672 let mut random_tape = RandomTape::new(b"proof");
673 let mut prover_transcript = Transcript::new(b"example");
674 let (proof, Cx, Cy) = DotProductProof::prove(
675 &gens_1,
676 &gens_1024,
677 &mut prover_transcript,
678 &mut random_tape,
679 &x,
680 &r_x,
681 &a,
682 &y,
683 &r_y,
684 );
685
686 let mut verifier_transcript = Transcript::new(b"example");
687 assert!(proof
688 .verify(&gens_1, &gens_1024, &mut verifier_transcript, &a, &Cx, &Cy)
689 .is_ok());
690 }
691
692 #[test]
693 fn check_dotproductproof_log() {
694 let mut csprng: OsRng = OsRng;
695
696 let n = 1024;
697
698 let gens = DotProductProofGens::new(n, b"test-1024");
699
700 let x: Vec<Scalar> = (0..n).map(|_i| Scalar::random(&mut csprng)).collect();
701 let a: Vec<Scalar> = (0..n).map(|_i| Scalar::random(&mut csprng)).collect();
702 let y = DotProductProof::compute_dotproduct(&x, &a);
703
704 let r_x = Scalar::random(&mut csprng);
705 let r_y = Scalar::random(&mut csprng);
706
707 let mut random_tape = RandomTape::new(b"proof");
708 let mut prover_transcript = Transcript::new(b"example");
709 let (proof, Cx, Cy) = DotProductProofLog::prove(
710 &gens,
711 &mut prover_transcript,
712 &mut random_tape,
713 &x,
714 &r_x,
715 &a,
716 &y,
717 &r_y,
718 );
719
720 let mut verifier_transcript = Transcript::new(b"example");
721 assert!(proof
722 .verify(n, &gens, &mut verifier_transcript, &a, &Cx, &Cy)
723 .is_ok());
724 }
725}