nova-study/src/hypernova/multifolding.rs
src/hypernova/multifolding.rsRaw
1use ark_crypto_primitives::sponge::{poseidon::PoseidonConfig, Absorb};
2use ark_ec::{CurveGroup, Group};
3use ark_ff::fields::PrimeField;
4use ark_poly::{
5 evaluations::multivariate::multilinear::{MultilinearExtension, SparseMultilinearExtension},
6 multivariate::{SparsePolynomial, SparseTerm, Term},
7 univariate::DensePolynomial,
8 DenseMVPolynomial, DenseUVPolynomial, Polynomial,
9};
10use ark_std::log2;
11
12use std::marker::PhantomData;
13
14use crate::hypernova::ccs::CCS;
15use crate::hypernova::sumcheck::{Point, SumCheck};
16use crate::pedersen::Commitment;
17use crate::transcript::Transcript;
18
19use ark_std::{One, Zero};
20
21// Committed CCS instance
22pub struct CCCS<C: CurveGroup> {
23 C: Commitment<C>,
24 x: Vec<C::ScalarField>,
25}
26
27// Linearized Committed CCS instance
28pub struct LCCCS<C: CurveGroup> {
29 C: Commitment<C>,
30 u: C::ScalarField,
31 x: Vec<C::ScalarField>,
32 r: Vec<C::ScalarField>,
33 v: Vec<C::ScalarField>,
34}
35
36// NIMFS: Non Interactive Multifolding Scheme
37pub struct NIMFS<C: CurveGroup> {
38 _c: PhantomData<C>,
39}
40
41impl<C: CurveGroup> NIMFS<C>
42where
43 <C as Group>::ScalarField: Absorb,
44 <C as CurveGroup>::BaseField: Absorb,
45{
46 // proof method folds and returns the proof of the multifolding
47 pub fn proof(
48 tr: &mut Transcript<C::ScalarField, C>,
49 poseidon_config: &PoseidonConfig<C::ScalarField>,
50 ccs: CCS<C::ScalarField>,
51 lcccs: LCCCS<C>,
52 cccs: CCCS<C>,
53 z1: Vec<C::ScalarField>,
54 z2: Vec<C::ScalarField>,
55 ) -> LCCCS<C> {
56 let s = log2(ccs.m) as usize; // s
57 let s_ = log2(ccs.n) as usize; // s'
58 let gamma = tr.get_challenge();
59 let beta = tr.get_challenge_vec(s);
60
61 // get MLE of M_i
62 let mut MLEs: Vec<SparseMultilinearExtension<C::ScalarField>> = Vec::new();
63 let n_vars = (s + s_) as usize;
64 for i in 0..ccs.M.len() {
65 let M_i_MLE = matrix_to_mle(n_vars, ccs.m, ccs.n, &ccs.M[i]);
66 MLEs.push(M_i_MLE);
67 }
68 // get MLE of z1 & z2
69 let z1_MLE = vector_to_mle(s_, ccs.n, z1);
70 let z2_MLE = vector_to_mle(s_, ccs.n, z2);
71
72 // compute Lj = eq(r_x,x) * \sum Mj * z1
73 let mut Lj_evals: Vec<(usize, C::ScalarField)> = Vec::new();
74 for i in 0..s_ {}
75 // compute Q = eq(beta, x) * ( \sum c_i * \prod( \sum Mj * z1 ) )
76 // compute g
77 // let g: SparsePolynomial<C::ScalarField, SparseTerm>;
78 // let proof = SC::<C>::prove(&poseidon_config, g);
79 // fold C, u, x, v, w
80
81 unimplemented!();
82 }
83}
84
85fn matrix_to_mle<F: PrimeField>(
86 n_vars: usize, // log2(m) + log2(n)
87 m: usize,
88 n: usize,
89 M: &Vec<Vec<F>>,
90) -> SparseMultilinearExtension<F> {
91 let mut M_evals: Vec<(usize, F)> = Vec::new();
92 for i in 0..m {
93 for j in 0..n {
94 if !M[i][j].is_zero() {
95 M_evals.push((i * n + j, M[i][j]));
96 }
97 }
98 }
99 SparseMultilinearExtension::<F>::from_evaluations(n_vars, M_evals.iter())
100}
101
102fn vector_to_mle<F: PrimeField>(s: usize, n: usize, z: Vec<F>) -> SparseMultilinearExtension<F> {
103 let mut z_evals: Vec<(usize, F)> = Vec::new();
104 for i in 0..n {
105 if !z[i].is_zero() {
106 z_evals.push((i, z[i]));
107 }
108 }
109 SparseMultilinearExtension::<F>::from_evaluations(s, z_evals.iter())
110}
111
112type SC<C: CurveGroup> = SumCheck<
113 C::ScalarField,
114 C,
115 DensePolynomial<C::ScalarField>,
116 SparsePolynomial<C::ScalarField, SparseTerm>,
117>;
118
119#[cfg(test)]
120mod tests {
121 use super::*;
122 use crate::transcript::poseidon_test_config;
123 use ark_mnt4_298::{Fr, G1Projective};
124 use ark_std::One;
125 use ark_std::UniformRand;
126
127 use crate::nifs::gen_test_values;
128
129 type P = Point<Fr>;
130
131 #[test]
132 fn test_cccs_mles() {
133 let (r1cs, ws, _) = gen_test_values(2);
134 let z1: Vec<Fr> = ws[0].clone();
135 println!("z1 {:?}", z1);
136
137 let ccs = r1cs.to_ccs();
138 let s = log2(ccs.m) as usize; // s
139 let s_ = log2(ccs.n) as usize; // s'
140 let pow_s_ = (2 as usize).pow(s_ as u32);
141
142 let mut M_MLEs: Vec<SparseMultilinearExtension<Fr>> = Vec::new();
143 let n_vars = (s + s_) as usize;
144 for i in 0..ccs.M.len() {
145 let M_i_MLE = matrix_to_mle(n_vars, ccs.m, ccs.n, &ccs.M[i]);
146 println!("i:{}, M_i_mle: {:?}", i, M_i_MLE);
147 M_MLEs.push(M_i_MLE);
148 }
149
150 let z1_MLE = vector_to_mle(s_, ccs.n, z1);
151 println!("z1_MLE: {:?}", z1_MLE);
152
153 let beta = Point::<Fr>::point_normal(s, 2); // imagine that this comes from random
154 println!("beta: {:?}", beta);
155
156 // check Committed CCS relation
157 let mut r: Fr = Fr::zero();
158 for i in 0..ccs.q {
159 let mut prod_res = Fr::one();
160 // for j in 0..ccs.S.len() {
161 for j in ccs.S[i].clone() {
162 let mut Mj_z_eval = Fr::zero();
163 // for k in 0..s_ {
164 // over the boolean hypercube un s' vars, but only the combinations that lead to
165 // some non-zero z()
166 for k in 0..ccs.n {
167 // over the whole boolean hypercube on s' vars
168 // for k in 0..pow_s_ {
169 let point_in_s_ = Point::<Fr>::point_normal(s_, k);
170 // println!("point_in_s {:?}", point_in_s_);
171 let z_eval = z1_MLE.evaluate(&point_in_s_).unwrap();
172 // println!(" ===================================z_eval {:?}", z_eval);
173
174 // let point_in_s_plus_s_ = Point::<Fr>::point_complete(beta.clone(), s + s_, k);
175 let mut point_in_s_plus_s_ = Point::<Fr>::point_normal(s_, k);
176 point_in_s_plus_s_.append(&mut beta.clone());
177 // println!("point_in_s_plus_s_ {:?}", point_in_s_plus_s_);
178 // println!("j: {}, Mj {:?}", j, M_MLEs[j]);
179 let Mj_eval = M_MLEs[j].evaluate(&point_in_s_plus_s_).unwrap();
180
181 if Mj_eval * z_eval != Fr::zero() {
182 println!(" j: {}, Mj_eval {:?}", j, Mj_eval);
183 println!(" z_eval {:?}", z_eval);
184 println!(" =(Mj*z)_eval {:?}", Mj_eval * z_eval);
185 }
186
187 Mj_z_eval += Mj_eval * z_eval;
188 }
189 println!("j: {}, {:?}\n", j, Mj_z_eval);
190 prod_res += Mj_z_eval;
191 }
192 println!("i:{}, c: {:?}, {:?}\n", i, ccs.c[i], prod_res);
193 r += ccs.c[i] * prod_res;
194 }
195 println!("r {:?}", r);
196 // assert!(r.is_zero());
197 }
198}