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