背景區(qū)塊鏈公鏈自誕生以來(lái)，雖然大大降低了信任的門(mén)檻，但一直面臨著一個(gè)效率問(wèn)題：即 TPS 不高。例如比特幣每秒僅支持7筆交易，而目前的以

背景

區(qū)塊鏈公鏈自誕生以來(lái)，雖然大大降低了信任的門(mén)檻，但一直面臨著一個(gè)效率問(wèn)題：即 TPS 不高。例如比特幣每秒僅支持7筆交易，而目前的以太坊也僅支持每秒 15 筆左右的交易。這樣的 TPS 很支持大型應(yīng)用。因此業(yè)界很多技術(shù)人員嘗試為區(qū)塊鏈擴(kuò)容。目前擴(kuò)容方案主要有兩類(lèi)：

· Layer 1 擴(kuò)容方案，即直接增加鏈上的交易處理能力，這種方式也被稱(chēng)為鏈上擴(kuò)容。常見(jiàn)的技術(shù)方案有：Sharding 和 DAG;

· Layer 2 擴(kuò)容方案，即將鏈上的相當(dāng)一部分工作量轉(zhuǎn)移到鏈下來(lái)完成。常見(jiàn)的技術(shù)有：State Channel, Plasma, Truebit 和 最近比較火的 zk Rollup。

ZK Rollup 并非新概念，@barrywhitehat 在一年前提出，目前由 Matter Lab 和 den3 進(jìn)行工程實(shí)現(xiàn)。

原理

· 那么，zk Rollup 背后的原理是什么?

zk Rollup 的本質(zhì)是將鏈上的用戶(hù)狀態(tài)壓縮存儲(chǔ)在一棵 Merkle 樹(shù)中，并將用戶(hù)狀態(tài)的變更轉(zhuǎn)移到鏈下來(lái)，同時(shí)通過(guò) zkSNARK 的證明來(lái)保證該鏈下用戶(hù)狀態(tài)變更過(guò)程的正確性。在鏈上直接處理用戶(hù)狀態(tài)的變更成本是比較高的，但是僅僅利用鏈上的智能合約來(lái)驗(yàn)證一個(gè)零知識(shí)證明的 PROOF 是否正確，成本是相對(duì)低很多的。另外必要的轉(zhuǎn)賬信息也會(huì)被和證明一起提交到合約，方便用戶(hù)查賬。

兩類(lèi)角色

zkRollup 系統(tǒng)中包含兩類(lèi)角色：transactor 和 relayer。

· transactor，即普通用戶(hù)，對(duì)應(yīng)以太坊上的外部賬戶(hù)。用戶(hù)構(gòu)建轉(zhuǎn)賬交易并用私鑰簽名，然后將交易發(fā)送給 relayer。

· relayer 負(fù)責(zé)收集并驗(yàn)證用戶(hù)的 transaction，之后將 transaction 批量打包，并生成 zkSNARK 的 PROOF，最終將用戶(hù) transaction 中的核心數(shù)據(jù)和 zkSNARK 的 PROOF 以及新的全局用戶(hù)狀態(tài)的 Merkle 根提交到鏈上的智能合約。

當(dāng)然 relayer 不會(huì)免費(fèi)為 transactor 提供服務(wù)，畢竟 relayer 向鏈上提交證明和數(shù)據(jù)是需要消耗 gas 的。因此，transactor 向 relayer 發(fā)送的交易里，也必須包含相應(yīng)的手續(xù)費(fèi)。

狀態(tài)遷移函數(shù)

當(dāng) relyer 收到 transaction 后，必須 “執(zhí)行” 它。transaction 的執(zhí)行，本質(zhì)上是改變相關(guān)賬戶(hù)的狀態(tài)，而 STF 就是改變賬戶(hù)狀態(tài)的函數(shù)。STF 是狀態(tài)遷移函數(shù)(state transition function)的縮寫(xiě)。

狀態(tài)是針對(duì)狀態(tài)機(jī)而言的，每個(gè)狀態(tài)機(jī)在某一時(shí)刻都有一個(gè)狀態(tài)。我們可以假設(shè)某狀態(tài)機(jī)的初始狀態(tài)是 S[0]。當(dāng)某個(gè) Action T[1] 作用在該狀態(tài)機(jī)上時(shí)，狀態(tài)機(jī)的狀態(tài)發(fā)生了遷移。我們可以用以下式子來(lái)表示遷移過(guò)程。

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

這里，S[0] 是初始狀態(tài)，S[1] 是狀態(tài)機(jī)執(zhí)行 Action T[1] 之后的狀態(tài)。

緊接著有新的若干 Action T[2], T[3], ..., T[n] 繼續(xù)作用在該狀態(tài)機(jī)上，則狀態(tài)機(jī)的狀態(tài)依次發(fā)生遷移。

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

S[3] = STF(S[2], T[3])

...

S[n] = STF[S[n-1], T[n]]

簡(jiǎn)單地，我們也可以將 T[1], T[2], ..., T[n] 看作一個(gè)整體，則狀態(tài)遷移過(guò)程可以簡(jiǎn)化為

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

更一般地，假設(shè)當(dāng)前狀態(tài)機(jī)的狀態(tài)是 PRE_STATE，然后有 n 個(gè) Action T[1], T[2], ..., T[n] 依次作用到狀態(tài)機(jī)上，之后狀態(tài)機(jī)的狀態(tài)是 POST_STATE，此可以表示為

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

如果將以上 Action 換成轉(zhuǎn)賬交易 transaction，把 系統(tǒng)中的賬戶(hù)集合看作是一個(gè)狀態(tài)機(jī)，那么整個(gè)過(guò)程也就是鏈上交易執(zhí)行的過(guò)程了。交易的執(zhí)行，使得整個(gè)鏈上的全局狀態(tài)發(fā)生變化。鏈上的全局狀態(tài)也就是各個(gè)賬戶(hù)的狀態(tài)集合，將所有賬戶(hù)的狀態(tài)組成一棵 Merkle 樹(shù)，樹(shù)的葉子節(jié)點(diǎn)是賬戶(hù)狀態(tài)，樹(shù)的根可以直接用來(lái)表示狀態(tài)集合。因此，上述的 PRE_STATE 和 POST_STATE 也就是全局賬戶(hù)狀態(tài)樹(shù)的根。

賬戶(hù)狀態(tài)模型

剛才我們提到鏈上的整個(gè)系統(tǒng)中的賬戶(hù)狀態(tài)，可由一棵 Merkle 樹(shù)來(lái)管理。Merkle 樹(shù)的葉子節(jié)點(diǎn)，即用戶(hù)的狀態(tài)信息。同樣，鏈下擴(kuò)容方案 zk Rollup 也可以用類(lèi)似的 Merkle 樹(shù)來(lái)組織其賬戶(hù)狀態(tài)。

最簡(jiǎn)單的賬戶(hù)狀態(tài)可以包含：賬戶(hù)的 public key，nonce 和 balance。而葉子節(jié)點(diǎn)在Merkle 樹(shù)中是有唯一位置的，因此位置的索引信息可間接引用這個(gè)賬戶(hù)信息。

如果我們用3個(gè)字節(jié)來(lái)表示這個(gè)索引信息的話(huà)，那么這棵 Merkle 樹(shù)總共可以支持 2^24 = 16,777,216 個(gè)賬戶(hù)。這對(duì)于一般的系統(tǒng)來(lái)說(shuō)已經(jīng)足夠。因此，以太坊為例，賬戶(hù)地址可以由 address 的 20個(gè)字節(jié) 轉(zhuǎn)為 Merkle 樹(shù)的葉子節(jié)點(diǎn)索引 3 個(gè)字節(jié)。這樣賬戶(hù)地址就被“壓縮”了。

除了對(duì)賬戶(hù)地址進(jìn)行壓縮，我們也可以對(duì)轉(zhuǎn)賬金額數(shù)據(jù)進(jìn)行壓縮。例如，在以太坊上金額用256位的大整型來(lái)表示，但是實(shí)際使用過(guò)程中幾乎很少用到超大金額和超小的金額。因此如果我們就假設(shè)系統(tǒng)中轉(zhuǎn)賬的最小單位是 0.001 ETH，并且用 4 個(gè)字節(jié)來(lái)表示轉(zhuǎn)賬金額的話(huà)，我們就可以支持 0.001 ~ 4,294,967.295 ETH 的轉(zhuǎn)賬，這對(duì)于一般的系統(tǒng)來(lái)說(shuō)也已經(jīng)夠了。如果還不夠可以適當(dāng)再增加字節(jié)來(lái)表示金額，或者引入浮點(diǎn)數(shù)表示方式。

手續(xù)費(fèi)與轉(zhuǎn)賬金額類(lèi)似，實(shí)際手續(xù)費(fèi)會(huì)在一定的范圍之內(nèi)浮動(dòng)，因此我們也可以為手續(xù)費(fèi)設(shè)定一個(gè)最小單位，例如：0.001 ETH。然后用 1 個(gè)字節(jié)來(lái)表示 0.001 ~ 0.255 ETH 的手續(xù)費(fèi)。這里的手續(xù)費(fèi)也就是 transactor 向 relayer 支付的手續(xù)費(fèi)。

同樣，我們假設(shè)在正常使用環(huán)境下一個(gè)賬戶(hù)的轉(zhuǎn)賬次數(shù)不會(huì)達(dá)到上萬(wàn)次，因此用2個(gè)字節(jié)來(lái)表示賬戶(hù)的 nonce 也差不多夠了，因?yàn)?2 個(gè)字節(jié) 可以表示的范圍達(dá)到 0~65535。

最后簽名字段不能壓縮，以以太坊為例，簽名 (r, s, v) 總共需要 65 個(gè)字節(jié)。但實(shí)際的zk Rollup 系統(tǒng)中使用 EdDSA的較多。

因此，一個(gè) transaction 的格式大體如下：

以上 transaction 各字段的長(zhǎng)度僅作參考，在實(shí)現(xiàn)具體系統(tǒng)的時(shí)候需要根據(jù)實(shí)際情況調(diào)整字段長(zhǎng)度，以防止發(fā)生字段溢出的情況，但原則上還是能省則省。因?yàn)榻灰讛?shù)據(jù)越少，在相同存儲(chǔ)容量的前提下，所能容納的交易數(shù)也就越多。

證明和驗(yàn)證

了解了狀態(tài)遷移函數(shù)和賬戶(hù)狀態(tài)模型后，我們?cè)賮?lái)了解下 relayer 收集 transaction 后做了些什么。

我們剛才提到在 zk Rollup 的系統(tǒng)里，所有用戶(hù)的賬戶(hù)信息由一棵 Merkle 樹(shù)管理。而 Merkle 樹(shù)的根被記錄在了鏈上的智能合約里，這個(gè)根的值也代表著整個(gè)系統(tǒng)當(dāng)前所有賬戶(hù)的狀態(tài)。當(dāng)有用戶(hù)發(fā)起轉(zhuǎn)賬 transaction 時(shí)，這個(gè)狀態(tài)就要發(fā)生改變。但改變必須依照規(guī)則進(jìn)行。

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

轉(zhuǎn)出賬戶(hù)是否有足夠的錢(qián)支付轉(zhuǎn)賬金額和手續(xù)費(fèi)

轉(zhuǎn)出賬戶(hù)的 nonce 是否正確

轉(zhuǎn)賬 transaction 的簽名是否正確

· 接著，relayer 執(zhí)行該轉(zhuǎn)賬 transaction，修改 Merkle 樹(shù)中的轉(zhuǎn)出賬戶(hù)和轉(zhuǎn)入賬戶(hù)的葉子節(jié)點(diǎn)，然后重新計(jì)算新的 Merkle 樹(shù)的根。

· 重復(fù)第二步，relayer 會(huì)按照先后順序一次性處理多個(gè) transaction，然后將最后計(jì)算得到的 Merkle 樹(shù)的根作為新的狀態(tài)提交到鏈上合約中。

但上述流程存在問(wèn)題：如果僅提交狀態(tài)樹(shù)的根到合約，那么用戶(hù)如何相信新的狀態(tài)根是如實(shí)地根據(jù)上述邏輯計(jì)算出來(lái)的。萬(wàn)一 relayer 作惡，故意調(diào)大 transaction 的手續(xù)費(fèi)呢?

解決這個(gè)問(wèn)題的一個(gè)方法是，要求 relayer 提交狀態(tài)樹(shù)的根到合約時(shí)，同時(shí)也將所有 transaction 提交到合約，這樣任何人都可以根據(jù)這些 transaction 來(lái)驗(yàn)證 relayer 在計(jì)算新的狀態(tài)樹(shù)時(shí)，有沒(méi)有作弊。但這等于是將所有鏈下的數(shù)據(jù)搬回了鏈上，沒(méi)有實(shí)現(xiàn) layer 2 擴(kuò)容的目的。

利用零知識(shí)證明就可以很好地解決這個(gè)問(wèn)題。zk Rollup 中的 zk 也就是 zero-knowledge 的縮寫(xiě)。relayer 在收集了一系列的 transactions 后，需要用預(yù)先定義好的 ZK circuits 來(lái)生成一個(gè) PROOF：

確保每個(gè)交易 T[1], T[2], ..., T[n] 中的 nonce, value, fee 等值都沒(méi)有問(wèn)題，且 signature 正確。

確保狀態(tài)遷移過(guò)程沒(méi)有問(wèn)題，即 STF(PRE_STATE, T[1], T[2], ..., T[n]) = POST_STATE

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

然后智能合約只需要驗(yàn)證這個(gè) PROOF 是否正確。如果 PROOF 正確且合約中保存的狀態(tài)與 PRE_STATE 相等，那么新的狀態(tài) POST_STATE 將會(huì)被記錄到合約中，替換原有狀態(tài)。

由于 relayer 必須生成 zkSNARK 的 PROOF，然后才能向合約提交，因此如果 relayer 作惡 修改用戶(hù)的 transaction，那么 PROOF 將無(wú)法被驗(yàn)證通過(guò)。

另外，由于提交到鏈上的交易 t[1], t[2], ..., t[n] 是不包含 nonce 和 signature 的，因此上鏈的數(shù)據(jù)將會(huì)變得更小(上例中每個(gè) transaction 僅會(huì)有11個(gè)字節(jié)上鏈)。

此時(shí)，relayer 由于證明的限制，已經(jīng)無(wú)法修改用戶(hù)的 transaction。但是 惡意的 relayer 依然可以拒絕為某個(gè) transactor 服務(wù)，不搜集該 transactor 的 tranaction。為了防止這種行為，合約上必須支持 on-chain withdrawal，也就是任何一個(gè) transactor 都可以從鏈上將自己的 token 提走。

目前的應(yīng)用

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

此外，開(kāi)源的 zk Rollup 框架還有：

barryWhiteHat/roll_up -C++

matter-labs/rollup - rust

總結(jié)

zk Rollup 是一種新型的 Layer 2 擴(kuò)容方案，該技術(shù)的核心思想是：

· 將主鏈作為存儲(chǔ)媒介，而非共識(shí)引擎 ;

· 將交易壓縮，并在鏈下達(dá)成狀態(tài)共識(shí) ;

· 用零知識(shí)證明保證鏈下?tīng)顟B(tài)共識(shí)的安全性。

目前，zk Rollup 最典型的應(yīng)用場(chǎng)景是去中心化的交易所。

PPIO 也在積極探索 zk Rollup 技術(shù)，并嘗試將其應(yīng)用到 去中心化的帶寬和存儲(chǔ)交易領(lǐng)域中去。（PPLabs）

關(guān)鍵詞： ZK Rollup 用戶(hù)狀態(tài) Merkle樹(shù)