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