Funbenius 的幂次

引言

在这篇文章中，我们只想介绍一个有趣的 bug：有趣是因为数学本身很有趣，也因为它以“恰到好处”的方式被破坏。这个 bug 是 Inferno 中的 issue #44，Inferno 是 Limbo（一种 MPC-in-the-head 零知识论证）的 Rust 实现，而 Limbo 是对 KKW 方案 的改进。这个实现中的 bug 只有一个字符长，通常很常见，通常不会导致游戏结束，但在二元扩域上，一切都会以恰到好处的方式崩溃……

Limbo

Limbo 证明算术电路 $C$ 在任意域 $F_p$ 上的可满足性，通常应用于小域，例如在 Inferno 中，$F_p = F_2$。因此每条线都承载一个二进制值，加法是 XOR，乘法是按位 AND。其优势在于，你不必为你想要操作的每个比特支付“嵌入到大域以获得可靠性”的开销，这意味着在具体计算和通信成本上非常出色。Limbo 的“缺点”是经典 MPC-in-the-head 的缺点：通信/验证者成本是线性的。

Limbo 的工作原理是，证明者通过 $n$ 个虚拟 MPC 方之间的加法秘密共享提交 $C$ 在 $w$ 上评估的每条线值，这些 MPC 方在“证明者头脑中”运行；验证者稍后打开部分方的视图并检查一致性。

线性门（加法、标量乘法）在共享上局部作用，因此各方无需额外承诺即可免费评估它们。乘法门是困难的部分：$x_\ell$ 和 $y_\ell$ 的共享无法局部组合成 $x_\ell \cdot y_\ell$ 的共享。因此，对于每个乘法门 $\ell \in [m]$，证明者额外提交声称的输出 $z_\ell$ 的共享，并且验证者必须检查证明者没有说谎：

$$ \forall \ell \in [m].\ z_\ell = x_\ell \cdot y_\ell $$

其中 $x_\ell, y_\ell$ 是第 $\ell$ 个乘法门的输入线（它们本身是早期线的线性组合，因此已经共享），$z_\ell$ 是新提交的声明。每个乘法门贡献一个门误差：

$$ e_\ell := x_\ell y_\ell - z_\ell \in F_p $$

证明者诚实当且仅当每个 $e_\ell = 0$。逐个检查每个门代价很高，因此 Limbo 将所有的 $m$ 个门误差合并为一次检查。误差存在于 $F_p$ 中，但验证者从大扩域 $F_q \supseteq F_p$ 中选择一个挑战 $r \in F_q$，在 Inferno 中我们有 $F_q = F_{2^{64}}$，并要求证明者说服他：

$$ f(r) := \sum_{\ell=1}^m e_\ell \cdot r^\ell = 0 $$

误差 $e_\ell$ 成为多项式 $f(X) \in F_p[X]$ 的系数，$r$ 是 $F_q$ 中均匀随机的评估点。如果证明者诚实，$f$ 是零多项式，$f(r) = 0$ 平凡成立。如果哪怕只有一个 $e_\ell$ 非零，$f$ 是次数最多为 $m$ 的非零多项式，因此根据 Schwartz-Zippel 引理，它在 $r$ 处为零的概率最多为 $m / |F_q|$。这就是 Limbo, §4.1 中的 $\Pi$-MultCheck，其余协议建立在其之上。

注意： Inferno 中的域 $F_{2^{64}}$ 大小不足以满足计算可靠性，只需在使用 Fiat-Shamir 编译协议时并行重复多次检查即可解决。

代码

以下是 round.rs 中实现 $f(r)$ 评估的相关片段：

pub(crate) fn round1<S: LinearSharing<F, N>, F: FiniteField, const N: usize>(
    round0: Round<S::SelfWithPrimeField>,
    mults: &[S::SelfWithPrimeField],
    challenge: F,
) -> Round<S> {
    let mut sum = S::default();
    let mut xs = vec![S::default(); round0.xs.len()];
    let mut ys = vec![S::default(); round0.ys.len()];
    let mut r = challenge;
    for (i, ((x, y), z)) in round0
        .xs
        .iter()
        .zip(round0.ys.iter())
        .zip(mults.iter())
        .enumerate()
    {
        sum += S::multiply_by_superfield(z, r);
        xs[i] = S::multiply_by_superfield(x, r);
        ys[i] = S::lift_into_superfield(y);
        r *= r;
    }
    Round { xs, ys, z: Some(sum) }
}

意图是让 $r$ 取值 $r, r^2, r^3, \dots, r^m$，目的是计算：

$$ \begin{aligned} \text{sum} &= \sum_i r^i \cdot z_i \ xs_i &= r^i \cdot x_i \ ys_i &= y_i \end{aligned} $$

三元组 $(xs, ys, \text{sum})$ 是协议其余部分验证的内积实例：下游验证者检查 $\langle xs, ys \rangle = \text{sum}$。使用预期值时，当证明者诚实 ($z_i = x_i y_i$) 时，完备性自动成立。可靠性简化为在 $r$ 处评估 $f$：

$$ \langle xs, ys \rangle - \text{sum} = \langle \vec{r} \circ \vec{x}, \vec{y} \rangle - \text{sum} = \sum_i r^i \cdot x_i y_i - \sum_i r^i \cdot z_i = \sum_i r^i \cdot (x_i y_i - z_i) = \sum_i r^i \cdot e_i = f(r) $$

因此检查 $\langle xs, ys \rangle = \text{sum}$ 正好是检查 $f(r) = 0$。

Bug

问题在于，代码使用了 r *= r 而不是 r *= challenge，也许你已经注意到了。这是重复平方，不是连续幂，因此 $r$ 实际取值为：$r, r^2, r^4, r^8, \dots, r^{2^{m-1}}$，因此验证者最终执行的检查是：

$$ f(r) := \sum_{i=0}^{m-1} e_i \cdot r^{2^i} = 0 $$

其中 $e_i = x_i y_i - z_i$ 是乘法门 $i$ 处的误差。

注意 $f(r)$ 的次数不是 $m-1$，而是 $2^{m-1}$，这简直大得惊人！因此通常基于 Schwartz–Zippel 引理的可靠性论证：

$$ f(X) \neq 0 \implies \Pr[f(r) = 0] \le \frac{\deg(f)}{|F_q|} $$

当 $m \ge 64$ 时毫无意义，此时右边大于 $1$（对于 Inferno，因为 $F_q = F_{2^{64}}$）。好吧，理论上被破坏了，但这只是证明上的漏洞吗？事实证明不是，要理解原因，我们需要看看 Frobenius 自同态……

Frobenius 自同态

$F_{2^k}$ 上的 Frobenius 自同态是映射：

$$ \phi: F_{2^k} \to F_{2^k}, \quad \phi(x) = x^2 $$

它的 $i$ 次幂是重复平方，即升高到 $2^i$ 次幂：

$$ \phi^i(x) = \underbrace{\phi(\phi(\dots(x)\dots))}_{i \text{ 次}} = x^{2^i} $$

线性性质

注意 $\phi$ 是 $F_2$-线性的，因为“新生之梦”：

$$ \phi(a+b) = (a+b)^2 = a^2 + 2ab + b^2 = a^2 + b^2 = \phi(a) + \phi(b) $$

因为在特征 $2$ 中 $2 = 0$，并且与 $F_2$ 中标量的乘法也成立：

$$ \phi(0 \cdot a) = 0 = 0 \cdot \phi(a), \quad \phi(1 \cdot a) = \phi(a) = 1 \cdot \phi(a) $$

$F_2$ 线性映射的复合也是 $F_2$-线性的，因此每个幂 $\phi^i$ 也是线性的。此外，线性映射的任意线性组合当然也是线性的，因此：

$$ X \mapsto \sum_i e_i \cdot \phi^i(X) = \sum_i \phi^i(e_i \cdot X) = \sum e_i \cdot X^{2^i} $$

其中 $e \in F_2$ 也是一个从 $F_q$ 到 $F_q$ 的线性映射。

周期性

最后，在 $F_{2^k}$ 上我们有 $\phi^k = \text{id}$，因为对于每个 $x \in F_{2^k}$：

$$ x^{2^k - 1} = 1 \implies x^{2^k} = x \implies \phi^k(x) = x $$

因此：

$$ \phi^i = \phi^{i \bmod k} $$

作为函数 $F_{2^k} \to F_{2^k}$，只有 $k$ 个不同的幂存在。

利用

这一切都意味着灾难……

明显的问题是 $f(r)$ 是这些 Frobenius 幂的组合，因此例如如果

$$ f(r) = \sum_{i=0}^{64} e_i \cdot r^{2^i} $$

那么 $\vec{e} = (0,0,\dots,0)$ 和 $\vec{e} = (1,0,0,\dots,-1)$ 对每个 $r$ 都有相同的评估，因为：$x = \phi^{64}(x)$ 所以 $r - \phi^{64}(r) = 0$ 对每个 $r$ 成立。注意在 $F_2$ 中 $-1 = 1$，因此最简单的攻击就是“翻转”两个乘法的结果：选择任意两个索引 $a \neq b$ 但满足 $a \equiv b \pmod{64}$ 的乘法门，并将两个误差都设为 $1$：

$$ f(r) = \phi^a(r) + \phi^b(r) = \phi^{a \bmod 64}(r) + \phi^{b \bmod 64}(r) = 0 $$

这只需要一个包含超过 $64$ 个乘法门的电路，这几乎是肯定的——没有多少有用的电路有少于 $65$ 次乘法……

然而，好奇的读者可能会想，是否可以用少于 $65$ 个门来利用这个漏洞。答案是肯定的，部分可行。如果我们将 $r \in F_{2^{64}}$ 视为 $64$ 维 $F_2$ 向量空间中的一个向量，那么当以下条件成立时，攻击有效：

$$ r \in \ker(f_e) $$

其中 $f_e$ 是线性映射：

$$ r \mapsto \sum_i e_i \cdot \phi^i(r) $$

对于这个误差向量，接受概率为：

$$ \frac{|\ker(f_e)|}{|F_{2^{64}}|} = 2^{\dim_{F_2}(\ker(f_e)) - 64} $$

对于攻击，我们只需展示一个具有大核的误差向量。令：

$$ N = \phi + \text{id} $$

这是映射 $N(r) = r^2 + r$。由于在 $F_{2^{64}}$ 上 $\phi^{64} = \text{id}$，我们有：

$$ N^{64} = (\phi + \text{id})^{64} = \phi^{64} + \text{id} = 0 $$

这里我们使用了特征 $2$ 中交换映射的新生之梦。此外：

$$ \ker(N) = { r \in F_{2^{64}} : r^2 + r = 0 } = F_2 $$

因此 $\dim_{F_2} \ker(N) = 1$。现在考虑依次应用 $N$ 得到的核：

$$ {0} = \ker(N^0) \subseteq \ker(N) \subseteq \ker(N^2) \subseteq \cdots \subseteq \ker(N^{64}) = F_{2^{64}} $$

每一步最多可以增加一个维度。实际上，模 $\ker(N^j)$，$r \in \ker(N^{j+1})$ 中的唯一新信息是 $N^j r$，这位于一维空间 $\ker(N)$ 中。但链从维度 $0$ 开始，以维度 $64$ 结束，因此每一步正好在核中增加一个维度：

$$ \dim_{F_2} \ker(N^t) = \dim_{F_2} \ker(N^{t-1}) + 1 = t $$

现在选择门误差，使得被破坏的检查恰好是 $N^t$。展开 $N^t$ 得到：

$$ N^t = (\phi + \text{id})^t = \sum_{i=0}^t \binom{t}{i} \phi^i = \sum_{i=0}^t e_i \phi^i, \quad e_i = \binom{t}{i} \bmod 2 $$

将门 $i$ 处的误差设为这个系数 $e_i$。那么：

$$ f_e(r) = \sum_{i=0}^t e_i \phi^i(r) = N^t(r) $$

因此 $\dim_{F_2} \ker(f_e) = t$，验证者接受这个误差向量的概率为 $2^{t-64}$。对于 $t=32$，新生之梦给出 $N^{32} = \phi^{32} + \text{id}$，因此我们只需要门 $0$ 和 $32$ 处的误差。这是一个包含 $33$ 个乘法门的电路。原本的检查接受概率约为 $33/2^{64}$，而被破坏的检查接受概率为 $2^{-32}$。

分享本文

分享到 X 分享到 LinkedIn 通过邮件分享

zkSecurity 为密码学系统（包括零知识证明、MPC、FHE、共识协议等）提供审计、研究和开发服务。

了解更多 →

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