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