基于時間排序的監督共識算法

牟 平， 梁鑒如

(上海工程技術大學，上海 201620)

0 引 言

Satoshi Nakamoto在2008年提出了bitcoin[1]，描述了一種全新的電子貨幣及其算法。它的不可篡改、多方維護的特性，引起了各個領域的廣泛關注，其重要底層技術之一的區塊鏈也吸引了諸多研究者關注。

在傳統的數據系統中，賬本上的一系列信息往往由一個中心服務器進行記錄，這種設計特性，節省了使用成本、保證了數據的強一致性、規避了分區容錯性但卻使得可用性風險極高[2]。在數據儲存階段，采用多備份容災，足以抵御自然條件下的偶發災害。相較而言，惡意的節點對傳統分布式數據系統造成的問題要嚴重得多，典型的有DDOS攻擊，冒充客戶端提交虛假信息，攻擊中心服務器篡改用戶提交的信息，篡改歷史信息等[3-4]。這對新型的數據系統分布式系統帶來了以下挑戰：在一個無中心，弱信任的分布式系統中，如何讓各個節點在指定時間內達成共識[5]。

所謂共識，簡單來說就是分布式系統中節點對某個數值或狀態的承認[6]。Lynch基于如今的計算機技術和網絡技術的結構提出了CAP理論[7]，認為分布式系統不可能同時滿足一致性(consistency)、可用性(availability)和分區容錯性(partition tolerance)這三個基本需求，最多只能同時滿足其中兩項。業界在分布式的實際使用中，對CAP特性進行進一步權衡，由Dan Pritchett總結為主要特征為基本可用(basically available)、軟狀態(soft state)和最終一致性(eventually consistent)的BASE原理。Gray在1978提出了2PC(concurrency control and recovery in database systems)通過兩階段進行事務提交，但如果從節點失效則會發生事務阻塞，使系統崩潰。為增強系統健壯性，Skeen在1981年提出(3PC)通過三階段進行事務提交，降低了數據不一致的概率。Lamport在1998年提出的Paxos[8]是第一個獲得廣泛認可的基于消息傳遞的一致性算法。Diego Ongaro和John Ousterhout通過問題拆分、狀態空間降維等方式對Paxos進行簡化，提出了Raft算法。Barbara Liskov等在1999年提出了實用拜占庭容錯算法[9]，解決了原始拜占庭不能容錯的問題，并且將算法的復雜度由指數級降低到多項式級。擴展了系統的可用性。Ramakrishna Kotla在2007年提出了基于zyzzyva協議[10]的SBFT算法[11]，使得消息事件復雜度由PBFT的O(n2)降為O(n)，改良后效果非常顯著，極大地提高了共識效率。但這些算法為了保證數據的一致性，一般選擇對客戶端發送的消息由一個主節點進行排序、打包，再分發到各個副本節點進行校驗，但是主節點的更換方式采取的是輪巡式，敵手非常容易猜到預備的主節點，這可能導致敵手有針對性地攻擊預備節點，或者故意癱瘓當前節點，迫使切換到已控制的節點中完成攻擊。因此，應當避免系統通過單一主節點接受輸入消息，防止主節點被劫持給系統帶來風險。同時應當減少同步數據中的計算開支。文中在SBFT共識算法的基礎上引入了計入時間戳排序的監督共識算法：

(1)引入多節點對客戶端消息排序打包，防止單主節點篡改、瞞報客戶端的消息。

(2)引入消息的時間水位和延時排隊概念，將時間戳作為消息排序的依據。設置消息緩沖，解決網絡延遲帶來的各節點消息不同步。

(3)增加節點間消息對比方式，對于不同的業務邏輯使用不同的對比邏輯，增加使用彈性。

1 主節點的選擇方法

1.1 PoW中主節點的選擇方法

比特幣的PoW共識算法[1]中每個節點會將收到的交易數據(記為m)、前一個區塊的merkle值、時間戳(記為t)以及隨機數(nonce)等結合進行一次哈希運算，需要滿足得到的哈希結果小于某一目標數值(target)，因此每個節點會不斷更改隨機數進行嘗試，直到得到滿足條件的隨機數。然后該節點會將結果向整個區塊鏈網絡廣播，其他節點驗證屬實后就會接納此節點生成的區塊，放到自己的鏈條上，得到一條“最長鏈”。

Hash(block,nonce)

PoW機制是最早和理論上最安全的公有鏈算法，參與競爭消息排序的節點越多，系統會自動調整target的大小，控制難度，使得出塊的速度大體穩定在一定區間，這使得篡改區塊鏈的內容越困難，而且難以預測下輪的主節點避免了數據打包時可能受到的干擾。但是PoW的缺陷也很明顯，巨量算力的消耗造成了資源和設備的浪費，而且根據調查顯示90%的算力掌握在5家“礦場”中，這無疑違背了分布的原則。而且長達10分鐘到1小時的確認時間以及7tx/s的交易速度使得應用場景非常受限[12]。

1.2 PoS中主節點的選擇方法

2011年7月Quantum Mechanic提出了權益證明PoS共識算法，提出將幣齡引入以減少節點尋找隨機數的難度。幣齡指的是節點擁有的幣乘以幣剩余的時間。PoS算法原理如下：

其中，target功能與PoW中的目標數一致，用來控制出塊速度，而擁有更多，時間更長的余額的人則可以以較低的代價計算出nonce從而獲得記賬權。但是這個算法對于幣齡沒有限制，于是有用戶開始囤幣升值，以期獲得在系統內的更多投票權。因此Peercoin修改了幣齡的計算方法由線性增長改為了衰減增長和控制coinage的最大值，使得囤幣者的效用增長不再明顯。

1.3 PBFT中主節點的選擇方法

2016年，IBM提出了基于PBFT[9]中的共識協議hyperledger，采用了授權式共識，在一個已經被驗證過的節點群中，節點間鏈接配置被稱為視圖(view)，在一個視圖中，一個節點是主節點，其他節點是備份，當需要視圖切換時(view-change)通過計算P=Vmod |R|選擇下一個主節點，其中V是視圖編號，R是參與共識的節點數。主節點的更換通常由以下情況觸發：主節點宕機超時；主節點是惡意節點，傳播惡意消息，被過半節點發現異常；設置的階段定時器超時。對于主節點P，由于在更替中視圖遵循是V,V+1,V+2原則使得攻擊者容易推測下一個可能的主節點，進而攻擊控制，而且如果主節點擅自增刪，修改客戶端的消息，其他節點未能發現異常，這對用戶的安全性無疑帶來極大危險。PBFT共識算法流程如圖1所示。

圖1 PBFT共識算法流程

1.4 DPoS中主節點的選擇方法

2013年8月，比特股(bitshare)則采用授權股份證明算法(delegated proof-of-stake，DPoS)即系統中每個節點可以將其持有的股份權益作為選票授予一個證人，獲得票數最多且愿意成為證人的前N個節點將進入“證人名單”，按照既定的時間表輪流對交易進行打包結算并且簽署(即生產)新區塊。每經過一個維護間隔(maintenance interval)時間(1天)，選票就會被統計一次，屆時活躍證人的名單也會更新一次。然后將證人名單洗牌(shuffle)，并且每個證人節點會輪流地在固定的預先計劃好的2秒內生產一個區塊。當所有證人輪完之后，他們又將被洗牌。

1.5 總 結

綜上來看，主節點的選擇一般出自以下幾種方式：算力競爭(PoW)；資產所有權競爭(PoS)；輪巡(PBFT)；投票+輪巡(DPoS)。在眾多改進算法中，除了PoW算法，一般是通過增加隨機選擇的特性防止主節點，如果主節點被腐蝕，或者被惡意控制，在算法中一般只考慮對節點的不統一欺騙即主節點對P1發出A→B卻對P2,P3發出A→C的交易命令。但是對于主節點篡改交易信息或憑空杜撰統一的消息記錄，即對原本A→B的交易信息被篡改為A→C，統一發布給P1,P2,P3，在這種情況下，現有的共識機制無法識別攔截。Hyperledge等聯盟鏈一般依托線下的強身份認證使得主節點一旦作惡將被追溯，Carboni引入了追溯機制使得作惡節點會被懲罰[13]，但考慮到一般攻擊方并不會是主節點的現實所有者，更可能是被植入后門的節點，造成的損失將很難挽回。因此一種對性能要求不大并能監視異常主節點行為的算法，對提高有明確主節點主導的區塊鏈算法安全性的提升很有必要。

2 改進方案

2.1 SBFT共識流程結構

SBFT算法分為6個階段，分別是請求、預準備、投票簽名、完全共識證明、簽名狀態、完全執行證明，流程如圖2所示。

(1)請求階段：客戶端向主節點發送消息m。

(2)預準備階段：主節點收到客戶端發來的消息m后，為其分配編號，并將收到的消息按編號打包成塊，發送給其他節點。

(3)投票簽名階段：各節點對收到消息進行核驗，確認后使用門限簽名(BLS)，將簽名消息發給收集節點C。

(4)完全共識證明階段：每一個收集節點會收集簽名，然后為該塊創造一個完全共識證明，將其發送給所有節點，一旦節點接收到完全共識消息，就會對這個塊進行共識同步，然后執行塊內記錄的交易信息。

(5)簽名狀態階段：當從節點執行完塊中所有交易后，開始創造一個完全執行證明，并進行門限簽名，然后發送消息給收集節點E。

(6)完全執行證明階段：收集節點E收集簽名，達到門限要求后，為該塊創建一個完全執行完成證明，并告訴所有節點和客戶端當前狀態是持久的，并且交易操作已經被執行。

2.2 共識流程優化

為解決共識算法過度依賴主節點的問題，引入監督節點(supervisor)對主節點的排序結果進行監督校準。流程如圖3所示。如果主節點篡改客戶端發來的消息，除非能同時控制監督節點否則必然會造成消息摘要的不一致，從而發現主節點異常，沒有必要通過等待收集f+1個異常證明來提出view-change。對于某些安全要求不高的場合，還可以采用采納多數的方式，即在一個主節點兩個監督節點的情況下，當主節點和一個監督節點的摘要不同，但與另一個監督節點相同時，可以認為是系統誤差造成，繼續執行后續步驟。

圖3 優化后的共識流程

優化后的流程具體如圖4所示。

圖4 優化后的SBFT共識算法

(1)請求階段：客戶端提交消息<”request”,m,c,t>sig給主節點和監督節點，m表示客戶端向區塊鏈請求寫入的交易數據，c表示客戶端編號，t表示時間戳，一般來說由本地時鐘控制，其精度應當滿足系統要求的Δλ。客戶端發出的時間戳是嚴格單調遞增的。sig是客戶端對這個消息的簽名，用以證明消息確實是此客戶端發出的。消息發送成功后，客戶端啟動計時器，計算消息是否發送超時。

(2)預準備階段：主節點接受到客戶端發來的請求后，通過時間排序為消息m分配編號，滿足打包條件后，將消息按序號打包成塊(blockp)，并生成區塊的摘要hash(blockp)以及交易列表{cp,hash(m)p,tp}，交易列表中存放了區塊中所有提交消息的客戶端編號和對應的提交時間戳。將sig發送給其他節點；監督節點接受到客戶端發來的請求后，按時間戳遞增順序為消息m分配編號，滿足打包條件后，將消息按序號打包成塊(blocks)并生成區塊的摘要hash(ms)，以及交易列表{cs,ts}，將sig發送給其他節點。

(3)投票簽名階段：一般節點對收到消息進行核驗，確認后使用門限簽名(BLS)，將簽名消息發給收集節點C。主節點和監督節點將收到的其他節點的摘要與自己生成的摘要比較，生成比較消息。將比較消息發送給收集節點。

(4)完全共識證明階段：收集節點C對比較消息驗證，不通過則進入視圖轉換，通過則繼續收集簽名，然后為該塊創造一個full commit proof消息，發送給所有節點，一旦從節點接收到full commit，就會對這個塊進行共識同步，然后執行塊內記錄的交易信息。

(5)與原方案相同。

(6)與原方案相同。

3 特性分析

3．1 基于時間排序

主節點和監督節點每Δt進行一次打包操作，抽取,構造形如以t為序號的消息矩陣。

受制于現實條件制約，節點廣播的信息不會同時抵達其他節點。可能在某些節點出現如下情況。

這時需要通過重新排序實現順序，排序后的消息矩陣成為block，如果某條消息因為延時，一部分節點將此消息打包入blocki，但另一部分節點中將其打包入blocki+1，將使得消息無法排序。因此，引入了時間水位[h,H]和延時排隊的概念。低水位h等于上一個打包完成區塊的最大時間戳編號，高水位為tH=th+Δt，其中Δt是指定的數值，等于區塊打包消息的時間間隔，其中tH+Δλ

圖5 消息隊列

3.2 消息比較

在投票階段各節點將自己的區塊摘要同其他節點的摘要進行比較[14]，相同為1，不同為0。若摘要全部相同則生成一條(1,1,1)消息，若主節點摘要為A，監督節點1摘要為B，監督節點2摘要為A,則主節點生成(1,0,1)，監督節點1生成(0,1,0)，監督節點2生成(1,0,1)，若主節點摘要為B，監督節點1摘要為A，監督節點2摘要為A,則主節點生成(1,0,0)，監督節點1生成(0,1,1)，監督節點2生成(0,1,1)。對不同的任務場景可以使用不同的錯誤容忍策略，對高要求場景可以使用嚴格模式必須(1,1,1)才能通過審查，對于寬容度較高的任務類型可以接受(1,0,1)或者(1,1,0)但是拒絕(1,0,0)。

4 仿真結果分析

改進方案通過引入了時間水位[h,H]和延時排隊以及消息比較的概念，實現了對主節點的監督。通過引入不同的監督節點數，增加攻擊主節點操縱數據的成本。如果采用嚴格模式，則使得攻擊成功的難度指數上升。如果采用寬容模式,敵手設定為n=2f+1，有總量為n節點，Mp個敵手節點，當選x-1個節點作為監督節點，則被敵手攻擊成功的概率Pr為：

在n=100，Mp=6,x=9的條件下，敵手攻擊成功的概率為2.97e-10，如果系統打包出塊的速度是每分鐘一塊，每天運行20小時，則平均2 805年才會出現一次攻擊成功。圖6是在n=100的情況下以log10計的攻擊成功概率圖。以攻擊成功的概率小于e-8為通過標準(千萬分之一)，可以看到敵手攻擊成功的概率隨著敵手控制點的增加而增加，而且當敵手控制節點數目不變時增加背書節點數目可以使攻擊成功概率呈指數下降，即使敵手控制了相對較多的節點Mp=10；當x=13時攻擊成功概率仍然僅為2.001e-09，充分體現了安全性。在實際使用中需要根據需求設置n和x，以滿足不同的場景需求和不同強度的安全需要。

圖6 敵手攻擊成功概率圖(以log10記)

在有100個節點的典型環境中，敵手數目為1～5時，不同監督節點數下攻擊成功的概率細節如表1所示。

表1 敵手攻擊成功概率

通過比較可以看到，引入監督節點后攻擊成功的概率大大降低，效果明顯。

5 結束語

主節點的極高權限使得惡意攻擊者一旦得手所得收益極大，這也是各個算法極力避免主節點提前計算出的原因，但是系統為了維持數據一致又必須由單節點進行記賬操作，因此引入一種帶有主節點監督的共識算法被視為效率與安全的一中折中方案。文中針對共識算法中存在的對主節點消息過度依賴的問題，提出一種基于時間排序的監督共識方案。通過引入監督節點，在系統內部利用現有資源對主節點的消息進行校準，以較小代價顯著提高主節點傳播消息的造假成本。通過消息的排隊解決多節點記錄時的異步網絡帶來的消息傳遞延遲。仿真結果表明，基于時間排序的監督共識可以很好地在有部分惡意節點的網絡中以較低的代價顯著增加主節點作弊的成本，有效提升了系統的安全性，并且可以通過設置不同的共識模式、引入不同的監督節點調節系統的抗攻擊能力。對有彈性安全需求的系統有較大應用潛力。