nova-study/src/nifs.rs
src/nifs.rsRaw
1use ark_ec::AffineRepr;
2use ark_std::ops::Add;
3use std::marker::PhantomData;
4
5use crate::pedersen::{Commitment, CommitmentVec};
6use crate::r1cs::*;
7use crate::transcript::Transcript;
8use crate::utils::*;
9
10// Phi: φ in the paper (later 𝖴), a folded instance
11pub struct Phi<C: AffineRepr> {
12 cmE: Commitment<C>, // TODO not Commitment but directly C (without rE)
13 u: C::ScalarField,
14 cmW: Commitment<C>, // TODO not Commitment but directly C (without rW)
15 x: Vec<C::ScalarField>,
16}
17
18// FWit: Folded Witness
19pub struct FWit<C: AffineRepr> {
20 E: Vec<C::ScalarField>,
21 rE: C::ScalarField,
22 W: Vec<C::ScalarField>,
23 rW: C::ScalarField,
24}
25
26impl<C: AffineRepr> FWit<C> {
27 pub fn commit(&self) -> Phi<C> {
28 unimplemented!();
29 }
30}
31
32pub struct NIFS<C: AffineRepr> {
33 _phantom: PhantomData<C>,
34}
35
36impl<C: AffineRepr> NIFS<C> {
37 pub fn comp_T(
38 cs1: RelaxedR1CS<C::ScalarField>,
39 cs2: RelaxedR1CS<C::ScalarField>,
40 z1: &Vec<C::ScalarField>,
41 z2: &Vec<C::ScalarField>,
42 ) -> Vec<C::ScalarField> {
43 // assuming cs1.R1CS == cs2.R1CS
44 let (A, B, C) = (cs1.ABC.A, cs1.ABC.B, cs1.ABC.C);
45
46 // this is parallelizable (for the future)
47 let Az1 = matrix_vector_product(&A, &z1);
48 let Bz1 = matrix_vector_product(&B, &z1);
49 let Az1_Bz1 = hadamard_product(Az1, Bz1);
50 let Az2 = matrix_vector_product(&A, &z2);
51 let Bz2 = matrix_vector_product(&B, &z2);
52 let Az2_Bz2 = hadamard_product(Az2, Bz2);
53 let Cz2 = matrix_vector_product(&C, &z2);
54 let Cz1 = matrix_vector_product(&C, &z1);
55 let u1Cz2 = vector_elem_product(&Cz2, &cs1.u);
56 let u2Cz1 = vector_elem_product(&Cz1, &cs2.u);
57 // this will get simplifyied with future operators from Add trait
58 let T = vec_sub(vec_sub(vec_add(Az1_Bz1, Az2_Bz2), u1Cz2), u2Cz1);
59 T
60 }
61
62 pub fn fold_witness(
63 r: C::ScalarField,
64 fw1: &FWit<C>,
65 fw2: &FWit<C>,
66 T: Vec<C::ScalarField>,
67 ) -> FWit<C> {
68 let r2 = r * r;
69 let E: Vec<C::ScalarField> = vec_add(
70 // TODO this syntax will be simplified with future operators impl
71 vec_add(fw1.E.clone(), vector_elem_product(&T, &r)),
72 vector_elem_product(&fw2.E, &r2),
73 );
74 let rE = fw1.rE + r * fw2.rE;
75 let W = vec_add(fw1.W.clone(), vector_elem_product(&fw2.W, &r));
76 let rW = fw1.rW + r * fw2.rW;
77 FWit::<C> {
78 E: E.into(),
79 rE,
80 W: W.into(),
81 rW,
82 }
83 }
84
85 pub fn fold_instance(
86 r: C::ScalarField,
87 phi1: Phi<C>,
88 phi2: Phi<C>,
89 cmT: CommitmentVec<C>,
90 ) -> Phi<C> {
91 let r2 = r * r;
92
93 let cmE = phi1.cmE.cm + cmT.cm.mul(r) + phi2.cmE.cm.mul(r2);
94 let u = phi1.u + r * phi2.u;
95 let cmW = phi1.cmW.cm + phi2.cmW.cm.mul(r);
96 let x = vec_add(phi1.x, vector_elem_product(&phi2.x, &r));
97
98 Phi::<C> {
99 cmE: Commitment::<C> {
100 cm: cmE.into(),
101 r: phi1.cmE.r,
102 },
103 u,
104 cmW: Commitment::<C> {
105 cm: cmW.into(),
106 r: phi1.cmW.r,
107 },
108 x,
109 }
110 }
111}
112
113#[cfg(test)]
114mod tests {
115 use super::*;
116 use crate::pedersen::Pedersen;
117 use ark_bn254::{g1::G1Affine, Fr};
118 use ark_ec::CurveGroup;
119 use ark_std::{
120 rand::{Rng, RngCore},
121 UniformRand,
122 };
123 use ark_std::{One, Zero};
124 use std::ops::Mul;
125
126 #[test]
127 fn test_simple_folding() {
128 let mut rng = ark_std::test_rng();
129
130 // R1CS for: x^3 + x + 5 = y
131 let A = to_F_matrix::<Fr>(vec![
132 vec![0, 1, 0, 0, 0, 0],
133 vec![0, 0, 0, 1, 0, 0],
134 vec![0, 1, 0, 0, 1, 0],
135 vec![5, 0, 0, 0, 0, 1],
136 ]);
137 let B = to_F_matrix::<Fr>(vec![
138 vec![0, 1, 0, 0, 0, 0],
139 vec![0, 1, 0, 0, 0, 0],
140 vec![1, 0, 0, 0, 0, 0],
141 vec![1, 0, 0, 0, 0, 0],
142 ]);
143 let C = to_F_matrix::<Fr>(vec![
144 vec![0, 0, 0, 1, 0, 0],
145 vec![0, 0, 0, 0, 1, 0],
146 vec![0, 0, 0, 0, 0, 1],
147 vec![0, 0, 1, 0, 0, 0],
148 ]);
149 let z1 = to_F_vec::<Fr>(vec![1, 3, 35, 9, 27, 30]);
150 let z2 = to_F_vec::<Fr>(vec![1, 4, 73, 16, 64, 68]);
151
152 let relaxed_r1cs_1 = R1CS::<Fr> {
153 A: A.clone(),
154 B: B.clone(),
155 C: C.clone(),
156 }
157 .relax();
158 let relaxed_r1cs_2 = R1CS::<Fr> { A, B, C }.relax();
159
160 let T = NIFS::<G1Affine>::comp_T(relaxed_r1cs_1, relaxed_r1cs_2, &z1, &z2);
161 let params = Pedersen::<G1Affine>::new_params(&mut rng);
162 let cmT = Pedersen::commit_vec(&mut rng, ¶ms, &T);
163
164 let r = Fr::rand(&mut rng); // this would come from the transcript
165
166 // WIP TMP
167 let fw1 = FWit::<G1Affine> {
168 E: vec![Fr::zero(); T.len()],
169 rE: Fr::zero(),
170 W: z1,
171 rW: Fr::zero(),
172 };
173 let fw2 = FWit::<G1Affine> {
174 E: vec![Fr::zero(); T.len()],
175 rE: Fr::zero(),
176 W: z2,
177 rW: Fr::zero(),
178 };
179
180 // fold witness
181 let folded_witness = NIFS::<G1Affine>::fold_witness(r, &fw1, &fw2, T);
182 let phi1 = fw1.commit(); // <- unimplemented
183 let phi2 = fw2.commit();
184 // fold instance
185 let folded_instance = NIFS::<G1Affine>::fold_instance(r, phi1, phi2, cmT);
186 // naive check r1cs of the folded witness
187 // assert_eq!(hadamard_product(Az, Bz), vec_add(vector_elem_product(Cz, u), E));
188 }
189}