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