ark_poly_commit/
utils.rs

1use ark_ff::Field;
2use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
3#[cfg(all(not(feature = "std")))]
4use ark_std::vec::Vec;
5#[cfg(all(not(feature = "std"), target_arch = "aarch64"))]
6use num_traits::Float;
7#[cfg(feature = "parallel")]
8use rayon::{
9    iter::{IntoParallelIterator, IntoParallelRefIterator, ParallelIterator},
10    prelude::IndexedParallelIterator,
11};
12
13/// Takes as input a struct, and converts them to a series of bytes. All traits
14/// that implement `CanonicalSerialize` can be automatically converted to bytes
15/// in this manner.
16/// From jellyfish lib
17#[macro_export]
18macro_rules! to_bytes {
19    ($x:expr) => {{
20        let mut buf = ark_std::vec![];
21        ark_serialize::CanonicalSerialize::serialize_compressed($x, &mut buf).map(|_| buf)
22    }};
23}
24
25/// Entropy function
26pub(crate) fn ent(x: f64) -> f64 {
27    assert!(0f64 <= x && x <= 1f64);
28    if x == 0f64 || x == 1f64 {
29        0f64
30    } else {
31        -x * x.log2() - (1.0 - x) * (1.0 - x).log2()
32    }
33}
34
35/// ceil of a * b, where a is integer and b is a rational number
36#[inline]
37pub(crate) fn ceil_mul(a: usize, b: (usize, usize)) -> usize {
38    (a * b.0 + b.1 - 1) / b.1
39}
40
41/// Return ceil(x / y).
42pub(crate) fn ceil_div(x: usize, y: usize) -> usize {
43    // XXX. warning: this expression can overflow.
44    (x + y - 1) / y
45}
46
47#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
48#[derivative(Default(bound = ""), Clone(bound = ""), Debug(bound = ""))]
49pub struct Matrix<F: Field> {
50    pub(crate) n: usize,
51    pub(crate) m: usize,
52    entries: Vec<Vec<F>>,
53}
54
55impl<F: Field> Matrix<F> {
56    /// Returns a Matrix of dimensions n x m given a list of n * m field elements.
57    /// The list should be ordered row-first, i.e. [a11, ..., a1m, a21, ..., a2m, ...].
58    ///
59    /// # Panics
60    /// Panics if the dimensions do not match the length of the list
61    pub(crate) fn new_from_flat(n: usize, m: usize, entry_list: &[F]) -> Self {
62        assert_eq!(
63            entry_list.len(),
64            n * m,
65            "Invalid matrix construction: dimensions are {} x {} but entry vector has {} entries",
66            n,
67            m,
68            entry_list.len()
69        );
70
71        // TODO more efficient to run linearly?
72        let entries: Vec<Vec<F>> = (0..n)
73            .map(|row| (0..m).map(|col| entry_list[m * row + col]).collect())
74            .collect();
75
76        Self { n, m, entries }
77    }
78
79    /// Returns a Matrix given a list of its rows, each in turn represented as a list of field elements.
80    ///
81    /// # Panics
82    /// Panics if the sub-lists do not all have the same length.
83    pub(crate) fn new_from_rows(row_list: Vec<Vec<F>>) -> Self {
84        let m = row_list[0].len();
85
86        for row in row_list.iter().skip(1) {
87            assert_eq!(
88                row.len(),
89                m,
90                "Invalid matrix construction: not all rows have the same length"
91            );
92        }
93
94        Self {
95            n: row_list.len(),
96            m,
97            entries: row_list,
98        }
99    }
100
101    /// Returns the entry in position (i, j). **Indexing starts at 0 in both coordinates**,
102    /// i.e. the first element is in position (0, 0) and the last one in (n - 1, j - 1),
103    /// where n and m are the number of rows and columns, respectively.
104    ///
105    /// Index bound checks are waived for efficiency and behaviour under invalid indexing is undefined
106    #[cfg(test)]
107    pub(crate) fn entry(&self, i: usize, j: usize) -> F {
108        self.entries[i][j]
109    }
110
111    /// Returns self as a list of rows
112    pub(crate) fn rows(&self) -> Vec<Vec<F>> {
113        self.entries.clone()
114    }
115
116    /// Returns self as a list of columns
117    pub(crate) fn cols(&self) -> Vec<Vec<F>> {
118        (0..self.m)
119            .map(|col| (0..self.n).map(|row| self.entries[row][col]).collect())
120            .collect()
121    }
122
123    /// Returns the product v * self, where v is interpreted as a row vector. In other words,
124    /// it returns a linear combination of the rows of self with coefficients given by v.
125    ///
126    /// Panics if the length of v is different from the number of rows of self.
127    pub(crate) fn row_mul(&self, v: &[F]) -> Vec<F> {
128        assert_eq!(
129            v.len(),
130            self.n,
131            "Invalid row multiplication: vector has {} elements whereas each matrix column has {}",
132            v.len(),
133            self.n
134        );
135
136        cfg_into_iter!(0..self.m)
137            .map(|col| {
138                inner_product(
139                    v,
140                    &cfg_into_iter!(0..self.n)
141                        .map(|row| self.entries[row][col])
142                        .collect::<Vec<F>>(),
143                )
144            })
145            .collect()
146    }
147}
148
149#[inline]
150pub(crate) fn inner_product<F: Field>(v1: &[F], v2: &[F]) -> F {
151    ark_std::cfg_iter!(v1)
152        .zip(v2)
153        .map(|(li, ri)| *li * ri)
154        .sum()
155}
156
157#[inline]
158pub(crate) fn scalar_by_vector<F: Field>(s: F, v: &[F]) -> Vec<F> {
159    ark_std::cfg_iter!(v).map(|x| *x * s).collect()
160}
161
162#[inline]
163pub(crate) fn vector_sum<F: Field>(v1: &[F], v2: &[F]) -> Vec<F> {
164    ark_std::cfg_iter!(v1)
165        .zip(v2)
166        .map(|(li, ri)| *li + ri)
167        .collect()
168}
169
170#[inline]
171#[cfg(test)]
172pub(crate) fn to_field<F: Field>(v: Vec<u64>) -> Vec<F> {
173    v.iter().map(|x| F::from(*x)).collect::<Vec<F>>()
174}
175
176// TODO: replace by https://github.com/arkworks-rs/crypto-primitives/issues/112.
177#[cfg(test)]
178use ark_crypto_primitives::sponge::poseidon::PoseidonSponge;
179#[cfg(test)]
180use ark_ff::PrimeField;
181
182#[cfg(test)]
183pub(crate) fn test_sponge<F: PrimeField>() -> PoseidonSponge<F> {
184    use ark_crypto_primitives::sponge::{poseidon::PoseidonConfig, CryptographicSponge};
185    use ark_std::test_rng;
186
187    let full_rounds = 8;
188    let partial_rounds = 31;
189    let alpha = 17;
190
191    let mds = vec![
192        vec![F::one(), F::zero(), F::one()],
193        vec![F::one(), F::one(), F::zero()],
194        vec![F::zero(), F::one(), F::one()],
195    ];
196
197    let mut v = Vec::new();
198    let mut ark_rng = test_rng();
199
200    for _ in 0..(full_rounds + partial_rounds) {
201        let mut res = Vec::new();
202
203        for _ in 0..3 {
204            res.push(F::rand(&mut ark_rng));
205        }
206        v.push(res);
207    }
208    let config = PoseidonConfig::new(full_rounds, partial_rounds, alpha, mds, v, 2, 1);
209    PoseidonSponge::new(&config)
210}
211
212#[cfg(test)]
213pub(crate) mod tests {
214    use super::*;
215    use ark_bls12_377::Fr;
216
217    #[test]
218    fn test_matrix_constructor_flat() {
219        let entries: Vec<Fr> = to_field(vec![10, 100, 4, 67, 44, 50]);
220        let mat = Matrix::new_from_flat(2, 3, &entries);
221        assert_eq!(mat.entry(1, 2), Fr::from(50));
222    }
223
224    #[test]
225    fn test_matrix_constructor_flat_square() {
226        let entries: Vec<Fr> = to_field(vec![10, 100, 4, 67]);
227        let mat = Matrix::new_from_flat(2, 2, &entries);
228        assert_eq!(mat.entry(1, 1), Fr::from(67));
229    }
230
231    #[test]
232    #[should_panic(expected = "dimensions are 2 x 3 but entry vector has 5 entries")]
233    fn test_matrix_constructor_flat_panic() {
234        let entries: Vec<Fr> = to_field(vec![10, 100, 4, 67, 44]);
235        Matrix::new_from_flat(2, 3, &entries);
236    }
237
238    #[test]
239    fn test_matrix_constructor_rows() {
240        let rows: Vec<Vec<Fr>> = vec![
241            to_field(vec![10, 100, 4]),
242            to_field(vec![23, 1, 0]),
243            to_field(vec![55, 58, 9]),
244        ];
245        let mat = Matrix::new_from_rows(rows);
246        assert_eq!(mat.entry(2, 0), Fr::from(55));
247    }
248
249    #[test]
250    #[should_panic(expected = "not all rows have the same length")]
251    fn test_matrix_constructor_rows_panic() {
252        let rows: Vec<Vec<Fr>> = vec![
253            to_field(vec![10, 100, 4]),
254            to_field(vec![23, 1, 0]),
255            to_field(vec![55, 58]),
256        ];
257        Matrix::new_from_rows(rows);
258    }
259
260    #[test]
261    fn test_cols() {
262        let rows: Vec<Vec<Fr>> = vec![
263            to_field(vec![4, 76]),
264            to_field(vec![14, 92]),
265            to_field(vec![17, 89]),
266        ];
267
268        let mat = Matrix::new_from_rows(rows);
269
270        assert_eq!(mat.cols()[1], to_field(vec![76, 92, 89]));
271    }
272
273    #[test]
274    fn test_row_mul() {
275        let rows: Vec<Vec<Fr>> = vec![
276            to_field(vec![10, 100, 4]),
277            to_field(vec![23, 1, 0]),
278            to_field(vec![55, 58, 9]),
279        ];
280
281        let mat = Matrix::new_from_rows(rows);
282        let v: Vec<Fr> = to_field(vec![12, 41, 55]);
283        // by giving the result in the integers and then converting to Fr
284        // we ensure the test will still pass even if Fr changes
285        assert_eq!(mat.row_mul(&v), to_field::<Fr>(vec![4088, 4431, 543]));
286    }
287}
ark_poly_commit/utils.rs

ark_poly_commit/
utils.rs
