[ZKP 讀書會] Zkopru
Zkopru
Zkopru 這個名稱是由 zk-transaction + Optimistic Roll-Up 的字首組成，這個layer 2 的協議包含了使用零知識證明來保護交易的隱私（ zk-transaction）、再搭配 Optimistic Rollup 來管理 layer 2 。
接下來會講到 Zk Rollup 和 Optimistic Rollup，如果讀者還不熟悉，可以先閱讀這篇介紹。
它和 Zk Rollup 有什麼不同？
Zk Rollup 連同 layer 2 的鏈的 state transition 都是由零知識證明來處理，但缺點是目前零知識證明技術的成本較高，包含在鏈下產生證明和在鏈上驗證證明（鏈下產生證明耗費時間，鏈上驗證證明則耗費 gas）。
註：接下來提到的（零知識證明、circuit）的鏈下成本都是指時間多寡，而鏈上成本則都是指 gas 多寡）
另外目前的 Rollup 協議都是使用 merkle tree 來儲存當前的鏈的狀態（例如使用者的餘額、nonce 或是 UTXO） — 如果使用者要證明他有 $20，則他必須要提供 merkle proof ，而這個 merkle proof 的大小及 hash 次數也會因為選擇的 merkle tree 的高度而有不同。
而這個因素再搭配上 hash 的成本在 EVM 和 circuit 會有不同，導致協議如果使用在 EVM 成本較便宜的 hash function，則 circuit 的 hash 成本會較高；反之亦然。
目前還沒有安全的 hash function 是在 EVM 或 circuit 裡都是便宜的，所以協議設計者必須做出妥協。可想而知，Zk Rollup 便是使用在 circuit 便宜但是在 EVM 貴的 hash function，這導致當使用者要離開 layer 2 回到 layer 1 時（這個步驟在這裡稱作 withdraw），他成本會很高（因為要在 EVM 裡驗證他持有資產的擁有權，這可以是一個 merkle proof 或 zk proof）。
和 Optimistic Rollup 有什麼不同？
而這個成本相對的也反映了採用 Optimistic Rollup 的好處 — 只有在特殊情況下（例如協議裡的 Operator 作惡）才需要付出較高的成本，其他時間大家則享受極低成本的使用費。
但使用 Optimistic 的方式也有附帶的缺點： challenge period 。輕節點使用者需要等待 challenge period 來確保交易不會被推翻、withdraw 過程需要等待 challenge period（以下稱 withdraw period） 過了才能將錢提回到 layer 1。
所以使用哪種 Rollup 就要看協議設計者如何依照他們的使用需求去權衡。
那為什麼不使用 Optimistic Rollup 就好？
因為需要零知識證明來保護交易隱私！
前提
- zkopru 使用和 Bitcoin 相同的 UTXO model
- transfer 的付款方、收款方和金額都是被保護住、看不到的，但 zkopru 和其他隱私幣一樣，不需要付款方和收款方合作即可由付款方單獨完成 transfer。
但也和隱私幣一樣，收款方必須去監看鏈上每一筆交易並嘗試解密來得知是否有人 transfer 給自己
基本使用流程
Deposit
使用者將 ether 、ERC20 或 ERC721 代幣轉入 zkopru 位於 layer 1 的合約，觸發 event。協議的 Operator 會監看合約並搜集 deposit event，然後將這些 deposit 一起放入下一個（zkopru 的）區塊裡。
Transfer
如同 Bitcoin 的 UTXO，zkopru 裡使用者必須要證明其對某 UTXO 有擁有權才能花費該 UTXO。要被花費的 UTXO 會被放到 transaction 格式裡的 inputs 欄位， outputs 欄位的 UTXO 則是填入收款方的公鑰和收款金額（outputs 的 UTXO 就會是新產生的 UTXO）。
因為要保護交易的隱私，新的 UTXO 的資訊是不會洩露出去的，第三方只會看到該 UTXO 的 hash 值。那收款方要怎麼知道一個 UTXO 是不是他的呢？
sender 會利用自己的私鑰、收款方的公鑰及一個隨機值，透過密鑰交換協議來產生一個臨時的共享密鑰。 付款方用此共享密鑰加密收款方所需的資訊（包含 transfer 的代幣種類和金額），而收款方會監看每一筆交易並試著用自己的私鑰組出一個共享密鑰然後去解密，如果解密完的資料不是亂碼而是合理的，則可確認收到錢。
Withdraw
使用者產生 withdraw 類別的交易，等待協議 Operator 收進區塊裡，然後再等待 withdraw period 過去，即可送出 merkle proof 來將錢提領回 layer 1。
註：提領回 layer 1 之後的收款方和金額都是公開透明的，隱私不再受保護。
零知識證明
zkopru 裡一共有三種類型的 merkle tree 來儲存所需的狀態，分別是 UTXO tree、Nullifier tree 以及 Withdrawal tree。
- UTXO tree 紀錄所有產生過的 UTXO，包含新的和已經花掉的。
- Nullifier tree 紀錄被花掉的 UTXO 的 nullifier 值。一個 UTXO 的 nullifer 由該 UTXO 的相關資訊算出，而且只能得出唯一一個 nullifier。這個 nullifier 能夠證明該 UTXO 已被花掉，但同時又不會洩露是哪個 UTXO 被花掉。聽起來很饒口，但這就是零知識證明的能力。
- Withdrawal tree 紀錄 withdraw 類別的交易的資訊，使用者要提領回 layer 1 就需要這棵 merkle tree 的 merkle proof。也是就說，前面說的 Operator 會把 withdraw 交易放到這棵 merkle tree 裡，然後等待 withdrawal period 過後，再由使用者提供 merkle proof 來領走。
這裏以 transfer 為例來說明其中一部分的 circuit 在做什麼事
當使用者要產生一筆 transfer，他首先要證明 inputs 裡的 UTXO 都是合法的，這包含了證明：
- 他擁有這個 UTXO — 藉由提供簽章來證明
- 這個 UTXO 是真的存在的 — 藉由證明該 UTXO 的 hash 值存在 UTXO tree 裡
- 這個 UTXO 沒有被花過 — 藉由證明該 UTXO 的 nullifier 值不存在 Nullifier tree 裡
接者是 outputs，新產生的 UTXO 的 hash 值會被放進 UTXO tree 裡。
最後是比對 inputs 金額加總等於 outputs 金額加總再加上交易手續費。
而這些都在 circuit 裡完成，第三方沒辦法得知實際的 inputs、outputs 或 nullifiers 等等，第三方只能知道新的 UTXO 的 hash 值以及運算過程是正確的 — 也就是這些 tree 都被正確的更新了。
其他特色
Mass migration
原本每個使用者要把資產換到另外一個 layer 2 協議，他必須申請 withdraw 、等待 withdraw period ，然後把資產 deposit 到另外一個 layer 2 協議。
zkopru 支援使用者成批的搬移資產到另外一個 layer 2 協議 — 共享經濟。
Instant withdrawal
如果其他需要等待 withdraw period 的應用來說，withdraw period 是一個 UX 痛點。zkopru 的 instant withdrawal 提供急著 withdraw 的一方和不急著 withdraw 的一方一個管道能互惠。
急的一方提供一點手續費，對自己的 withdraw 交易做簽名並廣播出去。不急的一方在聽到這個簽名後，可以將這個簽名送到 zkopru 合約並附上 withdraw 金額（扣掉自己該收的手續費）。
這筆錢會直接轉給急的一方，然後急的一方的 withdraw 擁有權便會轉移到不急的一方手上，不急的一方再慢慢等到 withdraw period 過了再提領。
估計效能
目前在初版的效能估計中，一筆 transfer 平均耗費 8800 gas；而 TPS 則是 105。zkopru 還在積極更新迭代中，所以這個效能會在提升。
Reference:
