testudo/src/nizk/bullet.rs
src/nizk/bullet.rsRaw
1//! This module is an adaptation of code from the bulletproofs crate.
2//! See NOTICE.md for more details
3#![allow(non_snake_case)]
4#![allow(clippy::type_complexity)]
5#![allow(clippy::too_many_arguments)]
6use super::super::errors::ProofVerifyError;
7use crate::math::Math;
8use crate::poseidon_transcript::PoseidonTranscript;
9use crate::transcript::Transcript;
10use ark_ec::AffineRepr;
11use ark_ec::CurveGroup;
12use ark_ff::Field;
13use ark_serialize::*;
14use ark_std::{One, Zero};
15use core::iter;
16use std::ops::Mul;
17use std::ops::MulAssign;
18
19#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
20pub struct BulletReductionProof<G: CurveGroup> {
21 L_vec: Vec<G>,
22 R_vec: Vec<G>,
23}
24
25impl<G: CurveGroup> BulletReductionProof<G> {
26 /// Create an inner-product proof.
27 ///
28 /// The proof is created with respect to the bases \\(G\\).
29 ///
30 /// The `transcript` is passed in as a parameter so that the
31 /// challenges depend on the *entire* transcript (including parent
32 /// protocols).
33 ///
34 /// The lengths of the vectors must all be the same, and must all be
35 /// either 0 or a power of 2.
36 pub fn prove(
37 transcript: &mut PoseidonTranscript<G::ScalarField>,
38 Q: &G::Affine,
39 G_vec: &[G::Affine],
40 H: &G::Affine,
41 a_vec: &[G::ScalarField],
42 b_vec: &[G::ScalarField],
43 blind: &G::ScalarField,
44 blinds_vec: &[(G::ScalarField, G::ScalarField)],
45 ) -> (
46 BulletReductionProof<G>,
47 G,
48 G::ScalarField,
49 G::ScalarField,
50 G,
51 G::ScalarField,
52 ) {
53 // Create slices G, H, a, b backed by their respective
54 // vectors. This lets us reslice as we compress the lengths
55 // of the vectors in the main loop below.
56 let mut G = &mut G_vec.to_owned()[..];
57 let mut a = &mut a_vec.to_owned()[..];
58 let mut b = &mut b_vec.to_owned()[..];
59
60 // All of the input vectors must have a length that is a power of two.
61 let mut n = G.len();
62 assert!(n.is_power_of_two());
63 let lg_n = n.log_2();
64
65 // All of the input vectors must have the same length.
66 assert_eq!(G.len(), n);
67 assert_eq!(a.len(), n);
68 assert_eq!(b.len(), n);
69 assert_eq!(blinds_vec.len(), 2 * lg_n);
70
71 let mut L_vec = Vec::with_capacity(lg_n);
72 let mut R_vec = Vec::with_capacity(lg_n);
73 let mut blinds_iter = blinds_vec.iter();
74 let mut blind_fin = *blind;
75
76 while n != 1 {
77 n /= 2;
78 let (a_L, a_R) = a.split_at_mut(n);
79 let (b_L, b_R) = b.split_at_mut(n);
80 let (G_L, G_R) = G.split_at_mut(n);
81
82 let c_L = inner_product(a_L, b_R);
83 let c_R = inner_product(a_R, b_L);
84
85 let (blind_L, blind_R) = blinds_iter.next().unwrap();
86 let gright_vec = G_R
87 .iter()
88 .chain(iter::once(Q))
89 .chain(iter::once(H))
90 .cloned()
91 .collect::<Vec<G::Affine>>();
92
93 let L = G::msm_unchecked(
94 &gright_vec,
95 a_L
96 .iter()
97 .chain(iter::once(&c_L))
98 .chain(iter::once(blind_L))
99 .copied()
100 .collect::<Vec<G::ScalarField>>()
101 .as_slice(),
102 );
103 let gl_vec = G_L
104 .iter()
105 .chain(iter::once(Q))
106 .chain(iter::once(H))
107 .cloned()
108 .collect::<Vec<G::Affine>>();
109 let R = G::msm_unchecked(
110 &gl_vec,
111 a_R
112 .iter()
113 .chain(iter::once(&c_R))
114 .chain(iter::once(blind_R))
115 .copied()
116 .collect::<Vec<G::ScalarField>>()
117 .as_slice(),
118 );
119
120 transcript.append_point(b"", &L);
121 transcript.append_point(b"", &R);
122
123 let u: G::ScalarField = transcript.challenge_scalar(b"");
124 let u_inv = u.inverse().unwrap();
125
126 for i in 0..n {
127 a_L[i] = a_L[i] * u + u_inv * a_R[i];
128 b_L[i] = b_L[i] * u_inv + u * b_R[i];
129 G_L[i] = (G_L[i].mul(u_inv) + G_R[i].mul(u)).into_affine();
130 }
131
132 blind_fin = blind_fin + u * u * blind_L + u_inv * u_inv * blind_R;
133
134 L_vec.push(L);
135 R_vec.push(R);
136
137 a = a_L;
138 b = b_L;
139 G = G_L;
140 }
141
142 let Gamma_hat = G::msm_unchecked(&[G[0], *Q, *H], &[a[0], a[0] * b[0], blind_fin]);
143
144 (
145 BulletReductionProof { L_vec, R_vec },
146 Gamma_hat,
147 a[0],
148 b[0],
149 G[0].into_group(),
150 blind_fin,
151 )
152 }
153
154 /// Computes three vectors of verification scalars \\([u\_{i}^{2}]\\), \\([u\_{i}^{-2}]\\) and \\([s\_{i}]\\) for combined multiscalar multiplication
155 /// in a parent protocol. See [inner product protocol notes](index.html#verification-equation) for details.
156 /// The verifier must provide the input length \\(n\\) explicitly to avoid unbounded allocation within the inner product proof.
157 fn verification_scalars(
158 &self,
159 n: usize,
160 transcript: &mut PoseidonTranscript<G::ScalarField>,
161 ) -> Result<
162 (
163 Vec<G::ScalarField>,
164 Vec<G::ScalarField>,
165 Vec<G::ScalarField>,
166 ),
167 ProofVerifyError,
168 > {
169 let lg_n = self.L_vec.len();
170 if lg_n >= 32 {
171 // 4 billion multiplications should be enough for anyone
172 // and this check prevents overflow in 1<<lg_n below.
173 return Err(ProofVerifyError::InternalError);
174 }
175 if n != (1 << lg_n) {
176 return Err(ProofVerifyError::InternalError);
177 }
178
179 // 1. Recompute x_k,...,x_1 based on the proof transcript
180 let mut challenges = Vec::with_capacity(lg_n);
181 for (L, R) in self.L_vec.iter().zip(self.R_vec.iter()) {
182 transcript.append_point(b"", L);
183 transcript.append_point(b"", R);
184 challenges.push(transcript.challenge_scalar(b""));
185 }
186
187 // 2. Compute 1/(u_k...u_1) and 1/u_k, ..., 1/u_1
188 let mut challenges_inv: Vec<G::ScalarField> = challenges.clone();
189
190 ark_ff::fields::batch_inversion(&mut challenges_inv);
191 let mut allinv = G::ScalarField::one();
192 for c in challenges.iter().filter(|s| !s.is_zero()) {
193 allinv.mul_assign(c);
194 }
195 allinv = allinv.inverse().unwrap();
196
197 // 3. Compute u_i^2 and (1/u_i)^2
198 for i in 0..lg_n {
199 challenges[i] = challenges[i].square();
200 challenges_inv[i] = challenges_inv[i].square();
201 }
202 let challenges_sq = challenges;
203 let challenges_inv_sq = challenges_inv;
204
205 // 4. Compute s values inductively.
206 let mut s = Vec::with_capacity(n);
207 s.push(allinv);
208 for i in 1..n {
209 let lg_i = (32 - 1 - (i as u32).leading_zeros()) as usize;
210 let k = 1 << lg_i;
211 // The challenges are stored in "creation order" as [u_k,...,u_1],
212 // so u_{lg(i)+1} = is indexed by (lg_n-1) - lg_i
213 let u_lg_i_sq = challenges_sq[(lg_n - 1) - lg_i];
214 s.push(s[i - k] * u_lg_i_sq);
215 }
216
217 Ok((challenges_sq, challenges_inv_sq, s))
218 }
219
220 /// This method is for testing that proof generation work,
221 /// but for efficiency the actual protocols would use `verification_scalars`
222 /// method to combine inner product verification with other checks
223 /// in a single multiscalar multiplication.
224 pub fn verify(
225 &self,
226 n: usize,
227 a: &[G::ScalarField],
228 transcript: &mut PoseidonTranscript<G::ScalarField>,
229 Gamma: &G,
230 Gs: &[G::Affine],
231 ) -> Result<(G, G, G::ScalarField), ProofVerifyError> {
232 let (u_sq, u_inv_sq, s) = self.verification_scalars(n, transcript)?;
233
234 let Ls = &self.L_vec;
235 let Rs = &self.R_vec;
236
237 let G_hat = G::msm(Gs, s.as_slice()).map_err(|_| ProofVerifyError::InternalError)?;
238 let a_hat = inner_product(a, &s);
239
240 let Gamma_hat = G::msm(
241 &G::normalize_batch(
242 &Ls
243 .iter()
244 .chain(Rs.iter())
245 .chain(iter::once(Gamma))
246 .copied()
247 .collect::<Vec<G>>(),
248 ),
249 u_sq
250 .iter()
251 .chain(u_inv_sq.iter())
252 .chain(iter::once(&G::ScalarField::one()))
253 .copied()
254 .collect::<Vec<G::ScalarField>>()
255 .as_slice(),
256 )
257 .map_err(|_| ProofVerifyError::InternalError)?;
258
259 Ok((G_hat, Gamma_hat, a_hat))
260 }
261}
262
263/// Computes an inner product of two vectors
264/// \\[
265/// {\langle {\mathbf{a}}, {\mathbf{b}} \rangle} = \sum\_{i=0}^{n-1} a\_i \cdot b\_i.
266/// \\]
267/// Panics if the lengths of \\(\mathbf{a}\\) and \\(\mathbf{b}\\) are not equal.
268fn inner_product<F: Field>(a: &[F], b: &[F]) -> F {
269 assert!(
270 a.len() == b.len(),
271 "inner_product(a,b): lengths of vectors do not match"
272 );
273 let mut out = F::zero();
274 for i in 0..a.len() {
275 out += a[i] * b[i];
276 }
277 out
278}