Basefold多项式承诺方案如何推广FRI

介绍

lambdaworks 是一个旨在提供高效证明系统的库。我们希望它支持最先进的 Prover 和相关的原语，以便人们可以使用它们来构建新的应用程序。在这些原语中，我们有 polynomial commitment schemes (PCS)。这是一种强大的密码学工具，允许我们通过小型数据结构（例如 Merkle 树的根或椭圆曲线上的一个点）将自己绑定到给定的多项式，并证明它在某些点上的求值。多项式承诺方案包含以下五个算法：

• Setup：给定一个安全参数，$\lambda$，它会生成 PCS 的公共参数（pp）。
• Commit：接受 pp 和一个多项式，$p$，输出多项式的承诺 $cm(p)$。
• Open：给定 pp、多项式 $p$ 和对 $p$ 的承诺 $cm(p)$，检查 $cm(p)$ 是否是对 $p$ 的承诺。
• Prove evaluation：给定 pp、多项式 $p$、点 $z$ 和声明的求值 $v$，输出一个证明 $\pi$，证明 $p(z)=v$。
• Verify evaluation：给定 pp、对 $p$ 的承诺、证明 $\pi$、点 $z$ 和声明的值 $v$，检查求值证明是否有效。

多项式承诺方案是现代 SNARK 的基本构建块之一。一些承诺方案需要可信设置（例如 KZG），而另一些则是透明的（例如 FRI、Brakedown 和 IPA）。不同的 PCS 在求值证明大小、求值时间、安全假设和其他代数性质（例如，加法同态）之间提供权衡。

Basefold 将 FRI 承诺方案 推广到不同于 Reed-Solomon 的其他代码。不过，这些代码需要具有某些属性。这篇文章将讨论编码理论的基础知识，并解释 basefold 的工作原理。

编码理论

纠错码是表示数据的一种方式，即使部分数据已损坏，我们仍然可以恢复信息。我们通过引入冗余来实现这一点，即使部分冗余数据已损坏，也可以恢复消息。在最大化纠错和冗余之间存在权衡：具有较高冗余的代码应该能够容忍更高数量的错误。

字母表 $\Sigma$ 上的块长度为 $n$ 的代码是 $\Sigma^n$ 的一个子集。在我们的例子中，我们将对字母表 $\Sigma$ 是某个有限域 $F$ 且 $|\Sigma|=q$ 的代码感兴趣。

维度为 $k$ 和块大小为 $n$ 的代码的速率由 $\rho=k/n$ 给出，并且是对代码中引入的冗余量的度量。

给定一个代码，两个码字之间的汉明距离 $d$，由它们不同的位置数给出。相对距离是距离与块长度之比，$\delta=d/n$。

$\Sigma^n$ 上维度为 $k$ 和距离为 $d$ 的代码称为 $(n,k,d)_\Sigma$ - 代码。线性代码是指码字的任何线性组合都会产生一个码字（也就是说，如果 $c_0$ 和 $c_1$ 分别是 $m_0$ 和 $m_1$ 的编码，则 $\alpha_0c_0+\alpha_1c_1$ 也是一个码字，具体来说，是与 $\alpha_0m_0+\alpha_1m_1$ 关联的码字）。

对于线性代码，编码函数可以使用生成矩阵 $G$ 表示为向量矩阵乘积，即

$Enc(v)=v.G$

例如，Reed-Solomon 代码使用具有点 $\alpha_0,\alpha1,...,\alpha{n-1}$ 的 Vandermondian 矩阵：

$V(\alpha_0,\alpha1,...,\alpha{n-1},k)_{i,j}=\alpha_i^j$

Reed-Solomon 代码的工作原理是将消息解释为 $k-1$ 次多项式的系数。如果消息是 $(m_0,m1,...,m{k-1})$，我们可以将它们视为 $m_0+m1x+...+m{k-1}x^{k-1}$，并提供 $n$ 个不同点上的求值。由于多项式的次数最多为 $k-1$，因此它最多有 $k-1$ 个零点，使得两个不同的码字最多在 $k-1$ 个位置重合，因此 $d=n-k+1$。满足 $d=n-k+1$ 的代码称为最大距离可分代码。

Basefold

Basefold 适用于可折叠线性码。请记住，我们可以通过生成矩阵 $G$ 来表示线性码。可折叠线性 $(n,k,d)$ - 代码的生成矩阵 $G_{k,n}$ 具有以下块矩阵结构：

$G{k,n}=[G{k/2,n/2} \mid G{k/2,n/2} \mid G{k/2,n/2}T{k/2,n/2} \mid G{k/2,n/2}T'_{k/2,n/2}]$

其中，$G{k/2,n/2}$ 是可折叠线性 $[n/2,k/2,d']\Sigma$ 代码的生成矩阵。

例如，当在大小为 $n=2^m$ 的乘法子群上实例化时，Reed-Solomon 代码满足此属性（我们还假设 $\rho=2^{-\beta}$）。如果我们选择子群的生成器 $g$ 并将点表示为 ${1,g,g^2,...g^{m-1}}$，我们有

G_{k,n}=\[
egin{array}{cccccccccccccccc}
1 & 1 & 1 & 1 & \cdots & 1 \
g & g^2 & g^3 & \cdots & g^{m-1} \
1 & g^2 & g^4 & g^6 & \cdots & g^{2(m-1)} \
1 & g^3 & g^6 & g^9 & \cdots & g^{3(m-1)} \
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \
1 & g^{k-1} & g^{2(k-1)} & g^{3(k-1)} & \cdots & g^{(k-1)(m-1)}
\end{array}
\]

让我们通过首先按递增顺序放置所有偶数行，然后放置所有奇数行来重新排序矩阵的行。我们得到，

G_{k,n}=\[
egin{array}{cccccccccccccccc}
1 & 1 & 1 & 1 & \cdots & 1 \
1 & g^2 & g^4 & g^6 & \cdots & g^{2(m-1)} \
1 & g^4 & g^8 & g^{12} & \cdots & g^{4(m-1)} \
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \
1 & g & g^2 & g^3 & \cdots & g^{m-1} \
1 & g^3 & g^6 & g^9 & \cdots & g^{3(m-1)} \
1 & g^5 & g^{10} & g^{15} & \cdots & g^{15(m-1)} \
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \
1 & g^{k-1} & g^{2(k-1)} & g^{3(k-1)} & \cdots & g^{(k-1)(m-1)}
\end{array}
\]

我们可以看到，较低的块（奇数行）看起来有点类似于上面的块，除了大多数列都移动了类似的量。例如，第一列缺少一个因子 $g$，第二列缺少一个因子 $g^2$，第三列缺少 $g^3$，依此类推。因此，我们将矩阵分成了上半部分和下半部分。我们需要将每个部分分成左右两部分。

如果 $g$ 是阶数为 $m$ 的群的生成器，则 $\omega=g^2$ 是阶数为 $m/2$ 的子群的生成器。一旦我们有了类似 $\omega^{m/2}$ 的东西，我们就会回到 $1$。这会将上半部分分成两个相同的矩阵，它们对应于 $G_{k/2,n/2}$。在下半部分中，对角矩阵是：

$T_{i,i}=g^i$

$T'_{i,i}=g^{m/2}g^i$

但是 $g^{m/2}=-1$，所以 $T=-T'$。

我们看到线性可折叠代码概括了我们在 Reed-Solomon 代码中拥有的此属性。但是，除了满足可折叠线性代码定义之外，对生成矩阵没有任何限制。这使我们可以更自由地选择对角矩阵 $T,T'$，并且能够使用非 FFT 友好的字段（这使得 basefold PCS 与字段无关）。在 basefold 中，他们设置矩阵 $T=-T'$，并且它们的元素是从基域的乘法群中随机采样的。我们可以通过选择 $G_0$ 和 $T_0,T'_0$ 并获得 $G_1$，然后将其与 $T_1,T'_1$ 一起获得 $G_2$，等等，以归纳方式构造生成矩阵。要编码消息 $v$，我们只需执行 $v.G_d$。我们还可以以递归方式对 $v$ 进行编码，

1. 如果 $d=0$，$enc_0(v)=v.G_0$
2. 否则，将 $v$ 拆分为前后两半 $v=(w_0,w_1)$。令 $c_0=enc(w_0)$，$c_1=enc(w_1)$，$t=diagonal(T)$ 并计算 $enc(v)=(m_0+m_1 \times t,m_0-m_1 \times t)$，其中 $\times$ 是分量 (Hadamard) 乘积。

多线性多项式 $p$ 在 $z$ 处的求值可以通过 sumcheck 协议 转换为 $p$ 在随机点处的求值检查。FRI 的工作方式类似：FRI 中发送的最后一个值对应于第一轮多项式的随机求值的编码。因此，可以通过使用对某些多项式 $p$ 的编码的 Merkle 树承诺来构造 PCS。在求值期间，Prover 和 Verifier 使用同一组挑战并行运行邻近性测试和 sumcheck 协议。Verifier 可以检查多项式的求值是否与邻近性测试中 Prover 的最后一条消息相对应。

Basefold 的邻近性测试的工作方式与 FRI 相同。我们有一个 commit 阶段，Prover 承诺码字/求值列表，以及一个 query 阶段，Verifier 检查码字之间的一致性。在 commit 阶段，

1. Prover 从 $\pi_d$ 开始，这是某个多项式的编码。
2. 对于 $i = d-1$ 到 $0$

a. 从 Verifier 中采样 $\alpha_i$。

b. 对于 $n_i$ 中的每个 $j$，Prover 计算穿过 $(Ti[j,j],\pi{i+1}[j])$ 和 $(-Ti[j,j],\pi{i+1}[j+n_i])$ 的直线 $l_j(x)$，并设置 $\pi_i[j]=l(\alpha_j)$

c. Prover 承诺 $\pi_i$。

事实上，此 commit 阶段与 FRI 相同。我们从组合多项式 $f$（它是多项式的 Reed-Solomon 编码）的求值开始，我们之前已承诺于该多项式。我们采样折叠挑战 $\alpha_i$，然后获得以下函数 $l(x)=(f(x_0)+f(-x_0))/2+x(f(x_0)-f(-x_0))/(2x_0)$。我们可以看到 $l(x_0)=f(x_0)$ 和 $l(-x_0)=f(-x_0)$，这本质上是穿过这两个点的直线。

在 query 阶段，

1. Verifier 在 $[0,n_d-1]$ 中采样一个索引 $i$。
2. 对于 $j=d-1$ 到 $0$，

a. 查询 $\pi{j+1}[i]$ 和 $\pi{j+1}[i+n_i/2]$

b. 计算穿过这两个点的直线 $l_i(x)$。

c. 检查 $\pi_j[i]=l(\alpha_j)$

d. 如果 $j>0$ 并且 $i>n{i-1}$，则设置 $i=i-n{i-1}$。

3. 最后，使用生成矩阵 $G_0$ 检查 $\pi_0$ 是否为有效码字。

为了减少可靠性错误，Verifier 可以查询更多索引，就像我们在 FRI 中所做的那样。我们仅缺少求值协议（证明和验证）。要构造它，我们需要使用 sumcheck 协议以及邻近性测试。

在协议开始时，Verifier 可以访问多项式的编码 $\pi_d$、求值点 $z$ 和声明的求值 $v$。该协议按如下方式进行：

1. Prover 将单变量多项式 $h_d(x)=\sum_bf(b,x)eq_z(b,x)$ 发送给 Verifier。
2. 对于 $i=d-1$ 到 $0$，

a. Prover 运行 commit 阶段的步骤 2.a、2.b、2.c。

b. 如果 $i>0$，Prover 发送 $h_i=\sum_bf(b,x,ri,...,r{d-1})eq_z(b,x,ri,...,r{d-1})$。

3. Verifier：

a. 检查邻近性测试的 query 阶段。

b. 执行 sumcheck 协议中的所有检查

c. 验证 $enc_0(h_1(r_0)/eq_z(r0,...r{d-1}))=\pi_0$

我们看到求值协议基本上由同时运行的 sumcheck 和邻近性测试组成。

结论

这篇文章讨论了一种新的承诺方案 basefold，它是 FRI 的概括。与 FRI 相比，主要优势在于新承诺更好地适用于多线性多项式并且与字段无关。该构造可以使用任何可折叠线性码来实例化。这些是生成矩阵具有给定块结构的代码。我们将在未来将这种新的承诺方案添加到 lambdaworks 中，并将其性能与其他构造进行比较。

• 原文链接： blog.lambdaclass.com/how...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～