sonobe_fs/definitions/
algorithms.rs

1//! Traits that define out-of-circuit widgets for folding scheme algorithms
2//! (preprocessing, key generation, proof generation, proof verification, and
3//! deciding).
4
5use ark_std::{borrow::Borrow, rand::RngCore};
6use sonobe_primitives::{relations::Relation, transcripts::Transcript};
7
8use super::{FoldingSchemeDef, errors::Error, keys::DeciderKey};
9
10/// [`FoldingSchemePreprocessor`] is the trait for folding scheme preprocessor.
11pub trait FoldingSchemePreprocessor: FoldingSchemeDef {
12    /// [`FoldingSchemePreprocessor::preprocess`] defines the preprocessing
13    /// algorithm, which is a randomized algorithm that takes as input the
14    /// config / parameterization `config` of the folding scheme (e.g., size
15    /// bounds of the folding scheme) and outputs the public parameters.
16    ///
17    /// Here, the randomness source is controlled by `rng`.
18    ///
19    /// The security parameter is implicitly specified by the size of underlying
20    /// fields and groups.
21    fn preprocess(config: Self::Config, rng: impl RngCore) -> Result<Self::PublicParam, Error>;
22}
23
24/// [`FoldingSchemeKeyGenerator`] is the trait for folding scheme key generator.
25pub trait FoldingSchemeKeyGenerator: FoldingSchemeDef {
26    /// [`FoldingSchemeKeyGenerator::generate_keys`] defines the key generation
27    /// algorithm, which is a deterministic algorithm that takes as input the
28    /// public parameters `pp` and the arithmetization `arith`, and outputs a
29    /// prover key and a verifier key.
30    fn generate_keys(pp: Self::PublicParam, arith: Self::Arith) -> Result<Self::DeciderKey, Error>;
31}
32
33/// [`FoldingSchemeProver`] is the trait for folding scheme prover.
34pub trait FoldingSchemeProver<const M: usize, const N: usize>: FoldingSchemeDef {
35    /// [`FoldingSchemeProver::prove`] defines the proof generation algorithm,
36    /// which is a (probably) randomized algorithm that takes as input the
37    /// prover key `pk`, the transcript `transcript` between the prover and the
38    /// verifier, `M` running witnesses `Ws`, `M` running instances `Us`, `N`
39    /// incoming witnesses `ws`, and `N` incoming instances `us`, and outputs
40    /// the folded witness and instance, the proof, and the challenges.
41    ///
42    /// Here, although the challenges can usually be derived by `transcript` and
43    /// thus do not necessarily need to be returned for verification, we still
44    /// have the prover return them explicitly so that they can be used for the
45    /// construction of CycleFold circuits in our CycleFold-based folding-to-IVC
46    /// compiler without re-deriving them from the transcript.
47    ///
48    /// The prover may further use `rng` as the randomness source, e.g., for
49    /// the hiding/zero-knowledge property.
50    #[allow(non_snake_case, clippy::type_complexity)]
51    fn prove(
52        pk: &<Self::DeciderKey as DeciderKey>::ProverKey,
53        transcript: &mut impl Transcript<Self::TranscriptField>,
54        Ws: &[impl Borrow<Self::RW>; M],
55        Us: &[impl Borrow<Self::RU>; M],
56        ws: &[impl Borrow<Self::IW>; N],
57        us: &[impl Borrow<Self::IU>; N],
58        rng: impl RngCore,
59    ) -> Result<(Self::RW, Self::RU, Self::Proof<M, N>), Error>;
60}
61
62/// [`FoldingSchemeVerifier`] is the trait for folding scheme verifier.
63pub trait FoldingSchemeVerifier<const M: usize, const N: usize>: FoldingSchemeDef {
64    /// [`FoldingSchemeVerifier::verify`] defines the proof verification
65    /// algorithm, which is a deterministic algorithm that takes as input the
66    /// verifier key `vk`, the transcript `transcript` between the prover and
67    /// the verifier, `M` running instances `Us`, `N` incoming instances `us`,
68    /// and the proof `proof`, and outputs the folded instance.
69    #[allow(non_snake_case)]
70    fn verify(
71        vk: &<Self::DeciderKey as DeciderKey>::VerifierKey,
72        transcript: &mut impl Transcript<Self::TranscriptField>,
73        Us: &[impl Borrow<Self::RU>; M],
74        us: &[impl Borrow<Self::IU>; N],
75        proof: &Self::Proof<M, N>,
76    ) -> Result<Self::RU, Error>;
77}
78
79/// [`FoldingSchemeDecider`] is the trait for folding scheme decider.
80pub trait FoldingSchemeDecider: FoldingSchemeDef {
81    /// [`FoldingSchemeDecider::decide_running`] defines the deciding algorithm
82    /// for running witness-instance pairs, which is a deterministic algorithm
83    /// that takes as input the decider key `dk`, a running witness `W` and a
84    /// running instance `U`, and outputs whether the witness-instance pair
85    /// satisfies the running relation.
86    #[allow(non_snake_case)]
87    fn decide_running(dk: &Self::DeciderKey, W: &Self::RW, U: &Self::RU) -> Result<(), Error> {
88        Relation::<Self::RW, Self::RU>::check_relation(dk, W, U)
89    }
90
91    /// [`FoldingSchemeDecider::decide_running`] defines the deciding algorithm
92    /// for incoming witness-instance pairs, which is a deterministic algorithm
93    /// that takes as input the decider key `dk`, an incoming witness `W` and an
94    /// incoming instance `U`, and outputs whether the witness-instance pair
95    /// satisfies the incoming relation.
96    fn decide_incoming(dk: &Self::DeciderKey, w: &Self::IW, u: &Self::IU) -> Result<(), Error> {
97        Relation::<Self::IW, Self::IU>::check_relation(dk, w, u)
98    }
99}
100
101impl<FS: FoldingSchemeDef> FoldingSchemeDecider for FS {}
102
103/// [`FoldingSchemeOps`] is a convenience super-trait bundling all algorithms.
104pub trait FoldingSchemeOps<const M: usize, const N: usize>:
105    FoldingSchemePreprocessor
106    + FoldingSchemeKeyGenerator
107    + FoldingSchemeProver<M, N>
108    + FoldingSchemeVerifier<M, N>
109    + FoldingSchemeDecider
110{
111}
112
113impl<FS, const M: usize, const N: usize> FoldingSchemeOps<M, N> for FS where
114    FS: FoldingSchemePreprocessor
115        + FoldingSchemeKeyGenerator
116        + FoldingSchemeProver<M, N>
117        + FoldingSchemeVerifier<M, N>
118        + FoldingSchemeDecider
119{
120}
sonobe_fs/definitions/algorithms.rs

sonobe_fs/definitions/
algorithms.rs
