摘要:同樣,鏈下擴容方案 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 或關注公衆號:

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

相關文章