ark_poly_commit/linear_codes/
mod.rs

1use crate::{
2    linear_codes::{
3        data_structures::*,
4        utils::{calculate_t, get_indices_from_sponge},
5    },
6    to_bytes,
7    utils::{inner_product, Matrix},
8    Error, LabeledCommitment, LabeledPolynomial, PCCommitterKey, PCUniversalParams, PCVerifierKey,
9    PolynomialCommitment,
10};
11use ark_crypto_primitives::{
12    crh::{CRHScheme, TwoToOneCRHScheme},
13    merkle_tree::{Config, MerkleTree},
14    sponge::{Absorb, CryptographicSponge},
15};
16use ark_ff::PrimeField;
17use ark_poly::Polynomial;
18use ark_std::{borrow::Borrow, marker::PhantomData, rand::RngCore};
19#[cfg(not(feature = "std"))]
20use ark_std::{string::ToString, vec::Vec};
21
22#[cfg(feature = "parallel")]
23use rayon::iter::{IntoParallelIterator, IntoParallelRefIterator, ParallelIterator};
24
25mod data_structures;
26mod utils;
27
28mod brakedown;
29
30mod ligero;
31
32mod multilinear_brakedown;
33
34mod multilinear_ligero;
35mod univariate_ligero;
36
37pub use data_structures::{BrakedownPCParams, LigeroPCParams, LinCodePCProof};
38pub use multilinear_brakedown::MultilinearBrakedown;
39pub use multilinear_ligero::MultilinearLigero;
40pub use univariate_ligero::UnivariateLigero;
41
42const FIELD_SIZE_ERROR: &str = "This field is not suitable for the proposed parameters";
43
44/// For linear code PC schemes, the universal paramters, committer key
45/// and verifier key are all the same. This trait abstracts the common
46/// information contained in these.
47pub trait LinCodeParametersInfo<C, H>
48where
49    C: Config,
50    H: CRHScheme,
51{
52    /// Get the security parameter.
53    fn sec_param(&self) -> usize;
54
55    /// Get the distance of the code.
56    fn distance(&self) -> (usize, usize);
57
58    /// See whether there should be a well-formedness check.
59    fn check_well_formedness(&self) -> bool;
60
61    /// Compute the dimensions of the coefficient matrix.
62    fn compute_dimensions(&self, n: usize) -> (usize, usize);
63
64    /// Get the hash parameters for obtaining leaf digest from leaf value.
65    fn leaf_hash_param(&self) -> &<<C as Config>::LeafHash as CRHScheme>::Parameters;
66
67    /// Get the parameters for hashing nodes in the merkle tree.
68    fn two_to_one_hash_param(
69        &self,
70    ) -> &<<C as Config>::TwoToOneHash as TwoToOneCRHScheme>::Parameters;
71
72    /// Get the parameters for hashing a vector of values,
73    /// representing a column of the coefficient matrix, into a leaf value.
74    fn col_hash_params(&self) -> &H::Parameters;
75}
76
77/// A trait for linear codes.
78pub trait LinearEncode<F, C, P, H>
79where
80    F: PrimeField,
81    C: Config,
82    H: CRHScheme,
83    P: Polynomial<F>,
84{
85    /// For schemes like Brakedown and Ligero, PCCommiiterKey and
86    /// PCVerifierKey and PCUniversalParams are all the same.
87    type LinCodePCParams: PCUniversalParams
88        + PCCommitterKey
89        + PCVerifierKey
90        + LinCodeParametersInfo<C, H>
91        + Sync;
92
93    /// Does a default setup for the PCS.
94    fn setup<R: RngCore>(
95        max_degree: usize,
96        num_vars: Option<usize>,
97        rng: &mut R,
98        leaf_hash_param: <<C as Config>::LeafHash as CRHScheme>::Parameters,
99        two_to_one_hash_param: <<C as Config>::TwoToOneHash as TwoToOneCRHScheme>::Parameters,
100        col_hash_params: H::Parameters,
101    ) -> Self::LinCodePCParams;
102
103    /// Encode a message, which is interpreted as a vector of coefficients
104    /// of a polynomial of degree m - 1.
105    fn encode(msg: &[F], param: &Self::LinCodePCParams) -> Result<Vec<F>, Error>;
106
107    /// Represent the polynomial as either coefficients,
108    /// in the univariate case, or evaluations over
109    /// the Boolean hypercube, in the multilinear case.
110    fn poly_to_vec(polynomial: &P) -> Vec<F>;
111
112    /// Represent the query point as a vector of Field elements.
113    fn point_to_vec(point: P::Point) -> Vec<F>;
114
115    /// Arrange the coefficients of the polynomial into a matrix,
116    /// and apply encoding to each row.
117    /// Returns the tuple (original_matrix, encoded_matrix).
118    fn compute_matrices(polynomial: &P, param: &Self::LinCodePCParams) -> (Matrix<F>, Matrix<F>) {
119        let mut coeffs = Self::poly_to_vec(polynomial);
120
121        // 1. Computing the matrix dimensions.
122        let (n_rows, n_cols) = param.compute_dimensions(coeffs.len());
123
124        // padding the coefficient vector with zeroes
125        coeffs.resize(n_rows * n_cols, F::zero());
126
127        let mat = Matrix::new_from_flat(n_rows, n_cols, &coeffs);
128
129        // 2. Apply encoding row-wise
130        let rows = mat.rows();
131        let ext_mat = Matrix::new_from_rows(
132            cfg_iter!(rows)
133                .map(|r| Self::encode(r, param).unwrap())
134                .collect(),
135        );
136
137        (mat, ext_mat)
138    }
139
140    /// Tensor the query point z in the following sense:
141    /// For a polynomial p(X) represented by a matrix M
142    /// with n rows and m columns such that M_{i,j} = p_{i + n*j},
143    /// we define the tensoring of `z`: (a, b) = tensor(z, n, m) such that:
144    /// p(z) = b^T.M.a
145    /// returns the evaluation of p at z.
146    fn tensor(z: &P::Point, n: usize, m: usize) -> (Vec<F>, Vec<F>);
147}
148
149/// Any linear-code-based commitment scheme.
150pub struct LinearCodePCS<L, F, P, C, H>
151where
152    F: PrimeField,
153    C: Config,
154    P: Polynomial<F>,
155    H: CRHScheme,
156    L: LinearEncode<F, C, P, H>,
157{
158    _phantom: PhantomData<(L, F, P, C, H)>,
159}
160
161impl<L, F, P, C, H> PolynomialCommitment<F, P> for LinearCodePCS<L, F, P, C, H>
162where
163    L: LinearEncode<F, C, P, H>,
164    F: PrimeField + Absorb,
165    P: Polynomial<F>,
166    C: Config + 'static,
167    Vec<F>: Borrow<<H as CRHScheme>::Input>,
168    H::Output: Into<C::Leaf> + Send,
169    C::Leaf: Sized + Clone + Default + Send + AsRef<C::Leaf>,
170    H: CRHScheme + 'static,
171{
172    type UniversalParams = L::LinCodePCParams;
173
174    type CommitterKey = L::LinCodePCParams;
175
176    type VerifierKey = L::LinCodePCParams;
177
178    type Commitment = LinCodePCCommitment<C>;
179
180    type CommitmentState = LinCodePCCommitmentState<F, H>;
181
182    type Proof = LPCPArray<F, C>;
183
184    type BatchProof = Vec<Self::Proof>;
185
186    type Error = Error;
187
188    /// This is only a default setup with reasonable parameters.
189    /// To create your own public parameters (from which vk/ck can be derived by `trim`),
190    /// see the documentation for `BrakedownPCUniversalParams` or `LigeroPCUniversalParams`.
191    fn setup<R: RngCore>(
192        max_degree: usize,
193        num_vars: Option<usize>,
194        rng: &mut R,
195    ) -> Result<Self::UniversalParams, Self::Error> {
196        let leaf_hash_param = <C::LeafHash as CRHScheme>::setup(rng).unwrap();
197        let two_to_one_hash_param = <C::TwoToOneHash as TwoToOneCRHScheme>::setup(rng)
198            .unwrap()
199            .clone();
200        let col_hash_params = <H as CRHScheme>::setup(rng).unwrap();
201        let pp = L::setup::<R>(
202            max_degree,
203            num_vars,
204            rng,
205            leaf_hash_param,
206            two_to_one_hash_param,
207            col_hash_params,
208        );
209        let real_max_degree = <Self::UniversalParams as PCUniversalParams>::max_degree(&pp);
210        if max_degree > real_max_degree || real_max_degree == 0 {
211            return Err(Error::InvalidParameters(FIELD_SIZE_ERROR.to_string()));
212        }
213        Ok(pp)
214    }
215
216    fn trim(
217        pp: &Self::UniversalParams,
218        _supported_degree: usize,
219        _supported_hiding_bound: usize,
220        _enforced_degree_bounds: Option<&[usize]>,
221    ) -> Result<(Self::CommitterKey, Self::VerifierKey), Self::Error> {
222        if <Self::UniversalParams as PCUniversalParams>::max_degree(pp) == 0 {
223            return Err(Error::InvalidParameters(FIELD_SIZE_ERROR.to_string()));
224        }
225        Ok((pp.clone(), pp.clone()))
226    }
227
228    fn commit<'a>(
229        ck: &Self::CommitterKey,
230        polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<F, P>>,
231        _rng: Option<&mut dyn RngCore>,
232    ) -> Result<
233        (
234            Vec<LabeledCommitment<Self::Commitment>>,
235            Vec<Self::CommitmentState>,
236        ),
237        Self::Error,
238    >
239    where
240        P: 'a,
241    {
242        let mut commitments = Vec::new();
243        let mut states = Vec::new();
244
245        for labeled_polynomial in polynomials {
246            let polynomial = labeled_polynomial.polynomial();
247
248            // 1. Arrange the coefficients of the polynomial into a matrix,
249            // and apply encoding to get `ext_mat`.
250            let (mat, ext_mat) = L::compute_matrices(polynomial, ck);
251            let n_rows = mat.n;
252            let n_cols = mat.m;
253            let n_ext_cols = ext_mat.m;
254
255            // 2. Create the Merkle tree from the hashes of each column.
256            let ext_mat_cols = ext_mat.cols();
257            let leaves: Vec<H::Output> = cfg_into_iter!(ext_mat_cols)
258                .map(|col| {
259                    H::evaluate(ck.col_hash_params(), col)
260                        .map_err(|_| Error::HashingError)
261                        .unwrap()
262                })
263                .collect();
264            let state = Self::CommitmentState {
265                mat,
266                ext_mat,
267                leaves,
268            };
269            let mut leaves: Vec<C::Leaf> =
270                state.leaves.clone().into_iter().map(|h| h.into()).collect(); // TODO cfg_inter
271            let col_tree = create_merkle_tree::<C>(
272                &mut leaves,
273                ck.leaf_hash_param(),
274                ck.two_to_one_hash_param(),
275            )?;
276
277            // 3. Obtain the MT root
278            let root = col_tree.root();
279
280            // 4. The commitment is just the root, but since each commitment could be to a differently-sized polynomial, we also add some metadata.
281            let commitment = LinCodePCCommitment {
282                metadata: Metadata {
283                    n_rows,
284                    n_cols,
285                    n_ext_cols,
286                },
287                root,
288            };
289
290            commitments.push(LabeledCommitment::new(
291                labeled_polynomial.label().clone(),
292                commitment,
293                None,
294            ));
295            states.push(state);
296        }
297        Ok((commitments, states))
298    }
299
300    fn open<'a>(
301        ck: &Self::CommitterKey,
302        _labeled_polynomials: impl IntoIterator<Item = &'a LabeledPolynomial<F, P>>,
303        commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
304        point: &'a P::Point,
305        sponge: &mut impl CryptographicSponge,
306        states: impl IntoIterator<Item = &'a Self::CommitmentState>,
307        _rng: Option<&mut dyn RngCore>,
308    ) -> Result<Self::Proof, Self::Error>
309    where
310        P: 'a,
311        Self::CommitmentState: 'a,
312        Self::Commitment: 'a,
313    {
314        let mut proof_array = LPCPArray::default();
315
316        for (labeled_commitment, state) in commitments.into_iter().zip(states) {
317            let commitment = labeled_commitment.commitment();
318            let n_rows = commitment.metadata.n_rows;
319            let n_cols = commitment.metadata.n_cols;
320
321            // 1. Arrange the coefficients of the polynomial into a matrix,
322            // and apply encoding to get `ext_mat`.
323            // 2. Create the Merkle tree from the hashes of each column.
324            let Self::CommitmentState {
325                mat,
326                ext_mat,
327                leaves: col_hashes,
328            } = state;
329            let mut col_hashes: Vec<C::Leaf> =
330                col_hashes.clone().into_iter().map(|h| h.into()).collect(); // TODO cfg_inter
331
332            let col_tree = create_merkle_tree::<C>(
333                &mut col_hashes,
334                ck.leaf_hash_param(),
335                ck.two_to_one_hash_param(),
336            )?;
337
338            // 3. Generate vector `b` to left-multiply the matrix.
339            let (_, b) = L::tensor(point, n_cols, n_rows);
340
341            sponge.absorb(&to_bytes!(&commitment.root).map_err(|_| Error::TranscriptError)?);
342
343            // If we are checking well-formedness, we need to compute the well-formedness proof (which is just r.M) and append it to the transcript.
344            let well_formedness = if ck.check_well_formedness() {
345                let r = sponge.squeeze_field_elements::<F>(n_rows);
346                let v = mat.row_mul(&r);
347
348                sponge.absorb(&v);
349                Some(v)
350            } else {
351                None
352            };
353
354            let point_vec = L::point_to_vec(point.clone());
355            sponge.absorb(&point_vec);
356
357            proof_array.push(LinCodePCProof {
358                // Compute the opening proof and append b.M to the transcript.
359                opening: generate_proof(
360                    ck.sec_param(),
361                    ck.distance(),
362                    &b,
363                    &mat,
364                    &ext_mat,
365                    &col_tree,
366                    sponge,
367                )?,
368                well_formedness,
369            });
370        }
371
372        Ok(proof_array)
373    }
374
375    fn check<'a>(
376        vk: &Self::VerifierKey,
377        commitments: impl IntoIterator<Item = &'a LabeledCommitment<Self::Commitment>>,
378        point: &'a P::Point,
379        values: impl IntoIterator<Item = F>,
380        proof_array: &Self::Proof,
381        sponge: &mut impl CryptographicSponge,
382        _rng: Option<&mut dyn RngCore>,
383    ) -> Result<bool, Self::Error>
384    where
385        Self::Commitment: 'a,
386    {
387        let leaf_hash_param: &<<C as Config>::LeafHash as CRHScheme>::Parameters =
388            vk.leaf_hash_param();
389        let two_to_one_hash_param: &<<C as Config>::TwoToOneHash as TwoToOneCRHScheme>::Parameters =
390            vk.two_to_one_hash_param();
391
392        for (i, (labeled_commitment, value)) in commitments.into_iter().zip(values).enumerate() {
393            let proof = &proof_array[i];
394            let commitment = labeled_commitment.commitment();
395            let n_rows = commitment.metadata.n_rows;
396            let n_cols = commitment.metadata.n_cols;
397            let n_ext_cols = commitment.metadata.n_ext_cols;
398            let root = &commitment.root;
399            let t = calculate_t::<F>(vk.sec_param(), vk.distance(), n_ext_cols)?;
400
401            sponge.absorb(&to_bytes!(&commitment.root).map_err(|_| Error::TranscriptError)?);
402
403            let out = if vk.check_well_formedness() {
404                if proof.well_formedness.is_none() {
405                    return Err(Error::InvalidCommitment);
406                }
407                let tmp = &proof.well_formedness.as_ref();
408                let v = tmp.unwrap();
409                let r = sponge.squeeze_field_elements::<F>(n_rows);
410                // Upon sending `v` to the Verifier, add it to the sponge. The claim is that v = r.M.
411                sponge.absorb(&v);
412
413                (Some(v), Some(r))
414            } else {
415                (None, None)
416            };
417
418            // 1. Seed the transcript with the point and the recieved vector
419            // TODO Consider removing the evaluation point from the transcript.
420            let point_vec = L::point_to_vec(point.clone());
421            sponge.absorb(&point_vec);
422            sponge.absorb(&proof.opening.v);
423
424            // 2. Ask random oracle for the `t` indices where the checks happen.
425            let indices = get_indices_from_sponge(n_ext_cols, t, sponge)?;
426
427            // 3. Hash the received columns into leaf hashes.
428            let col_hashes: Vec<C::Leaf> = proof
429                .opening
430                .columns
431                .iter()
432                .map(|c| {
433                    H::evaluate(vk.col_hash_params(), c.clone())
434                        .map_err(|_| Error::HashingError)
435                        .unwrap()
436                        .into()
437                })
438                .collect();
439
440            // 4. Verify the paths for each of the leaf hashes - this is only run once,
441            // even if we have a well-formedness check (i.e., we save sending and checking the columns).
442            // See "Concrete optimizations to the commitment scheme", p.12 of [Brakedown](https://eprint.iacr.org/2021/1043.pdf).
443            for (j, (leaf, q_j)) in col_hashes.iter().zip(indices.iter()).enumerate() {
444                let path = &proof.opening.paths[j];
445                if path.leaf_index != *q_j {
446                    return Err(Error::InvalidCommitment);
447                }
448
449                path.verify(leaf_hash_param, two_to_one_hash_param, root, leaf.clone())
450                    .map_err(|_| Error::InvalidCommitment)?;
451            }
452
453            // Helper closure: checks if a.b = c.
454            let check_inner_product = |a, b, c| -> Result<(), Error> {
455                if inner_product(a, b) != c {
456                    return Err(Error::InvalidCommitment);
457                }
458
459                Ok(())
460            };
461
462            // 5. Compute the encoding w = E(v).
463            let w = L::encode(&proof.opening.v, vk)?;
464
465            // 6. Compute `a`, `b` to right- and left- multiply with the matrix `M`.
466            let (a, b) = L::tensor(point, n_cols, n_rows);
467
468            // 7. Probabilistic checks that whatever the prover sent,
469            // matches with what the verifier computed for himself.
470            // Note: we sacrifice some code repetition in order not to repeat execution.
471            if let (Some(well_formedness), Some(r)) = out {
472                let w_well_formedness = L::encode(well_formedness, vk)?;
473                for (transcript_index, matrix_index) in indices.iter().enumerate() {
474                    check_inner_product(
475                        &r,
476                        &proof.opening.columns[transcript_index],
477                        w_well_formedness[*matrix_index],
478                    )?;
479                    check_inner_product(
480                        &b,
481                        &proof.opening.columns[transcript_index],
482                        w[*matrix_index],
483                    )?;
484                }
485            } else {
486                for (transcript_index, matrix_index) in indices.iter().enumerate() {
487                    check_inner_product(
488                        &b,
489                        &proof.opening.columns[transcript_index],
490                        w[*matrix_index],
491                    )?;
492                }
493            }
494
495            if inner_product(&proof.opening.v, &a) != value {
496                eprintln!("Function check: claimed value in position {i} does not match the evaluation of the committed polynomial in the same position");
497                return Ok(false);
498            }
499        }
500
501        Ok(true)
502    }
503}
504
505// TODO maybe this can go to utils
506fn create_merkle_tree<C>(
507    leaves: &mut Vec<C::Leaf>,
508    leaf_hash_param: &<<C as Config>::LeafHash as CRHScheme>::Parameters,
509    two_to_one_hash_param: &<<C as Config>::TwoToOneHash as TwoToOneCRHScheme>::Parameters,
510) -> Result<MerkleTree<C>, Error>
511where
512    C: Config,
513    C::Leaf: Default + Clone + Send + AsRef<C::Leaf>,
514{
515    // pad the column hashes with zeroes
516    let next_pow_of_two = leaves.len().next_power_of_two();
517    leaves.resize(next_pow_of_two, <C::Leaf>::default());
518
519    MerkleTree::<C>::new(leaf_hash_param, two_to_one_hash_param, leaves)
520        .map_err(|_| Error::HashingError)
521}
522
523fn generate_proof<F, C, S>(
524    sec_param: usize,
525    distance: (usize, usize),
526    b: &[F],
527    mat: &Matrix<F>,
528    ext_mat: &Matrix<F>,
529    col_tree: &MerkleTree<C>,
530    sponge: &mut S,
531) -> Result<LinCodePCProofSingle<F, C>, Error>
532where
533    F: PrimeField + Absorb,
534    C: Config,
535    S: CryptographicSponge,
536{
537    let t = calculate_t::<F>(sec_param, distance, ext_mat.m)?;
538
539    // 1. left-multiply the matrix by `b`.
540    let v = mat.row_mul(b);
541    sponge.absorb(&v);
542
543    // 2. Generate t column indices to test the linear combination on.
544    let indices = get_indices_from_sponge(ext_mat.m, t, sponge)?;
545
546    // 3. Compute Merkle tree paths for the requested columns.
547    let mut queried_columns = Vec::with_capacity(t);
548    let mut paths = Vec::with_capacity(t);
549
550    let ext_mat_cols = ext_mat.cols();
551
552    for i in indices {
553        queried_columns.push(ext_mat_cols[i].clone());
554        paths.push(
555            col_tree
556                .generate_proof(i)
557                .map_err(|_| Error::TranscriptError)?,
558        );
559    }
560
561    Ok(LinCodePCProofSingle {
562        paths,
563        v,
564        columns: queried_columns,
565    })
566}
ark_poly_commit/linear_codes/mod.rs

ark_poly_commit/linear_codes/
mod.rs
