【轉載】DPOS共識演算法 -- 缺失的白皮書

02-05

原文地址：
https://steemit.com/dpos/@dantheman/dpos-consensus-algorithm-this-missing-white-paper
DPOS共識演算法 -- 缺失的白皮書

這篇「缺失的白皮書」是對委託權益證明（DPOS）的分析，目的是為DPOS的工作原理及其魯棒性根源提供一個分析。 DPOS的早期描述可以在bitshares.org上找到；不過，那個描述還包含了許多不屬於實際共識過程的內容。

所有區塊鏈本質上都是一種由交易驅動的確定性狀態機。共識是商定確定性交易順序和過濾無效交易的過程。有許多不同的共識演算法都可以產生等效的交易排序，但DPOS已經通過在多個區塊鏈上經年累月的可靠運行證明自身是健壯、安全和有效的。

像所有共識演算法一樣，塊生產者可能導致的最大損害是審查。所有塊的有效性必須基於確定性的開源狀態機邏輯。

DPOS演算法概要

DPOS演算法分為兩部分：選擇一組塊生產者和調度生產。選舉過程確保利益相關方最終得到控制，因為當網路不能順利運行時，利益相關方的損失最大。選舉方法對實際運行中如何達成共識幾乎沒有影響，因此，本文將重點介紹如何在塊生產者被選擇之後達成共識。

為了幫助解釋這個演算法，我想假設3個塊生產者A，B和C。因為共識（的達成）需要2/3+1多數來解決所有情況，這個簡化的模型將假設生產者C是打破僵局的那個人。在現實世界中，將有21個或更多的塊生產者。像工作量證明一樣，一般規則是最長鏈勝出。任何時候當一個誠實的對等節點看到一個有效的更長鏈，它都會從當前分叉切換到更長的這條鏈。

我將舉例說明在大多數想得到的網路條件下DPOS如何運行。這些例子應該可以幫助您理解為什麼DPOS穩健且難以破壞。

正常操作

在正常操作模式下，塊生產者每3秒鐘輪流生成一個塊。假設沒有人錯過自己的輪次，那麼這將產生最長鏈。塊生產者在被調度輪次之外的任何時間段出塊都是無效的。

少數分叉

不超過節點總數三分之一的惡意或故障節點可能創建少數分叉。在這種情況下，少數分叉每9秒只能產生一個塊，而多數分叉每9秒可以產生兩個塊。這樣，誠實的2/3多數將永遠比少數（的鏈）更長。

離線少數的多重生產

（離線的）少數人可以試圖產生無限數量的分叉，但是他們的所有分叉都將比多數人的那條鏈短，因為少數人在出塊速度上註定比多數人來的更慢。

網路碎片化

網路完全有可能碎片化，導致沒有任何分叉擁有多數塊生成者。在這種情況下，最長的鏈將倒向最大的那個少數群體。當網路連通性恢復時，較小的少數群體會自然切換到最長的那條鏈，明確的共識將恢復。

有可能存在這樣三個分叉，其中兩個最長的分叉長度相同。在這種情況下，第3個（較小）分叉的塊生產者重新加入網路時會打破平局。塊生產者總數為奇數，因此不可能長時間保持平局。稍後我們還會講到生產者「洗牌」，它使得出塊順序隨機化，從而確保即使是生產者數目相同的兩個分叉也會以不同的步長增長，最終導致一個分叉超過另一個。

在線少數的多重生產

在這種場景下，少數節點B在其時間段內產生了兩個或更多可供選擇的塊。下一個計劃生產者（C）可以選擇基於B產生的任何一種方案繼續構建鏈條。一旦如此，這個選擇就成為最長的鏈，而所有選擇B1的節點都將切換分叉。少數不良生產者企圖廣播再多的替代塊也無關緊要，它們作為最長鏈的一部分永遠不會超過一輪。

最後不可逆塊

在網路碎片化的情況下，多個分叉都有可能持續不斷增長相當長的時間。長遠來看最長的鏈終將獲勝，但觀察者需要一種確切的手段來判定一個塊是否絕對處於增長最快的那條鏈。這可以通過觀察來自2/3+1多數塊生產者的確認來決定。

在下圖中，塊B已被C和A所確認，這代表了2/3+1多數確認，由此我們可以推斷沒有其它鏈會比這個更長 – 如果2/3的生產者是誠實的。

請注意，這個「規則」類似於比特幣的6塊確認「規則」。一些聰明人也許可以謀劃一系列事件使得兩個節點（應該是「交易」？）出現在不同的最後不可逆塊上。這種邊緣案例要求攻擊者能完全控制通信延遲，並且在幾分鐘內兩次--而不是一次--使用該控制。即便這真的發生了，那麼最長鏈（勝出）的長期規則仍然適用。我們估計這種攻擊的可能性足夠接近0，且經濟後果無關緊要，因此不足為慮。

生產者法定人數不足

在缺乏明晰的生產者法定人數這種不太可能的情況下，少數人還是可以繼續出塊。利益相關方可以在這些塊里包括更改投票的交易。這些投票可以選出一組新的生產者，並將出塊參與率恢復到100％。一旦如此，少數鏈將最終超過所有其他以低於100％參與率運行的鏈。

在此過程中，所有觀察者都會知道，在一條參與率超過67%的鏈形成之前，網路狀態是不定的。那些選擇在此條件下進行交易的人所冒的風險與選擇接受不到6個確認的人相似。他們知道存在這樣一些小的可能性，即：共識也許最終在一個不同的分叉上建立起來。在實踐中，這種情況比接受少於3個比特幣交易確認的塊要安全多了。

多數生產者舞弊

如果多數生產者變得腐敗，那麼他們可以產生無限數量的分叉，每個分叉都看起來以2/3多數確認向前走。這種情況下，最後不可逆塊演算法蛻變為最長鏈演算法。最長鏈就是為最大多數所批准的那條鏈，而這將由少數剩下的誠實節點決定。這種行為不會持續很長時間，因為利益相關方最終會投票替換生產者。

交易作為權益證明（TaPoS）

當用戶為一個交易簽名時，他們是在對區塊鏈狀態的一定假設下這樣做的。這個假設是基於他們對最近幾個塊的看法。如果最長鏈的共識發生改變，則潛在會使簽名者之前的假設失效。

就TaPoS而言，所有交易都包含最近一個塊的散列，如果該塊在鏈歷史中不存在則這些交易被認為是無效的。任何在孤兒分叉上給交易簽名的人，都會發現該交易無效且無法遷移到主分叉。

該過程的一個附帶作用是可以抵禦試圖產生替代鏈的長期攻擊。每個利益相關方在每次交易時都直接對區塊鏈做出確認。隨著時間推移，所有的塊都是由所有利益相關方確認過的，這在一條偽造鏈里是無法複製的。

確定性生產者洗牌

在上面所有例子中，我們展示的都是塊生產者按循環調度出塊。實際上，每出N個塊（N是生產者數量），塊生產者集合都會洗牌一次。這種隨機性確保塊生成者B不會總是忽略塊生成者A，每當形成多個擁有相同數量生產者的分叉時，平局最終都會被打破。

結論

在每一個我們能想到的自然網路分裂的情況下，委託權益證明都是強健的，甚至在面對相當數量生產者舞弊的情形時也是安全的。不像其它共識演算法，當大多數生產者不合格時，DPOS還是可以繼續工作。在此過程中，社區可以投票替換掉不合格的生產者，直到恢復100％參與率。我還不知道有任何其它演算法可以在如此高強度和變化多端的失敗條件下依然保持強健。

說到底，DPOS引人注目的安全性來自於其選擇塊生產者和驗證節點質量的演算法。運用贊成投票的過程可以確保一個人即使擁有50％的有效投票權也不能獨自挑選哪怕一個生產者。DPOS旨在優化擁有強壯網路連接的誠實節點100％參與（共識過程）的名義條件。這使得DPOS有能力在平均只有1.5秒的時間內以99.9％的確定性確認交易，同時以優雅和可檢測的方式降級 – 從降級中恢復正常也不過是小事一樁。

其它共識演算法以網路條件差的不誠實節點為名義條件展開設計，這樣設計的最終結果就是性能更差、延遲更高、通信開銷高的網路，而且這個網路在33％節點失效的情況下會完全停擺。

在BitShares成功運行三年以及在Steem運行一年期間，我們經歷了各種各樣的網路條件和軟體錯誤。DPOS成功穿行於其間，在處理了比任何其它區塊鏈更多交易的同時持續達成共識，展現了非凡的能力。