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