ZK Rollup & Optimistic Rollup

ZK Rollup不是一個新的提案，大約在一年前被Barry Whitehat所提出，同時間Vitalik在以太坊研究員的論壇有一篇比較完整的文章解釋，現在由Matter Lab在開發。研究完zk-SNARKs之後，一直沒空來看，直到最近才有機會來深入瞭解。除了ZK Rollup，也會簡單帶一下前陣子在Plasma Group所提出的Optimistic Rollup。

ZK Rollup一開始提出來的時候，是被定義為layer 2的解決方案，年初的時候一度以Plasma Ignis這個名稱作為發表。應該是因為去年Plasma很紅，一直不斷有新的提案跟進展，加上這當時也被定義為layer 2的解決方案，這些種種原因，開發者就冠上了Plasma的名稱，不過因為這項技術跟Plasma的精神完全不一樣，被社群抗議，後來就恢復到Rollup這個名稱（開發者的聲明），所以搜尋 'Plasma Ignis'會找不到什麼東西。到最近，Rollup被更名為semi-layer 2的解決方案，就是有一點layer 2但又沒這麼layer 2... XD

簡單一句話解釋ZK Rollup就是，資料放在鏈上的layer 2解決方案。在瞭解ZK Rollup之前，先來解釋原本layer 2有什麼問題。以Plasma為例，Plasma鏈只把Plasma區塊的hash放上Ethereum主鏈上做公正（欲瞭解Plasma可以參考這裡），也就是在鏈下交易了數百或數千筆的交易，最後上鏈只有幾十個bytes，這是鏈下交易的精神，但也是設計上最麻煩的地方 - 資料的可取得性。

就是當有人要離開這個鏈時，需要一個額外的遊戲規則，在Plasma叫做挑戰期（因為鏈上沒有資料，需要側鏈參與者的提供證據），這衍生了有資料才能挑戰，所以大家都要存一定數量的資料，相較於跟主鏈的互動，只需要裝一個錢包，並不需要下載區塊資料，使用者體驗上差異很大。挑戰期的另一個問題是，使用者需要保持上線狀態，不然錯過挑戰期，就代表默認了交易（因為是採用詐欺證明並非是有效性證明）。簡單來說，因為資料的可取得性問題，衍生了

 1.使用者需要常在線上

 2. 需下載部分資料

而造成使用者體驗很糟（當然現在的Plasma設計已經改進了不少）

如何資料放在鏈上，又不會造成資料過大呢？

首先，先介紹整體架構。跟Plasma一樣，有一個智能合約做擔保，有中繼者(relayer)幫忙送交易到智能合約（在Plasma叫operator），中繼者除了送交易外，還需要產生SNARK證明，一起送上鏈做驗證。

智能合約的部分，可以想像跟ERC20一樣，在合約裡記每個參與者的帳，差別在於，標準的ERC20交易是由Ethereum這系統做驗證，也因此不能合併（因為這就是Ethereum的標準交易），而Rollup中，是把好幾筆交易包成一個標準交易，對Ethereum這個系統，就是一個交易，而驗證交易的有效性則由智能合約做驗證。

實際在智能合約裡，用兩個merkle tree做紀錄，一棵樹是紀錄地址，所以只需要樹的索引值就可以代表一個位址（未註冊的索引值內容為0），因此位址的資料量就從原本的20 bytes減少到只有3 bytes，另一棵樹則記錄balance跟nonce。

這是資料格式（這是最初的提案，後來的實作交易量更小），

From	To	Value	Fee	Nonce
3 bytes	3 bytes	6 bytes	1 byte	2 bytes

因為用索引值當地址的代表，所以只需要3 bytes（2^24個位址），Value的部分是以10^-6當作基底，這樣只需要15 bytes就可以代表一筆交易，而儲存這樣一筆交易大約只需要 892 gas（雖然Value是6 bytes，但是文章中的假設大部分的交易只會使用到4 bytes，所以算法是13 bytes * 68 + 2 bytes * 4 = 892），而一般ether的轉移需要21K gas，因此交易速度能提升（所以Vitalik的文章標題是"On-chain scaling to potentially ~500 tx/sec through mass tx validation"）。

為什麼交易速度能提升？也順便來瞭解一下交易速度

現今以太坊每個區塊的gas上限約8M，所以若單純ether交易，速度約略是

8M / 21K / 15 ~= 25 tps

所以現在的交易瓶頸其實是gas 的問題，下降交易手續費或是提升區塊gas上限，都能適時紓困（但也會造成衍伸的問題），而ZK Rollup就是藉由交易數據量(size)的減少，進而能增加交易速度。那來看一下使用ZK Rollup後交易速度能到多快

(8M - 600K (zk-SNARK驗證) - 50K（預計合約運行的gas花費）) / 892 / 15 ~= 550 tps

這個數字就是Vitalik文章的標頭"On-chain scaling to potentially ~500 tx/sec"。但實際上並沒有這麼理想，在作者Barry的實作中，大約只有268 tps，因為每次資產的更新都會留下event，所以有多餘的gas花費，然而，這樣的設計在應用上也是比較親切的。

資料都在鏈上，而且透過zk-SNARK做驗證，代表著上鏈的資料都是被驗證過的，因此就沒有一開始layer 2遇到的問題，需要挑戰、需要下載資料等等。這也隱含著不需要信任中繼者，因為他們無法作壞，最多就是不幫你送交易。

事情沒有這麼美好...

大家都覺得zk-SNARK像個萬靈丹一樣，用了好像什麼事都解決了，不過實際上並沒有這麼完美。zk-SNARK除了需要初始設定之外，最大的問題就是需要大量的運算力，在 Barry提供的數據中，中繼者的電腦若是一台8G記憶體加上20G的硬碟swap，大概只能產生 20 tx/sec，遠遠不及預期的500tps或是實作的200多tps。所以這個方案最大的問題在於要怎麼解決算力問題。

平行運算！

Matter Lab使用了多中繼者模型跟平行運算。多中繼者的模型，很像小型的區塊鏈，使用了DPOS (Delegated Proof of Stake)，還有隨機挑選區塊產生者，所以被挑選到的區塊產生者，就可以收集交易、產生證明並且上鏈。這樣的方法避免了中心化，若中繼者被惡意攻擊，整個網路還是能運作得下去，另一方面，也為平行運算做了鋪路。零知識證明的產生非常花時間，因此基於多中繼者模型，Matter Lab提出了"上鏈-驗證"兩階段的方式，也就是中繼者先把資料上鏈，下一個階段再上傳證明做驗證，進而達到平行運算（如下圖）。再加上一些資料的最佳化，測試結果可達到1600 tps。

https://medium.com/matter-labs/introducing-matter-testnet-502fab5a6f17

延遲...

聽似很美好，但是因為你的交易被分兩階段上鏈，也就是從送出到到被驗證，會是好幾個區塊，時間比原本單純上鏈時間會更久。當然，延遲多久是使用者可接受的，這目前也無從得知。這是一個取捨，省了手續費，增加了交易速度，卻也增加了時間的延遲，這一切也要等上線後才會知道。

今年初，Vitalik在台北的線下聚會中分享了ZK Rollup的進階版 - ZK ZK Rollup，有興趣的人可以參考這篇文章，記錄的很詳細。

Plasma & Optimistic Rollup

Optimistic Rollup在設計上跟Plasma相關，所以只會簡單帶一下差異。

Karl（註）基於ZK Rollup的設計，在上個月提出Optimistic Rollup，概念上也是把資料都放鏈上，但不是用zk-SNARK做驗證，因為希望能達成更普遍性的應用。而不一樣的地方有，把from的部分，改為使用者的簽章(65 bytes)，因為資料量變大的，可想而知，花的gas會更多，交易速度就會不及ZK Rollup。另一部份是，因為不是用zk-SNARK做驗證，就需要資料驗證的輔助方法（validity game），這邊就不詳細介紹，有機會在寫一篇Plasma/Optimistic Rollup的詳細介紹。
在估算上，交易速度約是100 tps，若簽章方式改為BLS，約可提升到450 tps。而在10月的硬分岔後，gas會下降，預估的交易速度也會分別到達400/2000 tps。（許願：希望有人可以介紹一下10月的硬分岔細節 XD）

註：在中文的媒體文章中，都稱他是Casper的核心研究員之一，但是從我一開始知道這個人，都是在大力宣揚Plasma，他的部落格、twitter都是跟Plasma相關的文章，不確定他在Plasma Group的角色，但我是把他定位成Plasma Group的leader

文章內容若有錯誤或是不同觀點，歡迎指教

reference:
On-chain scaling to potentially ~500 tx/sec through mass tx validation
Introducing Matter Testnet
Optimistic Rollup