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