ark_poly_commit/linear_codes/
brakedown.rs

1use super::utils::SprsMat;
2use super::BrakedownPCParams;
3use super::LinCodeParametersInfo;
4use crate::linear_codes::utils::calculate_t;
5use crate::utils::ceil_div;
6use crate::utils::{ceil_mul, ent};
7use crate::{PCCommitterKey, PCUniversalParams, PCVerifierKey};
8
9use ark_crypto_primitives::crh::{CRHScheme, TwoToOneCRHScheme};
10use ark_crypto_primitives::merkle_tree::{Config, LeafParam, TwoToOneParam};
11use ark_ff::PrimeField;
12use ark_std::log2;
13use ark_std::rand::RngCore;
14use ark_std::vec::Vec;
15#[cfg(all(not(feature = "std"), target_arch = "aarch64"))]
16use num_traits::Float;
17
18impl<F, C, H> PCUniversalParams for BrakedownPCParams<F, C, H>
19where
20    F: PrimeField,
21    C: Config,
22    H: CRHScheme,
23{
24    fn max_degree(&self) -> usize {
25        usize::MAX
26    }
27}
28
29impl<F, C, H> PCCommitterKey for BrakedownPCParams<F, C, H>
30where
31    F: PrimeField,
32    C: Config,
33    H: CRHScheme,
34{
35    fn max_degree(&self) -> usize {
36        usize::MAX
37    }
38
39    fn supported_degree(&self) -> usize {
40        <BrakedownPCParams<F, C, H> as PCCommitterKey>::max_degree(self)
41    }
42}
43
44impl<F, C, H> PCVerifierKey for BrakedownPCParams<F, C, H>
45where
46    F: PrimeField,
47    C: Config,
48    H: CRHScheme,
49{
50    fn max_degree(&self) -> usize {
51        usize::MAX
52    }
53
54    fn supported_degree(&self) -> usize {
55        <BrakedownPCParams<F, C, H> as PCVerifierKey>::max_degree(self)
56    }
57}
58
59impl<F, C, H> LinCodeParametersInfo<C, H> for BrakedownPCParams<F, C, H>
60where
61    F: PrimeField,
62    C: Config,
63    H: CRHScheme,
64{
65    fn check_well_formedness(&self) -> bool {
66        self.check_well_formedness
67    }
68
69    fn distance(&self) -> (usize, usize) {
70        (self.rho_inv.1 * self.beta.0, self.rho_inv.0 * self.beta.1)
71    }
72
73    fn sec_param(&self) -> usize {
74        self.sec_param
75    }
76
77    fn compute_dimensions(&self, _n: usize) -> (usize, usize) {
78        (self.n, self.m)
79    }
80
81    fn leaf_hash_param(&self) -> &<<C as Config>::LeafHash as CRHScheme>::Parameters {
82        &self.leaf_hash_param
83    }
84
85    fn two_to_one_hash_param(
86        &self,
87    ) -> &<<C as Config>::TwoToOneHash as TwoToOneCRHScheme>::Parameters {
88        &self.two_to_one_hash_param
89    }
90
91    fn col_hash_params(&self) -> &<H as CRHScheme>::Parameters {
92        &self.col_hash_params
93    }
94}
95
96impl<F, C, H> BrakedownPCParams<F, C, H>
97where
98    F: PrimeField,
99    C: Config,
100    H: CRHScheme,
101{
102    /// Create a default UniversalParams, with the values from Fig. 2 from the paper.
103    pub fn default<R: RngCore>(
104        rng: &mut R,
105        poly_len: usize,
106        check_well_formedness: bool,
107        leaf_hash_param: LeafParam<C>,
108        two_to_one_hash_param: TwoToOneParam<C>,
109        col_hash_params: H::Parameters,
110    ) -> Self {
111        let sec_param = 128;
112        let a = (178, 1000);
113        let b = (61, 1000);
114        let r = (1521, 1000);
115        let base_len = 30;
116        let t = calculate_t::<F>(sec_param, (b.0 * r.1, b.1 * r.0), poly_len).unwrap(); // we want to get a rough idea what t is
117        let n = 1 << log2((ceil_div(2 * poly_len, t) as f64).sqrt().ceil() as usize);
118        let m = ceil_div(poly_len, n);
119        let c = Self::cn_const(a, b);
120        let d = Self::dn_const(a, b, r);
121        let ct = Constants { a, b, r, c, d };
122        let (a_dims, b_dims) = Self::mat_size(m, base_len, &ct);
123        let a_mats = Self::make_all(rng, &a_dims);
124        let b_mats = Self::make_all(rng, &b_dims);
125
126        Self::new(
127            sec_param,
128            a,
129            b,
130            r,
131            base_len,
132            n,
133            m,
134            a_dims,
135            b_dims,
136            a_mats,
137            b_mats,
138            check_well_formedness,
139            leaf_hash_param,
140            two_to_one_hash_param,
141            col_hash_params,
142        )
143    }
144
145    /// This function creates a UniversalParams. It does not check if the paramters are consistent/correct.
146    pub fn new(
147        sec_param: usize,
148        a: (usize, usize),
149        b: (usize, usize),
150        r: (usize, usize),
151        base_len: usize,
152        n: usize,
153        m: usize,
154        a_dims: Vec<(usize, usize, usize)>,
155        b_dims: Vec<(usize, usize, usize)>,
156        a_mats: Vec<SprsMat<F>>,
157        b_mats: Vec<SprsMat<F>>,
158        check_well_formedness: bool,
159        leaf_hash_param: LeafParam<C>,
160        two_to_one_hash_param: TwoToOneParam<C>,
161        col_hash_params: H::Parameters,
162    ) -> Self {
163        let m_ext = if a_dims.is_empty() {
164            ceil_mul(m, r)
165        } else {
166            Self::codeword_len(&a_dims, &b_dims)
167        };
168        let start = a_dims
169            .iter()
170            .scan(0, |acc, &(row, _, _)| {
171                *acc += row;
172                Some(*acc)
173            })
174            .collect::<Vec<_>>();
175        let end = b_dims
176            .iter()
177            .scan(m_ext, |acc, &(_, col, _)| {
178                *acc -= col;
179                Some(*acc)
180            })
181            .collect::<Vec<_>>();
182
183        Self {
184            sec_param,
185            alpha: a,
186            beta: b,
187            rho_inv: r,
188            base_len,
189            n,
190            m,
191            m_ext,
192            a_dims,
193            b_dims,
194            start,
195            end,
196            a_mats,
197            b_mats,
198            check_well_formedness,
199            leaf_hash_param,
200            two_to_one_hash_param,
201            col_hash_params,
202        }
203    }
204    /// mu = rho_inv - 1 - rho_inv * alpha
205    fn mu(a: (usize, usize), r: (usize, usize)) -> f64 {
206        let nom = r.0 * (a.1 - a.0) - r.1 * a.1;
207        let den = r.1 * a.1;
208        nom as f64 / den as f64
209    }
210    /// nu = beta + alpha * beta + 0.03
211    fn nu(a: (usize, usize), b: (usize, usize)) -> f64 {
212        let c = (3usize, 100usize);
213        let nom = b.0 * (a.1 + a.0) * c.1 + c.0 * b.1 * a.1;
214        let den = b.1 * a.1 * c.1;
215        nom as f64 / den as f64
216    }
217    /// cn_const
218    fn cn_const(a: (usize, usize), b: (usize, usize)) -> (f64, f64) {
219        let a = div(a);
220        let b = div(b);
221        let arg = 1.28 * b / a;
222        let nom = ent(b) + a * ent(arg);
223        let den = -b * arg.log2();
224        (nom, den)
225    }
226    /// cn
227    fn cn(n: usize, ct: &Constants) -> usize {
228        use ark_std::cmp::{max, min};
229        let b = ct.b;
230        let c = ct.c;
231        min(
232            max(ceil_mul(n, (32 * b.0, 25 * b.1)), 4 + ceil_mul(n, b)),
233            ((110f64 / (n as f64) + c.0) / c.1).ceil() as usize,
234        )
235    }
236    /// dn_const
237    fn dn_const(a: (usize, usize), b: (usize, usize), r: (usize, usize)) -> (f64, f64) {
238        let m = Self::mu(a, r);
239        let n = Self::nu(a, b);
240        let a = div(a);
241        let b = div(b);
242        let r = div(r);
243        let nm = n / m;
244        let nom = r * a * ent(b / r) + m * ent(nm);
245        let den = -a * b * nm.log2();
246        (nom, den)
247    }
248    /// dn
249    fn dn(n: usize, ct: &Constants) -> usize {
250        use ark_std::cmp::min;
251        let b = ct.b;
252        let r = ct.r;
253        let d = ct.d;
254        min(
255            ceil_mul(n, (2 * b.0, b.1))
256                + ((ceil_mul(n, r) - n + 110) as f64 / F::MODULUS_BIT_SIZE as f64).ceil() as usize, // 2 * beta * n  + n * (r - 1 + 110/n)
257            ((110f64 / (n as f64) + d.0) / d.1).ceil() as usize,
258        )
259    }
260    fn mat_size(
261        mut n: usize,
262        base_len: usize,
263        ct: &Constants,
264    ) -> (Vec<(usize, usize, usize)>, Vec<(usize, usize, usize)>) {
265        let mut a_dims: Vec<(usize, usize, usize)> = Vec::default();
266        let a = ct.a;
267        let r = ct.r;
268
269        while n >= base_len {
270            let m = ceil_mul(n, a);
271            let cn = Self::cn(n, ct);
272            let cn = if cn < m { cn } else { m }; // can't generate more nonzero entries than there are columns
273            a_dims.push((n, m, cn));
274            n = m;
275        }
276
277        let b_dims = a_dims
278            .iter()
279            .map(|&(an, am, _)| {
280                let n = ceil_mul(am, r);
281                let m = ceil_mul(an, r) - an - n;
282                let dn = Self::dn(n, ct);
283                let dn = if dn < m { dn } else { m }; // can't generate more nonzero entries than there are columns
284                (n, m, dn)
285            })
286            .collect::<Vec<_>>();
287        (a_dims, b_dims)
288    }
289
290    /// This function computes the codeword length
291    /// Notice that it assumes the input is bigger than base_len (i.e., a_dim is not empty)
292    pub(crate) fn codeword_len(
293        a_dims: &[(usize, usize, usize)],
294        b_dims: &[(usize, usize, usize)],
295    ) -> usize {
296        b_dims.iter().map(|(_, col, _)| col).sum::<usize>() + // Output v of the recursive encoding
297        a_dims.iter().map(|(row, _, _)| row).sum::<usize>() + // Input x to the recursive encoding
298        b_dims.last().unwrap().0 // Output z of the last step of recursion
299    }
300
301    /// Create a matrix with `n` rows and `m` columns and `d` non-zero entries in each row.
302    /// This function creates a list for entries of each columns and calls the constructor
303    /// from `SprsMat`. It leverages Fisher–Yates shuffle for choosing `d` indices in each
304    /// row.
305    fn make_mat<R: RngCore>(n: usize, m: usize, d: usize, rng: &mut R) -> SprsMat<F> {
306        let mut tmp: Vec<usize> = (0..m).collect();
307        let mut mat: Vec<Vec<(usize, F)>> = vec![vec![]; m];
308        for i in 0..n {
309            // Fisher–Yates shuffle algorithm
310            let idxs = {
311                (0..d)
312                    .map(|j| {
313                        let r = rng.next_u64() as usize % (m - j);
314                        tmp.swap(r, m - 1 - j);
315                        tmp[m - 1 - j]
316                    })
317                    .collect::<Vec<usize>>()
318            };
319            // Sampling values for each non-zero entry
320            for j in idxs {
321                mat[j].push((
322                    i,
323                    loop {
324                        let r = F::rand(rng);
325                        if r != F::zero() {
326                            break r;
327                        }
328                    },
329                ))
330            }
331        }
332        SprsMat::<F>::new_from_columns(n, m, d, &mat)
333    }
334
335    fn make_all<R: RngCore>(rng: &mut R, dims: &[(usize, usize, usize)]) -> Vec<SprsMat<F>> {
336        dims.iter()
337            .map(|(n, m, d)| Self::make_mat(*n, *m, *d, rng))
338            .collect::<Vec<_>>()
339    }
340}
341
342#[inline]
343fn div(a: (usize, usize)) -> f64 {
344    a.0 as f64 / a.1 as f64
345}
346
347struct Constants {
348    a: (usize, usize),
349    b: (usize, usize),
350    r: (usize, usize),
351    c: (f64, f64),
352    d: (f64, f64),
353}
ark_poly_commit/linear_codes/brakedown.rs

ark_poly_commit/linear_codes/
brakedown.rs
