ecfft/
lib.rs

1extern crate alloc;
2
3pub mod ec;
4pub mod fftree;
5pub mod find_curve;
6pub mod utils;
7
8use ark_ff::PrimeField;
9use ec::Point;
10pub use fftree::FFTree;
11pub use fftree::Moiety;
12
13/// The interface for fields to build FFTrees.
14pub trait FftreeField: PrimeField {
15    fn build_fftree(n: usize) -> Option<FFTree<Self>>;
16}
17
18pub mod secp256k1 {
19    use super::FFTree;
20    use super::FftreeField;
21    use super::Point;
22    use crate::ec::find_isogeny_chain;
23    use crate::ec::GoodCurve;
24    use ark_ff::Fp256;
25    use ark_ff::MontBackend;
26    use ark_ff::MontConfig;
27    use ark_ff::MontFp as F;
28    use ark_ff::Zero;
29
30    /// Secp256k1's field
31    #[derive(MontConfig)]
32    #[modulus = "115792089237316195423570985008687907853269984665640564039457584007908834671663"]
33    #[generator = "3"]
34    #[small_subgroup_base = "3"]
35    #[small_subgroup_power = "1"]
36    pub struct FqConfig;
37    pub type Fp = Fp256<MontBackend<FqConfig, 4>>;
38
39    impl FftreeField for Fp {
40        fn build_fftree(n: usize) -> Option<FFTree<Self>> {
41            assert!(n.is_power_of_two());
42            let log_n = n.ilog2();
43
44            // Curve with 2^36 | #E
45            let curve = GoodCurve::new_odd(
46                F!("31172306031375832341232376275243462303334845584808513005362718476441963632613"),
47                F!("45508371059383884471556188660911097844526467659576498497548207627741160623272"),
48            );
49            let coset_offset = Point::new(
50                F!("105623886150579165427389078198493427091405550492761682382732004625374789850161"),
51                F!("7709812624542158994629670452026922591039826164720902911013234773380889499231"),
52                curve,
53            );
54            let subgroup_generator = Point::new(
55                F!("41293412487153066667050767300223451435019201659857889215769525847559135483332"),
56                F!("73754924733368840065089190002333366411120578552679996887076912271884749237510"),
57                curve,
58            );
59            let subgroup_two_addicity = 36;
60
61            // FFTree size is too large for our generator
62            if log_n >= subgroup_two_addicity {
63                return None;
64            }
65
66            // get a generator of a subgroup with order `n`
67            let mut generator = subgroup_generator;
68            for _ in 0..subgroup_two_addicity - log_n {
69                generator += generator;
70            }
71
72            // generate the FFTree leaf nodes
73            let mut leaves = vec![Self::zero(); n];
74            let mut acc = Point::zero();
75            for x in &mut leaves {
76                *x = (coset_offset + acc).x;
77                acc += generator;
78            }
79
80            let isogenies = find_isogeny_chain(generator);
81            let rational_maps = isogenies.into_iter().map(|isogeny| isogeny.r).collect();
82
83            Some(FFTree::new(leaves, rational_maps))
84        }
85    }
86
87    #[cfg(test)]
88    mod tests {
89        use super::FftreeField;
90        use super::Fp;
91        use crate::FFTree;
92        use crate::Moiety;
93        use ark_poly::univariate::DensePolynomial;
94        use ark_poly::DenseUVPolynomial;
95        use ark_poly::Polynomial;
96        use ark_serialize::CanonicalDeserialize;
97        use ark_serialize::CanonicalSerialize;
98        use rand::rngs::StdRng;
99        use rand::SeedableRng;
100        use std::sync::OnceLock;
101
102        static FFTREE: OnceLock<FFTree<Fp>> = OnceLock::new();
103
104        fn get_fftree() -> &'static FFTree<Fp> {
105            FFTREE.get_or_init(|| Fp::build_fftree(64).unwrap())
106        }
107
108        #[test]
109        fn evaluates_polynomial() {
110            let n = 64;
111            let fftree = get_fftree();
112            let mut rng = StdRng::from_seed([1; 32]);
113            let poly = DensePolynomial::rand(n - 1, &mut rng);
114            let eval_domain = fftree.subtree_with_size(n).eval_domain();
115
116            let ecfft_evals = fftree.enter(&poly);
117
118            let expected_evals: Vec<Fp> = eval_domain.iter().map(|x| poly.evaluate(x)).collect();
119            assert_eq!(expected_evals, ecfft_evals);
120        }
121
122        #[test]
123        fn extends_evaluations_from_s0_to_s1() {
124            let n = 64;
125            let fftree = get_fftree();
126            let eval_domain = fftree.subtree_with_size(n).eval_domain();
127            let mut rng = StdRng::from_seed([1; 32]);
128            let poly = DensePolynomial::rand(n / 2 - 1, &mut rng);
129            let (s0, s1): (Vec<Fp>, Vec<Fp>) = eval_domain.chunks(2).map(|s| (s[0], s[1])).unzip();
130            let s0_evals: Vec<Fp> = s0.iter().map(|x| poly.evaluate(x)).collect();
131
132            let s1_evals_actual = fftree.extend(&s0_evals, Moiety::S1);
133
134            let s1_evals_expected: Vec<Fp> = s1.iter().map(|x| poly.evaluate(x)).collect();
135            assert_eq!(s1_evals_expected, s1_evals_actual)
136        }
137
138        #[test]
139        fn extends_evaluations_from_s1_to_s0() {
140            let n = 64;
141            let fftree = get_fftree();
142            let eval_domain = fftree.subtree_with_size(n).eval_domain();
143            let mut rng = StdRng::from_seed([1; 32]);
144            let poly = DensePolynomial::rand(n / 2 - 1, &mut rng);
145            let (s0, s1): (Vec<Fp>, Vec<Fp>) = eval_domain.chunks(2).map(|c| (c[0], c[1])).unzip();
146            let s1_evals: Vec<Fp> = s1.iter().map(|x| poly.evaluate(x)).collect();
147
148            let s0_evals_actual = fftree.extend(&s1_evals, Moiety::S0);
149
150            let s0_evals_expected: Vec<Fp> = s0.iter().map(|x| poly.evaluate(x)).collect();
151            assert_eq!(s0_evals_expected, s0_evals_actual)
152        }
153
154        #[test]
155        fn deserialized_uncompressed_tree_works() {
156            let n = 64;
157            let fftree = get_fftree();
158            let mut rng = StdRng::from_seed([1; 32]);
159            let poly = DensePolynomial::rand(n - 1, &mut rng);
160            let eval_domain = fftree.subtree_with_size(n).eval_domain();
161
162            let mut fftree_bytes = Vec::new();
163            fftree.serialize_uncompressed(&mut fftree_bytes).unwrap();
164            let fftree = FFTree::deserialize_uncompressed(&*fftree_bytes).unwrap();
165            let ecfft_evals = fftree.enter(&poly);
166
167            let expected_evals: Vec<Fp> = eval_domain.iter().map(|x| poly.evaluate(x)).collect();
168            assert_eq!(expected_evals, ecfft_evals);
169        }
170
171        #[test]
172        fn deserialized_compressed_tree_works() {
173            let n = 64;
174            let fftree = get_fftree();
175            let mut rng = StdRng::from_seed([1; 32]);
176            let poly = DensePolynomial::rand(n - 1, &mut rng);
177            let eval_domain = fftree.subtree_with_size(n).eval_domain();
178
179            let mut fftree_bytes = Vec::new();
180            fftree.serialize_compressed(&mut fftree_bytes).unwrap();
181            let fftree = FFTree::deserialize_compressed(&*fftree_bytes).unwrap();
182            let ecfft_evals = fftree.enter(&poly);
183
184            let expected_evals: Vec<Fp> = eval_domain.iter().map(|x| poly.evaluate(x)).collect();
185            assert_eq!(expected_evals, ecfft_evals);
186        }
187    }
188}
189
190pub mod m31 {
191    use super::FFTree;
192    use super::FftreeField;
193    use super::Point;
194    use crate::ec::build_ec_fftree;
195    use crate::ec::ShortWeierstrassCurve;
196    pub use ark_ff_optimized::fp31::Fp;
197
198    impl FftreeField for Fp {
199        fn build_fftree(n: usize) -> Option<FFTree<Fp>> {
200            /// Supersingular curve with 2^31 | #E
201            const CURVE: ShortWeierstrassCurve<Fp> = ShortWeierstrassCurve::new(Fp(1), Fp(0));
202            const COSET_OFFSET: Point<ShortWeierstrassCurve<Fp>> =
203                Point::new(Fp(1048755163), Fp(279503108), CURVE);
204            const SUBGROUP_GENERATOR: Point<ShortWeierstrassCurve<Fp>> =
205                Point::new(Fp(1273083559), Fp(804329170), CURVE);
206            const SUBGORUP_TWO_ADDICITY: u32 = 28;
207
208            build_ec_fftree(
209                SUBGROUP_GENERATOR,
210                1 << SUBGORUP_TWO_ADDICITY,
211                COSET_OFFSET,
212                n,
213            )
214        }
215    }
216
217    // TODO: there's a lot of repetition between field tests. Should implement macro
218    // or loop at solutions to remove duplication of test logic.
219    #[cfg(test)]
220    mod tests {
221        use super::Fp;
222        use crate::fftree::FFTree;
223        use crate::FftreeField;
224        use ark_ff::One;
225        use ark_ff::Zero;
226        use ark_poly::univariate::DensePolynomial;
227        use ark_poly::DenseUVPolynomial;
228        use ark_poly::Polynomial;
229        use rand::rngs::StdRng;
230        use rand::SeedableRng;
231        use std::sync::OnceLock;
232
233        static FFTREE: OnceLock<FFTree<Fp>> = OnceLock::new();
234
235        fn get_fftree() -> &'static FFTree<Fp> {
236            FFTREE.get_or_init(|| Fp::build_fftree(64).unwrap())
237        }
238
239        #[test]
240        fn evaluates_polynomial() {
241            let n = 64;
242            let fftree = get_fftree();
243            let mut rng = StdRng::from_seed([1; 32]);
244            let poly = DensePolynomial::rand(n - 1, &mut rng);
245            let eval_domain = fftree.subtree_with_size(n).eval_domain();
246
247            let ecfft_evals = fftree.enter(&poly);
248
249            let expected_evals: Vec<Fp> = eval_domain.iter().map(|x| poly.evaluate(x)).collect();
250            assert_eq!(expected_evals, ecfft_evals);
251        }
252
253        #[test]
254        fn interpolates_evaluations() {
255            let fftree = get_fftree();
256            let one = Fp::one();
257            let zero = Fp::zero();
258            let coeffs: &[Fp] = &[one, one, Fp::from(5u8), zero, zero, one, zero, zero];
259            let evals = fftree.enter(coeffs);
260
261            let exit_coeffs = fftree.exit(&evals);
262
263            assert_eq!(coeffs, &exit_coeffs);
264        }
265
266        #[test]
267        fn determines_degree() {
268            let fftree = get_fftree();
269            let one = Fp::one();
270            let zero = Fp::zero();
271            let coeffs = &[one, one, one, zero, zero, one, zero, zero];
272            let evals = fftree.enter(coeffs);
273
274            let degree = fftree.degree(&evals);
275
276            let poly = DensePolynomial::from_coefficients_slice(coeffs);
277            assert_eq!(poly.degree(), degree);
278        }
279    }
280}
ecfft/lib.rs

ecfft/
lib.rs
