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