zip_plus/pcs/
structs.rs

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

zip_plus/pcs/
structs.rs
