最近翻到一篇利用零知識證明在以太坊上實現隱私交易的新方案。Zkopru採用的還是UTXO模型，交易隱私實現的思路和ZCash類似。Zkopru的這篇介紹比較詳細的介紹交易的型別，layer1/layer2的互動等等。翻譯了一下，方便其他小夥伴檢視。對layer2隱私協議感興趣的小夥伴可以看看。
https://ethresear.ch/t/zkopru-zk-optimistic-rollup-for-private-transactions/7717
很高興能給大家分享Ethereum的一個隱私層 - Zkopru的實現。去年十一月開始，我和@barryWhiteHat 就開始撰寫這個教程，現在終於呈現給大家我們的成果。
特別感謝幫助我們修改，支援這個專案的V, W, K, J, JP, L, and A 等人。
Zkopru是什麼?
· 是隱私交易中的一個layer 2解決方案
· 使用 optimistic rollup來管理區塊
· 使用 zk SNARK 來建立隱私交易
效能
· Ethereum上每個隱私交易消耗 8800 gas
· 當gas limit為11.95M，block time為13.2s時，最大TPS是105
功能強大
· 支援 ETH, ERC20, 甚至是 ERC721
· 支援 private atomic swap，可用於私人的對盤系統
· Subtree rollup縮減了更新merkle tree大概20倍的成本
· 區塊結束前即時提取資產
· 透過使用大量存款和大規模遷移，我們可以構建一個inter-layer-2的網路.
重中之重，來這裡試試我們的測試版 https://zkopru.network
簡介
Zkopru 使用zk-SNARK和optimistic rollup，是實現隱私交易的layer-2擴充套件解決方案。Zkopru在layer-2網路中支援ETH, ERC20, ERC721間隱私交易和原子互換，並且成本很低。同時，它的提前支付功能使使用者可以在layer-2上狀態確定前提取資產。
交易
zk交易接受幾種UTXO輸入並且建立新的UTXO輸出，所以驗證UTXO的輸入輸出是非常重要的步驟。
注：交易採用的是UTXO模型。支援三種交易：一般交易，圖的最左邊。提取交易，圖的最右邊，鏈上交易，layer1和layer2之間。
UTXO輸入驗證
Zkopru透過使用資訊提交-作廢協議（commitment-nullifer）實現隱私性。這意味著zk交易在不揭示使用的是哪一個交易（note）的同時使用UTXO。與此相對的，透過生成nullifer，“斷開“和UTXO交易的連線。
使用UTXO需要滿足以下幾個條件:
UTXO 存在性證明
透過提交每一個UTXO的Merkle證明來證明其存在。為了提升SNARK計算的效能，UTXO樹使用Poseidon來作為它的hash function。
所有權證明
只有所有者擁有使用UTXO的許可權。為達成這個條件，每一個note都有一個公鑰（Babyjubjub點）。透過使用對應的金鑰，所有者可以建立EdDSA簽名來證明他/她的所有權。
Commitment證明
電路需要輸入UTXO交易的具體資訊來計算輸入交易的總和。並且，交易的Poseidon hash值應當與Merkle證明和所有權證明的葉子結點hash值相等。
Nullifier證明
提供的Nullifer應當從輸入UTXO中正確計算獲取。
UTXO輸出驗證
zk交易可以產生三種不同的輸出：一般UTXO交易（layer2的普通交易），提取交易（layer2中的特殊交易），遷移交易（layer1和layer2互動交易）。如果zk交易產生UTXO交易，將它們加到 UTXO樹上。當產生提取交易輸出時，Zkopru將它們加到withdrawal 樹上。最後，遷移交易，也就是layer-2區塊的一部分， 包含了區塊中每一個zk交易的遷移輸出。
輸出交易需要滿足以下幾點:
· 當輸出是UTXO交易時，輸出的hash值等於SNARK電路上的計算值。
· 當輸出是withdrawal或遷移，它應該將正確數量的資產移出layer2。
Zero-sum證明
最後，zk交易應當保證UTXO輸入和UTXO輸出金額相等，包括手續費。
區塊結構
區塊頭資訊
區塊頭372個位元組，包含了以下資訊：
Propertytype
Proposer’s addressaddress
Parent block hashbytes32
Metadatauint256
Feeuint256
Latest UTXO tree’s rootuint256
Latest UTXO tree’s leaf indexuint256
Nullifier tree’s rootbytes32
Latest withdrawal tree’s rootuint256
Latest withdrawal tree’s leaf indexuint256
Transactions’ rootbytes32
Deposits’ rootbytes32
Migrations’ rootbytes32
區塊內容
區塊內容由交易，充值和遷移組成。而且區塊頭應該包含了區塊的正確資訊。如果區塊頭不正確，區塊視為無效。
交易
充值
遷移
賬戶系統
新的公鑰結構正在起草，注意這部分說明會被更新。
Zkopru賬戶系統同時管理layer-1和layer-2的鑰匙串。首先，賬戶裡必須有一個隨機生成私鑰的Ethereum賬戶，用來在layer-1上進行操作。其次，Zkopru錢包從Ethereum賬戶的私鑰中建立一個Babyjubjub私鑰和公鑰對。這個Babyjubjub 鑰匙對會被用於EdDSA和layer-2上的加密備忘錄欄位。
Key大小如何得到在哪使用
Master seed32 byte隨機生成恢復鑰匙
Ethereum private key32 byteMaster seed透過BIP39派生Layer1 ECDSA
Ethereum public address 20 byte私鑰派生Layer 1 操作
Babyjubjub private key 254 bitEthereum私鑰派生建立EdDSA來使用UTXO
Babyjubjub public key (254 bit, 254 bit)Babyjubjub私鑰派生證明UTXO所有權
UTXO
新的UTXO說明近期將更新
性質 描述
Ether ETH數量
Public Key note所有者的一個Babyjubjub點
Salt 隨機salt. Zkopru 使用這個salt生成 UTXO hash
Token Address (Optional)當包含ERC20或者ERC721代幣合同的地址。預設值為0
ERC20 Amount (Optional)當包含ERC20時ERC20代幣的數量，預設值為0
NFT Id (Optional) 當包含ERC721時ERC721代幣的ID，預設值為0
然後Zkopru透過Poseidon hash計算Commitment:
var intermediate_hash = poseidon(ether, pub_key.x, pub_key.y, salt)
var result_hash = poseidon(intemediate_hash, token_address, erc20, nft)
接收者如何知道?
一筆zk交易可以包含81位元組給接收者的加密備忘錄欄位。因為零知識的特性，即使是接收者也無法在沒有一定操作的情況下了解到這些資訊，因此當我們想保持操作的簡便性，我們可以在備忘錄欄位上為接收者新增一些保密資訊。
加密
使用Diffie-Hellman金鑰交換協議生成共享的鑰匙，對於發信者生成共享鑰匙的具體步驟如下：
1. 建立一個臨時金鑰和其同態計算值
ehemeral = e
public_ephemeral = g^e
2. 用臨時金鑰乘以接收者的公鑰
recipient_pubkey = g^a
shared_key = (g^a)^e
3. 準備用於加密的壓縮資料
data = {
salt // 16 byte
tokenId, // 1 byte
value, // 32 byte
}
4. 使用chacha20演算法加密資料，並用臨時公鑰來建立備忘錄資料
ephemeral = random.new()
public_ephemeral = generator.multiply(ephemeral)
shared_key = recipient_jubjub.multiply(ephemeral)
ciphertext = chacha20.encrypt(data, shared_key)
memo = public_ephemeral + ciphertext
解密
使用Diffie-Hellman金鑰交換協議，接收者同樣透過臨時公鑰和金鑰建立共享鑰匙。
1. 解析備忘錄，利用私鑰獲取共享鑰匙
public_ephemeral, ciphertext = parse(memo)
shared_key = public_ephemeral.multiply(private_key)
2. 使用共享鑰匙解密密文
decrypted = ciphertext.decrypt(shared_key)
3. 加密資料僅有49位元組以儘量減小資料大小，接收者用解密結果驗證多個UTXO的輸出。
壓縮資料
為了儘量減小資料大小，Zkopru將原始資料壓縮成49個位元組。首先，公鑰不包括在加密資訊中，接收者可以用自己的公鑰來推斷。Zkopru採用代幣ID來對映被支援的代幣地址，指標範圍0～255。value可以是ether，erc20Amount或者nftId。最後，如果推斷出的UTXO存在於交易輸出的列表中，接收者便能成功收到UTXO。
限制
Zkopru並沒有採用電路證明加密協議。因此，如若發交易者沒有使用恰當的共享鑰匙或資料，接收者將不會收到該貨幣。
原子交換
Zkopru支援原子交換的方式非常直接。如果A和B想交換他們的資產，他們建立各自的note，並在交易資訊中透露適當的資料。然後打包者應當將相對的交易配對或刪除。
舉個例子，Alice想用她的50ETH換取Bob的1000DAI：
Alice 消費60 ETH幣，建立10 ETH幣給她自己，50 ETH幣給Bob。
Alice 同時為她將收到的1000DAI幣計算hash值，並將該數值記錄在她交易的swap中。
Bob 消費3000 DAI 幣，建立2000 DAI給他自己，1000 DAI幣給Alice。
Bob 同時為他將收到的 50 ETH計算hash值，並將該數值記錄在他交易的swap中。
當打包者將交易池中的這兩筆交易配對，將交易對打包進一個區塊裡。
如果區塊只有配對交易的其中一個交易，打包者將被懲罰。
Zkopru採用的是簡單版的原子交換。如果你想檢視一個MPC的zk原子交換模型，你可以在 這裡 讀到更多細節。
Merkle樹結構
注意Zkopru從下一版本開始將使用深度64的UTXO樹和withdrawal樹，以替代原本的深度32。
Zkopru森林由UTXO樹，nullifier樹和withdrawal樹組成。
UTXO樹是由UTXO組成的僅允許追加的Merkle樹。使用者可以透過提交包含Merkle證明，使用UTXO作為交易的流入，交易的結果將被加入UTXO樹。
同理，如果zk交易建立的是withdrawal輸出，Zkopru將它們加入withdrawal樹。一旦樹的根被標記為確定狀態，所有者在證明所有權之後可以提取資產。
隨後，依據承諾-無效符方案，被使用的UTXO的無效符會在nullifier樹中被標記成已使用， nullifier樹是一個唯一稀疏merkle樹。如果一筆交易試圖使用一個已經廢除的葉子，這筆交易將被作廢，同時區塊提交者將被懲罰。
Merkle樹說明
UTXO 樹 Nullifier 樹Withdrawal 樹
種類 稀疏Merkle樹 稀疏Merkle樹稀疏Merkle樹
深度 31 256 31
Hash Poseidon Keccak256Keccak256
How to update 僅許追加，5層深度樹rollupSMT rollup僅許追加，5層深度樹rollup
成本(gas/leaf) 180k 351k 5.2k
UTXO 樹和 withdrawal 樹在Burrito 版本中將有64層深度. https://github.com/zkopru-network/zkopru/issues/35 3
如何管理UTXO樹
一個單一的UTXO是為了存在性證明的稀疏Merkle樹。它採用的是Poseidon hash，SNARK中最便宜的hash函式之一，來生成zk-SNARK證明以隱藏雜湊和它的路徑。
協調者採用以下步驟來給UTXO樹新增新葉子：1. 準備一個陣列；2. 協調者選擇新增的MassDeposits並將MassDeposits中每一筆存款加入陣列；3. L2交易生成新的UTXO，將新生成的UTXO加入到陣列；4. 將準備好的陣列打散成chunk size 32；5. 構建子樹並執行子樹rollup
假定UTXO樹由(2^31)項填滿，系統封存被填滿的樹並開始一個新樹。被封存的樹允許被用作交易存在證明的參考。
Zkopru 積極地更新樹的根並僅當挑戰存在時進行確認。對於挑戰，Zkopru運用子樹rollup方法生成鏈上防欺詐。子樹rollup不是一個一個加入，而是將固定大小的子樹一次性加入。當子樹深度為5時，它將一次加入32個。如果子樹僅包含18個，剩下的14個將會永遠設定成0值。這個子樹rollup的方法相比較於rollup，極大地減小了gas成本——大約20倍。請到 contracts/controllers/challenges/RollUpChallenge.sol檢視原始碼，想知道子樹的運作原理請檢視packages/contracts/contracts/libraries/Tree.sol。
無效符樹
每一次轉賬，提取，和遷移交易都使用了包含證明的UTXO，並從樹上將派生的nullifier標誌成已使用。因此，nullifier樹是一個巨大的稀疏Merkle樹，在254層深的稀疏Merkle樹中記錄了使用的UTXO。所以Zkopru 使用了最廉價的keccak256作為 nullifier樹的雜湊函式。
協調者透過下列步驟來更新nullifier樹：
1. 選擇交易（轉賬，提取，遷移）並收集交易中所有的nullifier。
2. 確認不存在已被使用的nullifier。
3. 將所有nullifier標記成已使用。在更新過程中，如果樹根沒有被任何nullifier改變，廢棄這筆交易因為該交易試圖嘗試雙花。
同UTXO樹一樣，Zkopru積極更新nullifier樹根。如果過程存在任何問題，我們可以透過生成一個鏈上反欺詐來證明nullifier被多次使用，想知道這是如何運作的請檢視RollUpChallenge.sol 和 SMT.sol。
Withdrawal樹
withdrawal樹和UTXO樹唯一不同點在於withdrawal tree使用keccak256作為雜湊函式，使用keccak256的原因在於Zkopru在智慧合約上需要withdrawal樹的Merkle證明，同時需要UTXO樹的Merkle證明。withdrawal樹在layer-1智慧合約上樹根確定後，可以提取相應的資產。
協調者需要透過下列步驟來更新withdrawal樹：
1. 收集被選出的交易中所有的提取交易
2. 以32的塊大小來打散收集好的交易
3. 構建子樹，進行子樹rollup
大額存款
當使用者在Zkropu存入資產時會發生什麼
1. Zkopru合約將給定數目的資產從使用者賬戶轉移到自己的賬戶
2. 確認note具有合法雜湊值
3. 把note合併入MassDeposit[] 清單上最後一項
MassDeposit是什麼?
MassDeposit是用於rollup證明的mergedLeaves（bytes32）。如果協調者提出了一個含有 MassDeposits的區塊，區塊將MassDeposit中所有Note加入它的UTXO Merkle樹。
協調者如何處理MassDeposits?
協調器可以只包含確定的不會再改變的MassDeposits。協調者透過監控Deposit 事件來新增MassDeposit。
MassDeposit什麼時候變成“承諾的”?
存款需要儘快被推送到layer-2。協調者提出每個新區塊時，凍結最新一筆 MassDeposit 。
協調者可以包含多於一個MassDeposit嗎?
是的，在最大成本的區間裡同時包含多筆MassDeposits是可能的。
大規模遷移
大規模遷移的基本思想很簡單。當layer-1合約上的 deposit交易建立一個 MassDeposit物件， “遷移” 類別的交易輸出可以建立一個 MassMigration，為目標網路建立 MassDeposit 。
一筆交易可以有UTXO, 遷移, 或提取 型別的輸出。
在Zkopru裡，針對遷移有源網路和目的網路兩個概念。一旦源網路的大規模遷移完成（程式碼在 這裡），源網路上的 migrateTo函式 被執行。這個函式移動包含Ether, ERC20, 和ERC721在內的資產，並在目的網路建立一個MassDeposit物件。
因此，目的網路應當呼叫 acceptMigration 函式。詳情見 這裡
rollup間的遷移標準將透過EIP確立。
即時提款
在Zkopru中，取款者可以透過為每個即時提款支付費用完成及時提款。所有人都可以為尚未確定的取款提前支付並得到手續費。
為了申請即時提款，持有人為她的note生成一個ECDSA簽名並進行廣播。任何持有足夠資產的人可以透過使用該簽名為此次提款提前支付。一旦Zkopru完成這筆交易，智慧合約將所提取note的擁有權轉讓給支付方。最後，預付方在確定狀態後獲得支付。
我們可以為即時提款建立一個分散的公開市場。對這個話題有興趣的話請關注這個github issue https://github.com/zkopru-network/zkopru/issues/33 9](https://github.com/zkopru-network/zkopru/issues/33)
總結
我們就成功地透過Circom, Solidity, Typescript等搭建了測試網：
https://github.com/zkopru-network/zkopru
首先，每筆zk交易的gas費用都是可以我們承擔的，平均在8800 gas。當gas limit是11,950,000，block time是13.2秒時，理論TPS最大值為105。在Zkopru中，交易資料僅佔534位元組。因為證明資料是256位元組，在未來我們可以透過證明聚合來減少兩倍的交易成本。除此以外，每個區塊提出和確定的儲存費用分別是168k和55k。當完成350次交易時，這個成本大概是區塊生成成本的6.7 %。
此外，運用Optimistic Rollup的靈活性我們可以實現很多功能。第一，Zkopru支援多種交易型別。你甚至可以進行一個輸入，四個輸出或者四個輸入，一個輸出的交易。因為Optimistic Rollup靈活性，多種型別的交易是很容易支援。第二，Zkopru實現了pin-point的挑戰方式，這意味著如果區塊中第n個交易出了問題，挑戰會僅僅針對這個交易進行檢查。
另一個需要重視的點是Zkopru讓你在自己的機器上執行節點。因此SNARK效率和輕節點成為軟體開發中需要考慮的很重要的一個環節。相應地，專案是由Typescript和NodeJS實現的，支援未來在react-native架構下移動應用的使用。輕節點期望僅消耗50~100 MB的儲存空間。
簡而言之，我們希望Zkopru可以在Ethereum的隱私交易層中被採用。它具有快捷，廉價，並且可遷移到更新的版本的特性。
