sonobe/src/folding/nova/circuits.rs
src/folding/nova/circuits.rsRaw
1use ark_ec::{AffineRepr, CurveGroup};
2use ark_ff::Field;
3use ark_r1cs_std::{
4 alloc::{AllocVar, AllocationMode},
5 boolean::Boolean,
6 eq::EqGadget,
7 fields::fp::FpVar,
8 groups::GroupOpsBounds,
9 prelude::CurveVar,
10};
11use ark_relations::r1cs::{Namespace, SynthesisError};
12use core::{borrow::Borrow, marker::PhantomData};
13
14use super::CommittedInstance;
15use crate::folding::circuits::cyclefold::ECRLC;
16
17/// CF1 represents the ConstraintField used for the main Nova circuit which is over E1::Fr.
18pub type CF1<C> = <<C as CurveGroup>::Affine as AffineRepr>::ScalarField;
19/// CF2 represents the ConstraintField used for the CycleFold circuit which is over E2::Fr=E1::Fq.
20pub type CF2<C> = <<C as CurveGroup>::BaseField as Field>::BasePrimeField;
21
22/// CommittedInstance on E1 contains the u and x values which are folded on the main Nova
23/// constraints field (E1::Fr).
24#[derive(Debug, Clone)]
25pub struct CommittedInstanceE1Var<C: CurveGroup> {
26 _c: PhantomData<C>,
27 u: FpVar<C::ScalarField>,
28 x: Vec<FpVar<C::ScalarField>>,
29}
30
31impl<C> AllocVar<CommittedInstance<C>, CF1<C>> for CommittedInstanceE1Var<C>
32where
33 C: CurveGroup,
34{
35 fn new_variable<T: Borrow<CommittedInstance<C>>>(
36 cs: impl Into<Namespace<CF1<C>>>,
37 f: impl FnOnce() -> Result<T, SynthesisError>,
38 mode: AllocationMode,
39 ) -> Result<Self, SynthesisError> {
40 f().and_then(|val| {
41 let cs = cs.into();
42
43 let u = FpVar::<C::ScalarField>::new_variable(cs.clone(), || Ok(val.borrow().u), mode)?;
44 let x: Vec<FpVar<C::ScalarField>> =
45 Vec::new_variable(cs, || Ok(val.borrow().x.clone()), mode)?;
46
47 Ok(Self {
48 _c: PhantomData,
49 u,
50 x,
51 })
52 })
53 }
54}
55
56/// CommittedInstance on E2 contains the commitments to E and W, which are folded on the auxiliary
57/// curve constraints field (E2::Fr = E1::Fq).
58pub struct CommittedInstanceE2Var<C: CurveGroup, GC: CurveVar<C, CF2<C>>>
59where
60 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
61{
62 _c: PhantomData<C>,
63 cmE: GC,
64 cmW: GC,
65}
66
67impl<C, GC> AllocVar<CommittedInstance<C>, CF2<C>> for CommittedInstanceE2Var<C, GC>
68where
69 C: CurveGroup,
70 GC: CurveVar<C, CF2<C>>,
71 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
72{
73 fn new_variable<T: Borrow<CommittedInstance<C>>>(
74 cs: impl Into<Namespace<CF2<C>>>,
75 f: impl FnOnce() -> Result<T, SynthesisError>,
76 mode: AllocationMode,
77 ) -> Result<Self, SynthesisError> {
78 f().and_then(|val| {
79 let cs = cs.into();
80
81 let cmE = GC::new_variable(cs.clone(), || Ok(val.borrow().cmE), mode)?;
82 let cmW = GC::new_variable(cs.clone(), || Ok(val.borrow().cmW), mode)?;
83
84 Ok(Self {
85 _c: PhantomData,
86 cmE,
87 cmW,
88 })
89 })
90 }
91}
92
93/// Implements the circuit that does the checks of the Non-Interactive Folding Scheme Verifier
94/// described in section 4 of [Nova](https://eprint.iacr.org/2021/370.pdf), where the cmE & cmW checks are
95/// delegated to the NIFSCycleFoldGadget.
96pub struct NIFSGadget<C: CurveGroup> {
97 _c: PhantomData<C>,
98}
99
100impl<C: CurveGroup> NIFSGadget<C>
101where
102 C: CurveGroup,
103{
104 /// Implements the constraints for NIFS.V for u and x, since cm(E) and cm(W) are delegated to
105 /// the CycleFold circuit.
106 pub fn verify(
107 r: FpVar<CF1<C>>,
108 ci1: CommittedInstanceE1Var<C>,
109 ci2: CommittedInstanceE1Var<C>,
110 ci3: CommittedInstanceE1Var<C>,
111 ) -> Result<(), SynthesisError> {
112 // ensure that: ci3.u == ci1.u + r * ci2.u
113 ci3.u.enforce_equal(&(ci1.u + r.clone() * ci2.u))?;
114
115 // ensure that: ci3.x == ci1.x + r * ci2.x
116 let x_rlc = ci1
117 .x
118 .iter()
119 .zip(ci2.x)
120 .map(|(a, b)| a + &r * &b)
121 .collect::<Vec<FpVar<CF1<C>>>>();
122 x_rlc.enforce_equal(&ci3.x)?;
123
124 Ok(())
125 }
126}
127
128/// NIFSCycleFoldGadget performs the Nova NIFS.V elliptic curve points relation checks in the other
129/// curve following [CycleFold](https://eprint.iacr.org/2023/1192.pdf).
130pub struct NIFSCycleFoldGadget<C: CurveGroup, GC: CurveVar<C, CF2<C>>> {
131 _c: PhantomData<C>,
132 _gc: PhantomData<GC>,
133}
134impl<C: CurveGroup, GC: CurveVar<C, CF2<C>>> NIFSCycleFoldGadget<C, GC>
135where
136 C: CurveGroup,
137 GC: CurveVar<C, CF2<C>>,
138 for<'a> &'a GC: GroupOpsBounds<'a, C, GC>,
139{
140 pub fn verify(
141 r_bits: Vec<Boolean<CF2<C>>>,
142 cmT: GC,
143 ci1: CommittedInstanceE2Var<C, GC>,
144 ci2: CommittedInstanceE2Var<C, GC>,
145 ci3: CommittedInstanceE2Var<C, GC>,
146 ) -> Result<(), SynthesisError> {
147 // cm(E) check: ci3.cmE == ci1.cmE + r * cmT + r^2 * ci2.cmE
148 ci3.cmE.enforce_equal(
149 &((ci2.cmE.scalar_mul_le(r_bits.iter())? + cmT).scalar_mul_le(r_bits.iter())?
150 + ci1.cmE),
151 )?;
152 // cm(W) check: ci3.cmW == ci1.cmW + r * ci2.cmW
153 ECRLC::<C, GC>::check(r_bits, ci1.cmW, ci2.cmW, ci3.cmW)?;
154 Ok(())
155 }
156}
157
158#[cfg(test)]
159mod tests {
160 use super::*;
161 use ark_ff::{BigInteger, PrimeField};
162 use ark_pallas::{constraints::GVar, Fq, Fr, Projective};
163 use ark_r1cs_std::{alloc::AllocVar, R1CSVar};
164 use ark_relations::r1cs::ConstraintSystem;
165 use ark_std::UniformRand;
166
167 use crate::ccs::r1cs::tests::{get_test_r1cs, get_test_z};
168 use crate::folding::nova::{nifs::NIFS, Witness};
169 use crate::pedersen::Pedersen;
170 use crate::transcript::poseidon::{tests::poseidon_test_config, PoseidonTranscript};
171 use crate::transcript::Transcript;
172
173 #[test]
174 fn test_committed_instance_var() {
175 let mut rng = ark_std::test_rng();
176
177 let ci = CommittedInstance::<Projective> {
178 cmE: Projective::rand(&mut rng),
179 u: Fr::rand(&mut rng),
180 cmW: Projective::rand(&mut rng),
181 x: vec![Fr::rand(&mut rng); 1],
182 };
183
184 let cs = ConstraintSystem::<Fr>::new_ref();
185 let ciVar =
186 CommittedInstanceE1Var::<Projective>::new_witness(cs.clone(), || Ok(ci.clone()))
187 .unwrap();
188 assert_eq!(ciVar.u.value().unwrap(), ci.u);
189 assert_eq!(ciVar.x.value().unwrap(), ci.x);
190
191 // check the instantiation of the CycleFold side:
192 let cs = ConstraintSystem::<Fq>::new_ref();
193 let ciVar =
194 CommittedInstanceE2Var::<Projective, GVar>::new_witness(cs.clone(), || Ok(ci.clone()))
195 .unwrap();
196 assert_eq!(ciVar.cmE.value().unwrap(), ci.cmE);
197 assert_eq!(ciVar.cmW.value().unwrap(), ci.cmW);
198 }
199
200 #[test]
201 fn test_nifs_gadget() {
202 let r1cs = get_test_r1cs();
203 let z1 = get_test_z(3);
204 let z2 = get_test_z(4);
205 let (w1, x1) = r1cs.split_z(&z1);
206 let (w2, x2) = r1cs.split_z(&z2);
207
208 let w1 = Witness::<Projective>::new(w1.clone(), r1cs.A.n_rows);
209 let w2 = Witness::<Projective>::new(w2.clone(), r1cs.A.n_rows);
210
211 let mut rng = ark_std::test_rng();
212 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
213
214 // compute committed instances
215 let ci1 = w1.commit(&pedersen_params, x1.clone());
216 let ci2 = w2.commit(&pedersen_params, x2.clone());
217
218 // get challenge from transcript
219 let config = poseidon_test_config::<Fr>();
220 let mut tr = PoseidonTranscript::<Projective>::new(&config);
221 let r_bits = tr.get_challenge_nbits(128);
222 let r_Fr = Fr::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
223
224 let (_w3, ci3, _T, cmT) =
225 NIFS::<Projective>::prove(&pedersen_params, r_Fr, &r1cs, &w1, &ci1, &w2, &ci2).unwrap();
226
227 let cs = ConstraintSystem::<Fr>::new_ref();
228
229 let rVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(r_Fr)).unwrap();
230 let ci1Var =
231 CommittedInstanceE1Var::<Projective>::new_witness(cs.clone(), || Ok(ci1.clone()))
232 .unwrap();
233 let ci2Var =
234 CommittedInstanceE1Var::<Projective>::new_witness(cs.clone(), || Ok(ci2.clone()))
235 .unwrap();
236 let ci3Var =
237 CommittedInstanceE1Var::<Projective>::new_witness(cs.clone(), || Ok(ci3.clone()))
238 .unwrap();
239
240 NIFSGadget::<Projective>::verify(
241 rVar.clone(),
242 ci1Var.clone(),
243 ci2Var.clone(),
244 ci3Var.clone(),
245 )
246 .unwrap();
247 assert!(cs.is_satisfied().unwrap());
248
249 // cs_CC is the Constraint System on the Curve Cycle auxiliary curve constraints field
250 // (E2::Fr)
251 let cs_CC = ConstraintSystem::<Fq>::new_ref();
252
253 let r_bitsVar = Vec::<Boolean<Fq>>::new_witness(cs_CC.clone(), || Ok(r_bits)).unwrap();
254
255 let cmTVar = GVar::new_witness(cs_CC.clone(), || Ok(cmT)).unwrap();
256 let ci1Var = CommittedInstanceE2Var::<Projective, GVar>::new_witness(cs_CC.clone(), || {
257 Ok(ci1.clone())
258 })
259 .unwrap();
260 let ci2Var = CommittedInstanceE2Var::<Projective, GVar>::new_witness(cs_CC.clone(), || {
261 Ok(ci2.clone())
262 })
263 .unwrap();
264 let ci3Var = CommittedInstanceE2Var::<Projective, GVar>::new_witness(cs_CC.clone(), || {
265 Ok(ci3.clone())
266 })
267 .unwrap();
268
269 NIFSCycleFoldGadget::<Projective, GVar>::verify(r_bitsVar, cmTVar, ci1Var, ci2Var, ci3Var)
270 .unwrap();
271 assert!(cs_CC.is_satisfied().unwrap());
272 }
273}