摘要

本文研究了動態(tài) BFT，其中副本可以動態(tài)地加入和離開系統(tǒng)，這是當(dāng)今越來越需要的一種原語。我們?yōu)閯討B(tài) BFT 協(xié)議提供形式化處理，賦予它們靈活的語法和各種安全定義。

我們展示了將靜態(tài) BFT 擴展到動態(tài) BFT 的挑戰(zhàn)。然后我們設(shè)計并實現(xiàn)了部分同步模型下的高效動態(tài) BFT 協(xié)議 Dyno。我們展示了 Dyno 可以無縫處理成員資格更改，而不會導(dǎo)致性能下降。

1 介紹

拜占庭容錯狀態(tài)機復(fù)制 (BFT) 傳統(tǒng)上被稱為構(gòu)建關(guān)鍵任務(wù)系統(tǒng)的原語。如今，BFT 獲得了突出地位，因為它被視為區(qū)塊鏈的核心構(gòu)建塊：BFT 被稱為許可區(qū)塊鏈的模型 [54]，其中成員資格是靜態(tài)的，分類帳（副本）知道彼此的身份，但可能不信任彼此。BFT 也越來越多地以各種方式在無許可區(qū)塊鏈中使用（這些協(xié)議也稱為混合區(qū)塊鏈 [26、27、56]）。本文研究了具有動態(tài)成員資格的 BFT，或簡稱為動態(tài) BFT，其中副本可以動態(tài)地加入和離開系統(tǒng)。動態(tài) BFT 是一種傳統(tǒng)上可能被視為從系統(tǒng)角度實現(xiàn)理想功能的原語，如今越來越需要作為無數(shù)區(qū)塊鏈和安全應(yīng)用程序的核心構(gòu)建塊。

正?；謴?fù)和重新配置。與任何靜態(tài)分布式系統(tǒng)一樣，靜態(tài) BFT 系統(tǒng)具有實際限制 [46]：例如，如果其中一個副本崩潰、需要維護或被認(rèn)為有故障，則系統(tǒng)始終可用的概率會降低?；謴?fù)有故障的節(jié)點可能并不總是可行的，因為恢復(fù)節(jié)點可能需要時間，更重要的是，恢復(fù)可能并不總是可行的（例如，由于永久性硬件故障）。在這種情況下，更好的方法是創(chuàng)建一個新的副本來替換有故障的副本。

主動恢復(fù)。動態(tài) BFT 可用于構(gòu)建具有長期主動恢復(fù)功能的強大 BFT 系統(tǒng)。在許多先前的工作中已經(jīng)研究了主動安全 BFT 系統(tǒng)的問題 [10, 51]。這些系統(tǒng)使用受信任的硬件來定期重啟節(jié)點，希望它能驅(qū)逐對手。然而，對手（例如病毒）很可能會留在系統(tǒng)中，從而使這些努力毫無用處。然而，新鮮的副本沒有這樣的問題。因此，動態(tài) BFT 為傳統(tǒng)的主動恢復(fù)方法提供了一種替代方案，可以說是更好的解決方案。

聯(lián)盟區(qū)塊鏈。 BFT 的靜態(tài)成員屬性可能會極大地限制聯(lián)盟區(qū)塊鏈的適用性。區(qū)塊鏈實體可以選擇（或被迫）離開聯(lián)盟，而新實體可以加入聯(lián)盟。例如，現(xiàn)在更名為 Diem 的 Libra 已經(jīng)面臨這樣的情況，在 BFT 達成協(xié)議后，動態(tài)成員資格由其智能合約管理。

混合區(qū)塊鏈。使用 BFT 的混合區(qū)塊鏈需要選擇固定數(shù)量的 BFT 副本，稱為委員會，很容易成為坐鴨。能夠在保持系統(tǒng)正常運行的同時更換委員會是至關(guān)重要的。

A. 技術(shù)挑戰(zhàn)和我們的貢獻

動態(tài) BFT 的正式處理。盡管需要動態(tài) BFT，但到目前為止，還沒有為動態(tài) BFT 提供嚴(yán)格的形式化。雖然在崩潰故障模型 [11, 46] 和拜占庭故障模型 [20, 39, 40] 中定義了一些相關(guān)的原語，但對于具有可證明安全性的動態(tài) BFT 缺乏良好的抽象。從現(xiàn)代的角度來看動態(tài) BFT——在“區(qū)塊鏈時代”——早就應(yīng)該了。本文填補了這一空白，并提供了對動態(tài) BFT 的正式處理。我們的規(guī)范涵蓋了將 BFT 與成員服務(wù)分開的語法，這是一種源自 Schipper 為崩潰故障模型 [46] 所做的工作的方法。然而，我們對安全性的定義卻發(fā)生了相當(dāng)不同的轉(zhuǎn)變，通過處理模糊不清的常規(guī)請求和成員請求。更重要的是，我們的處理具有以下兩個特征：

? 在將安全定義提升到動態(tài) BFT 時，我們定義了一個新屬性（一致交付），我們認(rèn)為該屬性對動態(tài) BFT 的安全性至關(guān)重要。我們展示了一些自然和替代交付屬性無法正常工作。

? 我們的處理包括針對動態(tài)BFT 的不同“正確”概念的許多安全定義，每一個都有意義，從我們可以想象的最弱到最強。

識別動態(tài) BFT 的（新）問題。盡管動態(tài)成員的長期工作（主要在崩潰容錯系統(tǒng)中），我們發(fā)現(xiàn)了一些（新的）問題：

? 由于動態(tài)仲裁引起的問題（在第 IV 節(jié)中指定）。在動態(tài) BFT 中，成員資格的變化會導(dǎo)致 quorum 大小的變化，從而產(chǎn)生各種活躍度問題。

? 由于視圖更改（在第 IV 節(jié)中指定）引起的問題。在具有視圖變化的動態(tài) BFT（即領(lǐng)導(dǎo)者選舉）中，也存在各種問題。例如，下一個領(lǐng)導(dǎo)者可能無法收集到足夠多的視圖更改消息，甚至可能不知道視圖更改正在發(fā)生。更糟糕的是，多個副本可能會聲稱它們是同一視圖中的領(lǐng)導(dǎo)者。

? 由于消息傳遞引起的問題（在第 III-E 節(jié)中指定）。

靜態(tài)分布式系統(tǒng)有一個消息傳遞假設(shè)，即在正確的副本之間傳輸?shù)南⒆罱K會被傳遞。這個假設(shè)不適用于動態(tài)設(shè)置，因為一些正確的副本雖然在發(fā)送消息時是正確的，但可能會在將來的某些配置中離開系統(tǒng)。我們發(fā)現(xiàn)，即使是安全分布式計算社區(qū)中的一些經(jīng)典協(xié)議（例如，[46]）也只是假設(shè)跨配置的消息傳遞，并且這些協(xié)議的證明實際上是有缺陷的。

配置發(fā)現(xiàn)協(xié)議。我們的協(xié)議依賴于配置發(fā)現(xiàn)子協(xié)議，客戶端和新副本在其中獲得系統(tǒng)的成員資格。配置發(fā)現(xiàn)協(xié)議不僅從功能角度至關(guān)重要，而且對于我們動態(tài) BFT 協(xié)議的正確性也很重要。我們提供了一種這樣的協(xié)議，它使用顯式成員發(fā)現(xiàn)。我們還在附錄中介紹了兩個使用隱式成員發(fā)現(xiàn)的替代協(xié)議。

結(jié)構(gòu)、假設(shè)及其呈現(xiàn)。我們考慮兩個不同的假設(shè)：標(biāo)準(zhǔn)仲裁假設(shè)（假設(shè)每個配置的最佳彈性）和 G 正確假設(shè)（假設(shè)一部分正確的副本永遠不會離開系統(tǒng)）?；诿總€假設(shè)，我們提供滿足我們提出的不同安全定義的協(xié)議。我們首先介紹論文中的主要協(xié)議 Dyno。然后我們介紹 Dyno 的變體。我們正式證明了所有協(xié)議的安全性。

我們的目標(biāo)之一是無縫處理會員變更。 Dyno 保留了底層 BFT 協(xié)議的全部效率，并且可以獨立于視圖更改來處理成員請求。然而，Dyno 確實對正常情況下的操作和底層 BFT 協(xié)議的視圖更改機制進行了重大修改，同時沒有增加性能開銷。我們展示了 Dyno 在各種加入和離開場景下的高效和魯棒性。

2 相關(guān)工作

BFT。作為一種容忍任意故障的通用方法，BFT 可以分為同步 BFT [1]、部分同步 BFT [10、14、15、50] 和異步 BFT [16、17、33]。在這項工作中，我們專注于部分同步 BFT。主分區(qū)與可分區(qū)成員服務(wù)。成員服務(wù)可以是主分區(qū)或可分區(qū)的 [11]。在主分區(qū)服務(wù)中，所有副本的視圖都是完全有序的。在可分區(qū)視圖中，視圖是部分排序的，即多個不相交的視圖可能同時存在。本文只研究主分區(qū)模型。

動態(tài)群組交流。組成員資格問題和視圖同步通信問題首先由 Birman 和 Joseph [7] 討論。組成員抽象提供了活動成員的動態(tài)但一致的視圖。視圖同步通信 [7, 47] 擴展組成員資格以支持視圖成員內(nèi)的可靠廣播。擴展虛擬同步[37]擴展了虛擬同步，確保消息傳遞和所有副本的配置更改之間的關(guān)系保持一致。 Spread [5] 和 Secure Spread [4] 在碰撞故障模型中包含虛擬同步和擴展虛擬同步。 Secure Spread 通過身份驗證、完整性、訪問控制和機密性增強了 Spread。

Chockler 等人 [11] 對動態(tài)組通信系統(tǒng)進行了全面調(diào)查：首先定義組成員服務(wù)（用于添加和刪除進程），而在第二步中指定通信原語（例如，可靠廣播、原子廣播） .在這些系統(tǒng)中，組成員服務(wù)是各種通信棧的基礎(chǔ)層。相比之下，Schipper 的規(guī)范首先描述了通信原語，然后是成員更改，并允許所有成員更改來自對成員請求的顯式調(diào)用 [46]。例如，為原子廣播定義的原語稱為動態(tài)原子廣播，或簡稱為原子多播。 Schipper 認(rèn)為，這種選擇會導(dǎo)致更“自然”和更簡單的規(guī)范。 Schiper [46] 還表明，他的規(guī)范在活性屬性方面與 [11] 中調(diào)查的規(guī)范略有不同。

Guerraoui 等人最近提出了動態(tài)拜占庭可靠廣播 (DBRB)，其中副本可以動態(tài)地加入和離開系統(tǒng) [20]。從定義的角度來看，DBRB 解決了與我們的（共識）相當(dāng)不同的問題（廣播），并專注于異步設(shè)置。從技術(shù)角度來看，DBRB 允許最終收斂到同一視圖的不同視圖路徑。

Rampart [39] 和 SecureRing [25] 在拜占庭故障模型中實現(xiàn)狀態(tài)機復(fù)制，并依靠拜占庭故障檢測器來實現(xiàn)活性。

重新配置原子存儲。動態(tài)原子讀/寫 (R/W) 存儲可以是基于共識的 [19, 36, 44] 和無共識的。 Aguilera 等人在 DynaStore [2] 中證明，可以在異步設(shè)置中解決動態(tài)原子存儲，而無需使用共識（或隨機化）。

從 DynaStore 開始，已經(jīng)提出了許多無共識的動態(tài)原子存儲結(jié)構(gòu)（例如，[3,18,23]）。 Kuznetsov 和 Tonkikh 提出了具有拜占庭故障的異步原子存儲 [28]。

SMR 的重新配置。 Lamport 在 Paxos 中建議將成員資格更改作為系統(tǒng)狀態(tài)的一部分來管理 [30]。在成員請求達成協(xié)議后，副本等待 α 批請求執(zhí)行，然后再安裝新配置。 Lorch 等人提出了 SMART [34]，其中系統(tǒng)的重新配置是通過創(chuàng)建一組額外的副本來管理的。兩組副本運行并行 Paxos 實例，直到系統(tǒng)狀態(tài)完全遷移到新組。對于主/備份復(fù)制，在崩潰故障設(shè)置中研究了重新配置的解決方案 [22, 49]。 Raft [38] 提出了一種用于重新配置的兩階段方法。第一階段是一個過渡配置，稱為聯(lián)合共識。為了過渡到新的配置，兩種配置中的副本都參與了聯(lián)合共識，而共識是獨立維護的。這種方法允許舊配置中的副本繼續(xù)為客戶端提供服務(wù)，并允許新配置中的副本趕上歷史。只有在共同共識被提交后，系統(tǒng)才會轉(zhuǎn)移到新的配置。 BFT-SMaRt 是一個支持重新配置的 BFT 系統(tǒng) [50]，其中成員資格請求被視為一種特殊類型的客戶端請求并將所有請求排序在一起。我們的系統(tǒng)也使用這種策略。但是在不進一步修改協(xié)議的情況下單獨這樣做，可能會產(chǎn)生活性問題（零吞吐量），正如我們將在第 2 節(jié)中理論上展示的任何基于領(lǐng)導(dǎo)者的 BFT 協(xié)議一樣。 并在第八節(jié)中對 BFT-SMaRt 進行了實驗展示。

使用輔助主機重新配置。系統(tǒng)的重新配置（存儲、SMR 或主備份復(fù)制）可以由輔助主服務(wù)器管理 [31、35、43]。例如，Vertical Paxos 顯示（在崩潰故障設(shè)置中）使用 f + 1 個副本來構(gòu)建管理 SMR 配置的配置主機就足夠了。會員管理。動態(tài) BFT 與成員管理形成鮮明對比，成員管理是一種管理分布式系統(tǒng)中節(jié)點的服務(wù) [12、13、24、32、41、42、45、52]。該服務(wù)可以從獨立的 SMR（例如，Apache Zookeeper [21]、Google Chubby [9]）或通過成員的自我發(fā)現(xiàn)（例如，SWIM [13]）構(gòu)建。相比之下，動態(tài) BFT 是一個根本不同的原語，可以被視為可自配置的 SMR。耐用性。持久性是在狀態(tài)機復(fù)制系統(tǒng)崩潰或關(guān)閉時幸存下來并使正在恢復(fù)的副本保持最新的能力。該屬性之前已在靜態(tài)組的上下文中考慮 [6, 10]，而我們從不同的角度考慮動態(tài)組的類似屬性。

3 系統(tǒng)和威脅模型

A. 靜態(tài) BFT

傳統(tǒng)的拜占庭容錯 (BFT) 協(xié)議具有一組恒定的副本，其中一部分可能會任意失?。ò菡纪ス收希Ｔ?BFT 中，副本傳遞請求，每個請求都由客戶端提交。一個請求可以包括一個或多個操作。副本執(zhí)行請求中的操作并向相應(yīng)的客戶端發(fā)送回復(fù)。客戶端根據(jù)回復(fù)消息計算最終響應(yīng)。

在具有 n 個副本的系統(tǒng)中，BFT 可以容忍 f ≤ b n?1 3 c 拜占庭式故障，這是最優(yōu)的。 BFT 的正確性規(guī)定如下：

? 協(xié)議：如果一個正確的副本交付請求 m，那么每個正確的副本最終都會交付 m。

? 總順序：如果一個正確的副本在傳遞m0 之前傳遞了一條消息m，那么另一個正確的副本只有在它傳遞了m 之后才傳遞一條消息m0。

? 活躍度：如果正確的客戶端提交請求m，那么正確的副本最終會交付m。

? 完整性：沒有正確的副本多次傳遞相同的消息m；如果一個正確的副本傳遞了一條消息 m 并且提交 m 的客戶端是正確的，那么 m 之前是由客戶端提交的。

總秩序和完整性是安全屬性，而其他兩個是活力屬性。協(xié)議和活躍度一起意味著客戶端最終會收到有效的響應(yīng)。BFT 形式化可以顯式地將序列號分配給客戶端請求，并要求正確的副本根據(jù)順序執(zhí)行請求。

一般來說，部分同步的 BFT 協(xié)議依賴于視圖更改（以領(lǐng)導(dǎo)者輪換的形式）來獲得活躍性，因此在視圖中進行。當(dāng)領(lǐng)導(dǎo)者出現(xiàn)故障時（例如，PBFT [10]）或根據(jù)某些策略（例如，Spinning [53]，HotStuff [55]）定期觸發(fā)視圖更改。然而，異步 BFT 協(xié)議沒有視圖更改機制。

B. 動態(tài) BFT

我們考慮一個 BFT 系統(tǒng)，其副本取自有限集 Π = {p1, p2, ····}（也稱為全域）。每個副本 pi ∈ Π 都有一個公鑰/私鑰對（pki，ski），為了簡單起見，我們假設(shè)它的公鑰被集合中的所有進程都知道，并用作 pi 的唯一標(biāo)識符。動態(tài) BFT 組由 Π 的一個子集組成。 BFT 組中的副本是該組的成員。我們使用配置的概念來表示 BFT 組的連續(xù)成員資格。令 Mc 是配置的成員資格（副本組），編號為整數(shù) c，初始化為 0（初始配置）。副本通過配置安裝更改其配置。我們引入以下定義： 定義 III.1。如果 p ∈ Mc，則副本 p 在配置 c 中。

定義 III.2。如果 p 已經(jīng)安裝了配置 c 但在 c 之后沒有安裝另一個配置，那么 p 的（當(dāng)前）配置是 c。

定義 III.3。系統(tǒng)的最新配置是 c，如果至少有一個正確的副本安裝了 c，并且沒有正確的副本安裝 c0，其中 c0 > c。

定義 III.4。一個副本 p 在配置 c 中是正確的，如果 p 安裝了配置 c，并且 p 在 c 中是正確的（沒有錯誤）。（注 p 在配置 c + 1 中可能有錯，也可能沒有錯，但在 c 中沒有錯。）

定義 III.5。一個副本 p 是 c 正確的，如果 1) p 在配置 c 中是正確的，并且 2) 在 c 中沒有正確的副本安裝任何大于 c 的配置，或者 c 中的某些正確的副本在 c 和 p ∈ Mc 之后安裝配置 c + 1 +1。 （如果 c 是 c 中所有正確副本的最新配置，則 p 是 c 正確的，或者 p 在 c 的下一個配置中。）

定義 III.6。如果 p ∈ Mc 并且 p 不是 c 正確的，則副本 p 是 c 錯誤的。 （副本 p 在配置 c 中可能是正確的，但 c 錯誤，例如，p 可能會在配置 c 之后但在配置 c + 1 之前從組中刪除，并且永遠不會在配置 c + 1 中。）

定義 III.7。副本 p 是 g 正確的，如果 1) p 是 0 正確的（其中 0 是系統(tǒng)的初始配置），并且 2) 不存在 c > 0 使得 p 不是 c 正確的。 （一個 g 正確的副本在其所有配置中都是正確的。）

定義 III.8。對于 c ≥ 0，副本 p 是 gc 正確的，如果 1) p 是 c 正確的，并且 2) 不存在 c0 使得 c0 > c 并且 p 不是 c0 正確的。 （gc 正確的副本在配置 c0 ≥ c 中是正確的。g0 正確的副本是 g 正確的。）

我們的配置概念（處理成員資格）獨立于視圖（在部分同步 BFT 的視圖變化的意義上） .動態(tài)部分同步 BFT 可以同時具有配置的概念和視圖的概念。請注意，靜態(tài) BFT 組是動態(tài) BFT 模型的特例，具有固定數(shù)量的副本和單一配置。

C. 動態(tài) BFT 的組成員資格更改

我們考慮兩個可以修改成員資格的成員資格請求：將新副本添加到組的加入請求和從組中刪除副本的離開請求。成員資格請求不同于不會更改成員資格的常規(guī) BFT 請求（寫入和讀取請求）。我們不失一般性假設(shè)會員請求是修改會員的唯一方法。我們對誰可以發(fā)出會員請求沒有任何限制。它們可以被任何授權(quán)的客戶端（例如，加入或離開系統(tǒng)的副本、系統(tǒng)管理員、受信任的 CA、高級程序）調(diào)用。我們也不會討論為什么要包含或排除副本，而只會介紹我們是如何做到的。在實踐中，如第二節(jié)中的示例所示。我，在就誰將加入或離開小組以及為什么以及何時需要更改小組成員資格達成一致時通常沒有歧義。

在配置 c 中的副本 pj 執(zhí)行對 pi 的加入請求后，pj 的成員資格變?yōu)?Mc ∪ {pi}（并且相應(yīng)地 pj 安裝新配置）。在配置 c 中的副本 pj 執(zhí)行對 pi 的離開請求時，其成員資格變?yōu)?Mc - {pi}。

對于 i < j 的兩個配置成員 Mi 和 Mj，我們使用 Mj/Mi 表示存在于 Mj 中但不存在于 Mi 中的副本。例如，如果 Mi = {p2, p3, p4} 且 Mj = {p3, p4, p5, p6}，則 Mj/Mi = {p5, p6}。設(shè) nc 和 tc 分別是配置 c 中的副本數(shù)和 c-faulty 副本數(shù)。在配置 c 中，我們有 nc = |Mc|。

D. 假設(shè)

我們現(xiàn)在指定系統(tǒng)假設(shè)。

標(biāo)準(zhǔn)法定人數(shù)假設(shè)。我們假設(shè)這項工作中的最佳彈性模型。即，系統(tǒng)在配置 c 中可以容忍的最大故障數(shù)為 fc ≤ b nc-1 3 c。一個法定人數(shù)的副本至少由 d nc+fc+1 2 e 個副本組成。我們使用 Qc 來表示配置 c 中的仲裁大小。這是一個標(biāo)準(zhǔn)的和最優(yōu)的假設(shè)。除非另有說明，我們考慮默認(rèn)假設(shè)。

G-正確假設(shè)。我們還考慮了一個更強的假設(shè)，這不是必需的，但在某些情況下可能會產(chǎn)生一些（很多）更簡單的協(xié)議。對于所有 c ≥ 0，讓 F = max({fc}) + 1。G 正確假設(shè)要求至少存在 F 個在所有配置中都是正確的副本。換句話說，“足夠”正確的副本永遠不會離開系統(tǒng)。

此外，我們對動態(tài)成員資格做了兩個標(biāo)準(zhǔn)假設(shè)（用于所有其他此類場景）：首先，加入或離開系統(tǒng)的副本數(shù)量是有界的（一個自然的假設(shè)是從配置 c 到 c + 1，至少Q(mào)c c-正確的副本仍在 c+ 1) 中；其次，初始配置是宇宙 Π 中的所有副本都知道的。

E. 屬性規(guī)范

在我們的形式化中，成員資格請求和常規(guī) BFT 請求可以統(tǒng)稱為請求。我們以與常規(guī)請求相同的方式處理會員請求。因此，在下面指定動態(tài) BFT 的正確性時，請求 m 可以是會員請求或常規(guī)請求。特別是，加入或離開請求的調(diào)用只是對特殊客戶端請求的調(diào)用。加入（或離開）請求的執(zhí)行對應(yīng)于請求的交付和通過請求中的添加（或刪除）操作安裝新配置。

? 協(xié)議：如果配置c 中的正確副本交付請求m，則配置c 中的每個正確副本最終都會交付m。

? 相同的配置交付：如果一個正確的副本 pi (resp.pj) 在配置 ci (resp. cj) 中傳遞 m，然后 ci = cj。

? 總順序：如果配置c 中的一個正確副本在傳遞m0 之前傳遞了一條消息m，那么配置c 中的另一個正確副本只有在它傳遞了m 之后才傳遞一條消息m0。

? 活躍性：如果一個正確的客戶端提交請求m，那么最終某個配置c 中的正確副本會交付m。

? 完整性：沒有正確的副本多次傳遞相同的消息m；如果一個正確的副本在某個配置中傳遞了一條消息 m 并且提交 m 的客戶端是正確的，那么 m 之前是由客戶端提交的。

相同的配置交付屬性是會員服務(wù)的自然要求，并且是先前定義的（例如，[11, 46]）。 BFT 系統(tǒng)可以將遞增的序列號分配給不同的客戶端請求以訂購交易。在這樣的語法下，我們可以統(tǒng)一相同的配置交付屬性和總訂單屬性：

? 增強的總訂單：如果配置 c 中的一個正確副本交付具有序列號的請求 m，而配置 c0 中的另一個正確副本交付請求 m0具有相同的序列號，則 m = m0 和 c = c0。

一個實用、持久的 BFT 系統(tǒng)依賴于狀態(tài)傳輸協(xié)議來更新正在恢復(fù)的副本或落后于其對等方的副本 [6, 10]。在動態(tài) BFT 中，加入組的新副本也需要狀態(tài)轉(zhuǎn)移機制來趕上其他副本。新的副本或正在恢復(fù)的副本在獲得系統(tǒng)狀態(tài)之前可能被認(rèn)為是有故障的。

一些（但不是全部）現(xiàn)有的 BFT 協(xié)議是在沒有明確協(xié)議屬性的情況下指定的，但這些協(xié)議可以輕松滿足它。然而，動態(tài) BFT 并非如此，因為達成一致并非易事。因此，我們在所有動態(tài) BFT 結(jié)構(gòu)中都明確考慮了一致性。

需要額外的屬性。討論了動態(tài) BFT 屬性自然地反映了靜態(tài) BFT 的屬性，現(xiàn)在讓我們激發(fā)對附加屬性的需求。在靜態(tài) BFT 設(shè)置中，協(xié)議、總訂單和我們的活躍度定義意味著正確的客戶端將收到對其請求的回復(fù)。更具體地說，對于客戶端請求 m，協(xié)議和活躍度保證所有正確的副本最終都會交付 m。由于有 n ≥ 3f + 1 個副本，客戶端可以通過多數(shù)投票方法安全地傳遞響應(yīng)，在收到 f +1 個匹配的回復(fù)后計算響應(yīng)。事實上，靜態(tài) BFT 中活躍度的典型定義已經(jīng)要求客戶端最終會收到對其請求的回復(fù)，因此協(xié)議屬性不是“需要的”。

經(jīng)典定義不會立即適用于動態(tài)組。首先，由于不知道系統(tǒng)的成員身份或某些配置中的副本總數(shù)，客戶端可能永遠無法確定何時將回復(fù)傳遞給請求。其次，即使客戶端知道成員資格信息，在處理消息時成員資格也可能已經(jīng)改變。這兩個因素激發(fā)了定義附加屬性的需要。

嘗試1?？梢砸?guī)避成員資格問題的“自然”增強活性可以定義如下： ? 如果正確的客戶端提交請求 m，則客戶端最終會從副本傳遞響應(yīng)。

不幸的是，該定義沒有在動態(tài) BFT 設(shè)置中捕獲任何有意義的正確性保證。可以很容易地設(shè)計一個滿足上述定義的簡單協(xié)議，其中正確的客戶端接收到不相關(guān)的響應(yīng)。

嘗試2。另一種選擇是定義以下屬性： ? 成員身份發(fā)現(xiàn)：提交了 m 的正確客戶端最終可以了解為其交付 m 的配置的成員身份。

成員發(fā)現(xiàn)屬性要求客戶端最終知道傳遞其消息的配置的成員信息（副本的身份）。它沒有說明客戶端是否可以或需要學(xué)習(xí)最新的（當(dāng)前）成員，這在異步環(huán)境中具有挑戰(zhàn)性（即使我們假設(shè)活動的部分同步模型）。實際上，即使客戶獲得了最新的會員信息，會員也可能在客戶提交請求時或在處理請求時已更改。成員發(fā)現(xiàn)屬性似乎涵蓋了我們可以設(shè)想的許多場景，無論客戶端是通過獨立的子協(xié)議（在處理其請求之前或之后）獲取成員信息，還是在協(xié)議運行時獲取成員信息。

直觀地說，成員發(fā)現(xiàn)屬性，連同協(xié)議、活躍度和總順序，將意味著客戶端知道何時從相同的配置中收到足夠的匹配回復(fù)，并且可以基于多數(shù)投票安全地傳遞響應(yīng)。更準(zhǔn)確地說，對于客戶端請求 m，協(xié)議和活躍度保證了某些配置中的所有正確副本最終將傳遞客戶端消息 m；總訂單保證 m 必須在相同的配置中交付，例如 c；知道傳遞 m 的配置 c 的精確成員資格和配置 c 中的成員總數(shù)，客戶端可以通過傳統(tǒng)的多數(shù)投票方法安全地傳遞響應(yīng)，在接收到配置 c 中的 fc + 1 個匹配回復(fù)后計算響應(yīng).

不幸的是，上述論點有一個重大缺陷。即使客戶端了解了請求 m 為其傳遞的配置 c 的信息，即使我們假設(shè)通道完美，配置 c 中正確副本發(fā)送的回復(fù)消息也可能無法到達客戶端。這是因為完美通道僅在發(fā)送者始終正確時才能保證消息傳遞，但發(fā)送者可能會在未來的某些配置中離開系統(tǒng)；事實上，由于網(wǎng)絡(luò)異步，來自某個副本 pi 的回復(fù)消息可能在 pi 離開系統(tǒng)之前無法到達客戶端。

我們評論說，雖然我們不采用成員發(fā)現(xiàn)的定義，但我們的構(gòu)建確實是由這個想法驅(qū)動的。

最后的嘗試。最后，我們定義以下屬性： ? 一致交付：提交 m 的正確客戶端將交付正確響應(yīng)，該響應(yīng)與交付 m 的某些配置中的狀態(tài)一致。

該物業(yè)有點不合常規(guī)，既包括活力又包括安全。然而，可以很容易地將屬性劃分為活性屬性（正確的客戶端最終會收到對其請求的回復(fù)）和安全屬性（正確客戶端傳遞的請求與傳遞請求的某些配置的狀態(tài)一致） ）。

為了正式定義一致的交付，我們使用狀態(tài)機復(fù)制符號 [29, 48]。確定性狀態(tài)機由以下值元組組成：一組狀態(tài)、一組請求、一組回復(fù)、一個將請求和狀態(tài)作為輸入并輸出更新狀態(tài)的轉(zhuǎn)換函數(shù)，以及一個輸出函數(shù)將請求和狀態(tài)作為輸入并輸出回復(fù)。請求由客戶提交，回復(fù)被發(fā)送給客戶。狀態(tài)對系統(tǒng)狀態(tài)進行編碼（包括配置和保留的各種變量）。

如果回復(fù) re 是由某個請求的輸出函數(shù)和狀態(tài) st 生成的，則我們說回復(fù) re 與正確狀態(tài)機的狀態(tài) st 一致。當(dāng)我們考慮確定性狀態(tài)機時，并且由于所有正確的副本都實現(xiàn)了總順序，相同的請求和相同的狀態(tài)決定了正確副本的相同回復(fù)。

表 I：協(xié)議定義和結(jié)構(gòu)概述。定義變體也可以應(yīng)用于其他動態(tài) BFT 屬性，但它們不會（似乎）導(dǎo)致有趣的效率權(quán)衡。

請注意，正確的副本可能會在某些配置中生成回復(fù)（和相應(yīng)的狀態(tài)），但由于在此配置中某些回復(fù)可能永遠不會到達客戶端，因此客戶端不會在此配置中傳遞回復(fù)。 （回想一下，在回復(fù)到達客戶端之前，正確的副本可能已經(jīng)離開系統(tǒng)。）但是，我們確實希望確?？蛻舳俗罱K會提供與系統(tǒng)維護的狀態(tài)一致的回復(fù)。

另請注意，在傳統(tǒng)的靜態(tài)機器復(fù)制設(shè)置中，始終以相同的配置傳遞回復(fù)，因為有足夠的正確副本。在這種情況下，不必定義這種額外的“一致交付”。

F 定義的變體

第 2 節(jié)中的定義有許多變體。 III-E。例如，為了達成一致，if 子句和 main 子句都討論“c 中的正確副本”。我們在表 I 中總結(jié)了這些變體，上面詳細描述的定義是 V2，這是我們可以想象的最強的一個。我們使用協(xié)議屬性1 來說明它們的差異，不同的協(xié)議屬性導(dǎo)致不同的結(jié)構(gòu)，并具有有趣的效率權(quán)衡。

人們可以類似地描述其他屬性的定義。這些屬性的定義變體不會（似乎）導(dǎo)致更有效的構(gòu)造。所以本文只提供具有不同協(xié)議定義的結(jié)構(gòu)。

我們用圖1來解釋協(xié)議的定義。在這個例子中，有三個配置和七個副本。

復(fù)制體p1到p5是正確的，g1是正確的。復(fù)制體p6是1正確的，但2有問題，因為它在配置2之后離開了系統(tǒng)。復(fù)制件p7在1中是正確的，但在配置1后離開系統(tǒng)時是1個錯誤的。對于協(xié)議定義V，如果配置1中的正確副本p1傳遞了一個消息m2，任何其他g1正確的副本，包括p2到p5，最終都會傳遞m2。然而，復(fù)制體p6和p7可能會也可能不會傳遞m2。

對于協(xié)議定義V1，如果一個1正確的復(fù)制體p1交付了m1，任何其他1正確的復(fù)制體，包括p2到p6，都必須交付m1。對于V2，一個例子是m3。特別是，如果配置1中的正確副本p1交付了m3，配置1中的任何其他正確副本，包括p2到p7，將交付m3。V 0、V 01和V 02的屬性相似，只是if子句需要c個正確的副本。

應(yīng)該選擇六個版本中的哪一個？每個版本中的 if 子句表示屬性的條件：如果使用較弱的條件，我們將擁有更強的屬性。

請注意，V (resp. V 0) 比 V1 (resp. V 01) 和 V2 (resp. V 02) 弱，因為 gc 正確的副本也是 c 正確的副本和正??確的副本。此外，V1 (resp. V 01) 比 V2 (resp. V 02) 弱，因為某些配置 c 中的正確副本集包括 c 正確副本集?？梢詫⑽覀兊脑O(shè)置與針對崩潰故障的統(tǒng)一與非統(tǒng)一廣播原語的設(shè)置進行比較，其中統(tǒng)一廣播原語更強。

G. 與先前規(guī)范的比較

我們的語法遵循 Schiper 的語法，將動態(tài) BFT 從其成員服務(wù)中分離出來 [46]。正如 Schiper 所說，這種治療比 Chockler 等人 [46] 的治療更自然、更簡單。然而，我們對安全性（正確性）屬性的規(guī)范與 Schipper [46] 的規(guī)范有很大不同。

首先，我們的規(guī)范處理拜占庭式故障，而 Schiper 的規(guī)范是為崩潰故障模型中的統(tǒng)一廣播原語而設(shè)計的。

其次，雖然我們一起定義了常規(guī)請求和成員請求的屬性，但 Schipper 分別定義了常規(guī)請求和成員請求的所有屬性。特別是，Schipper 的工作首先描述了常規(guī)請求的總順序，然后描述了成員請求的總順序，兩者都是傳統(tǒng)意義上的請求總順序。僅 Schiper 的總訂單規(guī)范可能會導(dǎo)致以下“異?！?，如圖 2 所示：正確的副本 p1 可能在常規(guī)請求之前交付成員請求，而正確的副本 p2 在成員請求之前交付常規(guī)請求。這并不違反 Schiper 工作中定義的兩個單獨的總訂單屬性，但確實違反了我們定義的總訂單保證。

圖 2：不違反 Schiper 方案中的全序?qū)傩缘`反我們的定義的示例。

也就是說，在 Schipper 的工作中定義的兩個總順序?qū)傩?，即使結(jié)合起來，也比我們的要弱。然而，由于在Schiper的工作中為普通請求和會員請求額外定義了 "相同的配置交付 "屬性，人們可以檢查出 "異常 "不會發(fā)生。事實上，在 Schipper 的工作中定義的兩個總訂單屬性和兩個相同的配置交付屬性，加在一起就等價于我們增強的總訂單屬性（它包含相同的配置交付屬性）。因此，雖然我們的屬性與 Schiper 的屬性之間沒有一一對應(yīng)的關(guān)系，但我們的規(guī)范和 Schiper 的規(guī)范（對拜占庭故障進行了適當(dāng)?shù)男薷模┛梢宰鳛橐粋€整體等效。然而，我們的定義看起來更簡潔。

最后，Schipper 的工作沒有定義對動態(tài) BFT 的安全性至關(guān)重要的所需屬性（一致交付）。

4 動態(tài) BFT 的挑戰(zhàn)

在構(gòu)建動態(tài) BFT 時，可以簡單地將成員資格請求視為常規(guī)請求。然而，直觀的方法會導(dǎo)致各種問題，使得動態(tài) BFT 無法實現(xiàn)活性。我們在下面說明了基于領(lǐng)導(dǎo)者的 BFT 協(xié)議在部分同步環(huán)境中的視圖變化的一些挑戰(zhàn)。

正常情況下操作中的活性問題。協(xié)議屬性，無論是部分同步還是異步假設(shè)，都要求如果正確的發(fā)送者在線保持足夠長的時間，正確的接收者將接收到來自發(fā)送者的消息。然而，動態(tài) BFT 并非如此。特別是，考慮一個 cq 正確的副本 pi，它在 cr > cq 之后立即離開系統(tǒng)。副本 pi 已在 cq 中交付 m 并在 cr 中刪除（pi）。考慮另一個仍然在 cq 中的正確或 cq 正確的副本 pj。副本需要收集 Qcq 匹配消息來傳遞 m。然而，一些 cq 正確的副本（甚至除 pj 之外的所有 cq 正確的副本）可能不再正確，因為它們已經(jīng)移動到 cr，例如，pi 已經(jīng)離開系統(tǒng)。因此，正確的副本可能無法交付 m，從而產(chǎn)生一致性和活性問題。

視圖更改的活性問題。我們總結(jié)了與視圖更改相關(guān)的各種活性問題。

1. 新視圖中正確的領(lǐng)導(dǎo)者可能無法獲得足夠的視圖更改消息來啟動新視圖。

2. 新配置中的指定領(lǐng)導(dǎo)者可能不知道視圖變化。這是因為副本處于不同的配置中，并且它們無法在最新配置中發(fā)送所有副本視圖更改消息。

3）多個副本可能會在視圖更改后聲稱他們是新的領(lǐng)導(dǎo)者。

圖 3：視圖變化的活躍度挑戰(zhàn)。

我們在圖 3 中展示了一個示例。副本從配置 c = 1 移動到 c = 3，其中在所有三個配置中，p5 都是領(lǐng)導(dǎo)者。在配置 c = 1 中，有五個副本，并且刪除了 p3。副本 p2、p4、p5 安裝配置 2，而 p1 仍停留在 c = 1 中。在配置 2 中，仲裁大小為 3，因此 p2、p4 和 p5 能夠達成協(xié)議。在 c = 2 時，p6 請求加入系統(tǒng)。請求傳遞后，副本 p4、p5 和 p6 安裝 c = 3，而 p2 仍停留在 c = 2。如果在此階段發(fā)生視圖更改，則副本 p6 是新視圖中的指定領(lǐng)導(dǎo)者。由于 c = 3 中的 quorum 大小為 4，p6 必須收集 4 條消息才能啟動新視圖。然而，p1 和 p2 甚至不知道 p6。此外，副本 p1 可能認(rèn)為它是新的領(lǐng)導(dǎo)者。因此，所有正確的副本將永遠停止，因為副本在視圖更改期間不會處理任何消息，并且副本可能永遠不會恢復(fù)到正常情況下的操作。在靜態(tài)系統(tǒng)中，可以通過使副本與其他副本同步來解決此問題。然而，在動態(tài)系統(tǒng)中，副本甚至可能不知道系統(tǒng)中當(dāng)前副本的身份。

5 我們的協(xié)議概述

基于部分同步環(huán)境中的兩個假設(shè)，我們提供了滿足表 I 中各種動態(tài) BFT 定義的安全結(jié)構(gòu)。

A. Dyno-S：一種直觀但低效的構(gòu)造

Dyno-S 形式化的直覺是，每次處理成員資格請求時，都需要觸發(fā)視圖更改以防止副本丟失更新的配置。然而，使用這個想法構(gòu)建這樣一個具有可證明安全性的協(xié)議并非易事。該方法需要解決 Sec 中的挑戰(zhàn)。 IV 并且需要實現(xiàn)一致的交付。

由于篇幅限制，我們將在全文中介紹該結(jié)構(gòu)。該構(gòu)造的主要缺點是每次視圖更改都會導(dǎo)致吞吐量為零的窗口，因為副本在視圖更改期間不處理任何請求。

B. Dyno、Dyno-C 和 Dyno-AC

Dyno 是我們的主要協(xié)議，可在成員變更期間保持其效率。在標(biāo)準(zhǔn)仲裁假設(shè)下，它在定義 V 的意義上是安全的，在更強的 G 正確假設(shè)下在 V1 的意義上也是安全的。

向前躍進，我們還提供了具有更強特性的動態(tài) BFT 結(jié)構(gòu)（總結(jié)在表 I 中）。 Dyno-A 建立在 Dyno 之上，另外還有一個簡潔的附錄 (A) 協(xié)議正在運行。 Dyno-C 與 Dyno 略有不同，使用了輕微的約束 ?。 Dyno-AC，顧名思義，包含了附錄協(xié)議 (A) 和修改后的約束 ?。我們將在 Sec. 中描述附錄協(xié)議和約束的含義。七。

下面，我們從高層次上描述 Dyno。在描述我們的成員方法時，我們定義了兩個事件：init() 和 Deliver()。 init() 事件在當(dāng)前視圖中的主節(jié)點開始新一輪協(xié)議時觸發(fā)。 Deliver() 事件表示在正常情況下操作期間請求已提交并準(zhǔn)備好交付的事件。我們的成員協(xié)議具有以下關(guān)鍵組件，以確保正確性而不會中斷性能。

我們將配置作為系統(tǒng)狀態(tài)的一部分進行管理，類似于之前的工作（例如，Paxos、Schiper 的工作和 BFT-SMaRt）。

成員資格請求的處理方式與常規(guī)請求相同。副本在每一輪中就一批請求達成一致。如果批次包含常規(guī)請求和成員請求，則常規(guī)請求首先根據(jù)確定的順序交付（與具有靜態(tài)成員的 BFT 中的相同）。之后，會員請求被傳遞。然后所有副本都安裝新配置。

臨時會員管理。提交加入成員資格請求時，配置可能與提交請求時的配置不同。為了簡化通知流程，我們引入了臨時會員的概念。具體來說，每個新副本都充當(dāng)學(xué)習(xí)者。

現(xiàn)有副本將正常情況下的操作消息發(fā)送到當(dāng)前配置中的副本和所有臨時成員。但是，仲裁大小仍與當(dāng)前配置相同。在 Deliver() 事件中，成員資格被更新并與臨時成員資格相同。這樣做可以讓我們擁有更有效的狀態(tài)轉(zhuǎn)移機制。

配置發(fā)現(xiàn)協(xié)議和一致交付。

我們設(shè)計配置發(fā)現(xiàn)協(xié)議，以便新副本和客戶端了解當(dāng)前系統(tǒng)的成員資格。我們提供隱式和顯式實現(xiàn)目標(biāo)的協(xié)議。這些協(xié)議對于實現(xiàn)一致的交付也很重要，因為客戶端需要配置發(fā)現(xiàn)來驗證系統(tǒng)中當(dāng)前副本的回復(fù)。

我們還需要另外兩種技術(shù)來實現(xiàn)一致的交付。首先，我們在配置之間強制達成一致，以確保所有正確的副本，而不僅僅是一小部分正確的副本，都是最新的。其次，副本維護執(zhí)行歷史和配置歷史（執(zhí)行歷史的子集）的總順序。執(zhí)行歷史記錄包含每個請求的交付證明（以簽名的形式，證明法定人數(shù)的副本已同意交付請求），以確保總訂單和協(xié)議。配置歷史記錄僅包括會員請求的交付證明。

配置歷史記錄用于驗證正確的副本是否安裝了某些配置。配置歷史允許客戶端確定它是否已收到足夠的匹配副本回復(fù)以在某些配置中安全地傳遞它們。

請注意，客戶端可能無法在發(fā)出請求的配置中傳遞回復(fù)，但客戶端將在未來的某些配置中傳遞它們。

精心設(shè)計的視圖變化。為了確保新視圖中的指定領(lǐng)導(dǎo)者接收到一定數(shù)量的視圖更改消息，我們在視圖更改期間引入了額外的工作流。具體來說，每個副本都在視圖更改消息中包含其配置編號以及成員請求的有效傳遞證明。

對于配置 c 中的任何副本 pi，它將 c 與 c0 進行比較，其中 c0 是 pj 發(fā)送的視圖更改消息中攜帶的配置號。如果 c0 更小，pi 將視圖更改消息轉(zhuǎn)發(fā)給 Mc/Mc0 中的所有副本。請注意，Mc/Mc0 就足夠了，因為副本 pj（如果正確）必須已經(jīng)將消息發(fā)送到 Mc0。另一方面，如果 c 較小，則有兩種情況： pi 之前發(fā)送過視圖更改消息； pi 之前沒有發(fā)送過視圖更改消息。在前一種情況下，pi 將其視圖更改消息重新發(fā)送到 Mc0/Mc。在后一種情況下，pi 將其視圖更改消息（如果適用）直接發(fā)送到 Mc0 中的所有副本。這確保了新視圖中的副本能夠收集足夠多的視圖更改消息以進入新視圖。

6 DYNO 協(xié)議

我們現(xiàn)在介紹 Dyno，重點介紹如何處理會員請求和常規(guī)請求以及視圖更改的工作流程。在整篇論文中，我們假設(shè)每條消息 m 都是唯一的。在本節(jié)中，我們將正常情況下的操作用作預(yù)言機，由 init() 和 Deliver() 事件表示，如第 2 節(jié)所述。 V. 特別是，我們使用 Bracha 的可靠廣播 [8] 作為正常情況的操作，我們在附錄 A 中討論了如何觸發(fā) init() 和 Deliver() 事件的細節(jié)。我們使用 Bracha 的廣播，因為它是一個原語達成一致，我們認(rèn)為這對于動態(tài) BFT 至關(guān)重要。對于每個請求，我們使用交付證明來表示請求可以安全交付的證明。在我們的例子中，這指的是 Bracha 廣播的第二階段中的 2f + 1 個匹配消息（或 PBFT 術(shù)語中的準(zhǔn)備證書）或第三階段中的 f + 1 個匹配消息（或 PBFT 術(shù)語中的 f + 1 個 hCOMMITi 消息） .

當(dāng)我們描述協(xié)議時，我們考慮了一個通過獲取配置 ig() 函數(shù)觸發(fā)的配置發(fā)現(xiàn)協(xié)議。副本和客戶端可以通過查詢函數(shù)獲取當(dāng)前配置。配置發(fā)現(xiàn)的細節(jié)在 Sec. 中討論。 VI-B。在本節(jié)中，我們忽略垃圾收集的細節(jié)，因為我們的系統(tǒng)可以使用傳統(tǒng)的檢查點協(xié)議。

A. 協(xié)議

客戶定期提交請求?？蛻舳四軌蛲ㄟ^ObtainConf ig() 函數(shù)獲得配置c 和副本集Mc。為了提交請求，客戶端首先向配置 c 中的所有副本廣播一條消息 hSUBMIT, c, hREQUEST, cid, oii。請求 hREQUEST, cid, oi 是具有有效簽名的常規(guī)請求，其中 cid 是客戶端的 id，o 是操作?？蛻艨赡艿玫降拇饛?fù)有兩種情況。 1) 如果客戶端收到來自 Mc 中 fc + 1 個副本的回復(fù)，則完成請求。 2) 客戶端可能會從 c0 中的副本獲得回復(fù)，其中 c0 > c。在這種情況下，客戶端會驗證配置歷史 chist（稍后會詳細介紹）并檢查 c0 是否為有效配置。如果 c0 有效，則請求完成。如果沒有任何一種情況，客戶端超時，客戶端再次執(zhí)行配置發(fā)現(xiàn)并提交請求，直到請求完成。

初始化 c {當(dāng)前配置}
func submit() ? join {new replica}
c, Mc ← ObtainConf ig()
broadcast hSUBMIT, c, hJOIN, pkii to Mc
start timer ? 在接收到 hCONF, c0, Mc0 , chist0i {配置通知} 如果 chist0 有效且 c0 > c c ← c0, Mc ← Mc0 收到 2fc + 1 hHISTORY, s, h, C, Pi for m in h, deliver(m) upon deliver(batch) where hADD, i, mi ∈ batch wait until state transfer is completed stop ?, complete the要求 ？離開 {existing replica} broadcast hSUBMIT, c, hLEAVE, iii to Mcstart timer ? 在 deliver(batch) where hREMOVE, i, mi ∈ batch stop ?, complete the request ?提交一個常規(guī)請求 {client} c, Mc ← ObtainConf ig() broadcast hSUBMIT, c, hREQUEST, cid, oii to Mcstart timer ? 在 fc + 1 匹配 hREPLY, c, rei from Mcstop ?, fc0 + 完成請求1 匹配 hREPLY, c0, re, chist0i from pj ∈ Mc0 stop ?, 超時完成請求(?) repeat submit()
圖 4：發(fā)出請求的客戶端/副本 pi 的偽代碼。

正常情況下的操作和成員請求。復(fù)制體pi的正常情況下的操作的偽代碼顯示在圖5中。當(dāng)c中的副本收到hSUBMITi消息中帶有c0的客戶的請求時，有兩種情況。 1) 如果該請求已經(jīng)被傳遞，pi直接回復(fù)hREPLY, c0, re, chisti，其中re是執(zhí)行結(jié)果，chist是配置歷史。2) 否則，該請求被添加到待處理隊列中。同時，如果c = c0，副本將請求轉(zhuǎn)發(fā)給當(dāng)前配置中的領(lǐng)導(dǎo)者。 如果c>c0，客戶端仍處于先前的配置中，pi將請求轉(zhuǎn)發(fā)給Mc/Mc0。

對于加入系統(tǒng)的副本，副本廣播 hSUBMIT, c, hJOIN, pkii 請求，其中 pk 是公鑰。為了從系統(tǒng)中刪除副本，副本或管理員廣播 hSUBMIT, c, hLEAVE, iii 消息。當(dāng)系統(tǒng)的當(dāng)前領(lǐng)導(dǎo)者有一個非空隊列時，領(lǐng)導(dǎo)者從待處理隊列中獲取一批請求。如果有 hJOIN, pki 請求，leader 向 batch 添加 hADD, j, mi 消息，其中 m 是有效的 hJOINi 請求，j 是分配給副本的標(biāo)識符。如果有 hLEAVE, ji 請求，leader 向批處理中添加 hREMOVE, j, mi 消息，其中 m 是有效的 hLEAVEi 請求。然后leader觸發(fā)init()事件。如果非主副本觸發(fā)批處理的 init(batch) 事件，對于批處理中的每個 hADD、j、mi，副本將 pj 添加到 T M 并繼續(xù)正常情況下的操作，它也將消息發(fā)送到 pj。然而，f 的值和群體大小仍然由組成員 M 決定。換句話說，fc = b |M|?1 3 c，群體大小為 d |M|+fc+1 2 e。對于任何一個請求加入系統(tǒng)的副本pj，如果副本pi維護了一個更高的配置號，它就會執(zhí)行sync()函數(shù)并將配置歷史發(fā)送給pj。用于pj直接獲取系統(tǒng)最新配置。

圖 5：副本 pi 的正常情況操作。

圖 6：查看副本 pi 上的更改協(xié)議。

在 deliver() 事件發(fā)生后，副本 pi 首先傳遞常規(guī)請求，然后傳遞成員資格請求。如果批次中包含成員請求，pi 安裝新配置并將 c 加 1。對于每個 hADD、j、mi 消息，pi 將 pj 添加到 M，并開始向 pj 傳輸狀態(tài)。對于每個 hREMOVE, j, mi 消息，pi 從 M 中刪除 pj。如果 pj 傳遞了 REMOVE 請求，它就會離開系統(tǒng)。

任何請求加入系統(tǒng)的副本 pi 都充當(dāng)學(xué)習(xí)者，被動地從正常情況操作中學(xué)習(xí)結(jié)果，即，它被系統(tǒng)中的副本添加到臨時成員中。學(xué)習(xí)者按照與現(xiàn)有副本相同的規(guī)則處理正常情況的消息。在 pi 發(fā)送加入請求后，它等待直到它通過接受 2fc + 1 hHISTORY, s, h, C, Pi 消息完成狀態(tài)轉(zhuǎn)移。

之后，pi 參與正常情況下的操作。新副本的狀態(tài)轉(zhuǎn)移以趕上執(zhí)行歷史并維護歷史請求的交付證明。

查看更改。我們現(xiàn)在勾勒出視圖更改的主要工作流程，其偽代碼如圖 6 所示。為了開始視圖更改，每個副本 pi 增加其視圖編號并廣播 hVIEW-CHANGE, v, c, s, C, PP, ii，其中 v 是視圖編號，c 是配置編號，C 是穩(wěn)定檢查點，P 是自上次穩(wěn)定檢查點以來請求的一組交付證明，PP 是一組成員請求。

從副本 pj 收到 VIEW-CHANGE 消息后，副本將消息中攜帶的 c0 與其本地配置編號 c 進行比較。如果 c0 < c，這意味著副本 pj 沒有安裝更新的配置，因此 Mc 中的一些副本無法接收消息。在這種情況下，pi 將 VIEW-CHANGE 消息轉(zhuǎn)發(fā)給 Mc。如果 c0 > c，表示 replica pi 沒有安裝更新的配置。在這種情況下，pi 向 Mc0 廣播一個 VIEW-CHANGE 消息。 Mc0 可以從 PP 獲得，交貨證明可以從 P 獲得。

考慮 c 是由至少一個正確的副本安裝的配置，并且沒有正確的副本安裝了大于 c 的配置，新的領(lǐng)導(dǎo)者可以通過 Mc[v mod |Mc|] 來識別。當(dāng)新視圖中指定的leader收集到2fc+1條有效的VIEW-CHANGE消息時，它通過廣播一個hNEW-VIEW，v，c，V，Oi進入新視圖，其中V是一組VIEW-CHANGE消息，O是一組 normalcase 操作消息。然后副本恢復(fù)正常情況下的操作并相應(yīng)地處理 O 中的消息。

B.配置發(fā)現(xiàn)配置發(fā)現(xiàn)確保新副本和客戶端了解現(xiàn)有系統(tǒng)的成員資格。我們在 Dyno 中提出的方法需要客戶端和新副本來發(fā)現(xiàn)更新的配置（如果有的話）。在本節(jié)中，我們首先定義配置歷史。然后，我們通過定義正常情況操作使用的接口，介紹我們在協(xié)議中使用的自我發(fā)現(xiàn)方法。我們在附錄 B 中描述了兩種替代結(jié)構(gòu)。所有配置發(fā)現(xiàn)協(xié)議的證明顯示在附錄 C-A 中。

配置歷史。我們將配置歷史定義為一組根據(jù)配置編號按順序排序的成員資格請求。配置歷史是整個執(zhí)行歷史的一個子集。配置歷史僅包括請求批次，其中每個批次至少包含一個成員資格請求。每條消息中對應(yīng)的c號是按順序排列的。我們還要求每個副本為每個成員資格請求維護相應(yīng)的交付證明，即由 Mc 中的 Qc 副本簽名的消息。單個配置歷史可以被任何正確的副本驗證以證明配置的存在。

圖 7：配置發(fā)現(xiàn)：自我發(fā)現(xiàn)。

自我發(fā)現(xiàn)。默認(rèn)情況下，我們使用圖 7 所示的自我發(fā)現(xiàn)方法。為了獲取系統(tǒng)的配置，副本（或客戶端）pi 首先向 universe 發(fā)送 hDISCOVER，ci 請求，其中 c 是最新的配置 pi知道。定時器也啟動。收到 hDISCOVER, c0i 請求后，副本回復(fù) hCONF, c, Mc, chisti，其中 c 是其當(dāng)前配置，Mc 是配置 c 的成員，chist 是配置歷史記錄。在收到帶有有效 chist 的 CONF 消息后，pi 更新其本地配置編號、Mc 和 chist。在 Δ 超時后，配置發(fā)現(xiàn)完成并返回當(dāng)前的 c 和 Mc。

定理 VI.1。在標(biāo)準(zhǔn)的法定人數(shù)假設(shè)下，Dyno 實現(xiàn)了協(xié)議 V、總訂單、活躍度和一致交付。

Dyno 的正確性見附錄 C-B。

七。 DYNO WITH STRONGER AGREEMENT PROPERTIES 我們研究了具有更強屬性的 Dyno 變體，即 V1、V2、V 0、V 01 和 V 02。在本節(jié)中，我們介紹了 Dyno 實現(xiàn) V1 協(xié)議屬性的兩種方法。我們首先通過更強的假設(shè)證明 Dyno 本身可以實現(xiàn) V1。

然后，我們展示了 Dyno-A，一種基于 Dyno 的結(jié)構(gòu)，它在標(biāo)準(zhǔn)群體假設(shè)下實現(xiàn)了 V1。然后我們介紹 Dyno-AC，它在 Dyno-A 之上添加了一個簡單的約束以實現(xiàn) V2。我們進一步表明，協(xié)議的結(jié)構(gòu)對于 Dyno 保持不變，其中 V、V1 和 V2 分別實現(xiàn) V 0、V 01 和 V 02。本節(jié)討論的所有協(xié)議的證明見附錄 C-C。

在 G 正確假設(shè)下，帶 V1 的 Dyno。我們不改變協(xié)議的結(jié)構(gòu)來實現(xiàn)正確性，而是假設(shè)第 2 節(jié)中的 G-correct 假設(shè)。三、由于我們不修改協(xié)議，因此總體順序和活躍度遵循 Dyno。但是，協(xié)議屬性可以大大簡化。

定理 VII.1。在 G-correct 假設(shè)下，Dyno 實現(xiàn)了協(xié)議 V1、全序、活性和一致交付。

帶V1的Dyno-A。假設(shè)總是存在至少f+1個g-正確的副本是不實際的，因為它要求人們知道m(xù)ax(f0, f1 - - )，即在系統(tǒng)的整個生命周期中錯誤副本的最大數(shù)量。相反，我們展示了另一種結(jié)構(gòu)，在不改變系統(tǒng)假設(shè)的情況下實現(xiàn)了V1協(xié)議屬性。特別是，我們在Dyno之上提供了一個附錄協(xié)議來實現(xiàn)V1。

如圖 8 所示，我們?yōu)槊總€落后的副本引入了額外的過程，以趕上更新配置的副本。特別是，在正常情況下的操作期間，每個副本 pi 仍會為其隊列中的第一個請求設(shè)置一個計時器。如果在定時器超時之前請求沒有被投遞，不是直接觸發(fā)視圖變化，而是副本首先運行配置發(fā)現(xiàn)協(xié)議，獲得一個新的配置號c0，以及副本列表Mc0。

如果 c0 = c，則副本根據(jù) Dyno 中的過程開始視圖更改。否則，如果 c0 大于 c，則副本向配置 c0 中的所有副本廣播 hUPDATE, s, c, ii 消息，其中 s 是最后交付請求的序列號，c 是其當(dāng)前配置。當(dāng) c0 中的副本 pi 收到 hUPDATE, s, c0, ji 消息時，它首先驗證 pj 是否是配置 c0 中的有效副本。

如果 pi 的本地執(zhí)行歷史較長（即其最后提交請求的序列號大于 s），則 pi 將執(zhí)行歷史發(fā)送給 pj。在收到 fc0 + 1 匹配 hist 后，副本將發(fā)送 hist 中的請求。如果 hREMOVE, ii 請求已經(jīng)傳遞，pi 直接離開系統(tǒng)。

否則，pi 繼續(xù)參與協(xié)議。

定理 VII.2。在標(biāo)準(zhǔn)的群體假設(shè)下，Dyno-A 實現(xiàn)了協(xié)議 V1、全序、活性和一致交付。

附錄協(xié)議的動機是讓 c-correct 副本獲得執(zhí)行歷史記錄，即使副本落后。在副本超時的情況下，它會在開始視圖更改之前執(zhí)行配置發(fā)現(xiàn)協(xié)議。

如果副本落后，它會從其他副本獲取執(zhí)行歷史記錄。這確保任何 c-correct 副本在離開系統(tǒng)之前獲得執(zhí)行歷史并交付請求（如果適用）。

帶 V2 的 Dyno?；诰哂?G-correct 假設(shè)的 Dyno 或 Dyno-A，我們可以進一步向副本添加更多約束，以便協(xié)議實現(xiàn) V2，分別創(chuàng)建 Dyno-C 和 Dyno-AC。特別是，V2 進一步要求配置 c 中的任何正確副本也傳遞消息，如果 c 中的正確副本傳遞了消息。

附加約束非常簡單：任何正確的副本 pi 僅在發(fā)送 hREMOVE, ii 請求后才離開系統(tǒng)（如果已提交離開請求）。該約束確保 c 中任何正確的副本都傳遞所有消息，即使它在 c 之后立即被刪除。

因此，我們需要一個副本來發(fā)現(xiàn)更新的配置，并在它落后時獲取執(zhí)行歷史記錄。這樣可以確保每個正確的副本都按照 V2 的要求傳遞它應(yīng)該傳遞的所有請求。

定理 VII.3。在 G-correct 假設(shè)下，Dyno-C 實現(xiàn)了協(xié)議 V2、全序、活性和一致交付。在標(biāo)準(zhǔn)的群體假設(shè)下，Dyno-AC 實現(xiàn)了協(xié)議 V2、全序、活性和一致交付。

帶有 V0、V01、V02 的測功機。無需更改協(xié)議規(guī)范即可實現(xiàn) V 0、V 01 和 V 02。

即，Dyno 達到 V 0，Dyno-A（或 Gcorrect 假設(shè)下的 Dyno）達到 V 01，Dyno-C 和 Dyno-AC 達到 V 02。

8 實施與評估

概述。我們使用大約 10,000 LOC 在 Go 中實現(xiàn) Dyno 變體。我們對 Dyno 進行了優(yōu)化，其中加入系統(tǒng)的副本在傳遞成員資格請求后開始參與正常情況操作。狀態(tài)轉(zhuǎn)移是并行執(zhí)行的。然而，在傳遞成員資格請求之后的所有請求都是在狀態(tài)轉(zhuǎn)移完成之后執(zhí)行的。

我們的結(jié)果表明，Dyno-C 和 Dyno-AC 與 Dyno 實現(xiàn)了相似的性能，主要是因為附加約束和增編協(xié)議主要影響副本加入或離開系統(tǒng)的行為。因此，在本節(jié)中，我們將重點關(guān)注 Dyno 和 DynoS 的性能。我們將 Dyno 與 BFT-SMaRt [50] 進行了比較，BFT-SMaRt [50] 是一種用 Java 編寫的 PBFT 協(xié)議變體的開源實現(xiàn)。 BFT-SMaRt 支持重新配置，其中成員請求由單獨的視圖管理器發(fā)出。

我們使用最多 30 臺服務(wù)器在集群中部署協(xié)議。每臺服務(wù)器都有 16 核 2.3GHz CPU。我們使用 f 來表示網(wǎng)絡(luò)大小，我們在每個實驗中使用 3f + 1 個副本。與以前主要關(guān)注小交易基準(zhǔn)的協(xié)議不同，在我們的實驗中，我們將所有交易和回復(fù)消息設(shè)置為 100 字節(jié)，因為 BFT 應(yīng)用程序（例如區(qū)塊鏈）中的交易通常至少為 100 字節(jié)。除了副本的數(shù)量，我們還改變了垃圾收集的頻率（即檢查點），表示為 cp，以及同時向系統(tǒng)提交事務(wù)的客戶端數(shù)量。默認(rèn)情況下，副本在每交付 100 批請求時執(zhí)行檢查點協(xié)議。

潛伏。我們評估了 Dyno 和 Dyno-S 的會員請求延遲。我們設(shè)置 f = 1 并讓一個客戶端連續(xù)提交定期請求。我們讓副本在分別提交了 5000、10000 和 50000 個請求后提交成員請求（加入或離開）（在圖中表示為 b）。我們僅在圖 9d 中顯示了協(xié)議的延遲。

Dyno 平均有 50 毫秒到 100 毫秒的延遲。結(jié)果與常規(guī)請求的結(jié)果類似。相比之下，由于 Dyno-S 在每次成員更改時都運行視圖更改協(xié)議，因此延遲要高得多。 Dyno-S 的延遲分解如圖 9a 所示?？梢钥闯觯晥D更改是瓶頸，如果在視圖更改之前處理更多請求，則延遲會更高。

由于每個新副本在加入系統(tǒng)后都會執(zhí)行狀態(tài)傳輸，因此我們還評估了每個實驗的狀態(tài)傳輸延遲。我們在圖 9b 中顯示了 Dyno 的結(jié)果。我們將狀態(tài)傳輸（網(wǎng)絡(luò)通信）的延遲和轉(zhuǎn)換（副本處理歷史客戶端請求）的延遲分開。如圖所示，隨著 b 的增加，延遲明顯變高。這是預(yù)料之中的，因為在狀態(tài)轉(zhuǎn)移期間需要同步大量請求。相比之下，協(xié)議延遲幾乎可以忽略不計。

對于b=10000的實驗，我們也改變了檢查點的頻率，并評估了一個連接請求的延時。 如圖9c所示，檢查點的頻率對延遲沒有直接影響。這是預(yù)料之中的，因為每個副本都會同步所有的歷史事務(wù)，所以網(wǎng)絡(luò)帶寬的消耗是由狀態(tài)傳輸主導(dǎo)的。

吞吐量和可擴展性。我們評估了 f = 1、f = 2 和 f = 5 時 Dyno 的吞吐量。如圖 9e 所示，當(dāng) f = 1 時，Dyno 的峰值吞吐量為 76 ktx/s，在部分吞吐量中處于最高水平目前已知的同步 BFT。

當(dāng) f 增加時，性能會下降，正如幾乎所有 BFT 協(xié)議所觀察到的那樣。我們在圖 9f 中報告了 Dyno 和 BFT-SMaRt 的峰值吞吐量。 Dyno 實現(xiàn)了比 BFT-SMaRt 更高的峰值吞吐量，部分原因是底層實現(xiàn)的效率。

根據(jù)會員要求執(zhí)行。我們評估 Dyno 的會員請求的性能。我們讓 f = 1 并讓 400 個客戶端同時向系統(tǒng)提交常規(guī)請求。我們評估了三種不同的場景：1）加入請求下的性能； 2) 休假期間的表現(xiàn)； 3）加入和離開請求下的性能。

加入請求下的性能。我們讓一個副本提交加入請求，并評估 g-correct 副本（即從時間 0 開始正確的副本）和新副本的吞吐量。如圖 9g 所示，系統(tǒng)在加入請求時不會出現(xiàn)任何性能下降。

對于多個加入請求下的性能，我們從 4 個副本開始（f = 1）。然后我們定期發(fā)出成員請求并添加副本，直到系統(tǒng)有 8 個副本。我們展示了 g-correct 副本和加入系統(tǒng)的每個新副本的吞吐量。如圖 9h 所示，系統(tǒng)在收到每個加入請求后都會出現(xiàn)性能下降，并在一段時間后恢復(fù)正常。例如，當(dāng)?shù)谝粋€副本加入時，吞吐量從平均 50 ktx/s 下降到 30 ktx/s 左右，下降了 40%。這是預(yù)期的，因為新副本在處理常規(guī)請求時執(zhí)行狀態(tài)傳輸。然而，在狀態(tài)傳輸完成后，吞吐量又回到 50-60 ktx/s。隨著每個副本的加入，整個系統(tǒng)的吞吐量逐漸下降。這也是預(yù)料之中的，因為系統(tǒng)有更多的副本。當(dāng)系統(tǒng)有 8 個副本時，整體吞吐量從 50-60 ktx/s 下降到 40-50 ktx/s。

我們匹配大部分系統(tǒng)配置參數(shù)，并在相同設(shè)置下評估 BFT-SMaRt 的性能。結(jié)果如圖 9i 所示。與 Dyno 不同，在 BFT-SMaRt 中，加入系統(tǒng)的副本的吞吐量始終低于現(xiàn)有副本的吞吐量。此外，隨著副本加入 Dyno，整體吞吐量下降始終低于 BFT-SMaRt。

休假請求下的表現(xiàn)。我們從 10 個副本（f = 3）開始，然后讓 6 個副本一個接一個地離開。系統(tǒng)的吞吐量如圖 9j 所示。與之前的情況相比，吞吐量更穩(wěn)定，主要是因為副本可以在刪除請求傳遞后直接離開系統(tǒng)。 BFT-SMaRt 的性能相似，如圖 9k 所示，除了 BFT-SMaRt 的整體吞吐量比 Dyno 低約 30%-40%。

在多個加入和離開請求下的性能。我們還評估了加入和休假請求下的表現(xiàn)。特別是，我們在 30 秒的時間間隔內(nèi)觸發(fā) 3-5 個隨機加入或離開請求。我們首先從 4 個副本開始，評估 Dyno 和 BFT-SMaRt 的性能。我們在圖 9l 中展示了 g 校正副本的性能。性能類似于僅加入或離開請求下的性能。 BFT-SMaRt 在某些請求期間可能會達到低（接近 0）吞吐量。相比之下，Dyno 的性能總體上更穩(wěn)定。

我們讓系統(tǒng)一開始有 f = 3（10 個副本），然后再次進行相同的實驗。我們在圖 9m 中展示了 Dyno 的結(jié)果，在圖 9n 中展示了 BFT-SMaRt 的結(jié)果。我們展示了 g 校正副本、加入系統(tǒng)的副本和離開系統(tǒng)的副本的性能。盡管吞吐量通常較低，但兩種協(xié)議的結(jié)果與 f = 1 時的結(jié)果相似。

我們還在頻繁的成員請求下評估 Dyno，我們從 10 個副本開始，讓副本以隨機間隔頻繁加入和離開。如圖 9o 所示，隨著頻繁的成員請求，系統(tǒng)的吞吐量趨于更加動蕩，因為副本必須為新加入的副本執(zhí)行頻繁的狀態(tài)轉(zhuǎn)移。

9 結(jié)論

我們研究了動態(tài)拜占庭容錯協(xié)議，其中副本可以加入和離開系統(tǒng)。我們正式定義了動態(tài)拜占庭容錯的安全定義，并提出了不同但有意義的變體。我們介紹 Dyno，一種高效的動態(tài)拜占庭容錯協(xié)議。我們表明，通過多達 30 臺服務(wù)器的部署，Dyno 是高效的，能夠以低成本處理會員請求。文章來源地址http://www.zghlxwxcb.cn/news/detail-482280.html

到了這里，關(guān)于【論文閱讀】Foundations of Dynamic BFT --- IEEE S&P ‘22的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！