原文：https://steemit.com/dpos/@dantheman/dpos-consensus-algorithm-this-missing-white-paper
網(wǎng)絡(luò)上已經(jīng)有了好幾個(gè)版本的譯文，可能是原文寫的沒那么“平易近人”，這些譯文我都看得不太懂 :)
這篇“缺失的白皮書”是對(duì)委托權(quán)益證明(Delegated Proof of Stake, DPOS)的分析，旨在分析 DPOS 的工作原理及其魯棒性（robust）的根源。DPOS 的早期描述可以在 bitshares.org 找到；不過，那個(gè)描述里包含了很多與實(shí)際共識(shí)不大相關(guān)的內(nèi)容。
本質(zhì)上，所有區(qū)塊鏈都是一種由交易驅(qū)動(dòng)的確定性狀態(tài)機(jī)。而共識(shí)，是就確定性交易順序達(dá)成一致并過濾無效交易的過程。有各種不同的共識(shí)算法都可以產(chǎn)生等效的交易排序，但通過在多個(gè)區(qū)塊鏈上長年累月的可靠運(yùn)行，DPOS 已經(jīng)證明其具備健壯性、安全性和有效性。
像所有共識(shí)算法一樣，塊生產(chǎn)者(俗話就是出塊人)可能導(dǎo)致的最大損害是審查（censorship）。所有塊的有效性必須基于確定性的開源狀態(tài)機(jī)邏輯。
DPOS 算法概要
DPOS 算法分為兩部分：
- 選擇一組塊生產(chǎn)者
- 調(diào)度生產(chǎn)
選擇出塊人的過程，確保了利益相關(guān)方(stakeholder，通俗點(diǎn)也可以說是持幣人)最終能有控制權(quán)，因?yàn)楫?dāng)網(wǎng)絡(luò)不能順利運(yùn)行時(shí)，利益相關(guān)方的損失最大。就實(shí)際運(yùn)行中如何達(dá)成共識(shí)而言，如何選擇出塊人其實(shí)幾乎沒有多大影響，因此，本文將重點(diǎn)介紹在選好出塊人之后，如何達(dá)成共識(shí)。
為了幫助解釋這個(gè)算法，我將假設(shè) 3 個(gè)塊生產(chǎn)者 A，B 和 C。因?yàn)樾枰_(dá)成 2/3+1 的多數(shù)共識(shí)來解決所有情況，這個(gè)簡化的模型將假設(shè)生產(chǎn)者 C 是打破僵局的那個(gè)人（也就是 2/3+1 里面的 1，勝負(fù)手）。在現(xiàn)實(shí)世界中，將有 21 個(gè)或更多的出塊人。像工作量證明一樣，一般規(guī)則是最長鏈勝出。任何時(shí)候，當(dāng)一個(gè)誠實(shí)的節(jié)點(diǎn)看到一個(gè)有效的更長鏈，它都會(huì)從當(dāng)前鏈切換到更長的這條鏈。
我將舉例說明在大多數(shù)能夠想到的網(wǎng)絡(luò)條件下，DPOS 是如何運(yùn)行的。這些例子應(yīng)該可以幫助您理解為什么 DPOS 穩(wěn)健且難以破壞。
正常操作(Normal Operation)
在正常操作下，出塊人輪流每 3 秒鐘出一個(gè)塊。假設(shè)沒有人錯(cuò)過自己的輪次，那么將會(huì)產(chǎn)生最長鏈。出塊人在被調(diào)度輪次之外的任何時(shí)間段出塊都是無效的。也就是說，如果沒有輪到自己出塊，出的任何塊都是無效的。
少數(shù)分叉(Minority Fork)
如果出現(xiàn)不超過節(jié)點(diǎn)總數(shù)三分之一的惡意或故障節(jié)點(diǎn)，那么可能會(huì)產(chǎn)生少數(shù)分叉（minority fork, 或者可以說是小群體分叉）。在這種情況下，少數(shù)分叉每 9 秒只能產(chǎn)生一個(gè)塊，而多數(shù)分叉每 9 秒可以產(chǎn)生兩個(gè)塊。這樣，誠實(shí)的 2/3 多數(shù)將永遠(yuǎn)比少數(shù)（的鏈）更長。
離散少數(shù)的雙重生產(chǎn)(Double Production by Disconnected Minority)
如果有很多“各自為政”的小群體，那么他們可以試圖產(chǎn)生無數(shù)的分叉，但是因?yàn)樯贁?shù)人在出塊速度上注定比多數(shù)人更慢，所以所有小群體的分叉都會(huì)比多數(shù)人的那條鏈短。
網(wǎng)絡(luò)碎片化(Network Fragmentation)
網(wǎng)絡(luò)完全有可能碎片化，從而導(dǎo)致沒有任何分叉擁有數(shù)量上占多數(shù)的出塊人。在這種情況下，最長鏈將倒向最大的那個(gè)小群體（“矮子里面挑高個(gè)”）。當(dāng)網(wǎng)絡(luò)連通性恢復(fù)時(shí)，其他較小的小群體會(huì)自然切換到最長的那條鏈（也就是最大的小群體那條鏈），繼而恢復(fù)明確的共識(shí)。
有可能存在這樣三個(gè)分叉，其中兩個(gè)較長的分叉長度相同。在這種情況下，當(dāng)?shù)?3 個(gè)（較?。┓植娴某鰤K人重新加入網(wǎng)絡(luò)時(shí)，就會(huì)打破平局。出塊人總數(shù)為奇數(shù)，因此不可能長時(shí)間保持平局。稍后我們還會(huì)談到出塊人“混洗（shuffle）”，它使得出塊順序隨機(jī)化，從而確保即使是出塊人數(shù)目相同的兩個(gè)分叉，也會(huì)以不同的速度增長，最終導(dǎo)致一個(gè)分叉勝出。
在線少數(shù)的雙重生產(chǎn)(Double Production by Connected Minority)
在這種場(chǎng)景下，少數(shù)節(jié)點(diǎn) B 在其時(shí)間段內(nèi)產(chǎn)生了兩個(gè)或更多的競爭塊（alternative block）。下一個(gè)出塊人（C）可以選擇基于 B 產(chǎn)生的任意一個(gè)塊繼續(xù)往前走。如此一來，C 的這條鏈就成為最長鏈，而所有選擇 B1 的節(jié)點(diǎn)都將切換到最長鏈。即使少數(shù)不良出塊人試圖廣播再多的競爭塊也無關(guān)緊要，因?yàn)樗鼈冏鳛樽铋L鏈的一部分永遠(yuǎn)不會(huì)超過一輪(round，所有出塊人挨個(gè)出塊，轉(zhuǎn)完一圈就是一輪)。
最后不可逆塊(Last Irreversible Block)
在網(wǎng)絡(luò)碎片化的情況下，在相當(dāng)長的一段時(shí)間內(nèi)，很有可能有多個(gè)分叉都持續(xù)不斷地增長。長遠(yuǎn)來看，最長的鏈終將獲勝，但觀察者（observer）需要一種確切的手段，以此來確定一個(gè)塊是否在增長最快的鏈上。這可以通過看是否有 2/3+1 多數(shù)出塊人的確認(rèn)來確定。
在下圖中，塊 B 已被 C 和 A 所確認(rèn)，即表示有 2/3+1 多數(shù)確認(rèn)，由此我們可以推斷沒有其它鏈會(huì)比這條鏈更長 – 如果 2/3 的出塊人是誠實(shí)的。
請(qǐng)注意，這個(gè)“規(guī)則”類似于比特幣的 6 個(gè)塊確認(rèn)。一些“聰明”人也許可以謀劃一系列事件，使得兩個(gè)節(jié)點(diǎn)的最后不可逆塊不同。這種極端的例子要求攻擊者能完全控制通信延遲，并且在幾分鐘內(nèi)控制兩次--而不僅僅是一次。即便這真的發(fā)生了，最長鏈勝出的長期規(guī)則仍然適用。我們認(rèn)為這種攻擊的可能性足夠接近 0，且經(jīng)濟(jì)后果無關(guān)緊要，因此不足為慮。
出塊人不足(Lack of Quorum of Producers)
有一種不太可能會(huì)出現(xiàn)的情況，即沒有明確到底有多少個(gè)出塊人，在這種情況下，少數(shù)人還是可以繼續(xù)出塊。在這些塊里，利益相關(guān)方可以包含更改投票的交易。這些投票可以選出一組新的出塊人，并將出塊參與率恢復(fù)到 100％。一旦如此，這條小群體的鏈最終將超過所有其他出塊參與率低于 100％ 的鏈。
在此過程中，所有觀察者都會(huì)知道，在出現(xiàn)一條參與率超過 67% 的鏈之前，網(wǎng)絡(luò)都處于不穩(wěn)定的狀態(tài)。如果有人選擇在此條件下進(jìn)行交易，那么他將承受與接受不到 6 個(gè)確認(rèn)類似的風(fēng)險(xiǎn)。他們也知道存在這樣的小概率事件，即最終的共識(shí)（或者說最長鏈）出現(xiàn)在另一個(gè)不同的分叉上。在實(shí)際操作中，這種情況仍然要比接受少于 3 個(gè)比特幣確認(rèn)要安全的多。
多數(shù)出塊人出現(xiàn)問題(Corruption of Majority of Producers)
如果多數(shù)出塊人出現(xiàn)問題，那么他們可能產(chǎn)生無限的分叉，每個(gè)分叉都看起來以 2/3 多數(shù)確認(rèn)向前推進(jìn)。這種情況下，最后不可逆塊算法蛻變?yōu)樽铋L鏈算法。最長鏈就是為最多人認(rèn)同的鏈，而這條鏈實(shí)際將由少數(shù)剩下的誠實(shí)節(jié)點(diǎn)決定。這種行為不會(huì)持續(xù)很長時(shí)間，因?yàn)槔嫦嚓P(guān)方最終會(huì)投票替換掉這些出塊人。
交易權(quán)益證明（Transactions as Proof of Stake, TaPoS）
用戶為一個(gè)交易簽名，是基于對(duì)區(qū)塊鏈狀態(tài)的一個(gè)假設(shè)，而這個(gè)假設(shè)又基于他們對(duì)最近幾個(gè)塊的“認(rèn)識(shí)”（perception）。如果最長鏈的共識(shí)發(fā)生改變，則很可能會(huì)使簽名者之前簽名時(shí)所依據(jù)的假設(shè)失效。
就 TaPoS 而言，所有交易都包含最近一個(gè)塊的哈希，如果該塊在區(qū)塊鏈中不存在，那么認(rèn)為這些交易是無效的。任何在孤兒分叉(orphaned fork)上給交易簽名的人，最終都會(huì)發(fā)現(xiàn)該交易無效，且無法遷移到主分叉。
這個(gè)過程有個(gè)附帶的好處，它可以抵御試圖產(chǎn)生替代鏈的長程攻擊（long-range attack）。每次交易時(shí)，利益相關(guān)方都直接對(duì)區(qū)塊鏈做出確認(rèn)。隨著時(shí)間的推移，所有的塊都是由所有利益相關(guān)方確認(rèn)過的，這在一條偽造的鏈（forged chain）所做不到的。
確定性出塊人混洗(Deterministic Producer Shuffling)
在上面我們所展示的所有案例中，出塊人按循環(huán)調(diào)度出塊。實(shí)際上，每出 N 個(gè)塊（N 是出塊人數(shù)量），出塊人集合都會(huì)進(jìn)行一次混洗。這種隨機(jī)性確保了出塊人 B 不會(huì)總是忽略出塊人 A，并且當(dāng)出現(xiàn)多個(gè)數(shù)量出塊人相同的分叉時(shí)，最終會(huì)有一個(gè)分叉勝出。
結(jié)論
在每一個(gè)想得到的自然網(wǎng)絡(luò)破壞下，DPOS 都是健壯的，甚至在面對(duì)大部分出塊人作弊時(shí)，也是安全的。不像其它共識(shí)算法，當(dāng)大多數(shù)出塊人出現(xiàn)問題時(shí)，DPOS 仍然可以繼續(xù)工作。在此過程中，社區(qū)可以投票替換掉不合格的出塊人，直到恢復(fù) 100％ 參與率。在如此高強(qiáng)度和變化多端的故障條件下，我還不知道有任何其它算法也可以依然保持如此健壯。
DPOS 之所以能有這么高的安全性，歸根結(jié)底來自于其選擇出塊人和驗(yàn)證節(jié)點(diǎn)質(zhì)量的算法。通過贊成投票制（approval voting），可以確保即使一個(gè)人擁有 50％ 的有效投票權(quán)，也不能獨(dú)自選擇一個(gè)出塊人。DPOS 的設(shè)計(jì)初衷是在良好的網(wǎng)絡(luò)連接，誠實(shí)節(jié)點(diǎn) 100％ 參與共識(shí)的情況下優(yōu)化性能，這使得 DPOS 有能力在平均只有 1.5 秒的時(shí)間內(nèi)以 99.9％ 的確定性確認(rèn)交易，同時(shí)能夠以一種優(yōu)雅和可檢測(cè)的方式降級(jí) – 降級(jí)也不是什么大事。
其他共識(shí)算法的設(shè)計(jì)初衷是，節(jié)點(diǎn)不誠實(shí)且網(wǎng)絡(luò)條件惡劣。這種設(shè)計(jì)的最終結(jié)果就是，網(wǎng)絡(luò)的性能更差，延遲更高，更新開銷大，并且在 33% 節(jié)點(diǎn)出現(xiàn)問題的情況下就會(huì)徹底停止正常運(yùn)轉(zhuǎn)。
在 BitShares 成功運(yùn)行三年，Steem 運(yùn)行一年期間，我們經(jīng)歷了各種各樣的網(wǎng)絡(luò)條件和軟件錯(cuò)誤。對(duì)于各種狀況，DPOS 都成功地得以應(yīng)對(duì)，并且證明了在維護(hù)共識(shí)的同時(shí)，處理了比任何其它區(qū)塊鏈更多的交易。
