密码学 - 追寻(zk)-SNARK

lambdaclass
发布于 2023-01-12 16:38
阅读 19

本文介绍了zk-SNARKs的基本概念、性质和构造方法，zk-SNARKs 是一种强大的密码学工具，可以用于构建完全私有的应用程序。文章重点阐述了KZG承诺方案，并探讨了如何使用椭圆曲线配对来实现高效的证明生成和验证。

## 介绍

简洁的非交互式知识论证 (SNARKs) 是强大的密码学原语，具有去中心化金融、治理和计算应用。 有许多不同的 SNARK，例如 Marlin（Aleo 使用的）、Plonk、STARKs、Groth16 等，具体取决于它们构建的工具，并且在性能、证明大小、验证时间等方面存在差异。但是，它们都基于一些共同的原则和属性。 在 SNARK 中，对于隐私应用最重要的零知识 SNARK（简称 zk-SNARK）。 它们允许我们证明我们知道某些变量，称为 witness，$w$，这样函数 $F$ 的输出，在 witness 和 instance（公共变量）$x$ 处求值为 $F(x,w)=y$，而不会泄露任何关于 $w$ 的信息。

我们可以将计算机程序转换为接收输入（其中一些我们可能希望隐藏）的函数，并使用 SNARK 证明其正确执行。 例如，我们可以将程序转换为算术电路 $C$，并且，给定公共输入和输出 $x$ 和机密数据 $w$，我们可以通过显示电路的满足性来证明程序已正确执行，即 $C(x,w)=0$。 由于算术电路满足性是一个 NP 完全 (NP-complete) 问题，我们可以将任何 NP 问题简化为算术电路（但这并不是唯一的选择，许多构造依赖于不同的技术）。

在深入细节之前，让我们首先解释 SNARK 的主要属性以及名称中每个术语的精确含义。 zk-SNARK 涉及两个参与者，证明者 (prover) 和验证者 (verifier)，其中第一个尝试说服后者给定的陈述，例如证明者知道 $w$ 使得 $C(w,x)=0$。 SNARK 必须满足以下条件：

1. 完备性 (Completeness)：如果证明者知道 $w$，他将始终能够说服诚实的验证者该陈述的有效性。
2. 可靠性 (Soundness)：如果该陈述是错误的，那么除了以非常低的概率外，没有作弊的证明者可以说服验证者接受。
3. 零知识 (Zero-knowledge)：证明不会泄露任何关于 witness 的信息。

至于名称，我们有以下内容：

1. 简洁性 (Succinctness)：证明必须简短且快速验证。 此属性将使我们能够将昂贵的计算委托给不受信任的各方，并在不自己运行程序的情况下检查其有效性。
2. 非交互性 (Non-interactive)：不需要证明者和验证者之间的交互，也不需要生成证明或验证它。 我们将看到该构造首先依赖于交互式证明，但我们可以通过使用 [Fiat-Shamir](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic) 变换将其转换为非交互式证明。
3. 知识论证 (Argument of knowledge)：我们可以用很高的概率证明我们知道 witness。

## 设置 (Setup)

SNARK 需要可信设置 (trusted setups)。 其中，我们可以区分：

- 统一参考字符串或透明设置 (Uniform reference string or transparent setups, URS)。
- 结构化参考字符串或私有设置 (Structured reference string or private setup, SRS)。

在 SRS 的情况下，我们可以找到两个实例：

- 通用的 (Universal)（例如，MARLIN）
- 特定的 (Specific)（Groth 16）

在实践中，可信设置是作为多方计算进行的； 如果至少有一个诚实方，则该构造将是安全的。 特定 SRS 的问题在于字符串取决于程序，并且我们必须为每个程序执行新的设置（这是不希望的属性）。

## 概率证明和验证者的能力

论证的简洁性依赖于概率证明。 为此，我们首先必须确定验证者的“权力”或能力。 我们有：

- 交互性 (Interaction)：验证者可以与证明者交互，发送挑战并接收响应。
- 多证明者 (Multiprover)：有多个证明者，但他们是隔离的。
- 随机性 (Randomness)：验证者可以选择随机元素或查询。
- 执行预言查询的能力 (Ability to perform queries to an oracle)：验证者可以查询证明者的消息。

当验证者可以访问这些能力中的多个时，我们会得到不同类型的证明：

- 交互性 + 随机性：交互式证明 (Interactive proofs, IP)。
- 随机性 + 预言：概率可检查证明 (Probabilistically checkable proofs, PCP)。
- 交互性 + 随机性 + 预言：交互式预言证明 (Interactive Oracle Proofs, IOP)

还有其他可能性，例如 MIOP，但我们将重点关注前 3 个。 IOP 为 SNARK 提供了最有效的构造：准线性时间验证、线性大小的证明长度、线性时间证明者和高效的实现。 从教育的角度来看 (PCP) 是有趣的，但在实践中效率低下（除了线性查询外，它不会产生简洁的证明）。 最后，IP 以子例程的形式提供了一些强大的构建块。

在 IOP 中，证明者和验证者交换消息。 证明者发送任意消息（在多项式 IOP 中，证明者发送对多项式的承诺 - 见下一节），验证者发送随机挑战。 经过几轮之后，验证者查询一些值并决定是否接受或拒绝该证明。

## 承诺方案 (Commitment schemes)

SNARK 的性能取决于所用承诺的类型； 近年来，为了改进它们，已经取得了许多进展。

我们可以将承诺视为一个保险箱。 我们为某个赌注做出一些选择，将其存储在安全容器中，然后将其交给其他人。 一旦结果已知，我们可以通过打开保险箱来揭示我们的选择。

承诺必须验证两个属性：

- 绑定性 (Binding)：我们不能为同一承诺产生两个有效的打开。 换句话说，如果我们承诺了某个值 $a$，则应该不可能找到 $b$ 使得 $cm(a)=cm(b)$。
- 隐藏性 (Hiding)：承诺不会泄露任何关于承诺数据的信息。

承诺消息的一种方法是使用[抗碰撞哈希函数](https://en.wikipedia.org/wiki/Cryptographic_hash_function)。 如果我们有一个消息 $m$ 和一些随机值 $r$，

$cm(m,r)=hash(m|r)$

鉴于它是抗碰撞的，我们具有绑定属性。

之后我们可以打开承诺并验证以下内容：

```
Verify(m,r,cm)→Verify(m,r,cm)→ 接受或拒绝
```

承诺的一个优点是它们往往很短。 例如，如果我们使用 SHA-256，则摘要长度将为 32 字节。

一类相关的承诺是多项式方案。 以下是一些构造以及它们所依赖的数学：

- 基本椭圆曲线：bulletproofs
- 双线性群：Kate-Zaverucha-Goldberg (KZG) 多项式承诺（配对，可信设置）DORY（无信任设置）
- 未知阶的群：DARK
- 仅哈希函数：FRI

## SNARK 解剖

可以通过选择以下两个要素来构建 SNARK：

1. 一种概率证明：例如，概率可检查证明 (PCP) 或交互式预言证明 (IOP)。 一种特殊的 IOP 是多项式 IOP (PIOP)。
2.  一种承诺方案（密码学）。 例如，多项式/函数承诺、向量承诺和线性编码。

概率证明决定了计算的类型。 它可以是机器计算（例如 vmTinyRam）或电路。

密码学元素决定了生成证明的成本、它是否具有后量子安全性以及设置的类型（透明的或结构化的）。 我们需要使用它们的数学工具是：

- 线性编码：椭圆曲线配对 (Elliptic curve pairings, ECP) + 格
- 向量承诺：抗碰撞哈希 (Collision resistant hash, CRH) 函数 + ECP。
- 多项式承诺：CRH、ECP、PO 群、UO 群

一些 SNARK 配方是：

1. 线性 PCP + 线性编码：Groth16，Groth-Maller 17
2. PCP/IOP + 向量承诺：STARKs
3. 多项式 PCP/IOP + 多项式承诺：MARLIN、SONIC、Plonk、Spartan。

Bulletproofs 采用上述要素的不同组合，并且基于密码学sum-check。

证明的大小在很大程度上取决于构造的类型。 例如，对于具有 KZG 多项式承诺的 PIOP，证明小于 1 kB（两个椭圆曲线元素）。 相比之下，带有 [FRI](https://vitalik.ca/general/2017/11/22/starks_part_2.html)（快速 Reed-Solomon 交互式预言邻近证明）的 IOP 需要大约 100 kB，多出两个数量级！ 这种差异是因为 FRI 使用 Merkle 树； 验证需要一条认证路径，需要多个哈希。

我们使用电路面临的一个问题是，验证者应该读取它，从而导致线性验证时间，该时间线性地取决于大小（这将使其不简洁）。 为了避免这种情况，我们可以对其进行预处理并获得亚线性验证时间。

现在我们将重点关注 KZG 多项式承诺，它是 Marlin 和 Plonk 的基础。

## KZG 承诺方案

多项式承诺方案具有以下算法：

1. 设置 (Setup)。
2. 承诺 (Commit)。
3. 打开 (Open)。

为了承诺一个多项式，我们将在一个给定的但未知的点 $\alpha$ 评估该多项式。

该设置采用多项式的最大度数（取决于算术电路的门数）并输出公共参数：证明密钥和验证密钥。 为了能够评估多项式，我们将使用椭圆曲线（我们需要它是[配对友好](https://learnblockchain.cn/article/22825/)的，例如 BLS 12-377）来隐藏 $\alpha$ 及其幂（$\alpha$ 在设置仪式期间选择并作为有毒废物丢弃！）。 为此，我们选择一个大素数阶 $d+1$ 的群的生成元 $g$，并计算

$H=g,\alpha g,\alpha^2 g,\alpha^3 g,...,\alpha^d g=h_0,h_1,h_2,...h_d$

此计算将为我们提供大量的椭圆曲线点（我们将它们保存为一个字符串），该字符串将用作证明密钥。 对于通用设置，元素的数量将与电路的最大大小一致。 由于椭圆曲线点大约占用 100 B，如果我们想要处理 $10^8$ 个门，我们将需要超过 1 GB 的存储空间。 对于给定的电路，可能比最大值小得多，MARLIN 会修剪密钥，使其更简单、更快地工作。 该设置还取决于安全参数 $\lambda$，但我们将在分析中将其视为固定值。

因此，我们有 setup$(\lambda,N) \rightarrow pp(pk,vk)$。

证明者生成多项式 $P(x)=p_0+p_1x+...+p_dx^d$ 并通过在 $\alpha$ 处对其求值来承诺它。 由于我们不知道 $\alpha$，只有 $\alpha$ 的幂的群元素的标量倍数，

$cm(P)=p_0g+p_1\alpha g+...+p_d\alpha^d g=p_0h_0+p_1h_1+...+p_dh_d$

这个计算是多标量乘法问题（[MSM](https://learnblockchain.cn/article/22825/)）。 我们看到多项式承诺对应于椭圆曲线的一个群元素。

我们还可以使用 [Merkle 树](https://en.wikipedia.org/wiki/Merkle_tree) 来承诺一个多项式。 Merkle 树的问题在于树的大小将取决于多项式的度数。 在 KZG 的情况下，承诺只是一个独立于大小的群元素。 此外，当我们想在证明中评估多项式时，我们需要明确地发送所有系数（揭示多项式），并且验证者必须对多项式的大小进行线性工作。 另一方面，我们将看到 KZG 主要隐藏多项式（除非有很多查询），并且验证独立于多项式的度数。 此外，KZG 允许批量证明：如果我们有多个承诺 $cm_1$，$cm_2$，...，$cm_k$，我们可以生成一个单一证明来表明所有承诺都是有效的。

一旦证明者承诺了多项式，验证者（在交互方案中）可以向证明者发送随机点 $r_k$，后者给出在 $r_k$ 评估的多项式，$P(r_k)$。 为了使其非交互式，我们使用 Fiat-Shamir 变换从密码学哈希函数生成随机挑战。

假设证明者想要说服验证者 $P(u)=v$。 他可以将该方程转换为多项式 $g(x)=P(x)-v$，它在 $x=u$ 处有一个根。 这个事实意味着 $g(x)$ 可以被 $x-u$ 整除，我们可以将其写成 $g(x)=P(x)-v=Q(x)(x-u)$，其中 $Q$ 是商多项式。 证明者可以像以前一样通过执行以下操作来承诺 $Q(x)$

$cm(Q)=q_0g+q_1\alpha^d+...+q_{d-1}\alpha^{d-1}g=q_0h_0+q_1h_1+...+q_{d-1}h_{d-1}$

这是另一个 MSM。 证明 $\pi$ 包含这个群元素：常数大小！ 该证明将表明 $P(u)=v$，$P$ 确实是最多 $d$ 阶的多项式，并且 $P$ 的承诺是 $cm(P)$。

如果 $(\alpha-u)cm(Q)=cm(P)-vg$，则验证者接受该证明。 问题是我们不知道 $\alpha$。 这就是[配对](https://vitalik.ca/general/2017/01/14/exploring_ecp.html)发挥作用的地方，我们只需要元素 $h_0$ 和 $h_1$ 就能够进行计算。 粗略地说，椭圆曲线配对是一个函数

$f:G_1 \times G_2 \rightarrow G_t$

它接受两个元素，来自 $G_1$ 的 $P$ 和来自 $G_2$ 的 $Q$，并输出来自 $G_t$ 的元素 $R$。 所有群都具有相同的阶 $r$ 并且对应于配对友好的椭圆曲线中的群。 在 MARLIN 的情况下，我们使用 [曲线 BLS 12-377](https://learnblockchain.cn/article/22825/)。 配对满足以下条件：

$f(P,Q)=f(g,g_2)^{pq}$

其中 $g$ 和 $g_2$ 是群 $G_1$ 和 $G_2$ 的生成元（并且 $P=pg$ 和 $Q=qg_2$）。 配对中的验证方程的形式为

$f(cm(Q),(\alpha-u)g_2)=f(cm(P)-vg,g_2)$

我们对 $G_t$ 进行检查。 我们只需要从可信设置中知道 $\alpha g_2$ 即可。

我们如何才能确信，如果我们在一个点评估了多项式并且它们重合，那么该论证很可能是正确的？ 答案在于 [Schwartz-Zippel 引理](https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma)（我们将针对有限域进行说明）：对于阶数为 $p$ 的有限域上的 $d$ 次多项式 $P$，多项式在随机采样的点 $r$ 处为零的概率为

$Pr(P(r)=0)=d/p$

鉴于电路的最大大小（其给出多项式的最大度数）约为 $2^{26} \approx 10^8$，并且字段的大小大于 $2^{256}$，则概率约为 $2^{-230} \approx 10^{-70}$。 如果我们说 $P_1$ 和 $P_2$ 在一个点 $r$ 处重合，我们可以构造多项式 $P(x)=P_1(x)-P_2(x)$（因为多项式加法是封闭的）并且 $P(r)=0$。 鉴于随机击中零的可能性极小，我们有信心 $P(x)$ 是零多项式。

## 总结

Zk-SNARK 由于其在开发完全私有应用程序中的使用而开始受到关注。 它们提供了简洁的证明，证明特定计算已正确执行，而不会泄露敏感信息。 有许多可能的构造，大多数基于概率证明和承诺方案。 根据不同的选择，更有效的版本是可能的，并决定了计算的类型（机器或电路计算）。 我们探讨了 KZG 承诺方案，该方案展示了 MARLIN 和 Plonk 等系统背后的思想以及我们生成和验证证明所需的计算。

>- 原文链接： [blog.lambdaclass.com/the...](https://blog.lambdaclass.com/the-hunting-of-the-zk-snark)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

介绍

简洁的非交互式知识论证 (SNARKs) 是强大的密码学原语，具有去中心化金融、治理和计算应用。有许多不同的 SNARK，例如 Marlin（Aleo 使用的）、Plonk、STARKs、Groth16 等，具体取决于它们构建的工具，并且在性能、证明大小、验证时间等方面存在差异。但是，它们都基于一些共同的原则和属性。在 SNARK 中，对于隐私应用最重要的零知识 SNARK（简称 zk-SNARK）。它们允许我们证明我们知道某些变量，称为 witness，$w$，这样函数 $F$ 的输出，在 witness 和 instance（公共变量）$x$ 处求值为 $F(x,w)=y$，而不会泄露任何关于 $w$ 的信息。

我们可以将计算机程序转换为接收输入（其中一些我们可能希望隐藏）的函数，并使用 SNARK 证明其正确执行。例如，我们可以将程序转换为算术电路 $C$，并且，给定公共输入和输出 $x$ 和机密数据 $w$，我们可以通过显示电路的满足性来证明程序已正确执行，即 $C(x,w)=0$。由于算术电路满足性是一个 NP 完全 (NP-complete) 问题，我们可以将任何 NP 问题简化为算术电路（但这并不是唯一的选择，许多构造依赖于不同的技术）。

完备性 (Completeness)：如果证明者知道 $w$，他将始终能够说服诚实的验证者该陈述的有效性。
可靠性 (Soundness)：如果该陈述是错误的，那么除了以非常低的概率外，没有作弊的证明者可以说服验证者接受。
零知识 (Zero-knowledge)：证明不会泄露任何关于 witness 的信息。

至于名称，我们有以下内容：

简洁性 (Succinctness)：证明必须简短且快速验证。此属性将使我们能够将昂贵的计算委托给不受信任的各方，并在不自己运行程序的情况下检查其有效性。
非交互性 (Non-interactive)：不需要证明者和验证者之间的交互，也不需要生成证明或验证它。我们将看到该构造首先依赖于交互式证明，但我们可以通过使用 Fiat-Shamir 变换将其转换为非交互式证明。
知识论证 (Argument of knowledge)：我们可以用很高的概率证明我们知道 witness。

设置 (Setup)

SNARK 需要可信设置 (trusted setups)。其中，我们可以区分：

统一参考字符串或透明设置 (Uniform reference string or transparent setups, URS)。
结构化参考字符串或私有设置 (Structured reference string or private setup, SRS)。

在 SRS 的情况下，我们可以找到两个实例：

通用的 (Universal)（例如，MARLIN）
特定的 (Specific)（Groth 16）

在实践中，可信设置是作为多方计算进行的；如果至少有一个诚实方，则该构造将是安全的。特定 SRS 的问题在于字符串取决于程序，并且我们必须为每个程序执行新的设置（这是不希望的属性）。

概率证明和验证者的能力

论证的简洁性依赖于概率证明。为此，我们首先必须确定验证者的“权力”或能力。我们有：

交互性 (Interaction)：验证者可以与证明者交互，发送挑战并接收响应。
多证明者 (Multiprover)：有多个证明者，但他们是隔离的。
随机性 (Randomness)：验证者可以选择随机元素或查询。
执行预言查询的能力 (Ability to perform queries to an oracle)：验证者可以查询证明者的消息。

当验证者可以访问这些能力中的多个时，我们会得到不同类型的证明：

交互性 + 随机性：交互式证明 (Interactive proofs, IP)。
随机性 + 预言：概率可检查证明 (Probabilistically checkable proofs, PCP)。
交互性 + 随机性 + 预言：交互式预言证明 (Interactive Oracle Proofs, IOP)

还有其他可能性，例如 MIOP，但我们将重点关注前 3 个。 IOP 为 SNARK 提供了最有效的构造：准线性时间验证、线性大小的证明长度、线性时间证明者和高效的实现。从教育的角度来看 (PCP) 是有趣的，但在实践中效率低下（除了线性查询外，它不会产生简洁的证明）。最后，IP 以子例程的形式提供了一些强大的构建块。

在 IOP 中，证明者和验证者交换消息。证明者发送任意消息（在多项式 IOP 中，证明者发送对多项式的承诺 - 见下一节），验证者发送随机挑战。经过几轮之后，验证者查询一些值并决定是否接受或拒绝该证明。

承诺方案 (Commitment schemes)

SNARK 的性能取决于所用承诺的类型；近年来，为了改进它们，已经取得了许多进展。

我们可以将承诺视为一个保险箱。我们为某个赌注做出一些选择，将其存储在安全容器中，然后将其交给其他人。一旦结果已知，我们可以通过打开保险箱来揭示我们的选择。

承诺必须验证两个属性：

绑定性 (Binding)：我们不能为同一承诺产生两个有效的打开。换句话说，如果我们承诺了某个值 $a$，则应该不可能找到 $b$ 使得 $cm(a)=cm(b)$。
隐藏性 (Hiding)：承诺不会泄露任何关于承诺数据的信息。

承诺消息的一种方法是使用抗碰撞哈希函数。如果我们有一个消息 $m$ 和一些随机值 $r$，

$cm(m,r)=hash(m|r)$

鉴于它是抗碰撞的，我们具有绑定属性。

之后我们可以打开承诺并验证以下内容：

Verify(m,r,cm)→Verify(m,r,cm)→ 接受或拒绝

承诺的一个优点是它们往往很短。例如，如果我们使用 SHA-256，则摘要长度将为 32 字节。

一类相关的承诺是多项式方案。以下是一些构造以及它们所依赖的数学：

基本椭圆曲线：bulletproofs
双线性群：Kate-Zaverucha-Goldberg (KZG) 多项式承诺（配对，可信设置）DORY（无信任设置）
未知阶的群：DARK
仅哈希函数：FRI

SNARK 解剖

可以通过选择以下两个要素来构建 SNARK：

一种概率证明：例如，概率可检查证明 (PCP) 或交互式预言证明 (IOP)。一种特殊的 IOP 是多项式 IOP (PIOP)。
一种承诺方案（密码学）。例如，多项式/函数承诺、向量承诺和线性编码。

概率证明决定了计算的类型。它可以是机器计算（例如 vmTinyRam）或电路。

密码学元素决定了生成证明的成本、它是否具有后量子安全性以及设置的类型（透明的或结构化的）。我们需要使用它们的数学工具是：

线性编码：椭圆曲线配对 (Elliptic curve pairings, ECP) + 格
向量承诺：抗碰撞哈希 (Collision resistant hash, CRH) 函数 + ECP。
多项式承诺：CRH、ECP、PO 群、UO 群

一些 SNARK 配方是：

线性 PCP + 线性编码：Groth16，Groth-Maller 17
PCP/IOP + 向量承诺：STARKs
多项式 PCP/IOP + 多项式承诺：MARLIN、SONIC、Plonk、Spartan。

Bulletproofs 采用上述要素的不同组合，并且基于密码学sum-check。

证明的大小在很大程度上取决于构造的类型。例如，对于具有 KZG 多项式承诺的 PIOP，证明小于 1 kB（两个椭圆曲线元素）。相比之下，带有 FRI（快速 Reed-Solomon 交互式预言邻近证明）的 IOP 需要大约 100 kB，多出两个数量级！这种差异是因为 FRI 使用 Merkle 树；验证需要一条认证路径，需要多个哈希。

我们使用电路面临的一个问题是，验证者应该读取它，从而导致线性验证时间，该时间线性地取决于大小（这将使其不简洁）。为了避免这种情况，我们可以对其进行预处理并获得亚线性验证时间。

现在我们将重点关注 KZG 多项式承诺，它是 Marlin 和 Plonk 的基础。

KZG 承诺方案

多项式承诺方案具有以下算法：

设置 (Setup)。
承诺 (Commit)。
打开 (Open)。

为了承诺一个多项式，我们将在一个给定的但未知的点 $\alpha$ 评估该多项式。

该设置采用多项式的最大度数（取决于算术电路的门数）并输出公共参数：证明密钥和验证密钥。为了能够评估多项式，我们将使用椭圆曲线（我们需要它是配对友好的，例如 BLS 12-377）来隐藏 $\alpha$ 及其幂（$\alpha$ 在设置仪式期间选择并作为有毒废物丢弃！）。为此，我们选择一个大素数阶 $d+1$ 的群的生成元 $g$，并计算

$H=g,\alpha g,\alpha^2 g,\alpha^3 g,...,\alpha^d g=h_0,h_1,h_2,...h_d$

此计算将为我们提供大量的椭圆曲线点（我们将它们保存为一个字符串），该字符串将用作证明密钥。对于通用设置，元素的数量将与电路的最大大小一致。由于椭圆曲线点大约占用 100 B，如果我们想要处理 $10^8$ 个门，我们将需要超过 1 GB 的存储空间。对于给定的电路，可能比最大值小得多，MARLIN 会修剪密钥，使其更简单、更快地工作。该设置还取决于安全参数 $\lambda$，但我们将在分析中将其视为固定值。

因此，我们有 setup$(\lambda,N) \rightarrow pp(pk,vk)$。

证明者生成多项式 $P(x)=p_0+p_1x+...+p_dx^d$ 并通过在 $\alpha$ 处对其求值来承诺它。由于我们不知道 $\alpha$，只有 $\alpha$ 的幂的群元素的标量倍数，

$cm(P)=p_0g+p_1\alpha g+...+p_d\alpha^d g=p_0h_0+p_1h_1+...+p_dh_d$

这个计算是多标量乘法问题（MSM）。我们看到多项式承诺对应于椭圆曲线的一个群元素。

我们还可以使用 Merkle 树来承诺一个多项式。 Merkle 树的问题在于树的大小将取决于多项式的度数。在 KZG 的情况下，承诺只是一个独立于大小的群元素。此外，当我们想在证明中评估多项式时，我们需要明确地发送所有系数（揭示多项式），并且验证者必须对多项式的大小进行线性工作。另一方面，我们将看到 KZG 主要隐藏多项式（除非有很多查询），并且验证独立于多项式的度数。此外，KZG 允许批量证明：如果我们有多个承诺 $cm_1$，$cm_2$，...，$cm_k$，我们可以生成一个单一证明来表明所有承诺都是有效的。

一旦证明者承诺了多项式，验证者（在交互方案中）可以向证明者发送随机点 $r_k$，后者给出在 $r_k$ 评估的多项式，$P(r_k)$。为了使其非交互式，我们使用 Fiat-Shamir 变换从密码学哈希函数生成随机挑战。

假设证明者想要说服验证者 $P(u)=v$。他可以将该方程转换为多项式 $g(x)=P(x)-v$，它在 $x=u$ 处有一个根。这个事实意味着 $g(x)$ 可以被 $x-u$ 整除，我们可以将其写成 $g(x)=P(x)-v=Q(x)(x-u)$，其中 $Q$ 是商多项式。证明者可以像以前一样通过执行以下操作来承诺 $Q(x)$

$cm(Q)=q_0g+q1\alpha^d+...+q{d-1}\alpha^{d-1}g=q_0h_0+q_1h1+...+q{d-1}h_{d-1}$

这是另一个 MSM。证明 $\pi$ 包含这个群元素：常数大小！该证明将表明 $P(u)=v$，$P$ 确实是最多 $d$ 阶的多项式，并且 $P$ 的承诺是 $cm(P)$。

如果 $(\alpha-u)cm(Q)=cm(P)-vg$，则验证者接受该证明。问题是我们不知道 $\alpha$。这就是配对发挥作用的地方，我们只需要元素 $h_0$ 和 $h_1$ 就能够进行计算。粗略地说，椭圆曲线配对是一个函数

$f:G_1 \times G_2 \rightarrow G_t$

它接受两个元素，来自 $G_1$ 的 $P$ 和来自 $G_2$ 的 $Q$，并输出来自 $G_t$ 的元素 $R$。所有群都具有相同的阶 $r$ 并且对应于配对友好的椭圆曲线中的群。在 MARLIN 的情况下，我们使用曲线 BLS 12-377。配对满足以下条件：

$f(P,Q)=f(g,g_2)^{pq}$

其中 $g$ 和 $g_2$ 是群 $G_1$ 和 $G_2$ 的生成元（并且 $P=pg$ 和 $Q=qg_2$）。配对中的验证方程的形式为

$f(cm(Q),(\alpha-u)g_2)=f(cm(P)-vg,g_2)$

我们对 $G_t$ 进行检查。我们只需要从可信设置中知道 $\alpha g_2$ 即可。

我们如何才能确信，如果我们在一个点评估了多项式并且它们重合，那么该论证很可能是正确的？答案在于 Schwartz-Zippel 引理（我们将针对有限域进行说明）：对于阶数为 $p$ 的有限域上的 $d$ 次多项式 $P$，多项式在随机采样的点 $r$ 处为零的概率为

$Pr(P(r)=0)=d/p$

鉴于电路的最大大小（其给出多项式的最大度数）约为 $2^{26} \approx 10^8$，并且字段的大小大于 $2^{256}$，则概率约为 $2^{-230} \approx 10^{-70}$。如果我们说 $P_1$ 和 $P_2$ 在一个点 $r$ 处重合，我们可以构造多项式 $P(x)=P_1(x)-P_2(x)$（因为多项式加法是封闭的）并且 $P(r)=0$。鉴于随机击中零的可能性极小，我们有信心 $P(x)$ 是零多项式。

总结

Zk-SNARK 由于其在开发完全私有应用程序中的使用而开始受到关注。它们提供了简洁的证明，证明特定计算已正确执行，而不会泄露敏感信息。有许多可能的构造，大多数基于概率证明和承诺方案。根据不同的选择，更有效的版本是可能的，并决定了计算的类型（机器或电路计算）。我们探讨了 KZG 承诺方案，该方案展示了 MARLIN 和 Plonk 等系统背后的思想以及我们生成和验证证明所需的计算。

原文链接： blog.lambdaclass.com/the...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。