零知識證明： Tornado Cash 項目學習

前言

最近在了解零知識證明方面的內容，這方面的內容確實不好入門也不好掌握，在了解了一些基礎的概念以后，決定選擇一個應用了零知識證明的項目來進行進一步的學習。最終選擇了 Tornado Cash 這個項目，因為它著名且精致，適合入門的同學進行學習。

學習 Tornado Cash 項目，涉及以下方面：

了解項目功能與特性
了解項目智能合約實現
了解項目零知識證明部分實現

合約地址：https://etherscan.io/address/0x910cbd523d972eb0a6f4cae4618ad62622b39dbf#code

項目概覽

Tornado Cash 項目的主要功能是代幣混淆。由于區塊鏈上所有的交易都是公開的，所有人都可以通過分析交易的內容來得知在這筆交易中，代幣從哪些地址流向了哪些地址。而當你希望把你的代幣從賬戶 A 轉移到賬戶 B ，但是又不想被人分析出這兩個賬戶之間存在著轉賬關系，這個時候你就需要用到 Tornado Cash （下稱 tornado）的代幣混淆功能。

Tornado的主要業務流程：

用戶根據存款金額選擇對應的匿名池，并將資金發送到智能合約。合約會在不暴露取款憑證的前提下記錄這筆存款操作。然后存款資金會在匿名池中與其他來源的資金混合。最后，用戶提供取款憑證，通過零知識證明的校驗，匿名池會將代幣發送給指定的地址。這樣就完成了一次代幣混淆了。

存款頁面

取款憑證

tornado-eth-0.1-1-0xa6096ebb820ba1023314df16bd79f5c739187108fac1c9be3f7d1537c596890e2ecf4cedba0cd59b5a53414ce48e26d540664ee66d2dc015d03333e118b6

提款頁面

取款憑證所包含的信息

從 Tornado UI 代碼中可以得知，當用戶點擊提款按鈕時，將調用 onWithdraw 方法，該方法處理提款憑證的提交。

根據下面的代碼流程，可以追溯到 note 的解析方法

components/withdraw/Withdraw.vue -> store/application.js -> utils/crypto.js

根據下面的代碼，可以得知取款憑證被解析成以下內容

tornado(_) - 標識這是一個 Tornado Cash 的提款憑證。
eth(currency) - 加密貨幣的類型，這里是以太坊（ETH）。
0.1(amount) - 存款或提款的金額，這里是 0.1 ETH。
1(netId) - 網絡ID，指示該憑證適用于哪個網絡，如以太坊主網、Ropsten測試網等。
0xa609...e118b6(hexNote) - 加密的十六進制字符串，長度為 62 字節，是 nullifier 和 secret 的串聯。

const CUT_LENGTH = 31

export function parseNote(note) {
  const [, currency, amount, netId, hexNote] = note.split('-')

  return {
    ...parseHexNote(hexNote),
    netId,
    amount,
    currency
  }
}

export function parseHexNote(hexNote) {
  const buffNote = Buffer.from(hexNote.slice(2), 'hex')

  const commitment = buffPedersenHash(buffNote)

  const nullifierBuff = buffNote.slice(0, CUT_LENGTH)
  const nullifierHash = BigInt(buffPedersenHash(nullifierBuff))
  const nullifier = BigInt(leInt2Buff(buffNote.slice(0, CUT_LENGTH)))

  const secret = BigInt(leInt2Buff(buffNote.slice(CUT_LENGTH, CUT_LENGTH * 2)))

  return {
    secret,
    nullifier,
    commitment,
    nullifierBuff,
    nullifierHash,
    commitmentHex: toFixedHex(commitment),
    nullifierHex: toFixedHex(nullifierHash)
  }
}

取款憑證的原像是兩個值 ( nullifier + secret ) 的串聯，產生長度為 62 字節的消息，前 31 字節為 Nullifier，后 31 字節為 Secret。

為什么是 31 個字節而不是 32 個字節？

從文檔得知，采用的是 Baby Jubjub 橢圓曲線，該曲線在有限域 r = 21888242871839275222246405745257275088548364400416034343698204186575808495617 上。采用 31 字節的數字是為了能夠使得所選擇的 Nullifier 和 Secret 值都在有限域 r 內。

>>> 2 ** 248 < 21888242871839275222246405745257275088548364400416034343698204186575808495617
True
>>> 2 ** 256 < 21888242871839275222246405745257275088548364400416034343698204186575808495617
False

代碼總覽

整個 Tornado Cash 項目的核心代碼主要分為智能合約和約束電路兩部分。主要的業務邏輯包括存款和取款兩個部分。

智能合約：https://github.com/tornadocash/tornado-core/tree/master/contracts
約束電路：https://github.com/tornadocash/tornado-core/tree/master/circuits

其中，存款部分與智能合約部分的業務邏輯相關，而取款部分與智能合約和約束電路兩部分相關。

存款業務代碼分析

Tornado 采用了一個高度 32 的默克爾樹（Merkle tree）的葉子結點來存儲存款信息，存儲的最大數據量為 2 ** 32 。

調用 Tornado.deposit 函數進行存款，其中 _commitment 參數為兩個秘密值拼接以后的哈希（_commitment = hash(nullifier | secret) ）。

檢查 _commitment 是否已經被使用了；
調用 _insert 函數把 _commitment 插入到樹的葉子節點；
標記 _commitment 已經被使用了；
檢查轉入金額是否滿足。

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

兩種路徑進行存款：

通過 Dap：參數由 Dapp 給你生成
直接調用智能合約：參數自己準備

這部分的代碼邏輯比較簡單，整個 Tornado 合約精妙的內容是在默克爾樹的處理上，接下來我們進入到 MerkleTreeWithHistory 合約來進一步了解。

全局變量

在了解 MerkleTreeWithHistory 合約的業務邏輯之前，先來看一下它定義的全局變量。為了節省計算與存儲成本，Tornado 采用了許多優化策略。下面的全局變量會在各個策略中使用，每個變量的含義如下：

// Baby Jubjub 橢圓曲線的有限域
// 同時也被應用在 MiMC 算法中，令所有輸入輸出值都需要進行 mod FIELD_SIZE 處理以確保落在有限域內。
uint256 public constant FIELD_SIZE = 21888242871839275222246405745257275088548364400416034343698204186575808495617;

// keccak256("tornado") % FIELD_SIZE 的值，用作填充未被使用的葉子節點。
uint256 public constant ZERO_VALUE = 21663839004416932945382355908790599225266501822907911457504978515578255421292;

// MIMC 哈希的實現合約，用字節碼編寫而成，沒有 solidity 代碼
IHasher public immutable hasher;

// 默克爾樹樹的高度，取值范圍 (0, 32)
uint32 public levels;

// Merkle 樹每個層級中最新更新的全使用的子樹根節點，(層級 => 哈希值)。
mapping(uint256 => bytes32) public filledSubtrees;

// 每次更新后 Merkle 樹根的值
mapping(uint256 => bytes32) public roots;

// 可以存儲的最大樹根數量，避免存儲過多的歷史信息
uint32 public constant ROOT_HISTORY_SIZE = 30;

// 當前 Merkle 樹根的值，代表處于 (currentRootIndex / ROOT_HISTORY_SIZE) 的位置。
uint32 public currentRootIndex = 0;

// 下一個更新的葉子節點索引
uint32 public nextIndex = 0;

zeros() 預先計算空子樹根節點的值

在 zeros 函數中，已經提前計算好了高度為 i 的每個空子樹的根節點值。因為空葉子節點的值是固定的，所以可以提前計算出每個高度中，所有葉子節點都為空節點的子樹的根。這樣做可以節省大量的計算過程。

/// @dev provides Zero (Empty) elements for a MiMC MerkleTree. Up to 32 levels
function zeros(uint256 i) public pure returns (bytes32) {
  if (i == 0) return bytes32(0x2fe54c60d3acabf3343a35b6eba15db4821b340f76e741e2249685ed4899af6c);
  else if (i == 1) return bytes32(0x256a6135777eee2fd26f54b8b7037a25439d5235caee224154186d2b8a52e31d);
  else if (i == 2) return bytes32(0x1151949895e82ab19924de92c40a3d6f7bcb60d92b00504b8199613683f0c200);
  else if (i == 3) return bytes32(0x20121ee811489ff8d61f09fb89e313f14959a0f28bb428a20dba6b0b068b3bdb);
  else if (i == 4) return bytes32(0x0a89ca6ffa14cc462cfedb842c30ed221a50a3d6bf022a6a57dc82ab24c157c9);
  else if (i == 5) return bytes32(0x24ca05c2b5cd42e890d6be94c68d0689f4f21c9cec9c0f13fe41d566dfb54959);
  else if (i == 6) return bytes32(0x1ccb97c932565a92c60156bdba2d08f3bf1377464e025cee765679e604a7315c);
  else if (i == 7) return bytes32(0x19156fbd7d1a8bf5cba8909367de1b624534ebab4f0f79e003bccdd1b182bdb4);
  else if (i == 8) return bytes32(0x261af8c1f0912e465744641409f622d466c3920ac6e5ff37e36604cb11dfff80);
  else if (i == 9) return bytes32(0x0058459724ff6ca5a1652fcbc3e82b93895cf08e975b19beab3f54c217d1c007);
  else if (i == 10) return bytes32(0x1f04ef20dee48d39984d8eabe768a70eafa6310ad20849d4573c3c40c2ad1e30);
  else if (i == 11) return bytes32(0x1bea3dec5dab51567ce7e200a30f7ba6d4276aeaa53e2686f962a46c66d511e5);
  else if (i == 12) return bytes32(0x0ee0f941e2da4b9e31c3ca97a40d8fa9ce68d97c084177071b3cb46cd3372f0f);
  else if (i == 13) return bytes32(0x1ca9503e8935884501bbaf20be14eb4c46b89772c97b96e3b2ebf3a36a948bbd);
  else if (i == 14) return bytes32(0x133a80e30697cd55d8f7d4b0965b7be24057ba5dc3da898ee2187232446cb108);
  else if (i == 15) return bytes32(0x13e6d8fc88839ed76e182c2a779af5b2c0da9dd18c90427a644f7e148a6253b6);
  else if (i == 16) return bytes32(0x1eb16b057a477f4bc8f572ea6bee39561098f78f15bfb3699dcbb7bd8db61854);
  else if (i == 17) return bytes32(0x0da2cb16a1ceaabf1c16b838f7a9e3f2a3a3088d9e0a6debaa748114620696ea);
  else if (i == 18) return bytes32(0x24a3b3d822420b14b5d8cb6c28a574f01e98ea9e940551d2ebd75cee12649f9d);
  else if (i == 19) return bytes32(0x198622acbd783d1b0d9064105b1fc8e4d8889de95c4c519b3f635809fe6afc05);
  else if (i == 20) return bytes32(0x29d7ed391256ccc3ea596c86e933b89ff339d25ea8ddced975ae2fe30b5296d4);
  else if (i == 21) return bytes32(0x19be59f2f0413ce78c0c3703a3a5451b1d7f39629fa33abd11548a76065b2967);
  else if (i == 22) return bytes32(0x1ff3f61797e538b70e619310d33f2a063e7eb59104e112e95738da1254dc3453);
  else if (i == 23) return bytes32(0x10c16ae9959cf8358980d9dd9616e48228737310a10e2b6b731c1a548f036c48);
  else if (i == 24) return bytes32(0x0ba433a63174a90ac20992e75e3095496812b652685b5e1a2eae0b1bf4e8fcd1);
  else if (i == 25) return bytes32(0x019ddb9df2bc98d987d0dfeca9d2b643deafab8f7036562e627c3667266a044c);
  else if (i == 26) return bytes32(0x2d3c88b23175c5a5565db928414c66d1912b11acf974b2e644caaac04739ce99);
  else if (i == 27) return bytes32(0x2eab55f6ae4e66e32c5189eed5c470840863445760f5ed7e7b69b2a62600f354);
  else if (i == 28) return bytes32(0x002df37a2642621802383cf952bf4dd1f32e05433beeb1fd41031fb7eace979d);
  else if (i == 29) return bytes32(0x104aeb41435db66c3e62feccc1d6f5d98d0a0ed75d1374db457cf462e3a1f427);
  else if (i == 30) return bytes32(0x1f3c6fd858e9a7d4b0d1f38e256a09d81d5a5e3c963987e2d4b814cfab7c6ebb);
  else if (i == 31) return bytes32(0x2c7a07d20dff79d01fecedc1134284a8d08436606c93693b67e333f671bf69cc);
  else revert("Index out of bounds");
}

比如，要插入 N00 節點時，需要更新默克爾樹的根節點值，只需要在計算 N11 節點時獲取 zeros(0) 的值來進行構建，然后在計算 root 的值時獲取 zeros(1) 的值即可完成根節點的更新。

filledSubtrees 不是存放全被使用的子樹根節點嗎？

當 filledSubtrees[i] 被記錄的時候是作為每個層級中最新更新的子樹根節點，進行記錄。被記錄到 filledSubtrees 映射的時候該子樹未必所有葉子節點都被使用了。

而只有當 filledSubtrees[i] 成為了當前層級所有葉子節點都被使用了的子樹所對應的子樹根時，它才會被使用。

請看案例：

當插入 N00 節點時，filledSubtrees[1] 的值將會更新，但此時它對應的子樹 N11 還不是一個全部填充的子樹。

而當插入了 N01 時，filledSubtrees[1] 的值會被更新為 N11 的值。

然后插入 N02 ， filledSubtrees[1] 的值將會被使用，此時它對應的子樹已經是一個完全填充的子樹了。

MerkleTreeWithHistory._insert() 函數插入葉子節點

MerkleTreeWithHistory._insert 函數

首先獲取下一個插入的葉子結點索引，確保 Merkle 樹未滿，可以執行插入操作。
然后遍歷更新 Merkle 樹每一層相關的節點
1. 如果 currentIndex 是偶數，表示當前更新的節點為左節點，將當前哈希值存為左子節點，并將對應層級的默認右子節點（zero value）取出。（由于葉子節點插入是從左到右，所以當更新的節點為左節點時，右節點為空子樹）。將第 i 層的 filledSubtrees 記錄為當前哈希值。
2. 如果 currentIndex 是奇數，表示當前更新的節點為右節點，將左子節點（之前存儲在 filledSubtrees 中的）和當前哈希值組合。（更新的節點為右節點，意味著對應的左節點已經是完全使用的狀態）
3. 使用 hashLeftRight 函數計算當前層的新哈希值。
4. currentIndex 通過除以 2 得到父節點屬于左子節點還是右子節點。
計算新的 root 索引，使用循環數組的方式避免超出 ROOT_HISTORY_SIZE。
更新 currentRootIndex。
把新的跟哈希存放在 roots[newRootIndex] 中。
更新 nextIndex
返回當前的葉子節點索引。

function _insert(bytes32 _leaf) internal returns (uint32 index) {
  uint32 _nextIndex = nextIndex;
  require(_nextIndex != uint32(2)**levels, "Merkle tree is full. No more leaves can be added");
  uint32 currentIndex = _nextIndex;
  bytes32 currentLevelHash = _leaf;
  bytes32 left;
  bytes32 right;

  for (uint32 i = 0; i < levels; i++) {
    if (currentIndex % 2 == 0) {
      left = currentLevelHash;
      right = zeros(i);
      filledSubtrees[i] = currentLevelHash;
    } else {
      left = filledSubtrees[i];
      right = currentLevelHash;
    }
    currentLevelHash = hashLeftRight(hasher, left, right);
    currentIndex /= 2;
  }

  uint32 newRootIndex = (currentRootIndex + 1) % ROOT_HISTORY_SIZE;
  currentRootIndex = newRootIndex;
  roots[newRootIndex] = currentLevelHash;
  nextIndex = _nextIndex + 1;
  return _nextIndex;
}

MiMC 哈希函數

hashLeftRight 函數使用 MiMC 哈希算法對兩個樹葉節點進行哈希。其中 _hasher 合約對應的是 Hasher.sol 。由于 MiMC 算法是由字節碼編寫的（甚至都不是用內聯匯編寫的），所以在 etherscan 上的是沒有驗證的狀態。為什么不用內聯匯編實現，開發者給的原因是：內聯匯編不允許使用指令對堆棧進行操作。

MiMC 哈希算法：https://byt3bit.github.io/primesym/mimc/

MiMCSponge(R, C) 函數中

輸入： R 是被哈希的信息，C 是輪常數。
輸出： R 是哈希后的信息，C 是更新后的輪常數。

在對左葉子節點進行了第一次哈希操作后，需要對返回值進行相加取模操作 R = addmod(R, uint256(_right), FIELD_SIZE); ，以確保結果落在 FIELD_SIZE 范圍內，以便將其作為輸入再次進行哈希操作。

function hashLeftRight(
  IHasher _hasher,
  bytes32 _left,
  bytes32 _right
) public pure returns (bytes32) {
  require(uint256(_left) < FIELD_SIZE, "_left should be inside the field");
  require(uint256(_right) < FIELD_SIZE, "_right should be inside the field");
  uint256 R = uint256(_left);
  uint256 C = 0;
  (R, C) = _hasher.MiMCSponge(R, C);
  R = addmod(R, uint256(_right), FIELD_SIZE);
  (R, C) = _hasher.MiMCSponge(R, C);
  return bytes32(R);
}

在查找資料的過程中，發現了一個用 solidity 實現的 MiMC 算法，不知道是否和 Tornado 用字節碼編寫的算法版本細節一致，但是出于學習的目的可以對 solidity 版本的算法進行分享。

MiMC Solidity：https://gist.github.com/poma/5adb51d49057d0a0edad2cbd12945ac4#file-mimc-sol

整個算法主要由 220 輪的運算組成，每輪運算細節如下：

t 等于 xL 加上一個常數（注意這個常數每輪都不一樣）取模
xR 等于上一輪的 xL
xL 等于上一輪的 xR 加上 t 五次方取模

pragma solidity ^0.5.8;

contract MiMC {
  uint constant FIELD_SIZE = 21888242871839275222246405745257275088548364400416034343698204186575808495617;

  function MiMCSponge(uint256 xL, uint256 xR) public pure returns (uint256, uint256) {
    uint exp;
    uint t;
    uint xR_tmp;
    t = xL;
    exp = mulmod(t, t, FIELD_SIZE);
    exp = mulmod(exp, exp, FIELD_SIZE);
    exp = mulmod(exp, t, FIELD_SIZE);
    xR_tmp = xR;
    xR = xL;
    xL = addmod(xR_tmp, exp, FIELD_SIZE);

    t = addmod(xL, 7120861356467848435263064379192047478074060781135320967663101236819528304084, FIELD_SIZE);
    exp = mulmod(t, t, FIELD_SIZE);
    exp = mulmod(exp, exp, FIELD_SIZE);
    exp = mulmod(exp, t, FIELD_SIZE);
    xR_tmp = xR;
    xR = xL;
    xL = addmod(xR_tmp, exp, FIELD_SIZE);

    ...
    // totally 220 rounds
    ...

    t = xL;
    exp = mulmod(t, t, FIELD_SIZE);
    exp = mulmod(exp, exp, FIELD_SIZE);
    exp = mulmod(exp, t, FIELD_SIZE);
    xR = addmod(xR, exp, FIELD_SIZE);

    return (xL, xR);
  }

  function hashLeftRight(uint256 _left, uint256 _right) public pure returns (uint256) {
    uint256 R = _left;
    uint256 C = 0;
    (R, C) = MiMCSponge(R, C);
    R = addmod(R, uint256(_right), FIELD_SIZE);
    (R, C) = MiMCSponge(R, C);
    return R;
  }
}

取款業務代碼分析

當用戶需要進行取款操作時，先向 Dapp 提供存款時獲得的 note，再由 Dapp 補充一些相關的公共數據作為輸入參數，然后就可以調用智能合約進行取款操作了。

整個 withdraw 函數接收了一系列的參數，對參數進行了檢查后，調用 verifier.verifyProof 函數檢驗零知識證明的有效性（重點）。隨后記錄這筆取款，向收款地址發送取款金額。

為了文章的連貫性，參數檢查部分將會在后面展開介紹

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

首先來看一下輸入參數：

_proof：一個 zk-SNARKs 證明，用于驗證與提款請求相關的所有條件和數據都是有效的
_root：Merkle 樹的根哈希值
_nullifierHash：防止雙重支付的標識符，當存款被提取時對應的 nullifier 將被標記為已使用
_recipient：接收資金的地址
_relayer：中繼者地址，代替用戶進行合約交互
_fee：給中繼者的費用
_refund：交易的實際成本低于預支付的金額時，將退還給 _recipient 的金額

可以看到這些輸入參數都在 verifier.verifyProof 函數被使用到，verifier 合約是根據約束電路生成的，用來驗證零知識證明有效性的合約。由于他是根據約束電路生成的，所以其合約的具體實現我們不必深究，我們將重點放在約束電路的實現上。

通過閱讀 withdraw.circom 的代碼可以得知，其中 _proof 參數作為約束證明，而剩余的 6 個參數作為公共輸入參與驗證。

剩下的四個隱私輸入，都可以通過 note 解析出來：

nullifier：note 的前 31 個字節
secret：note 的后 31 個字節
pathElements[levels]：驗證（nullifier + secret）為 Mercle 樹中的子節點所對應的 proof path
pathIndices[levels]：pathElements[levels] 中每個節點作為左子節點還是右子節點的標志位

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];

    ...

}

首先定義的了一個 CommitmentHasher() 組件 hasher，其主要的功能就是哈希運算，根據輸入的 nullifier 和 secret，計算并輸入 nullifierHash 和 commitment 。約束計算得到的 hasher.nullifierHash 和用戶輸入的 nullifierHash 需要是相等的。

    component hasher = CommitmentHasher();
    hasher.nullifier <== nullifier;
    hasher.secret <== secret;
    hasher.nullifierHash === nullifierHash;

然后定義的了一個 MerkleTreeChecker() 組件 tree，用作驗證 hasher.commitment 是否為以 root 為根的 Merkle 樹中的一個葉子節點。

    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];
    }

最后這部分代碼，通過計算 recipient, relayer, fee, refund 的平方，間接地將這些值納入到電路的約束中。這樣做的目的，是為了將 Tornado.withdraw 函數中的輸入 proof 和剩余的輸入對應起來，避免了交易信息廣播后，攻擊者獲取了 proof 以后將 recipient 等參數替換成自己的地址進行搶跑操作。將下列參數寫進電路約束中后，一但 recipient, relayer, fee, refund 的值發生了改變，那么對應的 proof 也會改變，從而避免了在合約調用層面篡改參數的問題。

    signal recipientSquare;
    signal feeSquare;
    signal relayerSquare;
    signal refundSquare;
    recipientSquare <== recipient * recipient;
    feeSquare <== fee * fee;
    relayerSquare <== relayer * relayer;
    refundSquare <== refund * refund;

`MerkleTreeChecker` 函數檢查

進入到 merkleTree.MerkleTreeChecker 函數，這個函數的功能就是約束 leaf 作為 root 的一個葉子結點。其中 DualMux() 函數的作用就是根據標志位 s 來決定 in[0] 和 in[1] 誰作為左子樹誰作為右子樹。

在決定了左右子樹以后，將它們傳入到 HashLeftRight() 函數中進行哈希操作，輸出 hash。不斷地進行循環計算，并將最終結果和 root 參數進行約束 root === hashers[levels - 1].hash; ，確保兩個值相等。

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

DualMux() 函數的巧思

DualMux 函數是一個功能簡單，但是有點巧思的函數，可以和大家分享一下。

首先是 s * (1 - s) === 0 約束，它限制了 s 的值只能是 0 或 1。

其次是輸出的表達形式 out[0] <== (in[1] - in[0])*s + in[0];，這個寫法不需要使用條件分支（if … else …），通過使用代數表達式來實現這種動態選擇。

當 s = 0 時，(in[1] - in[0]) * 0 + in[0] = 0 + in[0] = in[0]，因此 out[0] = in[0]。
當 s = 1 時，(in[1] - in[0]) * 1 + in[0] = (in[1] - in[0]) + in[0] = in[1]，因此 out[0] = in[1]。

// 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];
}

為什么 note 要采用 nullifier + secret 的形式

Tornado Cash 作為一個混幣器，其功能是隱藏存款者與取款者之間的聯系。采用 nullifier + secret 的形式來構成取款憑證 note 是為了防止多次重復取款的同時保護取款者身份不被泄露。

首先考慮只用 secret 的場景：

用戶存款，生成 secret 值，并將其哈希值插入到 Merkle 樹中；
用戶取款，提供 secret 值對應的哈希進行驗證；
驗證通過，取款；
將改哈希值對應的取款狀態置位 true，防止重復取款。

經過第 4 步操作后，取款者的身份和 secret 哈希對應上了，而 secret 哈希又和存款者的身份是對應的。這樣就使得存款者和取款者聯系上了，徹底暴露了資金鏈兩端的聯系。

采用 nullifier + secret 的形式可以解決上述的問題

用戶存款，生成 nullifier + secret 值，并將其哈希值插入到 Merkle 樹中；
用戶取款，提供 hash(nullifier) 以及包含 nullifier 和 secret 的 proof 證明；
驗證 proof
1. 驗證 hash(nullifier) 和 proof 中的 hasher.nullifierHash 是否相等
2. 驗證 proof 證明中的 hash(nullifier + secret) 是否為 Merkle 樹的葉子結點
將 hash(nullifier) 對應的取款狀態置位 true，防止重復取款。

通過這種形式，用戶只需要暴露 hash(nullifier) 的值，其他人無法將 hash(nullifier) 和任意葉子節點 hash(nullifier + secret) 聯

isKnownRoot() 函數檢查 root 是否還有時效性

在 withdraw 函數中，會通過 isKnownRoot 函數對傳入的根 _root 進行檢查

require(isKnownRoot(_root), "Cannot find your merkle root"); // Make sure to use a recent one

在這個函數中，會使用到之前提到的全局變量

// 每次更新后 Merkle 樹根的值
mapping(uint256 => bytes32) public roots;

// 可以存儲的最大樹根數量，避免存儲過多的歷史信息
uint32 public constant ROOT_HISTORY_SIZE = 30;

// 當前 Merkle 樹根的值，代表處于 (currentRootIndex / ROOT_HISTORY_SIZE) 的位置。
uint32 public currentRootIndex = 0;

這個函數的功能就是檢查傳入的 _root 參數是否為 roots[] 中存儲的最近的 ROOT_HISTORY_SIZE 個根。roots[] 和 ROOT_HISTORY_SIZE 配合使用，實現了一個長度為 30 的循環數組，當前根的索引值為 currentRootIndex。

function isKnownRoot(bytes32 _root) public view returns (bool) {
  if (_root == 0) {
    return false;
  }
  uint32 _currentRootIndex = currentRootIndex;
  uint32 i = _currentRootIndex;
  do {
    if (_root == roots[i]) {
      return true;
    }
    if (i == 0) {
      i = ROOT_HISTORY_SIZE;
    }
    i--;
  } while (i != _currentRootIndex);
  return false;
}

采取這個方案的好處：

避免了存儲過多的歷史根值，縮小了檢索的范圍。
采用最近的 30 個根值也能夠避免當一個用戶 A 生成了 proof 到調用合約取款這個時間區間內，另一個用戶 B 發起了存款操作導致根值改變的情況。因為一但根值改變后，用戶 A 的 proof 將無法通過校驗。

參考文檔

APP：https://tornado.ws/
Circuit Doc：https://docs.tornado.ws/circuits/core-deposit-circuit.html
Tornado Cash工作原理（面對開發人員的逐行解析）
真正的ZK應用：回看Tornado Cash的原理與業務邏輯

后記

也好久沒有更新博客了，這段時間里處于一個對未來的職業發展以及技術積累比較迷茫的狀態，導致做事情有點舉棋不定，不敢做也不知道怎么做。在這種狀態下既沒辦法靜下心來深入研究某個東西，也沒有辦法鼓起勇氣去探索新的方向，總的來說就是兩個字：內耗。
目前也沒有想到什么好的辦法能夠走出當前這種局面，真的讓人苦惱。

posted @ 2024-05-09 18:48 ACai_sec 閱讀(1621) 評論(0) 收藏舉報

刷新頁面返回頂部

阿菜種菜的菜園子

零知識證明： Tornado Cash 項目學習

前言

項目概覽

取款憑證所包含的信息

為什么是 31 個字節而不是 32 個字節？

代碼總覽

存款業務代碼分析

全局變量

zeros() 預先計算空子樹根節點的值

filledSubtrees 不是存放全被使用的子樹根節點嗎？

MerkleTreeWithHistory._insert() 函數插入葉子節點

MiMC 哈希函數

取款業務代碼分析

`MerkleTreeChecker` 函數檢查

DualMux() 函數的巧思

為什么 note 要采用 nullifier + secret 的形式

isKnownRoot() 函數檢查 root 是否還有時效性

參考文檔

后記

公告

阿菜種菜的菜園子

零知識證明： Tornado Cash 項目學習

前言

項目概覽

取款憑證所包含的信息

為什么是 31 個字節而不是 32 個字節？

代碼總覽

存款業務代碼分析

全局變量

zeros() 預先計算空子樹根節點的值

filledSubtrees 不是存放全被使用的子樹根節點嗎？

MerkleTreeWithHistory._insert() 函數插入葉子節點

MiMC 哈希函數

取款業務代碼分析

MerkleTreeChecker 函數檢查

DualMux() 函數的巧思

為什么 note 要采用 nullifier + secret 的形式

isKnownRoot() 函數檢查 root 是否還有時效性

參考文檔

后記

公告

`MerkleTreeChecker` 函數檢查