基於 ZK 的資產證明

04-01

Summa

我們一般持有加密貨幣常常會在中心化交易所進行貨幣的買賣兌換等操作。在中心化交易所進行交易非常便捷迅速，自比特幣發行以來十多年的時間，市場上湧現過許許多多的中心化交易所，極大的方便了用戶進行加密貨幣買賣操作。但是伴隨著中心化交易所的繁榮，欺詐和惡意捲款跑路等行為屢見不鮮。奈飛曾為此專門拍攝過一部關於交易所突然倒閉，創始人神秘死亡的宣傳片：別信任任何人，虛擬貨幣懸案^[1]。特別的，2022 年 FTX 因為資不抵債而宣佈破產更是震驚了世界，諸多用戶和基金公司為此蒙受巨大損失。

事實上，不止在加密貨幣領域，其他傳統領域通過會計做假賬的方式欺瞞投資者的行為也是難以計數。如 21 世紀初轟動世界的安然事件。安然是一家連續六年被《財富》雜誌評選為「美國最具創新精神公司」，然而就是這樣擁有上千億資產的公司，在 2002 年在幾周內迅速破產。又比如恒大公司，將本來用於蓋樓的專款資金挪去他用，最終導致無數業主背上 30 年房貸苦等來的卻是爛尾房屋。

多個不同領域層出不窮的欺詐行為背後的一個重要原因就是審計和會計工作本身並不完全公開透明，於是產生巨大的腐敗和作弊空間。但是為了保護公司利益和投資者隱私，關鍵財務數據又不可能做到完全公開透明，因此應對財務造假除了加強監管一直沒有很好的解決辦法，但是隨著零知識證明技術逐漸成熟，我們可以看到一種新的解決思路。

如果每個用戶都可以驗證自己部分的資產是否有財務作假行為，那麼只要驗證的用戶足夠多，那麼一個組織想要去做財務欺詐難度就會非常高。而又因為驗證的過程是零知識的，那麼驗證數據在網絡傳輸過程中，第三者即使截獲了數據，他也不知道用戶的真實資產到底是多少，這樣一來，驗證過程就完全可以在網絡上公開展示出來。在零知識證明技術的幫助下，相當多的審計工作不再是像四大會計事務所一樣是某些組織的專利，關起門來秘密進行。而是任何利益相關方都可以參與的公開過程。

Summa^[2]是一個 PSE 研究項目，旨在用 zk 的辦法來去做用戶資產驗證。本文接下來的內容就概要的介紹一下該項目，以及技術實現原理。

合約

Summa 的整體數據流如圖所示。智能合約在這裡主要用於對一些公共數據存儲和驗證。並不一定和以太坊強綁定，即使將來部署在像 Solana 等其他區塊鏈也是可以的（只要 Halo2 有對應區塊鏈支持，本項目中一些合約是由 Halo2 證明生成的^[3]）。

圖中 Custodian 表示中心化交易所。合約由交易所部署上鍊，合約所有權歸交易所所有，公共數據只能由交易所提交。公共數據包含兩部分，一部分是交易所掌控的鏈基本信息以及數字簽名等。

第二部分是鏈上資產的信息，包括 Merkle sum tree 的 root hash，以及 root balance（鏈上資產的具體數量，比如多少個 BTC ），該部分數據將用於 zk 證明的 instance 輸入。

這兩部分數據都是很容易在鏈上公開可以查詢到的（除了 root hash ）。交易所很難對這些數據作弊。任何人都可以對比合約中存儲的數據和區塊鏈地址上實際數據結果。

proof 生成目前是由交易所生成，由用戶向交易所提交需要驗證的關鍵信息，然後由交易所生成 proof 返回給用戶。用戶可以拿著這個 proof 向智能合約請求，由合約來驗證 proof。

最後 Proof Verify 是用戶同合約直接交互的。該部分合約是由 Halo2 電路翻譯成 Solidity 代碼然後作為一個單獨的驗證合約部署上鍊。

在實際使用時可以通過傳入 proof 來在鏈上計算和驗證。

下面的代碼示例是實際的 Hash 運算所用到的函數，可以看到整個 hash 計算本身並沒有用到位運算，只有加法和乘法計算，是 zk 友好的。

zk 數據計算和傳統的程序計算不同的是 zk 數據要在有限域中計算，Merkle Tree 構建時確保每一個結點數據不能超過有限域就十分必要了，為此在計算前先要對數據做 range check 以後數據 overflow。

range check 的大致原理類似下面示例所示。首先對於輸入的數據，以 8 位為長度單位，截出多份，方便將來做減法運算。然後每次進行 next數值計算的時候都按照下面示例的計算步驟去做計算。range check 電路做約束的時候實際上是根據中間結果diff = z_cur - z_next * Expression::Constant(Fp::from(1 << 8))去做約束，要求 diff 只要在 8 位數值之內即可。這樣對於一個 32 位數據的約束，只需要佔用 4 個計算 cell，還有 256 個 lookup table，以後最高位為 0 的 instance 約束即可。如果不是這樣設計，單純去做 32 位數值的 range check，需要大小的 lookup table，顯然這樣的電路就太大了，無法實際應用。

有了這些輔助結構就可以正式構建 Merkle Sum Tree。每一個用戶輸入數據都稱之為 Entry，其結構為：

Merkle Tree 中間結點的 hash 計算方式是H(LeftChild.balance[0] + RightChild.balance[0], LeftChild.balance[1] + RightChild.balance[1], ..., LeftChild.balance[N_CURRENCIES - 1] + RightChild.balance[N_CURRENCIES - 1], LeftChild.hash, RightChild.hash)，因此實際要計算的 vec 數組長度是N_CURRENCIES + 2。

下面我們完整構建一下整個 Merkle Tree。葉子結點部分比較簡單，只需要將 Entry 轉換為 Node 即可。中間結點需要逐層構建，每一箇中間結點的值都和下一層的左子樹和右子樹的值有關。最後將計算的中間結點結果放到 tree 數組裡：

接下來我們使用 Merkle Tree 構建 zk proof。zk 要證明的是某個用戶的 entry 確實在該 Merkle Tree 上。所以首先需要對制定具體的 entry 索引，根據 Merkle Tree 生成 zk proof 需要的數據結構。

我們可以通過設置 0 和 1 來巧妙的達到讓整個等式為 0 的約束效果。

Merkle Tree zk 約束主要有兩部分，一部分是 swap 約束，以確保交易所在生成證明的時候確實是按照上圖的真實順序生成的。另一部分是 balance 約束，即父結點的 balance 確實來自左子結點和右子結點的和。關於 balance 的 sum 約束比較簡單，這裡著重看一下 swap 約束。

我們之前介紹的 Merkle zk tree 數據結構sibling_middle_node_hash_preimages是一個數組，並沒有包含位置信息。圖中虛線方框的位置到底是在應該在樹的左側還是右側，要有path_indices的 0 和 1 來判斷。因此我們一定要確保當數值為 0 的時候，該生成父結點位於左側，他對應的同 level 的兄弟結點位於右側，1 的時候相反。在數據導入 zk 電路時該邏輯可以比較輕鬆的用代碼實現：

整體的 Merkle Sum Tree zk proof 的過程就是逐層的處理數據，然後將對應位置數據輸入 zk 約束電路檢查。構建起整個 Merkle Tree。最後輸出的是根節點 hash 和總的 balance，它應該和合約中的對應數據保持一致，使用 instance 來驗證一致性。如果所有驗證都沒有問題，至此整個 Merkle Tree 的證明工作算是結束。

Solvency Verify

生成 proof 的過程是由用戶向交易所請求，然後交易所返回 proof 數據，隨後用戶再向智能合約去做驗證。目前該項目暫時不支持用戶繞過交易所自行生成 proof，但是覺得未來或許可能是一個可以探索的方向。由用戶直接生成 proof，而不是由交易所返回。整個 halo2 證明電路可以用 rust 打包成 web assembly，然後使用 ethers rs^[7] 作出對應的交互 api。Merkle Tree root 驗證時間複雜度是 log(n)，或許用戶的設備做驗證並不需要太多的時間，這樣進一步增強了去中心化的安全性。

參考

[1]

別信任任何人，虛擬貨幣懸案: https://www.netflix.com/hk/title/81349029

[2]

Summa: https://github.com/summa-dev

[3]

Halo2證明生成的: https://github.com/privacy-scaling-explorations/halo2-solidity-verifier

[4]

Poseidon Hash: https://github.com/ingonyama-zk/poseidon-hash

[5]

參數準備階段和Hash運算階段: https://autoparallel.github.io/overview/index.html

[6]

Linear-feedback shift register: https://en.wikipedia.org/wiki/Linear-feedback_shift_register

[7]

ethers rs: https://github.com/gakonst/ethers-rs

基於 ZK 的資產證明

Summa

合約

Solvency Verify

推薦閱讀