sonobe/folding-schemes/src/folding/protogalaxy/mod.rs
folding-schemes/src/folding/protogalaxy/mod.rsRaw
1/// Implements the scheme described in [ProtoGalaxy](https://eprint.iacr.org/2023/1106.pdf)
2use ark_crypto_primitives::sponge::{
3 poseidon::{PoseidonConfig, PoseidonSponge},
4 Absorb, CryptographicSponge,
5};
6use ark_ec::{CurveGroup, Group};
7use ark_ff::{BigInteger, PrimeField};
8use ark_r1cs_std::{
9 alloc::{AllocVar, AllocationMode},
10 eq::EqGadget,
11 fields::{fp::FpVar, FieldVar},
12 groups::{CurveVar, GroupOpsBounds},
13 R1CSVar, ToConstraintFieldGadget,
14};
15use ark_relations::r1cs::{
16 ConstraintSynthesizer, ConstraintSystem, ConstraintSystemRef, Namespace, SynthesisError,
17};
18use ark_std::{
19 borrow::Borrow, cmp::max, fmt::Debug, log2, marker::PhantomData, rand::RngCore, One, Zero,
20};
21use constants::{INCOMING, RUNNING};
22use num_bigint::BigUint;
23
24use crate::{
25 arith::{
26 r1cs::{extract_r1cs, extract_w_x, R1CS},
27 Arith,
28 },
29 commitment::CommitmentScheme,
30 folding::circuits::{
31 cyclefold::{
32 fold_cyclefold_circuit, CycleFoldCircuit, CycleFoldCommittedInstance, CycleFoldConfig,
33 CycleFoldWitness,
34 },
35 nonnative::affine::NonNativeAffineVar,
36 CF1, CF2,
37 },
38 frontend::{utils::DummyCircuit, FCircuit},
39 utils::{get_cm_coordinates, pp_hash},
40 Error, FoldingScheme,
41};
42
43pub mod circuits;
44pub mod constants;
45pub mod folding;
46pub mod traits;
47pub(crate) mod utils;
48
49use circuits::AugmentedFCircuit;
50use folding::Folding;
51
52use super::traits::{
53 CommittedInstanceOps, CommittedInstanceVarOps, Dummy, WitnessOps, WitnessVarOps,
54};
55
56/// Configuration for ProtoGalaxy's CycleFold circuit
57pub struct ProtoGalaxyCycleFoldConfig<C: CurveGroup> {
58 _c: PhantomData<C>,
59}
60
61impl<C: CurveGroup> CycleFoldConfig for ProtoGalaxyCycleFoldConfig<C> {
62 const RANDOMNESS_BIT_LENGTH: usize = C::ScalarField::MODULUS_BIT_SIZE as usize;
63 const N_INPUT_POINTS: usize = 2;
64 type C = C;
65 type F = C::BaseField;
66}
67
68/// CycleFold circuit for computing random linear combinations of group elements
69/// in ProtoGalaxy instances.
70pub type ProtoGalaxyCycleFoldCircuit<C, GC> = CycleFoldCircuit<ProtoGalaxyCycleFoldConfig<C>, GC>;
71
72/// The committed instance of ProtoGalaxy.
73///
74/// We use `TYPE` to distinguish between incoming and running instances, as
75/// they have slightly different structures (e.g., length of `betas`) and
76/// behaviors (e.g., in satisfiability checks).
77#[derive(Clone, Debug, PartialEq, Eq)]
78pub struct CommittedInstance<C: CurveGroup, const TYPE: bool> {
79 phi: C,
80 betas: Vec<C::ScalarField>,
81 e: C::ScalarField,
82 x: Vec<C::ScalarField>,
83}
84
85impl<C: CurveGroup, const TYPE: bool> Dummy<(usize, usize)> for CommittedInstance<C, TYPE> {
86 fn dummy((io_len, t): (usize, usize)) -> Self {
87 if TYPE == INCOMING {
88 assert_eq!(t, 0);
89 }
90 Self {
91 phi: C::zero(),
92 betas: vec![Zero::zero(); t],
93 e: Zero::zero(),
94 x: vec![Zero::zero(); io_len],
95 }
96 }
97}
98
99impl<C: CurveGroup, const TYPE: bool> Dummy<&R1CS<CF1<C>>> for CommittedInstance<C, TYPE> {
100 fn dummy(r1cs: &R1CS<CF1<C>>) -> Self {
101 let t = if TYPE == RUNNING {
102 log2(r1cs.num_constraints()) as usize
103 } else {
104 0
105 };
106 Self::dummy((r1cs.num_public_inputs(), t))
107 }
108}
109
110impl<C: CurveGroup, const TYPE: bool> CommittedInstanceOps<C> for CommittedInstance<C, TYPE> {
111 type Var = CommittedInstanceVar<C, TYPE>;
112
113 fn get_commitments(&self) -> Vec<C> {
114 vec![self.phi]
115 }
116
117 fn is_incoming(&self) -> bool {
118 TYPE == INCOMING
119 }
120}
121
122#[derive(Clone, Debug)]
123pub struct CommittedInstanceVar<C: CurveGroup, const TYPE: bool> {
124 phi: NonNativeAffineVar<C>,
125 betas: Vec<FpVar<C::ScalarField>>,
126 e: FpVar<C::ScalarField>,
127 x: Vec<FpVar<C::ScalarField>>,
128}
129
130impl<C: CurveGroup, const TYPE: bool> AllocVar<CommittedInstance<C, TYPE>, C::ScalarField>
131 for CommittedInstanceVar<C, TYPE>
132{
133 fn new_variable<T: Borrow<CommittedInstance<C, TYPE>>>(
134 cs: impl Into<Namespace<C::ScalarField>>,
135 f: impl FnOnce() -> Result<T, SynthesisError>,
136 mode: AllocationMode,
137 ) -> Result<Self, SynthesisError> {
138 f().and_then(|u| {
139 let cs = cs.into();
140
141 let u = u.borrow();
142
143 Ok(Self {
144 phi: NonNativeAffineVar::new_variable(cs.clone(), || Ok(u.phi), mode)?,
145 betas: Vec::new_variable(cs.clone(), || Ok(u.betas.clone()), mode)?,
146 e: if TYPE == RUNNING {
147 FpVar::new_variable(cs.clone(), || Ok(u.e), mode)?
148 } else {
149 FpVar::zero()
150 },
151 x: Vec::new_variable(cs.clone(), || Ok(u.x.clone()), mode)?,
152 })
153 })
154 }
155}
156
157impl<C: CurveGroup, const TYPE: bool> R1CSVar<C::ScalarField> for CommittedInstanceVar<C, TYPE> {
158 type Value = CommittedInstance<C, TYPE>;
159
160 fn cs(&self) -> ConstraintSystemRef<C::ScalarField> {
161 self.phi
162 .cs()
163 .or(self.betas.cs())
164 .or(self.e.cs())
165 .or(self.x.cs())
166 }
167
168 fn value(&self) -> Result<Self::Value, SynthesisError> {
169 Ok(CommittedInstance {
170 phi: self.phi.value()?,
171 betas: self
172 .betas
173 .iter()
174 .map(|v| v.value())
175 .collect::<Result<_, _>>()?,
176 e: self.e.value()?,
177 x: self.x.iter().map(|v| v.value()).collect::<Result<_, _>>()?,
178 })
179 }
180}
181
182impl<C: CurveGroup, const TYPE: bool> CommittedInstanceVarOps<C> for CommittedInstanceVar<C, TYPE> {
183 type PointVar = NonNativeAffineVar<C>;
184
185 fn get_commitments(&self) -> Vec<Self::PointVar> {
186 vec![self.phi.clone()]
187 }
188
189 fn get_public_inputs(&self) -> &[FpVar<CF1<C>>] {
190 &self.x
191 }
192
193 fn enforce_incoming(&self) -> Result<(), SynthesisError> {
194 // We don't need to check if `self` is an incoming instance in-circuit,
195 // because incoming instances and running instances already have
196 // different types of `e` (constant vs witness) when we allocate them
197 // in-circuit.
198 (TYPE == INCOMING)
199 .then_some(())
200 .ok_or(SynthesisError::Unsatisfiable)
201 }
202
203 fn enforce_partial_equal(&self, other: &Self) -> Result<(), SynthesisError> {
204 self.betas.enforce_equal(&other.betas)?;
205 self.e.enforce_equal(&other.e)?;
206 self.x.enforce_equal(&other.x)
207 }
208}
209
210#[derive(Clone, Debug)]
211pub struct Witness<F: PrimeField> {
212 w: Vec<F>,
213 r_w: F,
214}
215
216impl<F: PrimeField> Witness<F> {
217 pub fn new(w: Vec<F>) -> Self {
218 // note: at the current version, we don't use the blinding factors and we set them to 0
219 // always.
220 // Tracking issue: https://github.com/privacy-scaling-explorations/sonobe/issues/82
221 Self { w, r_w: F::zero() }
222 }
223
224 pub fn commit<CS: CommitmentScheme<C>, C: CurveGroup<ScalarField = F>>(
225 &self,
226 params: &CS::ProverParams,
227 x: Vec<F>,
228 ) -> Result<CommittedInstance<C, false>, crate::Error> {
229 let phi = CS::commit(params, &self.w, &self.r_w)?;
230 Ok(CommittedInstance::<C, false> {
231 phi,
232 x,
233 e: F::zero(),
234 betas: vec![],
235 })
236 }
237}
238
239impl<F: PrimeField> Dummy<&R1CS<F>> for Witness<F> {
240 fn dummy(r1cs: &R1CS<F>) -> Self {
241 Self {
242 w: vec![F::zero(); r1cs.num_witnesses()],
243 r_w: F::zero(),
244 }
245 }
246}
247
248impl<F: PrimeField> WitnessOps<F> for Witness<F> {
249 type Var = WitnessVar<F>;
250
251 fn get_openings(&self) -> Vec<(&[F], F)> {
252 vec![(&self.w, self.r_w)]
253 }
254}
255
256/// In-circuit representation of the Witness associated to the CommittedInstance.
257#[derive(Debug, Clone)]
258pub struct WitnessVar<F: PrimeField> {
259 pub W: Vec<FpVar<F>>,
260 pub rW: FpVar<F>,
261}
262
263impl<F: PrimeField> AllocVar<Witness<F>, F> for WitnessVar<F> {
264 fn new_variable<T: Borrow<Witness<F>>>(
265 cs: impl Into<Namespace<F>>,
266 f: impl FnOnce() -> Result<T, SynthesisError>,
267 mode: AllocationMode,
268 ) -> Result<Self, SynthesisError> {
269 f().and_then(|val| {
270 let cs = cs.into();
271
272 let W = Vec::new_variable(cs.clone(), || Ok(val.borrow().w.to_vec()), mode)?;
273 let rW = FpVar::new_variable(cs.clone(), || Ok(val.borrow().r_w), mode)?;
274
275 Ok(Self { W, rW })
276 })
277 }
278}
279
280impl<F: PrimeField> WitnessVarOps<F> for WitnessVar<F> {
281 fn get_openings(&self) -> Vec<(&[FpVar<F>], FpVar<F>)> {
282 vec![(&self.W, self.rW.clone())]
283 }
284}
285
286#[derive(Debug, thiserror::Error, PartialEq)]
287pub enum ProtoGalaxyError {
288 #[error("The remainder from G(X)-F(α)*L_0(X)) / Z(X) should be zero")]
289 RemainderNotZero,
290 #[error("Could not divide by vanishing polynomial")]
291 CouldNotDivideByVanishing,
292 #[error("The number of incoming instances + 1 should be a power of two, current number of instances: {0}")]
293 WrongNumInstances(usize),
294 #[error("The number of incoming items should be a power of two, current number of coefficients: {0}")]
295 BTreeNotFull(usize),
296 #[error("The lengths of β and δ do not equal: |β| = {0}, |δ|={0}")]
297 WrongLenBetas(usize, usize),
298}
299
300/// Proving parameters for ProtoGalaxy-based IVC
301#[derive(Debug, Clone)]
302pub struct ProverParams<C1, C2, CS1, CS2>
303where
304 C1: CurveGroup,
305 C2: CurveGroup,
306 CS1: CommitmentScheme<C1>,
307 CS2: CommitmentScheme<C2>,
308{
309 /// Poseidon sponge configuration
310 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
311 /// Proving parameters of the underlying commitment scheme over C1
312 pub cs_params: CS1::ProverParams,
313 /// Proving parameters of the underlying commitment scheme over C2
314 pub cf_cs_params: CS2::ProverParams,
315}
316
317/// Verification parameters for ProtoGalaxy-based IVC
318#[derive(Debug, Clone)]
319pub struct VerifierParams<C1, C2, CS1, CS2>
320where
321 C1: CurveGroup,
322 C2: CurveGroup,
323 CS1: CommitmentScheme<C1>,
324 CS2: CommitmentScheme<C2>,
325{
326 /// Poseidon sponge configuration
327 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
328 /// R1CS of the Augmented step circuit
329 pub r1cs: R1CS<C1::ScalarField>,
330 /// R1CS of the CycleFold circuit
331 pub cf_r1cs: R1CS<C2::ScalarField>,
332 /// Verification parameters of the underlying commitment scheme over C1
333 pub cs_vp: CS1::VerifierParams,
334 /// Verification parameters of the underlying commitment scheme over C2
335 pub cf_cs_vp: CS2::VerifierParams,
336}
337
338impl<C1, C2, CS1, CS2> VerifierParams<C1, C2, CS1, CS2>
339where
340 C1: CurveGroup,
341 C2: CurveGroup,
342 CS1: CommitmentScheme<C1>,
343 CS2: CommitmentScheme<C2>,
344{
345 /// returns the hash of the public parameters of ProtoGalaxy
346 pub fn pp_hash(&self) -> Result<C1::ScalarField, Error> {
347 // TODO (@winderica): support hiding commitments in ProtoGalaxy.
348 // For now, `H` is set to false.
349 // Tracking issue: https://github.com/privacy-scaling-explorations/sonobe/issues/82
350 pp_hash::<C1, C2, CS1, CS2, false>(
351 &self.r1cs,
352 &self.cf_r1cs,
353 &self.cs_vp,
354 &self.cf_cs_vp,
355 &self.poseidon_config,
356 )
357 }
358}
359
360/// Implements ProtoGalaxy+CycleFold's IVC, described in [ProtoGalaxy] and
361/// [CycleFold], following the FoldingScheme trait
362///
363/// [ProtoGalaxy]: https://eprint.iacr.org/2023/1106.pdf
364/// [CycleFold]: https://eprint.iacr.org/2023/1192.pdf
365#[derive(Clone, Debug)]
366pub struct ProtoGalaxy<C1, GC1, C2, GC2, FC, CS1, CS2>
367where
368 C1: CurveGroup,
369 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
370 C2: CurveGroup,
371 GC2: CurveVar<C2, CF2<C2>>,
372 FC: FCircuit<C1::ScalarField>,
373 CS1: CommitmentScheme<C1>,
374 CS2: CommitmentScheme<C2>,
375{
376 _gc1: PhantomData<GC1>,
377 _c2: PhantomData<C2>,
378 _gc2: PhantomData<GC2>,
379 /// R1CS of the Augmented Function circuit
380 pub r1cs: R1CS<C1::ScalarField>,
381 /// R1CS of the CycleFold circuit
382 pub cf_r1cs: R1CS<C2::ScalarField>,
383 pub poseidon_config: PoseidonConfig<C1::ScalarField>,
384 /// CommitmentScheme::ProverParams over C1
385 pub cs_params: CS1::ProverParams,
386 /// CycleFold CommitmentScheme::ProverParams, over C2
387 pub cf_cs_params: CS2::ProverParams,
388 /// F circuit, the circuit that is being folded
389 pub F: FC,
390 /// public params hash
391 pub pp_hash: C1::ScalarField,
392 pub i: C1::ScalarField,
393 /// initial state
394 pub z_0: Vec<C1::ScalarField>,
395 /// current i-th state
396 pub z_i: Vec<C1::ScalarField>,
397 /// ProtoGalaxy instances
398 pub w_i: Witness<C1::ScalarField>,
399 pub u_i: CommittedInstance<C1, false>,
400 pub W_i: Witness<C1::ScalarField>,
401 pub U_i: CommittedInstance<C1, true>,
402
403 /// CycleFold running instance
404 pub cf_W_i: CycleFoldWitness<C2>,
405 pub cf_U_i: CycleFoldCommittedInstance<C2>,
406}
407
408impl<C1, GC1, C2, GC2, FC, CS1, CS2> ProtoGalaxy<C1, GC1, C2, GC2, FC, CS1, CS2>
409where
410 C1: CurveGroup,
411 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
412 C2: CurveGroup,
413 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
414 FC: FCircuit<C1::ScalarField>,
415 CS1: CommitmentScheme<C1>,
416 CS2: CommitmentScheme<C2>,
417 <C1 as CurveGroup>::BaseField: PrimeField,
418 <C2 as CurveGroup>::BaseField: PrimeField,
419 C1::ScalarField: Absorb,
420 C2::ScalarField: Absorb,
421 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
422 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
423 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
424{
425 /// This method computes the parameter `t` in ProtoGalaxy for folding `F'`,
426 /// the augmented circuit of `F`
427 fn compute_t(
428 poseidon_config: &PoseidonConfig<CF1<C1>>,
429 F: &FC,
430 d: usize,
431 k: usize,
432 ) -> Result<usize, SynthesisError> {
433 // In ProtoGalaxy, prover and verifier are parameterized by `t = log(n)`
434 // where `n` is the number of constraints in the circuit (known as the
435 // mapping `f` in the paper).
436 // For IVC, `f` is the augmented circuit `F'`, which not only includes
437 // the original computation `F`, but also the in-circuit verifier of
438 // ProtoGalaxy.
439 // Therefore, `t` depends on the size of `F'`, but the size of `F'` in
440 // turn depends on `t`.
441 // To address this circular dependency, we first find `t_lower_bound`,
442 // the lower bound of `t`. Then we incrementally increase `t` and build
443 // the circuit `F'` with `t` as ProtoGalaxy's parameter, until `t` is
444 // the smallest integer that equals the logarithm of the number of
445 // constraints.
446
447 // For `t_lower_bound`, we configure `F'` with `t = 1` and compute log2
448 // of the size of `F'`.
449 let state_len = F.state_len();
450 let external_inputs_len = F.external_inputs_len();
451
452 // `F'` includes `F` and `ProtoGalaxy.V`, where `F` might be costly.
453 // Observing that the cost of `F` is constant with respect to `t`, we
454 // separately compute `step_constraints`, the size of `F`.
455 // Later, we only need to re-run the rest of `F'` with updated `t` to
456 // get the size of `F'`.
457 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
458 F.generate_step_constraints(
459 cs.clone(),
460 0,
461 Vec::new_witness(cs.clone(), || Ok(vec![Zero::zero(); state_len]))?,
462 Vec::new_witness(cs.clone(), || Ok(vec![Zero::zero(); external_inputs_len]))?,
463 )?;
464 let step_constraints = cs.num_constraints();
465
466 // Create a dummy circuit with the same state length and external inputs
467 // length as `F`, which replaces `F` in the augmented circuit `F'`.
468 let dummy_circuit: DummyCircuit =
469 FCircuit::<C1::ScalarField>::new((state_len, external_inputs_len)).unwrap();
470
471 // Compute `augmentation_constraints`, the size of `F'` without `F`.
472 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
473 AugmentedFCircuit::<C1, C2, GC2, DummyCircuit>::empty(
474 poseidon_config,
475 dummy_circuit.clone(),
476 1,
477 d,
478 k,
479 )
480 .generate_constraints(cs.clone())?;
481 let augmentation_constraints = cs.num_constraints();
482
483 // The sum of `step_constraints` and `augmentation_constraints` is the
484 // size of `F'` with `t = 1`, and hence the actual `t` should have lower
485 // bound `log2(step_constraints + augmentation_constraints)`.
486 let t_lower_bound = log2(step_constraints + augmentation_constraints) as usize;
487 // Optimization: we in fact only need to try two values of `t`.
488 // This is because increasing `t` will only slightly affect the size of
489 // `F'` (more specifically, the size of `F'` will never be doubled).
490 // Thus, `t_lower_bound` (the log2 size of `F'` with `t = 1`) is very
491 // close to the actual `t` (either `t` or `t - 1`).
492 let t_upper_bound = t_lower_bound + 1;
493
494 for t in t_lower_bound..=t_upper_bound {
495 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
496 AugmentedFCircuit::<C1, C2, GC2, DummyCircuit>::empty(
497 poseidon_config,
498 dummy_circuit.clone(),
499 t,
500 d,
501 k,
502 )
503 .generate_constraints(cs.clone())?;
504 let augmentation_constraints = cs.num_constraints();
505 if t == log2(step_constraints + augmentation_constraints) as usize {
506 return Ok(t);
507 }
508 }
509 unreachable!()
510 }
511}
512
513impl<C1, GC1, C2, GC2, FC, CS1, CS2> FoldingScheme<C1, C2, FC>
514 for ProtoGalaxy<C1, GC1, C2, GC2, FC, CS1, CS2>
515where
516 C1: CurveGroup,
517 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
518 C2: CurveGroup,
519 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
520 FC: FCircuit<C1::ScalarField>,
521 CS1: CommitmentScheme<C1>,
522 CS2: CommitmentScheme<C2>,
523 <C1 as CurveGroup>::BaseField: PrimeField,
524 <C2 as CurveGroup>::BaseField: PrimeField,
525 C1::ScalarField: Absorb,
526 C2::ScalarField: Absorb,
527 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
528 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
529 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
530{
531 type PreprocessorParam = (PoseidonConfig<CF1<C1>>, FC);
532 type ProverParam = ProverParams<C1, C2, CS1, CS2>;
533 type VerifierParam = VerifierParams<C1, C2, CS1, CS2>;
534 type RunningInstance = (CommittedInstance<C1, true>, Witness<C1::ScalarField>);
535 type IncomingInstance = (CommittedInstance<C1, false>, Witness<C1::ScalarField>);
536 type MultiCommittedInstanceWithWitness =
537 (CommittedInstance<C1, false>, Witness<C1::ScalarField>);
538 type CFInstance = (CycleFoldCommittedInstance<C2>, CycleFoldWitness<C2>);
539
540 fn preprocess(
541 mut rng: impl RngCore,
542 (poseidon_config, F): &Self::PreprocessorParam,
543 ) -> Result<(Self::ProverParam, Self::VerifierParam), Error> {
544 // We fix `k`, the number of incoming instances, to 1, because
545 // multi-instances folding is not supported yet.
546 // TODO (@winderica): Support multi-instances folding and make `k` a
547 // constant generic parameter (as in HyperNova)
548 // Tracking issue: https://github.com/privacy-scaling-explorations/sonobe/issues/82
549 let k = 1;
550 // `d`, the degree of the constraint system, is set to 2, as we only
551 // support R1CS for now, whose highest degree is 2.
552 let d = 2;
553 let t = Self::compute_t(poseidon_config, F, d, k)?;
554
555 // prepare the circuit to obtain its R1CS
556 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
557 let cs2 = ConstraintSystem::<C1::BaseField>::new_ref();
558
559 let augmented_F_circuit =
560 AugmentedFCircuit::<C1, C2, GC2, FC>::empty(poseidon_config, F.clone(), t, d, k);
561 let cf_circuit = ProtoGalaxyCycleFoldCircuit::<C1, GC1>::empty();
562
563 augmented_F_circuit.generate_constraints(cs.clone())?;
564 cs.finalize();
565 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
566 let r1cs = extract_r1cs::<C1::ScalarField>(&cs);
567
568 cf_circuit.generate_constraints(cs2.clone())?;
569 cs2.finalize();
570 let cs2 = cs2.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
571 let cf_r1cs = extract_r1cs::<C1::BaseField>(&cs2);
572
573 let (cs_pp, cs_vp) = CS1::setup(&mut rng, r1cs.A.n_rows)?;
574 let (cf_cs_pp, cf_cs_vp) = CS2::setup(&mut rng, max(cf_r1cs.A.n_rows, cf_r1cs.A.n_cols))?;
575
576 Ok((
577 Self::ProverParam {
578 poseidon_config: poseidon_config.clone(),
579 cs_params: cs_pp,
580 cf_cs_params: cf_cs_pp,
581 },
582 Self::VerifierParam {
583 poseidon_config: poseidon_config.clone(),
584 r1cs,
585 cf_r1cs,
586 cs_vp,
587 cf_cs_vp,
588 },
589 ))
590 }
591
592 /// Initializes the ProtoGalaxy+CycleFold's IVC for the given parameters and
593 /// initial state `z_0`.
594 fn init(
595 (pp, vp): &(Self::ProverParam, Self::VerifierParam),
596 F: FC,
597 z_0: Vec<C1::ScalarField>,
598 ) -> Result<Self, Error> {
599 // compute the public params hash
600 let pp_hash = vp.pp_hash()?;
601
602 // setup the dummy instances
603 let (w_dummy, u_dummy) = vp.r1cs.dummy_witness_instance();
604 let (W_dummy, U_dummy) = vp.r1cs.dummy_witness_instance();
605 let (cf_W_dummy, cf_U_dummy) = vp.cf_r1cs.dummy_witness_instance();
606
607 // W_dummy=W_0 is a 'dummy witness', all zeroes, but with the size corresponding to the
608 // R1CS that we're working with.
609 Ok(Self {
610 _gc1: PhantomData,
611 _c2: PhantomData,
612 _gc2: PhantomData,
613 r1cs: vp.r1cs.clone(),
614 cf_r1cs: vp.cf_r1cs.clone(),
615 poseidon_config: pp.poseidon_config.clone(),
616 cs_params: pp.cs_params.clone(),
617 cf_cs_params: pp.cf_cs_params.clone(),
618 F,
619 pp_hash,
620 i: C1::ScalarField::zero(),
621 z_0: z_0.clone(),
622 z_i: z_0,
623 w_i: w_dummy,
624 u_i: u_dummy,
625 W_i: W_dummy,
626 U_i: U_dummy,
627 // cyclefold running instance
628 cf_W_i: cf_W_dummy,
629 cf_U_i: cf_U_dummy,
630 })
631 }
632
633 /// Implements IVC.P of ProtoGalaxy+CycleFold
634 fn prove_step(
635 &mut self,
636 mut rng: impl RngCore,
637 external_inputs: Vec<C1::ScalarField>,
638 _other_instances: Option<Self::MultiCommittedInstanceWithWitness>,
639 ) -> Result<(), Error> {
640 // Multi-instances folding is not supported yet.
641 if _other_instances.is_some() {
642 return Err(Error::NoMultiInstances);
643 }
644 // We fix `k`, the number of incoming instances, to 1, because
645 // multi-instances folding is not supported yet.
646 // TODO (@winderica): Support multi-instances folding and make `k` a
647 // constant generic parameter (as in HyperNova)
648 // Tracking issue: https://github.com/privacy-scaling-explorations/sonobe/issues/82
649 let k = 1;
650 // `d`, the degree of the constraint system, is set to 2, as we only
651 // support R1CS for now, whose highest degree is 2.
652 let d = 2;
653
654 // `sponge` is for digest computation.
655 let sponge = PoseidonSponge::<C1::ScalarField>::new(&self.poseidon_config);
656 // `transcript` is for challenge generation.
657 let mut transcript_prover = sponge.clone();
658
659 let mut augmented_F_circuit: AugmentedFCircuit<C1, C2, GC2, FC>;
660
661 if self.z_i.len() != self.F.state_len() {
662 return Err(Error::NotSameLength(
663 "z_i.len()".to_string(),
664 self.z_i.len(),
665 "F.state_len()".to_string(),
666 self.F.state_len(),
667 ));
668 }
669 if external_inputs.len() != self.F.external_inputs_len() {
670 return Err(Error::NotSameLength(
671 "F.external_inputs_len()".to_string(),
672 self.F.external_inputs_len(),
673 "external_inputs.len()".to_string(),
674 external_inputs.len(),
675 ));
676 }
677
678 let i_bn: BigUint = self.i.into();
679 let i_usize: usize = i_bn.try_into().map_err(|_| Error::MaxStep)?;
680
681 let z_i1 = self
682 .F
683 .step_native(i_usize, self.z_i.clone(), external_inputs.clone())?;
684
685 // folded instance output (public input, x)
686 // u_{i+1}.x[0] = H(i+1, z_0, z_{i+1}, U_{i+1})
687 let u_i1_x: C1::ScalarField;
688 // u_{i+1}.x[1] = H(cf_U_{i+1})
689 let cf_u_i1_x: C1::ScalarField;
690
691 if self.i.is_zero() {
692 // Take extra care of the base case
693 // `U_{i+1}` (i.e., `U_1`) is fixed to `U_dummy`, so we just use
694 // `self.U_i = U_0 = U_dummy`.
695 u_i1_x = self.U_i.hash(
696 &sponge,
697 self.pp_hash,
698 self.i + C1::ScalarField::one(),
699 &self.z_0,
700 &z_i1,
701 );
702 // `cf_U_{i+1}` (i.e., `cf_U_1`) is fixed to `cf_U_dummy`, so we
703 // just use `self.cf_U_i = cf_U_0 = cf_U_dummy`.
704 cf_u_i1_x = self.cf_U_i.hash_cyclefold(&sponge, self.pp_hash);
705
706 augmented_F_circuit = AugmentedFCircuit::empty(
707 &self.poseidon_config,
708 self.F.clone(),
709 self.U_i.betas.len(),
710 d,
711 k,
712 );
713 augmented_F_circuit.pp_hash = self.pp_hash;
714 augmented_F_circuit.z_0.clone_from(&self.z_0);
715 augmented_F_circuit.z_i.clone_from(&self.z_i);
716 augmented_F_circuit
717 .external_inputs
718 .clone_from(&external_inputs);
719
720 // There is no need to update `self.U_i` etc. as they are unchanged.
721 } else {
722 // Primary part:
723 // Compute `U_{i+1}` by folding `u_i` into `U_i`.
724 let (U_i1, W_i1, F_coeffs, K_coeffs, L_evals, phi_stars) = Folding::prove(
725 &mut transcript_prover,
726 &self.r1cs,
727 &self.U_i,
728 &self.W_i,
729 &[self.u_i.clone()],
730 &[self.w_i.clone()],
731 )?;
732
733 // CycleFold part:
734 // get the vector used as public inputs 'x' in the CycleFold circuit
735 let mut r0_bits = L_evals[0].into_bigint().to_bits_le();
736 let mut r1_bits = L_evals[1].into_bigint().to_bits_le();
737 r0_bits.resize(C1::ScalarField::MODULUS_BIT_SIZE as usize, false);
738 r1_bits.resize(C1::ScalarField::MODULUS_BIT_SIZE as usize, false);
739
740 // cyclefold circuit for enforcing:
741 // 0 + U_i.phi * L_evals[0] == phi_stars[0]
742 let cf1_u_i_x = [
743 r0_bits
744 .chunks(C1::BaseField::MODULUS_BIT_SIZE as usize - 1)
745 .map(BigInteger::from_bits_le)
746 .map(C1::BaseField::from_bigint)
747 .collect::<Option<Vec<_>>>()
748 .unwrap(),
749 get_cm_coordinates(&C1::zero()),
750 get_cm_coordinates(&self.U_i.phi),
751 get_cm_coordinates(&phi_stars[0]),
752 ]
753 .concat();
754 let cf1_circuit = ProtoGalaxyCycleFoldCircuit::<C1, GC1> {
755 _gc: PhantomData,
756 r_bits: Some(r0_bits),
757 points: Some(vec![C1::zero(), self.U_i.phi]),
758 x: Some(cf1_u_i_x.clone()),
759 };
760
761 // cyclefold circuit for enforcing:
762 // phi_stars[0] + u_i.phi * L_evals[1] == U_i1.phi
763 // i.e., U_i.phi * L_evals[0] + u_i.phi * L_evals[1] == U_i1.phi
764 let cf2_u_i_x = [
765 r1_bits
766 .chunks(C1::BaseField::MODULUS_BIT_SIZE as usize - 1)
767 .map(BigInteger::from_bits_le)
768 .map(C1::BaseField::from_bigint)
769 .collect::<Option<Vec<_>>>()
770 .unwrap(),
771 get_cm_coordinates(&phi_stars[0]),
772 get_cm_coordinates(&self.u_i.phi),
773 get_cm_coordinates(&U_i1.phi),
774 ]
775 .concat();
776 let cf2_circuit = ProtoGalaxyCycleFoldCircuit::<C1, GC1> {
777 _gc: PhantomData,
778 r_bits: Some(r1_bits),
779 points: Some(vec![phi_stars[0], self.u_i.phi]),
780 x: Some(cf2_u_i_x.clone()),
781 };
782
783 // fold self.cf_U_i + cf1_U -> folded running with cf1
784 let (_cf1_w_i, cf1_u_i, cf1_W_i1, cf1_U_i1, cf1_cmT, _) = self.fold_cyclefold_circuit(
785 &mut transcript_prover,
786 self.cf_W_i.clone(), // CycleFold running instance witness
787 self.cf_U_i.clone(), // CycleFold running instance
788 cf1_u_i_x,
789 cf1_circuit,
790 &mut rng,
791 )?;
792 // fold [the output from folding self.cf_U_i + cf1_U] + cf2_U = folded_running_with_cf1 + cf2
793 let (_cf2_w_i, cf2_u_i, cf_W_i1, cf_U_i1, cf2_cmT, _) = self.fold_cyclefold_circuit(
794 &mut transcript_prover,
795 cf1_W_i1,
796 cf1_U_i1.clone(),
797 cf2_u_i_x,
798 cf2_circuit,
799 &mut rng,
800 )?;
801
802 // Derive `u_{i+1}.x[0], u_{i+1}.x[1]` by hashing folded instances
803 u_i1_x = U_i1.hash(
804 &sponge,
805 self.pp_hash,
806 self.i + C1::ScalarField::one(),
807 &self.z_0,
808 &z_i1,
809 );
810 cf_u_i1_x = cf_U_i1.hash_cyclefold(&sponge, self.pp_hash);
811
812 augmented_F_circuit = AugmentedFCircuit {
813 _gc2: PhantomData,
814 poseidon_config: self.poseidon_config.clone(),
815 pp_hash: self.pp_hash,
816 i: self.i,
817 i_usize,
818 z_0: self.z_0.clone(),
819 z_i: self.z_i.clone(),
820 external_inputs: external_inputs.clone(),
821 u_i_phi: self.u_i.phi,
822 U_i: self.U_i.clone(),
823 U_i1_phi: U_i1.phi,
824 F_coeffs: F_coeffs.clone(),
825 K_coeffs: K_coeffs.clone(),
826 phi_stars,
827 F: self.F.clone(),
828 x: Some(u_i1_x),
829 // cyclefold values
830 cf1_u_i_cmW: cf1_u_i.cmW,
831 cf2_u_i_cmW: cf2_u_i.cmW,
832 cf_U_i: self.cf_U_i.clone(),
833 cf1_cmT,
834 cf2_cmT,
835 cf_x: Some(cf_u_i1_x),
836 };
837
838 #[cfg(test)]
839 {
840 let mut transcript_verifier = sponge.clone();
841 assert_eq!(
842 Folding::verify(
843 &mut transcript_verifier,
844 &self.U_i,
845 &[self.u_i.clone()],
846 F_coeffs,
847 K_coeffs
848 )?,
849 U_i1
850 );
851 cf1_u_i.check_incoming()?;
852 cf2_u_i.check_incoming()?;
853 self.cf_r1cs.check_relation(&_cf1_w_i, &cf1_u_i)?;
854 self.cf_r1cs.check_relation(&_cf2_w_i, &cf2_u_i)?;
855 self.cf_r1cs.check_relation(&self.cf_W_i, &self.cf_U_i)?;
856 }
857
858 self.W_i = W_i1;
859 self.U_i = U_i1;
860 self.cf_W_i = cf_W_i1;
861 self.cf_U_i = cf_U_i1;
862 }
863
864 let cs = ConstraintSystem::<C1::ScalarField>::new_ref();
865
866 augmented_F_circuit.generate_constraints(cs.clone())?;
867
868 #[cfg(test)]
869 assert!(cs.is_satisfied().unwrap());
870
871 let cs = cs.into_inner().ok_or(Error::NoInnerConstraintSystem)?;
872 let (w_i1, x_i1) = extract_w_x::<C1::ScalarField>(&cs);
873 if x_i1[0] != u_i1_x || x_i1[1] != cf_u_i1_x {
874 return Err(Error::NotEqual);
875 }
876
877 #[cfg(test)]
878 if x_i1.len() != 2 {
879 return Err(Error::NotExpectedLength(x_i1.len(), 2));
880 }
881
882 // set values for next iteration
883 self.i += C1::ScalarField::one();
884 self.z_i = z_i1;
885 self.w_i = Witness::new(w_i1);
886 self.u_i = self.w_i.commit::<CS1, C1>(&self.cs_params, x_i1)?;
887
888 #[cfg(test)]
889 {
890 self.u_i.check_incoming()?;
891 self.r1cs.check_relation(&self.w_i, &self.u_i)?;
892 self.r1cs.check_relation(&self.W_i, &self.U_i)?;
893 }
894
895 Ok(())
896 }
897
898 fn state(&self) -> Vec<C1::ScalarField> {
899 self.z_i.clone()
900 }
901 fn instances(
902 &self,
903 ) -> (
904 Self::RunningInstance,
905 Self::IncomingInstance,
906 Self::CFInstance,
907 ) {
908 (
909 (self.U_i.clone(), self.W_i.clone()),
910 (self.u_i.clone(), self.w_i.clone()),
911 (self.cf_U_i.clone(), self.cf_W_i.clone()),
912 )
913 }
914
915 /// Implements IVC.V of ProtoGalaxy+CycleFold
916 fn verify(
917 vp: Self::VerifierParam,
918 z_0: Vec<C1::ScalarField>, // initial state
919 z_i: Vec<C1::ScalarField>, // last state
920 num_steps: C1::ScalarField,
921 running_instance: Self::RunningInstance,
922 incoming_instance: Self::IncomingInstance,
923 cyclefold_instance: Self::CFInstance,
924 ) -> Result<(), Error> {
925 let sponge = PoseidonSponge::<C1::ScalarField>::new(&vp.poseidon_config);
926
927 let (U_i, W_i) = running_instance;
928 let (u_i, w_i) = incoming_instance;
929 let (cf_U_i, cf_W_i) = cyclefold_instance;
930
931 if u_i.x.len() != 2 || U_i.x.len() != 2 {
932 return Err(Error::IVCVerificationFail);
933 }
934
935 let pp_hash = vp.pp_hash()?;
936
937 // check that u_i's output points to the running instance
938 // u_i.X[0] == H(i, z_0, z_i, U_i)
939 let expected_u_i_x = U_i.hash(&sponge, pp_hash, num_steps, &z_0, &z_i);
940 if expected_u_i_x != u_i.x[0] {
941 return Err(Error::IVCVerificationFail);
942 }
943 // u_i.X[1] == H(cf_U_i)
944 let expected_cf_u_i_x = cf_U_i.hash_cyclefold(&sponge, pp_hash);
945 if expected_cf_u_i_x != u_i.x[1] {
946 return Err(Error::IVCVerificationFail);
947 }
948
949 // check R1CS satisfiability, which is equivalent to checking if `u_i`
950 // is an incoming instance and if `w_i` and `u_i` satisfy RelaxedR1CS
951 u_i.check_incoming()?;
952 vp.r1cs.check_relation(&w_i, &u_i)?;
953 // check RelaxedR1CS satisfiability
954 vp.r1cs.check_relation(&W_i, &U_i)?;
955
956 // check CycleFold RelaxedR1CS satisfiability
957 vp.cf_r1cs.check_relation(&cf_W_i, &cf_U_i)?;
958
959 Ok(())
960 }
961}
962
963impl<C1, GC1, C2, GC2, FC, CS1, CS2> ProtoGalaxy<C1, GC1, C2, GC2, FC, CS1, CS2>
964where
965 C1: CurveGroup,
966 GC1: CurveVar<C1, CF2<C1>> + ToConstraintFieldGadget<CF2<C1>>,
967 C2: CurveGroup,
968 GC2: CurveVar<C2, CF2<C2>> + ToConstraintFieldGadget<CF2<C2>>,
969 FC: FCircuit<C1::ScalarField>,
970 CS1: CommitmentScheme<C1>,
971 CS2: CommitmentScheme<C2>,
972 <C1 as CurveGroup>::BaseField: PrimeField,
973 <C2 as CurveGroup>::BaseField: PrimeField,
974 <C1 as Group>::ScalarField: Absorb,
975 <C2 as Group>::ScalarField: Absorb,
976 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
977 for<'a> &'a GC1: GroupOpsBounds<'a, C1, GC1>,
978 for<'a> &'a GC2: GroupOpsBounds<'a, C2, GC2>,
979{
980 // folds the given cyclefold circuit and its instances
981 #[allow(clippy::type_complexity)]
982 fn fold_cyclefold_circuit(
983 &self,
984 transcript: &mut PoseidonSponge<C1::ScalarField>,
985 cf_W_i: CycleFoldWitness<C2>, // witness of the running instance
986 cf_U_i: CycleFoldCommittedInstance<C2>, // running instance
987 cf_u_i_x: Vec<C2::ScalarField>,
988 cf_circuit: ProtoGalaxyCycleFoldCircuit<C1, GC1>,
989 rng: &mut impl RngCore,
990 ) -> Result<
991 (
992 CycleFoldWitness<C2>,
993 CycleFoldCommittedInstance<C2>, // u_i
994 CycleFoldWitness<C2>, // W_i1
995 CycleFoldCommittedInstance<C2>, // U_i1
996 C2, // cmT
997 C2::ScalarField, // r_Fq
998 ),
999 Error,
1000 > {
1001 fold_cyclefold_circuit::<ProtoGalaxyCycleFoldConfig<C1>, C1, GC1, C2, GC2, CS2, false>(
1002 transcript,
1003 self.cf_r1cs.clone(),
1004 self.cf_cs_params.clone(),
1005 self.pp_hash,
1006 cf_W_i,
1007 cf_U_i,
1008 cf_u_i_x,
1009 cf_circuit,
1010 rng,
1011 )
1012 }
1013}
1014
1015#[cfg(test)]
1016mod tests {
1017 use super::*;
1018
1019 use ark_bn254::{constraints::GVar, Bn254, Fr, G1Projective as Projective};
1020 use ark_grumpkin::{constraints::GVar as GVar2, Projective as Projective2};
1021 use ark_std::test_rng;
1022 use rayon::prelude::*;
1023
1024 use crate::{
1025 commitment::{kzg::KZG, pedersen::Pedersen},
1026 frontend::utils::CubicFCircuit,
1027 transcript::poseidon::poseidon_canonical_config,
1028 };
1029
1030 /// This test tests the ProtoGalaxy+CycleFold IVC, and by consequence it is
1031 /// also testing the AugmentedFCircuit
1032 #[test]
1033 fn test_ivc() {
1034 let poseidon_config = poseidon_canonical_config::<Fr>();
1035
1036 let F_circuit = CubicFCircuit::<Fr>::new(()).unwrap();
1037
1038 // run the test using Pedersen commitments on both sides of the curve cycle
1039 test_ivc_opt::<Pedersen<Projective>, Pedersen<Projective2>>(
1040 poseidon_config.clone(),
1041 F_circuit,
1042 );
1043 // run the test using KZG for the commitments on the main curve, and Pedersen for the
1044 // commitments on the secondary curve
1045 test_ivc_opt::<KZG<Bn254>, Pedersen<Projective2>>(poseidon_config, F_circuit);
1046 }
1047
1048 // test_ivc allowing to choose the CommitmentSchemes
1049 fn test_ivc_opt<CS1: CommitmentScheme<Projective>, CS2: CommitmentScheme<Projective2>>(
1050 poseidon_config: PoseidonConfig<Fr>,
1051 F_circuit: CubicFCircuit<Fr>,
1052 ) {
1053 type PG<CS1, CS2> =
1054 ProtoGalaxy<Projective, GVar, Projective2, GVar2, CubicFCircuit<Fr>, CS1, CS2>;
1055
1056 let params =
1057 PG::<CS1, CS2>::preprocess(&mut test_rng(), &(poseidon_config, F_circuit)).unwrap();
1058
1059 let z_0 = vec![Fr::from(3_u32)];
1060 let mut protogalaxy = PG::init(¶ms, F_circuit, z_0.clone()).unwrap();
1061
1062 let num_steps: usize = 3;
1063 for _ in 0..num_steps {
1064 protogalaxy
1065 .prove_step(&mut test_rng(), vec![], None)
1066 .unwrap();
1067 }
1068 assert_eq!(Fr::from(num_steps as u32), protogalaxy.i);
1069
1070 let (running_instance, incoming_instance, cyclefold_instance) = protogalaxy.instances();
1071 PG::<CS1, CS2>::verify(
1072 params.1,
1073 z_0,
1074 protogalaxy.z_i,
1075 protogalaxy.i,
1076 running_instance,
1077 incoming_instance,
1078 cyclefold_instance,
1079 )
1080 .unwrap();
1081 }
1082
1083 #[ignore]
1084 #[test]
1085 fn test_t_bounds() {
1086 let d = 2;
1087 let k = 1;
1088
1089 let poseidon_config = poseidon_canonical_config::<Fr>();
1090 for state_len in [1, 10, 100] {
1091 for external_inputs_len in [1, 10, 100] {
1092 let dummy_circuit: DummyCircuit =
1093 FCircuit::<Fr>::new((state_len, external_inputs_len)).unwrap();
1094
1095 let costs = (1..32)
1096 .into_par_iter()
1097 .map(|t| {
1098 let cs = ConstraintSystem::<Fr>::new_ref();
1099 AugmentedFCircuit::<Projective, Projective2, GVar2, DummyCircuit>::empty(
1100 &poseidon_config,
1101 dummy_circuit.clone(),
1102 t,
1103 d,
1104 k,
1105 )
1106 .generate_constraints(cs.clone())
1107 .unwrap();
1108 cs.num_constraints()
1109 })
1110 .collect::<Vec<_>>();
1111
1112 for t_lower_bound in log2(costs[0]) as usize..32 {
1113 let num_constraints =
1114 (1 << t_lower_bound) - costs[0] + costs[t_lower_bound - 1];
1115 let t = log2(num_constraints) as usize;
1116 assert!(t == t_lower_bound || t == t_lower_bound + 1);
1117 }
1118 }
1119 }
1120 }
1121}