sonobe_fs/nova/
mod.rs

1//! This module implements the Nova folding scheme, which is introduced in this
2//! [paper].
3//!
4//! [paper]: https://eprint.iacr.org/2021/370.pdf
5
6use ark_r1cs_std::boolean::Boolean;
7use ark_std::marker::PhantomData;
8use sonobe_primitives::{
9    arithmetizations::r1cs::R1CS,
10    commitments::{CommitmentDef, CommitmentDefGadget, GroupBasedCommitment},
11    traits::{CF2, SonobeField},
12};
13
14use self::{
15    instances::{
16        IncomingInstance as IU, RunningInstance as RU,
17        circuits::{IncomingInstanceVar as IUVar, RunningInstanceVar as RUVar},
18    },
19    witnesses::{IncomingWitness as IW, RunningWitness as RW},
20};
21use crate::{
22    FoldingSchemeDef, FoldingSchemeDefGadget, GroupBasedFoldingSchemePrimaryDef,
23    GroupBasedFoldingSchemeSecondaryDef, nova::keys::NovaKey,
24};
25
26pub mod algorithms;
27pub mod circuits;
28pub mod instances;
29pub mod keys;
30pub mod witnesses;
31
32// used for the RO challenges.
33// From [Srinath Setty](https://microsoft.com/en-us/research/people/srinath/): In Nova, soundness
34// error ≤ 2/|S|, where S is the subset of the field F from which the challenges are drawn. In this
35// case, we keep the size of S close to 2^128.
36/// [`AbstractNova`] implements the Nova folding scheme which can operate on
37/// both the primary and secondary curves.
38pub struct AbstractNova<CM, TF, const CHALLENGE_BITS: usize = 128> {
39    _t: PhantomData<(CM, TF)>,
40}
41
42/// [`Nova`] is the main Nova folding scheme on the primary curve.
43pub type Nova<CM, const CHALLENGE_BITS: usize = 128> =
44    AbstractNova<CM, <CM as CommitmentDef>::Scalar, CHALLENGE_BITS>;
45
46/// [`CycleFoldNova`] is the Nova folding scheme on the secondary curve which
47/// can be used as the folding scheme for folding CycleFold instances.
48pub type CycleFoldNova<CM, const CHALLENGE_BITS: usize = 128> =
49    AbstractNova<CM, CF2<<CM as CommitmentDef>::Commitment>, CHALLENGE_BITS>;
50
51impl<CM: GroupBasedCommitment, TF: SonobeField, const CHALLENGE_BITS: usize> FoldingSchemeDef
52    for AbstractNova<CM, TF, CHALLENGE_BITS>
53{
54    type CM = CM;
55    type RW = RW<CM>;
56    type RU = RU<CM>;
57    type IW = IW<CM>;
58    type IU = IU<CM>;
59
60    type TranscriptField = TF;
61    type Arith = R1CS<CM::Scalar>;
62
63    type Config = usize;
64    type PublicParam = CM::Key;
65    type DeciderKey = NovaKey<Self::Arith, CM>;
66    type Challenge = [bool; CHALLENGE_BITS];
67    type Proof<const M: usize, const N: usize> = CM::Commitment;
68}
69
70/// [`AbstractNovaGadget`] is the in-circuit gadget for [`AbstractNova`].
71pub struct AbstractNovaGadget<CM, const CHALLENGE_BITS: usize = 128> {
72    _vc: PhantomData<CM>,
73}
74
75impl<CM, const CHALLENGE_BITS: usize> FoldingSchemeDefGadget
76    for AbstractNovaGadget<CM, CHALLENGE_BITS>
77where
78    CM: CommitmentDefGadget<Widget: GroupBasedCommitment>,
79{
80    type Widget = AbstractNova<CM::Widget, CM::ConstraintField, CHALLENGE_BITS>;
81
82    type CM = CM;
83    type RU = RUVar<CM>;
84    type IU = IUVar<CM>;
85    type VerifierKey = ();
86    type Challenge = [Boolean<CM::ConstraintField>; CHALLENGE_BITS];
87    type Proof<const M: usize, const N: usize> = CM::CommitmentVar;
88}
89
90impl<CM: GroupBasedCommitment, const CHALLENGE_BITS: usize> GroupBasedFoldingSchemePrimaryDef
91    for AbstractNova<CM, CM::Scalar, CHALLENGE_BITS>
92{
93    type Gadget = AbstractNovaGadget<CM::Gadget2, CHALLENGE_BITS>;
94}
95
96impl<CM: GroupBasedCommitment, const CHALLENGE_BITS: usize> GroupBasedFoldingSchemeSecondaryDef
97    for AbstractNova<CM, CF2<CM::Commitment>, CHALLENGE_BITS>
98{
99    type Gadget = AbstractNovaGadget<CM::Gadget1, CHALLENGE_BITS>;
100}
101
102#[cfg(test)]
103mod tests {
104    use ark_bn254::{Fq, Fr, G1Projective};
105    use ark_ff::UniformRand;
106    use ark_std::{
107        error::Error,
108        rand::{RngCore, thread_rng},
109    };
110    use sonobe_primitives::{
111        circuits::utils::{CircuitForTest, satisfying_assignments_for_test},
112        commitments::pedersen::Pedersen,
113    };
114    #[cfg(all(target_arch = "wasm32", target_os = "unknown"))]
115    use wasm_bindgen_test::wasm_bindgen_test as test;
116
117    use super::*;
118    use crate::tests::test_folding_scheme;
119
120    fn test_nova_opt<TF: SonobeField>(
121        rounds: usize,
122        mut rng: impl RngCore,
123    ) -> Result<(), Box<dyn Error>> {
124        test_folding_scheme::<AbstractNova<Pedersen<G1Projective, true>, TF>, 1, 1>(
125            8,
126            CircuitForTest {
127                x: Fr::rand(&mut rng),
128            },
129            (0..rounds)
130                .map(|_| satisfying_assignments_for_test(Fr::rand(&mut rng)))
131                .collect(),
132            &mut rng,
133        )?;
134
135        test_folding_scheme::<AbstractNova<Pedersen<G1Projective, false>, TF>, 1, 1>(
136            8,
137            CircuitForTest {
138                x: Fr::rand(&mut rng),
139            },
140            (0..rounds)
141                .map(|_| satisfying_assignments_for_test(Fr::rand(&mut rng)))
142                .collect(),
143            &mut rng,
144        )?;
145
146        test_folding_scheme::<AbstractNova<Pedersen<G1Projective, true>, TF>, 2, 0>(
147            8,
148            CircuitForTest {
149                x: Fr::rand(&mut rng),
150            },
151            (0..rounds)
152                .map(|_| satisfying_assignments_for_test(Fr::rand(&mut rng)))
153                .collect(),
154            &mut rng,
155        )?;
156
157        test_folding_scheme::<AbstractNova<Pedersen<G1Projective, false>, TF>, 2, 0>(
158            8,
159            CircuitForTest {
160                x: Fr::rand(&mut rng),
161            },
162            (0..rounds)
163                .map(|_| satisfying_assignments_for_test(Fr::rand(&mut rng)))
164                .collect(),
165            &mut rng,
166        )?;
167        Ok(())
168    }
169
170    #[test]
171    fn test_nova() -> Result<(), Box<dyn Error>> {
172        let mut rng = thread_rng();
173
174        test_nova_opt::<Fr>(10, &mut rng)?;
175        test_nova_opt::<Fq>(10, &mut rng)?;
176        Ok(())
177    }
178}
sonobe_fs/nova/mod.rs

sonobe_fs/nova/
mod.rs
