通过 Tornado Cash 的源代码理解零知识证明

来源：https ://unsplash.com/photos/JrrWC7Qcmhs

根据维基百科，零知识证明（ZKP）的定义如下：

…零知识证明或零知识协议是一种方法，一方（证明者）可以向另一方（验证者）证明给定的陈述是真实的，而证明者避免传达任何额外的信息，除了事实之外说法确实属实。零知识证明的本质是：通过简单地揭示某个信息来证明一个人拥有某些信息的知识是微不足道的；挑战在于如何在不透露信息本身或任何其他信息的情况下证明这种拥有。

ZKP 技术可以广泛应用于许多不同的领域，如：匿名投票或匿名转账，这些领域在区块链等公共数据库上难以解决。

Tornado Cash是一种完全去中心化的非托管协议，您可以用它来匿名化您的以太坊交易。由于区块链的逻辑，每笔交易都是公开的。如果您的帐户中有一些 ETH，您是不能匿名转移的，因为任何人都可以在区块链上跟踪您的交易历史。像 Tornado Cash 这样的代币混合器可以通过使用 ZKP 打破源地址和目标地址之间的链上链接来解决这个隐私问题。

如果您想匿名化您的一笔交易，您必须在 Tornado Cash 合约上存入少量 ETH（或 ERC20 代币）（例如：1 ETH）。一段时间后，您就可以用其他账户提取这 1 个 ETH。诀窍在于，没有人可以在存款人账户和提款账户之间建立联系。如果数百个账户在一边存入1个ETH，而另外数百个账户在另一边提取1个ETH，那么没有人能够跟踪资金的移动路径。技术上的挑战是，智能合约交易也像以太坊网络上的其他交易一样是公开的。这也是ZKP将发挥作用的地方。

当您在合约上存入 1 个 ETH 时，您必须提供一个“承诺”。这个承诺是由智能合约存储的。当您在另一方提取1个ETH时，您必须提供一个 "nullifier "和一个零知识证明。空值是一个与承诺有关的唯一ID，而零知识证明则证明了这种联系，但没有人知道哪个空值是分配给哪个承诺的（除了储户/取款账户的所有者）。

再说一遍。我们可以证明其中一个承诺是分配给我们的nullifier的，而不透露我们的承诺。

nullifier由智能合约跟踪，所以我们只能用一个nullifier提取一个存入的ETH。

听起来很简单？其实不然！:) 让我们深入了解一下这个技术。但在这之前，我们必须了解另一个棘手的问题，即默克尔树（ Merkle tree）。

1. 什么是 Merkle tree ？

来源：https ://en.wikipedia.org/wiki/Merkle_tree

Merkle tree 是哈希树，叶子是元素，每个节点都是子节点的哈希。树的根是 Merkle 根，它代表整个元素集。如果您添加、删除或更改树中的任何元素（叶子），Merkle 根将会改变。Merkle 根是元素集的唯一标识符。

2. 如何使用Merkle tree 呢？

有一种叫做 Merkle 证明的东西。如果我有一个 Merkle 根，您可以给我发送一个 Merkle 证明，证明一个元素在根所代表的集合中。下图显示了它是如何工作的。如果您想向我证明 HK在集合中，您必须将HL, HIJ, HMNOP, 和HABCDEFGH哈希值发送给我。使用这些哈希值，我可以计算出 Merkle 根。如果这个根与我的根相同，那么HK就在这个集合中。

可以在哪里使用 Merkle tree呢？

如：白名单这样的简单例子。想象一下，一个智能合约有一个方法，只能由白名单的用户调用。问题是，有 1000 个白名单帐户。您如何将它们存储在智能合约中呢？简单的方法是将每个帐户都存储在映射中，但这样成本是非常高的。一个成本低的解决方案是构建一个 Merkle 树，并且只存储 Merkle 根（1 个哈希对 1000 个白名单账户）。如果有人想调用这个方法，她必须提供一个 Merkle 证明（在这种情况下，它是个10条哈希值的列表），可以很容易地被智能合约验证。

同样：Merkle树是用来表示一组有一个哈希值（Merkle根）的元素。一个元素的存在可以通过Merkle证明来证明。

零知识证明的工作原理

接下来我们要了解的是零知识证明本身。通过ZKP，您可以证明您知道的东西，而不透露您知道的东西。为了生成一个ZKP，您需要一个电路。电路是类似于一个小程序，它有公共输入和输出，以及私人输入。这些私人输入是您在验证时不透露的信息，这就是为什么它被称为零知识证明。使用 ZKP，我们可以证明输出可以从给定电路的输入中产生。

一个简单的电路如下所示：

pragma circom 2.0.0;

include "node_modules/circomlib/circuits/bitify.circom";
include "node_modules/circomlib/circuits/pedersen.circom";

template Main() {
   signal input nullifier;
   signal output nullifierHash;

   component nullifierHasher = Pedersen(248);
   component nullifierBits = Num2Bits(248);

   nullifierBits.in <== nullifier;
   for (var i = 0; i < 248; i++) {
       nullifierHasher.in[i] <== nullifierBits.out[i];
   }

   nullifierHash <== nullifierHasher.out[0];
}

component main = Main();

使用这个电路，我们可以证明我们知道给定哈希值的来源。这个电路有一个输入（nullifier）和一个输出（nullifier哈希值）。输入的默认可访问性是私有的，输出始终是公开的。这个电路使用 Circomlib 中的 2 个库。Circomlib是一组有用的电路。第一个库是bitlify，包含了比特操作方法，第二个库是pedersen，包含了Pedersen hasher。Pedersen hashing是一种可以在ZKP电路中有效运行的散列方法。在 Main 模板的主体中，我们填充哈希值并计算哈希值。（有关 circom 语言的更多信息，请查看circom 文档）

为了生成零知识证明，您需要一个证明密钥。这是 ZKP 最敏感的部分，因为使用用于生成证明密钥的源数据，任何人都可以生成假证明。这些源数据被称为必须丢弃的“有毒废物”。因此，有一个生成证明密钥的“仪式”。仪式有许多成员，每个成员都为证明钥匙做出贡献。只有一个非恶意的成员才足以产生一个有效的证明密钥。使用私有输入、公共输入和证明密钥，ZKP 系统才可以运行电路并生成证明和输出。

证明密钥有一个验证密钥，可以用来进行验证。验证系统使用公共输入、输出和验证密钥来验证证明。

Snarkjs是一个全功能的工具，通过仪式生成证明密钥和验证密钥，生成证明，并进行验证。它还可以生成用于验证的智能合约，该合约可以被任何其他合约用来验证零知识证明。更多信息，可查看snarkjs 相关文档。

Tornado Cash (TC) 的工作原理

现在，了解了以上知识，我们来看下 Tornado Cash (TC) 的工作原理。当您在 TC 合约上存入 1 ETH 时，您必须提供一个承诺哈希值。这个承诺哈希值将存储在 Merkle 树中。当您用不同的账户提取这 1 个 ETH 时，您必须提供 2 个零知识证明。第一个证明 Merkle 树包含您的承诺。这个证明是 Merkle 证明的零知识证明。但这还不够，因为您只被允许一次提取这 1 个 ETH 。因此，您必须提供一个对承诺来说是唯一的nullifier。合约会存储这个nullifier，这确保您不能多次提取存入的资金。

nullifier的唯一性是由承诺的生成方法来保证的。承诺是从nullifier和通过散列的Secret生成的。如果您改变了nullifier，那么承诺也会改变，所以一个nullifier只能用于一个承诺。由于散列的单向性，我们不可能将承诺和nullifier联系起来，但我们可以为它生成一个 ZKP。

说完理论，让我们来看看TC的提现电路是什么样子的：

include "../node_modules/circomlib/circuits/bitify.circom";
include "../node_modules/circomlib/circuits/pedersen.circom";
include "merkleTree.circom";// computes Pedersen(nullifier + secret)
template CommitmentHasher() {
   signal input nullifier;
   signal input secret;
   signal output commitment;
   signal output nullifierHash;    component commitmentHasher = Pedersen(496);
   component nullifierHasher = Pedersen(248);
   component nullifierBits = Num2Bits(248);
   component secretBits = Num2Bits(248);
   nullifierBits.in <== nullifier;
   secretBits.in <== secret;
   for (var i = 0; i < 248; i++) {
       nullifierHasher.in[i] <== nullifierBits.out[i];
       commitmentHasher.in[i] <== nullifierBits.out[i];
       commitmentHasher.in[i + 248] <== secretBits.out[i];
   }    commitment <== commitmentHasher.out[0];
   nullifierHash <== nullifierHasher.out[0];
}// Verifies that commitment that corresponds to given secret and nullifier is included in the merkle tree of deposits
template Withdraw(levels) {
   signal input root;
   signal input nullifierHash;
   signal private input nullifier;
   signal private input secret;
   signal private input pathElements[levels];
   signal private input pathIndices[levels];    component hasher = CommitmentHasher();
   hasher.nullifier <== nullifier;
   hasher.secret <== secret;
   hasher.nullifierHash === nullifierHash;    component tree = MerkleTreeChecker(levels);
   tree.leaf <== hasher.commitment;
   tree.root <== root;
   for (var i = 0; i < levels; i++) {
       tree.pathElements[i] <== pathElements[i];
       tree.pathIndices[i] <== pathIndices[i];
   }
}component main = Withdraw(20);

第一个模板是 CommitmentHasher。它有两个输入，nullifier 和 secret，它们是两个随机的 248 位数字。该模板计算 nullifier 哈希和承诺哈希，承诺哈希是nullifier 哈希和Secret哈希的哈希值，上文已提到过。

第二个模板是 Withdraw 本身。它有 2 个公共输入，Merkle 根和 nullifierHash。Merkle root需要用来验证Merkle证明，而nullifierHash则需要由智能合约来存储它。私有的输入参数是 nullifier、secret以及Merkle证明的 pathElements 和 pathIndices。电路通过从它和secret生成承诺来检查nullifier，并检查给定的 Merkle 证明。如果一切正常，就会生成零知识证明，可以通过 TC 智能合约进行验证。

您可以在 repo的contracts 文件夹中找到智能合约。验证器是从电路中生成的。Tornado 合约使用它来验证给定 nullifier 哈希和 Merkle 根的 ZKP。

使用合约最简单的方法是命令行界面。它是用 JavaScript 编写的，它的源代码比较简单。您可以轻松找到参数和 ZKP 的生成位置并用于调用智能合约。

零知识证明在加密世界中相对较新。它背后的数学非常复杂且难以理解，但像snarkjs和circom这样的工具使它更容易使用。

希望这篇文章能帮助您理解这项 "神奇 "的技术，并且您能在您的下一个项目中使用ZKP。

更多ZK信息

长按加入“zkpDAO”社群

微信公众号：zklog

twitter账号：@ZKLog