了解恆星共識協議

原文

https://medium.com/interstellar/understanding-the-stellar-consensus-protocol-423409aad32e

了解恆星共識協議

恆星共識協議(Stellar Consensus Protocol)最初由David Mazières在2015年的白皮書中描述。它是一個“聯邦拜占庭協議系統”，允許去中心化、無領導的計算網路，有效地就某些決策達成共識結果。Stellar支付網路使用SCP向所有參與者提供網路交易歷史的一致視圖。

共識協議以難以理解而著稱。SCP比大多數更簡單，但仍然享有這種聲譽——部分原因是人們錯誤地認為白皮書前半部分描述的“聯邦投票”就是SCP。但事實並非如此！相反，它是白皮書後半部分用來構建實際恆星共識協議的重要組成部分。

在本文中，我們將簡要介紹什麼是“協議系統”，什麼可以使一個“拜占庭”，以及為什麼要使拜占庭成為“聯邦”。然後我們將解釋SCP白皮書中描述的聯邦投票程序，最後解釋SCP本身。

協議系統(Agreement systems)

協議系統允許一組參與者就某事達成相同的決定——例如，午餐點什麼。

在星際辦公室裡，我們實施了我們自己的午餐協議系統：我們訂購我們的運營經理John說的任何東西。這是一個簡單有效的協議系統。我們都相信John每天都會點一些有趣而有營養的東西。

但是如果John濫用這種信任呢？他可以單方面決定我們都必須成為素食主義者。一兩個星期後，我們可能會罷免他並將他的權力交給Elizabeth，但也許她正在吃酪梨鯷魚三明治，並認為我們都應該這樣做。權力會腐敗，我們可能會做出決定，因此我們會尋求一些更民主的方法：某種方式來確保聽到不同的偏好，同時仍能達到及時、明確的結果，這樣我們就不會最終沒有人點午餐，或者我們五個人重複下了午餐訂單，或者直到下午4點才決定點什麼。

看起來解決方案很簡單：只需進行投票！但這是騙人的。誰來收集選票並報告結果？為什麼我們其他人應該相信他們所說的話？也許我們可以先投票給一個我們都信任的領導人來進行投票——但是然後誰來進行投票呢？如果我們不能就一個領導人達成一致怎麼辦？或者，如果我們可以達成一致，但那個領導卻被困在會議中，或者病倒了怎麼辦？

類似的問題在分散式計算網路中很常見。所有參與者或節點必須就某個決定達成一致，例如輪到誰更新共享文件或從處理隊列中拉出任務。在加密貨幣網路中，節點必須反復從多個可能發生衝突的版本中決定共享賬本的完整歷史是什麼樣的。該網路範圍的協議允許加密硬幣的接收者相信該硬幣(a)有效（非偽造）和(b)尚未在其他地方使用。它還向他們保證他們將來能夠使用它，因為新的接收者將出於同樣的原因對它有同樣的信心。

分散式計算網路中的任何協議系統都需要容錯：它必須產生一致的結果，儘管出現諸如通訊線路緩慢、節點無回應和消息排序錯亂等錯誤。拜占庭協議系統還可以容忍“拜占庭式”錯誤：節點提供虛假信息，無論是由於錯誤還是蓄意試圖顛覆系統，或為了獲得某些好處。(註1)考慮加密貨幣的擁有者Alice，她必須選擇從Bob那裡購買美味的冰淇淋，或者將其支付給Carol以償還債務。Alice可能希望通過欺詐性地向Bob和Carol支付相同的硬幣來實現這兩種方式。為此，她必須讓Bob的電腦相信硬幣從未支付給Carol，並且她必須讓Carol的電腦也相信硬幣從未支付給Bob。拜占庭協議系統可以使用一種稱為仲裁(quorum)的多數規則來有效地實現這一點。這種網路中的節點拒絕承諾(commit to)特定版本的歷史，直到它看到足夠多的對等節點（仲裁）也準備承諾。一旦發生這種情況，他們就形成了一個足夠大的投票集團，以迫使網路中的其餘節點同意他們的決定。Alice也許可以讓一些節點代表她撒謊，但如果網路足夠大，她的嘗試將被誠實節點的投票壓倒。

形成一個仲裁需要多少個節點？至少要多數，更典型的是絕對多數，以打擊錯誤和欺詐行為。但是知道你何時擁有多數意味著知道你有多少參與者。在星際辦公室或縣市選舉中，這些數字很容易知道。但是，如果您的參與者集合是一個定義鬆散的網路，成員可以隨意加入和離開，而無需與任何中央機構協調，那麼您需要一個聯邦拜占庭協議系統：它可以不是從某個預定的節點名冊中確定仲裁人數，而是動態地從某個時間點不斷變化，且不可避免地不完整的成員快照中確定仲裁人數。

僅從龐大網路中單個節點的有限視角來構建仲裁似乎是不可能的，但確實如此。這個仲裁甚至可以對去中心化投票的結果產生信心。SCP白皮書展示了如何使用稱為聯邦投票的程序來做到這一點。

對於不耐煩的人

本文的其餘部分詳細描述了聯邦投票和恆星共識協議。作為後續內容的指南——或者如果你不關心細節而只想要長話短說——這裡是該過程的概述。

1. 節點們對“被提名人(nominees)”進行多輪聯邦投票。一輪聯邦投票意味著：

l 一個節點投票給某個陳述，例如“我提名 V”；

l 該節點監聽來自其對等節點的投票，直到找到一個它可以“接受(accept)”的投票；

l 該節點尋找一個也接受該陳述的“仲裁(quorum)”。這樣就“確認(confirms)”了這一陳述。

2. 一旦一個節點可以確認一個或多個被提名人，它就會開始嘗試通過更多輪聯邦投票來“準備(prepare)”“選票(ballot)”。

3. 一旦一個節點可以驗證選票已準備好，它就會開始嘗試通過更多輪聯邦投票來“承諾(commit)”選票。

4. 當一個節點可以確認選票已承諾，它就可以“外部化(externalize)”該選票中的值，將它當作共識的結果。

這些步驟涉及多輪聯邦投票，共同形成單輪SCP。要了解每個步驟的含義、為什麼需要這麼多步驟、它們是如何工作的以及可能出現的問題，請繼續閱讀！

聯邦投票(Federated voting)

聯邦投票是一種用於發現參與者網路是否可以就提案達成一致的程序。在一輪聯邦投票中，每個節點必須從潛在的許多可能值中選擇一個作為該輪的結果。但在確定網路中的其他節點不會選擇任何不同的結果之前，節點不能做出上述的選擇(也就是大家的選擇都要一樣)。為了確保這一點，節點來回交換一系列消息，使每個節點都確認「仲裁內的節點接受相同的投票」。本節的其餘部分解釋了該句子中的術語以及如何實現這種確認。

仲裁和仲裁切片(Quorums and quorum slices)

讓我們從確定仲裁開始。正如我們上面所討論的，在具有動態成員資格的去中心化網路中，不可能提前知道有多少節點，以及有多少節點才叫做多數。聯邦投票通過引入仲裁切片(quorum slice)的新穎思想解決了這個問題：節點信任的對等點的小集合，以傳達有關網路其餘部分投票狀態的信息。每個節點都定義了自己的仲裁切片（本身也是其成員）。

要形成仲裁，請從仲裁切片開始。對於每個成員，添加其仲裁切片的成員。然後添加這些成員切片的成員，依此類推。隨著您的繼續，您會遇到越來越多無法添加的節點，因為它們已經包含在內。當沒有更多新節點要添加時，停止：您已經從起始節點的仲裁切片的“傳遞閉路(transitive closure)”形成了一個仲裁。

要從給定節點中找到仲裁…

…添加其仲裁切片的成员…

…然後添加這些節點切片的成員

繼續，直到沒有要添加的節點

沒有剩餘的節點要添加。這就是一個仲裁。

事實上，每個節點可能有多個仲裁切片。要形成仲裁，只需選擇其中一個切片並添加成員；然後為每個成員選擇任何一個切片並添加這些成員，依此類推。這意味著每個節點都是許多可能的仲裁的成員。

在每個步驟中只選擇一個仲裁切片

一種可能的仲裁。或者…

…選擇不同的切片…

…(若有可能)…

…產生不同的仲裁

一個節點如何知道另一個節點的仲裁切片的成員？它以同樣的方式了解其他節點的任何其他信息：來自每個節點在其投票狀態發生變化時發送到網路的廣播。每個廣播都包含發送節點切片的詳細信息。(註2)

回想一下，在非聯邦拜占庭協議系統中，仲裁被定義為所有節點的多數。(註3)一旦提案超過仲裁臨界點，其他網路成員就會確信任何競爭提案都會失敗。這就是網路如何收斂到一個結果。

但是在聯邦拜占庭協議系統中，不僅不能有多數（因為沒有人知道網路的總規模），而且多數的概念甚至沒有用處！如果系統中的成員資格是開放的，那麼某人可以通過進行所謂的Sybil攻擊來獲得多數：使用多個節點多次加入網路。那麼，什麼是一個節點的仲裁切片的傳遞閉路使其成為一個仲裁？又是什麼使它能夠壓倒競爭的提案呢？

從技術上講，什麼都沒有！想像一個包含Alice、Bob、Carol、Dave、Elsie和Frank的網路。

Alice在她的仲裁切片中有Bob和Carol。Bob有Alice和Carol，Carol有Alice和Bob。同時，Dave、Elsie和Frank在各自的仲裁切片中都有彼此。Alice-Bob-Carol子群組可以做出Dave-Elsie-Frank群組永遠不會聽到的決定，反之亦然。該網路無法達成共識（意外除外）。

因此，為了使聯邦投票發揮作用（並且為了應用論文的重要定理），SCP要求網路必須具備仲裁交集(quorum intersection)的特性。在具有此特性的網路中，您可以建構的任何兩個仲裁總是至少有一個節點重疊。網路的普遍觀點，這種方式與擁有多數一樣好。直觀地說，這意味著如果任何仲裁同意陳述X，則沒有其他仲裁可以同意非X，因為它必然包括第一個仲裁中已經投票給X的某個節點。

如果網路有“仲裁交集”…

…然後你可以建構任何兩個仲裁…

…總是會重疊的

（當然，重疊的節點可能都是拜占庭式的——撒謊或行為不端。在這種情況下，具有仲裁交叉點並不能幫助網路達成一致。因此，SCP白皮書中的許多結果都依賴於明確陳述的假設，例如即使將行為不端的節點從網路中刪除，網路也享有仲裁交集。為了清楚起見，我們將在本文的其餘部分隱含這些假設。）

期望一組獨立的節點以這樣的方式組織它們的切片，可靠地享有仲裁交集，似乎是不合理的。但是有兩個原因可以說明這不是那麼牽強。

第一個原因是網際網路本身的存在。網際網路是具有仲裁交集的獨立節點網路的完美範例。網際網路上的大多數節點只連接到其他幾個本地節點，但是這些小集合重疊得足夠多，以至於每個節點都可以通過一條或另一條路由到達其他每個節點。

第二個原因是針對於Stellar支付網路（SCP最廣泛的應用）。Stellar網路中的每種資產類型都有一個發行人，而Stellar最佳實踐要求每個發行人在網路中指定一個或多個節點來處理贖回請求。為了您的利益，對於您關心的每個資產，應該直接或間接地將這些節點包含在您的仲裁切片中。然後，對這些資產感興趣的所有節點組成的仲裁，將至少在那些贖回節點中重疊。對多種資產感興趣的節點，將在其仲裁切片中包含所有相關發行人的贖回節點，這些節點往往會將所有資產連接在一起。另外，並不是任何資產都要以這種方式連接到網路上其他資產——沒有仲裁交集的網路是可以的。（想想以美元運營的銀行有時希望與以歐元運營的銀行、以比索運營的銀行進行交易，因此它們在一個網路上，但他們都不關心孩子們交易棒球卡的獨立網路。）

當然，期望網路應該享有仲裁交集並不等於保證。其他拜占庭協議系統的複雜性很大程度上歸功於對仲裁的保證。SCP的一個重要革新是它從共識算法本身中刪除了製定仲裁的責任，並將其推送到應用層。這表明，儘管聯邦投票足以適用於任何類型的投票值，但實際上它的穩健性主要取決於這些值的更廣泛含義。一些假設的用途可能不像其他用途那樣容易產生連接良好的網路。

投票、接受和確認(Voting, accepting, and confirming)

在一輪聯邦投票中，一個節點可以選擇從投票給某個值 V 開始。這意味著向網路廣播一條消息，說：“我是節點 N，我的仲裁切片是 Q，我投票給 V。”當一個節點以這種方式投票時，它承諾它從未投票反對 V，也永遠不會。

一個節點可以從他們的廣播消息中看到它的對等點是如何投票的。一旦該節點收集到足夠多的此類消息，它就可以遍歷其中的仲裁切片以找到仲裁。如果它可以看到仲裁內所有的節點都投票給 V，那麼它可以轉為接受 V，並將這條新消息廣播到網絡。（“我是節點 N，我的仲裁切片是 Q，我接受 V。”）接受(Accepting)比單純的投票(Voting)提供了更強的保證。當一個節點投票給 V 時，它永遠不會投票給非 V。但是當一個節點接受 V 時，網路中的任何節點都不會接受非 V。（SCP白皮書中的定理8證明了這一點。）

當然，N 很有可能不會立即看到大量節點同意其 V 投票。其他節點可能會投票給其他值。但是還有另一種方式可以讓節點從單純的投票推進到接受。N 可以接受一個不同的值 W，即使 N 沒有投票給它，也沒有看到投票給它的仲裁，但只要它看到一個阻塞集(blocking set)接受它。阻塞集是從 N 的每個仲裁切片中選擇一個節點來組成。顧名思義，它能夠阻止任何其他值。如果這樣一個集合中的所有節點都接受 W，那麼（根據定理8）將永遠不可能形成一個接受非 W 的群體，因此 N 也接受 W 是安全的。

具有三個仲裁切片的節點 N。

B-D-F 是 N 的阻塞集：它包含來自 N 的每個切片中的一個節點。

B-E 也是 N 的阻塞集，因為 E 出現在 N 的兩個切片中。

但是阻塞集不是仲裁。如果有人可以在 N 的每個切片中破壞一個節點，那麼就很容易欺騙節點 N 接受一個不應該接受的值。所以接受一個值並不是投票的結束。相反，N 必須確認該值，這意味著它看到一個仲裁的節點全都接受它。如果它走到這一步，那麼正如SCP白皮書所證明的（在定理11中），網路的其餘部分最終也將確認相同的值，因此 N 已經以該值作為聯邦投票結束的結果。

一張含有文字的圖片

自動產生的描述

聯邦投票

投票、接受和確認的過程構成了一輪完整的聯邦投票。恆星共識協議結合了許多這樣的回合來創建一個完整的共識系統。

恆星共識協議(The Stellar Consensus Protocol)

共識系統的兩個最重要的屬性是安全性(safety)和活性(liveness)。如果共識算法永遠不會為不同的參與者產生不同的結果，那麼它就是“安全的”。（Bob的歷史副本永遠不會與Carol的不一致。）同時，“活性”意味著算法永遠不會不產生結果——即它不會卡住。

剛剛描述的聯邦投票程序在某種意義上是安全的，如果一個節點確認值V，則沒有其他節點會確認不同的值。但“不會確認不同的事情”與“會確認某事”是兩回事。可能有太多不同的值被投票，甚至沒有達到“接受”門檻。這意味著聯邦投票缺乏活性。

恆星共識協議以保證安全性和活性的方式使用聯邦投票。(註4)簡而言之，這個想法是對多個值進行多次聯邦投票，直到一個值通過SCP的各個投票階段，如下所述。

SCP尋求共識的值可能是恆星賬本、午餐訂單或其他任何東西，但要注意的是，SCP的聯邦投票輪所投票、接受或確認的對象，並不是這些值。相反的，聯邦投票發生在關於這些值的陳述(statements)上。

第一輪聯邦投票發生在提名階段，在一系列形式為“我提名 V”的陳述中，可能有許多不同值的V。提名的目標是找到一個或多個這樣的陳述，可以通過一直接受和確認來達成。

在找到可確認的被提名人後，SCP進入投票階段(balloting phase)，目標是找到一些選票(ballot)（這是一個被提名值的容器）和可以承諾(commit)它的仲裁。如果仲裁承諾本次投票，其值就是這一輪共識的結果。但在節點可以表決要承諾選票之前，它必須先確認所有較小的選票都已中止(aborted)。這些步驟——中止選票以找到可以確認承諾的投票——涉及對有關選票的多項陳述進行多輪聯邦投票。

以下部分更詳細地描述了提名和投票。

提名(Nomination)

在提名階段開始時，每個節點可以自發地選擇一個值 V，並投票支持“我提名 V”這個陳述。此階段的目標是通過聯邦投票確認某些值的提名。

有可能有足夠多的節點投票支持足夠多不同的“我提名”陳述，這是一個不受控制的局面——沒有提名可以達到“接受”的門檻。因此，除了投出自己的提名票外，節點還會“附和”其對等節點的提名。附和意味著節點投票給“我提名 V”，在看到來自節點提名 W 的消息後，現在同時投票“我提名 V”和“我提名 W”。(註5)從概念上講，這些是並行發生的單獨的聯邦投票，每個單獨的投票都能夠達到接受或確認。在實踐中，SCP協議消息將這些單獨的投票集中在一起。

儘管投票提名 V 是承諾永遠不會投票反對提名 V，但聯邦投票之上的應用層（在本例中為 SCP）可以定義“反對”的含義。SCP沒有定義任何與“我提名 X”投票相矛盾的陳述——沒有“我拒絕對 X 的提名”——因此節點可以投票提名任意數量的值。其中許多提名可能無處可去，但最終會有一個或多個提名可以被節點接受或確認。一旦被提名人被確認，它被稱為候選人(candidate)。

使用聯邦投票的SCP提名。可能有許多值“B”由對等點提名並由節點“附和”。

提名可能會產生多個可確認的候選人，因此SCP要求應用層提供某種方法將候選人合併成一個組合。合併方法可以是應用層要求的任何方法，只要該方法是確定性的，也就是說每個節點合併相同的兩個候選對象時，都會產生相同的組合。在午餐訂購系統中，“合併(combining)”可能只是單純地丟棄兩個候選人中的一個。（但是，確定性地：每個節點都必須選擇相同的值來丟棄。例如，按字母順序較早的選擇。）在Stellar支付網路中，被提名人是分類賬(ledgers，在此可視同為區塊鏈中的blocks)，合併兩個被提名人涉及合併它們包含的交易，以及它們兩個時間戳記中的後者。

SCP白皮書證明（定理12）提名導致網路最終在提名結束時收斂到單個複合候選人。但是有一個問題：聯邦投票是一種非同步協議。（SCP也是如此。）換句話說，節點不是按時間協調的，而是通過它們發送的消息來協調的。從節點的角度來看，提名何時結束尚不清楚。儘管所有節點最終都會到達同一個複合候選人，但它們可能會採取不同的路線到達那裡，沿途產生不同的、有效的複合候選人，永遠無法分辨哪一個是最後一個。

不過這沒關係。提名只是為了產生並限制候選人的數量以達成共識。其餘的共識由稱為投票(balloting)的過程處理。

投票(balloting)

選票是一對：<counter,value>，其中 counter 是從 1 開始的整數，value 是提名階段的候選人。它可能是節點自己的候選人，也可能是節點接受的某個對等點的候選人。粗略地說，投票通過對有關選票的陳述進行可能的多次聯邦投票，反复嘗試讓網路在某些選票中就某個候選人達成共識。選票中的計數器跟踪所做的嘗試，具有較高計數器的選票優先於具有較低計數器的選票。如果選票 <counter,value> 似乎卡住了，則開始新的投票，現在在選票 <counter+1,value> 上。

區分值(values)（例如，午餐訂單應該是什麼，例如比薩餅或沙拉）、選票(ballots)（一對<counter,value>）和有關選票的陳述(statements)這三者，是非常重要的。一輪SCP包括對此類陳述的多輪聯邦投票，特別是：

l “我準備承諾選票B，”和

l “我承諾選票B。”

從某個節點的角度來看，當它找到能夠確認（找到接受的仲裁）“我承諾選票B”陳述的選票B時，就達成了共識。此時，對B中的值採取行動是安全的——例如，下午餐訂單。這被稱為外部化(externalizing)該值。一旦選票被確認承諾了，一個節點就可以確定每個其他節點都已外部化或不可避免地會外部化相同的值。

儘管從概念上講，許多聯邦投票發生在關於許多不同選票的陳述上，但交換的實際協議消息要少得多，因為每個消息都封裝了一系列選票。因此，一條消息會同時提升許多聯邦投票的狀態，例如：“我接受 <min,V> 到 <max,V> 範圍內的選票已承諾。”

那麼“準備(prepared)”和“承諾(committed)”是什麼意思呢？

當一個節點確信其他節點不會承諾具有不同值的選票時，它會投票承諾選票。對這一點深信不疑是準備(prepare)的目的。一張寫著“我準備承諾選票B”的投票是保證永遠不會投任何小於B的選票——即，一個計數器較小的選票。(註6)那些較小的選票被準備投票所“中止”，而B是“準備好的”。

為什麼“我準備承諾選票B”意味著“我保證永遠不會承諾低於B的選票”？這是因為SCP將“中止(abort)”定義為“承諾(commit)”的反義詞。正如我們之前討論的，投票支持某事是保證永遠不會投票反對它，所以對準備選票的投票也隱含著中止其他選票。

在進行“承諾”的投票之前，節點必須先找到它可以確認已準備好的選票。換句話說，它對可能許多不同的“我準備承諾選票B”選票進行聯邦投票，直到找到一個仲裁接受的選票。

準備投票的選票從哪裡來？節點投出的第一個準備投票是針對 <1,C> 的，其中 C 是提名階段產生的複合候選人。然而，即使在準備投票開始後，提名也可能產生額外的候選人，因此這些成為新的選票。同時，對等節點可能有不同的候選人，他們可以形成一個接受“我準備承諾選票B2”的阻塞集，這將說服節點也接受它。最後，如果當前的選票似乎被卡住了，那麼有一個逾時機制會導致新一輪的聯邦投票在具有更高計數器的新選票上開始。

一旦節點發現選票B可以確認已準備好了，它就會為“我承諾選票B”投下新票。該投票告訴對等節點該節點永遠不會中止B。事實上，如果B是選票 <N,C>，那麼“我承諾選票 <N,C>”也隱含地為準備從 <N,C> 到 <∞,C> 的每張選票進行投票。如果其他節點仍處於協議的早期階段，則此額外含義有助於接收此消息的其他節點趕上。

在這一點上值得再次強調的是，這些是非同步協議。僅僅因為一個節點正在發送承諾投票，並不意味著它的對等節點也是如此。有些人可能仍在對準備進行投票，有些人可能已經外部化了一個值。SCP說明了節點應如何處理每種類型的對等消息，無論它處於哪個階段。

如果“我承諾 <N,C>”不能被接受或確認，也許 <N+1,C> 可以，或者 <N+2,C> ，或者，在任何情況下，一些帶有C的選票，而不是任何其他值，因為節點現在已保證永不中止 <N,C>。當一個節點進行承諾投票時，就共識而言，結果是C或失敗。然而，這還不足以讓節點將C外部化。一些拜占庭節點（根據我們的安全假設，數量少於仲裁）可能會對節點撒謊。接受然後確認一些選票（或選票範圍）是使節點最終有信心將C外部化的原因。

一張含有文字的圖片

自動產生的描述