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