背景區(qū)塊鏈公鏈自誕生以來，雖然大大降低了信任的門檻，但一直面臨著一個效率問題：即 TPS 不高。例如比特幣每秒僅支持7筆交易，而目前的以
背景
區(qū)塊鏈公鏈自誕生以來，雖然大大降低了信任的門檻，但一直面臨著一個效率問題：即 TPS 不高。例如比特幣每秒僅支持7筆交易，而目前的以太坊也僅支持每秒 15 筆左右的交易。這樣的 TPS 很支持大型應用。因此業(yè)界很多技術人員嘗試為區(qū)塊鏈擴容。目前擴容方案主要有兩類：
· Layer 1 擴容方案，即直接增加鏈上的交易處理能力，這種方式也被稱為鏈上擴容。常見的技術方案有：Sharding 和 DAG;
· Layer 2 擴容方案，即將鏈上的相當一部分工作量轉移到鏈下來完成。常見的技術有：State Channel, Plasma, Truebit 和 最近比較火的 zk Rollup。
ZK Rollup 并非新概念，@barrywhitehat 在一年前提出，目前由 Matter Lab 和 den3 進行工程實現(xiàn)。
原理
· 那么，zk Rollup 背后的原理是什么?
zk Rollup 的本質是將鏈上的用戶狀態(tài)壓縮存儲在一棵 Merkle 樹中，并將用戶狀態(tài)的變更轉移到鏈下來，同時通過 zkSNARK 的證明來保證該鏈下用戶狀態(tài)變更過程的正確性。在鏈上直接處理用戶狀態(tài)的變更成本是比較高的，但是僅僅利用鏈上的智能合約來驗證一個零知識證明的 PROOF 是否正確，成本是相對低很多的。另外必要的轉賬信息也會被和證明一起提交到合約，方便用戶查賬。
兩類角色
zkRollup 系統(tǒng)中包含兩類角色：transactor 和 relayer。
· transactor，即普通用戶，對應以太坊上的外部賬戶。用戶構建轉賬交易并用私鑰簽名，然后將交易發(fā)送給 relayer。
· relayer 負責收集并驗證用戶的 transaction，之后將 transaction 批量打包，并生成 zkSNARK 的 PROOF，最終將用戶 transaction 中的核心數(shù)據(jù)和 zkSNARK 的 PROOF 以及新的全局用戶狀態(tài)的 Merkle 根提交到鏈上的智能合約。
當然 relayer 不會免費為 transactor 提供服務，畢竟 relayer 向鏈上提交證明和數(shù)據(jù)是需要消耗 gas 的。因此，transactor 向 relayer 發(fā)送的交易里，也必須包含相應的手續(xù)費。
狀態(tài)遷移函數(shù)
當 relyer 收到 transaction 后，必須 “執(zhí)行” 它。transaction 的執(zhí)行，本質上是改變相關賬戶的狀態(tài)，而 STF 就是改變賬戶狀態(tài)的函數(shù)。STF 是狀態(tài)遷移函數(shù)(state transition function)的縮寫。
狀態(tài)是針對狀態(tài)機而言的，每個狀態(tài)機在某一時刻都有一個狀態(tài)。我們可以假設某狀態(tài)機的初始狀態(tài)是 S[0]。當某個 Action T[1] 作用在該狀態(tài)機上時，狀態(tài)機的狀態(tài)發(fā)生了遷移。我們可以用以下式子來表示遷移過程。
S[1] = STF(S[0], T[1])
這里，S[0] 是初始狀態(tài)，S[1] 是狀態(tài)機執(zhí)行 Action T[1] 之后的狀態(tài)。
緊接著有新的若干 Action T[2], T[3], ..., T[n] 繼續(xù)作用在該狀態(tài)機上，則狀態(tài)機的狀態(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]]
簡單地，我們也可以將 T[1], T[2], ..., T[n] 看作一個整體，則狀態(tài)遷移過程可以簡化為
S[n] = STF(S[0], T[1], T[2], ..., T[n])
更一般地，假設當前狀態(tài)機的狀態(tài)是 PRE_STATE，然后有 n 個 Action T[1], T[2], ..., T[n] 依次作用到狀態(tài)機上，之后狀態(tài)機的狀態(tài)是 POST_STATE，此可以表示為
`POST_STATE = STF(PRE_STATE, T[1], T[2], ..., T[n])`
如果將以上 Action 換成轉賬交易 transaction，把 系統(tǒng)中的賬戶集合看作是一個狀態(tài)機，那么整個過程也就是鏈上交易執(zhí)行的過程了。交易的執(zhí)行，使得整個鏈上的全局狀態(tài)發(fā)生變化。鏈上的全局狀態(tài)也就是各個賬戶的狀態(tài)集合，將所有賬戶的狀態(tài)組成一棵 Merkle 樹，樹的葉子節(jié)點是賬戶狀態(tài)，樹的根可以直接用來表示狀態(tài)集合。因此，上述的 PRE_STATE 和 POST_STATE 也就是全局賬戶狀態(tài)樹的根。
賬戶狀態(tài)模型
剛才我們提到鏈上的整個系統(tǒng)中的賬戶狀態(tài)，可由一棵 Merkle 樹來管理。Merkle 樹的葉子節(jié)點，即用戶的狀態(tài)信息。同樣，鏈下擴容方案 zk Rollup 也可以用類似的 Merkle 樹來組織其賬戶狀態(tài)。
最簡單的賬戶狀態(tài)可以包含：賬戶的 public key，nonce 和 balance。而葉子節(jié)點在Merkle 樹中是有唯一位置的，因此位置的索引信息可間接引用這個賬戶信息。
如果我們用3個字節(jié)來表示這個索引信息的話，那么這棵 Merkle 樹總共可以支持 2^24 = 16,777,216 個賬戶。這對于一般的系統(tǒng)來說已經足夠。因此，以太坊為例，賬戶地址可以由 address 的 20個字節(jié) 轉為 Merkle 樹的葉子節(jié)點索引 3 個字節(jié)。這樣賬戶地址就被“壓縮”了。
除了對賬戶地址進行壓縮，我們也可以對轉賬金額數(shù)據(jù)進行壓縮。例如，在以太坊上金額用256位的大整型來表示，但是實際使用過程中幾乎很少用到超大金額和超小的金額。因此如果我們就假設系統(tǒng)中轉賬的最小單位是 0.001 ETH，并且用 4 個字節(jié)來表示轉賬金額的話，我們就可以支持 0.001 ~ 4,294,967.295 ETH 的轉賬，這對于一般的系統(tǒng)來說也已經夠了。如果還不夠可以適當再增加字節(jié)來表示金額，或者引入浮點數(shù)表示方式。
手續(xù)費與轉賬金額類似，實際手續(xù)費會在一定的范圍之內浮動，因此我們也可以為手續(xù)費設定一個最小單位，例如：0.001 ETH。然后用 1 個字節(jié)來表示 0.001 ~ 0.255 ETH 的手續(xù)費。這里的手續(xù)費也就是 transactor 向 relayer 支付的手續(xù)費。
同樣，我們假設在正常使用環(huán)境下一個賬戶的轉賬次數(shù)不會達到上萬次，因此用2個字節(jié)來表示賬戶的 nonce 也差不多夠了，因為 2 個字節(jié) 可以表示的范圍達到 0~65535。
最后簽名字段不能壓縮，以以太坊為例，簽名 (r, s, v) 總共需要 65 個字節(jié)。但實際的zk Rollup 系統(tǒng)中使用 EdDSA的較多。
因此，一個 transaction 的格式大體如下：
以上 transaction 各字段的長度僅作參考，在實現(xiàn)具體系統(tǒng)的時候需要根據(jù)實際情況調整字段長度，以防止發(fā)生字段溢出的情況，但原則上還是能省則省。因為交易數(shù)據(jù)越少，在相同存儲容量的前提下，所能容納的交易數(shù)也就越多。
證明和驗證
了解了狀態(tài)遷移函數(shù)和賬戶狀態(tài)模型后，我們再來了解下 relayer 收集 transaction 后做了些什么。
我們剛才提到在 zk Rollup 的系統(tǒng)里，所有用戶的賬戶信息由一棵 Merkle 樹管理。而 Merkle 樹的根被記錄在了鏈上的智能合約里，這個根的值也代表著整個系統(tǒng)當前所有賬戶的狀態(tài)。當有用戶發(fā)起轉賬 transaction 時，這個狀態(tài)就要發(fā)生改變。但改變必須依照規(guī)則進行。
· 首先，必須要確保 transaction 的合法性：
轉出賬戶是否有足夠的錢支付轉賬金額和手續(xù)費
轉出賬戶的 nonce 是否正確
轉賬 transaction 的簽名是否正確
· 接著，relayer 執(zhí)行該轉賬 transaction，修改 Merkle 樹中的轉出賬戶和轉入賬戶的葉子節(jié)點，然后重新計算新的 Merkle 樹的根。
· 重復第二步，relayer 會按照先后順序一次性處理多個 transaction，然后將最后計算得到的 Merkle 樹的根作為新的狀態(tài)提交到鏈上合約中。
但上述流程存在問題：如果僅提交狀態(tài)樹的根到合約，那么用戶如何相信新的狀態(tài)根是如實地根據(jù)上述邏輯計算出來的。萬一 relayer 作惡，故意調大 transaction 的手續(xù)費呢?
解決這個問題的一個方法是，要求 relayer 提交狀態(tài)樹的根到合約時，同時也將所有 transaction 提交到合約，這樣任何人都可以根據(jù)這些 transaction 來驗證 relayer 在計算新的狀態(tài)樹時，有沒有作弊。但這等于是將所有鏈下的數(shù)據(jù)搬回了鏈上，沒有實現(xiàn) layer 2 擴容的目的。
利用零知識證明就可以很好地解決這個問題。zk Rollup 中的 zk 也就是 zero-knowledge 的縮寫。relayer 在收集了一系列的 transactions 后，需要用預先定義好的 ZK circuits 來生成一個 PROOF：
確保每個交易 T[1], T[2], ..., T[n] 中的 nonce, value, fee 等值都沒有問題，且 signature 正確。
確保狀態(tài)遷移過程沒有問題，即 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 正確且合約中保存的狀態(tài)與 PRE_STATE 相等，那么新的狀態(tài) POST_STATE 將會被記錄到合約中，替換原有狀態(tài)。
由于 relayer 必須生成 zkSNARK 的 PROOF，然后才能向合約提交，因此如果 relayer 作惡 修改用戶的 transaction，那么 PROOF 將無法被驗證通過。
另外，由于提交到鏈上的交易 t[1], t[2], ..., t[n] 是不包含 nonce 和 signature 的，因此上鏈的數(shù)據(jù)將會變得更小(上例中每個 transaction 僅會有11個字節(jié)上鏈)。
此時，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 擴容方案，該技術的核心思想是：
· 將主鏈作為存儲媒介，而非共識引擎 ;
· 將交易壓縮，并在鏈下達成狀態(tài)共識 ;
· 用零知識證明保證鏈下狀態(tài)共識的安全性。
目前，zk Rollup 最典型的應用場景是去中心化的交易所。
PPIO 也在積極探索 zk Rollup 技術，并嘗試將其應用到 去中心化的帶寬和存儲交易領域中去。（PPLabs）
