Jagged Polynomial Commitments

Matrix Structure Overview

Assume a matrix with a fixed number of rows $2^n$ and $2^k$ columns. There are two ways to represent this matrix:

1. Treat each column as a separate multivariate polynomial. This results in $2^k$ distinct n-variate polynomials.
2. Use a single polynomial $f_c(x_1,...,x_k; y_1...,y_n)$, where $x$ indexes columns and $y$ indexes rows. This is a single $(n + k)$-variate polynomial.

The main challenge arises in zkVM systems, where the final recursion depth (and hence the matrix height) is unknown at the beginning. Moreover, each column has a different number of non-zero entries.

The Jagged polynomial commitments scheme (PCS) tackles the core problem of how to commit and verify efficiently when column heights are irregular.

Data Structures: Jagged / Sparse / Dense

• Jagged means each column has a different height:

• Sparse represents the same structure, padded with zeros:

• Dense is the fully padded matrix that supports standard PCS operations.

Jagged PCS adds constraints to transition from sparse to dense format, so that only valid (non-padding) values are used in verification.

Definition of Jagged Function

We encode the sparse matrix as a function:

• The domain is a table of size $2^n \times 2^k$, where each column can have up to $2^k$ entries.
• A vector $t_y$ records the valid height of each column. Cumulative height refers to the running count of non-zero elements; per-layer height refers to the number of non-zero entries per column.
• The goal is to define a function $p: \{0,1\}^n \times \{0,1\}^k \to F$.
• Constraint: $p(x,y) \neq 0$ only when $j \in [0,2^n)$, $i < t_u[i]$.

We focus on efficient representation under a bounded number of multiplications (i.e., number of non-zero entries).

Jagged Polynomial Commitment

To commit to a sparse matrix of size $2^n \times 2^k$.

• Each column has a valid height $t_y[j]$.
• Let $t_{kj} = h_j + t_y[j]$.
• Construct $t_{kj}$ as a monotonically increasing sequence.

To index sparse polynomials, we define $row(i), col(i)$:

• For $i \in [0, ..., M-1]$ and $j \in [0, ..., 2^n - 1]$.
• Find the smallest $t_y[j]$ such that $i < t_{kj}$.
• Let $col(i) = j$, and $row(i) = i - t_{kj-1}$ — this gives the position of the i-th element in the Sparse Polynomial at row $row(i) = i - t_{kj-1}$ and column $j$.
• The pair $(row(i), col(i))$ determines the corresponding position in the dense matrix.

Converting Between Sparse and Dense Representations

We define the sparse function $q(i) = p(row(i), col(i))$, where:

• $q: \{0,1\}^m \to F$, where $m$ is the number of non-zero elements (padding zeros may be present).
• $p: \{0,1\}^k \times \{0,1\}^n \to F$, which corresponds to the element at a given row and column.

Conversion between $p$ (sparse polynomial) and $q$ (dense polynomial):

• Treat the sparse function as an index-based function $q(i)$, mapping to $(row(i), col(i))$.
• This gives a dense representation of $p$ over $(x,y)$.

Interactive Protocol (Sparse to Dense Conversion) – Focus on PIOP Layer

Goal:

Use the Multivariate Sumcheck Protocol to verify the consistency between the sparse polynomial $p$ and dense polynomial $q$.

• Prover provides $p: \{0,1\}^k \times \{0,1\}^n \to F$ and $q: \{0,1\}^m \to F$.
• Define mapping functions $row(i), col(i)$, where $M = 2^m$ is the number of non-zero elements.
• Verifier chooses random $Z_r, Z_c \in F^k$.
• The goal is to verify:

\[ \hat{p}(Z_r, Z_c) = \sum_{x} \sum_{y} p(x,y) \cdot eq(x, Z_r) \cdot eq(y, Z_c) = \sum_{i \in [m]} q(i) \cdot eq(row(i), Z_r) \cdot eq(col(i), Z_c) \]

where $\hat{p}$ is the multilinear extension of $p$, and $eq$ is the corresponding Lagrange basis polynomial.

Then reduce the problem to proving:

\[ \hat{p}(Z_r, Z_c) = \sum_{i \in [m]} q(i) \cdot eq(row(i), Z_r) \cdot eq(col(i), Z_c) \]

Construct as follows:

1. Define $f_c(Z_r, Z_c, i) = eq(row(i), Z_r) \cdot eq(col(i), Z_c)$.
2. Use the Sumcheck Protocol to verify the equality:

\[ \sum_{i \in \{0,1\}^m} f_c(Z_r, Z_c, i) \cdot q(i) =^? \hat{p}(Z_r, Z_c) \]

Further Discussion

Construction of $f_c$

\[ f_c(Z_r, Z_c, i) = e_{c1}(Z_r, b_i) \cdot e_{c2}(Z_c, b_i) \]

where $b_i$ is the binary expansion of $i$, and $e_{c1}, e_{c2}$ are boolean selector polynomials:

• $e_{c1}(Z_r, b_i) = \prod_j (Z_r[j] \cdot b_i[j] + (1 - Z_r[j]) \cdot (1 - b_i[j]))$.
• $e_{c2}$ is defined similarly.

These ensure that the value is 1 if and only if $row(i) = Z_r$ and $col(i) = Z_c$, and 0 otherwise.

Multilinear Extension and Sumcheck

• Given $f: \{0,1\}^n \to F$, we can extend it to $\tilde{f}: F^n \to F$.
• Using standard multilinear extension:

\[ \tilde{f}(z) = \sum_{x \in \{0,1\}^n} f(x) \cdot \prod_{j=1}^n (z_j x_j + (1-z_j)(1-x_j)). \]

• The multivariate sumcheck can then verify whether the polynomial evaluates correctly at a random point $z$.

In the final step, we run sumcheck over $i \in \{0,1\}^m$.

• Use $f_c(Z_r, Z_c, i)$ as the selector.
• Input $q(i)$ as the values.
• Verify that their weighted sum equals $\hat{p}(Z_r, Z_c)$.

This completes the consistency check between the jagged and dense polynomial commitments.

Subscribe to the ZKM Blog to stay updated with the latest research by ZKM.

Explore the docs: https://docs.zkm.io/

Start building: https://github.com/ProjectZKM/Ziren

Follow on X: https://x.com/ProjectZKM