什么是LibraBFT共識(shí)協(xié)議

Libra白皮書中關(guān)于共識(shí)機(jī)制的描述

Libra區(qū)塊鏈采用了基于LibraBFT共識(shí)協(xié)議的BFT機(jī)制來實(shí)現(xiàn)所有驗(yàn)證者節(jié)點(diǎn)就將要執(zhí)行的交易及其執(zhí)行順序達(dá)成一致。這種方法可以在網(wǎng)絡(luò)中建立信任，因?yàn)榧词鼓承?yàn)證者節(jié)點(diǎn)（最多三分之一的網(wǎng)絡(luò)）被破壞或發(fā)生故障，BFT共識(shí)協(xié)議的設(shè)計(jì)也能夠確保網(wǎng)絡(luò)正常運(yùn)行。與其他一些區(qū)塊鏈中使用的“工作量證明”機(jī)制相比，這類共識(shí)協(xié)議還可實(shí)現(xiàn)高交易處理量、低延遲和更高能效的共識(shí)方法。

1. libra共識(shí)簡介

Libra的共識(shí)采用的是LibraBFT共識(shí)，是一個(gè)為Libra設(shè)計(jì)的魯棒的高效的狀態(tài)復(fù)制系統(tǒng)。它基于一種新型的BFT共識(shí)算法，HotStuff（BFT Consensus in Lens of Blockchain），在擴(kuò)展性和一致性上達(dá)到了較高的水平。LibraBFT 在HotStuff的基礎(chǔ)上引入顯示的活躍機(jī)制并提供了具體的延時(shí)分析。LibraBFT在3f+1個(gè)驗(yàn)證節(jié)點(diǎn)之間收集投票，這些驗(yàn)證者可能是誠實(shí)的節(jié)點(diǎn)也可能是拜占庭節(jié)點(diǎn)。在網(wǎng)絡(luò)中有2f+1個(gè)誠實(shí)節(jié)點(diǎn)的前提下，Libra能夠抵御f個(gè)驗(yàn)證節(jié)點(diǎn)的雙花攻擊和分叉攻擊。LibraBFT在一個(gè)有全局統(tǒng)一時(shí)間（GST），并且網(wǎng)絡(luò)最大延時(shí)（ΔT）可控的 Partial Synchrony的網(wǎng)絡(luò)中是有效的。并且，LibraBFT在所有驗(yàn)證節(jié)點(diǎn)都重啟的情況下，也能夠保證網(wǎng)絡(luò)的一致性。

Libra白皮書指出，其將以許可型區(qū)塊鏈的方式起步。未來為了確保Libra的真正開放，始終以符合用戶最佳利益的方式運(yùn)作，F(xiàn)acebook的最終目標(biāo)是讓Libra網(wǎng)絡(luò)成為“非許可型網(wǎng)絡(luò)”，但是其目前的挑戰(zhàn)在于，他們目前還沒有成熟的解決方案可以通過非許可型網(wǎng)絡(luò)，提供支持全球數(shù)十億人和交易所需的規(guī)模、穩(wěn)定性和安全性。從“許可型”網(wǎng)絡(luò)過渡到“非許可型”網(wǎng)絡(luò)，共識(shí)層面還需要做非常大的改進(jìn)。

2. HotStuff算法

2.1 HotStuff算法特點(diǎn)

HotStuff 是一個(gè)三階段的BFT算法，允許一個(gè)新的leader簡單地選擇一個(gè)最新的的QC（Quorum certification）。它引入了一個(gè)第二階段，允許副本在投票后在不需要請求leader請求的基礎(chǔ)上改變他的決策。這一改進(jìn)大大降低了復(fù)雜度，同時(shí)也降低了leader替換的復(fù)雜度。最后，由于長期委任所有的狀態(tài)，這樣HotStuff非常容易通過事件機(jī)制的方式實(shí)現(xiàn)，適合leader經(jīng)常切換的場景。HotStuff主要有以下幾個(gè)特性：

? 線性的視圖切換：在GST后，對于一個(gè)誠實(shí)的leader，一旦被指定，會(huì)發(fā)給n個(gè)驗(yàn)證者來收集簽名，以推動(dòng)共識(shí)的決定；

? 樂觀的響應(yīng)：在GST后，對于一個(gè)誠實(shí)的leader，一旦被指定，只需要等最早的 n-f 個(gè)驗(yàn)證者返回消息就可以發(fā)起有效的提案，包括leader替換；

? 支持頻繁切主：HotStuff還有一個(gè)特點(diǎn)是新leader的推動(dòng)協(xié)議達(dá)成共識(shí)的成本不高于當(dāng)前領(lǐng)導(dǎo)者的成本，所以其適用于leader切換的協(xié)議；

? 決策簡單：HotStuff中副本只有兩種消息類型和一個(gè)簡單的規(guī)則來決定是否要接受一個(gè)提案，其通過投票和提交規(guī)則來達(dá)成一致性，通過Pacemaker來保證可用性，并且各階段的算法復(fù)雜度低；

? 閾值簽名：HotStuff使用閾值簽名的方式來收集簽名，使得簽名的驗(yàn)證會(huì)更為簡單；

2.2 HotStuff算法流程

2.2.1 Basic HotStuff

Basic HotStuff 協(xié)議是HotStuff的基本過程，他在一系列的視圖中切換，視圖以單調(diào)遞增編號(hào)方式切換。在每個(gè)視圖內(nèi)，有一個(gè)唯一的達(dá)成共識(shí)的leader。每個(gè)副本在起本地?cái)?shù)據(jù)結(jié)構(gòu)中會(huì)記錄所有請求的tree，tree的每個(gè)葉子節(jié)點(diǎn)是一個(gè)已經(jīng)提出的提案。一個(gè)給定節(jié)點(diǎn)的分支是該節(jié)點(diǎn)到達(dá)樹根的所有路徑。按照HotStuff協(xié)議，隨著視圖的增長，分支會(huì)被提交。Leader需要像（n-f）個(gè)驗(yàn)證者采用閾值簽名的方式收集簽名，收集簽名的過程主要包括3個(gè)階段，PREPARE、PRE-COMMIT和COMMIT階段，整個(gè)算法包括5個(gè)階段，PREPARE、PRE-COMMIT、COMMIT、DECIDE和FINALLY階段，如下圖所示：

1. PREPARE階段：該階段，leader發(fā)起一個(gè)high的提案（highQC），組成消息，消息內(nèi)容 m = MSG（PREPARE， curProposal，highQC），并廣播給所有的驗(yàn)證節(jié)點(diǎn)；驗(yàn)證節(jié)點(diǎn)在收到時(shí)上述提案消息后會(huì)進(jìn)行投票，如果m的node超過本地已經(jīng)判決過的node是則會(huì)投票，并返回消息給leader，m‘ = voteMSG（PREPARE，n.node，⊥）。

2. PRE-COMMIT階段：該階段，當(dāng)Leader收到（n-f）個(gè)驗(yàn)證節(jié)點(diǎn)的PREPARE階段的投票信息后，會(huì)發(fā)起一個(gè) PREPARE的提案（prepareQC），組成消息，消息內(nèi)容為 m = MSG（COMMIT， ⊥，prepareQC），并廣播給所有的驗(yàn)證節(jié)點(diǎn)；驗(yàn)證節(jié)點(diǎn)在收到上述提案消息后會(huì)進(jìn)行投票，并返回消息給leader，m’ = voteMSG（PRE-COMMIT，m.justify.node，⊥）。

3. COMMIT階段：該階段，當(dāng)Leader收到（n-f）個(gè)驗(yàn)證節(jié)點(diǎn)的PRE-COMMIT階段的投票信息后，會(huì)發(fā)起一個(gè) PRE-COMMIT的提案（precommitQC），組成消息，消息內(nèi)容為 m = MSG（COMMIT， ⊥，precommitQC），并廣播給所有的驗(yàn)證節(jié)點(diǎn)；驗(yàn)證節(jié)點(diǎn)在收到上述提案消息后會(huì)進(jìn)行投票，并返回消息給leader，m‘ = voteMSG（COMMIT，m.justify.node，⊥）。

4. DECIDE階段：該階段，當(dāng)Leader收到（n-f）個(gè)驗(yàn)證節(jié)點(diǎn) COMMIT 的投票后，會(huì)生成一個(gè)COMMIT的提案（commitQC），組成消息，消息內(nèi)容為 m = MSG（DECIDE，⊥，commitQC），并廣播給所有的驗(yàn)證者；驗(yàn)證者在收到該消息后，會(huì)執(zhí)行命令，并返回給客戶端。

5. FINALLY階段：如果系統(tǒng)進(jìn)入下一個(gè)View，各個(gè)副本會(huì)發(fā)送一個(gè)消息給下一個(gè)View的leader，消息內(nèi)容為 m = MSG（NEW-VIEW，⊥，prepareQC）。

2.2.2 Chained HotStuff

上圖中可以看出來Basic HotStuff的各個(gè)phase中的流程都非常相似，作者又提出了一種Chained HotStuff來優(yōu)化和簡化Basic HotStuff。改進(jìn)的點(diǎn)主要是改變每個(gè)PREPARE節(jié)點(diǎn)的View。這將大大降低通信消息的數(shù)量，并且可以對決策進(jìn)行管道處理。Chained HotStuff的流程如下所示：

上述Figure1可以看出一個(gè)節(jié)點(diǎn)可以同時(shí)處于不同的View，通過鏈?zhǔn)降慕Y(jié)構(gòu)，一個(gè)提案在經(jīng)過3個(gè)塊后能夠達(dá)成共識(shí)。其內(nèi)部有一個(gè)狀態(tài)轉(zhuǎn)換器，通過genericQC實(shí)現(xiàn)提案的自動(dòng)切換。其主要算法流程如下所示：

3. LibraBft改進(jìn)

Libra 為了更好地適應(yīng)其生態(tài)，對HotStuff進(jìn)行了相應(yīng)的優(yōu)化，主要有5點(diǎn)：

1.首要的是Libra定義了安全的條件，提供了安全性、活性和樂觀響應(yīng)的擴(kuò)展證明；

2.第二點(diǎn)：Libra 通過讓驗(yàn)證器集體對區(qū)塊的狀態(tài)而不是事務(wù)的順序進(jìn)行簽名，使得協(xié)議會(huì)更加魯棒。同時(shí)還允許客戶端使用QC驗(yàn)證從數(shù)據(jù)庫里讀出的數(shù)據(jù)。

3.第三點(diǎn)：Libra 設(shè)計(jì)了一個(gè)Pacemaker 來發(fā)出顯示的超時(shí)信號(hào)，驗(yàn)證者通過他發(fā)出的提案自動(dòng)進(jìn)入下一個(gè)視圖，而不需要一個(gè)同步的時(shí)鐘；

4.第四點(diǎn)：Libra 希望讓礦工變得不可預(yù)測，它最新提交的區(qū)塊信息為種子生成一個(gè)可驗(yàn)證的隨機(jī)數(shù)VRF，成為下一個(gè)礦工；

5.第五點(diǎn)：Libra 使用聚合簽名的方式保留QC中驗(yàn)證者的身份，以提高驗(yàn)簽效率，同時(shí)為這些驗(yàn)證者提供獎(jiǎng)勵(lì)。