# 关于Groth16延展攻击

:::info
作者：Kurt Pan
:::
> 感谢Trapdoor Tech李星老师和安比实验室Even的帮助 :wink:

## 背景
[Geometry](https://geometryresearch.xyz/about)是[Kobi Gurkan](https://twitter.com/kobigurk) 等人所在的一个新成立不久的研究组织，Kobi本人曾给[ZK HACK](https://zkhack.dev/events/) 出过9道puzzles，这次又合作给出了这个关于Groth16延展攻击的新puzzle：[ZK Hack x Geometry Puzzle I](https://geometryresearch.xyz/notebook/zkhack-groth-challenge)
> 该puzzle的主要内容在这个github仓库中：[zkhack-groth-puzzle](https://github.com/geometryresearch/zkhack-groth-puzzle)，
> 英文题解参见[这篇](https://geometry.xyz/notebook/groth16-malleability)文章。
> 背景信息和中文题解，强烈推荐参考李星老师的[文章](https://mp.weixin.qq.com/s/8jr5AHVUB-nTPy54OsgspA)。

**SNARK领域中的延展攻击**，是指给定敌手一个合法证明，敌手在不知道见证的条件下自己生成新的（对相同或不同公开输入的）合法证明。

对于相同公开输入的伪造证明的方法请参见这篇文章[How to Generate a Groth16 Proof for Forgery](https://medium.com/ppio/how-to-generate-a-groth16-proof-for-forgery-9f857b0dcafd)，但是其中描述的两个攻击对于需要更改公开输入到特定值（如本题为攻击者的以太坊地址）时并不适用。

## 理论

论文[BKSV20](https://eprint.iacr.org/2020/811) 中的如下定理给出了Groth16抵抗延展攻击的一个条件：

> 定理：如果 $\left\{u_{i}(x)\right\}_{i=0}^{l}$ 是线性独立的，且$\operatorname{Span}\left\{u_{i}(x)\right\}_{i=0}^{l} \cap$ Span $\left\{u_{i}(x)\right\}_{i=l+1}^{m}=\emptyset$。
> 则Groth16在代数群模型中，离散对数假设下，可达到**弱白盒模拟可抽取性质**。

如果条件“$\left\{u_{i}(x)\right\}_{i=0}^{l}$ 是线性独立的，且$\operatorname{Span}\left\{u_{i}(x)\right\}_{i=0}^{l} \cap$ Span $\left\{u_{i}(x)\right\}_{i=l+1}^{m}=\emptyset$”不满足，则可以构造更改公开输入的延展攻击。本文下文即描述在不满足该条件时如何利用该点进行延展攻击伪造证明。

固定某个$k \in[l+1 . . m]$，$j \in[0 . . l]$ （分别是见证和公开输入的下标），使得多项式$u_{k}(x), v_{k}(x) ,w_{k}(x)$ 分别和$u_{j}(x), v_{j}(x), w_{j}(x)$ 线性相关。记：
$$
\begin{aligned}
&W_{k}(x)=\beta * u_{k}(x)+\alpha * v_{k}(x)+w_{k}(x) \\
&P I_{j}(x)=\beta * u_{j}(x)+\alpha * v_{j}(x)+w_{j}(x)
\end{aligned}
$$
于是$W_{k}(x)$和$P I_{j}(x)$也线性相关，即存在某个线性因子$lf$使得：
$$
lf \cdot W_{k}(x)=P I_{j}(x)
$$

---
Groth16的验证方程如下：
$$
[A]_{1} \cdot[B]_{2}=[\alpha]_{1} \cdot[\beta]_{2}+\sum_{i=0}^{l} z_{i}\left[\frac{\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)}{\gamma}\right]_{1} \cdot[\gamma]_{2}+[C]_{1} \cdot[\delta]_{2}
$$
把$P I_{j}(x)$项分离出来后如下：
$$
[A]_{1} \cdot[B]_{2}=[\alpha]_{1} \cdot[\beta]_{2}+\sum_{\substack{i=0 \\ i \neq j}}^{l} z_{i}\left[\frac{\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)}{\gamma}\right]_{1} \cdot[\gamma]_{2}+z_{j}\left[\frac{P I_{j}(x)}{\gamma}\right]_{1} \cdot[\gamma]_{2}+[C]_{1} \cdot[\delta]_{2}
$$
如果只考虑配对操作后$G_T$群中的指数，验证方程如下：
$$
\text { Result }=\alpha \beta+\sum_{i=0}^{l} z_{i} \left(\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)\right)+C_{\text {paired }}(x)
$$
注意这种形式下未知的分母$\gamma$已经被消去了。

---

如果更改公开输入值$z_j$为$z_j^\prime$，结果变为：
$$
\text { Result }^{\prime}=\operatorname{Result}+z_{j}^{\prime} * P I_{j}(x)-z_{j} * P I_{j}(x) = \text{Result}+\left(z_{j}^{\prime}-z_{j}\right) * P I_{j}(x)
$$

和原始$\text{Result}$差了一项$\left(z_{j}^{\prime}-z_{j}\right) * P I_{j}(x)$。
通过修改方程右式中的$C$如下，则可以在方程右边平衡左边原始结果多出来的$\left(z_{j}^{\prime}-z_{j}\right) * P I_{j}(x)$：

$$
C^{\prime}=C+lf *\left(z_{j}-z_{j}^{\prime}\right) *\left[\frac{W_{k}(x)}{\delta}\right]_{1}
$$

注意上式使用了线性相关关系：
$$
lf \cdot W_{k}(x)=P I_{j}(x)
$$

其中
$$
\left[\frac{W_{k}(x)}{\delta}\right]_{1}=\left[\frac{\beta u_{k}(x)+\alpha v_{k}(x)+w_{k}(x)}{\delta} \right]_1
$$
在公开参数中已知可用。
而公开参数里存储的是
$$
\left[\frac{PI_{j}(x)}{\gamma}\right]_{1}=\left[\frac{\beta u_{j}(x)+\alpha v_{j}(x)+w_{j}(x)}{\gamma} \right]_1
$$
不能被直接使用。

于是有：
$$
\begin{aligned}
&{[A]_{1} \cdot[B]_{2}=[\alpha]_{1} \cdot[\beta]_{2}+\sum_{\substack{i=0 \\
i \neq j}}^{l} z_{i}\left[\frac{\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)}{\gamma}\right]_{1} \cdot[\gamma]_{2}+z_{j}^{\prime}\left[\frac{P I_{j}(x)}{\gamma}\right]_{1} \cdot[\gamma]_{2}+C^{\prime}(x) \cdot[\delta]_{2}} \\
&=[\alpha]_{1} \cdot[\beta]_{2}+\sum_{\substack{i=0 \\
i \neq j}}^{l} z_{i}\left[\frac{\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)}{\gamma}\right]_{1} \cdot[\gamma]_{2}+z_{j}^{\prime}\left[\frac{P I_{j}(x)}{\gamma}\right]_{1} \cdot[\gamma]_{2}+C(x) \cdot[\delta]_{2}+l *\left(z_{j}-z_{j}^{\prime}\right) *\left[\frac{W_{k}(x)}{\delta}\right]_{1} \cdot[\delta]_{2}
\end{aligned}
$$

依然只考虑配对操作后$G_T$群中的指数，上式等于：
$$
\begin{gathered}
=\alpha * \beta+\sum_{\substack{i=0 \\
i \neq j}}^{l} z_{i} *\left(\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)\right)+z_{j}^{\prime} * P I_{j}(x)+C_{\text {paired }}(x)+l *\left(z_{j}-z_{j}^{\prime}\right) * W_{k}(x) \\
=\alpha * \beta+\sum_{\substack{i=0 \\
i \neq j}}^{l} z_{i} *\left(\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)\right)+z_{j}^{\prime} * P I_{j}(x)+C_{p a i r e d}(x)+\left(z_{j}-z_{j}^{\prime}\right) * P I_{j}(x) \\
=\alpha * \beta+\sum_{\substack{i=0 \\
i \neq j}}^{l} z_{i} *\left(\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)\right)+z_{j}^{\prime} * P I_{j}(x)+C_{\text {paired }}(x)+z_{j} * P I_{j}(x)-z_{j}^{\prime} * P I_{j}(x) \\
=\alpha * \beta+\sum_{\substack{i=0 \\
i \neq j}}^{l} z_{i} *\left(\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)\right)+C_{p a i r e d}(x)+z_{j} * P I_{j}(x) \\
=\alpha * \beta+\sum_{i=0}^{l} z_{i} *\left(\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)\right)+C_{p a i r e d}(x)
\end{gathered}
$$
注意到最后一行正是原始验证方程的右式，这意味着敌手改变了公共输入，并对新的语句伪造出了合法的证明，即成功进行了延展攻击。

## 实操
具体到本题电路中，公开输入`a`和见证`b`的相关约束为：$0 = b - a$ , 公开输入只有$z_0=1,z_1=a$，$l=1$。

$u_1(x)=v_1(x) = u_2(x)=v_2(x) = 0$, $w_1(x)= -w_2(x)$

$$
C^\prime=C+ lf * (z_1^\prime-z_1) * \left[\frac{\beta u_{2}(x)+\alpha v_{2}(x)+w_{2}(x)}{\delta}\right]_{1}
$$

其中$z_1^\prime$ = `new_a` ,$z_1$ = `a`, $lf=-1$

const buildMalleabeC = async (stringified_c, matching_base_index, matching_pub_input, new_public_input, lf) => {
    const c = unstringifyBigInts(stringified_c)

    const {fd: fdZKey, sections: sectionsZKey} = await binFileUtils.readBinFile(finalZkeyPath, "zkey", 2, 1<<25, 1<<23)
    const buffBasesC = await binFileUtils.readSection(fdZKey, sectionsZKey, 8)
    fdZKey.close()

    const curve = await buildBn128();
    const Fr = curve.Fr;
    const G1 = curve.G1;

    const new_pi = new Uint8Array(Fr.n8);
    Scalar.toRprLE(new_pi, 0, new_public_input, Fr.n8);

    const matching_pub = new Uint8Array(Fr.n8);
    Scalar.toRprLE(matching_pub, 0, matching_pub_input, Fr.n8);

    const sGIn = curve.G1.F.n8*2
    const matching_base = buffBasesC.slice(matching_base_index*sGIn, matching_base_index*sGIn + sGIn)
    
    const linear_factor = Fr.e(lf.toString(10))

    const delta_lf = Fr.mul(linear_factor, Fr.sub(matching_pub, new_pi));

    const p = await curve.G1.timesScalar(matching_base, delta_lf);
    const affine_c = G1.fromObject(c);

    const malleable_c = G1.toAffine(G1.add(affine_c, p))
    return stringifyBigInts(G1.toObject(malleable_c))
}

const linearDep = BigInt(-1)
const matchingBase = 0;
const malleable_c = await buildMalleabeC(proof.pi_c, matchingBase, BigInt(a), new_a, linearDep)
proof.pi_c = malleable_c;

## 防御
- 引入“伪平方约束”：对于一个不涉及任何约束的公开输入$z_i$，添加一个简单的约束作为防伪造“护身符”，比如$\text{sz}_i = z_i * z_i$。
- 引入“魔法约束”$z_{i} * 0=0$：$u_{i}(x), v_{i}(x), w_{i}(x)$ 并非全部是零多项式，从而$\left[\frac{\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)}{\gamma}\right]_{1}$非零，从而变$z_i$会使验证方程不通过。本质是确保公开输入线性无关从而满足论文中非延展的条件。