# ZK-SNARK 介绍

By [Asten](https://paragraph.com/@asten) · 2022-11-08

---

ZK-SNARK 是一种零知识证明协议，在该协议中，人们可以证明他们拥有某些信息，而无需透露这些信息，也无需证明者（Prover）和验证者（Verifier）之间进行任何交互来证明和验证信息。

术语“ZK-SNARK”是一个首字母缩写词，代表“Zero-Knowledge Succinct Non-Interactive Argument of Knowledge”。名称的每个部分都指代 ZK-SNARK 的一个特征：

*   Zero-Knowledge：证明者可以向验证者证明他们拥有一条信息，而无需提供信息本身。
    
*   Succinct：证明（Proof）可以在几毫秒内被验证，而且证明的长度一般只有几百到几千字节。
    
*   Non-Interactive：证明是由从证明者到验证者的单个消息组成。
    
*   Argument：论证是用于这些证明的术语。
    
*   Knowledge：知识是指证明者所拥有的信息。
    

零知识证明（Zero Knowledge Proof）最初是在 1985 年由 Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 撰写的一篇论文中引入的。 零知识证明是一种方法，它允许一方仅声明他们拥有一条信息，而不需要透露信息本身或任何其他信息。

早期的零知识协议要求证明者和验证者来回发送消息。 Nir Bitansky、Ran Canetti、Alessandro Chiesa 和 Eran Tromer 在 2012 年的一篇论文中创造了术语“ZK-SNARK”来描述一种新的零知识协议。 与以前的方法不同，它不需要证明者和验证者来回发送消息。

假设我知道某个消息 m 可以使得“SHA256(m) = 0”。我想向你证明我知道这样一个 m。一个简单证明方法就是我将消息 m 发送给你，然后你可以验证 m 的 SHA256 是否等于 0。如果消息 m 是千兆字节长，首先消息的传送消耗带宽和内存，其次验证者需要散列整个消息以验证它是否等于零。如果我不想透露 m 的原始值，上诉方法也不能解决。

我们的目标是建立一个非常短的证明，它只有几百到几千字节，而且验证也会非常快，验证它只需几毫秒验证并且验证者无需知道 m 就可以确信我知道这样的消息 m。这就是 ZK-SNARK 所要解决的问题。

Waldo 在哪里
---------

![Where Is Waldo](https://storage.googleapis.com/papyrus_images/6dca987bf910d799e43542777532f7f99dfa95e073e7a26f155f080cb54c4e94.png)

Where Is Waldo

在深入解释 ZK-SNARK 之前，先来了解一个零知识证明（Zero Knowledge Proof）的经典游戏，Waldo 在哪里？

给你一张有很多人的图片，如上图，你的工作是找到 Waldo。可以注意到 Waldo 就在图片的中心。想象一下，你想向某些人证明你知道 Waldo 在哪里，而不向他们透露 Waldo 在哪里，可以使用零知识向他们证明。

你走进一个什么都没有的房间，验证者会把上面的图片交给你并且给你一把剪刀。你在图片里面找到 Waldo，然后你会从中剪下 Waldo 的图片，然后破坏那张原始图片，例如撕掉它，然后把仅有 Waldo 的图片交给验证者。

为什么这是零知识证明？验证者已经知道 Waldo 的样子，因此你给它的 Waldo 图片并没有教给验证者任何它不知道的东西，这个想法正是零知识证明定义背后的想法，因为证明除了验证者已经知道的之外，没有向验证者透露任何其他信息。

ZK-SNARK 的数学计算式
---------------

假设Alice 知道计算散列值 H 的原始值 s，并且他希望向 Bob 证明他知道 s 。通常 Alice 会通过将 s 发送给 Bob 来证明这一点，之后 Bob 将计算 s 的散列值并检查它是否等于 H。

但是，假设 Alice 不想向 Bob 透露值 s，而只是想证明她知道该值。她可以为此使用 ZK-SNARK。

我们可以使用以下程序来描述 Alice 的场景：

    function C(x, w) {  
        return ( sha256(w) == x );
    }
    

这是一个 Arithmetic Circuits 抽象出的函数，记为 C，接受两个输入参数：C(x, w)。参数 x 是公开的声明 （statement），证明者和验证者都知悉的值，w（witness）是只有证明者知道的保密值。程序的输出是布尔值，即 true 或 false。然后给目标函数 一个特定的输入 x，使得 C(x,w) == true，证明证明者（prover）知道保密的输入 w。

换句话说：程序接受一个公开的参数散列值 x 和一个保密值 w，如果 w 的 SHA256 散列值等于 x，则返回 true。

使用函数 C(x,w) 转换 Alice 的问题，我们看到 Alice 需要证明她拥有 s 使得 C(H, s) == true，而不必揭示 s。这就是 ZK-SNARK 解决的一般问题。

ZK-SNARK 由三个算法 G、P、V 组成，定义如下：

### 密钥生成算法 G（generator）

G 采用保密随机数 lambda 和程序 C，生成两个公开可用的密钥，一个证明密钥（_proving key_） pk 和一个验证密钥（_verification key_） vk。这些密钥是公共参数，只需为给定程序 C 生成一次。

    (pk, vk) = G(C, lambda)
    

我们把生成 pk，vk 的算法 G 称为预处理程序，此设置过程接受 C 并产生一些公共参数，我们将 pk 称为证明者的公共参数，将 vk 作为验证者的公共参数。

### 证明生成算法 P （Proving）

证明者 P（Prover） 将证明密钥 pk、公共参数 x 和保密值 w 作为输入。该算法生成证明 prf（proof）

    prf = P(pk, x, w)
    

### 验证算法 V （Verifying）

验证者计算 V(vk, x, prf)，如果 proof 正确则返回 true，否则返回 false。因此，如果证明者知道正确的 w 则满足 C(x,w) == true，则此函数返回 true。

    bool = V(vk, x, prf)
    

该算法之所以被称为非交互式（Non-Interactive）的系统是因为证明者仅需一次性将证明发送给验证者，过程中没有任何交互式对话，验证者收到证明以后就可以马上确定证明者的证明是否为真。

请注意此处生成算法中使用的保密参数 lambda。这个参数有时会让在实际应用中使用 ZK-SNARK 变得很棘手。原因是任何知道这个参数的人都可以生成假证明。具体来说，给定任何程序 C 和公共输入 x，知道 lambda 的人可以生成假的 proof 即 fake\_prf，使得 V(vk, x, fake\_prf) 在不知道 w 的情况下也返回 true。

因此，实际运行生成算法需要一个非常安全的过程，以确保没有人知道 lambda 和它保存的地方。

Alice 和 Bob 在实践中如何使用 ZK-SNARK 来让 Alice 证明她知道上面示例中的保密值 w？

首先，如上所述，我们将使用由以下函数定义的 C：

`function C(x, w) { return ( sha256(w) == x ); }`

第一步是让 Bob 运行生成算法 G，以创建证明密钥 pk 和验证密钥 vk。首先，随机生成 lambda 并将其用作输入：

`(pk, vk) = G(C, lambda)`

小心处理参数 lambda，因为如果 Alice 知道 lambda 的值，她将能够创建假证明。

Bob 将与 Alice 共享 pk 和 vk。Alice 现在将扮演证明者的角色。她需要证明她知道计算散列值 H 的原值 s。她使用输入 pk、H 和 s 运行证明算法 P 以生成证明 prf：

`prf = P(pk, H, s)`

接下来，Alice 将证明 prf 提供给 Bob，Bob 运行验证函数 V(vk, H, prf)，在这种情况下，由于 Alice 正确地知道保密的值 s，它将返回 true。 Bob 可以确信 Alice 知道这个保密值 s，但 Alice 不需要向 Bob 透露这个这个保密值 s。

ZK-SNARK 的应用举例
--------------

### 隐私保护

在一个交易数据可以被任何人查看的公共区块链上，任何人都可以验证交易是否遵循协议规则，但是可以使用 ZK-SNARK 隐藏交易的具体内容。

### 合规性检查

某些场景希望在不公开内部数据的前提下满足合规性检查，例如交易所可能想要证明他们的偿付能力，他们有足够的资金来履行对客户的义务，但他们希望以零知识的方式进行，以便他们可以发布非常简短的证明，然后任何人都可以验证证明是有效的，证明交易所是有偿付能力的，而且这样做不会透露有关其内部运营的任何信息，因此不透露他们拥有多少资产、他们拥有多少客户等等。

### 有效性证明汇总（ ZK-Rollup）

具有有效性证明的汇总系统，上千或上万笔交易将被分批处理，所有交易都在链下计算，然后将它们汇总为单个事务，接着产生一个简短的证明，证明所有这些交易都是有效的，并且只有这个简短的证明会被发布到区块链上，链上的验证者只会验证该证明是否正确，而实际上不必一个接一个地验证所有交易，这大大减少了链上的工作量。

---

*Originally published on [Asten](https://paragraph.com/@asten/zk-snark)*