區塊鏈擴容方案之—分片（sharding）
分片背景：
這篇文章介紹的區塊鏈擴容方案是分片技術（sharding）。目前區塊鏈擴容領域中的擴容方案有很多，目前看來sharding是這些擴容方案中最有效的。在傳統不分片的區塊鏈中，通常在一段時間裡只產生一個塊，全網所有的礦工競爭唯一的挖礦權，或者針對一個塊達成共識。為了提高吞吐量和延遲，通常只能通過提高區塊生產速度或者增加區塊的大小來完成擴容。然而我在之前的文章也提到過，這兩種方式都存在缺點（頻繁分叉或者網路延遲）。隨後開發者開始把視線集中在了分片上。分片是通過改變網路中驗證塊的方式來增加吞吐量的。
分片思想(分而治之):
區塊鏈分片是受傳統資料庫分片概念的啟發，資料庫分割為多個部分並放置在不同的伺服器上。在分片網路中，節點被分到不同的分片中，網路中的交易也會被分到不同的分片中。因此，每個節點只處理一小部分傳入交易，並且它將與網路上的其他節點並行執行。這樣將網路分成碎片將導致更多事務被同時處理和驗證，原本只能驗證一個區塊的時間內，可以同時驗證多個區塊，從而完成對吞吐量的擴展。分片的最大優勢在於它可以真正做到線性擴展。吞吐量的大小同分片的數量線性相關。
我們可以想像現有的區塊鏈就像一條只有一個收費站的繁忙的高速公路。這樣一定會導致交通堵塞，因為人們排長隊等待並通過收費站。引入分片的區塊鏈就像在高速公路上增加15或20個收費站。它將大大提高車輛通過的速度。分片會對交易的處理速度有非常大的提升。
分片策略(分類):
分片只是一個基本的概念。在實際的實現過程中可能有很多種方式。目前主流的分片實現方式可以分為以下三類：網路分片（network sharding），交易分片（transaction sharding）和狀態分片（state sharding）。網路分片和交易分片更早被提出，網路中的節點被分到不同的分片中，每個分片針對不同的交易子集進行處理、驗證並達成共識。這樣不同的交易子集可以被並行處理，各個分片之間也不必進行頻繁的通訊。
另一方面，在如今的公共區塊鏈系統中，節點為了可以驗證交易的有效性，需要存儲系統所有的歷史交易區塊和UTXOs（Unspent Transaction Outputs）。如果我們把區塊鏈的吞吐量擴展到了Visa級別，簡單的計算可以算出每年增長的存儲消耗會高達21.5 TB，如下圖：
這樣的存儲空間消耗會給節點造成很大的壓力，存儲全部區塊的全節點會越來越少。隨之，系統的安全性也會越來越差。所以為瞭解決這樣的問題，狀態分片的方式被提出了。這種分片思想的核心是，把網路和交易進行分片的同時，把存儲狀態也進行分片，讓每個分片中的節點存儲不同的部分。因此，每個節點只負責存儲自己分片的數據，而不是完整的區塊鏈狀態。這樣的話，如果我們把網路和存儲狀態分成20個碎片，那麼每個分片一年增長的存儲消耗就會變成1TB這樣可以接受的範圍。
潛在挑戰：
前面整體上介紹了三類分片方案。很直觀的體現了他們彼此的不同。不同的分片方式存在他們自己獨特的優勢，一般來說，網路和交易分片更容易實現，而狀態分片更加複雜。同時在網路和交易分片中，每個節點存儲著系統的全部狀態，所以各個分片之間不需要頻繁的交流去確認其他分片的狀態。對於狀態分片，顯然最大的優勢是他解決的日益龐大的存儲問題。但是同時他們各自也存在很多潛在的挑戰，有些挑戰很容易克服，而有些挑戰卻很難克服。下面，我會討論不同的分片機制存在的一些挑戰和他們的可行性。
1. 網路分片（Network sharding）
網路分片的第一個也是最重要的挑戰是分片的創建。需要開發一種機制來確定哪些節點以安全的方式駐留在哪個碎片中，以避免有人可能通過對特定碎片的大量節點進行控制的方式對系統進行攻擊。
擊敗對手的最佳方法（至少在大多數情況下）是通過隨機性。通過利用隨機性，網路應該可以隨機地對節點進行分配從而形成分片。隨機抽樣可防止惡意節點過多地填充單個分片。
但是，僅使用隨機機制將節點分配給分片是不夠的。還必須確保分片中的所有成員都是獲得系統認後加入的。例如，可以通過工作證明（Proof of Work）來實現對節點身份的驗證。
例如在Elastico中，節點用自己的IP地址和公鑰做為身份的認證，在加上上一個時代結束時生成的隨機數，進行工作量證明運算。只有能提供工作量證明的身份才能加入網路。
2. 交易分片（transaction sharding）
交易分片並不像聽起來那麼簡單。考慮在類似比特幣的系統中引入交易分片（沒有智能合約），系統的狀態是使用UTXO定義的。讓我們假設網路已經由分片組成，並且用戶發出了一筆交易。這筆交易有兩個輸入和一個輸出。現在，該如何將此事務分配給分片？
最直觀的方法是根據交易哈希值的最後幾位來決定被分到哪個分片。例如，假設我們有四個分片，哈希值的後兩位為00，01，10，11的交易會被分別分配給第一，二，三，四個分片。這樣做最大的好處在於交易可以在單個分片中被驗證，不需要跨分片通訊。但是，如果用戶是惡意的，他可能會使用相同的輸入創建兩筆不同的交易，從而造成了雙重花費（double-spending）。如果兩筆交易被分到了不同的分片，那麼兩個分片都會認為自己手中的交易是有效的，從而造成了雙花攻擊。
為了防止雙重花費，在驗證過程中，分片必須相互通信。事實上，由於雙花交易可能落在任何分片中，因此接收交易的碎片必須與每個其他分片都進行通信。事實上，通信開銷可能會破壞交易分片的擴容效果。
事實上，當我們擁有基於帳戶（Account-based）的系統時，問題會更容易解決。每個交易都將具有發件人的地址，然後可以根據發件人的地址將其分配給對應的分片。這確保了造成雙花的兩筆交易將在同一個分片中得到驗證，這樣，雙重花費可以在沒有任何跨分片通信的情況下輕鬆被發現。
3. 狀態分片（state sharding）
事實上，狀態分片是迄今為止所有分片提案中最具挑戰性的。狀態分片遇到的第一個挑戰就是頻繁的跨分片通信和狀態交換。由於每個分片只存儲系統的部分狀態，分片之間不得不通過大量的通信來獲取存儲在其他分片中的信息，只有這樣才能驗證交易是否有效。例如，在一個UTXO模型的區塊鏈系統中，某一筆交易可能有多個輸入（input），而這些輸入可能存在與其他的分片中，輸出分片必須要和所有的輸入分片通信確認用戶提供的輸入是否有效，這會造成大量的通信成本。那麼在一個基於賬戶的系統中也同樣需要大量的跨分片通信。所以如何確保跨分片通信成本不會超過狀態分片的所獲的的性能增益仍然是一個值得深入研究的問題。個人認為，對於跨分片交易（cross-shard transaction）的解決方案目前有三種值得探討，他們分別是OmniLedger, Rapidchain和Harmony。他們提出的解決方案各不相同，有各自的優點，同時也各自存在問題，我會在以後的文章中詳細介紹本文提到的這四個分片方案（包括Elastico）。
狀態分片的第二個挑戰是數據可用性。考慮一種情況，由於某種原因，某個分片可能受到攻擊而導致離線。由於系統的狀態沒有在所有分片中複製，因此網路一旦有交易的輸入是來自離線的分片，那麼這筆交易將無法得到驗證。這樣，區塊鏈很有可能變得不可用。這個問題的解決方案是維護存檔或備份節點，以幫助網路進行故障排除並從數據不可用中恢復。然而，那些節點將必須存儲系統的整個狀態，因此可能引入集中化風險。
最後，在任何分片機制中都要考慮的另一個挑戰（不是特指狀態分片）是為了確保分片不是靜態的，為了抵禦攻擊和故障，網路必須接受新節點並以隨機方式將它們分配給不同的分片，並且隨機驅逐舊的不活躍節點。換句話說，每隔一段時間網路必須重新洗牌。
然而，在狀態分片的情況下分片的重新配置更加棘手。由於每個分片只維護一部分狀態，因此一次性重新洗牌可能會導致整個系統不可用，直到某些同步完成。為了防止中斷，必須逐步重新調整網路，以確保在逐出節點之前每個分片都有足夠的舊節點。類似地，一旦新節點加入分片，就必須確保節點有足夠的時間與分片的狀態同步，否則新加入的節點將完全拒絕每一個交易。在介紹Rapidchain分片協議的文章中我會重點介紹一個委員會重組方案，叫做有界的布穀鳥原則（Bounded Cuckoo Rule），它可以更加高效的進行分片委員會重構，並且同時可以防止惡意節點控制某個分片的行為發生。
總結：
三種分片方式都有各自的優缺點，目前也都存在侷限性，沒有一種分片方案是完勝的。目前來看很難做到完全的優點，只能根據系統的應用場景和系統重視的方面的不同在各種方案之間權衡利弊。
推薦閱讀：
