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