旋风路：使用WHIR作为多项式承诺方案的多线性STARKs

介绍

以太坊正迅速发展成为世界的金融后端。零知识证明的研究和开发使得以太坊能够通过 Rollup 进行扩展，具体方法是将交易进行链下批处理，然后发布账户的更新以及证明交易有效性的密码学证明。虽然进展令人印象深刻，但仍然存在一些挑战，例如量子计算机的兴起（这将打破以太坊现在核心原语的椭圆曲线密码学）、增加去中心化以及简化协议以减少攻击面和可能的错误。

以太坊在 Devcon 2024 上展示了 Lean Ethereum 的路线图，用于研究、定义规范、开发、测试和部署以太坊的未来，这将使该协议进入维护模式并避免进行重大更改。其中一个关键问题与后量子安全可聚合签名有关，以取代为以太坊共识提供支持的（基于椭圆曲线的）BLS 签名。虽然有几个后量子安全签名的候选方案，但我们应该关注那些可以提供高效聚合算法或其验证可以使用后量子安全证明系统有效证明的方案。使用 SNARK（简洁的非交互式知识论证）友好哈希（例如 Poseidon 2 或 Rescue Prime Optimized）的基于哈希的签名看起来很有希望，因为当前最先进的证明者能够在 GPU 上每秒证明近 1,000,000 个哈希。一个重要的约束与证明大小有关，证明大小应尽可能小，以减少节点之间的通信占用空间。当前的安全分析表明，使用 FRI 以 128 位安全性为目标的证明大小较大，这就是为什么需要不同的候选方案。WHIR 提供了一个很好的候选方案，即使在具体术语上它可能比 FRI 慢。因此，路线图包含至少 4 个要素，目标是使用简洁的知识论证进行后量子安全可聚合签名的原语，这不足为奇：

• Poseidon密码分析倡议。
• 基于哈希的多重签名
• 最小零知识虚拟机（用于处理证明聚合）
• 虚拟机的形式化验证和证明系统的规范。

在这篇文章中，我们将介绍 WHIR 的基础知识，用于证明虚拟机的执行，该虚拟机的执行通过代数中间表示（AIR）来描述。推导非交互式知识论证的方式将是标准的方式，首先是多项式交互式 oracle 证明，使用多项式承诺方案实例化 oracle 证明，并使用 Fiat-Shamir 变换。后续文章将侧重于签名方案和虚拟机。你可以查看 ethresearch 上的 WHIR 演示文稿 以获取更多参考资料，以及 WHIR 论文。有关 Whirlaway 的规范，请参阅 repo，以及 whir-p3。

多线性多项式

如果 $m$ 个变量的多项式中，每个单项式的每个不定元 $x_i$ 的最高次幂最多为 1，则称该多项式为多线性的。

给定函数 $f$ 在 $H^m$ 上的一个评估集合，存在唯一的 $H^m$ 上的多线性多项式 $\hat{f}$，使得对于每个 $x \in H^m$ 都有 $\hat{f}(x)=f(x)$。我们可以使用不同的基来表示相同的多线性多项式，最常见的两个是单项式基 $(1,x_0,x_1,x_0x_1,x_2,x_0x_2,...)$ 和 $H^m$ 上的拉格朗日基。为简单起见，我们此后将 $H={0,1}$。这些定义如下，

$$\chi_k (x) = \mathrm{eq} ( k_b , x) = \prodi ( k{b,i} xi + (\left\k{b,i} - 1)(x_i - 1))$$

其中 $k_b$ 是 $k$ 的二进制分解，即 $k=\sumi k{b,i}2^i$。多线性扩展，给出 $f$ 在 ${0,1}^m$ 上的评估，

$$\hat{f}(x)=\sum_{b\in{0,1}^m}f(b)eq(b,x)=\sum_k f_k\chi_k(x)$$

我们可以很容易地检查，通过评估拉格朗日多项式 $\chi_k(x)$ 并在 $f$ 的评估向量和拉格朗日基多项式的向量之间执行标量积，我们可以在任何点评估 $\hat{f}(x)$，

$$\hat{f}(z)=\sum_k f_k\chi_k(z)=f^t\cdot\chi$$

我们可以通过适当的变换找到一种将多线性多项式视为单变量多项式的方法。给定多线性基中的多项式，

$f(x_0,x_1,x2,\dots x{m-1})=a_0+a_1x_0+a_2x_1+a_3x_0x_1+a_4x_2+a_5x_0x_2+a_6x_1x2+\dots a{2^m-1}x_0x1\dots x{m-1}$

如果我们令 $x_0=x$， $x_1=x^2$， $x2=x^4$， ……， $x{m-1}=x^{2^{m-1}}$，那么

$f(x)=a_0+a_1x+a_2x^2+a_3xx^2+a_4x^4+a_5xx^4+a6x^2x^4+\dots a{2^m-1}xx^2x^4...x^{2^{m-1}}$

进行所有乘积运算，$f(x)=\sum_j a_jx^j$

WHIR 将利用从多线性单项式基到单变量单项式基的这种转换。例如，该论文定义了 $pow(z,m)=(z,z^2,...z^{2^{m-1}})$，用于将多线性多项式评估为 $f(z)$。

Sumcheck 协议

sumcheck 协议是设计高效交互式证明的重要组成部分。sumcheck 协议应用于证明以下形式的语句

$$\sum_{x\in H^\ell}f(x)=S$$

其中 $f(x)$ 是 $\ell$ 个变量中的多元多项式，而 $H$ 是一个集合（通常为 ${0,1}$）。换句话说，我们想要证明 $f$ 在 $H^\ell$ 中所有值上的评估之和等于 $S$。虽然这看起来有点限制性或复杂，但可以通过适当的转换将计算简化为此协议的某个实例。例如，当使用拉格朗日基多项式时，函数在 $z$ 处的多线性扩展的评估可以精确地以这种形式编写，

$$\hat{f}(z)=\sum_{b\in{0,1}^m}f(b)eq(b,z)$$

该协议允许证明者通过向验证者发送 $O(\ell)$ 个元素，并让后者执行 $O(\ell)$ 次运算，以及对随机点 $(r_0,r1,...r{\ell-1})$ 的 $f$ 进行单次评估，来说服验证者总和为 $S$。然后，我们可以使用 Fiat-Shamir 变换和多项式承诺方案（PCS）将此编译为非交互式简洁的知识论证，以授予验证者对 $f(r_0,r1,...r{\ell-1})$ 的 oracle 访问权限。

sumcheck 协议可以多次使用，以将复杂的声明简化为更简单的声明，例如在 Spartan 中。我们还可以通过使用随机线性组合对多个 sumcheck 进行批处理，从而将多个 sumcheck 组合成一个。例如，假设我们要证明：

$$\sum_{x\in H^\ell}f_1(x)=S_1$$

$$\sum_{x\in H^\ell}f_2(x)=S_2$$

我们可以让验证者采样随机标量 $\alpha_1,\alpha_2$，并且我们可以对以下内容运行 sumcheck

$$\sum_{x\in H^\ell}(\alpha_1f_1(x)+\alpha_2f_2(x))=\alpha_1S_1+\alpha_2S_2$$

与单独运行两个实例相比，这减少了证明者需要发送给验证者的元素数量以及所涉及的工作量。

协议概述

在 AIR 中，我们有一组多项式约束，例如：

• $f_0(x_7)=x_7-a_k$，它对第一行有效。这是一个边界约束。
• $f_1(x_0,x_1,x_2,y_0,y_1,y_2)=x_0x_1x_2-y_1y_2y_3$，它对所有连续的行都有效，除了最后一行。这是转换约束的一个例子。
• $f_2(x_3)=x_3(x_3-1)$，并且对所有行都有效，断言 $x_3$ 是一个布尔变量。此约束强制执行一致性条件。

约束由一个多元多项式和一个该约束应用在其上的集合给出。约束的次数（等于单项式的最高次数）很重要，因为它提供了我们需要评估的点数的信息，以便完全确定组合多项式。

在普通的 STARK 中，我们可以通过以下方式检查约束的有效性

1. 插值轨迹列以获得（单变量）轨迹多项式。
2. 将轨迹多项式与约束多项式组合。
3. 将每个约束除以相应的零化子。
4. 使用 FRI 来表明结果接近一个低次多项式。

如果我们想使用多元多项式，我们需要对协议的工作方式进行一些更改。我们将逐步展示一切如何运作。

我们将从轨迹表 $T$ 开始。我们假设轨迹有 $2^n$ 行和 $2^m$ 列。我们总是可以填充不满足此条件的表，或者利用 jagged PCS 的想法来避免填充。该表有 $2^{n+m}$ 个元素，我们可以将其视为多项式 $f_{trace}$ 在 ${0,1}^{n+m}$ 上的评估。在 Whirlaway 中，元素以行优先顺序存储。

轨迹被提交为单个多线性多项式，使用 WHIR 作为多项式承诺方案。我们将所有多项式检查简化为该多项式的单个评估，我们可以通过多项式承诺方案来证明这一点。

我们总是可以通过乘以一个合适的多项式从轨迹多项式中获得列，类似于我们可以使用合适的矩阵向量积从展平的向量中恢复列的方式。如果我们可以表明每个约束多项式在相应的集合上消失，则计算是正确的。假设我们需要证明对于所有行，$f_{16}(X_3)=X_3(X_3-1)=0$，其中 $X_3$ 表示我们需要使用第 3 列评估此多项式。我们称这个多项式为 $c_3(x)$，其中 $c_3(jb)=c{3j}$，其中 $j_b$ 是 $j$ 的二进制表示，其中 $j=0,1,...2^n-1$。约束的有效性等于证明对于 $x=j_b$ 的所有有效值，都有 $c_3(x)(c_3(x)-1)=0$。

我们应用 sumcheck 协议的变体，称为 zerocheck，以表明所有评估在集合上均为零：

$$\sum_{x\in{0,1}^n}eq(\tau,x)c_3(x)(c_3(x)-1)=0$$

其中 $\tau$ 由验证者随机采样。最终，在应用 sumcheck 协议之后，验证者剩下检查 $eq(\tau,r)c_3(r)(c_3(r)-1)=v_r$。验证者可以有效地计算 $eq(\tau,r)$，因为它是一个 $n$ 项的线性乘积。对于 $c_3(r)$，验证者可以查询 oracle，他最终可以执行乘法运算。可以使用 PCS 完成证明评估有效性的操作，但问题是他怎么知道 $c3(r)$ 是正确的，因为证明者承诺的是 $f{trace}(x)$ 而不是单个列？

核心思想是我们可以运行 sumcheck 协议的另一个实例，将轨迹多项式与列联系起来，并将检查简化为单个点。

小小的弯路 - Spartan

Whirlaway 是一个基于 SuperSpartan for AIR 的证明系统，但我们可以通过查看其他多元证明系统（例如 Spartan）来了解它的工作原理。虽然存在一些差异，但核心原则仍然相似。我们将从 R1CS 开始，这是一种表示电路的常用方法，其中我们有矩阵 $A,B,C$（来自 $F^{n\times m}$）和一个向量 $z=(w,1,u)$，其中 $w$ 是见证向量，$u$ 是实例向量，使得

$Az \circ Bz - Cz = 0$

其中 $\circ$ 表示向量的 Hadamard（分量式）乘积。我们可以通过注意以下几点将其转换为 sumcheck 协议的实例：

$F(x)=(\sum_y A(x,y)z(y))(\sum_y B(x,y)z(y))-(\sum_y C(x,y)z(y))$

$\sum_x eq(\tau,x)F(x)=0$

我们可以让证明者完成工作并提供 $a(x)=\sum_y A(x,y)z(y)$、$b(x)=\sum_y B(x,y)z(y)$ 和 $c(x)=\sum_y C(x,y)z(y)$。zerocheck 可以简化为

$eq(\tau,r_x)F(r_x)=v_x=eq(\tau,r_x)(a(r_x)b(r_x)-c(r_x))$

然后，证明者可以通过运行以下 sumcheck 来表明 $a(r_x),b(r_x),c(r_x)$ 是正确的：

$\sum_y A(r_x,y)z(y)=a(r_x)$

$\sum_y B(r_x,y)z(y)=b(r_x)$

$\sum_y C(r_x,y)z(y)=c(r_x)$

所有这些都可以通过采用随机线性组合来组合成单个检查，

$\sum_y(\alpha A(r_x,y)+\beta B(r_x,y)+\gamma C(r_x,y))z(y)=\alpha a(r_x)+\beta b(r_x)+\gamma c(r_x)$

这避免了处理一个大的 sumcheck，并将其分解为处理列的线性组合和一个处理行的线性组合。Whirlaway 利用了这个想法，首先对列执行 zerocheck，然后将列的评估简化为轨迹多项式的评估。

协议中的步骤：

1. 提交轨迹
2. 计算评估转换约束所需的轨迹列 $c{upk}$ 和 $c{downk}$。
3. 使用这些列和多项式约束执行 zerocheck，这将验证者的任务简化为在随机点 $\delta$ 评估 $c{upk}$ 和 $c{downk}$。
4. 批处理所有列的评估声明，并执行内部 sumcheck。
5. 找到列评估的多线性扩展，在 $z$ 处评估，并检查这是否与在点 $(z,\delta)$ 处打开轨迹的承诺相匹配。

WHIR

WHIR 是接近约束 Reed-Solomon 码的交互式 Oracle 证明。FRI 也是接近交互式 Oracle 证明，但针对 Reed-Solomon 码。我们可以将 WHIR 转换为多项式承诺方案，就像我们通过使用 Merkle 树承诺码字将 FRI 转换为 PCS 的方式一样。

在进入实际协议之前，我们将从纠错码的定义开始。

定义（纠错码）：长度为 $n$ 且字母表为 $A$ 的纠错码是 $A^n$ 的子集。 特别是，有限域 $F$ 上的线性码是 $F^n$ 的子空间。

线性码很重要，因为它们允许高效编码，并且码字的线性组合会产生码字。

定义（交织码）：给定一个码 $C \subseteq A^n$，则 $m$ 交织码是码 $C^m \subseteq (A^m)^n$。 码字的每个元素现在是 $A^m$ 的一个元素。

1. 平滑 Reed-Solomon 码

给定一个有限域 $F$，一个次数 $d=2^m$ 和一个评估域 $L \subseteq F^\star$，它必须是一个乘法 陪集，其阶数 $n$ 是 2 的幂，我们定义

$RS[F,L,m]={f:L\rightarrow F: \exists g \in F_{\leq d-1}[X]: s.t.: f(x)=g(x): \forall x \in L}.$

换句话说，它表示来自小次数多项式的所有评估。 在证明系统中，证明者声明函数 $f$ （或其评估）在 $RS[F,L,m]$ 中，以说服验证者 $f$ 是多项式，表明该函数接近次数为 $d-1$ 的多项式。

让我们回顾一下什么是 陪集：例如，在 Stark101 中，我们有一个长度为 1023 的一列轨迹，因此我们将一个子群 $G \subseteq F^\star$ 定义为评估域，其阶数 $|G|=1024$。 然后我们进行插值并希望将域扩大八倍（放大因子为 8），从而创建一个 Reed-Solomon 纠错码。 我们取一个子群 $H \subseteq F^\star$，其 $|H|=8192$，并将 LDE 定义为 $H$ $wH={w\cdot h1,\dots,w\cdot h{8192}}$ 的 陪集，其中 $w$ 是 $F^\star$ 的生成器。

2. 多线性 Reed-Solomon 码：

等效地，这样的 Reed-Solomon 碼可以被視為 $m$ 個變數中的多線性多項式的評估：

$RS[F,L,m]={f:L\rightarrow F: \exists g \in F{< d}[X]: s.t.: f(x)=g(x): \forall x \in L}={f:L\rightarrow F: \exists \hat{f} \in F{\leq 1}[X0,\dots,X{m-1}]: s.t.: f(x)=\hat{f}(x^{2^0},x^{2^1},\dots,x^{2^{m-1}}): \forall x \in L}$

例子： 如果 $m=3$，则 $2^{m-1}=7$ 和 $2^{m-1}=4$。 我们可以将次数为 7 的单变量多项式 $g$ 表示为 3 变量多项式 $\hat{f}$。 事实上，我们只需要三个变量 $X_0,X_1,X_2$，因为 $x^0\cdot x^1\cdot x^2=x^1\cdot x^2\cdot x^4=x^7$。 另一方面，如果我们有一个 3 变量多项式 $\hat{f}$，我们可以将其表示为次数为 7 的单变量多项式 $g$：获得的最大次数在 $x^0\cdot x^1\cdot x^2=x^7$ 中。 例如，多项式 $g(x)=a_0+a_3x^3+a_6x^6$

等价于多项式

$\hat{f}(x_0,x_1,x_2)=a_0x_0+a_1x_0x_2+a_2x_1x_2$

3. 约束 Reed-Solomon 码：

它是具有附加约束的平滑 Reed-Solomon 码。 给定一个权重多项式 $\hat{w} \in F[Z,X_1,\dots,X_m]$ 和一个目标 $\sigma \in F$，我们还需要

$\sum_{b\in{0,1}^m}\hat{w}(\hat{f}(b),b)=\sigma.$

这可以帮助强制执行多项式的特定评估（这减少了可能同时接近 $f$ 并满足条件码字的数量）或表明多项式在某个集合上具有零点。

我们为什么要用这个？

给定一个评估点 $r=(r_1,\dots,r_m) \in F^m$，我们希望额外约束 $\hat{f}(r)=\sigma$。

所以如果我们选择

$\hat{w}(Z,X_1,\dots X_m)=Z\cdot eq((X_1,\dots,X_m),(r_1,\dots,r_m))$,

然后我们有

$\sigma=\sum{b\in{0,1}^m}\hat{w}(\hat{f}(b),b)=\sum{b\in{0,1}^m}\hat{f}(b)\cdot eq(b,r)=\hat{f}(r)$。

WHIR 协议

预备符号

• $\rho:=2^{m}n$ 是码的 速率，其中 $n=|L|$ 且 $m$ 是变量的数量。
• $L(i)={x^i:x\in L}$。 由于 $L$ 是平滑的，如果 $i$ 是 2 的幂，则 $|L(i)|=|L|/i$。
• $k>1$ 是 折叠参数。

基本思想

每个 WHIR 迭代都会将测试任务简化为

$f\in C=CRS[F,L,m,\hat{w},\sigma]$

测试任务

$f\in C'=CRS[F,L(2),m-k,\hat{w}',\sigma']$,

其中域的大小从 $n$ 减小到 $n/2$，变量的数量从 $m$ 减小到 $m-k$。

WHIR 协议有 $M=m/k$ 次 WHIR 迭代，将邻近度测试简化为

$C(0)=C$

邻近度测试

$C(M)=CRS[F,L(2^M),O(1),\hat{w}^{(M)},\sigma^{(M)}]$.

注意。 $O(1)$：它不依赖于 $m$ 或 $k$。

协议步骤

1. Sumcheck 轮

证明者和验证者将 sumcheck 协议的 $k$ 轮应用于声明

$\sum_{b\in{0,1}^m}\hat{w}(\hat{f}(b),b)=\sigma.$

该协议从

$\hat{w}(Z,X)=Z\cdot eq(X,r)$

其中 $\hat{f}(r)=\sigma$。

证明者通过在每一轮中固定第一个变量并对其余变量求和来发送单变量轮多项式 $h_1,\dots k$。

验证者采样 $\alpha_1,\dots,\alpha_k\in F$，并检查 $h_1(0)+h_1(1)=\sigma$ 和 $h_j(0)+hj(1)=h{j-1}(\alpha_{j-1})$。

这会将初始声明简化为声明

$\sum_{b\in{0,1}^{m-k}}\hat{w}'(\hat{f}(\alpha_1,\dots,\alphak,b{k+1},\dots b_m),(\alpha_1,\dots,\alphak,b{k+1},\dots b_m))=h_k(\alpha_k)$,

在更简单的符号中：

$\sum_{b\in{0,1}^{m-k}}\hat{w}'(\hat{f}(\alpha,b),\alpha,b)=h_k(\alpha_k)$,

2. 发送折叠函数

证明者发送一个函数 $g:L(2)\rightarrow F$。在诚实情况下，$\hat{g}(X)=\hat{f}(\alpha,X)$，则 $\hat{g}\in F_{\leq 1}[X1,\dots,X{m-k}]$，并且 $g$ 表示 $\hat{g}$ 在域上的评估

$g(x)=\hat{f}(\alpha^{2^0},\dots,\alpha^{2^k},x^{2^{k+1}},\dots,x^{2^m}): \forall x \in L(2)$.

3. 异地采样和评估

验证者采样并发送 $z_0\in F$。证明者评估并发送 $y_0=\hat{g}(z_0)$。

简化符号： 我们用 $\hat{g}(z_0)=\hat{g}(z_0^{2^0},z_0^{2^1},\dots,z_0^{2^{m-k-1}})$ 表示 $\hat{g}(z_0)$。

异地采样本质上迫使证明者在与 oracle 关联的多项式列表中选择一个可能的多项式。

4. 移位查询和组合随机性

验证者采样并发送 $z_1,\dots,z_t\in L(2^k)$，其中 $t$ 是此 WHIR 迭代中所需的数量，由安全参数 $\lambda$ 确定。 然后对于每个 $i\in{1,\dots t}$，验证者查询 $f$ 并获取

$y_i=Fold(f,\alpha)(z_i)$

然后，验证者采样并发送 $\gamma\in F$。

什么是折叠函数？

Reed-Solomon 码的折叠是降低码复杂性的一种方法，成本相对较小，并且是 Reed-Solomon 码的 IOPP 的核心。

给定 $f:L\rightarrow F$ 和 $a\in F$，我们定义 $Fold(f,a):L(2)\rightarrow F$ 如下：对于每个 $z\in L(2)$ Fold(f,a)(z)=f(x)+f(−x)2+a⋅f(x)−f(−x)2x,Fold(f,a)(z)=f(x)+f(−x)2+a⋅f(x)−f(−x)2x,

其中 $x$ 是 $L$ 中的点，使得 $z=x^2=(-x)^2$。

现在，给定一个向量 $\alpha=(\alpha_1,\dots,\alpha_k) \in F^k$，我们表示

Fold(f,α):L(2k)→FFold(f,α):L(2k)→F

到 $\alpha$ 中每个条目的递归折叠。 也就是说：

Fold(f,(αj,…,αk))=Fold(Fold(f,αj),(αj+1,…,αk))Fold(f,(αj,…,αk))=Fold(Fold(f,αj),(αj+1,…,αk))

例子： 如果 $k=3$，则

Fold(f,(α1,α2,α3))=Fold(Fold(f,α1),(α2,α3))Fold(f,(α1,α2,α3))=Fold(Fold(f,α1),(α2,α3))

假设 Fold(f,α1)=f1Fold(f,α1)=f1。 然后，

Fold(Fold(f,α1),(α2,α3))=Fold(f1,(α2,α3))=Fold(Fold(f1,α2),α3)Fold(Fold(f,α1),(α2,α3))=Fold(f1,(α2,α3))=Fold(Fold(f1,α2),α3)

假设 Fold(f1,α2)=f2Fold(f1,α2)=f2。 然后，

Fold(Fold(f1,α2),α3)=Fold(f2,α3)Fold(Fold(f1,α2),α3)=Fold(f2,α3)

所以总而言之，

Fold(f,(α1,α2,α3))=Fold(f2,α3)=Fold(Fold(Fold(f,α1),α2),α3)Fold(f,(α1,α2,α3))=Fold(f2,α3)=Fold(Fold(Fold(f,α1),α2),α3)

6. 递归声明

证明者和验证者都定义了新的权重多项式和目标

^w′(Z,X)=^w(Z,α,X)+Z⋅t∑i=0γi+1⋅eq(zi,X)w^′(Z,X)=w^(Z,α,X)+Z⋅∑i=0tγi+1⋅eq(zi,X)

σ′=^h(αk)+t∑i=0γi+1⋅yiσ′=h^(αk)+∑i=0tγi+1⋅yi

并在以下声明中递归：

g∈CRS[F,L(2),m−k,^w′,σ′].g∈CRS[F,L(2),m−k,w^′,σ′].

为什么是这个权重和这个目标？

我们想看看这个迭代如何将声明

f∈C=CRS[F,L,m,^w,σ]f∈C=CRS[F,L,m,w^,σ] 替换为声明 g∈C′=CRS[F,L(2),m−k,^w′,σ′].g∈CRS[F,L(2),m−k,w^′,σ′].

首先，请注意 ^w∈F[Z,X1,…,Xm]w^∈F[Z,X1,…,Xm] 和 ^w′∈F[Z,X1,…,Xm−k]w^′∈F[Z,X1,…,Xm−k]。

如果证明者是诚实的并且 $f \in C$，那么为什么 $g \in C'$？

一方面，$g \in RS[F, L(2), m-k]$，因为 $\hat{g} \in F_{\leq 1}[X1, \dots, X{m-k}]$ 使得 $g(x) = \hat{f}(\alpha_1^2, \dots, \alphak^2, x{2k+1}, \dots, x_{2m})$。 另一方面，我们需要检查求和约束：我们想要证明

∑b∈{0,1}m−k^w′(^g(b),b)=σ′.∑b∈{0,1}m−kw^′(g^(b),b)=σ′.

让我们看看：

∑b∈{0,1}m−k^w′(^g(b),b)=∑b∈{0,1}m−k^w(^f(α,b),(α,b))+^f(α,b)t∑i=0γi+1⋅eq(zi,b)∑b∈{0,1}m−kw^′(g^(b),b)=∑b∈{0,1}m−kw^(f^(α,b),(α,b))+f^(α,b)∑i=0tγi+1⋅eq(zi,b)

σ′=^h(αk)+t∑i=0γi+1⋅yiσ′=h^(αk)+∑i=0tγi+1⋅yi

由于

^h(αk)=∑b∈{0,1}m−k^w(^f(α,b),(α,b)),h^(αk)=∑b∈{0,1}m−kw^(f^(α,b),(α,b)),

我们只需要检查

t∑i=0γi+1⋅yi=∑b∈{0,1}m−k^f(α,b)⋅t∑i=0γi+1⋅eq(zi,b),∑i=0tγi+1⋅yi=∑b∈{0,1}m−kf^(α,b)⋅∑i=0tγi+1⋅eq(zi,b),

其中

t∑i=0γi+1⋅yi=γ⋅^f(α,z0)+t∑i=1γi+1⋅Fold(f,α)(zi).∑i=0tγi+1⋅yi=γ⋅f^(α,z0)+∑i=1tγi+1⋅Fold(f,α)(zi).

下一步

在接下来的文章中，我们将介绍与 WHIR 安全性相关的几个方面，它作为一种证明后端，用于高效的后量子安全签名聚合，以及可能减少证明大小和证明时间的改进。

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