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        // The fill loop below writes exactly evals.len() / row_len rows; a
164        // mismatch with pp.num_rows would leave uninitialized rows behind.
165        assert_eq!(
166            evals.len(),
167            pp.num_rows * row_len,
168            "evals length {} does not match num_rows ({}) * row_len ({})",
169            evals.len(),
170            pp.num_rows,
171            row_len,
172        );
173
174        // Performance: Using DenseRowMatrix's linearized row in an uninit form
175        // is much more performant that using Vec<Vec<_>>.
176        let mut encoded_matrix = DenseRowMatrix::<Zt::Cw>::uninit(pp.num_rows, codeword_len);
177
178        cfg_chunks_mut!(encoded_matrix.data, codeword_len)
179            .zip(cfg_chunks!(evals, row_len))
180            .for_each(|(row, evals)| {
181                let encoded: Vec<Zt::Cw> = pp.linear_code.encode(evals);
182                Out::from(row).copy_from_slice(encoded.as_slice());
183            });
184
185        // Safe because we have just initialized all elements.
186        unsafe { encoded_matrix.init() }
187    }
188}
189
190//TODO. Review and add proper test
191#[cfg(test)]
192#[allow(
193    clippy::arithmetic_side_effects,
194    clippy::cast_possible_truncation,
195    clippy::cast_possible_wrap
196)]
197mod tests {
198    use crate::{
199        code::{LinearCode, iprs::IprsCode},
200        merkle::{MerkleTree, MtHash},
201        pcs::{
202            structs::{ZipPlus, ZipPlusParams, ZipTypes},
203            test_utils::*,
204        },
205        pcs_transcript::PcsProverTranscript,
206    };
207    use crypto_primitives::{
208        Matrix,
209        boolean::Boolean,
210        crypto_bigint_int::Int,
211        crypto_bigint_monty::MontyField,
212        crypto_bigint_uint::{U64, U256},
213    };
214    use itertools::Itertools;
215    use num_traits::Zero;
216    use rand::prelude::*;
217    use std::sync::LazyLock;
218    use zinc_poly::{mle::DenseMultilinearExtension, univariate::binary::BinaryPoly};
219    use zinc_utils::CHECKED;
220
221    const INT_LIMBS: usize = U64::LIMBS;
222
223    const N: usize = INT_LIMBS;
224    const K: usize = INT_LIMBS * 4;
225    const M: usize = INT_LIMBS * 8;
226    const DEGREE_PLUS_ONE: usize = 3;
227
228    type Zt = TestZipTypes<N, K, M>;
229    type C = IprsCode<Zt, TestIprsConfig, REP_FACTOR, CHECKED>;
230    static C: LazyLock<C> = LazyLock::new(|| C::new(IPRS_ROW_LEN, IPRS_DEPTH).unwrap());
231
232    type PolyZt = TestBinPolyZipTypes<K, M, DEGREE_PLUS_ONE>;
233    type PolyC = IprsCode<PolyZt, TestIprsConfig, REP_FACTOR, CHECKED>;
234    static POLY_C: LazyLock<PolyC> =
235        LazyLock::new(|| PolyC::new(IPRS_ROW_LEN, IPRS_DEPTH).unwrap());
236
237    type TestZip = ZipPlus<Zt, C>;
238    type TestPolyZip = ZipPlus<PolyZt, PolyC>;
239
240    #[test]
241    #[cfg_attr(miri, ignore)] // long running
242    fn commit_rejects_too_many_variables() {
243        let num_vars = 10;
244        let (pp, _) = setup_test_params(num_vars);
245
246        // Create MLE with a larger number of variables
247        let poly: DenseMultilinearExtension<_> =
248            (1..=(1 << (num_vars + 1))).map(Int::from).collect();
249
250        let result = TestZip::commit_single(&pp, &poly);
251        assert!(result.is_err());
252    }
253
254    #[test]
255    fn commit_is_deterministic() {
256        let num_vars = 10;
257        let (pp, poly) = setup_test_params(num_vars);
258
259        let result1 = TestZip::commit_single(&pp, &poly).unwrap();
260        let result2 = TestZip::commit_single(&pp, &poly).unwrap();
261
262        assert_eq!(result1.1.root, result2.1.root);
263    }
264
265    #[test]
266    fn different_polynomials_produce_different_commitments() {
267        let num_vars = 10;
268        let (pp, _) = setup_test_params(num_vars);
269        let poly_size = 1 << num_vars;
270
271        let poly1 = DenseMultilinearExtension::from_evaluations_vec(
272            num_vars,
273            vec![Int::from(1); poly_size],
274            Zero::zero(),
275        );
276        let poly2 = DenseMultilinearExtension::from_evaluations_vec(
277            num_vars,
278            vec![Int::from(2); poly_size],
279            Zero::zero(),
280        );
281
282        let (_, commitment1) = TestZip::commit_single(&pp, &poly1).unwrap();
283        let (_, commitment2) = TestZip::commit_single(&pp, &poly2).unwrap();
284
285        assert_ne!(commitment1.root, commitment2.root);
286    }
287
288    #[test]
289    fn commit_succeeds_for_small_polynomial() {
290        let num_vars = 4;
291        let num_rows = (1_usize << num_vars).div_ceil(C.row_len());
292        let pp = ZipPlusParams::new(num_vars, num_rows, C.clone());
293
294        let evaluations = vec![Int::from(42); 1 << num_vars];
295        let mut poly =
296            DenseMultilinearExtension::from_evaluations_vec(num_vars, evaluations, Zero::zero());
297        // Zero-pad MLE to match the expected number of evaluations
298        poly.evaluations
299            .resize(pp.num_rows * pp.linear_code.row_len(), Zero::zero());
300
301        let result = TestZip::commit_single(&pp, &poly);
302        assert!(result.is_ok());
303    }
304
305    #[test]
306    fn commit_succeeds_for_two_variables() {
307        let num_vars = 2;
308        let num_rows = (1_usize << num_vars).div_ceil(C.row_len());
309        let pp = ZipPlusParams::new(num_vars, num_rows, C.clone());
310
311        let poly_size = 1 << num_vars;
312        let evaluations: Vec<_> = (1..=poly_size).map(Int::from).collect();
313        let mut poly =
314            DenseMultilinearExtension::from_evaluations_vec(num_vars, evaluations, Zero::zero());
315        // Zero-pad MLE to match the expected number of evaluations
316        poly.evaluations
317            .resize(pp.num_rows * pp.linear_code.row_len(), Zero::zero());
318
319        let result = TestZip::commit_single(&pp, &poly);
320        assert!(result.is_ok());
321    }
322
323    #[test]
324    #[cfg_attr(miri, ignore)] // long running
325    fn batch_commit_produces_different_root_than_individual_commits() {
326        let num_vars = 10;
327        let (pp, _) = setup_test_params(num_vars);
328        let poly_size = 1 << num_vars;
329
330        let poly1: DenseMultilinearExtension<_> = (1..=poly_size).map(Int::from).collect();
331        let poly2: DenseMultilinearExtension<_> =
332            (poly_size + 1..=2 * poly_size).map(Int::from).collect();
333
334        let (_, batched_comm) = TestZip::commit(&pp, &[poly1.clone(), poly2.clone()]).unwrap();
335        let (_, comm1) = TestZip::commit_single(&pp, &poly1).unwrap();
336        let (_, comm2) = TestZip::commit_single(&pp, &poly2).unwrap();
337
338        assert_ne!(batched_comm.root, comm1.root);
339        assert_ne!(batched_comm.root, comm2.root);
340    }
341
342    #[test]
343    #[cfg_attr(miri, ignore)] // long running
344    fn batch_commit_is_deterministic() {
345        let num_vars = 10;
346        let (pp, _) = setup_test_params(num_vars);
347        let poly_size = 1 << num_vars;
348
349        let poly1: DenseMultilinearExtension<_> = (1..=poly_size).map(Int::from).collect();
350        let poly2: DenseMultilinearExtension<_> =
351            (poly_size + 1..=2 * poly_size).map(Int::from).collect();
352
353        let (_, comm_a) = TestZip::commit(&pp, &[poly1.clone(), poly2.clone()]).unwrap();
354        let (_, comm_b) = TestZip::commit(&pp, &[poly1, poly2]).unwrap();
355
356        assert_eq!(comm_a.root, comm_b.root);
357    }
358
359    #[test]
360    #[cfg_attr(miri, ignore)] // long running
361    fn batch_commit_batch_size_is_correct() {
362        let num_vars = 10;
363        let (pp, _) = setup_test_params(num_vars);
364        let poly_size = 1 << num_vars;
365
366        let polys: Vec<DenseMultilinearExtension<_>> = (0..5)
367            .map(|offset| {
368                let start = offset * poly_size + 1;
369                (start..start + poly_size).map(Int::from).collect()
370            })
371            .collect();
372
373        let (hint, comm) = TestZip::commit(&pp, &polys).unwrap();
374        assert_eq!(comm.batch_size, 5);
375        assert_eq!(hint.cw_matrices.len(), 5);
376    }
377
378    #[test]
379    #[cfg_attr(miri, ignore)] // long running
380    fn encode_rows_produces_correct_size() {
381        let num_vars = 10;
382        let (pp, poly) = setup_test_params(num_vars);
383        let encoded = TestZip::encode_rows(&pp, &poly);
384
385        assert_eq!(encoded.num_rows, pp.num_rows);
386        assert_eq!(encoded.num_cols, pp.linear_code.codeword_len());
387    }
388
389    /// Verifies that the output of `encode_rows` is semantically correct by
390    /// comparing it to a direct, row-by-row encoding.
391    #[test]
392    #[cfg_attr(miri, ignore)] // long running
393    fn encoded_rows_match_linear_code_definition() {
394        let num_vars = 10;
395        let (pp, poly) = setup_test_params(num_vars);
396        let encoded = TestZip::encode_rows(&pp, &poly);
397
398        for (i, row_chunk) in encoded.as_rows().enumerate() {
399            let start = i * pp.linear_code.row_len();
400            let end = start + pp.linear_code.row_len();
401            let row_evals = &poly[start..end];
402            let expected_encoding = pp.linear_code.encode(row_evals);
403            assert_eq!(
404                row_chunk,
405                expected_encoding.as_slice(),
406                "Row {i} encoding mismatch",
407            );
408        }
409    }
410
411    /// Verifies that corrupting the encoded data after commitment results in a
412    /// different Merkle root.
413    #[test]
414    #[cfg_attr(miri, ignore)] // long running
415    fn corrupted_encoding_changes_merkle_root() {
416        let num_vars = 10;
417        let (pp, poly) = setup_test_params(num_vars);
418        let (data, commitment) = TestZip::commit_single(&pp, &poly).unwrap();
419
420        assert!(!data.cw_matrices[0].is_empty());
421        let mut cw_matrix = data.cw_matrices[0].to_rows();
422        cw_matrix[0][0] = Int::from(999999);
423        let corrupted_row = cw_matrix[0].clone();
424        let new_tree = MerkleTree::new(&[corrupted_row.as_slice()]);
425        assert_ne!(
426            new_tree.root(),
427            commitment.root,
428            "Corruption should change Merkle root"
429        );
430    }
431
432    #[test]
433    #[cfg_attr(miri, ignore)] // long running
434    fn batch_commit_single_poly_matches_single_commit() {
435        let num_vars = 10;
436        let (pp, poly) = setup_test_params(num_vars);
437
438        let polys = std::slice::from_ref(&poly);
439        let (batched_hint, batched_comm) = TestZip::commit(&pp, polys).unwrap();
440        let (single_hint, single_comm) = TestZip::commit_single(&pp, &poly).unwrap();
441
442        assert_eq!(batched_comm.root, single_comm.root);
443        assert_eq!(batched_hint.cw_matrices.len(), 1);
444        assert_eq!(batched_hint.cw_matrices[0], single_hint.cw_matrices[0]);
445    }
446
447    #[test]
448    #[cfg_attr(miri, ignore)] // long running
449    fn encoded_rows_are_nonzero_for_nonzero_input() {
450        let num_vars = 10;
451        let (pp, poly) = setup_test_params(num_vars);
452        let encoded = TestZip::encode_rows(&pp, &poly.evaluations);
453
454        assert_eq!(encoded.num_rows, pp.num_rows);
455        assert_eq!(encoded.num_cols, pp.linear_code.codeword_len());
456
457        let non_zero_count = encoded.as_rows().flatten().filter(|x| !x.is_zero()).count();
458        assert!(non_zero_count > 0);
459    }
460
461    #[test]
462    fn commit_produces_correct_merkle_tree_count() {
463        let num_vars = 10;
464        let (pp, poly) = setup_test_params(num_vars);
465        let (hint, _) = TestZip::commit_single(&pp, &poly).unwrap();
466
467        assert_eq!(hint.cw_matrices[0].num_rows, pp.num_rows);
468        assert_eq!(hint.cw_matrices[0].num_cols, pp.linear_code.codeword_len());
469    }
470
471    #[test]
472    #[cfg(feature = "parallel")]
473    fn encoding_is_consistent_across_threads() {
474        use rayon::prelude::*;
475
476        let num_vars = 10;
477        let poly_size = 1 << num_vars;
478        let evaluations = (1..=poly_size).map(|v| Int::from(v as i32)).collect();
479        let poly =
480            DenseMultilinearExtension::from_evaluations_vec(num_vars, evaluations, Zero::zero());
481
482        let results: Vec<Vec<Vec<Int<4>>>> = (0..10)
483            .into_par_iter()
484            .map(|_| {
485                let row_len = C.row_len();
486                let pp = ZipPlusParams::new(num_vars, poly_size / row_len, C.clone());
487
488                let rows = TestZip::encode_rows(&pp, &poly.evaluations);
489                let rows: Vec<Vec<_>> = rows
490                    .data
491                    .chunks_exact(pp.linear_code.codeword_len())
492                    .map(|chunk| chunk.to_vec())
493                    .collect();
494                rows
495            })
496            .collect();
497
498        for w in results.windows(2) {
499            assert_eq!(
500                w[0], w[1],
501                "Parallel encoding runs produced inconsistent results: {:?} vs {:?}",
502                w[0], w[1]
503            );
504        }
505    }
506
507    #[test]
508    fn commit_succeeds_for_zero_polynomial() {
509        let num_vars = 10;
510        let (pp, _) = setup_test_params(num_vars);
511        let poly_size = 1 << num_vars;
512        let zero_poly = DenseMultilinearExtension::from_evaluations_vec(
513            num_vars,
514            vec![Zero::zero(); poly_size],
515            Zero::zero(),
516        );
517        let result = TestZip::commit_single(&pp, &zero_poly);
518        assert!(result.is_ok());
519    }
520
521    #[test]
522    fn commit_succeeds_for_alternating_values() {
523        let num_vars = 10;
524        let (pp, _) = setup_test_params(num_vars);
525        let poly_size = 1 << num_vars;
526        let alternating = (0..poly_size)
527            .map(|i| Int::from(if i % 2 == 0 { 1 } else { -1 }))
528            .collect();
529        let poly =
530            DenseMultilinearExtension::from_evaluations_vec(num_vars, alternating, Zero::zero());
531        let result = TestZip::commit_single(&pp, &poly);
532        assert!(result.is_ok());
533    }
534
535    #[test]
536    #[should_panic(expected = "Batch must contain at least one polynomial")]
537    fn batch_commit_on_empty_slice_panics() {
538        let num_vars = 10;
539        let (pp, _) = setup_test_params(num_vars);
540        let empty_polys: Vec<DenseMultilinearExtension<Int<INT_LIMBS>>> = vec![];
541        let _ = TestZip::commit(&pp, &empty_polys);
542    }
543
544    #[test]
545    #[cfg_attr(miri, ignore)] // long running
546    fn encode_rows_succeeds_for_single_row() {
547        // Exactly one code row: poly_size == row_len.
548        let num_vars = C.row_len().ilog2() as usize;
549        let poly_size = 1 << num_vars;
550        let pp = ZipPlusParams::new(num_vars, 1, C.clone());
551
552        let evaluations = vec![Int::from(5); poly_size];
553        let poly =
554            DenseMultilinearExtension::from_evaluations_vec(num_vars, evaluations, Zero::zero());
555        let encoded = TestZip::encode_rows(&pp, &poly.evaluations);
556        assert_eq!(encoded.num_rows, 1);
557        assert_eq!(encoded.num_cols, pp.linear_code.codeword_len());
558    }
559
560    #[test]
561    #[cfg_attr(miri, ignore)] // long running
562    fn encode_rows_succeeds_for_single_poly_row() {
563        // Exactly one code row: poly_size == row_len.
564        let num_vars = POLY_C.row_len().ilog2() as usize;
565        let pp = ZipPlusParams::new(num_vars, 1, POLY_C.clone());
566
567        let evaluations = vec![
568            BinaryPoly::new_padded([Boolean::FALSE, Boolean::FALSE]),
569            BinaryPoly::new_padded([Boolean::FALSE, Boolean::TRUE]),
570            BinaryPoly::new_padded([Boolean::TRUE, Boolean::FALSE]),
571        ];
572        let poly =
573            DenseMultilinearExtension::from_evaluations_vec(num_vars, evaluations, Zero::zero());
574        let encoded = TestPolyZip::encode_rows(&pp, &poly.evaluations);
575        assert_eq!(encoded.num_rows, 1);
576        assert_eq!(encoded.num_cols, pp.linear_code.codeword_len());
577    }
578
579    #[test]
580    #[cfg_attr(miri, ignore)] // long running
581    fn matrix_dimensions_are_invariant() {
582        let test_cases = vec![(8, 1), (10, 4), (12, 16)];
583        for (num_vars, expected_rows) in test_cases {
584            let (pp, poly) = setup_test_params(num_vars);
585            assert_eq!(pp.num_rows, expected_rows);
586            let result = TestZip::commit_single(&pp, &poly);
587            assert!(result.is_ok());
588        }
589    }
590
591    #[test]
592    #[should_panic]
593    fn reject_incompatible_dimensions() {
594        let num_vars = 10;
595        let (pp, poly) = setup_test_params(num_vars);
596        let incompatible_pp = ZipPlusParams::new(8, 8, pp.linear_code);
597        TestZip::commit_single(&incompatible_pp, &poly).unwrap();
598    }
599
600    #[test]
601    #[cfg_attr(miri, ignore)] // long running
602    fn linear_code_preserves_linearity() {
603        let num_vars = 10;
604        let (pp, poly) = setup_test_params(num_vars);
605        let encoded = TestZip::encode_rows(&pp, &poly.evaluations);
606        let row_len = pp.linear_code.row_len();
607        let codeword_len = pp.linear_code.codeword_len();
608        let row1_evals = &poly.evaluations[0..row_len];
609        let row2_evals = &poly.evaluations[row_len..2 * row_len];
610        let a = Int::from(3);
611        let b = Int::<4>::from(5);
612        let combined_evals: Vec<_> = (0..row_len)
613            .map(|i| a * row1_evals[i] + b.resize() * row2_evals[i])
614            .collect();
615        let combined_encoded = pp.linear_code.encode(&combined_evals);
616        let rows = encoded.as_rows().collect_vec();
617        let row1_encoded = rows[0];
618        let row2_encoded = rows[1];
619        let expected_combined: Vec<_> = (0..codeword_len)
620            .map(|i| a.resize() * row1_encoded[i] + b.resize() * row2_encoded[i])
621            .collect();
622        assert_eq!(combined_encoded, expected_combined);
623    }
624
625    #[test]
626    #[should_panic]
627    fn commit_panics_if_evaluations_not_multiple_of_row_len() {
628        let num_vars = 10;
629        let (pp, mut poly) = setup_test_params(num_vars);
630        poly.evaluations.truncate(15);
631        assert_eq!(poly.evaluations.len(), 15);
632        let _ = TestZip::commit_single(&pp, &poly);
633    }
634
635    #[test]
636    #[cfg_attr(miri, ignore)] // long running
637    fn commit_with_many_variables() {
638        let num_vars = 16;
639        let (pp, poly) = setup_test_params(num_vars);
640        assert_eq!(pp.num_vars, num_vars);
641        let result = TestZip::commit_single(&pp, &poly);
642        assert!(result.is_ok());
643    }
644
645    #[test]
646    #[cfg_attr(miri, ignore)] // long running
647    fn commit_with_smallest_matrix_arrangement() {
648        let num_vars = 8;
649        let (pp, poly) = setup_test_params(num_vars);
650        let poly_size = 1 << num_vars;
651        assert_eq!(pp.num_rows, 1);
652        assert_eq!(pp.linear_code.row_len(), poly_size);
653        let result = TestZip::commit_single(&pp, &poly);
654        assert!(result.is_ok());
655    }
656
657    #[test]
658    fn encode_rows_handles_large_integer_values() {
659        let num_vars = 10;
660        let (pp, _) = setup_test_params(num_vars);
661        let poly_size = 1 << num_vars;
662        let max_val = Int::<INT_LIMBS>::from(i64::MAX);
663        let poly = DenseMultilinearExtension::from_evaluations_vec(
664            num_vars,
665            vec![max_val; poly_size],
666            Zero::zero(),
667        );
668        let encoded_rows = TestZip::encode_rows(&pp, &poly.evaluations);
669        assert_eq!(encoded_rows.num_rows, pp.num_rows);
670        assert_eq!(encoded_rows.num_cols, pp.linear_code.codeword_len());
671    }
672
673    #[test]
674    #[should_panic(expected = "row_width.is_power_of_two()")]
675    fn merkle_tree_new_panics_on_non_power_of_two_leaves() {
676        let leaves_data: Vec<Int<INT_LIMBS>> = (0..7).map(Int::from).collect();
677        let _ = MerkleTree::new(&[leaves_data.as_slice()]);
678    }
679
680    fn make_poly_batch(
681        num_vars: usize,
682        batch_size: usize,
683    ) -> Vec<DenseMultilinearExtension<BinaryPoly<DEGREE_PLUS_ONE>>> {
684        let poly_size = 1 << num_vars;
685        let d = DEGREE_PLUS_ONE - 1;
686        (0..batch_size)
687            .map(|b| {
688                let coeffs: Vec<Boolean> = (0..poly_size * d)
689                    .map(|i| ((i + b * 7) % 3 != 0).into())
690                    .collect();
691                let evals = coeffs
692                    .chunks_exact(d)
693                    .map(BinaryPoly::new_padded)
694                    .collect_vec();
695                DenseMultilinearExtension::from_evaluations_vec(num_vars, evals, Zero::zero())
696            })
697            .collect()
698    }
699
700    #[test]
701    fn batch_commit_poly_succeeds() {
702        let num_vars = 8;
703        let (pp, _) = setup_poly_test_params::<K, M, DEGREE_PLUS_ONE>(num_vars);
704        let polys = make_poly_batch(num_vars, 3);
705
706        let (hint, comm) = TestPolyZip::commit(&pp, &polys).unwrap();
707        assert_eq!(comm.batch_size, 3);
708        assert_eq!(hint.cw_matrices.len(), 3);
709    }
710
711    #[test]
712    fn batch_commit_poly_is_deterministic() {
713        let num_vars = 8;
714        let (pp, _) = setup_poly_test_params::<K, M, DEGREE_PLUS_ONE>(num_vars);
715        let polys = make_poly_batch(num_vars, 2);
716
717        let (_, comm_a) = TestPolyZip::commit(&pp, &polys).unwrap();
718        let (_, comm_b) = TestPolyZip::commit(&pp, &polys).unwrap();
719        assert_eq!(comm_a.root, comm_b.root);
720    }
721
722    #[test]
723    fn batch_commit_poly_single_matches_commit_single() {
724        let num_vars = 10;
725        let (pp, poly) = setup_poly_test_params::<K, M, DEGREE_PLUS_ONE>(num_vars);
726
727        let polys = std::slice::from_ref(&poly);
728        let (single_hint, single_comm) = TestPolyZip::commit_single(&pp, &poly).unwrap();
729        let (batched_hint, batched_comm) = TestPolyZip::commit(&pp, polys).unwrap();
730
731        assert_eq!(batched_comm.root, single_comm.root);
732        assert_eq!(batched_hint.cw_matrices.len(), 1);
733        assert_eq!(batched_hint.cw_matrices[0], single_hint.cw_matrices[0]);
734    }
735
736    #[test]
737    #[cfg_attr(miri, ignore)] // long running
738    fn batch_commit_poly_different_polys_produce_different_roots() {
739        let num_vars = 10;
740        let (pp, _) = setup_poly_test_params::<K, M, DEGREE_PLUS_ONE>(num_vars);
741        let polys = make_poly_batch(num_vars, 2);
742
743        let (_, batched) = TestPolyZip::commit(&pp, &polys).unwrap();
744        let (_, single0) = TestPolyZip::commit_single(&pp, &polys[0]).unwrap();
745        let (_, single1) = TestPolyZip::commit_single(&pp, &polys[1]).unwrap();
746
747        assert_ne!(batched.root, single0.root);
748        assert_ne!(batched.root, single1.root);
749    }
750
751    #[test]
752    #[cfg_attr(miri, ignore)] // long running
753    fn batch_commit_cw_matrices_are_distinct_per_poly() {
754        let num_vars = 10;
755        let (pp, _) = setup_test_params(num_vars);
756        let poly_size = 1 << num_vars;
757        let polys: Vec<DenseMultilinearExtension<_>> = vec![
758            (1..=poly_size).map(Int::from).collect(),
759            (poly_size + 1..=poly_size * 2).map(Int::from).collect(),
760        ];
761
762        let (hint, _) = TestZip::commit(&pp, &polys).unwrap();
763        assert_eq!(hint.cw_matrices.len(), 2);
764        assert_ne!(hint.cw_matrices[0], hint.cw_matrices[1]);
765    }
766
767    #[test]
768    #[cfg_attr(miri, ignore)] // long running
769    fn proof_size_is_correct_for_parameters() {
770        use crypto_bigint::Word;
771        use std::mem::size_of;
772
773        fn calculate_expected_proof_size_bytes(
774            pp: &ZipPlusParams<Zt, C>,
775            batch_size: usize,
776        ) -> usize {
777            // size of a single entry of cw_matrix
778            let size_of_zt_k = K * size_of::<Word>();
779            // size of CombR in combine row
780            let size_of_zt_m = M * size_of::<Word>();
781            // Field elements are transcribed raw (no per-element modulus)
782            let size_of_f = U256::LIMBS * size_of::<Word>();
783            let size_of_usize_field = size_of::<u64>();
784            let size_of_path_elem = size_of::<MtHash>();
785
786            let codeword_len = pp.linear_code.codeword_len();
787            let merkle_depth = codeword_len.next_power_of_two().ilog2() as usize;
788
789            // b vectors: per poly, num_rows field elements
790            let b_phase_size = batch_size * (pp.num_rows * size_of_f);
791            let combined_row_size = pp.linear_code.row_len() * size_of_zt_m;
792
793            // Column openings: per opening, column values from all cw_matrices + one Merkle
794            // proof
795            let column_values_size = batch_size * pp.num_rows * size_of_zt_k;
796            let single_merkle_proof_size =
797                size_of_usize_field * 3 + merkle_depth * size_of_path_elem;
798            let column_opening_phase_size =
799                Zt::NUM_COLUMN_OPENINGS * (column_values_size + single_merkle_proof_size);
800
801            b_phase_size + combined_row_size + column_opening_phase_size
802        }
803
804        type F = MontyField<K>;
805
806        let mut rng = rand::rng();
807        let num_vars = 10;
808        let poly_size: usize = 1 << num_vars;
809        let param = TestZip::setup(poly_size, C.clone());
810        let evaluations: Vec<_> = (0..poly_size)
811            .map(|_| <Zt as ZipTypes>::Eval::from(rng.random::<i8>()))
812            .collect();
813        let mle =
814            DenseMultilinearExtension::from_evaluations_slice(num_vars, &evaluations, Zero::zero());
815        let point: Vec<_> = (0..num_vars)
816            .map(|_| rng.random::<<Zt as ZipTypes>::Pt>())
817            .collect();
818
819        let (hint, comm) = TestZip::commit_single(&param, &mle).unwrap();
820        let mut transcript = PcsProverTranscript::new_from_commitment(&comm);
821        let field_cfg = get_field_cfg::<Zt, F>(&mut transcript.fs_transcript);
822
823        let _eval_f = TestZip::prove_single::<F, CHECKED>(
824            &mut transcript,
825            &param,
826            &mle,
827            &point,
828            &hint,
829            &field_cfg,
830        )
831        .unwrap();
832        let actual_proof_size_bytes = transcript.stream.get_ref().len();
833        let expected_proof_size_bytes = calculate_expected_proof_size_bytes(&param, 1);
834        assert_eq!(actual_proof_size_bytes, expected_proof_size_bytes);
835    }
836}
zip_plus/pcs/phase_commit.rs

zip_plus/pcs/
phase_commit.rs
