ZK Rollup是Layer 2擴容方案 可將用戶狀態存儲在Merkle樹中

投稿人/來源:區塊網 | 2019-11-06 14:57:28 |

背景

區塊鏈公鏈自誕生以來,雖然大大降低了信任的門檻,但一直面臨著一個效率問題:即 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 應用場景是去中心化的交易所,其代表是 Loopring DEX Protocol (v3)。有興趣的小伙伴可以深入研究一下。

此外,開源的 zk Rollup 框架還有:

barryWhiteHat/roll_up -C++

matter-labs/rollup - rust

總結

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

· 將主鏈作為存儲媒介,而非共識引擎 ;

· 將交易壓縮,并在鏈下達成狀態共識 ;

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

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

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


网络游戏赛车