zip_plus/pcs/
phase_commit.rs

1use std::slice::from_ref;
2
3use crate::{
4    ZipError,
5    code::LinearCode,
6    merkle::MerkleTree,
7    pcs::{
8        structs::{ZipPlus, ZipPlusCommitment, ZipPlusHint, ZipPlusParams, ZipTypes},
9        utils::validate_input,
10    },
11};
12use crypto_primitives::DenseRowMatrix;
13use uninit::out_ref::Out;
14use zinc_utils::{cfg_chunks, cfg_chunks_mut, cfg_iter};
15
16#[cfg(feature = "parallel")]
17use rayon::prelude::*;
18use zinc_poly::mle::DenseMultilinearExtension;
19
20impl<Zt: ZipTypes, Lc: LinearCode<Zt>> ZipPlus<Zt, Lc> {
21    /// Creates a commitment to one or more multilinear polynomials using the
22    /// ZIP PCS scheme.
23    ///
24    /// This function implements the commitment phase of the ZIP polynomial
25    /// commitment scheme. It encodes each polynomial's evaluations using a
26    /// linear error-correcting code and then creates a single Merkle tree
27    /// commitment over the interleaved columns.
28    ///
29    /// # Algorithm
30    /// 1. Validates that each polynomial's number of variables matches the
31    ///    parameters.
32    /// 2. Arranges each polynomial's evaluations into a matrix with
33    ///    `pp.num_rows` rows.
34    /// 3. Encodes each row using the specified linear code, expanding its
35    ///    length from `row_len` to `codeword_len`.
36    /// 4. Constructs a single Merkle tree where `leaf_j = H(poly_1_col_j ||
37    ///    poly_2_col_j || ...)`.
38    /// 5. Returns the full commitment data (for the prover) and a compact
39    ///    commitment (for the verifier).
40    ///
41    /// # Parameters
42    /// - `pp`: Public parameters (`ZipPlusParams`) containing the configuration
43    ///   for the commitment scheme.
44    /// - `polys`: Slice of multilinear polynomials to be committed to.
45    ///
46    /// # Returns
47    /// A `Result` containing a tuple of:
48    /// - `ZipPlusHint`: Per-polynomial encoded rows and the shared Merkle tree,
49    ///   kept by the prover for the opening phase.
50    /// - `ZipPlusCommitment`: The compact commitment (Merkle root and batch
51    ///   size), to be sent to the verifier.
52    ///
53    /// # Errors
54    /// - Returns `Error::InvalidPcsParam` if any polynomial has more variables
55    ///   than the parameters support.
56    ///
57    /// # Panics
58    /// - Panics if any polynomial's evaluation count does not match
59    ///   `pp.num_rows * pp.linear_code.row_len()`.
60    #[allow(clippy::arithmetic_side_effects)]
61    pub fn commit(
62        pp: &ZipPlusParams<Zt, Lc>,
63        polys: &[DenseMultilinearExtension<Zt::Eval>],
64    ) -> Result<(ZipPlusHint<Zt::Cw>, ZipPlusCommitment), ZipError> {
65        assert!(
66            !polys.is_empty(),
67            "Batch must contain at least one polynomial"
68        );
69        let batch_size = polys.len();
70        let row_len = pp.linear_code.row_len();
71        validate_input::<Zt, Lc, bool>(
72            "commit",
73            pp.num_vars,
74            pp.linear_code.row_len(),
75            batch_size,
76            polys,
77            &[],
78        )?;
79
80        let expected_num_evals = pp.num_rows * row_len;
81        let cw_matrices: Vec<DenseRowMatrix<Zt::Cw>> = cfg_iter!(polys).map(|poly| {
82            assert_eq!(
83                poly.len(),
84                expected_num_evals,
85                "Polynomial has an incorrect number of evaluations ({}) for the expected matrix size ({})",
86                poly.len(),
87                expected_num_evals
88            );
89
90            Self::encode_rows(pp, poly)
91        }).collect();
92
93        let all_rows: Vec<&[Zt::Cw]> = cw_matrices.iter().flat_map(|m| m.as_rows()).collect();
94        let merkle_tree = MerkleTree::new(&all_rows);
95        let root = merkle_tree.root();
96
97        Ok((
98            ZipPlusHint::new(cw_matrices, merkle_tree),
99            ZipPlusCommitment { root, batch_size },
100        ))
101    }
102
103    /// Creates a commitment without constructing Merkle trees.
104    ///
105    /// This function performs the encoding step of the commitment phase but
106    /// deliberately skips the computationally intensive step of building
107    /// Merkle trees. It is intended **for testing and benchmarking purposes
108    /// only**, where the full commitment structure is not required.
109    ///
110    /// # Parameters
111    /// - `pp`: Public parameters (`ZipPlusParams`).
112    /// - `poly`: The multilinear polynomial to commit to.
113    ///
114    /// # Returns
115    /// A `Result` containing `ZipPlusHint` with the encoded rows but
116    /// empty Merkle trees, and a `ZipPlusCommitment` with an empty
117    /// vector of roots.
118    #[allow(dead_code)]
119    pub fn commit_no_merkle(
120        pp: &ZipPlusParams<Zt, Lc>,
121        poly: &DenseMultilinearExtension<Zt::Eval>,
122    ) -> Result<DenseRowMatrix<Zt::Cw>, ZipError> {
123        validate_input::<Zt, Lc, bool>(
124            "commit",
125            pp.num_vars,
126            pp.linear_code.row_len(),
127            1,
128            from_ref(poly),
129            &[],
130        )?;
131
132        Ok(Self::encode_rows(pp, poly))
133    }
134
135    pub fn commit_single(
136        pp: &ZipPlusParams<Zt, Lc>,
137        poly: &DenseMultilinearExtension<Zt::Eval>,
138    ) -> Result<(ZipPlusHint<Zt::Cw>, ZipPlusCommitment), ZipError> {
139        Self::commit(pp, std::slice::from_ref(poly))
140    }
141
142    /// Encodes the evaluations of a polynomial by arranging them into rows and
143    /// applying a linear code.
144    ///
145    /// This function treats the polynomial's flat evaluation vector as a matrix
146    /// with `pp.num_rows` and encodes each row individually. The resulting
147    /// encoded rows are concatenated into a single flat vector. This
148    /// operation can be parallelized if the `parallel` feature is enabled.
149    ///
150    /// # Parameters
151    /// - `pp`: Public parameters containing matrix dimensions and the linear
152    ///   code.
153    /// - `codeword_len`: The length of an encoded row.
154    /// - `poly`: The polynomial whose evaluations are to be encoded.
155    ///
156    /// # Returns
157    /// A `Vec<Int<K>>` containing all the encoded rows concatenated together.
158    #[allow(clippy::arithmetic_side_effects)]
159    pub fn encode_rows(pp: &ZipPlusParams<Zt, Lc>, evals: &[Zt::Eval]) -> DenseRowMatrix<Zt::Cw> {
160        let row_len = pp.linear_code.row_len();
161        let codeword_len = pp.linear_code.codeword_len();
162
163        // Performance: Using DenseRowMatrix's linearized row in an uninit form
164        // is much more performant that using Vec<Vec<_>>.
165        let mut encoded_matrix = DenseRowMatrix::<Zt::Cw>::uninit(pp.num_rows, codeword_len);
166
167        cfg_chunks_mut!(encoded_matrix.data, codeword_len)
168            .zip(cfg_chunks!(evals, row_len))
169            .for_each(|(row, evals)| {
170                let encoded: Vec<Zt::Cw> = pp.linear_code.encode(evals);
171                Out::from(row).copy_from_slice(encoded.as_slice());
172            });
173
174        // Safe because we have just initialized all elements.
175        unsafe { encoded_matrix.init() }
176    }
177}
178
179//TODO. Review and add proper test
180#[cfg(test)]
181#[allow(
182    clippy::arithmetic_side_effects,
183    clippy::cast_possible_truncation,
184    clippy::cast_possible_wrap
185)]
186mod tests {
187    use crate::{
188        code::{LinearCode, iprs::IprsCode},
189        merkle::{MerkleTree, MtHash},
190        pcs::{
191            structs::{ZipPlus, ZipPlusParams, ZipTypes},
192            test_utils::*,
193        },
194        pcs_transcript::PcsProverTranscript,
195    };
196    use crypto_bigint::{Random, U64, U256, Word};
197    use crypto_primitives::{
198        Matrix, boolean::Boolean, crypto_bigint_boxed_monty::BoxedMontyField,
199        crypto_bigint_int::Int,
200    };
201    use itertools::Itertools;
202    use num_traits::Zero;
203    use rand::{Rng, rng};
204    use std::sync::LazyLock;
205    use zinc_poly::{mle::DenseMultilinearExtension, univariate::binary::BinaryPoly};
206    use zinc_utils::CHECKED;
207
208    const INT_LIMBS: usize = U64::LIMBS;
209
210    const N: usize = INT_LIMBS;
211    const K: usize = INT_LIMBS * 4;
212    const M: usize = INT_LIMBS * 8;
213    const DEGREE_PLUS_ONE: usize = 3;
214
215    type Zt = TestZipTypes<N, K, M>;
216    type C = IprsCode<Zt, TestIprsConfig, REP_FACTOR, CHECKED>;
217    static C: LazyLock<C> = LazyLock::new(|| C::new(IPRS_ROW_LEN, IPRS_DEPTH).unwrap());
218
219    type PolyZt = TestBinPolyZipTypes<K, M, DEGREE_PLUS_ONE>;
220    type PolyC = IprsCode<PolyZt, TestIprsConfig, REP_FACTOR, CHECKED>;
221    static POLY_C: LazyLock<PolyC> =
222        LazyLock::new(|| PolyC::new(IPRS_ROW_LEN, IPRS_DEPTH).unwrap());
223
224    type TestZip = ZipPlus<Zt, C>;
225    type TestPolyZip = ZipPlus<PolyZt, PolyC>;
226
227    #[test]
228    #[cfg_attr(miri, ignore)] // long running
229    fn commit_rejects_too_many_variables() {
230        let num_vars = 10;
231        let (pp, _) = setup_test_params(num_vars);
232
233        // Create MLE with a larger number of variables
234        let poly: DenseMultilinearExtension<_> =
235            (1..=(1 << (num_vars + 1))).map(Int::from).collect();
236
237        let result = TestZip::commit_single(&pp, &poly);
238        assert!(result.is_err());
239    }
240
241    #[test]
242    fn commit_is_deterministic() {
243        let num_vars = 10;
244        let (pp, poly) = setup_test_params(num_vars);
245
246        let result1 = TestZip::commit_single(&pp, &poly).unwrap();
247        let result2 = TestZip::commit_single(&pp, &poly).unwrap();
248
249        assert_eq!(result1.1.root, result2.1.root);
250    }
251
252    #[test]
253    fn different_polynomials_produce_different_commitments() {
254        let num_vars = 10;
255        let (pp, _) = setup_test_params(num_vars);
256        let poly_size = 1 << num_vars;
257
258        let poly1 = DenseMultilinearExtension::from_evaluations_vec(
259            num_vars,
260            vec![Int::from(1); poly_size],
261            Zero::zero(),
262        );
263        let poly2 = DenseMultilinearExtension::from_evaluations_vec(
264            num_vars,
265            vec![Int::from(2); poly_size],
266            Zero::zero(),
267        );
268
269        let (_, commitment1) = TestZip::commit_single(&pp, &poly1).unwrap();
270        let (_, commitment2) = TestZip::commit_single(&pp, &poly2).unwrap();
271
272        assert_ne!(commitment1.root, commitment2.root);
273    }
274
275    #[test]
276    fn commit_succeeds_for_small_polynomial() {
277        let num_vars = 4;
278        let num_rows = (1_usize << num_vars).div_ceil(C.row_len());
279        let pp = ZipPlusParams::new(num_vars, num_rows, C.clone());
280
281        let evaluations = vec![Int::from(42); 1 << num_vars];
282        let mut poly =
283            DenseMultilinearExtension::from_evaluations_vec(num_vars, evaluations, Zero::zero());
284        // Zero-pad MLE to match the expected number of evaluations
285        poly.evaluations
286            .resize(pp.num_rows * pp.linear_code.row_len(), Zero::zero());
287
288        let result = TestZip::commit_single(&pp, &poly);
289        assert!(result.is_ok());
290    }
291
292    #[test]
293    fn commit_succeeds_for_two_variables() {
294        let num_vars = 2;
295        let num_rows = (1_usize << num_vars).div_ceil(C.row_len());
296        let pp = ZipPlusParams::new(num_vars, num_rows, C.clone());
297
298        let poly_size = 1 << num_vars;
299        let evaluations: Vec<_> = (1..=poly_size).map(Int::from).collect();
300        let mut poly =
301            DenseMultilinearExtension::from_evaluations_vec(num_vars, evaluations, Zero::zero());
302        // Zero-pad MLE to match the expected number of evaluations
303        poly.evaluations
304            .resize(pp.num_rows * pp.linear_code.row_len(), Zero::zero());
305
306        let result = TestZip::commit_single(&pp, &poly);
307        assert!(result.is_ok());
308    }
309
310    #[test]
311    #[cfg_attr(miri, ignore)] // long running
312    fn batch_commit_produces_different_root_than_individual_commits() {
313        let num_vars = 10;
314        let (pp, _) = setup_test_params(num_vars);
315        let poly_size = 1 << num_vars;
316
317        let poly1: DenseMultilinearExtension<_> = (1..=poly_size).map(Int::from).collect();
318        let poly2: DenseMultilinearExtension<_> =
319            (poly_size + 1..=2 * poly_size).map(Int::from).collect();
320
321        let (_, batched_comm) = TestZip::commit(&pp, &[poly1.clone(), poly2.clone()]).unwrap();
322        let (_, comm1) = TestZip::commit_single(&pp, &poly1).unwrap();
323        let (_, comm2) = TestZip::commit_single(&pp, &poly2).unwrap();
324
325        assert_ne!(batched_comm.root, comm1.root);
326        assert_ne!(batched_comm.root, comm2.root);
327    }
328
329    #[test]
330    #[cfg_attr(miri, ignore)] // long running
331    fn batch_commit_is_deterministic() {
332        let num_vars = 10;
333        let (pp, _) = setup_test_params(num_vars);
334        let poly_size = 1 << num_vars;
335
336        let poly1: DenseMultilinearExtension<_> = (1..=poly_size).map(Int::from).collect();
337        let poly2: DenseMultilinearExtension<_> =
338            (poly_size + 1..=2 * poly_size).map(Int::from).collect();
339
340        let (_, comm_a) = TestZip::commit(&pp, &[poly1.clone(), poly2.clone()]).unwrap();
341        let (_, comm_b) = TestZip::commit(&pp, &[poly1, poly2]).unwrap();
342
343        assert_eq!(comm_a.root, comm_b.root);
344    }
345
346    #[test]
347    #[cfg_attr(miri, ignore)] // long running
348    fn batch_commit_batch_size_is_correct() {
349        let num_vars = 10;
350        let (pp, _) = setup_test_params(num_vars);
351        let poly_size = 1 << num_vars;
352
353        let polys: Vec<DenseMultilinearExtension<_>> = (0..5)
354            .map(|offset| {
355                let start = offset * poly_size + 1;
356                (start..start + poly_size).map(Int::from).collect()
357            })
358            .collect();
359
360        let (hint, comm) = TestZip::commit(&pp, &polys).unwrap();
361        assert_eq!(comm.batch_size, 5);
362        assert_eq!(hint.cw_matrices.len(), 5);
363    }
364
365    #[test]
366    #[cfg_attr(miri, ignore)] // long running
367    fn encode_rows_produces_correct_size() {
368        let num_vars = 10;
369        let (pp, poly) = setup_test_params(num_vars);
370        let encoded = TestZip::encode_rows(&pp, &poly);
371
372        assert_eq!(encoded.num_rows, pp.num_rows);
373        assert_eq!(encoded.num_cols, pp.linear_code.codeword_len());
374    }
375
376    /// Verifies that the output of `encode_rows` is semantically correct by
377    /// comparing it to a direct, row-by-row encoding.
378    #[test]
379    #[cfg_attr(miri, ignore)] // long running
380    fn encoded_rows_match_linear_code_definition() {
381        let num_vars = 10;
382        let (pp, poly) = setup_test_params(num_vars);
383        let encoded = TestZip::encode_rows(&pp, &poly);
384
385        for (i, row_chunk) in encoded.as_rows().enumerate() {
386            let start = i * pp.linear_code.row_len();
387            let end = start + pp.linear_code.row_len();
388            let row_evals = &poly[start..end];
389            let expected_encoding = pp.linear_code.encode(row_evals);
390            assert_eq!(
391                row_chunk,
392                expected_encoding.as_slice(),
393                "Row {i} encoding mismatch",
394            );
395        }
396    }
397
398    /// Verifies that corrupting the encoded data after commitment results in a
399    /// different Merkle root.
400    #[test]
401    #[cfg_attr(miri, ignore)] // long running
402    fn corrupted_encoding_changes_merkle_root() {
403        let num_vars = 10;
404        let (pp, poly) = setup_test_params(num_vars);
405        let (data, commitment) = TestZip::commit_single(&pp, &poly).unwrap();
406
407        assert!(!data.cw_matrices[0].is_empty());
408        let mut cw_matrix = data.cw_matrices[0].to_rows();
409        cw_matrix[0][0] = Int::from(999999);
410        let corrupted_row = cw_matrix[0].clone();
411        let new_tree = MerkleTree::new(&[corrupted_row.as_slice()]);
412        assert_ne!(
413            new_tree.root(),
414            commitment.root,
415            "Corruption should change Merkle root"
416        );
417    }
418
419    #[test]
420    #[cfg_attr(miri, ignore)] // long running
421    fn batch_commit_single_poly_matches_single_commit() {
422        let num_vars = 10;
423        let (pp, poly) = setup_test_params(num_vars);
424
425        let polys = std::slice::from_ref(&poly);
426        let (batched_hint, batched_comm) = TestZip::commit(&pp, polys).unwrap();
427        let (single_hint, single_comm) = TestZip::commit_single(&pp, &poly).unwrap();
428
429        assert_eq!(batched_comm.root, single_comm.root);
430        assert_eq!(batched_hint.cw_matrices.len(), 1);
431        assert_eq!(batched_hint.cw_matrices[0], single_hint.cw_matrices[0]);
432    }
433
434    #[test]
435    #[cfg_attr(miri, ignore)] // long running
436    fn encoded_rows_are_nonzero_for_nonzero_input() {
437        let num_vars = 10;
438        let (pp, poly) = setup_test_params(num_vars);
439        let encoded = TestZip::encode_rows(&pp, &poly.evaluations);
440
441        assert_eq!(encoded.num_rows, pp.num_rows);
442        assert_eq!(encoded.num_cols, pp.linear_code.codeword_len());
443
444        let non_zero_count = encoded.as_rows().flatten().filter(|x| !x.is_zero()).count();
445        assert!(non_zero_count > 0);
446    }
447
448    #[test]
449    fn commit_produces_correct_merkle_tree_count() {
450        let num_vars = 10;
451        let (pp, poly) = setup_test_params(num_vars);
452        let (hint, _) = TestZip::commit_single(&pp, &poly).unwrap();
453
454        assert_eq!(hint.cw_matrices[0].num_rows, pp.num_rows);
455        assert_eq!(hint.cw_matrices[0].num_cols, pp.linear_code.codeword_len());
456    }
457
458    #[test]
459    #[cfg(feature = "parallel")]
460    fn encoding_is_consistent_across_threads() {
461        use rayon::prelude::*;
462
463        let num_vars = 10;
464        let poly_size = 1 << num_vars;
465        let evaluations = (1..=poly_size).map(|v| Int::from(v as i32)).collect();
466        let poly =
467            DenseMultilinearExtension::from_evaluations_vec(num_vars, evaluations, Zero::zero());
468
469        let results: Vec<Vec<Vec<Int<4>>>> = (0..10)
470            .into_par_iter()
471            .map(|_| {
472                let row_len = 1 << (num_vars / 2);
473                let pp = ZipPlusParams::new(num_vars, poly_size / row_len, C.clone());
474
475                let rows = TestZip::encode_rows(&pp, &poly.evaluations);
476                let rows: Vec<Vec<_>> = rows
477                    .data
478                    .chunks_exact(pp.linear_code.codeword_len())
479                    .map(|chunk| chunk.to_vec())
480                    .collect();
481                rows
482            })
483            .collect();
484
485        for w in results.windows(2) {
486            assert_eq!(
487                w[0], w[1],
488                "Parallel encoding runs produced inconsistent results: {:?} vs {:?}",
489                w[0], w[1]
490            );
491        }
492    }
493
494    #[test]
495    fn commit_succeeds_for_zero_polynomial() {
496        let num_vars = 10;
497        let (pp, _) = setup_test_params(num_vars);
498        let poly_size = 1 << num_vars;
499        let zero_poly = DenseMultilinearExtension::from_evaluations_vec(
500            num_vars,
501            vec![Zero::zero(); poly_size],
502            Zero::zero(),
503        );
504        let result = TestZip::commit_single(&pp, &zero_poly);
505        assert!(result.is_ok());
506    }
507
508    #[test]
509    fn commit_succeeds_for_alternating_values() {
510        let num_vars = 10;
511        let (pp, _) = setup_test_params(num_vars);
512        let poly_size = 1 << num_vars;
513        let alternating = (0..poly_size)
514            .map(|i| Int::from(if i % 2 == 0 { 1 } else { -1 }))
515            .collect();
516        let poly =
517            DenseMultilinearExtension::from_evaluations_vec(num_vars, alternating, Zero::zero());
518        let result = TestZip::commit_single(&pp, &poly);
519        assert!(result.is_ok());
520    }
521
522    #[test]
523    #[should_panic(expected = "Batch must contain at least one polynomial")]
524    fn batch_commit_on_empty_slice_panics() {
525        let num_vars = 10;
526        let (pp, _) = setup_test_params(num_vars);
527        let empty_polys: Vec<DenseMultilinearExtension<Int<INT_LIMBS>>> = vec![];
528        let _ = TestZip::commit(&pp, &empty_polys);
529    }
530
531    #[test]
532    #[cfg_attr(miri, ignore)] // long running
533    fn encode_rows_succeeds_for_single_row() {
534        let num_vars = 10;
535        let poly_size = 1 << num_vars;
536        let pp = ZipPlusParams::new(num_vars, 1, C.clone());
537
538        // Create a polynomial with 2 variables and 4 evaluations
539        let evaluations = vec![Int::from(5); poly_size];
540        let poly =
541            DenseMultilinearExtension::from_evaluations_vec(num_vars, evaluations, Zero::zero());
542        let encoded = TestZip::encode_rows(&pp, &poly.evaluations);
543        assert_eq!(encoded.num_rows, 1);
544        assert_eq!(encoded.num_cols, pp.linear_code.codeword_len());
545    }
546
547    #[test]
548    #[cfg_attr(miri, ignore)] // long running
549    fn encode_rows_succeeds_for_single_poly_row() {
550        let num_vars = 10;
551        let pp = ZipPlusParams::new(num_vars, 1, POLY_C.clone());
552
553        // Create a polynomial with 2 variables and 4 evaluations
554        let evaluations = vec![
555            BinaryPoly::new(vec![Boolean::FALSE, Boolean::FALSE]),
556            BinaryPoly::new(vec![Boolean::FALSE, Boolean::TRUE]),
557            BinaryPoly::new(vec![Boolean::TRUE, Boolean::FALSE]),
558        ];
559        let poly =
560            DenseMultilinearExtension::from_evaluations_vec(num_vars, evaluations, Zero::zero());
561        let encoded = TestPolyZip::encode_rows(&pp, &poly.evaluations);
562        assert_eq!(encoded.num_rows, 1);
563        assert_eq!(encoded.num_cols, pp.linear_code.codeword_len());
564    }
565
566    #[test]
567    #[cfg_attr(miri, ignore)] // long running
568    fn matrix_dimensions_are_invariant() {
569        let test_cases = vec![(8, 1), (10, 4), (12, 16)];
570        for (num_vars, expected_rows) in test_cases {
571            let (pp, poly) = setup_test_params(num_vars);
572            assert_eq!(pp.num_rows, expected_rows);
573            let result = TestZip::commit_single(&pp, &poly);
574            assert!(result.is_ok());
575        }
576    }
577
578    #[test]
579    #[should_panic]
580    fn reject_incompatible_dimensions() {
581        let num_vars = 10;
582        let (pp, poly) = setup_test_params(num_vars);
583        let incompatible_pp = ZipPlusParams::new(8, 8, pp.linear_code);
584        TestZip::commit_single(&incompatible_pp, &poly).unwrap();
585    }
586
587    #[test]
588    #[cfg_attr(miri, ignore)] // long running
589    fn linear_code_preserves_linearity() {
590        let num_vars = 10;
591        let (pp, poly) = setup_test_params(num_vars);
592        let encoded = TestZip::encode_rows(&pp, &poly.evaluations);
593        let row_len = pp.linear_code.row_len();
594        let codeword_len = pp.linear_code.codeword_len();
595        let row1_evals = &poly.evaluations[0..row_len];
596        let row2_evals = &poly.evaluations[row_len..2 * row_len];
597        let a = Int::from(3);
598        let b = Int::<4>::from(5);
599        let combined_evals: Vec<_> = (0..row_len)
600            .map(|i| a * row1_evals[i] + b.resize() * row2_evals[i])
601            .collect();
602        let combined_encoded = pp.linear_code.encode(&combined_evals);
603        let rows = encoded.as_rows().collect_vec();
604        let row1_encoded = rows[0];
605        let row2_encoded = rows[1];
606        let expected_combined: Vec<_> = (0..codeword_len)
607            .map(|i| a.resize() * row1_encoded[i] + b.resize() * row2_encoded[i])
608            .collect();
609        assert_eq!(combined_encoded, expected_combined);
610    }
611
612    #[test]
613    #[should_panic]
614    fn commit_panics_if_evaluations_not_multiple_of_row_len() {
615        let num_vars = 10;
616        let (pp, mut poly) = setup_test_params(num_vars);
617        poly.evaluations.truncate(15);
618        assert_eq!(poly.evaluations.len(), 15);
619        let _ = TestZip::commit_single(&pp, &poly);
620    }
621
622    #[test]
623    #[cfg_attr(miri, ignore)] // long running
624    fn commit_with_many_variables() {
625        let num_vars = 16;
626        let (pp, poly) = setup_test_params(num_vars);
627        assert_eq!(pp.num_vars, num_vars);
628        let result = TestZip::commit_single(&pp, &poly);
629        assert!(result.is_ok());
630    }
631
632    #[test]
633    #[cfg_attr(miri, ignore)] // long running
634    fn commit_with_smallest_matrix_arrangement() {
635        let num_vars = 8;
636        let (pp, poly) = setup_test_params(num_vars);
637        let poly_size = 1 << num_vars;
638        assert_eq!(pp.num_rows, 1);
639        assert_eq!(pp.linear_code.row_len(), poly_size);
640        let result = TestZip::commit_single(&pp, &poly);
641        assert!(result.is_ok());
642    }
643
644    #[test]
645    fn encode_rows_handles_large_integer_values() {
646        let num_vars = 10;
647        let (pp, _) = setup_test_params(num_vars);
648        let poly_size = 1 << num_vars;
649        let max_val = Int::<INT_LIMBS>::from(i64::MAX);
650        let poly = DenseMultilinearExtension::from_evaluations_vec(
651            num_vars,
652            vec![max_val; poly_size],
653            Zero::zero(),
654        );
655        let encoded_rows = TestZip::encode_rows(&pp, &poly.evaluations);
656        assert_eq!(encoded_rows.num_rows, pp.num_rows);
657        assert_eq!(encoded_rows.num_cols, pp.linear_code.codeword_len());
658    }
659
660    #[test]
661    #[should_panic(expected = "row_width.is_power_of_two()")]
662    fn merkle_tree_new_panics_on_non_power_of_two_leaves() {
663        let leaves_data: Vec<Int<INT_LIMBS>> = (0..7).map(Int::from).collect();
664        let _ = MerkleTree::new(&[leaves_data.as_slice()]);
665    }
666
667    fn make_poly_batch(
668        num_vars: usize,
669        batch_size: usize,
670    ) -> Vec<DenseMultilinearExtension<BinaryPoly<DEGREE_PLUS_ONE>>> {
671        let poly_size = 1 << num_vars;
672        let d = DEGREE_PLUS_ONE - 1;
673        (0..batch_size)
674            .map(|b| {
675                let coeffs: Vec<Boolean> = (0..poly_size * d)
676                    .map(|i| ((i + b * 7) % 3 != 0).into())
677                    .collect();
678                let evals = coeffs.chunks_exact(d).map(BinaryPoly::new).collect_vec();
679                DenseMultilinearExtension::from_evaluations_vec(num_vars, evals, Zero::zero())
680            })
681            .collect()
682    }
683
684    #[test]
685    fn batch_commit_poly_succeeds() {
686        let num_vars = 8;
687        let (pp, _) = setup_poly_test_params::<K, M, DEGREE_PLUS_ONE>(num_vars);
688        let polys = make_poly_batch(num_vars, 3);
689
690        let (hint, comm) = TestPolyZip::commit(&pp, &polys).unwrap();
691        assert_eq!(comm.batch_size, 3);
692        assert_eq!(hint.cw_matrices.len(), 3);
693    }
694
695    #[test]
696    fn batch_commit_poly_is_deterministic() {
697        let num_vars = 8;
698        let (pp, _) = setup_poly_test_params::<K, M, DEGREE_PLUS_ONE>(num_vars);
699        let polys = make_poly_batch(num_vars, 2);
700
701        let (_, comm_a) = TestPolyZip::commit(&pp, &polys).unwrap();
702        let (_, comm_b) = TestPolyZip::commit(&pp, &polys).unwrap();
703        assert_eq!(comm_a.root, comm_b.root);
704    }
705
706    #[test]
707    fn batch_commit_poly_single_matches_commit_single() {
708        let num_vars = 10;
709        let (pp, poly) = setup_poly_test_params::<K, M, DEGREE_PLUS_ONE>(num_vars);
710
711        let polys = std::slice::from_ref(&poly);
712        let (single_hint, single_comm) = TestPolyZip::commit_single(&pp, &poly).unwrap();
713        let (batched_hint, batched_comm) = TestPolyZip::commit(&pp, polys).unwrap();
714
715        assert_eq!(batched_comm.root, single_comm.root);
716        assert_eq!(batched_hint.cw_matrices.len(), 1);
717        assert_eq!(batched_hint.cw_matrices[0], single_hint.cw_matrices[0]);
718    }
719
720    #[test]
721    #[cfg_attr(miri, ignore)] // long running
722    fn batch_commit_poly_different_polys_produce_different_roots() {
723        let num_vars = 10;
724        let (pp, _) = setup_poly_test_params::<K, M, DEGREE_PLUS_ONE>(num_vars);
725        let polys = make_poly_batch(num_vars, 2);
726
727        let (_, batched) = TestPolyZip::commit(&pp, &polys).unwrap();
728        let (_, single0) = TestPolyZip::commit_single(&pp, &polys[0]).unwrap();
729        let (_, single1) = TestPolyZip::commit_single(&pp, &polys[1]).unwrap();
730
731        assert_ne!(batched.root, single0.root);
732        assert_ne!(batched.root, single1.root);
733    }
734
735    #[test]
736    #[cfg_attr(miri, ignore)] // long running
737    fn batch_commit_cw_matrices_are_distinct_per_poly() {
738        let num_vars = 10;
739        let (pp, _) = setup_test_params(num_vars);
740        let poly_size = 1 << num_vars;
741        let polys: Vec<DenseMultilinearExtension<_>> = vec![
742            (1..=poly_size).map(Int::from).collect(),
743            (poly_size + 1..=poly_size * 2).map(Int::from).collect(),
744        ];
745
746        let (hint, _) = TestZip::commit(&pp, &polys).unwrap();
747        assert_eq!(hint.cw_matrices.len(), 2);
748        assert_ne!(hint.cw_matrices[0], hint.cw_matrices[1]);
749    }
750
751    #[test]
752    #[cfg_attr(miri, ignore)] // long running
753    fn proof_size_is_correct_for_parameters() {
754        use std::mem::size_of;
755
756        fn calculate_expected_proof_size_bytes(
757            pp: &ZipPlusParams<Zt, C>,
758            batch_size: usize,
759        ) -> usize {
760            // size of a single entry of cw_matrix
761            let size_of_zt_k = K * size_of::<Word>();
762            // size of CombR in combine row
763            let size_of_zt_m = M * size_of::<Word>();
764            // size_f = field_value || field_modulus
765            let size_of_f = 2 * U256::LIMBS * size_of::<Word>();
766            let size_of_usize_field = size_of::<u64>();
767            let size_of_path_elem = size_of::<MtHash>();
768
769            let codeword_len = pp.linear_code.codeword_len();
770            let merkle_depth = codeword_len.next_power_of_two().ilog2() as usize;
771
772            // b vectors: per poly, 1-byte length prefix + num_rows field elements
773            let b_phase_size = batch_size * (1 + pp.num_rows * size_of_f);
774            let combined_row_size = pp.linear_code.row_len() * size_of_zt_m;
775
776            // Column openings: per opening, column values from all cw_matrices + one Merkle
777            // proof
778            let column_values_size = batch_size * pp.num_rows * size_of_zt_k;
779            let single_merkle_proof_size =
780                size_of_usize_field * 3 + merkle_depth * size_of_path_elem;
781            let column_opening_phase_size =
782                Zt::NUM_COLUMN_OPENINGS * (column_values_size + single_merkle_proof_size);
783
784            b_phase_size + combined_row_size + column_opening_phase_size
785        }
786
787        type F = BoxedMontyField;
788
789        let mut rng = rng();
790        let num_vars = 10;
791        let poly_size: usize = 1 << num_vars;
792        let param = TestZip::setup(poly_size, C.clone());
793        let evaluations: Vec<_> = (0..poly_size)
794            .map(|_| <Zt as ZipTypes>::Eval::from(rng.random::<i8>()))
795            .collect();
796        let mle =
797            DenseMultilinearExtension::from_evaluations_slice(num_vars, &evaluations, Zero::zero());
798        let point: Vec<_> = (0..num_vars)
799            .map(|_| <Zt as ZipTypes>::Pt::random(&mut rng))
800            .collect();
801
802        let (hint, comm) = TestZip::commit_single(&param, &mle).unwrap();
803        let mut transcript = PcsProverTranscript::new_from_commitment(&comm);
804        let field_cfg = get_field_cfg::<Zt, F>(&mut transcript.fs_transcript);
805
806        let _eval_f = TestZip::prove_single::<F, CHECKED>(
807            &mut transcript,
808            &param,
809            &mle,
810            &point,
811            &hint,
812            &field_cfg,
813        )
814        .unwrap();
815        let actual_proof_size_bytes = transcript.stream.get_ref().len();
816        let expected_proof_size_bytes = calculate_expected_proof_size_bytes(&param, 1);
817        assert_eq!(actual_proof_size_bytes, expected_proof_size_bytes);
818    }
819}
zip_plus/pcs/phase_commit.rs

zip_plus/pcs/
phase_commit.rs
