Introduction to zk-SNARKs with Examples

本文介绍 zk-SNARK 的定义，以及 zk-SNARK 的应用场景，本文不会介绍 zk-SNARK 的实现原理。本文不是原创，是一篇翻译文章，原文为：Introduction to zk-SNARKs with Examples ，推荐读者阅读原文。

在这篇文章中，我们旨在从实用的角度概述 zk-SNARK。我们将把其数学原理视为一个黑匣子，会聚焦在如何使用它，并将给出一个简单应用。

零知识证明的目标是让验证者（verifier）能够说服自己，证明者（prover）确实拥有一个秘密值（称为 witness），会满足某种关系，而无需向验证者或其他任何人透露 witness。

更具体地说，可以把它记为程序 $C$ ，它接受两个输入： $C(x,w)$ 。其中输入 $x$ 是公开的输入，而 $w$ 秘密的输入（witness 缩写）。程序 $C$ 的输出是布尔值，即 true 或 false。零知识证明的目标是被给予公开输入 $x$ ，证明 prover 知道某个秘密输入 $w$ ，会满足关系 $C(x,w)==true$ 。

我们将特别讨论非交互式零知识证明，这意味着证明本身是一组数据，无需 prover 进行任何交互即可进行验证。

假设 Bob 得到了某个值的哈希值 $H$ ，并且他希望有一个证明，证明 Alice 知道 $s$ 的哈希值就是 $H$ 。显然，Alice 直接把 $s$ 值给 Bob，然后 Bob 计算它的哈希值并检查它是否等于 $H$ 即可。

然而，假设 Alice 不想把 $s$ 透露给 Bob，而只是想证明她知道 $s$ 。为此，Alice 可以使用 zk-SNARK。

我们可以使用以下程序来描述 Alice 的场景，这里编写为 Javascript 函数：

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

换句话说：上面程序接受一个公开的哈希值 $x$ 和一个秘密值 $w$ ，如果 $w$ 的 SHA-256 哈希值等于 $x$ 则返回 true。

用上面的函数 $C(x,w)$ 翻译 Alice 的问题，就是 Alice 需要创建一个证明，以证明她知道某个值 $s$ ，会满足关系 $C(H,s)==true$ ，且不必透露这个 $s$ 。这就是 zk-SNARKs 所能解决的问题。

zk-SNARK 由三种算法 G, P, V 组成，分别定义如下：

1. 算法 G，表示 Key Generator。它接受秘密参数 lambda 和程序 $C$ ，并生成两个公开可用的密钥：证明密钥 $pk$ 和验证密钥 $vk$ 。可表示为 $(pk,vk)=G(C,lambda)$ 。生成的这两个密钥是公开参数，且对于指定的程序 $C$ 来说只需要生成一次。
   
2. 算法 P 是 prover 执行的算法。它有三个输入：证明密钥 $pk$ 、公开输入 $x$ 和秘密输入 $w$ 。运行该算法会得到一个证明，即 $prf=P(pk,x,w)$ 。
   
3. 算法 V 是 verifier 执行的算法。它有三个输入：验证密钥 $vk$ 、公开输入 $x$ 和算法 $P$ 输出值 $prf$ 。如果 $prf$ 是正确的，则 $V(vk,x,prf)$ 返回 true，否则返回 false。也就是说，如果 prover 确实知道某个 $w$ 会满足 $C(x,w)==true$ ，且 prover 正确地计算了 prf，那么 $V(vk,x,prf)$ 就会为 true。
   

需要注意的是，在算法 $G$ 中使用的秘密参数 lambda。该参数会使在实际应用中使用 zk-SNARK 变得很棘手。原因是任何知道这个参数的人都可以生成假证明。具体来说，给定任何程序 $C$ 和公开输入 $x$ ，知道秘密参数 lambda 的人可以生成一个假证明 $fake\text{\_}prf$ ，会满足 $V(vk,x,fake\text{\_}prf)==true$ ，就算这个人不知道秘密输入 $w$ （注：正常情况下，知道了秘密输入 $w$ ，执行算法 P 才能生成证明）。

因此，在实际运行算法 G 时需要一个非常安全的过程，以确保没有人知道和保存 lambda 在任何地方。这就是 Zcash 团队进行极其复杂的 ceremony 的原因，以生成证明密钥 $pk$ 和验证密钥 $vk$ ，同时确保“有毒废物”参数 lambda 在此过程中被销毁。

在实践中，Alice 和 Bob 如何使用 zk-SNARK 来让 Alice 证明她知道上面示例中的秘密值（即解决节 3 中的问题）呢？

首先，我们将使用由以下函数定义的程序：

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

Bob 的第一个操作是运行算法 G，以创建证明密钥 pk 和验证密钥 vk。这是通过首先随机生成 lambda 并将其用作输入来完成的：

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

Bob 将 $pk$ 和 $vk$ 分享给 Alice。前面说过了，参数 lambda 必须被小心地处理，因为如果 Alice 知道了参数 lambda，她将能够创建假证明。

Alice 现在是 prover 角色。她需要证明她知道值 $s$ ，其 SHA256 哈希值为 $H$ 。Alice 运行算法 $P$ 生成证明 prf：

prf = P(pk, H, s)

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

在上面的示例中，如果 Bob 想向 Alice 证明他知道一个秘密，则 Bob 不能使用前面 zk-SNARK 的证明密钥 pk 来生成证明。这是因为 Alice 无法确保 Bob 没有保存 lambda 参数，因此 Bob 可能能够伪造证明（假设 Bob 悄悄地保存了 lambda 的话）。

如果一个程序对很多人有用，那么可以由受信任的第三方来运行生成器算法 G，以创建证明密钥 pk 和验证密钥 vk ，由受信任的第三方来保证参数 lambda 没有被保存。

任何信任这个第三方的人都可以使用这些密钥进行未来的交互。

开发者已经开始将 zk-SNARK 集成到以太坊中（参见 PR213）。这看起来像什么？具体来说，验证算法的构建块以预编译合约的形式添加到以太坊中。用法如下：生成器 G 在链外运行来生成证明密钥 $pk$ 和验证密钥 $vk$ 。然后，任何证明者都可以使用证明密钥 $pk$ 来创建证明，这也是链下的。然后，通用验证算法 $V$ 可以在智能合约内运行，使用 $prf$ 、验证密钥 $vk$ 和公开输入 $x$ 作为输入参数。验证算法的结果可用于触发其他链上活动。

这是 zk-SNARKs 如何帮助保护以太坊隐私的简单示例。假设我们有一个简单的代币合约。通常，代币合约的核心是从地址到余额的映射：

mapping (address => uint256) balances;

我们将保留相同的基本逻辑，除了用余额的哈希值替换余额：

mapping (address => bytes32) balanceHashes;

我们不会隐藏交易的发送者或接收者，但我们将能够隐藏余额和发送的金额。该属性有时称为保密交易（confidential transactions）。

两个 zk-SNARK 将用于将代币从一个账户发送到另一个账户，一份由发送者创建，一份由接收者创建。

通常，在代币合约中，为了使交易值 value 有效，我们需要验证以下内容：

balances[fromAddress] >= value

因此，我们的 zk-SNARK 需要证明这一点成立，并且更新的哈希值与更新的余额相匹配。

主要思想是发送者将使用其起始余额和交易价值作为秘密输入，并将起始余额、最终余额和价值的哈希值作为公开输入。类似地，接收者将使用起始余额和价值作为秘密输入，并将起始余额、最终余额和价值的哈希值作为公开输入。

下面是我们将用于发送方 zk-SNARK 的程序，其中与之前一样 $x$ 代表公开输入，并 $w$ 代表秘密输入。

function senderFunction(x, w) {
  return (
    w.senderBalanceBefore > w.value &&
    sha256(w.value) == x.hashValue &&
    sha256(w.senderBalanceBefore) == x.hashSenderBalanceBefore &&
    sha256(w.senderBalanceBefore - w.value) == x.hashSenderBalanceAfter
  )
}

接收方使用的程序如下：

function receiverFunction(x, w) {
  return (
    sha256(w.value) == x.hashValue &&
    sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore &&
    sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter
  )
}

程序检查发送余额是否大于发送的值，并检查所有哈希值是否匹配。一组值得信赖的人将为我们的 zk-SNARK 生成证明密钥和验证密钥，我们记它们为 confTxSenderPk、confTxSenderVk、confTxReceiverPk 和 confTxReceiverVk。

在代币合约中使用 zk-SNARK 看起来像这样：

function transfer(address _to, bytes32 hashValue, bytes32 hashSenderBalanceAfter, bytes32 hashReceiverBalanceAfter, bytes zkProofSender, bytes zkProofReceiver) {
  bytes32 hashSenderBalanceBefore = balanceHashes[msg.sender];
  bytes32 hashReceiverBalanceBefore = balanceHashes[_to];

  bool senderProofIsCorrect = zksnarkverify(confTxSenderVk, [hashSenderBalanceBefore, hashSenderBalanceAfter, hashValue], zkProofSender);

  bool receiverProofIsCorrect = zksnarkverify(confTxReceiverVk, [hashReceiverBalanceBefore, hashReceiverBalanceAfter, hashValue], zkProofReceiver);

  if(senderProofIsCorrect && receiverProofIsCorrect) {
    balanceHashes[msg.sender] = hashSenderBalanceAfter;
    balanceHashes[_to] = hashReceiverBalanceAfter;
  }
}

因此，区块链上的唯一更新是余额的哈希值，而不是余额本身。但是，我们可以知道所有余额都已正确更新，因为我们可以检查自己的证明是否已得到验证。

上述保密交易方案主要是为了给出一个实际的例子来说明如何在以太坊上使用 zk-SNARKs。为了创建一个基于此的强大的保密交易方案，我们还需要解决许多问题：

1. 用户需要在客户端跟踪他们的余额，如果丢失余额，这些代币将无法恢复。也许可以使用从签名密钥派生的密钥在链上加密存储余额。
   
2. 余额需要使用 32 字节的数据，并编码随机熵来防止通过反向哈希（如彩虹表攻击）来计算出余额。
   
3. 需要处理发送到未使用地址的边缘情况。
   
4. 发送者需要与接收者交互才能发送。人们可能有一个系统，其中发送者使用他们的证明来发起交易，而接收者可以在区块链上看到他们有一个“待处理的传入交易”并可以完成它。
   

本文不是原创，是一篇翻译文章，原文为：Introduction to zk-SNARKs with Examples ，推荐读者阅读原文。