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