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