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 Insights 系列
zkp 學習筆記
Wen Building Podcast
研究分析系列文章
Uniswap 精翻系列
Antalpha Labs 是一個非營利的 Web3 開發者社區，致力於透過發起和支援開源軟體來推動 Web3 技術的創新和應用。
官網：https://labs.antalpha.com
Twitter：https://twitter.com/Antalpha_Labs
Youtube：https://www.youtube.com/channel/UCNFowsoGM9OI2NcEP2EFgrw
聯絡我們：hello.labs@antalpha.com
