HomeBlogNewsTechVision

Jagged Polynomial Commitments

ZKM
Jul 15, 2025
Share on

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:
Coll:
Col2:
Col3:
  • Sparse represents the same structure, padded with zeros:
Coll:
0
Col2:
0
0
Col3:
  • 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

More articles
Analysis of The Plonky2 Protocol
Plonky2 is a zkSNARK protocol based on polynomial commitment and the Plonk-based PIOP interactive proof. It focuses on achieving efficient zkSNARK through the FRI technique. The primary goal of Plonky2 is to improve the efficiency of traditional zkSNARKs in recursive zero-knowledge proof scenarios while enhancing post-quantum security. Its core concept is leveraging the FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) to allow efficient polynomial verification and using random sampling to enhance the integrity and security of the protocol.
ZKM
Feb 11
ZKM at Invisible Garden, ZK Hub & Devcon
The ZKM team began our journey in Thailand by establishing a strong presence at @invisiblgarden, an @Ethereum and ZK-focused developer hub in Chiang Mai. They delivered a series of talks and workshops to showcase ZKM’s technology and its potential applications to the local community.
ZKM
Nov 22
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:
Coll:
Col2:
Col3:
  • Sparse represents the same structure, padded with zeros:
Coll:
0
Col2:
0
0
Col3:
  • 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

Home
Team
whitepapers
BLOG
docs
EVENTS
CONTACT
Brand Guideline
Brand Assets
Terms and Conditions
Privacy Policy for ZKM