sonobe_fs/nova/algorithms/
prover.rs

1//! Proof generation for Nova.
2
3use ark_ff::{Field, One};
4use ark_std::{borrow::Borrow, cfg_into_iter, cfg_iter, ops::Mul, rand::RngCore};
5#[cfg(not(feature = "parallel"))]
6use itertools::Itertools;
7#[cfg(feature = "parallel")]
8use rayon::prelude::*;
9use sonobe_primitives::{
10    algebra::ops::bits::FromBits,
11    arithmetizations::r1cs::R1CS,
12    circuits::{Assignments, AssignmentsOwned},
13    commitments::GroupBasedCommitment,
14    traits::SonobeField,
15    transcripts::Transcript,
16};
17
18use crate::{
19    Error, FoldingSchemeProver,
20    nova::{AbstractNova, NovaKey},
21};
22
23fn cross_term<'a, F: Field>(
24    arith: &R1CS<F>,
25    z1: impl Into<Assignments<F, &'a [F]>>,
26    z2: impl Into<Assignments<F, &'a [F]>>,
27    #[cfg(feature = "parallel")] e: impl IndexedParallelIterator<Item: Borrow<F>>,
28    #[cfg(not(feature = "parallel"))] e: impl Iterator<Item: Borrow<F>>,
29) -> Result<Vec<F>, Error> {
30    let z1 = z1.into();
31    let z2 = z2.into();
32
33    // Compute the cross term `T` by following the optimized approach in
34    // [Mova](https://eprint.iacr.org/2024/1220.pdf)'s section 5.2.
35    let v = arith.evaluate_r1cs(AssignmentsOwned::from((
36        z1.constant + z2.constant,
37        cfg_iter!(z1.public)
38            .zip_eq(z2.public)
39            .map(|(a, b)| *a + b)
40            .collect(),
41        cfg_iter!(z1.private)
42            .zip_eq(z2.private)
43            .map(|(a, b)| *a + b)
44            .collect(),
45    )))?;
46    Ok(cfg_into_iter!(v)
47        .zip_eq(e)
48        .map(|(a, b)| a - b.borrow())
49        .collect())
50}
51
52impl<CM: GroupBasedCommitment, TF: SonobeField, const B: usize> FoldingSchemeProver<1, 1>
53    for AbstractNova<CM, TF, B>
54{
55    #[allow(non_snake_case)]
56    fn prove(
57        pk: &NovaKey<Self::Arith, CM>,
58        transcript: &mut impl Transcript<TF>,
59        Ws: &[impl Borrow<Self::RW>; 1],
60        Us: &[impl Borrow<Self::RU>; 1],
61        ws: &[impl Borrow<Self::IW>; 1],
62        us: &[impl Borrow<Self::IU>; 1],
63        rng: impl RngCore,
64    ) -> Result<(Self::RW, Self::RU, Self::Proof<1, 1>), Error> {
65        let (W, U) = (Ws[0].borrow(), Us[0].borrow());
66        let (w, u) = (ws[0].borrow(), us[0].borrow());
67
68        let (z1, z2) = ((U.u, &U.x[..], &W.w[..]), (One::one(), &u.x[..], &w.w[..]));
69        let t = cross_term(&pk.arith, z1, z2, cfg_iter!(W.e))?;
70
71        let (cm_t, r_t) = CM::commit(&pk.ck, &t, rng)?;
72
73        let rho_bits = transcript.add(&U).add(&u).add(&cm_t).challenge_bits(B);
74        let rho = CM::Scalar::from_bits_le(&rho_bits);
75
76        let WW = Self::RW {
77            e: cfg_iter!(W.e)
78                .zip_eq(&t)
79                .map(|(a, b)| rho * b + a)
80                .collect(),
81            r_e: W.r_e + r_t * rho,
82            w: cfg_iter!(W.w)
83                .zip_eq(&w.w)
84                .map(|(a, b)| rho * b + a)
85                .collect(),
86            r_w: W.r_w + w.r_w * rho,
87        };
88        let UU = Self::RU {
89            cm_e: U.cm_e + cm_t.mul(rho),
90            u: U.u + rho,
91            cm_w: U.cm_w + u.cm_w.mul(rho),
92            x: cfg_iter!(U.x)
93                .zip_eq(&u.x)
94                .map(|(a, b)| rho * b + a)
95                .collect(),
96        };
97        Ok((WW, UU, cm_t))
98    }
99}
100
101impl<CM: GroupBasedCommitment, TF: SonobeField, const B: usize> FoldingSchemeProver<2, 0>
102    for AbstractNova<CM, TF, B>
103{
104    #[allow(non_snake_case)]
105    fn prove(
106        pk: &NovaKey<Self::Arith, CM>,
107        transcript: &mut impl Transcript<TF>,
108        [W1, W2]: &[impl Borrow<Self::RW>; 2],
109        [U1, U2]: &[impl Borrow<Self::RU>; 2],
110        _: &[impl Borrow<Self::IW>; 0],
111        _: &[impl Borrow<Self::IU>; 0],
112        rng: impl RngCore,
113    ) -> Result<(Self::RW, Self::RU, Self::Proof<2, 0>), Error> {
114        let (W1, U1) = (W1.borrow(), U1.borrow());
115        let (W2, U2) = (W2.borrow(), U2.borrow());
116
117        let (z1, z2) = ((U1.u, &U1.x[..], &W1.w[..]), (U2.u, &U2.x[..], &W2.w[..]));
118        let e = cfg_iter!(W1.e).zip_eq(&W2.e).map(|(a, b)| *a + b);
119        let t = cross_term(&pk.arith, z1, z2, e)?;
120
121        let (cm_t, r_t) = CM::commit(&pk.ck, &t, rng)?;
122
123        let rho_bits = transcript.add(&(U1, U2)).add(&cm_t).challenge_bits(B);
124        let rho = CM::Scalar::from_bits_le(&rho_bits);
125        let rho_squared = rho * rho;
126
127        let WW = Self::RW {
128            e: cfg_iter!(W1.e)
129                .zip_eq(&t)
130                .zip_eq(&W2.e)
131                .map(|((a, b), c)| rho_squared * c + rho * b + a)
132                .collect(),
133            r_e: W1.r_e + r_t * rho + W2.r_e * rho_squared,
134            w: cfg_iter!(W1.w)
135                .zip_eq(&W2.w)
136                .map(|(a, b)| rho * b + a)
137                .collect(),
138            r_w: W1.r_w + W2.r_w * rho,
139        };
140        let UU = Self::RU {
141            cm_e: U1.cm_e + cm_t.mul(rho) + U2.cm_e.mul(rho_squared),
142            u: U1.u + rho * U2.u,
143            cm_w: U1.cm_w + U2.cm_w.mul(rho),
144            x: cfg_iter!(U1.x)
145                .zip_eq(&U2.x)
146                .map(|(a, b)| rho * b + a)
147                .collect(),
148        };
149        Ok((WW, UU, cm_t))
150    }
151}
sonobe_fs/nova/algorithms/prover.rs

sonobe_fs/nova/algorithms/
prover.rs
