testudo/src/nizk/mod.rs
src/nizk/mod.rsRaw
1#![allow(clippy::too_many_arguments)]
2use super::commitments::{MultiCommitGens, PedersenCommit};
3use super::errors::ProofVerifyError;
4use crate::ark_std::UniformRand;
5use crate::math::Math;
6use crate::poseidon_transcript::PoseidonTranscript;
7use crate::transcript::Transcript;
8use ark_crypto_primitives::sponge::Absorb;
9use ark_ec::CurveGroup;
10
11use ark_serialize::*;
12use std::ops::Mul;
13
14mod bullet;
15use bullet::BulletReductionProof;
16
17#[derive(Clone)]
18pub struct DotProductProofGens<G: CurveGroup> {
19 n: usize,
20 pub gens_n: MultiCommitGens<G>,
21 pub gens_1: MultiCommitGens<G>,
22}
23
24impl<G: CurveGroup> DotProductProofGens<G> {
25 pub fn new(n: usize, label: &[u8]) -> Self {
26 let (gens_n, gens_1) = MultiCommitGens::<G>::new(n + 1, label).split_at(n);
27 DotProductProofGens { n, gens_n, gens_1 }
28 }
29}
30
31#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
32pub struct DotProductProofLog<G: CurveGroup> {
33 bullet_reduction_proof: BulletReductionProof<G>,
34 delta: G,
35 beta: G,
36 z1: G::ScalarField,
37 z2: G::ScalarField,
38}
39
40impl<G> DotProductProofLog<G>
41where
42 G: CurveGroup,
43 G::ScalarField: Absorb,
44{
45 pub fn prove(
46 gens: &DotProductProofGens<G>,
47 transcript: &mut PoseidonTranscript<G::ScalarField>,
48 x_vec: &[G::ScalarField],
49 blind_x: &G::ScalarField,
50 a_vec: &[G::ScalarField],
51 y: &G::ScalarField,
52 blind_y: &G::ScalarField,
53 ) -> (Self, G, G) {
54 // transcript.append_protocol_name(DotProductProofLog::protocol_name());
55
56 let n = x_vec.len();
57 assert_eq!(x_vec.len(), a_vec.len());
58 assert_eq!(gens.n, n);
59
60 // produce randomness for generating a proof
61 let d = G::ScalarField::rand(&mut rand::thread_rng());
62 let r_delta = G::ScalarField::rand(&mut rand::thread_rng()).into();
63 let r_beta = G::ScalarField::rand(&mut rand::thread_rng()).into();
64 let blinds_vec = {
65 (0..2 * n.log_2())
66 .map(|_| {
67 (
68 G::ScalarField::rand(&mut rand::thread_rng()).into(),
69 G::ScalarField::rand(&mut rand::thread_rng()).into(),
70 )
71 })
72 .collect::<Vec<(G::ScalarField, G::ScalarField)>>()
73 };
74
75 let Cx = PedersenCommit::commit_slice(x_vec, blind_x, &gens.gens_n);
76 transcript.append_point(b"", &Cx);
77
78 let Cy = PedersenCommit::commit_scalar(y, blind_y, &gens.gens_1);
79 transcript.append_point(b"", &Cy);
80 transcript.append_scalar_vector(b"", &a_vec);
81
82 let blind_Gamma = (*blind_x) + blind_y;
83 let (bullet_reduction_proof, _Gamma_hat, x_hat, a_hat, g_hat, rhat_Gamma) =
84 BulletReductionProof::<G>::prove(
85 transcript,
86 &gens.gens_1.G[0],
87 &gens.gens_n.G,
88 &gens.gens_n.h,
89 x_vec,
90 a_vec,
91 &blind_Gamma,
92 &blinds_vec,
93 );
94 let y_hat = x_hat * a_hat;
95
96 let delta = {
97 let gens_hat = MultiCommitGens {
98 n: 1,
99 G: vec![g_hat.into_affine()],
100 h: gens.gens_1.h,
101 };
102 PedersenCommit::commit_scalar(&d, &r_delta, &gens_hat)
103 };
104 transcript.append_point(b"", &delta);
105
106 let beta = PedersenCommit::commit_scalar(&d, &r_beta, &gens.gens_1);
107 transcript.append_point(b"", &beta);
108
109 let c: G::ScalarField = transcript.challenge_scalar(b"");
110
111 let z1 = d + c * y_hat;
112 let z2 = a_hat * (c * rhat_Gamma + r_beta) + r_delta;
113
114 (
115 Self {
116 bullet_reduction_proof,
117 delta,
118 beta,
119 z1,
120 z2,
121 },
122 Cx,
123 Cy,
124 )
125 }
126
127 pub fn verify(
128 &self,
129 n: usize,
130 gens: &DotProductProofGens<G>,
131 transcript: &mut PoseidonTranscript<G::ScalarField>,
132 a: &[G::ScalarField],
133 Cx: &G,
134 Cy: &G,
135 ) -> Result<(), ProofVerifyError> {
136 assert_eq!(gens.n, n);
137 assert_eq!(a.len(), n);
138
139 // transcript.append_protocol_name(DotProductProofLog::protocol_name());
140 // Cx.write_to_transcript( transcript);
141 // Cy.write_to_transcript( transcript);
142 // a.write_to_transcript( transcript);
143
144 transcript.append_point(b"", Cx);
145 transcript.append_point(b"", Cy);
146 transcript.append_scalar_vector(b"", &a);
147
148 let Gamma = Cx.add(Cy);
149
150 let (g_hat, Gamma_hat, a_hat) =
151 self
152 .bullet_reduction_proof
153 .verify(n, a, transcript, &Gamma, &gens.gens_n.G)?;
154 // self.delta.write_to_transcript( transcript);
155 // self.beta.write_to_transcript( transcript);
156
157 transcript.append_point(b"", &self.delta);
158 transcript.append_point(b"", &self.beta);
159
160 let c = transcript.challenge_scalar(b"");
161
162 let c_s = &c;
163 let beta_s = self.beta;
164 let a_hat_s = &a_hat;
165 let delta_s = self.delta;
166 let z1_s = &self.z1;
167 let z2_s = &self.z2;
168
169 let lhs = (Gamma_hat.mul(c_s) + beta_s).mul(a_hat_s) + delta_s;
170 let rhs = (g_hat + gens.gens_1.G[0].mul(a_hat_s)).mul(z1_s) + gens.gens_1.h.mul(z2_s);
171
172 assert_eq!(lhs, rhs);
173
174 if lhs == rhs {
175 Ok(())
176 } else {
177 Err(ProofVerifyError::InternalError)
178 }
179 }
180}
181
182#[cfg(test)]
183mod tests {
184
185 use crate::parameters::poseidon_params;
186
187 use super::*;
188 use ark_std::UniformRand;
189 type F = ark_bls12_377::Fr;
190 type G = ark_bls12_377::G1Projective;
191
192 #[test]
193 fn check_dotproductproof_log() {
194 let mut rng = ark_std::rand::thread_rng();
195
196 let n = 1024;
197
198 let gens = DotProductProofGens::<G>::new(n, b"test-1024");
199
200 let x: Vec<F> = (0..n).map(|_i| F::rand(&mut rng)).collect();
201 let a: Vec<F> = (0..n).map(|_i| F::rand(&mut rng)).collect();
202 let y = crate::dot_product(&x, &a);
203
204 let r_x = F::rand(&mut rng);
205 let r_y = F::rand(&mut rng);
206
207 let params = poseidon_params();
208 let mut prover_transcript = PoseidonTranscript::new(¶ms);
209 let (proof, Cx, Cy) =
210 DotProductProofLog::<G>::prove(&gens, &mut prover_transcript, &x, &r_x, &a, &y, &r_y);
211
212 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
213 assert!(proof
214 .verify(n, &gens, &mut verifier_transcript, &a, &Cx, &Cy)
215 .is_ok());
216 }
217}