少數決：更安全的分布式一致性算法選舉機制*

李 彬，姜建國

1.北京交通大學計算機與信息技術學院，北京 100044

2.國家保密科技測評中心，北京 100044

3.中國科學院信息工程研究所，北京 100093

1 引言

現實生活中，選舉就是讓符合多數人想法或利益的人獲得領導權，被選舉者需要大多數人或大多數有投票權人的贊同，即多數者決策。這個在人類社會中的民主模式啟發并影響了分布式系統一致性算法研究者們，經典的一致性算法Paxos的選舉機制就是如此。它的Leader選舉分為兩個階段[1]，且兩個階段無法分割、相互關聯共同保障了數據的一致性。第一階段：準備階段，提案者（proposer）選擇一個提案號，并發送提案給投票者（acceptor），試探能否得到多數派投票者的響應。第二階段：如果某個提案者在第一階段收到多數派投票者的響應，則提交提案，如果能夠再次得到多數派acceptor的同意，則這個提案者被選為Leader。顯然，這兩個階段都是采用多數決的方式。其實，分布式系統中各個服務器并不在乎Leader是誰，Leader是否意識形態與自己一致，是否為民主選舉，他們需要的只是能非固定地選出一個服務器，它能按照協議履行相關職能，讓系統保持數據更新一致。本文將提出“少數決”這一新的選舉機制，通過研究分析此種選舉不僅是簡單的逆向思維，還在保護去中心化，提高一致性算法安全性上有更好的表現。

2 基于選舉的一致性算法面臨的風險

首先，Multi-Paxos[2]、Raft[3]、ZAB[4]、VR（viewstamped replication）[5]這些已實際應用的一致性算法其實都是基于選舉的一致性算法。Multi-Paxos中的Leader是作為對經典Paxos的優化而提出，通過選擇一個proposer作為Leader降低多個提案者引起沖突的概率，提升性能將一次決議的平均消息代價縮小到最優的兩次，而且當有多個Leader存在時算法也仍是安全的，只是退回為經典Paxos選舉。而Raft、ZAB、VR這些強調唯一Leader的協議，它們直接從Leader的角度描述協議的流程，但是實際上它們使用了和Paxos完全一樣的原理來保證協議的安全性，當同時存在多個節點同時嘗試成為Leader或者多個節點都認為自己是Leader時，它們也將退回至經典Paxos選舉[6]。

在基于選舉的分布式系統中可能存在這么一種問題節點：它們不同于傳統的拜占庭將軍問題[7]（Byzantine failures）節點，不會故意發出錯誤的更新去破壞系統數據的一致性，但是它們會在選舉誰作為Leader時操作選票，目的是讓指定的節點獲得Leader特權，從而壟斷客戶業務。這種自私行為本身違背了去中心的原則，一旦這個被指定的節點遭受攻擊或故障，將是災難性的系統崩潰。因此，需要選擇更安全的一致性算法選舉機制來提升整個分布式系統的安全性。

3 現實中的少數決選舉

現實中少數決選舉來源于Liar Game中的Minority Decision[8]，它并不牽扯少數者博弈[9]問題，本是一個純粹基于隨機目的選擇“幸運兒”游戲，具體規則如下：

首先，組織者隨機選擇一名參與者出一道二選一的題目，如“你是否喜歡紅色？”。為充分保證公平性，一般是一人出一題后就換下一個人出題，出題順序無特殊要求，總之大家都有公平的機率出題即可。

接著，大家根據題目和自己想法做出“是”或“否”的選擇。這里需要說明的是大家的選擇并不一定是自己真實的想法，需要思考是：怎么讓自己的選擇不是大多數人的選擇？但可以肯定的是絕不能讓別人知道你的選擇，因為如果有人知道足夠多人的選擇后，他就能做出少數選擇。因此，現實中最簡單的方法就是將選擇寫在紙上后折疊，再投入一個不透明的箱子中。

一次選舉包含多輪答題，每輪答題結束后，由組織者唱票。選擇為少數派的那一方獲勝，進入下一輪繼續進行出題、答題；而選擇為多數派一方遭淘汰；如雙方人數持平或大家選擇都一致，則無淘汰者，并直接進入下一輪。

最后，可能是剩下一個人或是兩個人，一個人時直接宣布勝出；兩個人時則組織者參與進來以打破兩人無法產生少數派的僵局，進行決賽。假設進入決賽的兩人為A和B，組織者為Z。如果不是A或B的選擇為少數派（即Z勝出），則A、B和Z繼續下一輪，直至A或B勝出。

根據上述規則描述，可以歸納此種選舉機制的流程如圖1所示。

Fig.1 Minority election mechanism process圖1 少數決選舉機制流程

下面舉例進行說明，假設參與者為10人，分別為P1,P2,…,P10，組織者為Z。例1：第一輪P1、P2、P3、P4選擇Yes，其余人選擇No，則P1、P2、P3、P4進入下一輪；第二輪P1、P2、P3選擇Yes，P4選擇No，則P4獲勝。例2：第一輪P1、P2選擇Yes，其余人選擇No，則P1、P2進入下一輪（決賽）；第二輪P1、P2選擇Yes，Z選擇No，則無人淘汰進行下一輪；第三輪P1和Z選擇Yes，P2選擇No，則P2獲勝。例3：第一輪P1、P2、P3、P4、P5選擇Yes，其余人選擇No，平局無人淘汰進行下一輪；第二輪P1選擇Yes，其余人選擇No，則P1獲勝。

4 安全性分析

多數決選舉中最常見的一種作弊方式就是控票，控制半數以上有投票權的人的選票，就能保證自己想讓誰當選就讓誰當選。在經典Paxos中可以更容易些，因為只有acceptor（投票者）能投票，所以只要控制50%以上的acceptor就能隨心所欲地指定Leader。而在類Raft這種每個節點都有投票權的系統中實現控票，則需要控制50%以上的節點。本章將分析采用少數決選舉機制是否也存在類似的安全性問題。為方便分析，本章假設是由22個參與者組成的少數決選舉系統。

4.1 絕對控制攻擊

在這22個參與者組成的少數決選舉系統中，如果已經控制了其中的12個參與者的選票（超過50%），接下來是否能夠完全按照自己的意志選擇Leader。假設P1,P2,…,P22為22個參與者，P1,P2,…,P12組成受控團隊。假定想指定P1成為Leader，就必須保證P1能100%順利通過3輪的淘汰，因此團隊采取全力保證P1和盡可能多的隊友進入下一輪的方式進行投票。第一輪，因為還是不知道團隊外這10個參與者的選擇，所以要保證P1能進入第二輪，只能讓P2,P3,…,P12這11個隊友選擇Yes，P1選擇No，這樣才能保證結果最壞是平票（因為有可能團隊外的10個參與者也同時選擇No），但只要這10個參與者是未經商量隨機投票的，總會有一輪它們會選擇不同的答案。但是，這樣做后第二輪又變成公平的10選1選舉了，P1將只有10%的獲勝幾率。

加大攻擊力度，分析在控票率達到81.8%（18/22）的情況下是否可以保證P1獲勝。第一輪，因為不知道團隊外P19、P20、P21、P22的選擇，所以要保證P1能進入下一輪，先能讓P1,P2,…,P7這7個隊友選擇Yes，P8,P9,…,P18這11個隊友選擇No，這樣才能保證結果最壞是平票（P19、P20、P21、P22同時選擇Yes），但只要P19、P20、P21、P22是未經商量隨機投票的，總會有一輪其中會有參與者因選擇No而遭淘汰。假設第一輪P20、P21、P22選擇Yes，P19選擇No，因此P1,P2,…,P7和P20、P21、P22進入下一輪。第二輪，同理P1、P2這2個隊友選擇Yes，P3、P4、P5、P6、P7這5個隊友選擇No，最壞情況，假設第二輪P21、P22選擇Yes，P20選擇No，因此P1、P2和P21、P22進入下一輪。第三輪，P1、P2無論怎么作弊，都無法保證P1獲勝。這表示控制81.8%的選票只能將P1獲勝的幾率提升至25%，且其他少于18個隊友的團隊也都無法保證P1的100%獲勝。

再次加大攻擊力度，分析在控票率達到86.4%（19/22）的情況下是否可以保證P1獲勝。第一輪，因為不知道團隊外P20、P21、P22的選擇，所以要保證P1能進入下一輪，先能讓P1,P2,…,P8這8個隊友選擇Yes，P9,P10,…,P19這11個隊友選擇No，這樣才能保證結果最壞是平票（P20、P21、P22也選擇Yes），但只要P20、P21、P22是未經商量隨機投票的，總會有一輪其中會有參與者因選擇No而遭淘汰。假設第一輪P21和P22選擇Yes，P20選擇No，因此P1,P2,…,P8和P21、P22進入下一輪。第二輪，同理P1、P2、P3這3個隊友選擇Yes，P4,P5,…,P8這5個隊友選擇No，這時最壞情況又是平票，逼P21和P22至少一個淘汰，否則永遠平票。假設P22選擇Yes，P21選擇No，因此P1、P2、P3和P22進入下一輪。第三輪，同理P1選擇Yes，P2、P3這2個隊友選擇No，P22注定被淘汰，而P1通過一系列操作終于獲勝了。

根據上面分析可以得出，少數決中絕對控制攻擊需要滿足一個十分苛刻的條件才能確保攻擊成功，表1列出了參與者分別為3至30個時保證絕對控制攻擊成功所需要的受控個數，圖2展示了對應的所需受控率。

Table 1 Number of controls required for success of absolute control attack with 3 to 30 participants表1 參與者為3至30個時絕對控制攻擊成功所需受控數

分析表1和圖2，可以看出：

（1）參與者為4個時，控票率達到75%（3/4）時，是少數決遭受絕對控制攻擊所需控票率的最低值，即最易受攻擊狀態；

（2）參與者為10個時，是一個低值（下劃線標記的），此時控票率需達到80%（8/10）；

（3）參與者為22個時，是另一低值，此時控票率需達到86.4%（19/22）；進而推論隨著參與者的增加，低值出現的頻率將越來越低，且低值也越來越高，即攻擊難度越來越大。

4.2 團隊攻擊

Fig.2 Control rate required for success of absolute control attack with 3 to 30 participants圖2 參與者為3至30個時絕對控制攻擊成功所需受控率

如果能成功控制一定數量節點的投票，是可以保證這個團隊中的一個最終獲勝，即團隊攻擊成功。第一輪中，安排團隊中的8個節點中4個節點選Yes，另4個節點選No。因此這一輪后留下來的節點中總有團隊中的4個，最壞情況下還有4個團隊外的節點。第二輪中，安排團隊中的4個隊友中2個選Yes，另2個選No。因此這一輪后留下來的節點中總有團隊中的2個，最壞情況下還有2個團隊外的節點。第三輪中，團隊中的2個隊友中的1個選Yes，另1個選No，只要另外兩節點是未經商量隨機投票的，總會有一輪它們選擇同樣的答案，于是最終成為Leader將是團隊中的一員。

要保證在少數決選舉團隊攻擊成功，團隊成員的數量Tn要滿足一定條件。Tn與可能進行的有效投票輪數r（平局輪不計，r與參與者總數An相關）有關，因此當控制節點數量Tn滿足Tn≥2r時可以確保團隊攻擊成功。

但是，團隊攻擊只能保證團隊中的某一個成員被選為Leader，但仍然無法確定最終獲勝的是哪一個，即只是縮小了產生Leader的節點范圍，降低了系統去中心化的程度。

4.3 欺詐攻擊

首先，假設P1找到P2,P3,…,P8等7個參與者在不為人知的情況下組成一個團隊，把保證團隊獲勝的方法告訴團隊成員，并承諾團隊獲勝后平分作為Leader的權益。然后，P1再找P9,P10,…,P15等7個參與者秘密地組建第二支團隊，策略和承諾相同。最后，P1再與剩余的P16,P17,…,P22秘密地組成第三支團隊。這里成功地組織了3支“8人”團隊，讓每個參與者都堅信自己身在一個將要利用必勝法獲勝并平分勝利果實的團隊里。除了P1，大家都不知道還有其他團隊存在。在第一輪游戲中，P1指示每個團隊里包括P1自己在內的4個隊友投Yes，其余的人都投No。這樣下來，投Yes的一共就有10票，No有12票，于是P1和每個團隊里除P1之外的另外3個人獲勝。下一輪游戲中，P1再指示每個隊伍里包括P1在內的2人投Yes，其他人都投No，這樣Yes就有4票，No有6票，P1再次勝出。最后，P1自己投Yes，并指示其他人都投No，這就保證了P1可以100%獲勝。

這種攻擊方式因其在現實中確實存在理論上的可能，但在沒有獎勵機制、沒有智能協商、需要重復多次選舉的分布式系統中是不可能實現的，因為把一致性算法當作共識機制的分布式系統，被設定是不存在拜占庭將軍問題的。

5 少數決在一致性算法中的實現

本文認為可以利用少數決選舉的科學性產生一致性算法中的隨機Leader。通常來講，一個正確的一致性算法需要滿足以下3條性質：

安全性：具備安全性的算法保證壞的事情絕對不會發生，例如分布式Leader選舉算法，絕對不會出現一個以上進程被選為Leader的情況。

存活性：具備存活性的算法保證好的事情終將發生，即算法在有限的時間內可以結束。

去中心性：在去中心化系統中，任何人都是一個節點，任何人也都可以成為一個中心。任何中心都不是永久的，而是階段性的，任何中心對節點都不具有強制性[10]。

作為一致性算法中最關鍵的選舉機制設計也應具備上述3個性質，下面將給出少數決選舉機制的一個設計方案。

5.1 去中心化

因為分布式系統是去中心化的，所以不能固定設置一個組織者角色。另外，由組織者承擔出題者的職能是沒有任何問題的，因此組織者可以是由所有節點輪流承擔，即每進行一輪就換一個組織者，避免中心化的問題。這種輪換機制，可以是簡單地按ID號i從小到大順序輪轉，然后最大號碼鏈接1號的方式，即1 →2 →3 →…→max→1 →2…，也可以采用其他輪換機制。

5.2 統計參與者范圍

采取少數決選舉分布式系統的每個節點是需要知道整個系統節點個數An，之后增加或減少節點個數時要及時更新An，并且設置初始化判斷勝負的關鍵計數器n=An。

5.3 題目及計票方式

根據第3章描述的少數決選舉特點，題目并不要求難度只是需要二選一的題目，這就自然而然讓布爾值成為首選。而題目競猜也可轉變為：猜二進制隨機數的最后一位、域名服務器ping值的奇偶性等方式。只要是能夠產生具有隨機性的布爾值，且布爾值出現的概率為50%的方式[11]均可作為少數決的題目。下面將以猜二進制隨機數的最后一位為例進行描述。

如由An個節點組成的分布式系統，每個節點產生一個隨機數Rn，并將自己ID信息Answ(Rn,i)一同發送給組織者，組織者將使用Lr(i)函數剝離i所對應隨機數二進制格式時的最后一位。需按照式（1）計算j，如果j=n/2、j=n或j=0則表示沒有淘汰者，每個節點重新產生隨機數；j＞n/2則Lr(i)=0對應的節點ID號進入下一輪比賽名單，設n=n-j；否則，Lr(i)=1對應的節點ID號進入下一輪比賽名單，設n=j。

5.4 存活性

少數決選舉的存活性問題，就是Leader可以在有限的時間內選舉出來，進而推論就是二選一答題是否可以在有限次數內結束。顯然，少數決選舉中的二選一答題問題相當于擲硬幣問題。利用高斯分布函數[12]式（2），可得出以下結論：當觀測結果的正面向上次數遠遠大于正面向下次數，也遠遠大于先驗分布[13]的正面向下次數，則判斷下次為正面向上的概率無限接近1[14]。

式中，a、b、m、l分別代表先驗分布的正面向上次數、反面向上次數、已觀測數據的正面向上次數、反面向上次數。

上述結論說明了，隨著答題次數的增加，每個答題者的答案會一直變動，極小概率會出現所有人答題結果都一致或結果永遠是50%對50%的情況。因為小概率事件可視為不可能事件，所以二選一答題可以在有限次數內結束。

5.5 組織者的期號

為避免由于通信延遲、重發等原因造成一個少數決系統中出現兩個或者兩個以上的組織者，造成混亂，每個組織者都需要附加一個期號（term）。這里的期號使用可參考Raft算法中的實現方式[3]，每次輪換組織者期號就會遞增，答題者只跟隨期號大的組織者進行持續競選。

5.6 組織者

組織者只需要接收本輪比賽名單內的答題者的答案，初始名單為所有節點。組織者需要通知大家本輪答題開始，讓答題者將隨機數Rn發送給自己。這個通知信息包含自己的期號和下一任組織者的ID信息，如M1(term,NextqwID)。

5.7 信息保密性和身份認證

可以通過非對稱加密算法[15]保證答題者隨機數的保密性和確認答題者、組織者身份。非對稱加密算法實現保密信息交換的基本過程是：每個節點生成一對密鑰并將公鑰公開；當答題者需要向組織者發送信息的時候使用組織者的公鑰對隨機數信息進行加密后再發送給組織者；組織者再用自己私鑰對加密后的信息進行解密。此外，非對稱加密算法實現身份認證的基本過程是：答題者可以使用自己的私鑰對需要發送的信息進行簽名后再發送給組織者；組織者再用答題者的公鑰對答題者發送回來的數據進行驗簽，確認其身份。

反之，組織者給答題者發送信息的加密方式和組織者的身份認證也將采取上述方式，這里不再贅述。

5.8 唱票方式

組織者需要將期號、計票結果、進入下一輪的節點ID號、本輪每個答題者的答案等信息，如M2(term,result,NRA_IDs,Answs(n)) 通過廣播方式告知本輪的每個答題者，以示公允。

M2中的信息越詳細越能體現公正性，因為每個答題者是可以通過M2發現當前組織者是否有篡改答題結果或計票錯誤等作惡行為。這里不必采取冷酷策略，即發現某組織者出現一點兒錯誤就終止其參與資格，因為可能會無法區分主觀作惡和客觀網絡傳輸錯誤。可通過EigenTrust[16]、PeerTrust[17]等網絡節點信任評價方法，對該惡意節點做出臨時屏蔽或永久去除等懲罰措施。

5.9 容錯處理

在少數決選舉進行的過程中，可能會出現一些故障，如節點宕機或通信受阻的情況，下面描述兩種最常見故障的處理方式。

（1）答題者中途宕機。由于答題者可能宕機或通信受阻，在規定時間內收到的答案個數num(Answs)少于2個時，代表整個系統出現嚴重故障，本次選舉終止，按照ID號輪換下一個節點繼續出題；如果num(Answs)大于2個但少于預期個數n時，重置n(n=num(Answs))；如果計票結果為平票時，本輪無淘汰節點，直接進行下一輪答題；如果計票結果可以分出勝負時，將未收到答案的答題者列為淘汰方，獲勝者繼續進行下一輪答題。

（2）組織者中途宕機。答題者在發送一個答案給組織者后，一定時間內未收到組織者的計票結果時，首先詢問查看組織者狀態，如果確認是組織者宕機且下一任組織者不是自己，就等待下一任組織者的廣播信息，準備下一次答題；如果自己是下一任組織者，累加期號后廣播自己成為組織者的消息，準備出題。

5.10 決賽問題

按照現實中的游戲規則，決賽是需要組織者這個固定角色參與的，但在前面去中心化設計并已去掉了這個固定的角色的情況下，可以通過另一種方法解決此事。首先對比兩個節點ID號i1和i2，如果i1＞i2，則Mid=i1，Lid=i2；如果i1＜i2，則Mid=i2，Lid=i1。再對比兩個節點的答案Lr(i1)和Lr(i2)，如果決賽兩節點的答案是相同的，即“11”或“00”，就判定Lid對應的那個節點當選；如果是不同的，即“01”或“10”，就判定Mid對應的那個節點當選，這樣依然能夠保證Leader選舉的隨機性和公正性，形式化后的計算公式如式（3）所示。

5.11 組織者核心算法偽代碼

6 實驗驗證

本實驗主要是在單臺計算機上，通過多個虛擬終端來仿真多臺計算機之間的通信過程，對比多數決和少數決選舉機制的選舉速度和安全性。采用C語言實現少數決選舉；通過修改的開源libPaxos實現多數決選舉，并設所有服務器均承擔proposer和acceptor兩種角色；實驗環境為Dell Precision移動工作站，Intel Core i9-8950HK，2.9 GHz，32 GB DDR4內存，操作系統為VMware Workstation虛擬機下的Ubuntu 16.4.04。

6.1 選舉成功率

模擬同一網段內的8臺集群服務器。通過分別執行1 000次多數決和少數決選舉，對比兩種選舉機制的規定時間內選舉成功次數[18]。圖3展示了在250 ms、500 ms、1 000 ms內，模擬集群服務器分別運行多數決和少數決選舉機制，成功選舉出Leader的次數。

Fig.3 Comparison of the number of successful elections within specified time圖3 規定時間內選舉成功次數對比

6.2 選舉安全性

模擬同一網段內的8臺和10臺集群服務器兩種場景。通過執行多數決和少數決選舉，對比兩種選舉機制的安全性。多數決時采用共同投票給P1的方式進行攻擊，少數決時采用本文4.1節描述的：全力保證P1和盡可能多的隊友進入下一輪的方式進行攻擊。

圖4是在受控節點分別為1,2,…,8的情況下，分別采用經典Paxos的多數決選舉機制和少數決選舉機制各進行20次Leader選舉，統計擬定對象P1的獲勝次數。圖5是在受控節點分別為1,2,…,10的情況下分別采用經典Paxos的多數決選舉機制和少數決選舉機制各進行20次Leader選舉，統計擬定對象P1的獲勝次數。

Fig.4 Comparison of election security of 8 cluster servers圖4 8臺集群服務器選舉安全性對比

Fig.5 Comparison of election security of 10 cluster servers圖5 10臺集群服務器選舉安全性對比

6.3 實驗結果分析

（1）多數決選舉機制和少數決選舉機制在成功選舉出Leader的所需時間基本一致。

（2）8臺集群服務器時分別使用兩種選舉機制發起絕對控制攻擊，少數決要比多數決多控制37.5%的節點才能確保攻擊成功，即少數決選舉安全性明顯高于多數決選舉。

（3）10臺集群服務器分別使用兩種選舉機制發起絕對控制攻擊，少數決要比多數決多控制30%的節點才能確保攻擊成功，即在表1中的低值時，少數決選舉安全性也遠高于多數決選舉。

（4）對比圖4、圖5兩種選舉機制的斜率，少數決選舉只有在控制節點數臨近絕對控制攻擊滿足條件時，才會對獲勝次數產生明顯影響；而多數決選舉在隨控制節點數增加的初始階段，就對獲勝次數產生明顯的影響。

7 結束語

本文通過理論分析和實驗證明，在分布式系統中采用少數決方式進行Leader節點選舉是完全可行的，且少數決選舉機制相比多數決選舉機制在降低控票攻擊風險方面有明顯的優勢。本文認為此種選舉機制具有很好的科學性和進一步的研究價值。下一步，將研究分析少數決選舉機制在其他領域的應用潛力。