p3_commit/
encoder.rs

1//! Linear codes applied column-wise to a matrix.
2
3use p3_dft::TwoAdicSubgroupDft;
4use p3_field::{Field, TwoAdicField};
5use p3_matrix::Matrix;
6use p3_matrix::dense::RowMajorMatrix;
7
8/// A linear code applied to every column of a matrix.
9///
10/// The blanket impl below covers every [`TwoAdicSubgroupDft`], which restricts what an
11/// implementor may write: `impl<F: Field> Encoder<F> for MyEncoder` overlaps it and is rejected
12/// (E0119), since a downstream crate could implement [`TwoAdicSubgroupDft`] for `MyEncoder`. An
13/// impl must therefore name the concrete field(s) it encodes over, as in
14/// `impl Encoder<MyField> for MyEncoder`.
15///
16/// The randomized counterpart is `p3_zk_codes::ZkEncoding`, whose codewords additionally hide the
17/// message from a bounded number of queries.
18pub trait Encoder<F: Field> {
19    /// Encodes each column of `message` into a codeword.
20    ///
21    /// `message` has height `2^k`; the result has the same width and height
22    /// `2^(k + log_inv_rate)`. Output row `i` is codeword symbol `i`.
23    ///
24    /// # Panics
25    /// Panics if the height of `message` is not a power of two, or if the codeword height
26    /// `2^(k + log_inv_rate)` overflows `usize`.
27    fn encode_batch(&self, message: RowMajorMatrix<F>, log_inv_rate: usize) -> RowMajorMatrix<F>;
28
29    /// Encodes a coefficient matrix already padded to its final height.
30    ///
31    /// The original message occupies the first `height / 2^log_inv_rate` rows; the
32    /// caller must set the remaining entries to zero. Implementations may ignore
33    /// that tail and use the rate to avoid work on zero coefficients.
34    /// The default preserves the ordinary transform of the full padded matrix.
35    ///
36    /// # Panics
37    /// Panics if the height is not a power of two or the padding exceeds its height.
38    fn encode_batch_padded(
39        &self,
40        message: RowMajorMatrix<F>,
41        log_inv_rate: usize,
42    ) -> RowMajorMatrix<F> {
43        let log_height = p3_util::log2_strict_usize(message.height());
44        assert!(log_inv_rate <= log_height, "padding exceeds matrix height");
45        self.encode_batch(message, 0)
46    }
47}
48
49/// Reed-Solomon over the two-adic subgroup of order `2^(k + log_inv_rate)`: each column of
50/// `message` is the low-degree coefficient vector of a polynomial, and the codeword is its
51/// evaluation vector on that subgroup.
52impl<F: TwoAdicField, D: TwoAdicSubgroupDft<F>> Encoder<F> for D {
53    fn encode_batch(
54        &self,
55        mut message: RowMajorMatrix<F>,
56        log_inv_rate: usize,
57    ) -> RowMajorMatrix<F> {
58        if log_inv_rate > 0 {
59            // Appending zero rows extends every column's coefficient vector.
60            let len = message.values.len();
61            let padded_len = u32::try_from(log_inv_rate)
62                .ok()
63                .and_then(|rate| len.checked_shl(rate))
64                // `checked_shl` only rejects a shift amount that is too wide; it does not
65                // detect the value itself overflowing, so recovering `len` from the shifted
66                // result is what actually proves no bits were lost.
67                .filter(|&padded| padded >> log_inv_rate == len)
68                .expect("codeword length overflows usize");
69            let mut values = F::zero_vec(padded_len);
70            values[..len].copy_from_slice(&message.values);
71            message.values = values;
72        }
73        self.dft_batch(message).to_row_major_matrix()
74    }
75}
76
77#[cfg(test)]
78mod tests {
79    use alloc::vec;
80
81    use p3_baby_bear::BabyBear;
82    use p3_dft::{Radix2DFTSmallBatch, Radix2DitParallel, TwoAdicSubgroupDft};
83    use p3_field::PrimeCharacteristicRing;
84    use p3_matrix::Matrix;
85    use p3_matrix::dense::RowMajorMatrix;
86    use rand::SeedableRng;
87    use rand::rngs::SmallRng;
88
89    use super::Encoder;
90
91    /// `encode_batch` must agree with zero-padding the message and calling `dft_batch`.
92    fn check_matches_padded_dft<D: TwoAdicSubgroupDft<BabyBear>>(dft: &D) {
93        let mut rng = SmallRng::seed_from_u64(1);
94        let message = RowMajorMatrix::<BabyBear>::rand(&mut rng, 8, 3);
95
96        let mut padded = message.clone();
97        padded
98            .values
99            .resize(message.values.len() * 4, BabyBear::ZERO);
100        let expected = dft.dft_batch(padded.clone()).to_row_major_matrix();
101
102        assert_eq!(dft.encode_batch_padded(padded, 2), expected);
103        assert_eq!(dft.encode_batch(message, 2), expected);
104    }
105
106    #[test]
107    fn small_batch_encoder_matches_padded_dft() {
108        check_matches_padded_dft(&Radix2DFTSmallBatch::<BabyBear>::default());
109    }
110
111    #[test]
112    fn dit_parallel_encoder_matches_padded_dft() {
113        check_matches_padded_dft(&Radix2DitParallel::<BabyBear>::default());
114    }
115
116    #[test]
117    #[should_panic = "codeword length overflows usize"]
118    fn encode_batch_panics_when_the_codeword_length_overflows() {
119        let message = RowMajorMatrix::<BabyBear>::new(vec![BabyBear::ZERO; 2], 1);
120        let _ = Radix2DitParallel::<BabyBear>::default()
121            .encode_batch(message, usize::BITS as usize - 1);
122    }
123}
p3_commit/encoder.rs

p3_commit/
encoder.rs
