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