分片是區塊鏈擴容的一個重要方向。
傳統的區塊鏈如以太坊每秒僅能處理20個左右的交易，主要原因是以太坊中每個交易都要在每個節點上執行一遍, 單臺機器的處理能力限制了以太坊的最大TPS，
分片的思路是把所有節點進行分組，每個節點不再參與全部交易的驗證，而是僅驗證一部分的交易，因此可以突破單臺機器處理能力的限制。
今天這篇文章將會為大家介紹Near protocol提出的分片方案—夜影協議(Nightshade) 。
分片的基本設計
區塊鏈依靠在所有節點復制所有交易來保證數據的正確性，每個節點如果只驗證一部分，那就明顯會降低安全性，
系統共有10個分片（shard chain）, 每個分片鏈由1/10的節點驗證，理論上TPS可以提升十倍，但安全性也會隨之下降，
假設原始的區塊鏈中有51%以上的惡意節點合謀了，才可以破壞整條鏈的狀態，那么分片后只要有5.1% (51/100) 的惡意節點合謀就足夠破壞某個分片上的狀態，
大部分分片方案的應對思路是隨機分配驗證者，只要讓惡意節點不在同一條分片鏈上，他們就無法合謀。
大多數方案選擇用一條獨立的鏈來實現管理分片，處理POS（proof of stake）共識，生成隨機數等等。
就比如以太坊2.0的Beacon chain、PolkaDot的Relay chain、Cosmos的Cosmos Hub。
而Nightshade也使用了一條這樣的Beacon chain (信標鏈)。
一般來說區塊鏈的節點會負責以下任務：
1.處理交易 。
2.Relay 合法的交易和區塊給其他節點 ，
3.保存整條鏈的狀態和歷史數據，
以上三點都會影響整個網路的處理能力。
從長遠來看，狀態存儲的壓力比較大，即使TPS一直保持在20左右，鏈的狀態也會一直增長，但短期來看，區塊鏈處理交易的能力才是更加重要的，
截止發稿，以太坊全狀態大約為100G，大多數節點仍可以輕松處理，但是以太坊的TPS僅有20左右，很難滿足實際需求。
Nightshade的分片也會分割以上提到的三點。分片中的節點僅驗證和傳播與分片相關的交易，并且只存儲和分片相關的狀態，
在Nightshade的方案中，分片數量和計算、存儲、網路等資源為線性關系，
Nightshade對Beacon chain和分片鏈進行了簡化，在Nightshade中僅維護一條區塊鏈，所有分片上的交易都會在這一條鏈上被確認。
一個塊中的交易列表按照分片數量被分為多個chunks, 每個chunk對應一個分片，分片的驗證者只需要下載和驗證分片的chunk而不需要下載整個塊，系統中沒有節點會驗證整個塊的交易和狀態，
現實中由于網路因素可能會導致chunks丟失，所以我們允許每個塊中的分片可以對應一個或零個chunk。
出塊
Nightshade中有兩個角色共同維護協議：出塊者和驗證者，
在系統中任何時間點都有w個出塊者和wv個驗證者，系統采用POS (proof of stake)，出塊者和驗證者都會質押一定的Token作為不遵守協議時的懲罰。
系統包含n個分片，每個出塊者和驗證者都僅下載和驗證一部分的狀態。
在本文所討論的模型中w=100, wv=10000, n=1000。
系統的參與者可以通過質押大量的Token成為出塊者，一個出塊者會被分配到Sw個分片上（如果Sw=40, 那么每個分片就會有Sw*w/n=4個出塊者），
Nightshade中按照Epoch的概念選擇驗證者和出塊者的分片，出塊者需要在Epoch開始前下載分片的狀態，并在整個Epoch中處理分片上的交易，
對于每個分片，都有一個出塊者來負責生成chunk（和該分片相關的交易列表），在最終的塊里只會包含交易列表的merkle root而不會包含完整的交易列表。
同一個分片上的出塊者會輪流出塊，如上面描述的，每個分片上有4個出塊者，則每個出塊者隔4 個塊就要產生一次chunk，
跨分片交易
上文描述的分片方案中不同分片之間狀態是完全隔離的，無法進行跨分片的交易。
舉一個簡單的例子，Alice想要轉賬給Bob，如果他們在同一個分片中，則交易可以正常處理。
但如果Alice和Bob在不同的分片，則每個分片的驗證者都缺失了一部分狀態，無法完成這筆交易的驗證，
有兩類方法可以支持跨分片交易：
一、同步，在同一個塊進行與跨分片交易相關的多個分片的狀態更新，驗證者們通過與其他分片上的節點合作來處理交易。
二、異步，異步的完成跨分片交易的狀態更新，比如某個分片先更新一部分狀態，另一個分片再更新其余的狀態。
這種方式非常簡單并且易于協作，Cosmos、 Ethereum serenity (以太坊 2.0)、Near、Kadena等都采用的異步方案，
區塊鏈或分片的互操作性在分片以外的場景也非常重要。分片的場景下每個分片是同構的，且可以借助Beacon chain協調，所以跨分片的設計相比跨鏈會更容易一些。
Nightshade中則采用了收據交易的概念，發起跨鏈交易時首先在一個分片上執行交易，這個交易隨后被打包在分片的chunk里，當chunk被打包到塊中時，會生成一個收據交易，
驗證者將這個收據交易發送到下一個需要更新的分片上執行。如果這筆交易需要更新更多的分片上的狀態，則會重復以上過程，
這個方案有可能會導致某個特定的分片成為熱點，大量的收據交易需要發送到這個分片上，導致分片的處理能力不夠，
為了解決這個問題Nightshade會在chunk中記錄最后處理的跨鏈交易的進度：
塊和分片以及處理到了哪個收據交易，下一個塊的chunk就會繼續處理接下來的收據交易，
如果待處理的收據交易數量實在太多，超過了一定限制的話，系統會禁止再發送新的跨鏈交易。
狀態驗證
分片的核心思想是驗證者不用去下載和驗證所有的狀態。當節點與分片交互時，如何在不下載分片的情況下確定其狀態是一個難題。
有個簡單的方案：
假設整個系統總共有1000個驗證節點，如果其中惡意節點不超過20%，那么當我們從中隨機挑選200個節點組成分片時，惡意節點占比在1/3以上的可能性就幾乎可以忽略。(惡意節點在1/3以下保證了分片可以使用BFT類共識)，
在這個簡單的假設中，每個Epoch的驗證者都會去詢問之前的一組驗證者，并獲取到主鏈的資訊。
而BFT類共識保證惡意節點在1/3以下時，塊是合法的，且不會產生分叉。
因此我們只需從最初的狀態去檢查驗證者的簽名，就可以確定這條鏈的合法性。
簡單方案只考慮了系統初始時有固定數量的惡意節點，但如果我們引入一個新的假設：
在系統運行時，誠實的驗證者也可以被腐化為惡意節點，這個簡單方案就無法正常工作了，
攻擊者僅需腐化一個分片中2/3n+1的驗證者就可以生成非法的狀態，這種安全性對于區塊鏈來說顯然太弱了。
Nightshade在BFT共識之上增加了挑戰機制來提升安全性。任何的參與者檢測到一個chunk包含非法狀態時，都可以提供一個證明對chunk的出塊者進行懲罰，同時獲取獎勵，
因為系統中大多數節點是沒有非法chunk的分片狀態的，所以證明中必須要包含足夠的資訊。
Nightshade要求在chunk中保存每一個交易執行后分片狀態的merkle root，這樣挑戰者只需要找到第一個非法的狀態，并從前一個狀態進行驗證就可以證明chunk是非法的。
Nightshade通過隱藏具體的驗證者來進一步降低驗證者被腐化的可能性，
這個想法類似于Algorand的方案，但需要注意的是，即使隱藏了驗證者，一個攻擊者仍能通過廣播來倡議驗證者進行合謀，
當誠實的驗證者發現倡議合謀的廣播消息時，可以下載攻擊者想要攻擊的分片并進行監控，這樣即使合謀成功，誠實的驗證者也可以立刻發送挑戰來懲罰攻擊者。
Nightshade用以下方法來隱藏驗證者：
1.在每個Epoch開始前，驗證者使用VRF（可驗證隨機方法）確定被分配到的分片，并在Epoch中負責驗證這些分片，
2.所有的驗證者都在區塊上簽名，而非在chunk上簽名，
驗證者有可能不去真正下載分片狀態并執行驗證，而是通過從網路中觀察其他驗證者的消息并進行重復來獲利。
采用這種策略的驗證者沒有給網路帶來任何額外的安全性。
為了防止這種行為，我們要求驗證者首先提交一個承諾，承諾中要么包含一條消息確定chunk的交易都是合法的，要么包含對某個非法狀態的挑戰，
驗證者需要等待一定的時間后再去揭露實際提交內容，任何提交錯誤的驗證結果，以及無法揭露承諾內容的驗證者都會被懲罰，
數據可見性
數據可見性是區塊鏈分片設計的另一個難題。即使有了復雜的驗證和挑戰機制，攻擊者仍然有作惡空間。
同一個分片上的驗證者還可以共謀作惡，只發布chunk header而不發布完整的chunk內容。
因為主鏈只會對chunk做確認而不會對其驗證（如果驗證每個chunk，分片就沒有意義了），
所以主鏈的驗證者無法判斷chunk的內容是否被發布，出塊者仍會把chunk包含在塊中，
如果這些chunk包含了非法的狀態，即使有誠實的節點對其產生懷疑，因為chunk的內容沒有發布，節點也無法生成挑戰證明，
NightShade的解決方案是選擇引入了擦除碼（Erasure Codes, 方案與PolkaDot和以太坊 2.0類似），擦除碼允許我們在一部分數據不可見時仍能恢復整個區塊，
我們對協議進行修改。當一個出塊者生成了新的 chunk時，同時也要對chunk的內容生成擦除碼。
Chunk的出塊者把擦除碼分割成w份（系統中出塊者的數量），并用merkle tree計算每一個碎片，然后把merkle root保存在chunk header里。
Chunk的出塊者隨后通過onepart消息（用來發送擦除碼的碎片）把擦除碼碎片按照每人一份發送給所有出塊者，消息包含：
chunk header、擦除碼碎片的編號、擦除碼碎片的內容、擦除碼碎片的merkle proof以及出塊者對這條消息的簽名，
當主鏈的出塊者收到塊時，會檢查是否已經收到了塊中所有chunks的onepart消息，如果沒有則需要等待全部消息接受完成后再繼續處理，
等到主鏈出塊者確定每個chunks都收到了對應的onepart消息之后，就會向peers請求每個chunks其余的擦除碼碎片，并重新構建chunks。
如果出塊者無法成功構建chunks, 或者無法獲取某個chunk的onepart消息的話，就會停止處理該塊。
反之，如果出塊者能夠成功的構建出完整的chunks的話，則可以確定chunks的完整內容的確被發布了，Chunk header如果包含了非法狀態，那么任何節點都可以對其生成挑戰證明，
但是當前的協議仍有一個問題，主鏈出塊者有可能在收集完所有的onepart消息之前就進行了簽名。
這樣出塊者仍會收到出塊獎勵，但不會受到任何懲罰，當大多數節點采取了這種策略時，數據可見性就無法得到保證了，
為了解決這個問題，chunk出塊者需要對每個擦除碼碎片分配顏色（紅色或藍色），并且將顏色保存為bitmask與chunk的內容一起編碼成擦除碼，
當chunk出塊者發送onepart消息時同時也會附上碎片的顏色，并且擦除碼碎片的merkle root也會同顏色一起計算。
主鏈出塊者對塊簽名時，需要在簽名中包含所有紅色的chunks碎片組成的bitmask。
因為完整的bitmask只存在于擦除碼中，主鏈的出塊者只有通過擦除碼重新構造chunk內容和bitmask才能獲取正確的顏色，
因此，主鏈出塊者必須確保自己接收到了所有的onepart消息，且能正確構造所有chunks內容，才可以確保簽名是正確的。
如果出塊者沒有收到某個onepart消息卻仍然簽名，則有50%的概率猜錯顏色從而被懲罰。
投資有風險，本文觀點和意見僅代表作者本人，并不構成任何建議，
