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