p3_commit/
domain.rs

1use alloc::vec::Vec;
2
3use itertools::Itertools;
4use p3_field::{
5    batch_multiplicative_inverse, cyclic_subgroup_coset_known_order, ExtensionField, Field,
6    TwoAdicField,
7};
8use p3_matrix::dense::RowMajorMatrix;
9use p3_matrix::Matrix;
10use p3_util::{log2_ceil_usize, log2_strict_usize};
11
12#[derive(Debug)]
13pub struct LagrangeSelectors<T> {
14    pub is_first_row: T,
15    pub is_last_row: T,
16    pub is_transition: T,
17    pub inv_zeroifier: T,
18}
19
20pub trait PolynomialSpace: Copy {
21    type Val: Field;
22
23    fn size(&self) -> usize;
24
25    fn first_point(&self) -> Self::Val;
26
27    // This is only defined for cosets.
28    fn next_point<Ext: ExtensionField<Self::Val>>(&self, x: Ext) -> Option<Ext>;
29
30    // There are many choices for this, but we must pick a canonical one
31    // for both prover/verifier determinism and LDE caching.
32    fn create_disjoint_domain(&self, min_size: usize) -> Self;
33
34    /// Split this domain into `num_chunks` even chunks.
35    /// `num_chunks` is assumed to be a power of two.
36    fn split_domains(&self, num_chunks: usize) -> Vec<Self>;
37    // Split the evals into chunks of evals, corresponding to each domain
38    // from `split_domains`.
39    fn split_evals(
40        &self,
41        num_chunks: usize,
42        evals: RowMajorMatrix<Self::Val>,
43    ) -> Vec<RowMajorMatrix<Self::Val>>;
44
45    fn zp_at_point<Ext: ExtensionField<Self::Val>>(&self, point: Ext) -> Ext;
46
47    // Unnormalized
48    fn selectors_at_point<Ext: ExtensionField<Self::Val>>(
49        &self,
50        point: Ext,
51    ) -> LagrangeSelectors<Ext>;
52
53    // Unnormalized
54    fn selectors_on_coset(&self, coset: Self) -> LagrangeSelectors<Vec<Self::Val>>;
55}
56
57#[derive(Copy, Clone, Debug)]
58pub struct TwoAdicMultiplicativeCoset<Val: TwoAdicField> {
59    pub log_n: usize,
60    pub shift: Val,
61}
62
63impl<Val: TwoAdicField> TwoAdicMultiplicativeCoset<Val> {
64    fn gen(&self) -> Val {
65        Val::two_adic_generator(self.log_n)
66    }
67}
68
69impl<Val: TwoAdicField> PolynomialSpace for TwoAdicMultiplicativeCoset<Val> {
70    type Val = Val;
71
72    fn size(&self) -> usize {
73        1 << self.log_n
74    }
75
76    fn first_point(&self) -> Self::Val {
77        self.shift
78    }
79    fn next_point<Ext: ExtensionField<Val>>(&self, x: Ext) -> Option<Ext> {
80        Some(x * self.gen())
81    }
82
83    fn create_disjoint_domain(&self, min_size: usize) -> Self {
84        Self {
85            log_n: log2_ceil_usize(min_size),
86            shift: self.shift * Val::generator(),
87        }
88    }
89    fn zp_at_point<Ext: ExtensionField<Val>>(&self, point: Ext) -> Ext {
90        (point * self.shift.inverse()).exp_power_of_2(self.log_n) - Ext::one()
91    }
92
93    fn split_domains(&self, num_chunks: usize) -> Vec<Self> {
94        let log_chunks = log2_strict_usize(num_chunks);
95        (0..num_chunks)
96            .map(|i| Self {
97                log_n: self.log_n - log_chunks,
98                shift: self.shift * self.gen().exp_u64(i as u64),
99            })
100            .collect()
101    }
102    fn split_evals(
103        &self,
104        num_chunks: usize,
105        evals: RowMajorMatrix<Self::Val>,
106    ) -> Vec<RowMajorMatrix<Self::Val>> {
107        // todo less copy
108        (0..num_chunks)
109            .map(|i| {
110                evals
111                    .as_view()
112                    .vertically_strided(num_chunks, i)
113                    .to_row_major_matrix()
114            })
115            .collect()
116    }
117
118    fn selectors_at_point<Ext: ExtensionField<Val>>(&self, point: Ext) -> LagrangeSelectors<Ext> {
119        let unshifted_point = point * self.shift.inverse();
120        let z_h = unshifted_point.exp_power_of_2(self.log_n) - Ext::one();
121        LagrangeSelectors {
122            is_first_row: z_h / (unshifted_point - Ext::one()),
123            is_last_row: z_h / (unshifted_point - self.gen().inverse()),
124            is_transition: unshifted_point - self.gen().inverse(),
125            inv_zeroifier: z_h.inverse(),
126        }
127    }
128
129    fn selectors_on_coset(&self, coset: Self) -> LagrangeSelectors<Vec<Val>> {
130        assert_eq!(self.shift, Val::one());
131        assert_ne!(coset.shift, Val::one());
132        assert!(coset.log_n >= self.log_n);
133        let rate_bits = coset.log_n - self.log_n;
134
135        let s_pow_n = coset.shift.exp_power_of_2(self.log_n);
136        // evals of Z_H(X) = X^n - 1
137        let evals = Val::two_adic_generator(rate_bits)
138            .powers()
139            .take(1 << rate_bits)
140            .map(|x| s_pow_n * x - Val::one())
141            .collect_vec();
142
143        let xs = cyclic_subgroup_coset_known_order(coset.gen(), coset.shift, 1 << coset.log_n)
144            .collect_vec();
145
146        let single_point_selector = |i: u64| {
147            let coset_i = self.gen().exp_u64(i);
148            let denoms = xs.iter().map(|&x| x - coset_i).collect_vec();
149            let invs = batch_multiplicative_inverse(&denoms);
150            evals
151                .iter()
152                .cycle()
153                .zip(invs)
154                .map(|(&z_h, inv)| z_h * inv)
155                .collect_vec()
156        };
157
158        let subgroup_last = self.gen().inverse();
159
160        LagrangeSelectors {
161            is_first_row: single_point_selector(0),
162            is_last_row: single_point_selector((1 << self.log_n) - 1),
163            is_transition: xs.into_iter().map(|x| x - subgroup_last).collect(),
164            inv_zeroifier: batch_multiplicative_inverse(&evals)
165                .into_iter()
166                .cycle()
167                .take(1 << coset.log_n)
168                .collect(),
169        }
170    }
171}
p3_commit/domain.rs

p3_commit/
domain.rs
