fri-commitment/src/lib.rs
src/lib.rsRaw
1#![allow(non_snake_case)]
2#![allow(non_camel_case_types)]
3#![allow(non_upper_case_globals)]
4
5pub mod merkletree;
6use merkletree::{Hash, MerkleTree};
7pub mod transcript;
8use transcript::Transcript;
9
10use ark_ff::PrimeField;
11use ark_poly::{
12 univariate::DensePolynomial, DenseUVPolynomial, EvaluationDomain, GeneralEvaluationDomain,
13};
14
15use ark_std::cfg_into_iter;
16use ark_std::marker::PhantomData;
17use ark_std::ops::Div;
18use ark_std::ops::Mul;
19
20// rho^-1
21const rho1: usize = 8; // WIP TODO parametrize
22
23// FRI low degree testing proof
24pub struct LDTProof<F: PrimeField> {
25 degree: usize, // claimed degree
26 commitments: Vec<F>,
27 mtproofs: Vec<Vec<F>>,
28 evals: Vec<F>,
29 constants: [F; 2],
30}
31
32// FRI_LDT implements the FRI Low Degree Testing
33pub struct FRI_LDT<F: PrimeField, P: DenseUVPolynomial<F>, H: Hash<F>> {
34 _f: PhantomData<F>,
35 _poly: PhantomData<P>,
36 _h: PhantomData<H>,
37}
38
39impl<F: PrimeField, P: DenseUVPolynomial<F>, H: Hash<F>> FRI_LDT<F, P, H> {
40 pub fn new() -> Self {
41 Self {
42 _f: PhantomData,
43 _poly: PhantomData,
44 _h: PhantomData,
45 }
46 }
47
48 fn split(p: &P) -> (P, P) {
49 // TODO see if enable check, take in mind g(x) being d-1
50 // let d = p.coeffs().len();
51 // if (d != 0) && (d & (d - 1) != 0) {
52 // println!("d={:?}", d);
53 // panic!("d should be a power of 2");
54 // }
55
56 // let d = p.degree() + 1;
57 let coeffs = p.coeffs();
58 let odd: Vec<F> = coeffs.iter().step_by(2).cloned().collect();
59 let even: Vec<F> = coeffs.iter().skip(1).step_by(2).cloned().collect();
60
61 return (
62 P::from_coefficients_vec(odd),
63 P::from_coefficients_vec(even),
64 );
65 }
66
67 // prove implements the proof generation for a FRI-low-degree-testing
68 // pub fn prove(p: &P) -> (Vec<F>, Vec<Vec<F>>, Vec<F>, [F; 2]) {
69 pub fn prove(p: &P) -> LDTProof<F> {
70 // init transcript
71 let mut transcript: Transcript<F> = Transcript::<F>::new();
72
73 let d = p.degree();
74 let mut commitments: Vec<F> = Vec::new();
75 let mut mts: Vec<MerkleTree<F, H>> = Vec::new();
76
77 // f_0(x) = fL_0(x^2) + x fR_0(x^2)
78 let mut f_i1 = p.clone();
79
80 // sub_order = |F_i| = rho^-1 * d
81 let mut sub_order = d * rho1; // TMP, TODO this will depend on rho parameter
82 let mut eval_sub_domain: GeneralEvaluationDomain<F> =
83 GeneralEvaluationDomain::new(sub_order).unwrap();
84
85 // V sets rand z \in \mathbb{F} challenge
86 let (z_pos, z) = transcript.get_challenge_in_eval_domain(eval_sub_domain, b"get z");
87
88 let mut f_is: Vec<P> = Vec::new();
89 // evals = {f_i(z^{2^i}), f_i(-z^{2^i})} \forall i \in F_i
90 let mut evals: Vec<F> = Vec::new();
91 let mut mtproofs: Vec<Vec<F>> = Vec::new();
92 let mut fL_i: P = P::from_coefficients_vec(Vec::new());
93 let mut fR_i: P = P::from_coefficients_vec(Vec::new());
94 let mut i = 0;
95 while f_i1.degree() >= 1 {
96 f_is.push(f_i1.clone());
97 let alpha_i = transcript.get_challenge(b"get alpha_i");
98
99 let subdomain_evaluations: Vec<F> = cfg_into_iter!(0..eval_sub_domain.size())
100 .map(|k| f_i1.evaluate(&eval_sub_domain.element(k)))
101 .collect();
102
103 // commit to f_{i+1}(x) = fL_i(x) + alpha_i * fR_i(x), commit to the evaluation domain
104 let (cm_i, mt_i) = MerkleTree::<F, H>::commit(&subdomain_evaluations);
105 commitments.push(cm_i);
106 mts.push(mt_i);
107 transcript.add(b"root_i", &cm_i);
108
109 // evaluate f_i(z^{2^i}), f_i(-z^{2^i}), and open their commitment
110 let z_2i = z.pow([2_u64.pow(i as u32)]); // z^{2^i} // TODO check usage of .pow(u64)
111 let neg_z_2i = z_2i.neg();
112 let eval_i = f_i1.evaluate(&z_2i);
113 evals.push(eval_i);
114 transcript.add(b"f_i(z^{2^i})", &eval_i);
115 let eval_i = f_i1.evaluate(&neg_z_2i);
116 evals.push(eval_i);
117 transcript.add(b"f_i(-z^{2^i})", &eval_i);
118
119 // gen the openings in the commitment to f_i(z^(2^i))
120 let mtproof = mts[i].open(F::from(z_pos as u32));
121 mtproofs.push(mtproof);
122
123 (fL_i, fR_i) = Self::split(&f_i1);
124
125 // compute f_{i+1}(x) = fL_i(x) + alpha_i * fR_i(x)
126 let aux = DensePolynomial::from_coefficients_slice(fR_i.coeffs());
127 f_i1 = fL_i.clone() + P::from_coefficients_slice(aux.mul(alpha_i).coeffs());
128
129 // prepare next subdomain
130 sub_order = sub_order / 2;
131 eval_sub_domain = GeneralEvaluationDomain::new(sub_order).unwrap();
132
133 i += 1;
134 }
135 if fL_i.coeffs().len() != 1 {
136 panic!("fL_i not constant");
137 }
138 if fR_i.coeffs().len() != 1 {
139 panic!("fR_i not constant");
140 }
141 let constant_fL_l: F = fL_i.coeffs()[0].clone();
142 let constant_fR_l: F = fR_i.coeffs()[0].clone();
143
144 LDTProof {
145 degree: p.degree(),
146 commitments,
147 mtproofs,
148 evals,
149 constants: [constant_fL_l, constant_fR_l],
150 }
151 }
152
153 // verify implements the verification of a FRI-low-degree-testing proof
154 pub fn verify(
155 proof: LDTProof<F>,
156 degree: usize, // expected degree
157 ) -> bool {
158 // init transcript
159 let mut transcript: Transcript<F> = Transcript::<F>::new();
160
161 if degree != proof.degree {
162 println!("proof degree missmatch");
163 return false;
164 }
165 // TODO check that log_2(evals/2) == degree, etc
166
167 let sub_order = rho1 * degree;
168 let eval_sub_domain: GeneralEvaluationDomain<F> =
169 GeneralEvaluationDomain::new(sub_order).unwrap();
170
171 let (z_pos, z) = transcript.get_challenge_in_eval_domain(eval_sub_domain, b"get z");
172
173 if proof.commitments.len() != (proof.evals.len() / 2) {
174 println!("sho commitments.len() != (evals.len() / 2) - 1");
175 return false;
176 }
177
178 let mut i_z = 0;
179 for i in (0..proof.evals.len()).step_by(2) {
180 let alpha_i = transcript.get_challenge(b"get alpha_i");
181
182 // take f_i(z^2) from evals
183 let z_2i = z.pow([2_u64.pow(i_z as u32)]); // z^{2^i}
184 let fi_z = proof.evals[i];
185 let neg_fi_z = proof.evals[i + 1];
186 // compute f_i^L(z^2), f_i^R(z^2) from the linear combination
187 let L = (fi_z + neg_fi_z) * F::from(2_u32).inverse().unwrap();
188 let R = (fi_z - neg_fi_z) * (F::from(2_u32) * z_2i).inverse().unwrap();
189
190 // compute f_{i+1}(z^2) = f_i^L(z^2) + a_i f_i^R(z^2)
191 let next_fi_z2 = L + alpha_i * R;
192
193 // check: obtained f_{i+1}(z^2) == evals.f_{i+1}(z^2) (=evals[i+2])
194 if i < proof.evals.len() - 2 {
195 if next_fi_z2 != proof.evals[i + 2] {
196 println!(
197 "verify step i={}, should f_i+1(z^2) == evals.f_i+1(z^2) (=evals[i+2])",
198 i
199 );
200 return false;
201 }
202 }
203 transcript.add(b"root_i", &proof.commitments[i_z]);
204 transcript.add(b"f_i(z^{2^i})", &proof.evals[i]);
205 transcript.add(b"f_i(-z^{2^i})", &proof.evals[i + 1]);
206
207 // check commitment opening
208 if !MerkleTree::<F, H>::verify(
209 proof.commitments[i_z],
210 F::from(z_pos as u32),
211 proof.evals[i],
212 proof.mtproofs[i_z].clone(),
213 ) {
214 println!("verify step i={}, MT::verify failed", i);
215 return false;
216 }
217
218 // last iteration, check constant values equal to the obtained f_i^L(z^{2^i}),
219 // f_i^R(z^{2^i})
220 if i == proof.evals.len() - 2 {
221 if L != proof.constants[0] {
222 println!("constant L not equal to the obtained one");
223 return false;
224 }
225 if R != proof.constants[1] {
226 println!("constant R not equal to the obtained one");
227 return false;
228 }
229 }
230 i_z += 1;
231 }
232
233 true
234 }
235}
236
237pub struct FRI_PCS_Proof<F: PrimeField> {
238 p_proof: LDTProof<F>,
239 g_proof: LDTProof<F>,
240 mtproof_y: Vec<F>,
241}
242
243// FRI_PCS implements the FRI Polynomial Commitment
244pub struct FRI_PCS<F: PrimeField, P: DenseUVPolynomial<F>, H: Hash<F>> {
245 _F: PhantomData<F>,
246 _poly: PhantomData<P>,
247 _h: PhantomData<H>,
248}
249
250impl<F: PrimeField, P: DenseUVPolynomial<F>, H: Hash<F>> FRI_PCS<F, P, H>
251where
252 for<'a, 'b> &'a P: Div<&'b P, Output = P>,
253{
254 pub fn commit(p: &P) -> F {
255 let (cm, _) = Self::tree_from_domain_evals(p);
256 cm
257 }
258
259 fn tree_from_domain_evals(p: &P) -> (F, MerkleTree<F, H>) {
260 let d = p.degree();
261 let sub_order = d * rho1;
262 let eval_sub_domain: GeneralEvaluationDomain<F> =
263 GeneralEvaluationDomain::new(sub_order).unwrap();
264 let subdomain_evaluations: Vec<F> = cfg_into_iter!(0..eval_sub_domain.size())
265 .map(|k| p.evaluate(&eval_sub_domain.element(k)))
266 .collect();
267 MerkleTree::<F, H>::commit(&subdomain_evaluations)
268 }
269
270 pub fn open(p: &P, r: F) -> (F, FRI_PCS_Proof<F>) {
271 let y = p.evaluate(&r);
272 let y_poly: P = P::from_coefficients_vec(vec![y]);
273 let mut p_y: P = p.clone();
274 p_y.sub_assign(&y_poly);
275 // p_y = p_y - y_poly;
276 let x_r: P = P::from_coefficients_vec(vec![-r, F::one()]);
277
278 // g(x), quotient polynomial
279 let g: P = p_y.div(&x_r);
280
281 if p.degree() != g.degree() + 1 {
282 panic!("ERR p.deg: {}, g.deg: {}", p.degree(), g.degree()); // TODO err
283 }
284
285 // TODO proof for commitment
286 // reconstruct commitment_mt
287 let (_, commitment_mt) = Self::tree_from_domain_evals(&p);
288 let y_eval_index = F::from(3_u32); // TODO find y in subdomain_evaluations
289 let mtproof_y = commitment_mt.open(y_eval_index);
290
291 let p_proof = FRI_LDT::<F, P, H>::prove(p);
292 let g_proof = FRI_LDT::<F, P, H>::prove(&g);
293
294 (
295 y,
296 FRI_PCS_Proof {
297 p_proof,
298 g_proof,
299 mtproof_y,
300 },
301 )
302 }
303
304 pub fn verify(commitment: F, proof: FRI_PCS_Proof<F>, r: F, y: F) -> bool {
305 let deg_p = proof.p_proof.degree;
306 let deg_g = proof.g_proof.degree;
307 if deg_p != deg_g + 1 {
308 return false;
309 }
310
311 // obtain z from transcript
312 let sub_order = rho1 * proof.p_proof.degree;
313 let eval_sub_domain: GeneralEvaluationDomain<F> =
314 GeneralEvaluationDomain::new(sub_order).unwrap();
315 let mut transcript: Transcript<F> = Transcript::<F>::new();
316 let (_, z) = transcript.get_challenge_in_eval_domain(eval_sub_domain, b"get z");
317
318 // check g(z) == (f(z) - y) * (z-r)^-1
319 let gz = proof.g_proof.evals[0];
320 let fz = proof.p_proof.evals[0];
321 let rhs = (fz - y) / (z - r);
322 if gz != rhs {
323 return false;
324 }
325
326 // TODO check commitment
327
328 // check FRI-LDT for p(x)
329 if !FRI_LDT::<F, P, H>::verify(proof.p_proof, deg_p) {
330 return false;
331 }
332
333 // check FRI-LDT for g(x)
334 if !FRI_LDT::<F, P, H>::verify(proof.g_proof, deg_p - 1) {
335 return false;
336 }
337
338 return true;
339 }
340}
341
342#[cfg(test)]
343mod tests {
344 use super::*;
345 use ark_ff::Field;
346 use ark_std::UniformRand;
347 // pub type Fr = ark_bn254::Fr; // scalar field
348 use ark_bn254::Fr; // scalar field
349 use ark_poly::univariate::DensePolynomial;
350 use ark_poly::Polynomial;
351 use ark_std::log2;
352 use merkletree::Keccak256Hash;
353
354 #[test]
355 fn test_split() {
356 let mut rng = ark_std::test_rng();
357 let deg = 7;
358 let p = DensePolynomial::<Fr>::rand(deg, &mut rng);
359 assert_eq!(p.degree(), deg);
360
361 type FRID = FRI_LDT<Fr, DensePolynomial<Fr>, Keccak256Hash<Fr>>;
362 let (pL, pR) = FRID::split(&p);
363
364 // check that f(z) == fL(x^2) + x * fR(x^2), for a rand z
365 let z = Fr::rand(&mut rng);
366 assert_eq!(
367 p.evaluate(&z),
368 pL.evaluate(&z.square()) + z * pR.evaluate(&z.square())
369 );
370 }
371
372 #[test]
373 fn test_prove() {
374 let deg = 31;
375 let p = DensePolynomial::<Fr>::rand(deg, &mut ark_std::test_rng());
376 assert_eq!(p.degree(), deg);
377 // println!("p {:?}", p);
378
379 type LDT = FRI_LDT<Fr, DensePolynomial<Fr>, Keccak256Hash<Fr>>;
380
381 let proof = LDT::prove(&p);
382 // commitments contains the commitments to each f_0, f_1, ..., f_n, with n=log2(d)
383 assert_eq!(proof.commitments.len(), log2(p.coeffs().len()) as usize);
384 assert_eq!(proof.evals.len(), 2 * log2(p.coeffs().len()) as usize);
385
386 let v = LDT::verify(proof, deg);
387 assert!(v);
388 }
389
390 #[test]
391 fn test_polynomial_commitment() {
392 let deg = 31;
393 let mut rng = ark_std::test_rng();
394 let p = DensePolynomial::<Fr>::rand(deg, &mut rng);
395
396 type PCS = FRI_PCS<Fr, DensePolynomial<Fr>, Keccak256Hash<Fr>>;
397
398 let commitment = PCS::commit(&p);
399
400 // Verifier
401 let r = Fr::rand(&mut rng);
402
403 let (claimed_y, proof) = PCS::open(&p, r);
404
405 let v = PCS::verify(commitment, proof, r, claimed_y);
406 assert!(v);
407 }
408}