这篇文章上次修改于 550 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

zero-knowledge protocol：是一组数学规则，根据这些规则，在给定 instance 后，prover 可以向 verifier 证明自己知道该 instance 的 witness 而不揭露 witness 任何信息。

设 $R$ 是域 $F_{r}$ 上的 R1CS， $R$ 的 Groth_16 参数如下：

$G r o t h_16 - P a r a m (R) = (r, G_{1}, G_{2}, e (\cdot, \cdot), g_{1}, g_{2})$

$G_{1}, G_{2}$ 是有限循环群，阶为 $r$ ， $G_{1}$ 的生成器是 $g_{1}$ ， $G_{2}$ 的生成器是 $g_{2}$ ， $e : G_{1} \times G_{2} \to G_{T}$ 是对于 $G_{T}$ 的有效计算的、非退化的、双线性配对。这些参数通常需要预先协商。

Groth_16 协议如下：

Setup 阶段 $(C R S, S T) \leftarrow S E T U P (R)$ ：SETUP 算法以 R1CS $R$ 作为输入，算出公共引用字符串 CRS（Common Reference String）和模拟后门 ST（simulation trapdoor）
Prover 阶段 $π \leftarrow P R O V E (R, C R S, I, W)$ ：给定 $R$ 的 constructive proof $(I; W)$ ，算法 PROVE 将 $R$ 、 $C R S$ 和 $(I; W)$ 作为输入，算出 zk-SNARK $π$
Verify 阶段 ${a c c e p t, r e j e c t} \leftarrow V F Y (R, C R S, I, π)$ ：算法将 $R$ 、 $C R S$ 、instance $I$ 和 zk-SNARK $π$ 作为输入，输出 reject 或 accept
$π \leftarrow S I M (R, τ, C R S, I)$ ：算法 SIM 将 $R$ 、后门 ST 的参数 $τ$ 、 $C R S$ 、instance $I$ 作为输入，输出 zk-SNARK $π$

3-因子分解问题

QAP 定义于 $F_{13}$ ，所以必须选择阶为 13 的配对群 $G_{1}, G_{2}$

BLS6_6 有两个子群 $G_{1} [13], G_{2} [13]$ ，阶均为 13。相关的 Weil 配对 $e (\cdot, \cdot)$ 是有效计算的、双线性、非退化的。所以可以选择这些群和 Weil 配对， $G_{1} [13], G_{2} [13]$ 的生成器分别为 $g_{1} = (13, 15), g_{2} = (7 v^{2}, 16 v^{3})$ ，得到如下参数：

$G r o t h - P a r a m (R_{3. f a c_{z} k}) = (13, G_{1} [13], G_{2} [13], e (\cdot, \cdot), (13, 15), (7 v^{2}, 16 v^{3})))$

参数的选择并非唯一，每对具有有效可计算、非退化双线性配对的 13 阶有限循环群都可以作为 Groth_16 参数集。

1 启动阶段

该阶段对于每个 R1CS 和关联的 QAP 只需执行一次，输出的 CRS 会被 prover 和 verifier 用于生成和验证 zk-SNARK。此外，还会生成一个模拟后门，可被用来模拟 proof。

设 $L$ 是 R1CS $R$ 定义的语言，该语言的一个 instance $< I_{1}, . . ., I_{n} >$ 的一个 constructive proof 是 witness $< W_{1}, . . ., W_{m} >$ ， $R$ 的 $Q A P (R) = {T \in F [x], {A_{j}, B_{j}, C_{j} \in F [x]}_{h = 0}^{n + m}}$ ， ${G_{1}, G_{2}, e (\cdot, \cdot), g_{1}, g_{2}, F_{r})}$ 是 Groth_16 参数。

从标量域 $F_{r}$ 中随机选取 5 个可逆的元素 $α, β, γ, δ, τ$ ，得到模拟后门（simulation trapdoor） ST：

$S T = (α, β, γ, δ, τ)$

这 5 个随机数和 2 个生成器 $g_{1}, g_{2}$ 以及 QAP 一起生成语言 $L$ 的公共引用字符串（Common Reference String） $C R S_{Q A P} = (C R S_{G_{1}}, C R S_{G_{2}})$ ：

CRS 取决于后门，所以不是唯一的。CRS 大小与 instance 和 witness 的大小是线性相关的。

模拟后门 $S T = (α, β, γ, δ, τ)$ 中的 $τ$ 为秘密评估点（secret evaluation point）。因为 $F_{r}$ 是有限循环群 $G_{1}, G_{2}$ 的标量域，所以 CRS 的一个关键特征是提供了一种在生成器 $g_{1}, g_{2}$ 的指数中计算度为 $d e g (P) < d e p (T)$ 的多项式 $P \in F_{r} [x]$ ，而不需要知道 $τ$ 。例如多项式 $P (x) = g_{1}^{a_{0} \cdot x^{0} + a_{1} \cdot x^{1} + . . . a_{k} \cdot x^{k}}$ ，将 $τ$ 代入后，得到：

只需要知道 $τ$ 的幂（powers of tau） $g_{1 o r 2}^{τ^{j}}$ 就可以算出 $g_{1}^{P (τ)}$ ，而 $g_{1 o r 2}^{τ^{j}}$ 是 CRS 的一部分。同理可算出 $g_{2}^{P (τ)}$ 。

模拟后门被称为 toxic waste，因为可以生成欺诈 proof。CRS 也被称为 prover and verifier key pair。

模拟后门必须被丢弃，为此一般会引入多方计算，每方都持有后门的一部分，只要有一方不同意，后门就无法恢复。

2 证明阶段

给定 R1CS $R$ 和 instance $I =< I_{1}, . . ., I_{n} >$ ，该阶段的目标是说服 verifier，prover 知道 $I$ 的 witness $W$ ，而不透露 $W$ 的任何知识。 $(I; W)$ 是语言 $L_{R}$ 的一个单词。

为了构建一个 constructive proof，prover 需要计算 $W =< W_{1}, . . ., W_{m} >$ 使得 $(< I_{1}, . . ., I_{n} >; < W_{1}, . . ., W_{m} >)$ 是 R1CS $R$ 的一个解。

生成 witness 后，prover 通过 QAP 计算多项式 $P_{(I; w)} = (A_{0} + \sum_{j}^{n} I_{j} A_{j} + \sum_{j}^{m} W_{j} A_{n + j}) (B_{0} + \sum_{j}^{n} I_{j} B_{j} + \sum_{j}^{m} W_{j} B_{n + j}) - (C_{0} + \sum_{j}^{n} I_{j} C_{j} + \sum_{j}^{m} W_{j} C_{n + j})$ ，然后使用 QAP 的目标多项式 $T$ 整除 $P_{(I; W)}$ ，得到 $H := P_{(I; W)} / T$ 。

然后在生成器 $g_{1}$ 的指数中计算秘密评估点 $τ$ 处的多项式 $(H \cdot T) / δ$ 。设 $H (x) = P / T$ ：

$H (x) = H_{0} \cdot x^{0} + H_{1} \cdot x^{1} + . . . + H_{k} \cdot x^{k}$

为了在 $g_{1}$ 的指数中计算 $τ$ 处的 $(H \cdot T) / δ$ ，prover 使用 CRS 计算如下：

$g_{1}^{\frac{H (τ) \cdot T (τ)}{δ}} = (g_{1}^{\frac{τ^{0} \cdot T (τ)}{δ}})^{H_{0}} \cdot (g_{1}^{\frac{τ^{1} \cdot T (τ)}{δ}})^{H_{1}} . . . (g_{1}^{\frac{τ^{k} \cdot T (τ)}{δ}})^{H_{k}}$

然后随机选择两个域元素 $r, t \in F_{r}$ ，使用 $I_{1}, . . . I_{n}$ 和 $W_{1}, . . ., W_{n}$ 计算如下曲线点：

其中，群元素 $g_{1}^{A_{j} (τ)}, g_{1}^{B_{j} (τ)}, g_{2}^{B_{j} (τ)}$ 可从 CRS 和 QAP 获得，这些点只需要计算一次，且可被公开，可被重用，因为对于所有的 instance 和 witness 都是一致的。

便可得到一个合法的 Groth_16 的 zk-SNARK 参数 π：

$π = (g_{1}^{A}, g_{1}^{C}, g_{2}^{B})$

由 3 个曲线点组成，两个来自群 $G_{1}$ ，一个来自群 $G_{2}$ 。这种安排是有目的的，因为 $G_{1}$ 是素数域上的椭圆曲线的 torsion 群， $G_{2}$ 是扩展域上的 full torsion 群的子群。因为 $G_{1}$ 比 $G_{2}$ 所需的存储空间和计算更少，所以这种设计是较优的。

witness 编码到了安全曲线的生成器的指数中，这样就不会被暴露给任何人。此外，随机域元素 $r, t$ 使得每个 proof 随机化，确保不会有两个 proof 对应于同一个 witness。

3 验证阶段

给定 R1CS $R$ 、instance $I =< I_{1}, . . ., I_{n} >$ 和 zk-SNARK $π$ ， $π$ 为有效 proof。如果后门已经不存在了，且 proof 通过来验证，那么 verifier 就可以确信存在一个 witness $W =< W_{1}, . . ., W_{m} >$ 使得 $(I; W)$ 属于语言 $R$ 。

为了实现 Groth_16，假设 verifier 可以计算对映射 $e (\cdot, \cdot)$ ，并可访问用于生成 $π$ 的 CRS。为了验证，verifier 计算如下曲线点：

$g_{1}^{I} = (g_{1}^{\frac{β \cdot A_{0} (τ) + α \cdot B_{0} (τ) + C_{0} (τ)}{γ}}) \cdot (g_{1}^{\frac{β \cdot A_{1} (τ) + α \cdot B_{1} (τ) + C_{1} (τ)}{γ}})^{I_{1}} \cdot \cdot \cdot (g_{1}^{\frac{β \cdot A_{n} (τ) + α \cdot B_{n} (τ) + C_{n} (τ)}{γ}})^{I_{n}}$

有了这些群元素，verifier 就可以使用配对映射通过如下等式验证 zk-SNARK $π = (g_{1}^{A}, g_{1}^{C}, g_{2}^{B})$ ：

$e (g_{1}^{A}, g_{2}^{B}) = e (g_{1}^{α}, g_{2}^{β}) \cdot e (g_{1}^{I}, g_{2}^{γ}) \cdot e (g_{1}^{C}, g_{2}^{δ})$

如果等式成立，则 verifier 输出 accept；否则，输出 reject。

配对 $e (g_{1}^{α}, g_{2}^{β})$ 独立于 proof，所以只需计算一次，然后成为 verifier key 的一部分。

4 模拟 proof 阶段

在启动阶段，创建了 CRS 和一个模拟后门，该后面应该在启动阶段结束后被丢弃。有了该后门，可以在不知道 witness 的情况下生成 zk-SNARK。

假设攻击者可以访问 Groth_16 参数，QAP，CRS 和相应的后门 ST：

$S T = (α, β, γ, δ, τ)$

给定 instance $I$ ，欺诈者可以生成该 instance 的 zk-SNARK，并可通过验证，而不需要知道该 instance 的witness $W$ 。

欺诈者可以使用模拟后门、QAP、任意两个来自配对群的标量域 $F_{r}$ 的域元素 $A, B$ 来计算给定 instance $< I_{1}, . . ., I_{n} >$ 的 $g_{1}^{C}$ ：

$g_{1}^{C} = g_{1}^{\frac{A \cdot B}{δ}} \cdot g_{1}^{- \frac{α \cdot β}{δ}} \cdot g_{1}^{- \frac{β A_{0} (τ) + α B_{0} (τ) + C_{0} (τ)}{δ}} \cdot (g_{1}^{- \frac{β A_{1} (τ) + α B_{1} (τ) + C_{1} (τ)}{δ}})^{I_{1}} \cdot \cdot \cdot (g_{1}^{- \frac{β A_{n} (τ) + α B_{n} (τ) + C_{n} (τ)}{δ}})^{I_{n}}$

其中， $g_{1}, g_{2}$ 是已知的，因为已经作为 $g_{1}^{τ^{0}}, g_{2}^{τ^{0}}$ 而被包含在了 CRS 中，所以欺诈者可以算出 $g_{1}^{A \cdot B}$ 。另外，模拟后门中的每个参数都是已知的，所以可以算出 $g_{1}^{C}$ 中的剩余部分。

然后发布 zk-SNARK $π_{f o r g e d} = (g_{1}^{A}, g_{1}^{C}, g_{2}^{B})$ ，可以通过验证，并且在不知道 $< W_{1}, . . ., W_{m} >$ 的情况下是可计算的。

# 参考

The MoonMath Manual 第 8 章

阿萍的博客

密码学[5]：Groth16

1 启动阶段

2 证明阶段

3 验证阶段

4 模拟 proof 阶段

没有评论

目录