sonobe-fs 0.1.0-alpha.1

//! Shared traits for folding schemes, including definitions of related
//! cryptographic objects and algorithms in and out of circuit.

pub mod algorithms;
pub mod circuits;
pub mod errors;
pub mod instances;
pub mod keys;
pub mod utils;
pub mod variants;
pub mod witnesses;

use ark_r1cs_std::{GR1CSVar, alloc::AllocVar};
use sonobe_primitives::{
    arithmetizations::{Arith, ArithConfig},
    circuits::AssignmentsOwned,
    commitments::{CommitmentDef, CommitmentDefGadget},
    relations::{Relation, WitnessInstanceSampler},
    traits::{Dummy, SonobeField},
};

use self::{
    errors::Error,
    instances::{FoldingInstance, FoldingInstanceVar},
    keys::DeciderKey,
    witnesses::FoldingWitness,
};

/// [`FoldingSchemeDef`] provides the core type definitions of a folding scheme.
///
/// A folding scheme is a cryptographic primitive that folds multiple instances
/// of computations into a single instance while preserving the validity of the
/// computations.
/// More specifically, a folding scheme in general considers two relations `R1`
/// and `R2`.
/// The folding prover folds `M` witness-instance pairs satisfying `R1` and `N`
/// witness-instance pairs satisfying `R2` into a single witness-instance pair
/// satisfying `R1`, along with a proof that the folding was done correctly.
/// The folding verifier folds `M` instances of `R1` and `N` instances of `R2`
/// into a single instance of `R1` under the help of the proof.
///
/// While folding schemes can be applied in various contexts, we primarily focus
/// on their use in constructing recursive proof systems, and thus we refer to
/// `R1` as the "running relation" and `R2` as the "incoming relation" in the
/// codebase.
/// A witness-instance pair `(W, U)` of type `(RW, RU)` for `R1` is called a
/// "running" witness-instance pair, while a witness-instance pair `(w, u)` of
/// type `(IW, IU)` for `R2` is called an "incoming" witness-instance pair.
///
/// Different folding schemes support different running and incoming relations,
/// as well as the number of witness-instance pairs that can be folded at once.
pub trait FoldingSchemeDef {
    /// [`FoldingSchemeDef::CM`] is the commitment scheme used by the folding
    /// scheme.
    type CM: CommitmentDef<Scalar: SonobeField>;
    /// [`FoldingSchemeDef::RW`] is the type of running witness.
    type RW: FoldingWitness<Self::CM>;
    /// [`FoldingSchemeDef::RU`] is the type of running instance.
    type RU: FoldingInstance<Self::CM>;
    /// [`FoldingSchemeDef::IW`] is the type of incoming witness.
    type IW: FoldingWitness<Self::CM>;
    /// [`FoldingSchemeDef::IU`] is the type of incoming instance.
    type IU: FoldingInstance<Self::CM>;
    /// [`FoldingSchemeDef::TranscriptField`] is the field type used in the
    /// transcript of the folding scheme.
    type TranscriptField: SonobeField;
    /// [`FoldingSchemeDef::Arith`] is the constraint system supported by the
    /// folding scheme.
    type Arith: Arith;
    /// [`FoldingSchemeDef::Config`] is the type of configuration required to
    /// generate the public parameters of the folding scheme.
    type Config;
    /// [`FoldingSchemeDef::PublicParam`] is the type of public parameters of
    /// the folding scheme.
    type PublicParam;
    /// [`FoldingSchemeDef::DeciderKey`] is the type of decider key of the
    /// folding scheme, which is used to determine the satisfiability of a
    /// witness-instance pair.
    type DeciderKey: DeciderKey
        + Clone
        + Relation<Self::RW, Self::RU, Error = Error>
        + Relation<Self::IW, Self::IU, Error = Error>
        + WitnessInstanceSampler<Self::RW, Self::RU, Source = (), Error = Error>
        + WitnessInstanceSampler<
            Self::IW,
            Self::IU,
            Source = AssignmentsOwned<<Self::CM as CommitmentDef>::Scalar>,
            Error = Error,
        >;
    /// [`FoldingSchemeDef::Challenge`] is the type of challenge generated
    /// during the folding process.
    type Challenge;
    /// [`FoldingSchemeDef::Proof`] is the type of proof generated by the
    /// folding prover.
    type Proof<const M: usize, const N: usize>: Clone + for<'a> Dummy<&'a ArithConfig>;
}

/// [`FoldingSchemeDefGadget`] specifies the in-circuit associated types for a
/// folding scheme gadget.
pub trait FoldingSchemeDefGadget {
    /// [`FoldingSchemeDefGadget::Widget`] points to the out-of-circuit folding
    /// scheme widget.
    type Widget: FoldingSchemeDef;

    /// [`FoldingSchemeDefGadget::CM`] is the commitment scheme gadget.
    type CM: CommitmentDefGadget<Widget = <Self::Widget as FoldingSchemeDef>::CM>;
    /// [`FoldingSchemeDefGadget::RU`] is the type of in-circuit running
    /// instance variable.
    type RU: FoldingInstanceVar<Self::CM, Value = <Self::Widget as FoldingSchemeDef>::RU>;
    /// [`FoldingSchemeDefGadget::IU`] is the type of in-circuit incoming
    /// instance variable.
    type IU: FoldingInstanceVar<Self::CM, Value = <Self::Widget as FoldingSchemeDef>::IU>;

    /// [`FoldingSchemeDefGadget::VerifierKey`] is the type of in-circuit
    /// verifier key variable.
    type VerifierKey;

    /// [`FoldingSchemeDefGadget::Challenge`] is the type of in-circuit
    /// challenge variable.
    type Challenge: AllocVar<
            <Self::Widget as FoldingSchemeDef>::Challenge,
            <Self::CM as CommitmentDefGadget>::ConstraintField,
        > + GR1CSVar<
            <Self::CM as CommitmentDefGadget>::ConstraintField,
            Value = <Self::Widget as FoldingSchemeDef>::Challenge,
        >;
    /// [`FoldingSchemeDefGadget::Proof`] is the type of in-circuit proof
    /// variable.
    type Proof<const M: usize, const N: usize>: AllocVar<
            <Self::Widget as FoldingSchemeDef>::Proof<M, N>,
            <Self::CM as CommitmentDefGadget>::ConstraintField,
        > + GR1CSVar<
            <Self::CM as CommitmentDefGadget>::ConstraintField,
            Value = <Self::Widget as FoldingSchemeDef>::Proof<M, N>,
        >;
}