fri-commitment/src/lib.rs
src/lib.rsRaw
1#![allow(non_snake_case)]
2#![allow(non_camel_case_types)]
3
4pub mod merkletree;
5use merkletree::{MerkleTreePoseidon as MT, Params as MTParams};
6
7use ark_ff::PrimeField;
8use ark_poly::{
9 univariate::DensePolynomial, EvaluationDomain, GeneralEvaluationDomain, UVPolynomial,
10};
11
12use ark_std::log2;
13use ark_std::marker::PhantomData;
14use ark_std::ops::Mul;
15use ark_std::{cfg_into_iter, rand::Rng, UniformRand};
16
17pub struct FRI_LDT<F: PrimeField, P: UVPolynomial<F>> {
18 _f: PhantomData<F>,
19 _poly: PhantomData<P>,
20}
21
22impl<F: PrimeField, P: UVPolynomial<F>> FRI_LDT<F, P> {
23 pub fn new() -> Self {
24 Self {
25 _f: PhantomData,
26 _poly: PhantomData,
27 }
28 }
29
30 pub fn split(p: &P) -> (P, P) {
31 // let d = p.degree() + 1;
32 let d = p.coeffs().len();
33 if (d != 0) && (d & (d - 1) != 0) {
34 println!("d={:?}", d);
35 panic!("d should be a power of 2");
36 }
37
38 let coeffs = p.coeffs();
39 let odd: Vec<F> = coeffs.iter().step_by(2).cloned().collect();
40 let even: Vec<F> = coeffs.iter().skip(1).step_by(2).cloned().collect();
41
42 return (
43 P::from_coefficients_vec(odd),
44 P::from_coefficients_vec(even),
45 );
46 }
47
48 // prove implements the proof generation for a FRI-low-degree-testing
49 pub fn prove<R: Rng>(rng: &mut R, p: &P) -> (Vec<F>, Vec<Vec<F>>, Vec<F>, [F; 2]) {
50 let d = p.degree();
51 let mut commitments: Vec<F> = Vec::new();
52 let mut mts: Vec<MT<F>> = Vec::new();
53
54 // f_0(x) = fL_0(x^2) + x fR_0(x^2)
55 let mut f_i1 = p.clone();
56
57 // sub_order = |F_i| = rho^-1 * d
58 let mut sub_order = d; // TMP, TODO this will depend on rho parameter
59 let mut eval_sub_domain: GeneralEvaluationDomain<F> =
60 GeneralEvaluationDomain::new(sub_order).unwrap();
61
62 // TODO merge in the next for loop
63 let evals: Vec<F> = cfg_into_iter!(0..eval_sub_domain.size())
64 .map(|k| f_i1.evaluate(&eval_sub_domain.element(k)))
65 .collect();
66 let (cm_i, mt_i) = MT::commit(&evals);
67 commitments.push(cm_i);
68 mts.push(mt_i);
69 sub_order = sub_order / 2;
70 eval_sub_domain = GeneralEvaluationDomain::new(sub_order).unwrap();
71 //
72
73 // V sets rand z \in \mathbb{F} challenge
74 // TODO this will be a hash from the transcript
75 let z_pos = 3;
76 let z = eval_sub_domain.element(z_pos);
77 let z_pos = z_pos * 2; // WIP
78
79 let mut f_is: Vec<P> = Vec::new();
80 f_is.push(p.clone());
81 while f_i1.degree() > 1 {
82 let alpha_i = F::from(42_u64); // TODO: WIP, defined by Verifier (well, hash transcript)
83
84 let (fL_i, fR_i) = Self::split(&f_i1);
85
86 // compute f_{i+1}(x) = fL_i(x) + alpha_i * fR_i(x)
87 let aux = DensePolynomial::from_coefficients_slice(fR_i.coeffs());
88 f_i1 = fL_i.clone() + P::from_coefficients_slice(aux.mul(alpha_i).coeffs());
89 f_is.push(f_i1.clone());
90
91 let subdomain_evaluations: Vec<F> = cfg_into_iter!(0..eval_sub_domain.size())
92 .map(|k| f_i1.evaluate(&eval_sub_domain.element(k)))
93 .collect();
94
95 // commit to f_{i+1}(x) = fL_i(x) + alpha_i * fR_i(x)
96 let (cm_i, mt_i) = MT::commit(&subdomain_evaluations); // commit to the evaluation domain instead
97 commitments.push(cm_i);
98 mts.push(mt_i);
99
100 // prepare next subdomain
101 sub_order = sub_order / 2;
102 eval_sub_domain = GeneralEvaluationDomain::new(sub_order).unwrap();
103 }
104 let (fL_i, fR_i) = Self::split(&f_i1);
105 let constant_fL_l: F = fL_i.coeffs()[0].clone();
106 let constant_fR_l: F = fR_i.coeffs()[0].clone();
107
108 // evals = {f_i(z^{2^i}), f_i(-z^{2^i})} \forall i \in F_i
109 let mut evals: Vec<F> = Vec::new();
110 let mut mtproofs: Vec<Vec<F>> = Vec::new();
111 // TODO this will be done inside the prev loop, now it is here just for clarity
112 // evaluate f_i(z^{2^i}), f_i(-z^{2^i}), and open their commitment
113 for i in 0..f_is.len() {
114 let z_2i = z.pow([2_u64.pow(i as u32)]); // z^{2^i} // TODO check usage of .pow(u64)
115 let neg_z_2i = z_2i.neg();
116 let eval_i = f_is[i].evaluate(&z_2i);
117 evals.push(eval_i);
118 let eval_i = f_is[i].evaluate(&neg_z_2i);
119 evals.push(eval_i);
120
121 // gen the openings in the commitment to f_i(z^(2^i))
122 let mtproof = mts[i].open(F::from(z_pos as u32)); // WIP open to 2^i?
123 mtproofs.push(mtproof);
124 }
125
126 (commitments, mtproofs, evals, [constant_fL_l, constant_fR_l])
127 }
128
129 // verify implements the verification of a FRI-low-degree-testing proof
130 pub fn verify(
131 degree: usize, // expected degree
132 commitments: Vec<F>,
133 mtproofs: Vec<Vec<F>>,
134 evals: Vec<F>,
135 constants: [F; 2],
136 ) -> bool {
137 let sub_order = ((degree + 1) / 2) - 1; // TMP, TODO this will depend on rho parameter
138 let eval_sub_domain: GeneralEvaluationDomain<F> =
139 GeneralEvaluationDomain::new(sub_order).unwrap();
140 // TODO this will be a hash from the transcript
141 let z_pos = 3;
142 let z = eval_sub_domain.element(z_pos);
143 let z_pos = z_pos * 2;
144
145 if commitments.len() != (evals.len() / 2) {
146 println!("sho commitments.len() != (evals.len() / 2) - 1");
147 return false;
148 }
149
150 let mut i_z = 0;
151 for i in (0..evals.len()).step_by(2) {
152 let alpha_i = F::from(42_u64); // TODO: WIP, defined by Verifier (well, hash transcript)
153
154 // take f_i(z^2) from evals
155 let z_2i = z.pow([2_u64.pow(i_z as u32)]); // z^{2^i}
156 let fi_z = evals[i];
157 let neg_fi_z = evals[i + 1];
158 // compute f_i^L(z^2), f_i^R(z^2) from the linear combination
159 let L = (fi_z + neg_fi_z) * F::from(2_u32).inverse().unwrap();
160 let R = (fi_z - neg_fi_z) * (F::from(2_u32) * z_2i).inverse().unwrap();
161
162 // compute f_{i+1}(z^2) = f_i^L(z^2) + a_i f_i^R(z^2)
163 let next_fi_z2 = L + alpha_i * R;
164
165 // check: obtained f_{i+1}(z^2) == evals.f_{i+1}(z^2) (=evals[i+2])
166 if i < evals.len() - 2 {
167 if next_fi_z2 != evals[i + 2] {
168 println!(
169 "verify step i={}, should f_i+1(z^2) == evals.f_i+1(z^2) (=evals[i+2])",
170 i
171 );
172 return false;
173 }
174 }
175
176 // check commitment opening
177 if !MT::verify(
178 commitments[i_z],
179 // F::from(i as u32),
180 F::from(z_pos as u32),
181 evals[i],
182 mtproofs[i_z].clone(),
183 ) {
184 println!("verify step i={}, MT::verify failed", i);
185 return false;
186 }
187
188 // last iteration, check constant values equal to the obtained f_i^L(z^{2^i}),
189 // f_i^R(z^{2^i})
190 if i == evals.len() - 2 {
191 if L != constants[0] {
192 println!("constant L not equal to the obtained one");
193 return false;
194 }
195 if R != constants[1] {
196 println!("constant R not equal to the obtained one");
197 return false;
198 }
199 }
200 i_z += 1;
201 }
202
203 true
204 }
205}
206
207#[cfg(test)]
208mod tests {
209 use super::*;
210 use ark_ff::Field;
211 use ark_std::UniformRand;
212 pub type Fr = ark_bn254::Fr; // scalar field
213 use ark_poly::univariate::DensePolynomial;
214 use ark_poly::Polynomial;
215
216 #[test]
217 fn test_split() {
218 let mut rng = ark_std::test_rng();
219 let deg = 7;
220 let p = DensePolynomial::<Fr>::rand(deg, &mut rng);
221 assert_eq!(p.degree(), deg);
222
223 type FRIT = FRI_LDT<Fr, DensePolynomial<Fr>>;
224 let (pL, pR) = FRIT::split(&p);
225
226 // check that f(z) == fL(x^2) + x * fR(x^2), for a rand z
227 let z = Fr::rand(&mut rng);
228 assert_eq!(
229 p.evaluate(&z),
230 pL.evaluate(&z.square()) + z * pR.evaluate(&z.square())
231 );
232 }
233
234 #[test]
235 fn test_prove() {
236 let mut rng = ark_std::test_rng();
237
238 let deg = 15;
239 let p = DensePolynomial::<Fr>::rand(deg, &mut rng);
240 assert_eq!(p.degree(), deg);
241 // println!("p {:?}", p);
242
243 type FRIT = FRI_LDT<Fr, DensePolynomial<Fr>>;
244 // prover
245 let (commitments, mtproofs, evals, constvals) = FRIT::prove(&mut rng, &p);
246 // commitments contains the commitments to each f_0, f_1, ..., f_n, with n=log2(d)
247 assert_eq!(commitments.len(), log2(p.coeffs().len()) as usize);
248 assert_eq!(evals.len(), 2 * log2(p.coeffs().len()) as usize);
249
250 let v = FRIT::verify(
251 // Fr::from(deg as u32),
252 deg,
253 commitments,
254 mtproofs,
255 evals,
256 constvals,
257 );
258 assert!(v);
259 }
260}