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