---
type: slide
slideOptions:
theme: simple
---

# Groth16的延展攻击

Kurt Pan

---

## Groth16 方案回顾

---


---


---


---

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

---

$$
AB=\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)
$$

---

第一个攻击

$$
\begin{gathered}
A^{\prime}=A \\
B^{\prime}=B+\delta \\
C^{\prime}=C+A
\end{gathered}
$$

---

带入验证方程
$$
\begin{aligned}
\left[A^{\prime}\right]_{1} \cdot\left[B^{\prime}\right]_{2}
&=[A]_{1} \cdot[B+\delta]_{2} \\
&=[A]_{1} \cdot[B]_{2}+[A]_{1} \cdot[\delta]_{2} \\
&=\ldots+[C]_{1} \cdot[\delta]_{2}+[A]_{1} \cdot[\delta]_{2} \\
&=\ldots+[C+A]_{1} \cdot[\delta]_{2} \\
&=\ldots+\left[C^{\prime}\right]_{1} \cdot[\delta]_{2}
\end{aligned}
$$

---

第一个攻击扩展版

$\eta \gets Z^*_p$
$$
\begin{gathered}
A^{\prime}=A \\
B^{\prime}=B+\eta \delta \\
C^{\prime}=C+\eta A
\end{gathered}
$$

原理和上述一致

---

第二个攻击
$x\gets \mathbb{Z}_p^*$
$$
\begin{gathered}
A^{\prime}=x A \\
B^{\prime}=x^{-1} B \\
C^{\prime}=C
\end{gathered}
$$
原理很简单，验证方程中$A*B$会消掉$x$

---

- 前两个攻击都是对相同公开输入进行延展攻击伪造证明的方法，
- 如果公开输入和私有输入之间出现线性相关时，可以进行如下更改公开输入到特定值（如攻击者的以太坊地址）的第三个攻击

---

使用的电路

pragma circom 2.0.6;

include "../node_modules/circomlib/circuits/poseidon.circom";

template Circuit() {
    signal input a;
    signal input b;
    signal input c;

    a === b;
    component p = Poseidon(1);
    p.inputs[0] <== c;
    p.out === 17744324452969507964952966931655538206777558023197549666337974697819074895989;
}

component main {public [a]} = Circuit();

>注意a为公开输入，b为私有输入。

---

论文[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$”不满足，则可以构造更改公开输入的延展攻击。
- 上述电路中`a===b`，线性相关，不满足该条件，可以利用该点进行延展攻击伪造证明。

---

- 对于通用的出现线性相关情况下延展攻击原理详见文章 https://hackmd.io/@Kurt-Pan/ryRK70v05
- 具体到本题电路中，公开输入`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$

---

## 防御

---

- signed proofs
- nullifiers
- usage of an ethereum address as a public input to the program
- usage of non-malleable schemes such as GM17
- 引入“伪平方约束”：对于一个不涉及任何约束的公开输入$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$会使验证方程不通过。本质是确保公开输入线性无关从而满足论文中非延展的条件。

---

thx