夜影:NEAR協議中的分片設計

買賣虛擬貨幣
眾所周知,以太坊作為迄今為止最廣為使用的通用區塊鏈,主網每秒只能處理不到20筆交易。在以太坊網路流行後,由於這個侷限,導致了高昂的以太坊gas價格(gas是以太坊網路上執行交易的費用)和過長的確認時間。儘管在撰寫該文的時候,以太坊平均每10到20秒可以產出一個新塊,然而根據ETHGas監測站的資料,一筆交易實際上要花1.2分鐘才能加到鏈上。低產能,高費用和長延遲,都導致了以太坊不適合執行大規模使用的鏈上服務。 以太坊低產能的主要原因是,每個節點都要處理全網的每一筆交易。開發者們提出了許多解決方案,試圖在協議層面解決這個問題。這些方案主要分為兩類:一類是把所有的計算工作交給數量有限的強力節點;另一類是讓網路中的每個節點只做所有計算工作的一部分。前一種方案的例子是Solana,系統中的每個節點透過細緻的低層最佳化和GPU的使用,來支撐每秒幾十萬筆簡單的支付交易。Algorand,SpaceMesh,Thunder都可歸入這一類;他們透過改進共識以及區塊結構本身來超過以太坊的TPS,雖然有一定的效果,但仍然受制於單臺機器的處理能力。 後一種方案,即把工作分給所有的參與節點。這種方法叫做分片。這也是當前以太坊基金會打算的擴充套件方案。撰寫本文時,以太坊的分片規範還未定稿,最新的規範可以透過以下連結檢視。 連結: https://github.com/ethereum/eth2.0-specs. NEAR協議基於分片搭建。NEAR團隊的成員包括:多位世界級電腦競賽獲獎者;若干前MemSQL工程師,負責構建分片、跨分片交易以及分散式的JOIN;9位前谷歌、臉書員工,他們在構建分散式系統方面等有著豐富的行業經驗。
本文重點闡述了區塊鏈分片的通用方法,以及需要解決的主要問題,包括狀態有效性和資料可用性問題。本文還提出了NEAR協議創新的的夜影方案。1. 關於分片的基礎知識 讓我們從最簡單的分片方法開始。舉例來說,不同於執行一個鏈,我們執行多個鏈,每個鏈稱為一個“分片”。每個分片有自己的驗證節點集合。在下文裡,不管是POW中挖礦的方式,還是投票機制,我們都會使用這個原生詞彙“驗證節點”,去指代那些進行交易驗證和生產區塊的參與者。同時,讓我們先假設各個分片之間互不通訊。 這一設計,雖然簡單,但卻足夠概括早期分片面臨的一些主要挑戰了。 1.1 驗證節點分割槽和信標鏈

假設一個系統包含10個分片。第一個問題是,由於每個分片有自己獨立的驗證節點,現在每個分片的安全性都只有原先整條鏈的十分之一了。如果一個包含X位的非分片鏈決定硬分叉成一個分片鏈,X位驗證節點就會分佈到10個分片上,每個分片現在僅有 X/10 位驗證節點。攻擊一個分片只需要買通5.1%(51% / 10)的驗證節點(見圖1)。

這就帶來第二個問題:誰負責為每個分片選擇驗證節點?如果5.1% 的驗證節點被攻破,但也只有在這些驗證節點正好處於同一個分片時才有威脅。如果驗證節點不能自主選擇去驗證哪個分片,那麼一個控制了5.1% 驗證節點的參與者是很難讓他控制的所有驗證節點都在同一個分片的。這也就就大大降低了他破壞系統的能力。

當今幾乎所有的分片系統都依賴給分片隨機分配驗證節點。區塊鏈上的隨機性本身就是一個極富挑戰的話題,它超出了本文討論的範疇。現在,讓我們假設有這樣一個可用的隨機性。我們會在2.1節介紹驗證節點分配的更多細節。

隨機性和驗證節點分配都要求計算工作與任意分片之間不存在對應關係。目前對於分片計算而言,幾乎所有設計都使用一個額外的獨立區塊鏈,來執行維護整個網路所需要的操作。除了隨機數生成和給分片分配驗證節點外,這些操作通常還包括了接收分片更新以及執行分片快照,處理POS中的質押和取消驗證節點資格,以及在支援再平衡功能的分片系統上進行分片的再平衡。這種獨立鏈的名稱,以太坊上叫信標鏈,波卡上叫中繼鏈,Cosmos上叫Cosmos Hub。

本文統一將其稱為信標鏈。信標鏈的存在引出了下面一個有趣的主題,即二次方分片。

1.2 二次方分片

分片經常被視為一種可以隨著網路中節點數的增加而無限擴充套件的方案。雖然從理論上看,人們是有可能設計出這種方案的,但任何使用信標鏈概念的方案都不可能無限擴充套件。為了理解其原因,我們要意識到,信標鏈要做一些記賬的計算工作,例如給分片分配驗證節點,或快照分片鏈區塊,而這些都與系統中的分片數量成比例關係。因為信標鏈本身只是一條單獨的鏈,計算量受限於執行節點的算力,因此分片數量自然就受到了限制。

然而,分片網路的結構確實對節點的改進產生了倍增的效果。想象一下這樣一個場景,對網路中節點效率作出一定量的改進,從而使得節點處理交易的時間縮短。

如果節點(包括信標鏈中的節點)執行網路的速度提高了四倍,那麼,每個分片都可以處理原先交易量的四倍多,而信標鏈也可以維持原先分片數量的四倍多。整個系統吞吐量的將提升:4 × 4 = 16 倍,這就是二次方分片名稱的由來。

當前,對於究竟能支援多少分片,很難提供精確的度量。但是,在可以預見的未來,區塊鏈使用者的吞吐量需求不太可能超過二次方分片的能力。執行如此眾多的分片所需要的節點數,可能比當今所有區塊鏈節點數的總和還要高出幾個數量級。

1.3 狀態分片

目前為止,我們還未準確定義當網路切割成分片後,究竟什麼被分割開,什麼沒有被分割出去。尤其要注意,區塊鏈中的節點需執行三個重要任務:1)執行交易,2)把經過驗證的交易和構建完成的區塊中繼給其他節點,3)儲存整個網路賬本的狀態和歷史。三個任務中的每一個都對執行網路的節點提出了不斷增加的需求:

· 隨著需要處理的交易量的增加,執行交易的必要性導致更高的算力需求;
· 隨著需要中繼的交易量的增加,中繼交易和區塊的必要性導致更高的網路頻寬需求;
· 隨著狀態資料的增長,儲存資料的必要性導致更大的儲存需求。重要的是,不像算力和網路需求,儲存要求是持續增長的,即使交易速率(TPS)保持恆定。

上面的列表可能讓人覺得,儲存需求是最急迫的,因為它是唯一一個隨著時間持續增長的因素(即使每秒交易量不變)。但實際上,當前最急迫的需求是算力。撰寫本文時,以太坊的全網狀態大小是100GB,大部分的節點都可以輕鬆應對。而以太坊的每秒可處理交易量在20筆左右,比許多實際應用場景的需求低了好幾個數量級。

Zilliqa是最廣為人知的對交易處理而不是儲存進行分片的專案。對處理分片相對容易:因為每個節點都有完整的狀態,意味著一個合約可以自由呼叫其他合約,從鏈上讀取任何資料。為了確保對狀態同一部分進行更新的多個分片不會產生衝突,還需要一些細緻的技術工作。從這方面來說,Zilliqa的方法有些簡單 (2)。

儘管之前有提出過對儲存分片但不對處理分片的方案,但這是極不尋常的情況。在實踐中,對儲存分片,也就是狀態分片,幾乎總是隱含了對處理分片和網路分片。

實際上,狀態分片中,每個分片中的節點都在構建他們自己分片的區塊鏈,這條鏈僅包含那些對被分配給該分片的全域性狀態的本地部分產生影響的交易。因此,分片的驗證節點只需要儲存全域性狀態的本地(分片)部分,也僅僅執行和中繼那些影響到這些本地狀態的交易。這種分割槽線性地減少了所有包括算力、儲存、頻寬的需求。但是這也帶來了新的問題,例如資料可用性和跨分片交易的問題。這兩個問題我們會在下文闡述。

1.4 跨分片交易

迄今為止,我們描述的分片模型還不是很有用。如果單個分片不能跟其他分片互相通訊,整個系統不過就是多個獨立的區塊鏈而已。甚至在分片技術還不可用的今天,不同區塊鏈之間的互操作性依然是一個巨大的需求。

現在,讓我們只考慮簡單支付交易,每個參與者僅在一個分片上擁有賬戶。如果有使用者希望在同一分片內從一個賬戶轉賬到另一賬戶,這筆交易可以由本分片的驗證節點全權處理。然而,如果分片1上的Alice想轉賬給分片2上的Bob,無論是分片1上的驗證節點(他們無法把賬存入Bob的賬戶),還是分片2上的驗證節點(他們無法把賬從Alice的賬戶取出),都不能處理整筆交易。

有兩種跨分片交易的實現方案:

同步:無論何時,一筆跨分片交易需要執行時,所涉及分片上含有相關交易狀態轉移資訊的區塊都同時生成。這些分片的驗證節點合作執行此類交易。

非同步:影響多個分片的跨分片交易在其所涉及的分片上非同步執行。貸記方的分片一旦有了充足的證據,表明借記方分片已經執行了借記那邊的工作,就可以執行自己這邊的貸記工作。這種方案更趨於流行,因為它比較簡單,並且易於協同。這種系統被Cosmos、以太坊寧靜、NEAR、Kadena等採用。這種方案有一個問題,如果區塊是獨立產生的,相關區塊中的某個成為孤塊的可能性總歸存在,導致整個交易僅被部分執行。

想一下圖2中描述的情況:兩個分片都遭遇分叉。同時,一筆跨分片交易相應記錄於塊 A 和塊X’ 中。如果鏈 A-B 和 鏈 V’-X’-Y’-Z’ 成為了各自分片的正統鏈,則跨分片交易完全確認。若 A’-B’-C’-D’ 和 V-X 成為正統鏈,則跨分片交易完全被遺棄,這也是可以接受的。但如果 A-B 和V-X 成為正統鏈,則跨分片交易的一部分確認,另一部分被遺棄,這會導致一個原子性錯誤。我們在第二部分中提出的協議裡,會介紹該問題的解決辦法,包括分片協議提出的分叉選擇規則以及共識演算法的變動。

值得注意的是,跨鏈通訊不止在分片區塊鏈有用。鏈間的互操作性是個複雜的問題,許多專案想要解決這個問題。在分片區塊鏈中,該問題相對簡單些,因為區塊結構和共識在分片之間都是相似的,還有一個信標鏈可以用來做協調。所有的分片鏈都是大同小異的,然而全域性的區塊鏈生態體系中有許多不同的鏈,他們有不同的目標使用場景、不同的去中心化程度和隱私保證程度。

構建這樣一個包含公共信標鏈,和一系列雖然擁有不同屬性、但有一系列足夠類似的共識和結構的區塊鏈系統,可以實現一個有可用互操作子系統的異構區塊鏈生態。這樣的系統不太可能有驗證節點輪替的功能,所以需要採取一些額外措施確保安全性。Cosmos和波卡實際上都屬於這種系統。

1.5 惡意行為

這一節,我們將回顧,如果惡意驗證節點想破壞一個分片,會採用什麼樣的行為。我們將在2.1節回顧那些防止分片破壞的經典實現方法。

1.5.1 惡意分叉

一部分惡意驗證節點也許試圖建立一個分叉。需要注意的是,無論底層共識是否是BFT,買通足夠數量的驗證節點就都可能建立一個分叉。

相對來說,最可能發生的是買通一個分片中的50%以上(的驗證節點),而不是買通整個鏈的50%以上(的驗證節點)(我們將在2.1節詳細闡述這些可能性)。正如1.4節中所討論的,跨分片交易牽涉到多個分片中的某些狀態改變,這類分片中應用這些狀態變化的相應區塊要麼全部確定(即出現在對應分片被選中的分支上),要麼全部成為孤塊(即不出現在對應分片被選中的分支上)。一般意義上看,分片被破壞的可能性是不可忽視的,即使分片驗證節點之間已經達成了某種拜占庭共識或是包含狀態變化的塊之上已經產出許多區塊,我們也不能假設不會發生分叉。

這個問題有多種解決方案,最常用的一種是將分片鏈上最新的區塊偶爾交叉連線到信標鏈上。分片鏈上的分叉選擇規則相應變化為總會優選那些交叉連線的鏈,並且只對最後一個交叉連線之後產生的區塊使用分片特定的分叉選擇規則。

1.5.2 審批無效塊

一些驗證節點也許會嘗試建立一個包含了不正確狀態轉換函式的區塊。例如,從Alice有10枚通證、Bob有0枚通證的狀態開始,區塊可能包含包含一筆Alice轉給Bob10枚通證的交易,但是最終狀態如圖3所示,Alice有0枚通證,Bob卻獲得了1000枚。

在一個經典的非分片區塊鏈中,這種攻擊是不可能成功的,因為網路中所有參與者都會驗證所有的區塊。一個帶有無效狀態轉換的區塊,其他出塊人和不出塊的網路參與者都會拒絕。即使惡意驗證節點繼續在這個無效區塊之上以相對誠實驗證節點更快的速度堆積新的區塊,使得包含無效區塊的鏈更長,也沒有關係。因為,不管出於何種目的使用這個區塊鏈的參與者都會驗證所有區塊,並丟棄那些構建在無效區塊之上的所有區塊。

圖4中有五個驗證節點,其中三個是作惡者。他們建立了一個無效區塊 A’ ,並繼續在其上建立新的區塊。兩個誠實驗證節點丟棄無效的 A’ ,並在最後一個在他們看來有效的區塊上構建區塊,導致了一個分叉。因為誠實驗證節點的分叉中驗證節點的數量更少,所以他們的鏈更短一些。然而,在經典的非分片區塊鏈中,每個出於各種目的使用區塊鏈的參與者都負責驗證所收到的所有區塊,並重新計算狀態。因此,任何關注該區塊鏈的人都能發現A’ 是無效的,並立即丟棄 B’ 、 C’ 和 D’ 。這樣一來,鏈 A-B 就是當前最長的有效鏈了。

但是,分片區塊鏈中, 任何參與者都無法驗證所有分片上的全部交易。所以它們需要某種方法確認,鏈上任何分片的任何歷史狀態中,都不存在無效的區塊。

需要注意的是,與分叉不同,交叉連線到信標鏈並不是該問題的一個充分的解決方案,因為信標鏈無法驗證所有區塊。它只能驗證該分片中有足夠數量的驗證節點簽名(並以此作為其正確性的證據)。

我們將在下面的2.2節討論該問題的解決方案。

2. 狀態有效性和資料可用性

分片區塊鏈的核心思想是大部分操作和使用網路的參與者無法驗證所有分片的區塊。因此,任何時候,參與者需要與某個特定的分片互動時,他們一般都無法下載和驗證該分片的完整歷史狀態。

然而,分片的分割槽屬性,引起了一個顯著的潛在問題:如果不下載和驗證特定分片的完整歷史狀態,參與者無法確信他們互動的狀態是某個有效區塊序列的結果,而且也不能確信這個序列就是該分片的正統鏈。這個問題在非分片區塊鏈上是不存在的。

首先,我們會呈現解決該問題的一個簡單方案,許多協議中也提出過這個方案。然後分析如何破解該方案,以及為了防止破解進行了哪些嘗試。

2.1 驗證節點輪替

解決狀態有效性一個比較簡單天真的方案如圖5所示:假設整個系統有數千位驗證節點,其中不超過20%的是作惡者或會失效(比如掉線無法出塊)。然後,如果我們取出200個驗證節點作為樣本,那麼樣本中超過1/3的驗證節點會失效的概率在實際中可以視為0。

1/3是個很重要的閾值。有一個共識協議族,叫做BFT共識協議,可以保證只要少於1/3的參與者失效,不管是宕機或以某種方式違反了協議,整個系統還是能達成共識。

在這種誠實驗證節點百分比的假設下,若某分片的當前驗證節點集合提供了某個塊,簡單的方案就認為該塊是有效的,且構建在這些驗證節點開始驗證工作時就認定的該分片的正統鏈上。這些驗證節點從之前的驗證節點集合中識別了正統鏈,而根據同樣的假設,這些驗證節點構建的區塊就在正統鏈的前面。這樣推導下去,整個鏈都是有效的。而且,既然任何時間節點的驗證節點集合都沒有產生分叉,這種簡單的方案也確信當前鏈就是該分片的唯一鏈。觀察圖6可獲得一個直觀感受。

如果我們假設驗證節點受到自適應攻擊,這個簡單的方案就失效了。這個假設並非不合情理。自適應攻擊擁有1000個分片的系統中的一個分片,其成本遠低於去收買整個系統。因此,協議的安全性隨著分片數量的增加而線性降低。為了確信一個塊的有效性,我們必須知道系統的所有分片在任何歷史時間點上,其大多數驗證節點都沒有勾結在一起。然而這種自適應破壞導致我們不再可以確信塊的有效性。正如在1.5節中討論的,被收買的驗證節點可以實行兩種基礎的破壞行為:建立分叉,以及建立無效區塊。

惡意分叉可以透過向信標鏈交叉連線區塊的方式解決。信標鏈通常在設計上就比分片鏈有明顯更高的安全性。然而,建立無效區塊顯然是個更難解決的問題。

2.2 狀態有效性

看一下圖7的情況:分片1被攻破了,惡意行為人產生了無效的區塊B。假設在這個區塊B裡,Alice的賬戶上憑空鑄造了1000枚通證。惡意行為人接著在B後面建立了有效區塊C(意思是C中的交易正確執行),從而掩蓋了無效的區塊B,併發起了一個到分片2的跨分片交易,內容是轉賬那1000枚通證給Bob的賬戶。此時,非法生成的通證反而駐留在分片2中一個完全有效的區塊裡。

以下是應對該問題的一些簡單方法:

· 分片2的驗證節點(跨分片)驗證產生交易的那個區塊。這個方法在上圖的場景中都不起作用,因為區塊C看起來是完全有效的。

· 分片2的驗證節點(跨分片)驗證交易所在區塊之前的一大批前置區塊。自然的,對於接收分片驗證的任何區塊個數N,惡意驗證節點都可以在產出的無效區塊上建立N+1個有效區塊來應對。

解決該問題的一個可行的方法是:把分片排列成無向圖,每個分片都與若干其他分片相連。並且只允許這些相鄰分片之間的跨分片交易(例子有,這就是Vlad Zamfir的分片精要的做法(3),而且在Kadena的Chainweb中也用了相似的思想[1])。如果非相鄰的分片需要一個跨分片交易,多個(相鄰)分片路由的方式可以解決。在這個設計中,每個分片中的驗證節點都要驗證自己分片和相鄰分片的所有區塊。下圖有10個分片,每個都有4個相鄰分片,對於跨分片交易的兩個分片之間最多僅需要兩跳(見圖8)。

分片2不僅驗證自己的區塊,還驗證所有相鄰分片,其中包括分片1。如果一個分片1上的惡意行為人試圖建立一個無效區塊B,在其上建立區塊C併發起跨分片交易,則這樣的交易無法成功。因為分片2會驗證分片1的完整歷史,由此識別出無效的區塊B。

儘管只攻破單個分片不再是可行的攻擊方法,攻破若干分片仍然是個問題。在圖9中,一個對手同時攻破了分片1和2,使用來自無效區塊B的資金,執行了到分片3的跨分片交易:

分片3驗證了分片2的所有區塊,但是並不驗證分片1的區塊,因此無法檢測到那個惡意區塊。正確解決狀態有效性問題有兩個主要方向:漁夫與密碼學計算證明。

2.3 漁夫

第一種實現方法背後的思想是:一旦一個區塊頭 (header) 因為某種目的(比如交叉連線到信標鏈或跨分片交易)在鏈間傳遞,就有一個時間視窗讓誠實的驗證節點提交那個區塊無效的證明。如今存在各種各樣的設計,允許透過簡潔的證明即可指認無效區塊。對於接收節點來說,區塊頭的通訊遠比要接收整個區塊小多了。透過這種方法,只要分片中至少有一個誠實驗證節點,系統就是安全的。

這是當前提出的協議中主流的實現方法(除非假設這個問題不存在)。然而,這種實現有兩大主要缺陷。一是質疑的時間視窗要足夠長,讓誠實驗證節點可以識別產生的區塊、下載並完全校驗區塊,並準備好在驗證出無效區塊時提出質疑。引入這麼一種時間段會明顯拖慢跨分片交易。

二是質疑機制的存在導致了一個新的攻擊維度,作惡者用大量無效的質疑衝擊系統。該問題的一個直接解決方案是讓質疑者抵押一定量的通證,質疑有效才歸還。但這也只是部分解決了問題,因為有可能對手(在抵押被沒收的情況下)仍然能透過無效質疑獲利。例如,以此阻止誠實驗證節點的質疑獲得透過。這種攻擊被稱為Griefing Attack(損人不利己)。處理後面這個問題的方法,參見3.7.2節。

2.4 簡潔的非互動知識論證

第二種應對多分片賄賂的方案是使用某種密碼學的措施,允許一個人證明某個計算(比如從一系列交易中算出區塊)被正確執行了。這種措施確實存在,比如 zk-SNARKs、zk-STARKs 等技術,經常用在當今隱私支付領域的區塊鏈協議中,其中最知名的是ZCash。那些方案的主要問題是計算起來非常慢。例如,Coda協議,專門使用zk-SNARKs證明鏈上的所有區塊都是有效的,在一次訪談中表示,為了建立一個證明,每筆交易要花費30秒時間(目前這個數字可能要小些)。

有趣的是,證明未必需要一個可信實體進行計算。因為證明不僅能證實它的目標計算的有效性,還能證實其自身的有效性。因此,這種證明的計算工作可以分配給一系列參與者,與必須執行某些無需信任的計算相比,顯著降低了冗餘。它也允許計算zk-SNARKs的參與者執行在特殊的硬體上,同時不會減低系統的去中心化程度。

除了效能外,zk-SNARKs面臨的挑戰還有:

· 依賴於鮮有研究和缺少時間驗證的密碼學基元 (primitives);
· “有害廢棄物”-- zk-SNARKs依賴於一個可信的設定過程,其中一組人執行某種計算,並丟棄該計算的中間值。如果該過程的所有參與者互相勾結,保留了中間值,則就能建立虛假證明;
· 系統設計引入額外的複雜性;
· zk-SNARKs只適用於所有可能計算的一個子集。所以,支援圖靈完備的智慧合約語言的協議將不能使用SNARKs證明鏈的有效性。

2.5 資料可用性

我們遇到的第二個問題是資料可用性。一般來說,執行特定區塊鏈的節點分為兩種:全節點,指那些下載每一個完整區塊並驗證每一筆交易的節點;和輕節點,指那些僅下載區塊頭、並對其關注的部分狀態和交易應用默克爾證明的節點。參見圖11。

如果大部分全節點互為勾結,他們可以建立有效或無效的區塊,併傳送其雜湊值給輕節點,但從不暴露該區塊的全部內容。有多種方式可以讓他們從中受益。例如,圖12的情況:

這裡有3個區塊:前置區塊A,由誠實驗證節點建立;當前區塊B,由受賄的驗證節點簽發;以及接下來的區塊C,也將由誠實驗證節點建立(區塊鏈描繪在圖的右下角)。

假設你是個商家。當前區塊B的驗證節點從前代驗證節點手裡接收到區塊A,接著計算出你收到錢的區塊,併傳送給你一個包括默克爾證明的該塊區塊頭,顯示擁有這筆錢的狀態(或者是傳送給你錢的有效交易的默克爾證明)。你確信這筆交易已確定,所以提供了相應服務。

然而,驗證節點從未把區塊B的全部內容分發給任何人。因此,構建區塊C的誠實驗證節點無法獲取該區塊,只能強制終止整個系統,或者在區塊A上構建新塊,同時剝奪你作為商家對那筆錢的所有權。

當我們把相似的場景放到分片上,全節點和輕節點的定義一般可以對應到每個分片上:每個分片的驗證節點下載該分片的每個區塊並驗證其中的每筆交易,但是系統中的其他節點,包括那些快照分片鏈狀態到信標鏈的節點,都只下載區塊頭。因此,分片驗證節點對該分片來說,實際上就是全節點,而系統的其他參與者,包括信標鏈,就像一個輕節點那樣運作。

為了讓我們前面討論的漁夫方案發揮作用,誠實驗證節點需要能下載交叉連線到信標鏈的區塊。然而,如果惡意驗證節點交叉連線一個無效區塊的頭部(或使用它發起跨分片交易),但從不分發該區塊,那麼誠實驗證節點就無法發起質疑。我們將介紹應對該問題的三種互補的解決方案。

2.5.1 託管證明

亟待解決的最直接問題是,區塊一旦被髮布是否就是可用的。一種想法是,使用被稱為公證人(Notary)的角色,讓其在分片中以比驗證節點更快的頻率輪轉。他們唯一的工作是下載一個區塊並證明他們有能力下載它。他們之所以能更頻繁的輪轉,是因為無需下載分片的整個狀態,不像驗證節點,後者每次輪轉都要下載分片的狀態,因此不能頻繁輪轉,如圖13所示。

該想法不足之處在於,後面無法驗證某個公證人是否真能下載那個區塊。因此,一個公證人可以選擇總是聲稱他們能下載那個區塊,甚至不用嘗試獲取這個區塊。一個解決方案是讓公證人提供某種證據證明其下載了區塊或質押一定數量的通證作為擔保費。這裡討論了該類方案的其中一種:

https://ethresear.ch/t/1-bit-aggregation-friendly-custody-bonds/2236.

2.5.2 糾刪碼

當一個特定的輕節點收到一個區塊雜湊值時,為了提升節點對區塊可用性的信心,它可以嘗試下載該區塊的一些隨機碎片。這還不是一個完整的方案,因為除非輕節點聯合下載完整區塊,惡意出塊人可以選擇扣押區塊中未被任何輕節點下載的那部分內容,因此仍可以使區塊不可用。

一個解決方案是使用一種稱為“糾刪碼”的措施,即使在只有區塊的部分內容可用的情況下,也能恢復整個區塊,如圖14所示。

波卡和以太坊寧靜都採用了基於這種思想的設計,為輕節點提供了一種方式,使其能確信區塊是可用的。以太坊寧靜的實現在參考文獻2中有詳細介紹[2]。

2.5.3 波卡對資料可用性的實現

和大部分分片方案一樣,波卡每個分片(叫做平行鏈)快照它的區塊到信標鏈(叫做中繼鏈)。假設中繼鏈有2f+1個驗證節點。平行鏈的出塊人叫做整理人.平行鏈區塊一產出,整理人便計算該區塊的一個糾刪碼版本,其中包含2f+1個部分,因此任意f個部分都能重建整個區塊。

然後他們給每個中繼鏈的驗證節點分發一個部分。一個特定的中繼鏈驗證節點,只有在中繼鏈驗證節點擁有每個被快照至該中繼鏈區塊的每個平行鏈區塊的專屬部分,該驗證節點才對該中繼鏈區塊簽名。因此,如果一箇中繼鏈區塊包含來自2f+1個驗證節點的簽名,且只要其中不超過f個驗證節點違反了協議,那每個平行鏈區塊都還是能從那些遵循了協議的驗證節點手中重建出來。見圖15。

2.5.4 長期資料可用性

值得注意的是,上述方案都只能證明一件事:已經釋出一個區塊且當前可用。一段時間後,由於以下各種原因,區塊可能變為不可用:節點下線,節點故意刪除了歷史資料等。

對於該問題,Polyshard [3]的白皮書值得一提:使用糾刪碼確保區塊在分片之間是可用的,即使一些分片完全丟失了他們的資料也無妨。不幸的是,他們的特定實現需要任一分片都下載其他所有分片的區塊,成本過於高昂。

還好長期可用性問題並不太急迫,因為系統並不指望其參與者能驗證所有分片上的所有鏈。所以,分片協議的安全性設計需要能夠做到:即使一些分片的舊區塊變得完全不可用,整個系統依然是安全的。

3. 夜影分片協議

3.1 從分片鏈到分片段

這種多個分片鏈加一個信標鏈的分片模型非常強大,但也相當複雜。特別的,分叉選擇規則需要在每個鏈上獨立執行,而且分片鏈和信標鏈的分叉選擇規則一定要有區別的構建和獨立的測試。

在夜影中,我們把系統建模成一個單一的區塊鏈,其中每個塊邏輯上包含所有分片的全部交易,以及改變所有分片的整個狀態。然而,從物理的角度看,任何參與者都不會下載完整的狀態或完整的邏輯區塊。網路的每個參與者其實只是維護他們為之驗證交易的分片上對應的狀態。區塊中的所有交易的列表都被分割成物理上的段,每個分片對應一個段。

在理想的條件下,每個(邏輯)塊裡,每個分片都正好有一個分段對應。這基本上對應到分片鏈模型中,分片鏈和信標鏈以相同的速度出塊。然而,由於網路延遲,一些分段可能錯過(出塊),所以在實踐中,每個(邏輯)塊的每個分片對應著0個或1個分段。對如何出塊的詳細介紹參見3.3節。

3.2 共識

當今區塊鏈共識的兩個主流方法是:最長(或最重)鏈共識,指由最多工作量或權益打造的鏈被認為是正統鏈;以及BFT共識,指對於每個塊,都由一批驗證節點在其中達成一個BFT共識。

在最近提出的協議中,後一種共識的實現更加流行一些。因為它提供了即時的確定性,而在最長鏈規則中,需要更多的區塊建立在目標區塊之後,才能確保確定性。通常,為了達到一個嚴謹的安全等級,需要小時級別的時間才能有足夠數量的區塊(在目標區塊之後)建立出來。

對每個塊使用BFT共識,也有些缺點,例如:BFT共識涉及相當多的通訊量。儘管最新進展允許以參與者達成共識的時間與網路參與者的數量形成線性關係(見[4]),但這個工作量對每個塊來說仍然是不可忽視的;

所有網路參與者都參與每個塊的BFT共識是不現實的,因此通常僅有一個參與者的隨機樣本子集參與達成共識。一個隨機的樣本集合,原則上是可能受到自適應攻擊的,因此理論上分叉是會出現的。系統在設計上要麼需要為這種情況做好準備(因此,除了BFT共識,依然還要有分叉選擇規則),要麼就要在這種情況下關閉。值得一提的是,某些設計,例如Algorand [5],已大大降低了自適應攻擊的可能性。

最重要的是,如果1/3或更多的參與者掉線,系統將中止。因此,任何臨時的網路小故障或一個網路分裂就會使系統完全癱瘓。理想情況是,系統必須能夠繼續執行,只要至少一半的參與者線上(基於最重鏈的協議,甚至能在少於一半參與者線上的情況下繼續執行,但是這個特點是否必要在社羣內還有不少爭論)。

在一個混合模型中,共識使用的是某種最重鏈規則,但是週期性的對一些塊使用BFT確定性工具來實現其確定性。這樣就同時保有了兩種共識模型的優點。這種BFT確定性工具有用於以太坊2.0 (1)的Casper FFG [6]、Casper CBC和用於波卡的GRANDPA 。

Casper CBC:
https://vitalik.ca/general/2018/12/05/cbc_casper.html

GRANDPA:
https://medium.com/polkadot-network/d08a24a021b5)。

夜影使用最重鏈共識。尤其當一個出塊人產生一個區塊時(參見3.3節),他們可以從其他出塊人和驗證節點中收集簽名,作為對前一個區塊的證明。參見3.8節對於如何積累如此大量簽名的詳細介紹。一個區塊的權重就是所有那些在區塊中籤了名的簽名者積累的抵押權益。而一個鏈的權重就是區塊權重的和。

在最重鏈共識之上,我們使用一個確定性工具,利用證明確定區塊。為了減低系統複雜度,我們使用的確定性工具在任何情況下都不影響分叉選擇規則,而只是引入額外的罰沒質押通證條件。這樣一來,一旦一個區塊被確定性工具確定下來,就不可能出現分叉,除非佔總權益極大百分比的權益都被罰沒了。

Casper CBC就是這樣一種確定性工具,我們在設計時有參考Casper CBC。

我們也在研究一個獨立的BFT協議,叫做TxFlow。撰寫本文時,尚不清楚TxFlow是否會用來取代Casper CBC。然而,我們注意到,確定性工具的選擇在很大程度上與設計的其餘部分無關。

3.3 出塊

夜影中有兩種角色:出塊人和驗證節點。設系統有w個出塊人,以及wv個驗證節點 (v在這裡指的是驗證節點和出塊人的比例),在我們的模型裡w=100,v=100(此處v的定義原文中沒給),wv=10000。作為一個權益證明(POS)系統,意味著出塊人和驗證節點把一定數量的內部貨幣(稱為“通證”)鎖定一段時間,且這段鎖定期遠超過他們用來執行構建和驗證鏈的時間。

與所有的PoS系統一樣,不一定w個出塊人和wv個驗證節點都是不同的實體,因為這是無法強制的。然而,w個出塊人和wv個驗證節點中的每一個節點都單獨抵押權益。

系統包含n個分片,我們的模型中n=1000。正如3.1節提到的,夜影中沒有分片鏈,取而代之的是,所有的出塊人和驗證節點共同構建單一的區塊鏈,我們稱之為主鏈。主鏈的狀態被分到n個分片中。每個出塊人和驗證節點在任何時候都只在本地下載對應某個分片子集的狀態子集,且只處理和驗證影響這部分狀態的交易。

要成為出塊人,一個網路參與者鎖定一大筆通證(一筆質押權益)。網路按週期(epoch)進行維護,一個週期是數天級別的時間長度。每個週期之初,質押權益最多的前w個參與者就是該週期的出塊人。每個出塊人指派給sw個分片,(設sw=40,則每分片有 swW/n = 4個出塊人)。在週期開始前,出塊人下載所指派分片的狀態,然後在整個週期中收集影響該分片的交易,並把它們應用到狀態上。

對於主鏈上的每個塊b,和每個分片s,都有一個指定給s的出塊人負責生產b上有關該分片的區塊部分。這個部分被稱為分片段,包含了b中有關該分片的交易列表,以及結果狀態的默克爾樹根。b最終只包含該分片段的一個很小的段頭,也就是所有應用交易的默克爾樹根(具體資訊參見3.7.1節),和最終狀態的默克爾樹根。

本文剩餘部分,我們通常把在特定時間為特定分片建立分片段的出塊人稱為出段人,出段人一定是出塊人之一。

出塊人和出段人根據一個固定的安排輪換每個塊。出塊人有個順序並依序重複出塊。例如,如果有100個出塊人,第一位出塊人負責建立塊1、101、201等,第二位出塊人負責2、102、202等。

建立分片段與建立區塊不同,需要維護狀態。而且對每個分片來說,僅僅 swW/n 位出塊人維護著每個分片的狀態,相應的也就只有這swW/n位出塊人輪換建立分片段。例如,按照上面的常量設定,一個分片指定了4個出塊人,每個出塊人每四個塊建立一次分片段。

3.4 確保資料可用性

為了確保資料可用性,我們使用了跟2.5.3節描述的波卡類似的方式。一旦一個出塊人建立了一個分片段,就建立該分片段的一個糾刪碼版本,糾刪碼引數為(w, ⌊w/6 + 1⌋),然後傳送該段糾刪碼的每一片(我們稱這樣的碼片為段顆粒chunk parts,或者就叫顆粒parts)給每個出塊人。

我們計算出一棵默克爾樹,其中每個顆粒都是葉子,並在每個段的頭部都包含該默克爾樹的根。這些顆粒透過單顆粒訊息(onepart message)發給驗證節點。每條這種訊息包含該段的段頭、顆粒序號以及顆粒內容。訊息中還包含建立該段的出塊人的簽名,以及證明該顆粒對應頭部且由正確的出塊人建立的默克爾路徑。

一旦一個出塊人收到一個主鏈的塊,他首先檢查自己是否有該塊包含的每個段的單顆粒訊息。如果沒有,該塊就不被處理,直到獲取到缺失的單顆粒訊息。

一旦所有的單顆粒訊息收全了,這個出塊人從其他出塊人那裡拿來剩餘部分並重建他們為之持有狀態的那些段。

出現以下情況時,出塊人不會處理主鏈區塊:如果區塊中至少有一個分片段的對應單顆粒訊息未收到;或如果他負責維護狀態的分片中至少有一個分片無法重建出對應的完整段。

若要一個特定的分片段可用,只要有⌊w/6⌋+1的出塊人持有並能提供相關的顆粒即可。因此,只要作惡者的數量不超過⌊w/3⌋,就不會讓一個超過半數出塊人(線上)的鏈含有無效的分片段。

3.4.1 處理懶惰的出塊人

如果一個出塊人遇到一個缺失了一條單顆粒訊息的塊,他可能仍然會簽名。因為如果這個塊最終上鍊了,就能使該出塊人的利益最大化。而且這對出塊人沒有風險,因為過後無法證明這個出塊人沒有那條單顆粒訊息。

為了解決這個問題,我們讓每個出段人在建立段的時候為後面經過編碼的段的每個顆粒選擇一個顏色(紅或藍),並在編碼前將所選顏色的掩碼存入段中。每條單顆粒訊息都包含該顆粒指定的顏色,這個顏色也用來計算編碼顆粒的默克爾根。如果出段人違反協議,將被輕易檢測出來。因為,要麼默克爾根對不上單顆粒訊息,要麼匹配了默克爾根的單顆粒訊息中的顏色與段的掩碼不匹配。

當出塊人簽名一個區塊時,他將收到的該塊中所有段的紅色顆粒做成掩碼放在簽名中。釋出一個不正確的掩碼是一種可罰沒質押通證的行為。如果一個出塊人沒有收到某條單顆粒訊息,是無法知道其顏色的,因此嘗試盲籤區塊就有50%的可能性會被懲罰。

3.5 狀態轉換的執行

出段人建立段時,只是選擇哪些交易要放在段中,而不會執行狀態轉換。相應的,段頭部包含執行該段交易之前的默克爾狀態的默克爾根。僅當一個包括該段的完整區塊得到處理時,這些交易才會執行。而一個參與者僅在以下條件達成時處理區塊:

前一個區塊已經接收並得到處理;
對於不維護狀態的那些段,參與者見到了單顆粒訊息;
對於需要維護狀態的那些段,參與者擁有完整的段。

一旦區塊得到處理,對於那些需要維護狀態的每個分片,參與者執行交易並計算交易執行後的新狀態。之後,如果被分配到任何分片,參與者就準備好建立下個區塊的對應段,因為他已經有了新默克爾狀態的默克爾根。

3.6 跨分片交易和收據

如果一筆交易不止影響一個分片,就需要在不同的分片中連續獨立執行。完整的交易發給第一個相關的分片。一旦該分片的段中包含了該交易,且在該段被包含進區塊之後被執行,就會產生一筆收據(receipt)交易。該收據被路由給下一個需要執行該交易的分片。如果跨分片交易需要更多的步驟,則當執行收據交易的時候,會產生一筆新的收據交易,如此迴圈。

3.6.1 收據交易生命週期

理想的情況是,收據交易在產生收據的塊的下一個塊中立刻被執行。只有在維護源分片的出塊人接收並執行了前一個塊後,收據交易才會生成。並且,需要在目的分片的出塊人為下一個區塊建立段之前被其知曉。因此,在這兩個事件間的一段短時間內,收據必須由源分片通訊到達目的分片。

假設 A 是最後產生的區塊,包含交易 t,而 t 產生了收據 r 。把下一個將產生的區塊記為B (也就是說,這個塊將 A 作為其前置區塊),我們希望在 B 中包含 r 。假設 t 在分片a 中,而 r 在分片 b中。如圖18中所述,收據的生命週期如下:產生和儲存收據。分片 a 的出段人 cpa收到塊 A , 執行交易 t ,並生成收據r 。cpa接著將所有生成的收據儲存在它內建的持久化儲存中,以源分片的id為索引。

分發收據。一旦cpa準備為塊 B 建立分片a 的段,他獲取到所有透過執行塊 A 中分片 a 的相關交易時產生的收據,並將它們包含在塊 B 對應分片 a 的段中。段生成後,cpa產生它的糾刪碼版本,和所有對應的單顆粒訊息。cpa知道哪些出塊人維護哪些分片的全狀態。對一個特定的出塊人 bp,cpa在釋出區塊 B 裡對應分片 a 的段時,把一些收據放進單顆粒訊息中,這些收據是執行塊A中有關分片 a 的交易的結果,且這些交易的目的分片是 bp 去維護狀態的(收據放進單顆粒訊息的展示參見圖17)。

接收收據。回憶一下,參與者(包括出塊人和驗證節點)不會執行塊,除非他們有了塊中每個分片段的單顆粒訊息。因此,在任何參與者執行區塊B 的時候,他們已經獲得 B 中所有段對應的全部單顆粒訊息,也就擁有了所有傳入的收據,這些收據以參與者維護狀態的分片為目的地。當執行一個特定分片的狀態轉換時,參與者既執行單顆粒訊息中與該分片有關的收據交易,也執行該段自身包含的所有交易。

3.6.2 應對過量的收據

有可能指向一個特定區塊的特定分片的收據的數量過大,超過了其處理能力。例如,圖19的情況,每個分片的每筆交易都產生了一個指向分片1的收據。到下個區塊時,分片1需要處理的收據數量已經與上個區塊中所有分片合起來要處理的收據數量一樣多了。

要解決這個問題,我們使用一個類似QuarkChain (2) 中使用的技術。特別的,對每個分片,最後的區塊B中最後一條被執行的收據所在的分片s被記錄下來。當新的段建立時,會首先從塊B中遺留還未處理的收據開始執行,接著才是塊B之後的區塊,直到新的段被塞滿為止。

在正常情況下,隨著負載均衡,這個過程的結果是所有收據都被執行(因此每個段中記錄的都是最後一個塊的最後一個分片)。然而,當負載不均衡時,如果一個特定的分片收到了過多的收據,該技術也能允許這些收據在段中交易條數有限制的前提下被處理。

需要注意的是,如果這種負載不均衡持續了很長時間,則收據從建立到執行之間的延遲可能持續地無限增長。一種解決方式是,當收據指向的是處理延遲超過了某個常數(例如,一個週期)的分片時,該收據產生的交易會被丟棄。

考慮圖20的情況。直到區塊B時,分片4還沒有處理完所有收據。它僅處理到來自區塊A中分片3所產生的收據,並記錄了下來。在區塊C時,收據處理跟進到區塊B的分片5,最後在區塊D時,該分片趕上了進度,處理了區塊B裡所有遺留的收據和區塊C裡的全部收據。

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;