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