寫在前面的話：
算是想了很久，加上個人最近工作上的變動，這篇又拖了很久，猶豫再三，決定這篇結合我自己的研究，來寫一寫區塊鏈領域的熱門問題——擴容和區塊鏈不可能三角。
我看過不少介紹可擴展性和不可能三角的文章，中文和英文都有，甚至不乏一些知名作者或者著名研究機構的文章，但是沒有一篇能夠非常準確的完全解釋清楚這個問題。不太客氣地說，幾乎每篇文章裡總會有那麼幾句話會讓我皺起眉頭：“等等這裡寫得不對”。所以，我決定在這裡用一個系列詳細地解釋這個問題。
那麼，憑什麼這篇會比其他的好一些呢？
實際上，區塊鏈可擴展性，也就是不可能三角的這個問題，是我之前研究的主要方向，也是我一直想要寫的東西。但是，具體到成文其實我斟酌了很久。猶豫的主要原因是，我個人其實比較牴觸在科普文章裡夾私貨這種行為——我的答案裡我會盡量分清科普的部分和個人意見的部分，而如果我要寫科普文章的話，我會寫一些更中立更經過檢驗的內容，而儘量避免仍舊爭議或未經過同行評議的創新性內容。而且，由於應該說在區塊鏈這個領域目前的現狀是——大部分搞科普和媒體的人對於區塊鏈技術不夠專業，而大部分專業的人多多少少都是利益相關方，於是這個專欄的定位是希望創造一個“沒有利益相關的專業視角”的原創技術專欄，因此我一直在刻意去避免自己成為某個“利益相關方”而失去了科普的中立性（當然，這完全是個人選擇問題，有些區塊鏈從業者的科普也做得很好）。
基於以上的原因，我一直都沒有在我的專欄裡介紹關於我自己的研究和成果，一方面，之前的成果還有待完善，另一方面，我也擔心介紹不成熟的論點有悖於這個專欄的定位。不過，最終還是考慮在現在把這個東西寫出來的原因，主要是因為我的論文“VAPOR: a Value-Centric Blockchain that is Scale-out, Decentralized, and Flexible by Design”在剛剛結束的Financial Crypto 2019上正式發表，因此，我覺得現在我比較有底氣來寫一寫關於不可能三角的問題，也介紹一下自己對於這個問題的解決方案。
為了證明自己確實在區塊鏈可擴展性領域有一定的發言權，可能在這裡還是需要介紹一下我的一些工作：
我關於區塊鏈無限擴展的第一篇論文Implicit Consensus: Blockchain with Unbounded Throughput於2017年5月上傳arxiv，算是最早的關於無限擴展（scale-out）的論文之一，如果說投稿的時間的話，其實比公認最早的無限擴展方案omniledger上傳arxiv的時間還要早兩天。不過其實這沒有什麼值得說的，因為它沒有正式在學術會議或期刊上發表，而且，從現在看起來，確實想法不算很成熟，關於無限擴展的原因沒有寫到點上。這篇文章的另一個偏工程實現的版本，發表於IFIP Networking 2018，叫A Blockchain Consensus Protocol With Horizontal Scalability。
後來，我把這篇文章的共識部分抽象出來進行了更嚴謹的證明，並且提出了Spontaneous Sharding（自主分片）的概念並做了實驗室的仿真證明無限擴展的可能性，即：A Scale-Out Blockchain for Value Transfer with Spontaneous Sharding。這篇論文發表在Crypto Valley Conference on Blockchain Technology 2018上，這個會議據稱（主辦方說的）是IEEE的第一個區塊鏈會議，雖然是個新會議，影響力遠不及相關領域的頂會，名字聽起來也很山寨，但是這個會確實是個正經的學術會議，審稿也很嚴格，技術委員會看起來簡直是全明星陣容（主席包括康奈爾大學的Emin Gun Sirer教授），這也是我當時投這個會的原因。
我去年下半年的主要工作就是把這個共識算法可以達到無限擴展的原因再次抽象出來，並且針對這個原因提出了“價值中心區塊鏈（Value-centric Blockchain）”的概念和理論結構，並且論證了這種結構實際上在實現“價值轉移”，換句話說就是虛擬貨幣的基本功能上，比傳統區塊鏈的結構擁有許多優勢，最重要的是，應該天然是無限擴展的。這篇論文最終在去年年底被Financial Cryptography and Data Security 2019（FC2019）接收，並且在今年二月20號發表了，就是上文中提到的那一篇。
在這裡我說一下FC。關於FC，也許非密碼學專業甚至非應用密碼學領域的人聽起來都有些陌生，在中科院的排名也只是C類（我是後來才知道還有中科院排名這回事。。。）。但是，這個會議在應用密碼學領域，本就是聲望卓著的頂會之一。而如果要具體到“區塊鏈”這個剛剛出現在學術界沒多久的領域的話，那麼FC應該毫無疑問的是區塊鏈領域的頂會。這其中有兩個原因，一是歷史原因：FC是最早開始接受關於比特幣和區塊鏈論文的會議之一，也是最早加入了比特幣workshop的會議（相比於這兩年陸陸續續的有不少相關領域的會議加入了關於區塊鏈的workshop，FC早在2014年就加入了Bitcoin Workshop），許多關於比特幣的重要論文都發表在這個會或者是BW上，例如selfish mining的論文，共識算法Ghost的論文，關於可擴展性的position paper：On scaling decentralized blockchain等等。這其中更深層次的原因是因為這個會的參會者的研究領域本來就與數字貨幣高度重合，所以這些人也成為了第一批學術界中接納並開始研究比特幣的學者，到了今年，由於區塊鏈的熱度已經上升成為金融密碼學領域最熱門的研究問題，以及其實際上已經無法界定哪些論文應該發表在主會而哪些應該發表在BW中，因此，主辦方今年將BW併入了主會。第二個原因其實也和第一個原因相輔相成——到目前為止，FC（以及BW）的技術委員會都可以說是世界上最懂區塊鏈的那批人，而也正是因此，對於一篇關於區塊鏈的論文而言，FC是能夠收到最客觀和最有意義的審稿人意見的會議，同時，也是在區塊鏈上的學術貢獻最容易被發現和認可的地方。
這個是FC2019的網站：Financial Cryptography 2019
迴歸正題：擴容（Scaling）與擴展（Scaling）與可擴展的（Scalable）與可擴展性（Scalability）
以上這幾個概念毫無疑問都是區塊鏈領域的熱詞，但是，如果你是一個嚴謹的學者，或者，你只是喜歡刨根問底，想要真正從媒體或者白皮書乃至論文裡想要搞清楚頻繁出現的Scalability和Scaling到底是個什麼意思，我估計你八成會被搞瘋，因為很多論文裡面說的scaling根本就不是一個事。但如果你恰巧又不是英文讀者的話，那麼這種混亂也許會被加劇，因為scaling在不同的語境下也許會被翻成擴容或擴展。總之，標題裡提到的這三個詞在區塊鏈領域沒有任何確切的定義，在不同的語境中他們可能有不同的意義，甚至，在有些白皮書中這個詞可能沒有任何意義。換句話說，當你在白皮書上看到“這是個可擴展的區塊鏈”或者“解決了可擴展性問題”又或者“可擴展的共識算法”的時候，在不結合上下文的情況下，你壓根就不知道它指的是什麼。
出現這種情況的原因，我認為，是因為區塊鏈本身就是個沒有嚴謹定義的領域，而Scalability在各領域中又有不一樣的定義，因此，當不同領域的人來按照自己的想法定義Scalability的問題，而沒有一篇共同承認的權威論文或者教材做出某個大家都認可的定義時，就變成了現在這個樣子——人人都可以從自己的角度上去說自己的系統是可擴展的。而接下來，由於大部分人都很難理解這些不同方案之間關於可擴展性的區別，於是，很多概述文、科普文、媒體文將各種可擴展混為一談就更加劇了這種混亂。
可擴展的第一個定義——可擴展的POW
我們來先說說什麼是scalable（可擴展的）。在不加任何限定下，這是指某個表現x隨著某個變量y的增長的變化情況，如果x能夠隨著y的增長而線性增長，我們會說x是linear scalable的，或者就簡單地說是scalable的。換句話說，如果我們定一個很高的目標x，如果我們知道“這種東西我們只要用某f方法，然後把y堆起來就一定可以達到”，那麼我們就說這個f方法是scalable的。
然後，在很早之前，人們就已經意識到比特幣是不scalable的——因為想要提升比特幣的7TPS，尤其是想要把它提高到能和傳統支付手段相比的輸出，例如10000TPS，我們能做的事很有限。最自然而然的方法是加大區塊大小，或者降低區塊間隔，而因為即便沒有嚴謹的數學分析和證明，人們也知道這是不可能的，因為要是把區塊加大1000倍到一個G然後十分鐘一個區塊，不說別的，就是放在當時的網速也不允許。
然而，其實制約區塊大小和區塊間隔的遠遠不止傳輸區塊的網速。定量的分析大家可以參照前文提到的On Scaling Decentralized Blockchain那篇論文，而定性的解釋是——
比特幣的POW算法裡，安全性依賴於區塊同步速度遠小於區塊間隔的前提。
比特幣的安全性的前提是——假設所有礦工都是逐利的，那麼任何人想要作弊，都需要打敗50%的算力，因為你必須要擁有超過其他人的算力，才能挖出比別人更長的鏈。然而，這個競爭是公平的前提是，作弊者和其他所有人都在挖同一條鏈，即全網對於當前最長鏈在大多數時間裡是同步的。然而，對於比特幣而言，這是不一定的。而這也是比特幣的POW和傳統分佈式系統的算法不一樣的地方——比特幣中允許網絡中出現短暫的不一致，即分叉，即網絡中的兩部分不同節點同時分別認為兩條不同的鏈是合法的。這個時候，如果惡意節點想要挖出最長的鏈，他不再需要競爭過其他所有人了。假設一個分叉中兩條鏈各被50%的算力接受，那麼這個時候一個惡意節點只要擁有超過25%的算力就能夠有超過50%的概率挖到下一個區塊了。於是，如果比特幣中總是擁有兩條分叉，我們其實可以認為比特幣的安全性下降了一半。
看到這裡也許大家還不理解——比特幣不是很少出現分叉，而且一般分叉很快就會消失嗎？為什麼會有“比特幣中多數時間都在分叉”的情況出現呢？
這裡，大家來回想一下分叉是怎麼出現的——當A挖到一個塊的時候，A會盡快把這個塊公佈到全網，越多的人知道，就越多人會繼續在後面挖礦，於是這一條鏈比別人長的可能性就越大，於是這一塊最終出現在最長鏈上的可能性就越高——而在比特幣中，只有最長鏈上的才是最終結果。然而，如果A的這塊還沒有被網絡中的另一點B收到的時候，B也挖到了一塊，而B在不知道A挖到這塊的前提下，也會做同樣的事情，於是就產生了分叉，而網絡也會被分割成兩部分，先收到A的塊的就會認為A的鏈更有前途，在後面繼續挖，反之亦然。在現在的比特幣網絡中，一個區塊是1M，傳輸和驗證起來都比較快，所以需要把一個區塊同步到全網的時間很短，只有當兩個節點在這段時間裡同時挖到區塊才可能產生分叉。因此，如果這個延遲遠小於區塊間隔的話，分叉的概率就會很小，而連續幾次分叉的概率就更小，所以大概率分叉在一個區塊後就會結束，留下一個深度1的孤塊。而如果我們加大區塊大小，或者縮短區塊間隔，使得同步區塊的時間和區塊間隔的比例沒有那麼懸殊的時候那麼同步所需要的時間就會變長，於是產生分叉的可能性就會增加。而如果同步區塊時間超過了區塊間隔，那麼分叉數量就永遠不會減少，而是會越來越多。
區塊大小增大導致區塊傳輸延遲增大，於是區塊延遲/區塊間隔的比例增大導致網絡中可能出現分叉的幾率增大。同理，如果減小區塊間隔也會造成一樣的結果。
而如果網絡中一直有分叉，很難收斂，那麼就總有人不是在最終的最長鏈上挖礦，於是整個網絡的安全性就達不到POW理論上的50%的水平；而分叉無法收斂，則不僅僅是安全性下降，而是交易永遠無法確認。
後者不僅僅侷限於比特幣的POW算法，而可以說是區塊鏈不可能三角或者說分佈式系統CAP的問題——如果網速跟不上區塊傳播速度，無論如何這個系統是不可能保證一致的。
但前者，則是比特幣POW算法上的限制。
從這個角度講，比特幣不可擴展——因為它的輸出不能隨著擴大區塊大小（減小區塊間隔）而在碰上網速的邊界之前無限提升，而是在那之前就先碰上比特幣POW算法自身安全性對於同步依賴的邊界了。
於是，也是出於同樣的角度，我們想要改進比特幣的POW算法，使得它能夠擺脫安全性對於同步性的依賴，使得我們能夠簡單地通過擴大區塊大小（減小區塊間隔）來提升輸出，直到遇到網速的邊界為止，這類的嘗試，我們稱為“擴展比特幣（Scaling Bitcoin）”，而這樣的算法，則可以稱為“可擴展的POW算法”，因為，相比於比特幣的POW，它們從這個角度上來講更可擴展了。
這一類算法例如Bitcoin-NG，GHOST，Hybrid Consensus等。然後，可擴展性也在同一級別的還包括使用了類比特幣POW結構的POS例如Snow White和Ouroboros，我們下期再詳細介紹。
可擴展的第二個定義——無限擴展
看到這裡，可擴展的定義似乎沒什麼爭議——實際上，一開始當沒有區塊鏈只有比特幣的時候，談到可擴展，就是第一個定義。
那什麼時候開始“可擴展”這個詞又有了新的意思呢？
大概是從傳統分佈式系統的人開始研究比特幣開始的……
在傳統分佈式系統裡，通常scalable的定義是指系統的輸出是否能夠隨著增加節點的數量而線性增加，如果能，就是scalable的，或者叫Horizontally scalable的。所以用這個定義的話，如果一個區塊鏈系統是scalable的，那麼如果他有1000個節點的輸出是x，那麼如果我們加上1000個節點，輸出應該變成2x。比如，如果把比特幣的網絡擴大一倍，那麼TPS應該翻倍。
然而，如上所述，比特幣並沒有這樣的性質——比特幣的算法決定了它的輸出就是7TPS。
因此，比特幣是不scalable的。
但是，其實這帶來了一個問題——從這個角度講，就算是第一個定義中可擴展的POW也不是scalable的，即便到現在為止，也幾乎沒有哪個區塊鏈是scalable的，其實這也好理解——一個linear scalable的分佈式系統中，每增加一臺服務器它都能增加相應的輸出的原因是，新增加的這臺服務器可以獨立承擔一部分任務。
而區塊鏈和傳統數據庫不同，它幾乎一定在某種程度上需要多個節點存儲同樣的數據（傳統分佈式數據庫的人管這叫異地多活，冗餘設計），否則就失去了去中心的意義，所以，一定從某種程度上，它無法達到多出幾個節點就提高多少輸出的效果。除非，它要做出一定的安全性犧牲，或者可信假設，而這就是總是被人津津樂道的“區塊鏈不可能三角”。
因此，很多人詬病對於這種scalable的追求——他們認為犧牲了安全性和去中心化而盲目追求高輸出，就失去了區塊鏈的意義。
然而，即便如此，高輸出的吸引力還是巨大的——區塊鏈出現之後，人們總是把區塊鏈對標互聯網，也總是把公鏈對標未來的互聯網獨角獸。然而，如果區塊鏈達不到這樣的可擴展性，那麼它的輸出最終會受制於網絡，是無論如何支撐不起互聯網獨角獸的場景的。為了將這種可擴展和之前所說的可擴展區分開，在區塊鏈共識算法的語境下，這種被稱為scale-out，即無限擴展。
總體來說，能夠達到無限擴展目前的方法有兩類——鏈下技術和分片，前者其實本身就不在不可能三角的框架之中，從我的角度看，更多的是一種把區塊鏈當成可信中介，然後根據不同應用和場景，然後考慮不同區塊鏈的特性，提出一個可以藉由區塊鏈的鏈下解決方案。例如鏈下支付通道，實際上就是儲值卡這種針對小額高頻交易的解決方案在區塊鏈場景中的映射。從理論上來講，鏈下技術和鏈上最大的區別在於BFT中的一致性（見上一篇），鏈上技術需要共識算法保證交易的一致性（儘管可能會需要在安全性或者去中心上做出妥協），而鏈下技術中交易的一致性共識算法本身是不管的，而依賴於鏈下方案本身的設計以及雙方根據場景對鏈下的協商。
但是，在學術界，通常不用scale-out這個詞來形容鏈下算法——因為就如我之前說的，鏈下算法天然scale-out，所以沒有必要再特地去用這個詞來形容。所以，一般說道scale-out都是分片算法，能夠歸於這一類的算法包括Omniledger，Chainspace，和
老師的Monoxide，以及偏工程的以太坊分片和Rchain，我的方案VAPOR從結果看來也是分片，但是原理比較不同。這些，我最後一部分再詳述。
從這種角度看來，兩者似乎和很火的另外兩個概念即“第二層（鏈下擴容）”和“第一層（鏈上擴容）”方案的定義非常類似，但是實際上，第一層和第二層的概念更多地不是從我們在這裡考慮的無限擴展角度出發的，而是從“要不要改變主鏈算法”或者“是不是通過鏈上抵押把交易挪到鏈下進行”這種角度定義的，所以，實際上，除了分片，許多達不到“無限擴展”而只是“可擴展”，即我們的第一個定義以及我們接下來要講的第三個定義的方案，也被稱為第一層方案。
這其中，最容易造成混淆的是DAG（有向無環圖）。由於一些DAG項目的宣傳，以及很多人對於DAG結構直觀印象造成的錯誤概念，DAG在很多綜述類文章中被和分片並列，認為是無限擴展的——然而，DAG只是一個概念，而把DAG用於區塊鏈的方法有很多，例如GHOST，BLOCKDAG，SPECTRE，PHANTOM，Swirld Hashgraph，IOTA，Byteball，Conflux等等。儘管DAG理論上有無限擴展的可能，但是目前的所有有具體算法的DAG方案（光有個概念的不算）中，沒有一個是無限擴展的，而都只是可擴展。
可擴展的第三個定義——可擴展的BFT
現在，如果管第一類的可擴展叫做“可擴展”，第二類叫做“無限擴展”，似乎“可擴展”這個詞也沒有什麼歧義。
然而，實際上我們還有第三個概念，就是我之前介紹過的BFT類算法。
之前我的幾篇文章中著重介紹了拜占庭容錯問題和一些重要的拜占庭容錯算法，其中，我們介紹了一個重要的拜占庭容錯算法PBFT（實用拜占庭容錯），也介紹了它的消息複雜度是O(N^2)，即，想要對一條消息（一筆交易）達成共識，需要首先將消息廣播給網絡中的每一個節點（O(N)消息複雜度），然後為了防止惡意節點夥同惡意消息發佈者故意在網絡中散播假消息導致不一致，每一個節點需要再把自己收到的消息廣播一遍，於是就有了O(N^2)的消息複雜度。
O(N^2)是個什麼概念呢？我們用可擴展性的概念去分析一下——假設每個節點的帶寬是c，那麼全網的總吞吐量上限是cN。那麼，消息複雜度是O(N^2)的概念是，如果你把節點數量翻一倍，那麼全網的帶寬變成原來的兩倍，但是所需要消耗的資源卻是原來的四倍。換句話說，傳統BFT豈止是不可擴展，簡直是可擴展的反面，所以採用BFT算法的區塊鏈的共識節點基本上都只有十幾或者幾十個。
而我在之前關於BFT的文章裡也說過了，大家一開始並沒有認為這個O(N^2)消息複雜度有啥問題，因為第一，他們一開始沒考慮實用，第二，就算有了PBFT，也只是考慮在安全條件更嚴苛分佈式數據庫中使用，並沒有考慮到區塊鏈這種大網絡的場景。
然而，當區塊鏈出現之後，人們又開始重新審視BFT的時候，O(N^2)消息複雜度就完全沒法用了。於是，人們開始考慮更“可擴展”（你看，又是這個詞）的BFT算法，即O(N)消息複雜度的BFT算法，這類BFT算法就多了，包括Honeybadger，Byzcoin，Hyperledger-Iroha，Elastico，乃至Algorand和Avalanche的BFT的部分，都屬於此類。他們確實是“使用了（更）可擴展的BFT的區塊鏈”，然而，當有的地方單純地在突出他們的優勢的時候說“可擴展”或者簡單地把他們稱為“可擴展的區塊鏈”的時候，就和第一類可擴展的POW混在一起了。雖然，我們會在後面介紹，兩者實際上最終的效果是殊途同歸的。但是，如果想要更深刻的理解這個問題，需要知道可擴展的POW和可擴展的BFT的來歷並不一樣。
可擴展的第3.5個定義——比特幣擴容
此外，還有第3.5類可擴展，也就是比特幣擴容方案——例如大區塊和隔離見證。
之所以是第3.5類，是因為從任何角度來講，它們都只是提高了一些輸出，而完全沒有解決可擴展性問題。然而，擴容本身英文也是scalable，而且從歷史角度講，這兩個方案的確也是擴展的第一步，因為——
大區塊-->分叉多-->採用GHOST-->可擴展POW
隔離見證-->解決比特幣可變性問題-->方便鏈下方案的實現-->無限擴展
所以，從這種角度講，說兩個方案擴展了比特幣也無可厚非——只不過最終，真正在比特幣上的升級，也就只停留在了這第一步上。
不同定義之間的關係
看到這裡，是不是很多原先以為自己已經瞭解了可擴展性問題的人覺得腦子更亂了——
難道想知道什麼是可擴展的區塊鏈就一定得知道這東西的來歷麼？有沒有啥可以更簡單的可以在一看到“可擴展的區塊鏈”，就知道它大概是做什麼的，它的性能是什麼的方法呢？
實際上很簡單——
首先，第3.5類只有兩種方案，大區塊和隔離見證首先可以排除出去，因為這兩種方案現在基本上只會以“擴容”的名稱出現，只有非常不專業的地方會用“可擴展”的名義去拿它和其他可擴展算法比較。
其次，在目前，能標榜自己是“無限擴展”的，基本上也不會介紹自己是“可擴展”的。如果這裡仍有疑問的話，也只要記住，分片和鏈下技術是不應該和其他“可擴展”方案放在一起比較的，因為這兩個方案的可擴展性更高，即在大網絡中的輸出更高，但是會在安全性或者中心化上做出一些妥協。更基礎一些的不同是——看這些算法為了保證一致性，是不是要求每個節點都記錄每一筆交易，如果是，則消息複雜度至少是O(N)，於是當網絡中加入節點的時候，輸出一定是不會增加的。而想要無限擴展，就一定有一些交易，是不需要廣播到整個網絡的。
然後，剩下的所有可擴展算法，即我們定義中的第一種和第三種，其實最終都殊途同歸，達到了一樣的可擴展性，即O(N)消息複雜度。然後，兩者的輸出最終都只會受到網絡網速和響應延遲的約束，最終，比較優秀的算法大概在實驗室環境下，達到1000TPS這個量級，最終當然還是會取決於算法的優劣以及實現的優化程度，但是實驗室環境模擬的大網絡的延遲實際上是遠好於實際的水平，所以在現實中，隨著網絡的擴大，輸出不隨著節點數量增加的提升而提升是個美好的想象——輸出幾乎一定會隨著網絡的增大而下降。
這其中最容易混淆的就是DAG，但是這類算法中，我們之前也已經介紹過了，無論是工業界的IOTA，Swirld Hashgraph還是偏學術的Phantom和Conflux，無論在某些媒體或，文章，或者他們自己白皮書中是怎麼介紹的，請記住，它們嚴格都是“可擴展”的共識算法，而不是“無限擴展”的。
下一篇，我們會著重介紹這裡第一種和第三種定義中的可擴展方案，他們的共性和目前面臨的挑戰。在後面，我們會介紹一些DAG算法和分片的算法，最後介紹一下我自己的工作。這次，我會盡量地更新的快一些……
閱讀更多 巴比特 的文章
