sonobe/folding-schemes/src/folding/nova/nifs/mova.rs
folding-schemes/src/folding/nova/nifs/mova.rsRaw
1/// This module contains the implementation the NIFSTrait for the
2/// [Mova](https://eprint.iacr.org/2024/1220.pdf) NIFS (Non-Interactive Folding Scheme).
3use ark_crypto_primitives::sponge::Absorb;
4use ark_ec::{CurveGroup, Group};
5use ark_ff::PrimeField;
6use ark_poly::MultilinearExtension;
7use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
8use ark_std::log2;
9use ark_std::rand::RngCore;
10use ark_std::{One, UniformRand, Zero};
11use std::marker::PhantomData;
12
13use super::{
14 nova::NIFS as NovaNIFS,
15 pointvsline::{PointVsLine, PointVsLineProof, PointvsLineEvaluationClaim},
16 NIFSTrait,
17};
18use crate::arith::{r1cs::R1CS, Arith};
19use crate::commitment::CommitmentScheme;
20use crate::folding::circuits::CF1;
21use crate::folding::traits::Dummy;
22use crate::transcript::AbsorbNonNative;
23use crate::transcript::Transcript;
24use crate::utils::{
25 mle::dense_vec_to_dense_mle,
26 vec::{is_zero_vec, vec_add, vec_scalar_mul},
27};
28use crate::Error;
29
30#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
31pub struct CommittedInstance<C: CurveGroup> {
32 // Random evaluation point for the E
33 pub rE: Vec<C::ScalarField>,
34 // mleE is the evaluation of the MLE of E at r_E
35 pub mleE: C::ScalarField,
36 pub u: C::ScalarField,
37 pub cmW: C,
38 pub x: Vec<C::ScalarField>,
39}
40
41impl<C: CurveGroup> Absorb for CommittedInstance<C>
42where
43 C::ScalarField: Absorb,
44{
45 fn to_sponge_bytes(&self, _dest: &mut Vec<u8>) {
46 // This is never called
47 unimplemented!()
48 }
49
50 fn to_sponge_field_elements<F: PrimeField>(&self, dest: &mut Vec<F>) {
51 self.u.to_sponge_field_elements(dest);
52 self.x.to_sponge_field_elements(dest);
53 self.rE.to_sponge_field_elements(dest);
54 self.mleE.to_sponge_field_elements(dest);
55 // We cannot call `to_native_sponge_field_elements(dest)` directly, as
56 // `to_native_sponge_field_elements` needs `F` to be `C::ScalarField`,
57 // but here `F` is a generic `PrimeField`.
58 self.cmW
59 .to_native_sponge_field_elements_as_vec()
60 .to_sponge_field_elements(dest);
61 }
62}
63
64impl<C: CurveGroup> Dummy<usize> for CommittedInstance<C> {
65 fn dummy(io_len: usize) -> Self {
66 Self {
67 rE: vec![C::ScalarField::zero(); io_len],
68 mleE: C::ScalarField::zero(),
69 u: C::ScalarField::zero(),
70 cmW: C::zero(),
71 x: vec![C::ScalarField::zero(); io_len],
72 }
73 }
74}
75
76#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
77pub struct Witness<C: CurveGroup> {
78 pub E: Vec<C::ScalarField>,
79 pub W: Vec<C::ScalarField>,
80 pub rW: C::ScalarField,
81}
82
83impl<C: CurveGroup> Dummy<&R1CS<C::ScalarField>> for Witness<C> {
84 fn dummy(r1cs: &R1CS<C::ScalarField>) -> Self {
85 Self {
86 E: vec![C::ScalarField::zero(); r1cs.A.n_rows],
87 W: vec![C::ScalarField::zero(); r1cs.A.n_cols - 1 - r1cs.l],
88 rW: C::ScalarField::zero(),
89 }
90 }
91}
92
93impl<C: CurveGroup> Witness<C> {
94 pub fn new<const H: bool>(w: Vec<C::ScalarField>, e_len: usize, mut rng: impl RngCore) -> Self {
95 let rW = if H {
96 C::ScalarField::rand(&mut rng)
97 } else {
98 C::ScalarField::zero()
99 };
100
101 Self {
102 E: vec![C::ScalarField::zero(); e_len],
103 W: w,
104 rW,
105 }
106 }
107
108 pub fn commit<CS: CommitmentScheme<C, H>, const H: bool>(
109 &self,
110 params: &CS::ProverParams,
111 x: Vec<C::ScalarField>,
112 rE: Vec<C::ScalarField>,
113 ) -> Result<CommittedInstance<C>, Error> {
114 let mut mleE = C::ScalarField::zero();
115 if !is_zero_vec::<C::ScalarField>(&self.E) {
116 let E = dense_vec_to_dense_mle(log2(self.E.len()) as usize, &self.E);
117 mleE = E.evaluate(&rE).ok_or(Error::NotExpectedLength(
118 rE.len(),
119 log2(self.E.len()) as usize,
120 ))?;
121 }
122 let cmW = CS::commit(params, &self.W, &self.rW)?;
123 Ok(CommittedInstance {
124 rE,
125 mleE,
126 u: C::ScalarField::one(),
127 cmW,
128 x,
129 })
130 }
131}
132
133#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
134pub struct Proof<C: CurveGroup> {
135 pub h_proof: PointVsLineProof<C>,
136 pub mleE1_prime: C::ScalarField,
137 pub mleE2_prime: C::ScalarField,
138 pub mleT: C::ScalarField,
139}
140
141/// Implements the Non-Interactive Folding Scheme described in section 4 of
142/// [Mova](https://eprint.iacr.org/2024/1220.pdf).
143/// `H` specifies whether the NIFS will use a blinding factor
144pub struct NIFS<
145 C: CurveGroup,
146 CS: CommitmentScheme<C, H>,
147 T: Transcript<C::ScalarField>,
148 const H: bool = false,
149> {
150 _c: PhantomData<C>,
151 _cp: PhantomData<CS>,
152 _ct: PhantomData<T>,
153}
154
155impl<C: CurveGroup, CS: CommitmentScheme<C, H>, T: Transcript<C::ScalarField>, const H: bool>
156 NIFSTrait<C, CS, T, H> for NIFS<C, CS, T, H>
157where
158 <C as Group>::ScalarField: Absorb,
159 <C as CurveGroup>::BaseField: PrimeField,
160{
161 type CommittedInstance = CommittedInstance<C>;
162 type Witness = Witness<C>;
163 type ProverAux = Vec<C::ScalarField>; // T in Mova's notation
164 type Proof = Proof<C>;
165
166 fn new_witness(w: Vec<C::ScalarField>, e_len: usize, rng: impl RngCore) -> Self::Witness {
167 Witness::new::<H>(w, e_len, rng)
168 }
169
170 fn new_instance(
171 mut rng: impl RngCore,
172 params: &CS::ProverParams,
173 W: &Self::Witness,
174 x: Vec<C::ScalarField>,
175 aux: Vec<C::ScalarField>, // = r_E
176 ) -> Result<Self::CommittedInstance, Error> {
177 let mut rE = aux.clone();
178 if is_zero_vec(&rE) {
179 // means that we're in a fresh instance, so generate random value
180 rE = (0..log2(W.E.len()))
181 .map(|_| C::ScalarField::rand(&mut rng))
182 .collect();
183 }
184
185 W.commit::<CS, H>(params, x, rE)
186 }
187
188 // Protocol 7 - point 3 (16)
189 fn fold_witness(
190 a: C::ScalarField,
191 W_i: &Witness<C>,
192 w_i: &Witness<C>,
193 aux: &Vec<C::ScalarField>, // T in Mova's notation
194 ) -> Result<Witness<C>, Error> {
195 let a2 = a * a;
196 let E: Vec<C::ScalarField> = vec_add(
197 &vec_add(&W_i.E, &vec_scalar_mul(aux, &a))?,
198 &vec_scalar_mul(&w_i.E, &a2),
199 )?;
200 let W: Vec<C::ScalarField> = W_i
201 .W
202 .iter()
203 .zip(&w_i.W)
204 .map(|(i1, i2)| *i1 + (a * i2))
205 .collect();
206
207 let rW = W_i.rW + a * w_i.rW;
208 Ok(Witness::<C> { E, W, rW })
209 }
210
211 /// [Mova](https://eprint.iacr.org/2024/1220.pdf)'s section 4. Protocol 8
212 /// Returns a proof for the pt-vs-line operations along with the folded committed instance
213 /// instances and witness
214 #[allow(clippy::type_complexity)]
215 fn prove(
216 _cs_prover_params: &CS::ProverParams, // not used in Mova since we don't commit to T
217 r1cs: &R1CS<C::ScalarField>,
218 transcript: &mut T,
219 pp_hash: C::ScalarField,
220 W_i: &Witness<C>,
221 U_i: &CommittedInstance<C>,
222 w_i: &Witness<C>,
223 u_i: &CommittedInstance<C>,
224 ) -> Result<
225 (
226 Self::Witness,
227 Self::CommittedInstance,
228 Self::Proof,
229 Vec<bool>,
230 ),
231 Error,
232 > {
233 transcript.absorb(&pp_hash);
234 // Protocol 5 is pre-processing
235 transcript.absorb(U_i);
236 transcript.absorb(u_i);
237
238 // Protocol 6
239 let (
240 h_proof,
241 PointvsLineEvaluationClaim {
242 mleE1_prime,
243 mleE2_prime,
244 rE_prime,
245 },
246 ) = PointVsLine::<C, T>::prove(transcript, U_i, u_i, W_i, w_i)?;
247
248 // Protocol 7
249
250 transcript.absorb(&mleE1_prime);
251 transcript.absorb(&mleE2_prime);
252
253 // compute the cross terms
254 let z1: Vec<C::ScalarField> = [vec![U_i.u], U_i.x.to_vec(), W_i.W.to_vec()].concat();
255 let z2: Vec<C::ScalarField> = [vec![u_i.u], u_i.x.to_vec(), w_i.W.to_vec()].concat();
256 let T = NovaNIFS::<C, CS, T, H>::compute_T(r1cs, U_i.u, u_i.u, &z1, &z2)?;
257
258 let n_vars: usize = log2(W_i.E.len()) as usize;
259 if log2(T.len()) as usize != n_vars {
260 return Err(Error::NotExpectedLength(T.len(), n_vars));
261 }
262
263 let mleT = dense_vec_to_dense_mle(n_vars, &T);
264 let mleT_evaluated = mleT.evaluate(&rE_prime).ok_or(Error::EvaluationFail)?;
265
266 transcript.absorb(&mleT_evaluated);
267
268 let alpha: C::ScalarField = transcript.get_challenge();
269
270 let ci = Self::fold_committed_instance(
271 alpha,
272 U_i,
273 u_i,
274 &rE_prime,
275 &mleE1_prime,
276 &mleE2_prime,
277 &mleT_evaluated,
278 )?;
279 let w = Self::fold_witness(alpha, W_i, w_i, &T)?;
280
281 let proof = Self::Proof {
282 h_proof,
283 mleE1_prime,
284 mleE2_prime,
285 mleT: mleT_evaluated,
286 };
287 Ok((
288 w,
289 ci,
290 proof,
291 vec![], // r_bits, returned to be passed as inputs to the circuit, not used at the
292 // current impl status
293 ))
294 }
295
296 /// [Mova](https://eprint.iacr.org/2024/1220.pdf)'s section 4. It verifies the results from the proof
297 /// Both the folding and the pt-vs-line proof
298 /// returns the folded committed instance
299 fn verify(
300 transcript: &mut T,
301 pp_hash: C::ScalarField,
302 U_i: &CommittedInstance<C>,
303 u_i: &CommittedInstance<C>,
304 proof: &Proof<C>,
305 ) -> Result<(Self::CommittedInstance, Vec<bool>), Error> {
306 transcript.absorb(&pp_hash);
307 transcript.absorb(U_i);
308 transcript.absorb(u_i);
309 let rE_prime = PointVsLine::<C, T>::verify(
310 transcript,
311 U_i,
312 u_i,
313 &proof.h_proof,
314 &proof.mleE1_prime,
315 &proof.mleE2_prime,
316 )?;
317
318 transcript.absorb(&proof.mleE1_prime);
319 transcript.absorb(&proof.mleE2_prime);
320 transcript.absorb(&proof.mleT);
321
322 let alpha: C::ScalarField = transcript.get_challenge();
323
324 Ok((
325 Self::fold_committed_instance(
326 alpha,
327 U_i,
328 u_i,
329 &rE_prime,
330 &proof.mleE1_prime,
331 &proof.mleE2_prime,
332 &proof.mleT,
333 )?,
334 vec![],
335 ))
336 }
337}
338
339impl<C: CurveGroup, CS: CommitmentScheme<C, H>, T: Transcript<C::ScalarField>, const H: bool>
340 NIFS<C, CS, T, H>
341{
342 // Protocol 7 - point 3 (15)
343 fn fold_committed_instance(
344 a: C::ScalarField,
345 U_i: &CommittedInstance<C>,
346 u_i: &CommittedInstance<C>,
347 rE_prime: &[C::ScalarField],
348 mleE1_prime: &C::ScalarField,
349 mleE2_prime: &C::ScalarField,
350 mleT: &C::ScalarField,
351 ) -> Result<CommittedInstance<C>, Error> {
352 let a2 = a * a;
353 let mleE = *mleE1_prime + a * mleT + a2 * mleE2_prime;
354 let u = U_i.u + a * u_i.u;
355 let cmW = U_i.cmW + u_i.cmW.mul(a);
356 let x = U_i
357 .x
358 .iter()
359 .zip(&u_i.x)
360 .map(|(i1, i2)| *i1 + (a * i2))
361 .collect::<Vec<C::ScalarField>>();
362
363 Ok(CommittedInstance::<C> {
364 rE: rE_prime.to_vec(),
365 mleE,
366 u,
367 cmW,
368 x,
369 })
370 }
371}
372
373impl<C: CurveGroup> Arith<Witness<C>, CommittedInstance<C>> for R1CS<CF1<C>> {
374 type Evaluation = Vec<CF1<C>>;
375
376 fn eval_relation(
377 &self,
378 w: &Witness<C>,
379 u: &CommittedInstance<C>,
380 ) -> Result<Self::Evaluation, Error> {
381 self.eval_at_z(&[&[u.u][..], &u.x, &w.W].concat())
382 }
383
384 fn check_evaluation(
385 w: &Witness<C>,
386 _u: &CommittedInstance<C>,
387 e: Self::Evaluation,
388 ) -> Result<(), Error> {
389 (w.E == e).then_some(()).ok_or(Error::NotSatisfied)
390 }
391}
392
393#[cfg(test)]
394pub mod tests {
395 use super::*;
396 use ark_crypto_primitives::sponge::poseidon::PoseidonSponge;
397 use ark_pallas::{Fr, Projective};
398
399 use crate::arith::{r1cs::tests::get_test_r1cs, Arith};
400 use crate::commitment::pedersen::Pedersen;
401 use crate::folding::nova::nifs::tests::test_nifs_opt;
402
403 #[test]
404 fn test_nifs_mova() {
405 let (W, U) = test_nifs_opt::<NIFS<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>>();
406
407 // check the last folded instance relation
408 let r1cs = get_test_r1cs();
409 r1cs.check_relation(&W, &U).unwrap();
410 }
411}