sonobe/folding-schemes/src/folding/circuits/decider/off_chain.rs
folding-schemes/src/folding/circuits/decider/off_chain.rsRaw
1/// This file implements a generic offchain decider circuit.
2/// For ethereum use cases, use the `GenericOnchainDeciderCircuit`.
3/// More details can be found at the documentation page:
4/// https://privacy-scaling-explorations.github.io/sonobe-docs/design/nova-decider-offchain.html
5use ark_crypto_primitives::sponge::{
6 constraints::{AbsorbGadget, CryptographicSpongeVar},
7 poseidon::{constraints::PoseidonSpongeVar, PoseidonConfig},
8 Absorb,
9};
10use ark_ec::CurveGroup;
11use ark_r1cs_std::{
12 alloc::AllocVar, eq::EqGadget, fields::fp::FpVar, prelude::CurveVar, ToConstraintFieldGadget,
13};
14use ark_relations::r1cs::{ConstraintSynthesizer, ConstraintSystemRef, SynthesisError};
15use ark_std::{marker::PhantomData, Zero};
16
17use crate::{
18 arith::{
19 r1cs::{circuits::R1CSMatricesVar, R1CS},
20 Arith, ArithGadget,
21 },
22 folding::{
23 circuits::{
24 cyclefold::{
25 CycleFoldCommittedInstance, CycleFoldCommittedInstanceVar, CycleFoldWitness,
26 },
27 decider::{EvalGadget, KZGChallengesGadget},
28 nonnative::affine::NonNativeAffineVar,
29 CF1, CF2,
30 },
31 nova::{circuits::CommittedInstanceVar, decider_eth_circuit::WitnessVar},
32 traits::{CommittedInstanceOps, CommittedInstanceVarOps, Dummy, WitnessOps, WitnessVarOps},
33 },
34};
35
36use super::DeciderEnabledNIFS;
37
38/// Circuit that implements part of the in-circuit checks needed for the offchain verification over
39/// the Curve2's BaseField (=Curve1's ScalarField).
40pub struct GenericOffchainDeciderCircuit1<
41 C1: CurveGroup,
42 C2: CurveGroup,
43 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
44 RU: CommittedInstanceOps<C1>, // Running instance
45 IU: CommittedInstanceOps<C1>, // Incoming instance
46 W: WitnessOps<CF1<C1>>, // Witness
47 A: Arith<W, RU>, // Constraint system
48 AVar: ArithGadget<W::Var, RU::Var>, // In-circuit representation of `A`
49 D: DeciderEnabledNIFS<C1, RU, IU, W, A>,
50> {
51 pub _gc2: PhantomData<GC2>,
52 pub _avar: PhantomData<AVar>,
53 /// Constraint system of the Augmented Function circuit
54 pub arith: A,
55 pub poseidon_config: PoseidonConfig<CF1<C1>>,
56 /// public params hash
57 pub pp_hash: CF1<C1>,
58 pub i: CF1<C1>,
59 /// initial state
60 pub z_0: Vec<CF1<C1>>,
61 /// current i-th state
62 pub z_i: Vec<CF1<C1>>,
63 /// Folding scheme instances
64 pub U_i: RU,
65 pub W_i: W,
66 pub u_i: IU,
67 pub w_i: W,
68 pub U_i1: RU,
69 pub W_i1: W,
70
71 /// Helper for folding verification
72 pub proof: D::Proof,
73 pub randomness: D::Randomness,
74
75 /// CycleFold running instance
76 pub cf_U_i: CycleFoldCommittedInstance<C2>,
77
78 /// KZG challenges
79 pub kzg_challenges: Vec<CF1<C1>>,
80 pub kzg_evaluations: Vec<CF1<C1>>,
81}
82
83impl<
84 C1: CurveGroup,
85 C2: CurveGroup<ScalarField = CF2<C1>, BaseField = CF1<C1>>,
86 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
87 RU: CommittedInstanceOps<C1> + for<'a> Dummy<&'a A>,
88 IU: CommittedInstanceOps<C1> + for<'a> Dummy<&'a A>,
89 W: WitnessOps<CF1<C1>> + for<'a> Dummy<&'a A>,
90 A: Arith<W, RU>,
91 AVar: ArithGadget<W::Var, RU::Var> + AllocVar<A, CF1<C1>>,
92 D: DeciderEnabledNIFS<C1, RU, IU, W, A>,
93 >
94 Dummy<(
95 A,
96 &R1CS<CF1<C2>>,
97 PoseidonConfig<CF1<C1>>,
98 D::ProofDummyCfg,
99 D::RandomnessDummyCfg,
100 usize,
101 usize,
102 )> for GenericOffchainDeciderCircuit1<C1, C2, GC2, RU, IU, W, A, AVar, D>
103{
104 fn dummy(
105 (
106 arith,
107 cf_arith,
108 poseidon_config,
109 proof_config,
110 randomness_config,
111 state_len,
112 num_commitments,
113 ): (
114 A,
115 &R1CS<CF1<C2>>,
116 PoseidonConfig<CF1<C1>>,
117 D::ProofDummyCfg,
118 D::RandomnessDummyCfg,
119 usize,
120 usize,
121 ),
122 ) -> Self {
123 Self {
124 _gc2: PhantomData,
125 _avar: PhantomData,
126 poseidon_config,
127 pp_hash: Zero::zero(),
128 i: Zero::zero(),
129 z_0: vec![Zero::zero(); state_len],
130 z_i: vec![Zero::zero(); state_len],
131 U_i: RU::dummy(&arith),
132 W_i: W::dummy(&arith),
133 u_i: IU::dummy(&arith),
134 w_i: W::dummy(&arith),
135 U_i1: RU::dummy(&arith),
136 W_i1: W::dummy(&arith),
137 proof: D::Proof::dummy(proof_config),
138 randomness: D::Randomness::dummy(randomness_config),
139 cf_U_i: CycleFoldCommittedInstance::dummy(cf_arith),
140 kzg_challenges: vec![Zero::zero(); num_commitments],
141 kzg_evaluations: vec![Zero::zero(); num_commitments],
142 arith,
143 }
144 }
145}
146
147impl<
148 C1: CurveGroup,
149 C2: CurveGroup<ScalarField = CF2<C1>, BaseField = CF1<C1>>,
150 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
151 RU: CommittedInstanceOps<C1>,
152 IU: CommittedInstanceOps<C1>,
153 W: WitnessOps<CF1<C1>>,
154 A: Arith<W, RU>,
155 AVar: ArithGadget<W::Var, RU::Var> + AllocVar<A, CF1<C1>>,
156 D: DeciderEnabledNIFS<C1, RU, IU, W, A>,
157 > ConstraintSynthesizer<CF1<C1>>
158 for GenericOffchainDeciderCircuit1<C1, C2, GC2, RU, IU, W, A, AVar, D>
159where
160 RU::Var: AbsorbGadget<CF1<C1>> + CommittedInstanceVarOps<C1, PointVar = NonNativeAffineVar<C1>>,
161 CF1<C1>: Absorb,
162{
163 fn generate_constraints(self, cs: ConstraintSystemRef<CF1<C1>>) -> Result<(), SynthesisError> {
164 let arith = AVar::new_witness(cs.clone(), || Ok(&self.arith))?;
165
166 let pp_hash = FpVar::new_input(cs.clone(), || Ok(self.pp_hash))?;
167 let i = FpVar::new_input(cs.clone(), || Ok(self.i))?;
168 let z_0 = Vec::new_input(cs.clone(), || Ok(self.z_0))?;
169 let z_i = Vec::new_input(cs.clone(), || Ok(self.z_i))?;
170
171 let u_i = IU::Var::new_witness(cs.clone(), || Ok(self.u_i))?;
172 let U_i = RU::Var::new_witness(cs.clone(), || Ok(self.U_i))?;
173 // here (U_i1, W_i1) = NIFS.P( (U_i,W_i), (u_i,w_i))
174 let U_i1_commitments = Vec::<NonNativeAffineVar<C1>>::new_input(cs.clone(), || {
175 Ok(self.U_i1.get_commitments())
176 })?;
177 let U_i1 = RU::Var::new_witness(cs.clone(), || Ok(self.U_i1))?;
178 let W_i1 = W::Var::new_witness(cs.clone(), || Ok(self.W_i1))?;
179 U_i1.get_commitments().enforce_equal(&U_i1_commitments)?;
180
181 let cf_U_i =
182 CycleFoldCommittedInstanceVar::<C2, GC2>::new_input(cs.clone(), || Ok(self.cf_U_i))?;
183
184 // allocate the inputs for the checks 7.1 and 7.2
185 let kzg_challenges = Vec::new_input(cs.clone(), || Ok(self.kzg_challenges))?;
186 let kzg_evaluations = Vec::new_input(cs.clone(), || Ok(self.kzg_evaluations))?;
187
188 // `sponge` is for digest computation.
189 let sponge = PoseidonSpongeVar::new(cs.clone(), &self.poseidon_config);
190 // `transcript` is for challenge generation.
191 let mut transcript = sponge.clone();
192 // notice that the `pp_hash` is absorbed inside the ChallengeGadget::get_challenge_gadget call
193
194 // 1. enforce `U_{i+1}` and `W_{i+1}` satisfy `arith`
195 arith.enforce_relation(&W_i1, &U_i1)?;
196
197 // 2. enforce `u_i` is an incoming instance
198 u_i.enforce_incoming()?;
199
200 // 3. u_i.x[0] == H(i, z_0, z_i, U_i), u_i.x[1] == H(cf_U_i)
201 let (u_i_x, U_i_vec) = U_i.hash(&sponge, &pp_hash, &i, &z_0, &z_i)?;
202 let (cf_u_i_x, _) = cf_U_i.hash(&sponge, pp_hash.clone())?;
203 u_i.get_public_inputs().enforce_equal(&[u_i_x, cf_u_i_x])?;
204
205 // 6.1. partially enforce `NIFS.V(U_i, u_i) = U_{i+1}`.
206 D::fold_field_elements_gadget(
207 &self.arith,
208 &mut transcript,
209 pp_hash,
210 U_i,
211 U_i_vec,
212 u_i,
213 self.proof,
214 self.randomness,
215 )?
216 .enforce_partial_equal(&U_i1)?;
217
218 // 7.1. compute and check KZG challenges
219 KZGChallengesGadget::get_challenges_gadget(&mut transcript, &U_i1)?
220 .enforce_equal(&kzg_challenges)?;
221
222 // 7.2. check the claimed evaluations
223 for (((v, _r), c), e) in W_i1
224 .get_openings()
225 .iter()
226 .zip(&kzg_challenges)
227 .zip(&kzg_evaluations)
228 {
229 // The randomness `_r` is currently not used.
230 EvalGadget::evaluate_gadget(v, c)?.enforce_equal(e)?;
231 }
232
233 Ok(())
234 }
235}
236
237/// Circuit that implements part of the in-circuit checks needed for the offchain verification over
238/// the Curve1's BaseField (=Curve2's ScalarField).
239pub struct GenericOffchainDeciderCircuit2<C2: CurveGroup> {
240 /// R1CS of the CycleFold circuit
241 pub cf_arith: R1CS<CF1<C2>>,
242 pub poseidon_config: PoseidonConfig<CF1<C2>>,
243 /// public params hash
244 pub pp_hash: CF1<C2>,
245
246 /// CycleFold running instance
247 pub cf_U_i: CycleFoldCommittedInstance<C2>,
248 pub cf_W_i: CycleFoldWitness<C2>,
249
250 /// KZG challenges
251 pub kzg_challenges: Vec<CF1<C2>>,
252 pub kzg_evaluations: Vec<CF1<C2>>,
253}
254
255impl<C2: CurveGroup> Dummy<(R1CS<CF1<C2>>, PoseidonConfig<CF1<C2>>, usize)>
256 for GenericOffchainDeciderCircuit2<C2>
257{
258 fn dummy(
259 (cf_arith, poseidon_config, num_commitments): (
260 R1CS<CF1<C2>>,
261 PoseidonConfig<CF1<C2>>,
262 usize,
263 ),
264 ) -> Self {
265 Self {
266 poseidon_config,
267 pp_hash: Zero::zero(),
268 cf_U_i: CycleFoldCommittedInstance::dummy(&cf_arith),
269 cf_W_i: CycleFoldWitness::dummy(&cf_arith),
270 kzg_challenges: vec![Zero::zero(); num_commitments],
271 kzg_evaluations: vec![Zero::zero(); num_commitments],
272 cf_arith,
273 }
274 }
275}
276
277impl<C2: CurveGroup> ConstraintSynthesizer<CF1<C2>> for GenericOffchainDeciderCircuit2<C2> {
278 fn generate_constraints(self, cs: ConstraintSystemRef<CF1<C2>>) -> Result<(), SynthesisError> {
279 let cf_r1cs = R1CSMatricesVar::<CF1<C2>, FpVar<CF1<C2>>>::new_witness(cs.clone(), || {
280 Ok(self.cf_arith.clone())
281 })?;
282
283 let pp_hash = FpVar::new_input(cs.clone(), || Ok(self.pp_hash))?;
284
285 let cf_U_i = CommittedInstanceVar::new_input(cs.clone(), || Ok(self.cf_U_i))?;
286 let cf_W_i = WitnessVar::new_witness(cs.clone(), || Ok(self.cf_W_i))?;
287
288 // allocate the inputs for the checks 4.1 and 4.2
289 let kzg_challenges = Vec::new_input(cs.clone(), || Ok(self.kzg_challenges))?;
290 let kzg_evaluations = Vec::new_input(cs.clone(), || Ok(self.kzg_evaluations))?;
291
292 // `transcript` is for challenge generation.
293 let mut transcript = PoseidonSpongeVar::new(cs.clone(), &self.poseidon_config);
294 transcript.absorb(&pp_hash)?;
295
296 // 5. enforce `cf_U_i` and `cf_W_i` satisfy `cf_r1cs`
297 cf_r1cs.enforce_relation(&cf_W_i, &cf_U_i)?;
298
299 // 4.1. compute and check KZG challenges
300 KZGChallengesGadget::get_challenges_gadget(&mut transcript, &cf_U_i)?
301 .enforce_equal(&kzg_challenges)?;
302
303 // 4.2. check the claimed evaluations
304 for (((v, _r), c), e) in cf_W_i
305 .get_openings()
306 .iter()
307 .zip(&kzg_challenges)
308 .zip(&kzg_evaluations)
309 {
310 // The randomness `_r` is currently not used.
311 EvalGadget::evaluate_gadget(v, c)?.enforce_equal(e)?;
312 }
313
314 Ok(())
315 }
316}