摘要：同樣，鏈下擴容方案 zk Rollup 也可以用類似的 Merkle 樹來組織其賬戶狀態。relayer 負責收集並驗證用戶的 transaction，之後將 transaction 批量打包，並生成 zkSNARK 的 PROOF，最終將用戶 transaction 中的核心數據和 zkSNARK 的 PROOF 以及新的全局用戶狀態的 Merkle 根提交到鏈上的智能合約。

本文來自PPLabs， PPIO 是爲開發者打造的去中心化存儲與分發平臺，讓數據更便宜、更高速、更隱私。官方網站是 https://pp.io 。

背景

區塊鏈公鏈自誕生以來，雖然大大降低了信任的門檻，但一直面臨着一個效率問題：即 TPS 不高。例如比特幣每秒僅支持7筆交易，而目前的以太坊也僅支持每秒 15 筆左右的交易。這樣的 TPS 很支持大型應用。因此業界很多技術人員嘗試爲區塊鏈擴容。目前擴容方案主要有兩類：

  • Layer 1 擴容方案，即直接增加鏈上的交易處理能力，這種方式也被稱爲鏈上擴容。常見的技術方案有：Sharding 和 DAG；

  • Layer 2 擴容方案，即將鏈上的相當一部分工作量轉移到鏈下來完成。常見的技術有：State Channel,Plasma,Truebit 和 最近比較火的 zk Rollup。

ZK Rollup 並非新概念，@barrywhitehat 在一年前提出，目前由 Matter Lab 和 den3 進行工程實現。

原理

  • 那麼，zk Rollup 背後的原理是什麼？

zk Rollup 的本質是將鏈上的用戶狀態壓縮存儲在一棵 Merkle 樹中，並將用戶狀態的變更轉移到鏈下來，同時通過 zkSNARK 的證明來保證該鏈下用戶狀態變更過程的正確性。在鏈上直接處理用戶狀態的變更成本是比較高的，但是僅僅利用鏈上的智能合約來驗證一個零知識證明的 PROOF 是否正確，成本是相對低很多的。另外必要的轉賬信息也會被和證明一起提交到合約，方便用戶查賬。

兩類角色

zkRollup 系統中包含兩類角色：transactor 和 relayer。

  • transactor，即普通用戶，對應以太坊上的外部賬戶。用戶構建轉賬交易並用私鑰簽名，然後將交易發送給 relayer。

  • relayer 負責收集並驗證用戶的 transaction，之後將 transaction 批量打包，並生成 zkSNARK 的 PROOF，最終將用戶 transaction 中的核心數據和 zkSNARK 的 PROOF 以及新的全局用戶狀態的 Merkle 根提交到鏈上的智能合約。

當然 relayer 不會免費爲 transactor 提供服務，畢竟 relayer 向鏈上提交證明和數據是需要消耗 gas 的。因此，transactor 向 relayer 發送的交易裏，也必須包含相應的手續費。

狀態遷移函數

當 relyer 收到 transaction 後，必須 “執行” 它。transaction 的執行，本質上是改變相關賬戶的狀態，而 STF 就是改變賬戶狀態的函數。STF 是狀態遷移函數(state transition function)的縮寫。

狀態是針對狀態機而言的，每個狀態機在某一時刻都有一個狀態。我們可以假設某狀態機的初始狀態是 S[0]。當某個 Action T[1] 作用在該狀態機上時，狀態機的狀態發生了遷移。我們可以用以下式子來表示遷移過程。

S[1] = STF(S[0], T[1])

這裏，S[0] 是初始狀態，S[1] 是狀態機執行 Action T[1] 之後的狀態。

緊接着有新的若干 Action T[2], T[3], …, T[n] 繼續作用在該狀態機上，則狀態機的狀態依次發生遷移。

S[2] = STF(S[1], T[2])
S[3] = STF(S[2], T[3])
...
S[n] = STF[S[n-1], T[n]]

簡單地，我們也可以將 T[1], T[2], …, T[n] 看作一個整體，則狀態遷移過程可以簡化爲：

S[n] = STF(S[0], T[1], T[2], ..., T[n])

更一般地，假設當前狀態機的狀態是 PRE_STATE，然後有 n 個 Action T[1], T[2], …, T[n] 依次作用到狀態機上，之後狀態機的狀態是 POST_STATE，此可以表示爲：

POST_STATE = STF(PRE_STATE, T[1], T[2], ..., T[n])

如果將以上 Action 換成轉賬交易 transaction，把 系統中的賬戶集合看作是一個狀態機，那麼整個過程也就是鏈上交易執行的過程了。交易的執行，使得整個鏈上的全局狀態發生變化。鏈上的全局狀態也就是各個賬戶的狀態集合，將所有賬戶的狀態組成一棵 Merkle 樹，樹的葉子節點是賬戶狀態，樹的根可以直接用來表示狀態集合。因此，上述的 PRE_STATE 和 POST_STATE 也就是全局賬戶狀態樹的根。

賬戶狀態模型

剛纔我們提到鏈上的整個系統中的賬戶狀態，可由一棵 Merkle 樹來管理。Merkle 樹的葉子節點，即用戶的狀態信息。同樣，鏈下擴容方案 zk Rollup 也可以用類似的 Merkle 樹來組織其賬戶狀態。

最簡單的賬戶狀態可以包含：賬戶的 public key，nonce 和 balance。而葉子節點在Merkle 樹中是有唯一位置的，因此位置的索引信息可間接引用這個賬戶信息。

如果我們用3個字節來表示這個索引信息的話，那麼這棵 Merkle 樹總共可以支持 2^24 = 16,777,216 個賬戶。這對於一般的系統來說已經足夠。因此，以太坊爲例，賬戶地址可以由 address 的 20個字節 轉爲 Merkle 樹的葉子節點索引 3 個字節。這樣賬戶地址就被“壓縮”了。

除了對賬戶地址進行壓縮，我們也可以對轉賬金額數據進行壓縮。例如，在以太坊上金額用256位的大整型來表示，但是實際使用過程中幾乎很少用到超大金額和超小的金額。因此如果我們就假設系統中轉賬的最小單位是 0.001 ETH，並且用 4 個字節來表示轉賬金額的話，我們就可以支持 0.001 ~ 4,294,967.295 ETH 的轉賬，這對於一般的系統來說也已經夠了。如果還不夠可以適當再增加字節來表示金額，或者引入浮點數表示方式。

手續費與轉賬金額類似，實際手續費會在一定的範圍之內浮動，因此我們也可以爲手續費設定一個最小單位，例如：0.001 ETH。然後用 1 個字節來表示 0.001 ~ 0.255 ETH 的手續費。這裏的手續費也就是 transactor 向 relayer 支付的手續費。

同樣，我們假設在正常使用環境下一個賬戶的轉賬次數不會達到上萬次，因此用2個字節來表示賬戶的 nonce 也差不多夠了，因爲 2 個字節 可以表示的範圍達到 0~65535。

最後簽名字段不能壓縮，以以太坊爲例，簽名 (r, s, v) 總共需要 65 個字節。但實際的zk Rollup 系統中使用 EdDSA的較多。

因此，一個 transaction 的格式大體如下：

以上 transaction 各字段的長度僅作參考，在實現具體系統的時候需要根據實際情況調整字段長度，以防止發生字段溢出的情況，但原則上還是能省則省。因爲交易數據越少，在相同存儲容量的前提下，所能容納的交易數也就越多。

證明和驗證

瞭解了狀態遷移函數和賬戶狀態模型後，我們再來了解下 relayer 收集 transaction 後做了些什麼。

我們剛纔提到在 zk Rollup 的系統裏，所有用戶的賬戶信息由一棵 Merkle 樹管理。而 Merkle 樹的根被記錄在了鏈上的智能合約裏，這個根的值也代表着整個系統當前所有賬戶的狀態。當有用戶發起轉賬 transaction 時，這個狀態就要發生改變。但改變必須依照規則進行。

  • 首先，必須要確保 transaction 的合法性：

    • 轉出賬戶是否有足夠的錢支付轉賬金額和手續費
    • 轉出賬戶的 nonce 是否正確
    • 轉賬 transaction 的簽名是否正確

  • 接着，relayer 執行該轉賬 transaction，修改 Merkle 樹中的轉出賬戶和轉入賬戶的葉子節點，然後重新計算新的 Merkle 樹的根。

  • 重複第二步，relayer 會按照先後順序一次性處理多個 transaction，然後將最後計算得到的 Merkle 樹的根作爲新的狀態提交到鏈上合約中。

但上述流程存在問題：如果僅提交狀態樹的根到合約，那麼用戶如何相信新的狀態根是如實地根據上述邏輯計算出來的。萬一 relayer 作惡，故意調大 transaction 的手續費呢？

解決這個問題的一個方法是：要求 relayer 提交狀態樹的根到合約時，同時也將所有 transaction 提交到合約，這樣任何人都可以根據這些 transaction 來驗證 relayer 在計算新的狀態樹時，有沒有作弊。但這等於是將所有鏈下的數據搬回了鏈上，沒有實現 layer 2 擴容的目的。

利用零知識證明就可以很好地解決這個問題。zk Rollup 中的 zk 也就是 zero-knowledge 的縮寫。relayer 在收集了一系列的 transactions 後，需要用預先定義好的 ZK circuits 來生成一個 PROOF：

  • 確保每個交易 T[1], T[2], …, T[n] 中的 nonce, value, fee 等值都沒有問題，且 signature 正確。

  • 確保狀態遷移過程沒有問題，即 STF(PRE_STATE, T[1], T[2], ..., T[n]) = POST_STATE

  • 然後將這個 PROOF 與 POST_STATE, t[1], t[2], …, t[n] 一起提交到鏈上合約。其中 t[1], t[2], …, t[n]是 transaction 的簡化信息，不包含 nonce 和 signature。所以 t[i] 比 T[i] 更小。

然後智能合約只需要驗證這個 PROOF 是否正確。如果 PROOF 正確且合約中保存的狀態與 PRE_STATE 相等，那麼新的狀態 POST_STATE 將會被記錄到合約中，替換原有狀態。

由於 relayer 必須生成 zkSNARK 的 PROOF，然後才能向合約提交，因此如果 relayer 作惡 修改用戶的 transaction，那麼 PROOF 將無法被驗證通過。

另外，由於提交到鏈上的交易 t[1], t[2], …, t[n] 是不包含 nonce 和 signature 的，因此上鍊的數據將會變得更小（上例中每個 transaction 僅會有11個字節上鍊）。

此時，relayer 由於證明的限制，已經無法修改用戶的 transaction。但是 惡意的 relayer 依然可以拒絕爲某個 transactor 服務，不蒐集該 transactor 的 tranaction。爲了防止這種行爲，合約上必須支持 on-chain withdrawal，也就是任何一個 transactor 都可以從鏈上將自己的 token 提走。

zk Rollup 目前的應用

目前一個典型的 zk Rollup 應用場景是去中心化的交易所，其代表是 Loopring DEX Protocol (v3) 。有興趣的小夥伴可以深入研究一下。

此外，開源的 zk Rollup 框架還有：

總結

zk Rollup 是一種新型的 Layer 2 擴容方案，該技術的核心思想是：

  • 將主鏈作爲存儲媒介，而非共識引擎 ；

  • 將交易壓縮，並在鏈下達成狀態共識 ；

  • 用零知識證明保證鏈下狀態共識的安全性。

目前，zk Rollup 最典型的應用場景是去中心化的交易所。

PPIO 也在積極探索 zk Rollup 技術，並嘗試將其應用到 去中心化的帶寬和存儲交易領域中去。

參考文獻

想了解更多有關 PPIO 的信息，可以移步官網： pp.io 或關注公衆號：

深入淺出區塊鏈 - 打造高質量區塊鏈技術博客。

相關文章