sonobe_fs/
lib.rs

1#![warn(missing_docs)]
2
3//! Folding scheme definition and implementations.
4//!
5//! This crate provides the traits for folding schemes, the out-of-circuit
6//! widgets and the in-circuit gadgets of their algorithms, and their associated
7//! structures (such as keys, instances, and witnesses) in [`definitions`].
8//!
9//! Concrete constructions of the following folding schemes are then implemented
10//! as submodules:
11//! - [`Nova`](nova)
12//!
13//! Each scheme module mirrors the same directory layout:
14//! - `algorithms/`: Implementations for the following algorithms:
15//!     - Preprocessing/Setup: [`FoldingSchemePreprocessor`]
16//!     - Key generation: [`FoldingSchemeKeyGenerator`]
17//!     - Proof generation: [`FoldingSchemeProver`]
18//!     - Proof verification: [`FoldingSchemeVerifier`]
19//! - `circuits/`: In-circuit (partial / full) gadgets, mainly for verification.
20//! - `instances/`: Instance types.
21//! - `keys/`: Key types.
22//! - `witnesses/`: Witness types.
23//!
24//! # Example
25//!
26//! Aggregating independent claims about solutions to an equation into a single
27//! accumulator.
28//!
29//! This example is also runnable with
30//! `cargo run --release --example aggregate_solutions`.
31#![doc = concat!("```\n", include_str!("../examples/aggregate_solutions.rs"), "```")]
32
33pub mod definitions;
34pub mod nova;
35
36pub use self::definitions::{
37    FoldingSchemeDef, FoldingSchemeDefGadget,
38    algorithms::{
39        FoldingSchemeDecider, FoldingSchemeKeyGenerator, FoldingSchemeOps,
40        FoldingSchemePreprocessor, FoldingSchemeProver, FoldingSchemeVerifier,
41    },
42    circuits::{FoldingSchemeFullVerifierGadget, FoldingSchemePartialVerifierGadget},
43    errors::Error,
44    instances::{FoldingInstance, FoldingInstanceVar, PlainInstance, PlainInstanceVar},
45    keys::DeciderKey,
46    utils::TaggedVec,
47    variants::{
48        GroupBasedFoldingSchemePrimary, GroupBasedFoldingSchemePrimaryDef,
49        GroupBasedFoldingSchemeSecondary, GroupBasedFoldingSchemeSecondaryDef,
50    },
51    witnesses::{FoldingWitness, FoldingWitnessVar, PlainWitness, PlainWitnessVar},
52};
53
54#[cfg(test)]
55mod tests {
56    use ark_relations::gr1cs::{ConstraintSynthesizer, ConstraintSystem};
57    use ark_std::{error::Error, rand::Rng, sync::Arc};
58    use sonobe_primitives::{
59        circuits::{ArithExtractor, AssignmentsOwned},
60        commitments::CommitmentDef,
61        relations::WitnessInstanceSampler,
62        transcripts::{
63            Transcript,
64            griffin::{GriffinParams, sponge::GriffinSponge},
65        },
66    };
67
68    use super::*;
69
70    #[allow(non_snake_case)]
71    pub fn test_folding_scheme<FS: FoldingSchemeOps<M, N>, const M: usize, const N: usize>(
72        config: FS::Config,
73        circuit: impl ConstraintSynthesizer<<FS::CM as CommitmentDef>::Scalar>,
74        assignments_vec: Vec<AssignmentsOwned<<FS::CM as CommitmentDef>::Scalar>>,
75        mut rng: impl Rng,
76    ) -> Result<(), Box<dyn Error>>
77    where
78        FS::Arith: From<ConstraintSystem<<FS::CM as CommitmentDef>::Scalar>>,
79    {
80        let pp = FS::preprocess(config, &mut rng)?;
81
82        let cs = ArithExtractor::new();
83        cs.execute_synthesizer(circuit)?;
84        let arith = cs.arith()?;
85        let dk = FS::generate_keys(pp, arith)?;
86        let pk = dk.to_pk();
87        let vk = dk.to_vk();
88
89        let mut Ws = vec![];
90        let mut Us = vec![];
91        for _ in 0..M {
92            let (W, U) = WitnessInstanceSampler::<FS::RW, FS::RU>::sample(&dk, (), &mut rng)?;
93            FS::decide_running(&dk, &W, &U)?;
94            Ws.push(W);
95            Us.push(U);
96        }
97        let mut Ws = Ws.try_into().unwrap();
98        let mut Us = Us.try_into().unwrap();
99
100        let config = Arc::new(GriffinParams::new(16, 5, 9));
101
102        let mut transcript_p = GriffinSponge::new(config.clone());
103        let mut transcript_v = GriffinSponge::new(config);
104
105        for assignments in assignments_vec {
106            let mut ws = vec![];
107            let mut us = vec![];
108            for _ in 0..N {
109                let (w, u) = WitnessInstanceSampler::<FS::IW, FS::IU>::sample(
110                    &dk,
111                    assignments.clone(),
112                    &mut rng,
113                )?;
114                FS::decide_incoming(&dk, &w, &u)?;
115                ws.push(w);
116                us.push(u);
117            }
118            let ws = ws.try_into().unwrap();
119            let us = us.try_into().unwrap();
120
121            let (WW, UU, pi) = FS::prove(pk, &mut transcript_p, &Ws, &Us, &ws, &us, &mut rng)?;
122            FS::decide_running(&dk, &WW, &UU)?;
123            assert_eq!(FS::verify(vk, &mut transcript_v, &Us, &us, &pi)?, UU);
124
125            for i in 0..M {
126                let (W, U) = WitnessInstanceSampler::<FS::RW, FS::RU>::sample(&dk, (), &mut rng)?;
127                FS::decide_running(&dk, &W, &U)?;
128                Ws[i] = W;
129                Us[i] = U;
130            }
131            if M != 0 {
132                let idx = rng.gen_range(0..M);
133                Ws[idx] = WW;
134                Us[idx] = UU;
135            }
136        }
137
138        Ok(())
139    }
140}
sonobe_fs/lib.rs

sonobe_fs/
lib.rs
