ark_poly_commit/linear_codes/multilinear_brakedown/
mod.rs

1use crate::Error;
2
3use super::utils::tensor_vec;
4use super::{BrakedownPCParams, LinearEncode};
5use ark_crypto_primitives::{
6    crh::{CRHScheme, TwoToOneCRHScheme},
7    merkle_tree::Config,
8};
9use ark_ff::{Field, PrimeField};
10use ark_poly::{MultilinearExtension, Polynomial};
11#[cfg(not(feature = "std"))]
12use ark_std::vec::Vec;
13use ark_std::{log2, marker::PhantomData, rand::RngCore};
14
15mod tests;
16
17/// The multilinear Brakedown polynomial commitment scheme based on [[Brakedown]][bd].
18/// The scheme defaults to the naive batching strategy.
19///
20/// Note: The scheme currently does not support hiding.
21///
22/// [bd]: https://eprint.iacr.org/2021/1043.pdf
23pub struct MultilinearBrakedown<F: PrimeField, C: Config, P: MultilinearExtension<F>, H: CRHScheme>
24{
25    _phantom: PhantomData<(F, C, P, H)>,
26}
27
28impl<F, C, P, H> LinearEncode<F, C, P, H> for MultilinearBrakedown<F, C, P, H>
29where
30    F: PrimeField,
31    C: Config,
32    P: MultilinearExtension<F>,
33    <P as Polynomial<F>>::Point: Into<Vec<F>>,
34    H: CRHScheme,
35{
36    type LinCodePCParams = BrakedownPCParams<F, C, H>;
37
38    fn setup<R: RngCore>(
39        _max_degree: usize,
40        num_vars: Option<usize>,
41        rng: &mut R,
42        leaf_hash_param: <<C as Config>::LeafHash as CRHScheme>::Parameters,
43        two_to_one_hash_param: <<C as Config>::TwoToOneHash as TwoToOneCRHScheme>::Parameters,
44        col_hash_params: H::Parameters,
45    ) -> Self::LinCodePCParams {
46        Self::LinCodePCParams::default(
47            rng,
48            1 << num_vars.unwrap(),
49            true,
50            leaf_hash_param,
51            two_to_one_hash_param,
52            col_hash_params,
53        )
54    }
55
56    fn encode(msg: &[F], pp: &Self::LinCodePCParams) -> Result<Vec<F>, Error> {
57        if msg.len() != pp.m {
58            return Err(Error::EncodingError);
59        }
60        let cw_len = pp.m_ext;
61        let mut cw = Vec::with_capacity(cw_len);
62        cw.extend_from_slice(msg);
63
64        // Multiply by matrices A
65        for (i, &s) in pp.start.iter().enumerate() {
66            let mut src = pp.a_mats[i].row_mul(&cw[s - pp.a_dims[i].0..s]);
67            cw.append(&mut src);
68        }
69
70        // later we don't necessarily mutate in order, so we need the full vec now.
71        cw.resize(cw_len, F::zero());
72        // RS encode the last one
73        let rss = *pp.start.last().unwrap_or(&0);
74        let rsie = rss + pp.a_dims.last().unwrap_or(&(0, pp.m, 0)).1;
75        let rsoe = *pp.end.last().unwrap_or(&cw_len);
76        naive_reed_solomon(&mut cw, rss, rsie, rsoe);
77
78        // Come back
79        for (i, (&s, &e)) in pp.start.iter().zip(&pp.end).enumerate() {
80            let src = &pp.b_mats[i].row_mul(&cw[s..e]);
81            cw[e..e + pp.b_dims[i].1].copy_from_slice(src);
82        }
83        Ok(cw.to_vec())
84    }
85
86    fn poly_to_vec(polynomial: &P) -> Vec<F> {
87        polynomial.to_evaluations()
88    }
89
90    fn point_to_vec(point: <P as Polynomial<F>>::Point) -> Vec<F> {
91        point
92    }
93
94    /// For a multilinear polynomial in n+m variables it returns a tuple for k={n,m}:
95    /// ((1-z_1)*(1-z_2)*...*(1_z_k), z_1*(1-z_2)*...*(1-z_k), ..., z_1*z_2*...*z_k)
96    fn tensor(
97        point: &<P as Polynomial<F>>::Point,
98        left_len: usize,
99        _right_len: usize,
100    ) -> (Vec<F>, Vec<F>) {
101        let point: Vec<F> = Self::point_to_vec(point.clone());
102
103        let split = log2(left_len) as usize;
104        let left = &point[..split];
105        let right = &point[split..];
106        (tensor_vec(left), tensor_vec(right))
107    }
108}
109
110// This RS encoding is on points 1, ..., oe - s without relying on FFTs
111fn naive_reed_solomon<F: Field>(cw: &mut [F], s: usize, ie: usize, oe: usize) {
112    let mut res = vec![F::zero(); oe - s];
113    let mut x = F::one();
114    for r in res.iter_mut() {
115        for j in (s..ie).rev() {
116            *r *= x;
117            *r += cw[j];
118        }
119        x += F::one();
120    }
121    cw[s..oe].copy_from_slice(&res);
122}
ark_poly_commit/linear_codes/multilinear_brakedown/mod.rs

ark_poly_commit/linear_codes/multilinear_brakedown/
mod.rs
