zksnark-tornado

eth

zk-snark

这里以介绍Tornado cash来简单看一下零知识证明。

Tornado 是以太坊链上的匿名转账协议，使用智能合约接受各用户的 ETH 存款起到混币功能，用户可以通过指定不同地址提币来实现匿名转账。实现主要是依托于零知识证明。

zk-snark

（是真的很难）

同态加密

如果加密函数E(x)满足加法同态性，由 img 可以推出，对于整数k，有img。

进而，对于一个多项式P(x)，如果加密函数E(x)满足加法同态性，那么有下式成立：

img

如果Alice持有这个多项式P(x)，将a0，a1,….an的系数给到Bob; Alice选择一个值s，将E(1)到E(s的n次方)的值给到Bob，Bob就能计算得出E(P(s))的值了，又E是加密算法，再解密就可得出P(s)的值。这样Alice既不会暴露s的值也不会暴露多项式P(x)。

到这为止我也还能理解，但接下来的实际问题如何套入上面的多项式的知识就超出了我的理解范围了…

V神有三篇文章解释了接下来的事

  1. Quadratic Arithmetic Programs: from Zero to Hero
  2. Exploring Elliptic Curve Pairings
  3. Zk-SNARKs: Under the Hood

关于实际问题到电路的转换，这篇图文介绍得很好。

简单使用

iden3提供了一整套开源工具来使用零知识证明。这里有简单的tutorial。简单说来，有以下的步骤

  • 编写circom，定义证明。circom将包含多个输入和多个输出，通过一些基本运算来书写输入和输出之间的约束，比如

    1
    2
    3
    4
    5
    6
    7
    template Multiplier() {
        signal private input a;
        signal private input b;
        signal output c;

        c <== a*b;
    }

    这样的话，约束就是输出c = 输入a*输入b。

  • 将circom编译为r1cs

  • 使用生成算法（G）为刚生成的r1cs生成 proving key (pk) 和 verification key (vk)； vk可交于验证人手中

  • 使用证明算法（P）生成 R1CS 可满足性的证明。proof = P(pk, out, x)，x指输入，如上例的a和b, out指输出，假设a和b选值为2，3，那么我知道c肯定为6，所以这里proof = P(pk, 6, 2, 3)

  • 对应使用 Verify 函数（V）验证证明。V(vk, out, proof) ?= true;

    验证人将手中的vk以及我再给他的out（6）和生成的 proof带入验证函数，就能进行校验。这里的意思是，验证人并不知道2，3（a b）的值，也不知道具体的约束，但能验证结果。

    （这里我理解到的是，如果带入上面同态加密，假设vk是a0到an的系数，proof是一系列E的值，out是P(x)的值，这样验证人就能根据proof校验out的正确性, 且他不知道多项式具体的组成以及不知道x的选值）

文档

  • Circom 基本语法和入门文档
  • circom lib 提供了一些常用的circom，如merkle tree, hash，等等

Tornado

试想一下，如果要达到”洗钱”的功能，

  • 第一，肯定要提供存钱和取钱的方法，但是如何判断取钱的权限呢，为了隐私，不能由地址(私钥所有)来作为权限
  • 存钱的时候，附加一个信息的hash值，取钱的时候使用zksnark证明拥有原信息，

我们先就这个hash的零知识证明看下代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// in circom
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];
}

两个输入nullifier和secret，输出是commitment和nullifierHash

采用的hash函数是Pedersen，这个hash函数的文档👈

nullifierHash是nullifier的hash结果，commitment是nullifier + secret的hash结果。

编译circom产生r1cs后，再使用生成函数，产生 proving key (pk) 和 verification key (vk), 将vk设置到合约中用以验证时使用。

用户存钱的时候，生成nullifier和secret，和对应hash，commitment和nullifierHash，假设将commitment提交到合约中；

使用这4个值再生成proof，取钱的时候，将proof和nullifierHash提交，在合约中完成验证。

这里有一个疑问是，为什么要使用两个hash值呢，使用一个进行证明不就好了？

按照前面的推论，存钱的交易中带有output的信息，然后取的时候再带有output信息的话，就会让这个钱又变得可定向了(通过筛选交易的字段即可)。

那单单是现在这样，还不能实现钱不可定向。所以还需要增加一个实现，便是merkle树的证明。加入merkle树后的代码便是下面这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
template Withdraw(levels) {
    signal input root;
    signal input nullifierHash;
    signal input recipient; // not taking part in any computations
    signal input relayer;  // not taking part in any computations
    signal input fee;      // not taking part in any computations
    signal input refund;   // not taking part in any computations
    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];
    }

    // Add hidden signals to make sure that tampering with recipient or fee will invalidate the snark proof
    // Most likely it is not required, but it's better to stay on the safe side and it only takes 2 constraints
    // Squares are used to prevent optimizer from removing those constraints
    signal recipientSquare;
    signal feeSquare;
    signal relayerSquare;
    signal refundSquare;
    recipientSquare <== recipient * recipient;
    feeSquare <== fee * fee;
    relayerSquare <== relayer * relayer;
    refundSquare <== refund * refund;
}

根据在取钱进行证明的时候，只需提供生成的证明，和公开的input参数即可完成证明。

要确定取钱的这个证明的确是存过钱的，是通过这个root，在合约中约定这个root是所有存款的merkle root。

合约中的代码大致是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//存钱
function deposit(bytes32 _commitment) external payable nonReentrant {
   require(!commitments[_commitment], "The commitment has been submitted");
	//向merkle树中插入叶子节点，计算出新的root, 产生过的root存储于一个数组中
   uint32 insertedIndex = _insert(_commitment);
   commitments[_commitment] = true;
   _processDeposit();

   emit Deposit(_commitment, insertedIndex, block.timestamp);
 }
 
 //取钱
   function withdraw(bytes calldata _proof, bytes32 _root, bytes32 _nullifierHash, address payable _recipient, address payable _relayer, uint256 _fee, uint256 _refund) external payable nonReentrant {
   require(_fee <= denomination, "Fee exceeds transfer value");
   require(!nullifierHashes[_nullifierHash], "The note has been already spent");
   //选择参与证明的root的确是存储在链上数组中的
   require(isKnownRoot(_root), "Cannot find your merkle root"); // Make sure to use a recent one
   require(verifier.verifyProof(_proof, [uint256(_root), uint256(_nullifierHash), uint256(_recipient), uint256(_relayer), _fee, _refund]), "Invalid withdraw proof");

   nullifierHashes[_nullifierHash] = true;
   _processWithdraw(_recipient, _relayer, _fee, _refund);
   emit Withdrawal(_recipient, _nullifierHash, _relayer, _fee);
 }

延伸一下

基于zk-snark的layer2实现，可以看看zksync，这个团队还提供了一个新的编程语言，Zinc。希望我不久之后能完成这个项目的学习。