sonobe/folding-schemes/src/lib.rs
folding-schemes/src/lib.rsRaw
1#![allow(non_snake_case)]
2#![allow(non_upper_case_globals)]
3#![allow(non_camel_case_types)]
4#![allow(clippy::upper_case_acronyms)]
5
6use ark_ec::{pairing::Pairing, CurveGroup};
7use ark_ff::PrimeField;
8use ark_std::rand::CryptoRng;
9use ark_std::{fmt::Debug, rand::RngCore};
10use thiserror::Error;
11
12use crate::frontend::FCircuit;
13
14pub mod ccs;
15pub mod commitment;
16pub mod constants;
17pub mod folding;
18pub mod frontend;
19pub mod transcript;
20pub mod utils;
21
22#[derive(Debug, Error)]
23pub enum Error {
24 // Wrappers on top of other errors
25 #[error("ark_relations::r1cs::SynthesisError")]
26 SynthesisError(#[from] ark_relations::r1cs::SynthesisError),
27 #[error("ark_serialize::SerializationError")]
28 SerializationError(#[from] ark_serialize::SerializationError),
29 #[error("ark_poly_commit::Error")]
30 PolyCommitError(#[from] ark_poly_commit::Error),
31 #[error("crate::utils::espresso::virtual_polynomial::ArithErrors")]
32 ArithError(#[from] utils::espresso::virtual_polynomial::ArithErrors),
33 #[error(transparent)]
34 ProtoGalaxy(folding::protogalaxy::ProtoGalaxyError),
35 #[error("std::io::Error")]
36 IOError(#[from] std::io::Error),
37
38 // Relation errors
39 #[error("Relation not satisfied")]
40 NotSatisfied,
41 #[error("SNARK verification failed")]
42 SNARKVerificationFail,
43 #[error("IVC verification failed")]
44 IVCVerificationFail,
45 #[error("R1CS instance is expected to not be relaxed")]
46 R1CSUnrelaxedFail,
47 #[error("Could not find the inner ConstraintSystem")]
48 NoInnerConstraintSystem,
49 #[error("Sum-check prove failed: {0}")]
50 SumCheckProveError(String),
51 #[error("Sum-check verify failed: {0}")]
52 SumCheckVerifyError(String),
53
54 // Comparators errors
55 #[error("Not equal")]
56 NotEqual,
57 #[error("Vectors should have the same length ({0}: {1}, {2}: {3})")]
58 NotSameLength(String, usize, String, usize),
59 #[error("Vector's length ({0}) is not the expected ({1})")]
60 NotExpectedLength(usize, usize),
61 #[error("Vector ({0}) length ({1}) is not a power of two")]
62 NotPowerOfTwo(String, usize),
63 #[error("Can not be empty")]
64 Empty,
65 #[error("Value out of bounds")]
66 OutOfBounds,
67 #[error("Could not construct the Evaluation Domain")]
68 NewDomainFail,
69 #[error("The number of folded steps must be greater than 1")]
70 NotEnoughSteps,
71 #[error("Evaluation failed")]
72 EvaluationFail,
73
74 // Commitment errors
75 #[error("Pedersen parameters length is not sufficient (generators.len={0} < vector.len={1} unsatisfied)")]
76 PedersenParamsLen(usize, usize),
77 #[error("Blinding factor not 0 for Commitment without hiding")]
78 BlindingNotZero,
79 #[error("Commitment verification failed")]
80 CommitmentVerificationFail,
81
82 // Other
83 #[error("{0}")]
84 Other(String),
85 #[error("Randomness for blinding not found")]
86 MissingRandomness,
87 #[error("Missing value: {0}")]
88 MissingValue(String),
89 #[error("Feature '{0}' not supported yet")]
90 NotSupportedYet(String),
91 #[error("Feature '{0}' is not supported and it will not be")]
92 NotSupported(String),
93 #[error("max i-th step reached (usize limit reached)")]
94 MaxStep,
95 #[error("Circom Witness calculation error: {0}")]
96 WitnessCalculationError(String),
97 #[error("BigInt to PrimeField conversion error: {0}")]
98 BigIntConversionError(String),
99}
100
101/// FoldingScheme defines trait that is implemented by the diverse folding schemes. It is defined
102/// over a cycle of curves (C1, C2), where:
103/// - C1 is the main curve, which ScalarField we use as our F for all the field operations
104/// - C2 is the auxiliary curve, which we use for the commitments, whose BaseField (for point
105/// coordinates) are in the C1::ScalarField.
106/// In other words, C1.Fq == C2.Fr, and C1.Fr == C2.Fq.
107pub trait FoldingScheme<C1: CurveGroup, C2: CurveGroup, FC>: Clone + Debug
108where
109 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
110 C2::BaseField: PrimeField,
111 FC: FCircuit<C1::ScalarField>,
112{
113 type PreprocessorParam: Debug;
114 type ProverParam: Debug;
115 type VerifierParam: Debug;
116 type CommittedInstanceWithWitness: Debug;
117 type CFCommittedInstanceWithWitness: Debug; // CycleFold CommittedInstance & Witness
118
119 fn preprocess(
120 prep_param: &Self::PreprocessorParam,
121 ) -> Result<(Self::ProverParam, Self::VerifierParam), Error>;
122
123 fn init(
124 pp: &Self::ProverParam,
125 step_circuit: FC,
126 z_0: Vec<C1::ScalarField>, // initial state
127 ) -> Result<Self, Error>;
128
129 fn prove_step(&mut self, external_inputs: Vec<C1::ScalarField>) -> Result<(), Error>;
130
131 // returns the state at the current step
132 fn state(&self) -> Vec<C1::ScalarField>;
133
134 // returns the instances at the current step, in the following order:
135 // (running_instance, incoming_instance, cyclefold_instance)
136 fn instances(
137 &self,
138 ) -> (
139 Self::CommittedInstanceWithWitness,
140 Self::CommittedInstanceWithWitness,
141 Self::CFCommittedInstanceWithWitness,
142 );
143
144 fn verify(
145 vp: Self::VerifierParam,
146 z_0: Vec<C1::ScalarField>, // initial state
147 z_i: Vec<C1::ScalarField>, // last state
148 // number of steps between the initial state and the last state
149 num_steps: C1::ScalarField,
150 running_instance: Self::CommittedInstanceWithWitness,
151 incoming_instance: Self::CommittedInstanceWithWitness,
152 cyclefold_instance: Self::CFCommittedInstanceWithWitness,
153 ) -> Result<(), Error>;
154}
155
156pub trait Decider<
157 C1: CurveGroup,
158 C2: CurveGroup,
159 FC: FCircuit<C1::ScalarField>,
160 FS: FoldingScheme<C1, C2, FC>,
161> where
162 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
163 C2::BaseField: PrimeField,
164{
165 type ProverParam: Clone;
166 type Proof;
167 type VerifierParam;
168 type PublicInput: Debug;
169 type CommittedInstanceWithWitness: Debug;
170 type CommittedInstance: Clone + Debug;
171
172 fn prove(
173 pp: Self::ProverParam,
174 rng: impl RngCore + CryptoRng,
175 folding_scheme: FS,
176 ) -> Result<Self::Proof, Error>;
177
178 fn verify(
179 vp: Self::VerifierParam,
180 i: C1::ScalarField,
181 z_0: Vec<C1::ScalarField>,
182 z_i: Vec<C1::ScalarField>,
183 running_instance: &Self::CommittedInstance,
184 incoming_instance: &Self::CommittedInstance,
185 proof: &Self::Proof,
186 // returns `Result<bool, Error>` to differentiate between an error occurred while performing
187 // the verification steps, and the verification logic of the scheme not passing.
188 ) -> Result<bool, Error>;
189}
190
191/// DeciderOnchain extends the Decider into preparing the calldata
192pub trait DeciderOnchain<E: Pairing, C1: CurveGroup, C2: CurveGroup>
193where
194 C1: CurveGroup<BaseField = C2::ScalarField, ScalarField = C2::BaseField>,
195 C2::BaseField: PrimeField,
196{
197 type Proof;
198 type CommittedInstance: Clone + Debug;
199
200 fn prepare_calldata(
201 i: C1::ScalarField,
202 z_0: Vec<C1::ScalarField>,
203 z_i: Vec<C1::ScalarField>,
204 running_instance: &Self::CommittedInstance,
205 incoming_instance: &Self::CommittedInstance,
206 proof: Self::Proof,
207 ) -> Result<Vec<u8>, Error>;
208}