背景區塊鏈公鏈自誕生以來，雖然大大降低了信任的門檻，但一直面臨著一個效率問題：即 TPS 不高。例如比特幣每秒僅支持7筆交易，而目前的以
背景
區塊鏈公鏈自誕生以來，雖然大大降低了信任的門檻，但一直面臨著一個效率問題：即 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）
