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

p3_commit/
domain.rs
