Alaya共識方案詳解(三):初識Giskard共識協議

前面的內容中,我們分析了BFT共識協議的問題,以及幾種主流的最佳化BFT共識協議,這些BFT共識協議在降低通訊複雜度和出塊效率方面都取得了不錯的研究成果,但仍存在一些改進空間。
· PBFT較之於之前的BFT演算法雖更實用,但因受制於O(n³)的檢視切換開銷,在擴充套件性方面存在很大的問題。

· Tendermint將round change和正常流程合併,簡化了檢視切換邏輯,將檢視切換的通訊複雜度降低為O(n²),但需要等待一個比較大的網路時延來保證活躍性。同時Tendermint仍然是序列出塊和確認,一個區塊的投票需要等上一個區塊commit完成才能開始。

· EOS的BFT-DPOS共識協議中,區塊生產者可以連續產生若干區塊,同時區塊採用並行確認,提高了出塊速度。使用BFT協議確認出塊,但僅適用於強同步的通訊模型。

· HotStuff創新地提出了基於leader節點的、三階段提交的BFT共識協議,吸收了Tendermint的優點,將viewchange和正常流程合併,並將viewchange的通訊複雜度降至線性。同時透過簡化訊息型別,可以以pipeline的方式確認區塊。但引入了新的投票階段也會增加通訊複雜度,同時一個檢視視窗只確認一個區塊,這無疑需要耗費較多的通訊複雜度在檢視切換上。此外,基於Leader節點收集投票的星狀拓撲結構,比較適合於Libra這種網路環境良好的聯盟鏈,在弱網環境中比較容易受單點故障影響,造成較大的leader節點切換開銷。

因此,我們提出了Giskard共識協議,在以上共識協議的基礎上進行進一步的最佳化,可以極大地降低通訊複雜度,並且提高出塊效率。

Giskard共識協議概述

Giskard共識協議基於部分同步網狀通訊模型,提出了一個三階段共識的並行拜占庭容錯協議。網狀的通訊模型更適合公網的弱網環境,在Alaya上已經使用了該協議作為共識演算法。

Giskard共識協議的正常流程和Hotstuff類似,分為prepare,pre-comit,commit和decide幾個階段。但Giskard還作了關鍵的改進:在一個檢視視窗內可以連續提議多個區塊,下一個區塊的產生不用等上一個區塊達到QC;而且各個節點可以在接收上一個區塊投票的同時,並行執行下個區塊的交易,以pipeline的方式對區塊進行投票確認,從而極大提高了出塊速度。

Giskard共識協議有自適配的檢視切換機制:在一個檢視視窗內,節點接收到足夠多的區塊以及贊成票(超過2/3的節點投票,也就是 QC)時,會自動進行視窗切換,切換到下一個視窗,無需進行viewchange投票。只有時間視窗超時後,節點才會啟動viewchange流程,並且在viewchange階段引入了和Hotstuff一樣的二階段鎖定投票規則,同時使用BLS聚合簽名,可以在O(n²)的通訊複雜度內完成檢視視窗切換。

根據上面的討論,Giskard共識協議只在正常流程之外才會進行viewchange,因此相比HotStuff會有更少的檢視切換開銷。

接下來先給出Giskard共識協議共識中涉及的相關概念及其含義說明,便於之後對Giskard共識協議進行詳細介紹。

Giskard共識協議相關術語:

提議人(Proposer):Giskard共識協議中負責出塊的節點

T: 時間視窗,每個提議人只能在自己的時間視窗進行出塊
N: 共識節點總數
f: 拜占庭節點最大數量

足夠多贊成票: 表示為至少收到N-f張贊成票
驗證人(Validator): 共識節點中非提議人節點
檢視(View): 當前提議人的時間視窗可以產生區塊的時間範圍
ViewNumber: 每個時間視窗的序號,隨著時間視窗遞增
HighestQCBlock: 本地最高的N-f 個PrepareVote區塊
ProposalIndex: 提議人的索引號
ValidatorIndex: 驗證人的索引號
PrepareBlock: 提議的區塊訊息,主要包含區塊(Block),提議人索引號

PrepareVote: 驗證人對提議區塊的Prepare投票,每個驗證人需要執行區塊後才傳送PrepareVote。主要包含ViewNumber, 區塊hash, 區塊高度,驗證人索引號(ValidatorIndex)

ViewChange: 當時間視窗超時,提議人的區塊沒有都收集N-f個PrepareVote,則會向下一個提議人傳送ViewChange。ViewChange包含提議人索引號(ValidatorIndex),最高確認區塊(HighestQCBlock)
鎖(Lock): 對指定塊高進行鎖定
Timeout: 超時(時間視窗到期可以看作提議人的超時時間)
法定: 最大被允許
同一個View: 兩個View的ViewNumber相等,可以成為同一個View

BLS簽名

目前業界採用的聚合簽名方案主要是BLS聚合簽名。BLS聚合簽名是在BLS簽名方案基礎上的擴充套件方案。Boneh-Lynn-Shacham(BLS)簽名方案是Dan Boneh,Ben Lynn, Hovav Shacham[9]於2001年提出的。BLS簽名目前在許多區塊鏈專案如Dfinity、Filecoin、Libra中都得到了運用。BLS聚合簽名可以把多個簽名簡化為1個聚合簽名,對於提高BFT共識協議中的通訊效率至關重要。

值得注意的是,BLS聚合簽名的方法是有漏洞的。一種被稱為rogue public key的攻擊可以使得攻擊者有機會在獲得其他簽名者的公鑰和標準BLS簽名資訊之後,能夠操縱聚合簽名的輸出結果。

對這個攻擊的一種最直接的防禦措施是,參與BLS聚合簽名的人都需要先證明各自確實掌握了BLS私鑰資訊,並事先註冊。這一過程可以透過使用一種簡單高效的零知識證明技術(Schnorr非互動式零知識證明協議)完成。參與者在進行聚合簽名之前,需要給出零知識證明,證明其持有公鑰資訊的同時,確實掌握了該公鑰對應的私鑰資訊。

免責聲明:

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

推荐阅读