Ethereum上的隐私保护协议（混币+零知识证明）

https://github.dev/tornadocash/tornado-core

Protocol description

  • deposit

    Tornado.sol

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    function deposit(bytes32 _commitment) external payable nonReentrant {
        require(!commitments[_commitment], "The commitment has been submitted");
        
        uint32 insertedIndex = _insert(_commitment);
        commitments[_commitment] = true;
        _processDeposit();

        emit Deposit(_commitment, insertedIndex, block.timestamp);
    }

    /** @dev this function is defined in a child contract */
    function _processDeposit() internal virtual;

    ERC20Tornado.sol

    1
    2
    3
    function _processDeposit() internal override {
        require(msg.value == denomination, "Please send `mixDenomination` ETH along with transaction");
    }

  • withdraw

    deposit每次调用后，合约都会更新Merkle Tree的root，且会存储一定数量(ROOT_HISTORY_SIZE)的历史root。

    • 选择合约中存储的其中一个历史root \(R\)，并计算要withdraw的叶节点对应的Merkle opening \(O\)（该节点到根路径上的所有sister nodes的value以及位置（left/right））。

    • 计算nullifier hash \(h=H_1(k)\)。

    • 计算零知识证明值\(P\)：

      \(ZKPoK\{(k,r,O):h=H_1(k)\and O\ is\ the\ Merkle\ opening\ of\ H_1(k||r)\ of\ root\ R\}\)

    • 调用withdraw ，参数为\(R,h,P\)，以及提取地址等必要字段。

    • 若\(R\)在合约历史列表中，且对零知识证明作校验合法后，向提取地址转账固定金额，并将nullifier hash存入列表（避免双花）。

      [Question] 用户在withdraw时，需要根据此时的历史root之一对应的Merkle Tree叶节点计算path，但合约MerkleTreeWithHistory中仅存储最新叶节点到根路径上的值。需要链下扫描所有历史deposit交易插入的叶节点再构建树？（除非deposit后马上withdraw，且中间无其他deposit提前被接受）

    Tornado.sol

    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
    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");
        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);
    }

    /** @dev this function is defined in a child contract */
    function _processWithdraw(
        address payable _recipient,
        address payable _relayer,
        uint256 _fee,
        uint256 _refund
    ) internal virtual;

Circuits detail

  • merkleTree.circom

    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
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    include "../node_modules/circomlib/circuits/mimcsponge.circom";

    // Computes MiMC([left, right])
    template HashLeftRight() {
        signal input left;
        signal input right;
        signal output hash;

        component hasher = MiMCSponge(2, 1);
        hasher.ins[0] <== left;
        hasher.ins[1] <== right;
        hasher.k <== 0;
        hash <== hasher.outs[0];
    }

    // if s == 0 returns [in[0], in[1]]
    // if s == 1 returns [in[1], in[0]]
    template DualMux() {
        signal input in[2];
        signal input s;
        signal output out[2];

        s * (1 - s) === 0
        out[0] <== (in[1] - in[0])*s + in[0];
        out[1] <== (in[0] - in[1])*s + in[1];
    }

    // Verifies that merkle proof is correct for given merkle root and a leaf
    // pathIndices input is an array of 0/1 selectors telling whether given pathElement is on the left or right side of merkle path
    template MerkleTreeChecker(levels) {
        signal input leaf;
        signal input root;
        signal input pathElements[levels];
        signal input pathIndices[levels];

        component selectors[levels];
        component hashers[levels];

        for (var i = 0; i < levels; i++) {
            selectors[i] = DualMux();
            selectors[i].in[0] <== i == 0 ? leaf : hashers[i - 1].hash;
            selectors[i].in[1] <== pathElements[i];
            selectors[i].s <== pathIndices[i];

            hashers[i] = HashLeftRight();
            hashers[i].left <== selectors[i].out[0];
            hashers[i].right <== selectors[i].out[1];
        }

        root === hashers[levels - 1].hash;
    }

    MiMC是snark-friendly hash function（https://blog.csdn.net/mutourend/article/details/118157053）

  • withdraw.circom

    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
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    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 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;
    }

    component main = Withdraw(20);

About circom

定义在Baby Jubjub曲线上，适用于Pedersen Hash等底层的计算

如果需要换其他曲线（相应安全参数也随之变化），则可能需要进行GLOBAL_FIELD_P的替换