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