Zilliqa博客發布，Rita譯

Nakamoto共識協議（或PoW）不理想以及為什么Zilliqa需要一個不同的共識協議。Zilliqa使用的共識協議被稱為實用拜占庭容錯（PracticalByzantine Fault Tolerance），簡稱pBFT，該協議具有計算成本低、在低能耗的情況下即可賦予交易最終性、提出下個區塊無需確認等多個優點。

然而，卡斯特羅和利斯科夫（Castroand Liskov）在其論文（鏈接https://dl.acm.org/citation.cfm?id=296824）中設計的經典pBFT 只有在共識組（在Zilliqa中指一個分片）較小時，例如少于50個節點，才具有較高的通信效率。當共識組變大，節點之間的通信成本將驟升從而成為效率的障礙。而我們此前的文章提到，Zilliqa中任何分片都必須有至少600個節點才能確保其中拜占庭節點（即惡意節點）的比例低于三分之一的概率非常低。

本文是此系列文章的終篇，我們將討論經典pBFT協議對通信的要求有多高以及我們如何使用多重簽名的方法來降低這個要求。

在本文中，我們將用n來表示共識組的大小， Zilliqa中n假設等于600。

pBFT的通信成本

在此前提到的論文中，經典pBFT要求每個節點與所有其他節點通信共享協議消息，從而對系統狀態達成一致。這意味著每個節點都必須發送n條消息，因此總的通信數量為n2，這一通訊成本是很高的。

認證消息的成本

此外，在拜占庭網絡中僅僅發送消息是不夠的。特別是在一個公開的拜占庭網絡中，當節點A接收到來自節點B的消息時，A必須確定該消息確實由B發送，且該消息在傳輸過程中未被修改，沒有這種保證，節點就很難確保消息的真實性，因為黑客可以在中間環節修改消息并給節點提供不正確的信息。

一種驗證消息傳輸的解決方案是在A和B之間生成保密的密鑰，然后可以使用該密鑰為每個傳出的消息生成“標簽”。由于只有A和B知道密鑰，所以標簽只能由A或B生成，從而他們可以驗證消息的來源。

消息認證碼（MessageAuthentication Code，簡稱 MAC）是可以生成這種標簽的加密方法。構建MAC的一種可能方式是使用加密散列函數（cryptographichash function），該函數將密鑰和消息作為輸入并生成標簽作為輸出。

下圖顯示了發送者和接收者使用MAC的方式。發送者用消息和密鑰通過MAC生成標簽，并將其與消息一起發送給接收者。接收者再次計算MAC得到一個標簽，將之與收到的信息進行比對，確認兩者是否吻合，如吻合則該消息未被篡改。

然而，MAC和大多數對稱密鑰方法的問題在于，如果我們有n個節點，每對節點都需要一個密鑰。因此，如果我們有n個節點，總共需要n（n-1）/ 2個密鑰。

那么MAC的通信成本到底是多少？如果我們在網絡中有4個節點A、B、C、D，當A要向整個網絡即向B、C、D發送消息時，A要創建3個不同的標簽因為A與B、C、D分別有不同的密鑰。現在，假設A用B作為中繼（relay）將標簽傳送到C和D，那么A將需要向B發送3個標簽（參見下圖）。B在收到它的標簽后，用C作為中繼將A的標簽轉發給C和D時，它只會向C發送2個標簽。以此類推，使用這種簡單的基于中繼的廣播機制分發的消息總數為3 + 2 + 1 = 6。

此圖顯示出一條消息在網絡中傳輸的方式。三種不同的顏色顯示出A創建的三個不同的標簽，A先將三個標簽發送給B，B再將兩個標簽發送給C，最后C轉發最后一個標簽給D。

對于具有n個節點的網絡，如果我們使用MAC，則以標簽形式發送的消息總數為：（n-1）+（n-2）.. + 1 = n（n-1）/2。

采用公鑰密碼學提高效率

因為驗證消息上的簽名也可以確保該消息確實是由合法的發送者簽發的，因此MAC實際上可以用數字簽名來替代。卡斯特羅和利斯科夫之所以沒有使用數字簽名是因為，當時計算MAC比生成數字簽名計算量便宜得多。如今，數字簽名的計算量已經相當便宜。

而且，公鑰密碼學自身有很多優點。為了理解這一點，我們繼續使用前面的例子。現在，我們假設A、B、C、D節點使用數字簽名。因此當A發送消息時，它將簽署消息并由此產生簽名。請注意，A在這里不需要創建三個簽名，只有一個就夠了。然后簽名被發送到下一個節點B，B在此只收到一條消息和相應的簽名，B再發給下一個節點C。以此類推，在每個節點，只有一個簽名被轉發，在這種情況下分發的消息總數將為1 + 1 + 1 = 3。

使用數字簽名的傳輸模式時。A只需要為每個消息生成一個簽名。

對于具有n個節點的網絡，如果我們使用數字簽名，則所傳遞的消息總數將為：1 + 1 +1 …(n-1)次= n-1。

最近有篇學術論文提出了用數字簽名取代MAC的想法

鏈接：

https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/kogias

使用數字簽名而不是MAC將發送消息的數量從二次方數量級減少到線性，當n很大時這種減少會產生重要影響。以600個節點為例，其中傳播的消息數量可以從17.97萬減少到599。

使用多重簽名方案減少每個消息的大小

講到這兒，你應該相信使用數字簽名比MAC能更好地減少網絡中需傳輸消息的數量了吧，那么接下來就讓我們用數字簽名來替換傳統pBFT協議中的MAC。

現在的問題是，我們是否找到比數字簽名更好的方法呢?答案是肯定的!數字簽名確實還有一定的改進空間，我們會在未來的博客中更多地介紹這個內容。現在先讓我們看一下數字簽名有哪些可以改進的地方。

我們知道，pBFT賦予了交易最終性，這意味著一旦交易被提交到區塊鏈，那么它就是最終的了且不會有臨時分叉，因此不需要確認。交易之所以有最終性是因為，pBFT協議本身已要求每個區塊必須由共識組中的絕對多數誠實節點簽署。每個誠實的節點通過簽名確認它已經驗證了塊的內容，確保交易有效。而在基于PoW的共識中，每個節點都可以生成一個區塊，而網絡的其他節點或接受或拒絕它，這就會導致臨時分叉的產生。

具體的簽名方法是：每個節點簽署一個區塊，然后將簽過名的區塊轉發到網絡的其余部分，之后其余節點都將自己的簽名附加在這個區塊上，最終在廣泛傳播后，這個區塊就會獲得絕大多數誠實節點的簽名。如果網絡中的每個節點(包括惡意節點)都對該區塊進行簽名，那么區塊的簽名數量為n，在這里我們就需要引入多重簽名的概念了：多重簽名是一種密碼術語，指的是把一條信息上的n個節點簽署的n個簽名整合到一個大小固定的簽名上。

簡化的多重簽名如何工作

在介紹細節之前，讓我們先了解一下背景：在多重簽名方案中，我們有n個簽名者，每個簽名者都有一對密鑰(公鑰和私鑰)、一個驗證簽名的驗證者和一個匯總各方“簽名”的聚合者(aggregator)。為了便于理解，我們現在簡單假設所有節點都是誠實的，并且會配合簽署消息。

驗證者在檢驗匯總后的簽名時，會檢查所有簽名者是否都正確地簽了名。僅當驗證者確認所有簽名者都正確地簽了名之后，驗證才算通過，反之則驗證失敗。

接下來讓我們深入細節，請做好準備，因為這有些偏技術性。

多重簽名方案基本上分兩步進行。在協議的第一步中，每個節點將其公鑰發送給聚合者，聚合者根據公鑰的數學形式，通過簡單的加法或乘法將之聚合為一個單一的公鑰。

例如，聚合公鑰= 公鑰_1 + 公鑰_2 + …+公鑰_n。

然后聚合者將聚合公鑰轉發給驗證者從而可以使后者驗證聚合簽名，與此同時聚合者也將聚合公鑰發送給每個簽名者讓所有人簽名。

在第二步中，聚合者啟動與每個簽名者的交互協議（interactiveprotocol）。這個交互協議總分包含三個階段：

1、提交階段（Commit phase）：此階段每個節點生成一些隨機內容并提交給交互協議。如果你不了解什么是加密提交（cryptographiccommitment），那么可以通過這種類比的方式理解：每個節點都秘密地擲骰子，然后將結果寫在一張紙上并將其放在一個盒子中鎖好，最后發送給聚合者。聚合者無權打開盒子。

2、挑戰階段（Challenge phase）：此階段聚合者首先使用加法或乘法將所有的提交聚合為一個聚合提交，然后使用它以及聚合公鑰、消息生成一個挑戰，再將挑戰發送到所有節點。之后挑戰可用于確認所有節點都知道公鑰對應的私鑰。這與常規數字簽名的工作方式類似，即由簽名證明簽名人確實知道私鑰。

3、回應階段（Response phase）：所有節點為了應對挑戰會向挑戰發送私鑰進行回應，之后聚合者將聚合所有的回應。因此回應可被視為簽名者知道其公鑰對應的私鑰的證據。

因此，最后的聚合簽名實際上是挑戰和聚合回應的信息對，并能驗證第一步生成的聚合公鑰。

值得注意的是，聚合簽名的大小不取決于簽名者的數量，它是固定的。

圖中藍色的節點是聚合者。H是用于將消息m生成挑戰的密碼散列函數。聚合簽名就是R和S的信息對。R的大小等于Ri，S的大小等于Si的。僅在知道私鑰的情況下才能生成有效的回應。

當驗證者檢查聚合簽名時，它檢查的不是每個單獨簽名者是否都正確地遵守協議，而是檢查所有簽名者作為一個整體是否正確地遵守協議并知道私鑰。因此，驗證者做出的決定是全有或全無（all-or-nothing）。

目前一種比較流行的多重簽名方案是基于Schnorr數字簽名技術的并由于一篇學術論文（鏈接https://arxiv.org/abs/1503.08768）得到了關注，該論文在一些證人需要證明事件發生的背景下使用了這個技術。

結論

Zilliqa使用了近期一些學術論文中的技術來提高經典pBFT協議的效率。

本文的主要亮點是多重簽名協議將簽名數量從n減少到1，從而減少認定后的區塊的大小。

還有一些問題在這篇文章里面沒有涉及，最重要的一個問題就是如果只是絕對多數節點而不是所有節點對信息進行了簽名，那么這個協議還有效嗎?需要對協議做出什么樣的修改?另外，你覺得有什么方法可以攻擊這個簡單版的多重簽名?

要回答這些疑問，你可以通過兩種方法：比較難的方法是閱讀 Zilliqa的技術白皮書，鏈接：

https://docs.zilliqa.com/whitepaper.pdf

?

總結

以上是生活随笔為你收集整理的Zilliqa 的设计构思 第3部分：使共识更有效的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。