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