zip_plus/pcs/
structs.rs

1use crate::{
2    code::LinearCode,
3    merkle::{MerkleTree, MtHash},
4};
5use crypto_primitives::{ConstIntRing, ConstIntSemiring, DenseRowMatrix, FixedSemiring};
6use num_traits::CheckedAdd;
7use std::{fmt::Debug, marker::PhantomData, ops::Neg};
8use zinc_poly::{ConstCoeffBitWidth, Polynomial};
9use zinc_primality::PrimalityTest;
10use zinc_transcript::traits::{ConstTranscribable, GenTranscribable};
11use zinc_utils::{
12    from_ref::FromRef, inner_product::InnerProduct, mul_by_scalar::MulByScalar, named::Named,
13};
14
15pub trait ZipTypes: Clone + Debug + Send + Sync {
16    const NUM_COLUMN_OPENINGS: usize;
17
18    /// Semiring of witness/polynomial evaluations on boolean hypercube
19    type Eval: ConstCoeffBitWidth + Default + Named + Clone + Debug + Send + Sync;
20
21    /// Semiring of codeword elements, at least as wide as the evaluation ring
22    type Cw: FixedSemiring
23        + ConstCoeffBitWidth
24        + ConstTranscribable
25        + FromRef<Self::Eval>
26        + CheckedAdd
27        + Named
28        // TODO(Ilia): Find out if the Copy can be avoided.
29        + Copy
30        + Debug;
31
32    /// Semiring type used to draft field modulus elements, natural numbers
33    type Fmod: ConstIntSemiring + ConstTranscribable + Named;
34    type PrimeTest: PrimalityTest<Self::Fmod>;
35
36    /// Ring of challenge elements (coefficients) to perform a random linear
37    /// combination of codewords
38    type Chal: ConstIntRing + ConstTranscribable + Named;
39
40    /// Ring of point coordinates to evaluate the multilinear polynomial
41    type Pt: ConstIntRing;
42
43    /// Coefficient ring of linear combination polynomial [Self::Comb]
44    type CombR: ConstIntRing
45        + Neg<Output = Self::CombR>
46        + ConstTranscribable
47        + FromRef<Self::CombR>
48        + for<'a> MulByScalar<&'a Self::Chal>;
49    /// Ring of elements in the linear combination of codewords, at least as
50    /// wide as the evaluation, codeword, and challenge rings.
51    type Comb: FixedSemiring
52        + Polynomial<Self::CombR>
53        + FromRef<Self::Eval>
54        + FromRef<Self::Cw>
55        + Named;
56
57    type EvalDotChal: InnerProduct<Self::Eval, Self::Chal, Self::CombR> + Debug;
58    type CombDotChal: InnerProduct<Self::Comb, Self::Chal, Self::CombR> + Debug;
59    type ArrCombRDotChal: InnerProduct<[Self::CombR], Self::Chal, Self::CombR> + Debug;
60}
61
62/// Zip is a Polynomial Commitment Scheme (PCS) that supports committing to
63/// multilinear polynomials.
64// Note(alex): We cannot define CHECK_FOR_OVERFLOW in ZipTypes because type
65// parameters may not be used in const expressions
66pub struct ZipPlus<Zt: ZipTypes, Lc: LinearCode<Zt>>(PhantomData<(Zt, Lc)>);
67
68impl<Zt, Lc> ZipPlus<Zt, Lc>
69where
70    Zt: ZipTypes,
71    Lc: LinearCode<Zt>,
72{
73    #[allow(clippy::arithmetic_side_effects)]
74    pub fn setup(poly_size: usize, linear_code: Lc) -> ZipPlusParams<Zt, Lc> {
75        assert!(poly_size.is_power_of_two());
76        let num_vars = poly_size.ilog2() as usize;
77        let row_len = linear_code.row_len();
78        assert!(
79            row_len > 0 && poly_size.is_multiple_of(row_len),
80            "poly_size ({poly_size}) must be divisible by row_len ({row_len})"
81        );
82        let num_rows = poly_size / row_len;
83        assert!(
84            num_rows.is_power_of_two(),
85            "num_rows ({num_rows}) must be a power of two"
86        );
87        ZipPlusParams::new(num_vars, num_rows, linear_code)
88    }
89}
90
91/// Parameters for the Zip+ PCS.
92#[derive(Clone, Debug)]
93pub struct ZipPlusParams<Zt: ZipTypes, Lc: LinearCode<Zt>> {
94    pub num_vars: usize,
95    pub num_rows: usize,
96    pub linear_code: Lc,
97    phantom_data: PhantomData<Zt>,
98}
99
100impl<Zt: ZipTypes, Lc: LinearCode<Zt>> ZipPlusParams<Zt, Lc> {
101    pub fn new(num_vars: usize, num_rows: usize, linear_code: Lc) -> Self {
102        Self {
103            num_vars,
104            num_rows,
105            linear_code,
106            phantom_data: PhantomData,
107        }
108    }
109}
110
111/// Full data of zip commitment to a multilinear polynomial, including encoded
112/// rows and Merkle tree, kept by the prover for the testing phase.
113#[derive(Debug, Clone, Default)]
114pub struct ZipPlusHint<R> {
115    /// The encoded rows of the polynomial matrix representation, referred to as
116    /// "u-hat" in the Zinc paper
117    pub cw_matrices: Vec<DenseRowMatrix<R>>,
118    /// Merkle trees of entire matrix
119    pub merkle_tree: MerkleTree,
120}
121
122impl<R> ZipPlusHint<R> {
123    pub fn new(cw_matrices: Vec<DenseRowMatrix<R>>, merkle_tree: MerkleTree) -> ZipPlusHint<R> {
124        ZipPlusHint {
125            cw_matrices,
126            merkle_tree,
127        }
128    }
129}
130
131/// The compact commitment to a multilinear polynomial, consisting of only the
132/// Merkle roots, to be sent to the verifier.
133#[derive(Clone, Debug, Default, PartialEq, Eq)]
134pub struct ZipPlusCommitment {
135    /// Roots of the merkle tree of entire matrix
136    pub root: MtHash,
137    pub batch_size: usize,
138}
139
140impl GenTranscribable for ZipPlusCommitment {
141    fn read_transcription_bytes_exact(bytes: &[u8]) -> Self {
142        let root = MtHash::read_transcription_bytes_exact(&bytes[..MtHash::NUM_BYTES]);
143        let batch_size = u64::read_transcription_bytes_exact(&bytes[MtHash::NUM_BYTES..]);
144        let batch_size = usize::try_from(batch_size).expect("num_bytes must fit into usize");
145        Self { root, batch_size }
146    }
147
148    fn write_transcription_bytes_exact(&self, buf: &mut [u8]) {
149        let (root_buf, rest) = buf.split_at_mut(MtHash::NUM_BYTES);
150        self.root.write_transcription_bytes_exact(root_buf);
151        (self.batch_size as u64).write_transcription_bytes_exact(rest);
152    }
153}
154
155impl ConstTranscribable for ZipPlusCommitment {
156    const NUM_BYTES: usize = MtHash::NUM_BYTES + u64::NUM_BYTES;
157}
zip_plus/pcs/structs.rs

zip_plus/pcs/
structs.rs
