fri-commitment/src/lib.rs
src/lib.rsRaw
1#![allow(non_snake_case)]
2
3pub mod merkletree;
4use merkletree::{MerkleTreePoseidon as MT, Params as MTParams};
5
6use ark_ff::PrimeField;
7use ark_poly::{univariate::DensePolynomial, UVPolynomial};
8use ark_std::log2;
9use ark_std::marker::PhantomData;
10use ark_std::ops::Mul;
11use ark_std::{rand::Rng, UniformRand};
12
13pub struct FRI<F: PrimeField, P: UVPolynomial<F>> {
14 _f: PhantomData<F>,
15 _poly: PhantomData<P>,
16}
17
18impl<F: PrimeField, P: UVPolynomial<F>> FRI<F, P> {
19 pub fn new() -> Self {
20 Self {
21 _f: PhantomData,
22 _poly: PhantomData,
23 }
24 }
25
26 pub fn split(p: &P) -> (P, P) {
27 // let d = p.degree() + 1;
28 let d = p.coeffs().len();
29 if (d != 0) && (d & (d - 1) != 0) {
30 println!("d={:?}", d);
31 panic!("d should be a power of 2");
32 }
33
34 let coeffs = p.coeffs();
35 let odd: Vec<F> = coeffs.iter().step_by(2).cloned().collect();
36 let even: Vec<F> = coeffs.iter().skip(1).step_by(2).cloned().collect();
37
38 return (
39 P::from_coefficients_vec(odd),
40 P::from_coefficients_vec(even),
41 );
42 }
43
44 pub fn prove<R: Rng>(rng: &mut R, p: &P) -> (Vec<F>, Vec<F>, [F; 2]) {
45 // f_0(x) = fL_0(x^2) + x fR_0(x^2)
46 let mut f_i1 = p.clone();
47
48 // TODO challenge a_0
49 let mut f_is: Vec<P> = Vec::new();
50 f_is.push(p.clone());
51 let mut commitments: Vec<F> = Vec::new();
52 let mut mts: Vec<MT<F>> = Vec::new();
53 while f_i1.degree() > 1 {
54 let alpha_i = F::from(3_u64); // TODO: WIP, defined by Verifier (well, hash transcript)
55
56 let (fL_i, fR_i) = Self::split(&f_i1);
57
58 // compute f_{i+1}(x) = fL_i(x) + alpha_i * fR_i(x)
59 let aux = DensePolynomial::from_coefficients_slice(fR_i.coeffs());
60 f_i1 = fL_i.clone() + P::from_coefficients_slice(aux.mul(alpha_i).coeffs());
61 f_is.push(f_i1.clone());
62
63 // commit to f_{i+1}(x) = fL_i(x) + alpha_i * fR_i(x)
64 let (cm_i, mt_i) = MT::commit(f_i1.coeffs());
65 commitments.push(cm_i);
66 mts.push(mt_i);
67 }
68 let (fL_i, fR_i) = Self::split(&f_i1);
69 let constant_fL_l: F = fL_i.coeffs()[0].clone();
70 let constant_fR_l: F = fR_i.coeffs()[0].clone();
71
72 // TODO this will be a hash from the transcript
73 // V sets rand z \in \mathbb{F} challenge
74 let z = F::from(10_u64);
75
76 let mut evals: Vec<F> = Vec::new();
77 // TODO this will be done inside the prev loop, now it is here just for clarity
78 // evaluate f_i(z^{2^i})
79 for i in 0..f_is.len() {
80 // TODO check usage of .pow(u64)
81 let z_2i = z.pow([2_u64.pow(i as u32)]); // z^{2^i}
82 let neg_z_2i = z_2i.neg();
83 let eval_i = f_is[i].evaluate(&z_2i);
84 evals.push(eval_i);
85 let eval_i = f_is[i].evaluate(&neg_z_2i);
86 evals.push(eval_i);
87 }
88
89 // TODO return also the commitment_proofs
90 // return: Comm(f_i(x)), f_i(+-z^{2^i}), constant values {f_l^L, f_l^R}
91 (commitments, evals, [constant_fL_l, constant_fR_l])
92 }
93
94 pub fn verify(commitments: Vec<F>, evals: Vec<F>, constants: [F; 2]) -> bool {
95 let z = F::from(10_u64); // TODO this will be a hash from the transcript
96
97 // TODO check commitments.len()==evals.len()/2
98
99 for i in (0..evals.len()).step_by(2) {
100 let alpha_i = F::from(3_u64); // TODO: WIP, defined by Verifier (well, hash transcript)
101
102 let z_2i = z.pow([2_u64.pow((i as u32) / 2)]); // z^{2^i}
103 // take f_i(z^2) from evals
104 let fi_z = evals[i];
105 let neg_fi_z = evals[i + 1];
106 // compute f_i^L(z^2), f_i^R(z^2) from the linear combination
107 let L = (fi_z + neg_fi_z) * F::from(2_u32).inverse().unwrap();
108 let R = (fi_z - neg_fi_z) * (F::from(2_u32) * z_2i).inverse().unwrap();
109
110 // compute f_{i+1}(z^2) = f_i^L(z^2) + a_i f_i^R(z^2)
111 let next_fi_z2 = L + alpha_i * R;
112
113 // check: obtained f_{i+1}(z^2) == evals.f_{i+1}(z^2) (=evals[i+2])
114 if i < evals.len() - 2 {
115 if next_fi_z2 != evals[i + 2] {
116 println!("\nerr, i={:?}", i);
117 println!(" next_fi^z2 {:?}", next_fi_z2.to_string());
118 println!(" e[i] {:?}", evals[i + 2].to_string());
119 panic!("should f_i+1(z^2) == evals.f_i+1(z^2) (=evals[i+2])");
120 }
121 }
122
123 // check commitment opening
124 // TODO
125
126 // last iteration, check constant values equal to the obtained f_i^L(z^{2^i}),
127 // f_i^R(z^{2^i})
128 if i == evals.len() - 2 {
129 if L != constants[0] {
130 panic!("constant L not equal");
131 }
132 if R != constants[1] {
133 println!("R {:?}\n {:?}", R.to_string(), constants[1].to_string());
134 panic!("constant R not equal");
135 }
136 }
137 }
138
139 true
140 }
141}
142
143#[cfg(test)]
144mod tests {
145 use super::*;
146 use ark_ff::Field;
147 use ark_std::UniformRand;
148 pub type Fr = ark_bn254::Fr; // scalar field
149 use ark_poly::univariate::DensePolynomial;
150 use ark_poly::Polynomial;
151
152 #[test]
153 fn test_split() {
154 let mut rng = ark_std::test_rng();
155 let deg = 7;
156 let p = DensePolynomial::<Fr>::rand(deg, &mut rng);
157 assert_eq!(p.degree(), deg);
158
159 type FRIC = FRI<Fr, DensePolynomial<Fr>>;
160 let (pL, pR) = FRIC::split(&p);
161
162 // check that f(z) == fL(x^2) + x * fR(x^2), for a rand z
163 let z = Fr::rand(&mut rng);
164 assert_eq!(
165 p.evaluate(&z),
166 pL.evaluate(&z.square()) + z * pR.evaluate(&z.square())
167 );
168 }
169
170 #[test]
171 fn test_prove() {
172 let mut rng = ark_std::test_rng();
173
174 let deg = 15;
175 let p = DensePolynomial::<Fr>::rand(deg, &mut rng);
176 assert_eq!(p.degree(), deg);
177 // println!("p {:?}", p);
178
179 type FRIC = FRI<Fr, DensePolynomial<Fr>>;
180 // prover
181 let (commitments, evals, constvals) = FRIC::prove(&mut rng, &p);
182 // commitments contains the commitments to each f_0, f_1, ..., f_n, with n=log2(d)
183 assert_eq!(commitments.len(), log2(p.coeffs().len()) as usize - 1);
184 assert_eq!(evals.len(), 2 * log2(p.coeffs().len()) as usize);
185
186 let v = FRIC::verify(commitments, evals, constvals);
187 assert!(v);
188 }
189}