Jagged 多项式承诺用于在列高不规则的矩阵中高效进行承诺和验证。通过定义稀疏与稠密多项式的映射，并使用多变量 Sumcheck 协议验证它们在随机点的一致性，从而实现高效、灵活的零知识证明支持。

# 不规则多项式承诺（Jagged Polynomial Commitments）

## 矩阵结构概述

假设有一个固定大小的矩阵，行数为 $2^n$，列数为 $2^k$。该矩阵有两种表示方式：

1. 将每一列视为一个多变量多项式。这将产生 $2^k$ 个 $n$ 变量多项式。
2. 使用一个单一的多项式 $f_c(x_1,\ldots,x_k;y_1,\ldots,y_n)$，其中 $x$ 表示列索引，$y$ 表示行索引。这是一个 $(n+k)$ 变量的多项式。

在 zkVM 系统中，一个主要的挑战是最终的递归深度（即矩阵的高度）在开始时并不确定。此外，每一列的非零项数量不同。

不规则多项式承诺方案（Jagged PCS）旨在解决在列高不规则的情况下如何高效地承诺与验证的问题。

## 数据结构：不规则 / 稀疏 / 稠密

* **不规则（Jagged）** 表示每一列具有不同的高度：

```
列1:   █ █ █
列2:   █ █
列3:   █ █ █ █
```

* **稀疏（Sparse）** 用零进行填充以表示相同结构：

```
列1:   █ █ █ 0
列2:   █ █ 0 0
列3:   █ █ █ █
```

* **稠密（Dense）** 是完全填充的矩阵，支持标准的 PCS 操作。

Jagged PCS 引入约束，使得从稀疏格式转化为稠密格式的过程中，只有有效（非填充）的值被用于验证。

## 不规则函数的定义

将稀疏矩阵编码为一个函数：

* 定义域是大小为 $2^n \times 2^k$ 的表格，每列最多包含 $2^k$ 个元素。
* 向量 $t_y$ 记录每列的有效高度。**累计高度**是非零元素的累加计数；**每层高度**是每列的非零项数量。
* 希望定义函数 $p: {0,1}^n \times {0,1}^k \to \mathbb{F}$。
* 约束条件为：仅当 $j \in \in [0, 2^n)$ 且 $i < t_u\in [i]$ 时，$p(x, y) \ne 0$。

关注的是在有限乘法次数下（即非零项数量受限）如何高效表示。

## 不规则多项式承诺

对大小为 $2^n \times 2^k$ 的稀疏矩阵进行承诺：

* 每一列有一个有效高度 $t_y\in [j]$。
* 设 $t_{kj} = h_t + t_y\in [j]$。
* 构造 $t_{kj}$ 为单调递增序列。

为索引稀疏多项式，定义 $row(i),\ col(i)$：

* 对于 $i \in {0,\ldots, M-1}$ 和 $j \in {0,\ldots,2^n-1}$。
* 找到最小的 $t_y\in [j]$，使得 $i < t_{kj}$。
* 令 $col(i) = j$，并令 $row(i) = i - t_{kj-1}$，表示稀疏多项式中第 $i$ 个元素在第 $row(i)$ 行、第 $j$ 列。
* 对应的 $(row(i), col(i))$ 就是稠密矩阵中的位置。

## 稀疏与稠密表示的转换

定义稀疏函数 $q(i) = p(row(i), col(i))$，其中：

* $q: {0,1}^m \to \mathbb{F}$，$m$ 是非零元素的数量（可能有填充 0）。
* $p: {0,1}^k \times {0,1}^n \to \mathbb{F}$，对应于指定行列位置的元素。

从稀疏多项式 $p$ 到稠密多项式 $q$ 的转换方法如下：

* 将稀疏函数视为基于索引的函数 $q(i)$，映射到 $(row(i), col(i))$。
* 这提供了 $p$ 在 $(x,y)$ 上的稠密表示。

## 交互协议（稀疏到稠密的转换）——专注于 PIOP 层

### 目标：

使用多变量 Sumcheck 协议验证稀疏多项式 $p$ 与稠密多项式 $q$ 之间的一致性。

* 证明者提供 $p: {0,1}^k \times {0,1}^n \to \mathbb{F}$ 和 $q: {0,1}^m \to \mathbb{F}$。
* 定义映射函数 row(i), col(i)，其中 $M = 2^m$ 是非零元素的个数。
* 验证者选择随机值 $Z_r, Z_c \in \mathbb{F}^k$。
* 验证目标为：

$$
\hat{p}(Z_r, Z_c) = \sum 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)
$$

其中 $\hat{p}$ 是 $p$ 的多线性扩展，$eq$ 是相应的拉格朗日基多项式。

### 问题简化为证明：

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

构造步骤如下：

1. 定义 $f_c(Z_r, Z_c, i) = eq(row(i), Z_r) \cdot eq(col(i), Z_c)$。
2. 使用 Sumcheck 协议验证以下等式：

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

## 拓展讨论

### 构造 $f_c$

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

其中 $b_i$ 是 $i$ 的二进制展开，$e_{c1}$ 和 $e_{c2}$ 是布尔选择器多项式：

* $e_{c1}(Z_r, b_i) = \prod_j(Z_r\in [j] \cdot b_i\in [j] + (1 - Z_r\in [j]) \cdot (1 - b_i\in [j]))$。
* $e_{c2}$ 定义方式类似。

这些多项式保证当且仅当 $row(i) = Z_r$ 且 $col(i) = Z_c$ 时，取值为 1；否则为 0。

### 多线性扩展与 Sumcheck

* 给定 $f: {0,1}^n \to \mathbb{F}$，可以扩展为 $\widetilde{f}: \mathbb{F}^n \to \mathbb{F}$。
* 使用标准多线性扩展公式：

$$
\widetilde{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}
$$

* 多变量 sumcheck 可用于验证多项式在随机点 $z$ 处的值是否正确。

最终步骤中，对 $i \in {0,1}^m$ 执行 sumcheck：

* 使用 $f_c(Z_r, Z_c, i)$ 作为选择器。
* 输入值为 $q(i)$。
* 验证加权和是否等于 $p(Z_r, Z_c)$。

完成不规则与稠密多项式承诺之间一致性的验证。

不规则多项式承诺（Jagged Polynomial Commitments）

矩阵结构概述