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

zip_plus/pcs/
structs.rs
