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