testudo/src/mipp.rs
src/mipp.rsRaw
1use crate::poseidon_transcript::PoseidonTranscript;
2use crate::transcript::Transcript;
3use ark_ec::scalar_mul::variable_base::VariableBaseMSM;
4use ark_ec::CurveGroup;
5use ark_ec::{pairing::Pairing, AffineRepr};
6use ark_ff::{Field, PrimeField};
7use ark_poly::DenseMultilinearExtension;
8use ark_poly_commit::multilinear_pc::data_structures::{
9 CommitmentG2, CommitterKey, ProofG1, VerifierKey,
10};
11use ark_poly_commit::multilinear_pc::MultilinearPC;
12use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, SerializationError};
13use ark_std::One;
14use ark_std::Zero;
15use rayon::iter::ParallelIterator;
16use rayon::prelude::IntoParallelIterator;
17use rayon::prelude::*;
18use std::ops::{AddAssign, Mul, MulAssign};
19use thiserror::Error;
20
21#[derive(Debug, Clone, CanonicalDeserialize, CanonicalSerialize)]
22pub struct MippProof<E: Pairing> {
23 pub comms_t: Vec<(<E as Pairing>::TargetField, <E as Pairing>::TargetField)>,
24 pub comms_u: Vec<(E::G1Affine, E::G1Affine)>,
25 pub final_a: E::G1Affine,
26 pub final_h: E::G2Affine,
27 pub pst_proof_h: ProofG1<E>,
28}
29
30impl<E: Pairing> MippProof<E> {
31 pub fn prove(
32 transcript: &mut PoseidonTranscript<E::ScalarField>,
33 ck: &CommitterKey<E>,
34 a: Vec<E::G1Affine>,
35 y: Vec<E::ScalarField>,
36 h: Vec<E::G2Affine>,
37 U: &E::G1Affine,
38 _T: &<E as Pairing>::TargetField,
39 ) -> Result<MippProof<E>, Error> {
40 // the values of vectors A and y rescaled at each step of the loop
41 let (mut m_a, mut m_y) = (a.clone(), y.clone());
42 // the values of the commitment keys h for the vector A rescaled at
43 // each step of the loop
44 let mut m_h = h.clone();
45
46 // storing the cross commitments for including in the proofs
47 let mut comms_t = Vec::new();
48 let mut comms_u = Vec::new();
49
50 // the transcript challenges
51 let mut xs: Vec<E::ScalarField> = Vec::new();
52 let mut xs_inv: Vec<E::ScalarField> = Vec::new();
53
54 // we append only the MIPP because the aggregated commitment T has been
55 // appended already
56 transcript.append(b"U", U);
57
58 while m_a.len() > 1 {
59 // recursive step
60 // Recurse with problem of half size
61 let split = m_a.len() / 2;
62
63 // MIPP where n' = split///
64 // a[:n'] a[n':]
65 let (a_l, a_r) = m_a.split_at_mut(split);
66 // y[:n'] y[n':]
67 let (y_l, y_r) = m_y.split_at_mut(split);
68 // h[:n'] y[n':]
69 let (h_l, h_r) = m_h.split_at_mut(split);
70
71 // since we do this in parallel we take reference first so it can be
72 // moved within the macro's rayon scope.
73 let (_rh_l, _rh_r) = (&h_l, &h_r);
74 let (ra_l, ra_r) = (&a_l, &a_r);
75 let (ry_l, ry_r) = (&y_l, &y_r);
76
77 try_par! {
78 // MIPP part
79 // Compute cross commitments
80 // u_l = a[n':] ^ y[:n']
81 // TODO to replace by bitsf_multiexp
82 let comm_u_l = multiexponentiation(ra_l, &ry_r),
83 // u_r = a[:n'] ^ y[n':]
84 let comm_u_r = multiexponentiation(ra_r, &ry_l)
85 };
86
87 par! {
88 // Compute the cross pairing products over the distinct halfs of A
89 // t_l = a[n':] * h[:n']
90 let comm_t_l = pairings_product::<E>(&a_l, h_r),
91 // t_r = a[:n'] * h[n':]
92 let comm_t_r = pairings_product::<E>(&a_r, h_l)
93
94 };
95
96 // Fiat-Shamir challenge
97 transcript.append(b"comm_u_l", &comm_u_l);
98 transcript.append(b"comm_u_r", &comm_u_r);
99 transcript.append(b"comm_t_l", &comm_t_l);
100 transcript.append(b"comm_t_r", &comm_t_r);
101 let c_inv = transcript.challenge_scalar::<E::ScalarField>(b"challenge_i");
102
103 // Optimization for multiexponentiation to rescale G2 elements with
104 // 128-bit challenge Swap 'c' and 'c_inv' since we
105 // can't control bit size of c_inv
106 let c = c_inv.inverse().unwrap();
107
108 // Set up values for next step of recursion by compressing as follows
109 // a[n':] + a[:n']^x
110 compress(&mut m_a, split, &c);
111 // y[n':] + y[:n']^x_inv
112 compress_field(&mut m_y, split, &c_inv);
113 // h[n':] + h[:n']^x_inv
114 compress(&mut m_h, split, &c_inv);
115
116 comms_t.push((comm_t_l, comm_t_r));
117 comms_u.push((comm_u_l.into_affine(), comm_u_r.into_affine()));
118 xs.push(c);
119 xs_inv.push(c_inv);
120 }
121 assert!(m_a.len() == 1 && m_y.len() == 1 && m_h.len() == 1);
122
123 let final_a = m_a[0];
124 let final_h = m_h[0];
125
126 // get the structured polynomial p_h for which final_h = h^p_h(vec{t})
127 // is the PST commitment given generator h and toxic waste \vec{t}
128 let poly = DenseMultilinearExtension::<E::ScalarField>::from_evaluations_vec(
129 xs_inv.len(),
130 Self::polynomial_evaluations_from_transcript::<E::ScalarField>(&xs_inv),
131 );
132 let c = MultilinearPC::<E>::commit_g2(ck, &poly);
133 debug_assert!(c.h_product == final_h);
134
135 // generate a proof of opening final_h at the random point rs
136 // from the transcript
137 let rs: Vec<E::ScalarField> = (0..poly.num_vars)
138 .into_iter()
139 .map(|_| transcript.challenge_scalar::<E::ScalarField>(b"random_point"))
140 .collect();
141
142 let pst_proof_h = MultilinearPC::<E>::open_g1(ck, &poly, &rs);
143
144 Ok(MippProof {
145 comms_t,
146 comms_u,
147 final_a,
148 final_h,
149 pst_proof_h,
150 })
151 }
152
153 // builds the polynomial p_h in Lagrange basis which uses the
154 // inverses of transcript challenges this is the following
155 // structured polynomial $\prod_i(1 - z_i + cs_inv[m - i - 1] * z_i)$
156 // where m is the length of cs_inv and z_i is the unknown
157 fn polynomial_evaluations_from_transcript<F: Field>(cs_inv: &[F]) -> Vec<F> {
158 let m = cs_inv.len();
159 let pow_m = 2_usize.pow(m as u32);
160
161 // constructs the list of evaluations over the boolean hypercube \{0,1\}^m
162 let evals = (0..pow_m)
163 .into_par_iter()
164 .map(|i| {
165 let mut res = F::one();
166 for j in 0..m {
167 // we iterate from lsb to msb and, in case the bit is 1,
168 // we multiply by the corresponding challenge i.e whose
169 // index corresponds to the bit's position
170 if (i >> j) & 1 == 1 {
171 res *= cs_inv[m - j - 1];
172 }
173 }
174 res
175 })
176 .collect();
177 evals
178 }
179
180 pub fn verify(
181 vk: &VerifierKey<E>,
182 transcript: &mut PoseidonTranscript<E::ScalarField>,
183 proof: &MippProof<E>,
184 point: Vec<E::ScalarField>,
185 U: &E::G1Affine,
186 T: &<E as Pairing>::TargetField,
187 ) -> bool {
188 let comms_u = proof.comms_u.clone();
189 let comms_t = proof.comms_t.clone();
190
191 let mut xs = Vec::new();
192 let mut xs_inv = Vec::new();
193 let mut final_y = E::ScalarField::one();
194
195 let mut final_res = MippTU {
196 tc: T.clone(),
197 uc: U.into_group(),
198 };
199
200 transcript.append(b"U", U);
201
202 // Challenges need to be generated first in sequential order so the
203 // prover and the verifier have a consistent view of the transcript
204 for (i, (comm_u, comm_t)) in comms_u.iter().zip(comms_t.iter()).enumerate() {
205 let (comm_u_l, comm_u_r) = comm_u;
206 let (comm_t_l, comm_t_r) = comm_t;
207
208 // Fiat-Shamir challenge
209 transcript.append(b"comm_u_l", comm_u_l);
210 transcript.append(b"comm_u_r", comm_u_r);
211 transcript.append(b"comm_t_l", comm_t_l);
212 transcript.append(b"comm_t_r", comm_t_r);
213 let c_inv = transcript.challenge_scalar::<E::ScalarField>(b"challenge_i");
214 let c = c_inv.inverse().unwrap();
215
216 xs.push(c);
217 xs_inv.push(c_inv);
218
219 // the verifier computes the final_y by themselves because
220 // this is field operations so it's quite fast and parallelisation
221 // doesn't bring much improvement
222 final_y *= E::ScalarField::one() + c_inv.mul(point[i]) - point[i];
223 }
224
225 // First, each entry of T and U are multiplied independently by their
226 // respective challenges which is done in parralel and, at the end,
227 // the results are merged together for each vector following their
228 // corresponding merge operation.
229 enum Op<'a, E: Pairing> {
230 TC(&'a E::TargetField, <E::ScalarField as PrimeField>::BigInt),
231 UC(&'a E::G1Affine, &'a E::ScalarField),
232 }
233
234 let res = comms_t
235 .par_iter()
236 .zip(comms_u.par_iter())
237 .zip(xs.par_iter().zip(xs_inv.par_iter()))
238 .flat_map(|((comm_t, comm_u), (c, c_inv))| {
239 let (comm_t_l, comm_t_r) = comm_t;
240 let (comm_u_l, comm_u_r) = comm_u;
241
242 // we multiple left side by x^-1 and right side by x
243 vec![
244 Op::TC::<E>(comm_t_l, c_inv.into_bigint()),
245 Op::TC(comm_t_r, c.into_bigint()),
246 Op::UC(comm_u_l, c_inv),
247 Op::UC(comm_u_r, c),
248 ]
249 })
250 .fold(MippTU::<E>::default, |mut res, op: Op<E>| {
251 match op {
252 Op::TC(tx, c) => {
253 let tx: E::TargetField = tx.pow(c);
254 res.tc.mul_assign(&tx);
255 }
256 Op::UC(zx, c) => {
257 let uxp: E::G1 = zx.mul(c);
258 res.uc.add_assign(&uxp);
259 }
260 }
261 res
262 })
263 .reduce(MippTU::default, |mut acc_res, res| {
264 acc_res.merge(&res);
265 acc_res
266 });
267
268 // the initial values of T and U are also merged to get the final result
269 let ref_final_res = &mut final_res;
270 ref_final_res.merge(&res);
271
272 // get the point rs from the transcript, used by the prover to generate
273 // the PST proof
274 let mut rs: Vec<E::ScalarField> = Vec::new();
275 let m = xs_inv.len();
276 for _i in 0..m {
277 let r = transcript.challenge_scalar::<E::ScalarField>(b"random_point");
278 rs.push(r);
279 }
280
281 // Given p_h is structured as defined above, the verifier can compute
282 // p_h(rs) by themselves in O(m) time
283 let v = (0..m)
284 .into_par_iter()
285 .map(|i| E::ScalarField::one() + rs[i].mul(xs_inv[m - i - 1]) - rs[i])
286 .product();
287
288 let comm_h = CommitmentG2 {
289 nv: m,
290 h_product: proof.final_h,
291 };
292
293 // final_h is the commitment of p_h so the verifier can perform
294 // a PST verification at the random point rs, given the pst proof
295 // received from the prover prover
296 let check_h = MultilinearPC::<E>::check_2(vk, &comm_h, &rs, v, &proof.pst_proof_h);
297 assert!(check_h == true);
298
299 let final_u = proof.final_a.mul(final_y);
300 let final_t: <E as Pairing>::TargetField = E::pairing(proof.final_a, proof.final_h).0;
301
302 let check_t = ref_final_res.tc == final_t;
303 assert!(check_t == true);
304
305 let check_u = ref_final_res.uc == final_u;
306 assert!(check_u == true);
307 check_h & check_u
308 }
309}
310
311/// MippTU keeps track of the variables that have been sent by the prover and
312/// must be multiplied together by the verifier.
313struct MippTU<E: Pairing> {
314 pub tc: E::TargetField,
315 pub uc: E::G1,
316}
317
318impl<E> Default for MippTU<E>
319where
320 E: Pairing,
321{
322 fn default() -> Self {
323 Self {
324 tc: E::TargetField::one(),
325 uc: E::G1::zero(),
326 }
327 }
328}
329
330impl<E> MippTU<E>
331where
332 E: Pairing,
333{
334 fn merge(&mut self, other: &Self) {
335 self.tc.mul_assign(&other.tc);
336 self.uc.add_assign(&other.uc);
337 }
338}
339
340/// compress modifies the `vec` vector by setting the value at
341/// index $i:0 -> split$ $vec[i] = vec[i] + vec[i+split]^scaler$.
342/// The `vec` vector is half of its size after this call.
343pub fn compress<C: AffineRepr>(vec: &mut Vec<C>, split: usize, scaler: &C::ScalarField) {
344 let (left, right) = vec.split_at_mut(split);
345 left
346 .par_iter_mut()
347 .zip(right.par_iter())
348 .for_each(|(a_l, a_r)| {
349 // TODO remove that with master version
350 let mut x = a_r.mul(scaler);
351 x.add_assign(a_l.into_group());
352 *a_l = x.into_affine();
353 });
354 let len = left.len();
355 vec.resize(len, C::zero());
356}
357
358// TODO make that generic with points as well
359pub fn compress_field<F: PrimeField>(vec: &mut Vec<F>, split: usize, scaler: &F) {
360 let (left, right) = vec.split_at_mut(split);
361 assert!(left.len() == right.len());
362 left
363 .par_iter_mut()
364 .zip(right.par_iter_mut())
365 .for_each(|(a_l, a_r)| {
366 // TODO remove copy
367 a_r.mul_assign(scaler);
368 a_l.add_assign(a_r.clone());
369 });
370 let len = left.len();
371 vec.resize(len, F::zero());
372}
373
374pub fn multiexponentiation<G: AffineRepr>(
375 left: &[G],
376 right: &[G::ScalarField],
377) -> Result<G::Group, Error> {
378 if left.len() != right.len() {
379 return Err(Error::InvalidIPVectorLength);
380 }
381
382 Ok(<G::Group as VariableBaseMSM>::msm_unchecked(left, right))
383}
384
385pub fn pairings_product<E: Pairing>(gs: &[E::G1Affine], hs: &[E::G2Affine]) -> E::TargetField {
386 E::multi_pairing(gs, hs).0
387}
388
389#[derive(Debug, Error)]
390pub enum Error {
391 #[error("Serialization error: {0}")]
392 Serialization(#[from] SerializationError),
393
394 #[error("Vectors length do not match for inner product (IP)")]
395 InvalidIPVectorLength,
396 // #[error("Commitment key length invalid")]
397 // InvalidKeyLength,
398
399 // #[error("Invalid pairing result")]
400 // InvalidPairing,
401
402 // #[error("Invalid SRS: {0}")]
403 // InvalidSRS(String),
404
405 // #[error("Invalid proof: {0}")]
406 // InvalidProof(String),
407
408 // #[error("Malformed Groth16 verifying key")]
409 // MalformedVerifyingKey,
410}