ark_poly_commit/linear_codes/
data_structures.rs

1use crate::{linear_codes::utils::SprsMat, utils::Matrix, PCCommitment, PCCommitmentState};
2use ark_crypto_primitives::{
3    crh::CRHScheme,
4    merkle_tree::{Config, LeafParam, Path, TwoToOneParam},
5};
6use ark_ff::PrimeField;
7use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
8#[cfg(not(feature = "std"))]
9use ark_std::vec::Vec;
10use ark_std::{marker::PhantomData, rand::RngCore};
11
12#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
13#[derivative(Clone(bound = ""), Debug(bound = ""))]
14/// The public parameters for Brakedown PCS.
15pub struct BrakedownPCParams<F: PrimeField, C: Config, H: CRHScheme> {
16    /// The security parameter
17    pub(crate) sec_param: usize,
18    /// alpha in the paper
19    pub(crate) alpha: (usize, usize),
20    /// beta in the paper
21    pub(crate) beta: (usize, usize),
22    /// The inverse of the code rate.
23    pub(crate) rho_inv: (usize, usize),
24    /// Threshold of the base case to encode with RS
25    pub(crate) base_len: usize,
26    /// Length of each column in the matrix that represents the polynomials
27    pub(crate) n: usize,
28    /// Length of each row in the matrix that represents the polynomials
29    pub(crate) m: usize,
30    /// Length of each row in the matrix that represents the polynomials, **after encoding**
31    pub(crate) m_ext: usize,
32    /// Constarints on A matrices. `a_dims[i]` is `(n, m, c)`, where `n` is
33    /// the number of rows, `m` is the number of columns, `c` is the number of
34    /// non-zero elements in each row, for the matrix A in the `i`th step of
35    /// the encoding.
36    pub(crate) a_dims: Vec<(usize, usize, usize)>,
37    /// Same as `a_dims`, but for B matrices.
38    pub(crate) b_dims: Vec<(usize, usize, usize)>,
39    /// By having `a_dims` and `b_dims`, we compute a vector of indices that
40    /// specfies where is the beginning of the sub-chunk that we need to
41    /// encode during the recursive encoding. Notice that we do not recurse
42    /// in this implementation, instead we do it iteratively.
43    pub(crate) start: Vec<usize>,
44    /// Same as `start`, but stores the end index of those chunks.
45    pub(crate) end: Vec<usize>,
46    /// A vector of all A matrices we need for encoding.
47    pub(crate) a_mats: Vec<SprsMat<F>>,
48    /// A vector of all B matrices we need for encoding.
49    pub(crate) b_mats: Vec<SprsMat<F>>,
50    /// This is a flag which determines if the random linear combination is done.
51    pub(crate) check_well_formedness: bool,
52    /// Parameters for hash function of Merkle tree leaves
53    #[derivative(Debug = "ignore")]
54    pub(crate) leaf_hash_param: LeafParam<C>,
55    /// Parameters for hash function of Merke tree combining two nodes into one
56    #[derivative(Debug = "ignore")]
57    pub(crate) two_to_one_hash_param: TwoToOneParam<C>,
58    // Parameters for obtaining leaf digest from leaf value.
59    #[derivative(Debug = "ignore")]
60    pub(crate) col_hash_params: H::Parameters,
61}
62
63#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
64#[derivative(Clone(bound = ""), Debug(bound = ""))]
65/// The public parameters for Ligero PCS.
66pub struct LigeroPCParams<F: PrimeField, C: Config, H: CRHScheme> {
67    pub(crate) _field: PhantomData<F>,
68    /// The security parameter
69    pub(crate) sec_param: usize,
70    /// The inverse of the code rate.
71    pub(crate) rho_inv: usize,
72    /// This is a flag which determines if the random linear combination is done.
73    pub(crate) check_well_formedness: bool,
74    /// Parameters for hash function of Merkle tree leaves
75    #[derivative(Debug = "ignore")]
76    pub(crate) leaf_hash_param: LeafParam<C>,
77    /// Parameters for hash function of Merke tree combining two nodes into one
78    #[derivative(Debug = "ignore")]
79    pub(crate) two_to_one_hash_param: TwoToOneParam<C>,
80    // Parameters for obtaining leaf digest from leaf value.
81    #[derivative(Debug = "ignore")]
82    pub(crate) col_hash_params: H::Parameters,
83}
84
85#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
86#[derivative(Default(bound = ""), Clone(bound = ""), Debug(bound = ""))]
87pub(crate) struct Metadata {
88    pub(crate) n_rows: usize,
89    pub(crate) n_cols: usize,
90    pub(crate) n_ext_cols: usize,
91}
92
93/// The commitment to a polynomial is a root of the merkle tree,
94/// where each node is a hash of the column of the encoded coefficient matrix U.
95#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
96#[derivative(Default(bound = ""), Clone(bound = ""), Debug(bound = ""))]
97pub struct LinCodePCCommitment<C: Config> {
98    // number of rows resp. columns of the square matrix containing the coefficients of the polynomial
99    pub(crate) metadata: Metadata,
100    pub(crate) root: C::InnerDigest,
101}
102
103impl<C: Config> PCCommitment for LinCodePCCommitment<C> {
104    fn empty() -> Self {
105        LinCodePCCommitment::default()
106    }
107
108    fn has_degree_bound(&self) -> bool {
109        false
110    }
111}
112
113#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
114#[derivative(Default(bound = ""), Clone(bound = ""), Debug(bound = ""))]
115pub struct LinCodePCCommitmentState<F, H>
116where
117    F: PrimeField,
118    H: CRHScheme,
119{
120    pub(crate) mat: Matrix<F>,
121    pub(crate) ext_mat: Matrix<F>,
122    pub(crate) leaves: Vec<H::Output>,
123}
124
125impl<F, H> PCCommitmentState for LinCodePCCommitmentState<F, H>
126where
127    F: PrimeField,
128    H: CRHScheme,
129{
130    type Randomness = ();
131    fn empty() -> Self {
132        unimplemented!()
133    }
134
135    fn rand<R: RngCore>(
136        _num_queries: usize,
137        _has_degree_bound: bool,
138        _num_vars: Option<usize>,
139        _rng: &mut R,
140    ) -> Self::Randomness {
141        unimplemented!()
142    }
143}
144
145/// Proof of an individual linear code well-formedness check or opening
146#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
147#[derivative(Default(bound = ""), Clone(bound = ""), Debug(bound = ""))]
148pub(crate) struct LinCodePCProofSingle<F, C>
149where
150    F: PrimeField,
151    C: Config,
152{
153    /// For each of the indices in q, `paths` contains the path from the root of the merkle tree to the leaf
154    pub(crate) paths: Vec<Path<C>>,
155
156    /// v, s.t. E(v) = w
157    pub(crate) v: Vec<F>,
158
159    pub(crate) columns: Vec<Vec<F>>,
160}
161
162/// The Proof type for linear code PCS, which amounts to an array of individual proofs
163#[derive(Derivative, CanonicalSerialize, CanonicalDeserialize)]
164#[derivative(Default(bound = ""), Clone(bound = ""), Debug(bound = ""))]
165pub struct LinCodePCProof<F, C>
166where
167    F: PrimeField,
168    C: Config,
169{
170    pub(crate) opening: LinCodePCProofSingle<F, C>,
171    pub(crate) well_formedness: Option<Vec<F>>,
172}
173
174// Multiple poly at one point
175pub(crate) type LPCPArray<F, C> = Vec<LinCodePCProof<F, C>>;
ark_poly_commit/linear_codes/data_structures.rs

ark_poly_commit/linear_codes/
data_structures.rs
