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    let delta = d_vec.commit(&r_delta, gens_n).compress();
340    delta.append_to_transcript(b"delta", transcript);
341
342    let dotproduct_a_d = DotProductProof::compute_dotproduct(a_vec, &d_vec);
343
344    let beta = dotproduct_a_d.commit(&r_beta, gens_1).compress();
345    beta.append_to_transcript(b"beta", transcript);
346
347    let c = transcript.challenge_scalar(b"c");
348
349    let z = (0..d_vec.len())
350      .map(|i| c * x_vec[i] + d_vec[i])
351      .collect::<Vec<Scalar>>();
352
353    let z_delta = c * blind_x + r_delta;
354    let z_beta = c * blind_y + r_beta;
355
356    (
357      DotProductProof {
358        delta,
359        beta,
360        z,
361        z_delta,
362        z_beta,
363      },
364      Cx,
365      Cy,
366    )
367  }
368
369  pub fn verify(
370    &self,
371    gens_1: &MultiCommitGens,
372    gens_n: &MultiCommitGens,
373    transcript: &mut Transcript,
374    a: &[Scalar],
375    Cx: &CompressedGroup,
376    Cy: &CompressedGroup,
377  ) -> Result<(), ProofVerifyError> {
378    assert_eq!(gens_n.n, a.len());
379    assert_eq!(gens_1.n, 1);
380
381    transcript.append_protocol_name(DotProductProof::protocol_name());
382    Cx.append_to_transcript(b"Cx", transcript);
383    Cy.append_to_transcript(b"Cy", transcript);
384    self.delta.append_to_transcript(b"delta", transcript);
385    self.beta.append_to_transcript(b"beta", transcript);
386
387    let c = transcript.challenge_scalar(b"c");
388
389    let mut result =
390      c * Cx.unpack()? + self.delta.unpack()? == self.z.commit(&self.z_delta, gens_n);
391
392    let dotproduct_z_a = DotProductProof::compute_dotproduct(&self.z, a);
393    result &= c * Cy.unpack()? + self.beta.unpack()? == dotproduct_z_a.commit(&self.z_beta, gens_1);
394
395    if result {
396      Ok(())
397    } else {
398      Err(ProofVerifyError::InternalError)
399    }
400  }
401}
402
403pub struct DotProductProofGens {
404  n: usize,
405  pub gens_n: MultiCommitGens,
406  pub gens_1: MultiCommitGens,
407}
408
409impl DotProductProofGens {
410  pub fn new(n: usize, label: &[u8]) -> Self {
411    let (gens_n, gens_1) = MultiCommitGens::new(n + 1, label).split_at(n);
412    DotProductProofGens { n, gens_n, gens_1 }
413  }
414}
415
416#[derive(Debug, Serialize, Deserialize)]
417pub struct DotProductProofLog {
418  bullet_reduction_proof: BulletReductionProof,
419  delta: CompressedGroup,
420  beta: CompressedGroup,
421  z1: Scalar,
422  z2: Scalar,
423}
424
425impl DotProductProofLog {
426  fn protocol_name() -> &'static [u8] {
427    b"dot product proof (log)"
428  }
429
430  pub fn compute_dotproduct(a: &[Scalar], b: &[Scalar]) -> Scalar {
431    assert_eq!(a.len(), b.len());
432    (0..a.len()).map(|i| a[i] * b[i]).sum()
433  }
434
435  pub fn prove(
436    gens: &DotProductProofGens,
437    transcript: &mut Transcript,
438    random_tape: &mut RandomTape,
439    x_vec: &[Scalar],
440    blind_x: &Scalar,
441    a_vec: &[Scalar],
442    y: &Scalar,
443    blind_y: &Scalar,
444  ) -> (DotProductProofLog, CompressedGroup, CompressedGroup) {
445    transcript.append_protocol_name(DotProductProofLog::protocol_name());
446
447    let n = x_vec.len();
448    assert_eq!(x_vec.len(), a_vec.len());
449    assert_eq!(gens.n, n);
450
451    // produce randomness for generating a proof
452    let d = random_tape.random_scalar(b"d");
453    let r_delta = random_tape.random_scalar(b"r_delta");
454    let r_beta = random_tape.random_scalar(b"r_delta");
455    let blinds_vec = {
456      let v1 = random_tape.random_vector(b"blinds_vec_1", 2 * n.log2() as usize);
457      let v2 = random_tape.random_vector(b"blinds_vec_2", 2 * n.log2() as usize);
458      (0..v1.len())
459        .map(|i| (v1[i], v2[i]))
460        .collect::<Vec<(Scalar, Scalar)>>()
461    };
462
463    let Cx = x_vec.commit(blind_x, &gens.gens_n).compress();
464    Cx.append_to_transcript(b"Cx", transcript);
465
466    let Cy = y.commit(blind_y, &gens.gens_1).compress();
467    Cy.append_to_transcript(b"Cy", transcript);
468
469    let blind_Gamma = blind_x + blind_y;
470    let (bullet_reduction_proof, _Gamma_hat, x_hat, a_hat, g_hat, rhat_Gamma) =
471      BulletReductionProof::prove(
472        transcript,
473        &gens.gens_1.G[0],
474        &gens.gens_n.G,
475        &gens.gens_n.h,
476        x_vec,
477        a_vec,
478        &blind_Gamma,
479        &blinds_vec,
480      );
481    let y_hat = x_hat * a_hat;
482
483    let delta = {
484      let gens_hat = MultiCommitGens {
485        n: 1,
486        G: vec![g_hat],
487        h: gens.gens_1.h,
488      };
489      d.commit(&r_delta, &gens_hat).compress()
490    };
491    delta.append_to_transcript(b"delta", transcript);
492
493    let beta = d.commit(&r_beta, &gens.gens_1).compress();
494    beta.append_to_transcript(b"beta", transcript);
495
496    let c = transcript.challenge_scalar(b"c");
497
498    let z1 = d + c * y_hat;
499    let z2 = a_hat * (c * rhat_Gamma + r_beta) + r_delta;
500
501    (
502      DotProductProofLog {
503        bullet_reduction_proof,
504        delta,
505        beta,
506        z1,
507        z2,
508      },
509      Cx,
510      Cy,
511    )
512  }
513
514  pub fn verify(
515    &self,
516    n: usize,
517    gens: &DotProductProofGens,
518    transcript: &mut Transcript,
519    a: &[Scalar],
520    Cx: &CompressedGroup,
521    Cy: &CompressedGroup,
522  ) -> Result<(), ProofVerifyError> {
523    assert_eq!(gens.n, n);
524    assert_eq!(a.len(), n);
525
526    transcript.append_protocol_name(DotProductProofLog::protocol_name());
527    Cx.append_to_transcript(b"Cx", transcript);
528    Cy.append_to_transcript(b"Cy", transcript);
529
530    let Gamma = Cx.unpack()? + Cy.unpack()?;
531
532    let (g_hat, Gamma_hat, a_hat) =
533      self
534        .bullet_reduction_proof
535        .verify(n, a, transcript, &Gamma, &gens.gens_n.G)?;
536    self.delta.append_to_transcript(b"delta", transcript);
537    self.beta.append_to_transcript(b"beta", transcript);
538
539    let c = transcript.challenge_scalar(b"c");
540
541    let c_s = &c;
542    let beta_s = self.beta.unpack()?;
543    let a_hat_s = &a_hat;
544    let delta_s = self.delta.unpack()?;
545    let z1_s = &self.z1;
546    let z2_s = &self.z2;
547
548    let lhs = ((Gamma_hat * c_s + beta_s) * a_hat_s + delta_s).compress();
549    let rhs = ((g_hat + gens.gens_1.G[0] * a_hat_s) * z1_s + gens.gens_1.h * z2_s).compress();
550
551    assert_eq!(lhs, rhs);
552
553    if lhs == rhs {
554      Ok(())
555    } else {
556      Err(ProofVerifyError::InternalError)
557    }
558  }
559}
560
561#[cfg(test)]
562mod tests {
563  use super::*;
564  use rand::rngs::OsRng;
565  #[test]
566  fn check_knowledgeproof() {
567    let mut csprng: OsRng = OsRng;
568
569    let gens_1 = MultiCommitGens::new(1, b"test-knowledgeproof");
570
571    let x = Scalar::random(&mut csprng);
572    let r = Scalar::random(&mut csprng);
573
574    let mut random_tape = RandomTape::new(b"proof");
575    let mut prover_transcript = Transcript::new(b"example");
576    let (proof, committed_value) =
577      KnowledgeProof::prove(&gens_1, &mut prover_transcript, &mut random_tape, &x, &r);
578
579    let mut verifier_transcript = Transcript::new(b"example");
580    assert!(proof
581      .verify(&gens_1, &mut verifier_transcript, &committed_value)
582      .is_ok());
583  }
584
585  #[test]
586  fn check_equalityproof() {
587    let mut csprng: OsRng = OsRng;
588
589    let gens_1 = MultiCommitGens::new(1, b"test-equalityproof");
590    let v1 = Scalar::random(&mut csprng);
591    let v2 = v1;
592    let s1 = Scalar::random(&mut csprng);
593    let s2 = Scalar::random(&mut csprng);
594
595    let mut random_tape = RandomTape::new(b"proof");
596    let mut prover_transcript = Transcript::new(b"example");
597    let (proof, C1, C2) = EqualityProof::prove(
598      &gens_1,
599      &mut prover_transcript,
600      &mut random_tape,
601      &v1,
602      &s1,
603      &v2,
604      &s2,
605    );
606
607    let mut verifier_transcript = Transcript::new(b"example");
608    assert!(proof
609      .verify(&gens_1, &mut verifier_transcript, &C1, &C2)
610      .is_ok());
611  }
612
613  #[test]
614  fn check_productproof() {
615    let mut csprng: OsRng = OsRng;
616
617    let gens_1 = MultiCommitGens::new(1, b"test-productproof");
618    let x = Scalar::random(&mut csprng);
619    let rX = Scalar::random(&mut csprng);
620    let y = Scalar::random(&mut csprng);
621    let rY = Scalar::random(&mut csprng);
622    let z = x * y;
623    let rZ = Scalar::random(&mut csprng);
624
625    let mut random_tape = RandomTape::new(b"proof");
626    let mut prover_transcript = Transcript::new(b"example");
627    let (proof, X, Y, Z) = ProductProof::prove(
628      &gens_1,
629      &mut prover_transcript,
630      &mut random_tape,
631      &x,
632      &rX,
633      &y,
634      &rY,
635      &z,
636      &rZ,
637    );
638
639    let mut verifier_transcript = Transcript::new(b"example");
640    assert!(proof
641      .verify(&gens_1, &mut verifier_transcript, &X, &Y, &Z)
642      .is_ok());
643  }
644
645  #[test]
646  fn check_dotproductproof() {
647    let mut csprng: OsRng = OsRng;
648
649    let n = 1024;
650
651    let gens_1 = MultiCommitGens::new(1, b"test-two");
652    let gens_1024 = MultiCommitGens::new(n, b"test-1024");
653
654    let mut x: Vec<Scalar> = Vec::new();
655    let mut a: Vec<Scalar> = Vec::new();
656    for _ in 0..n {
657      x.push(Scalar::random(&mut csprng));
658      a.push(Scalar::random(&mut csprng));
659    }
660    let y = DotProductProofLog::compute_dotproduct(&x, &a);
661    let r_x = Scalar::random(&mut csprng);
662    let r_y = Scalar::random(&mut csprng);
663
664    let mut random_tape = RandomTape::new(b"proof");
665    let mut prover_transcript = Transcript::new(b"example");
666    let (proof, Cx, Cy) = DotProductProof::prove(
667      &gens_1,
668      &gens_1024,
669      &mut prover_transcript,
670      &mut random_tape,
671      &x,
672      &r_x,
673      &a,
674      &y,
675      &r_y,
676    );
677
678    let mut verifier_transcript = Transcript::new(b"example");
679    assert!(proof
680      .verify(&gens_1, &gens_1024, &mut verifier_transcript, &a, &Cx, &Cy)
681      .is_ok());
682  }
683
684  #[test]
685  fn check_dotproductproof_log() {
686    let mut csprng: OsRng = OsRng;
687
688    let n = 1024;
689
690    let gens = DotProductProofGens::new(n, b"test-1024");
691
692    let x: Vec<Scalar> = (0..n).map(|_i| Scalar::random(&mut csprng)).collect();
693    let a: Vec<Scalar> = (0..n).map(|_i| Scalar::random(&mut csprng)).collect();
694    let y = DotProductProof::compute_dotproduct(&x, &a);
695
696    let r_x = Scalar::random(&mut csprng);
697    let r_y = Scalar::random(&mut csprng);
698
699    let mut random_tape = RandomTape::new(b"proof");
700    let mut prover_transcript = Transcript::new(b"example");
701    let (proof, Cx, Cy) = DotProductProofLog::prove(
702      &gens,
703      &mut prover_transcript,
704      &mut random_tape,
705      &x,
706      &r_x,
707      &a,
708      &y,
709      &r_y,
710    );
711
712    let mut verifier_transcript = Transcript::new(b"example");
713    assert!(proof
714      .verify(n, &gens, &mut verifier_transcript, &a, &Cx, &Cy)
715      .is_ok());
716  }
717}