共識算法作為區(qū)塊鏈的基石之一，快速和不可逆是我們重點關注的目標。除此之外，為了更好地建設公鏈生態(tài)，我們認為公平性同樣重要，如果大資本可以輕松占據(jù)公鏈中區(qū)塊共識的話語權，那么會有很多公鏈上的開發(fā)者和用戶的利益無端受損，一個不能保障公鏈建設者利益的生態(tài)，很難沉淀出價值深度，和星云鏈設計原則相違背。所以我們在設計共識算法時，在優(yōu)先保證快速和不可逆的情況下，將盡可能追求公平性，維護公鏈建設者的利益。
常用共識算法的缺陷
我們試圖在較為常用的共識算法中找到符合我們設計目標的選擇，但是這些算法和我們的目標多少都有些差距。
PoW （Proof of Work） 工作量證明共識算法為零和博弈，采用競爭性哈希計算來確定記賬人，導致了整個生態(tài)每次出塊時都有大量電能在競爭中被無端消耗，挖礦成本高，而且速度受限。如果把公鏈參與者作為整體來看，隨著參與挖礦的節(jié)點增加，每個節(jié)點獲得記賬權的概率將會減小，那么 PoW 協(xié)議下生態(tài)維持平穩(wěn)出塊的成本將會持續(xù)升高。不斷增加挖礦難度的 Bitcoin 早晚需要?臨礦機收益入不敷出的情形，而Ethereum 則早已在考慮使用新的 PoS 共識算法 Casper來逐步取代現(xiàn)階段的 PoW 共識 。可見，從挖礦速度和經(jīng)濟成本?度，PoW 都不利于公鏈生態(tài)的長期快速發(fā)展，和我們“快速”的目標不相符。
PoS （Proof of Stake） 股權證明共識算法試圖采用資產(chǎn)的多寡來取代算力的作用，按照幣齡或者押金數(shù)額來分配獲得記賬權的概率，現(xiàn)階段 Peercoin 和 Ethereum 的 Casper 協(xié)議都采用了 PoS 共識算法。這種算法解決了 PoW 高能耗的弊端，但很直觀地放大了資本對記賬權概率分配的影響，相較于 PoW，在PoS 下大資本更容易占據(jù)生態(tài)的話語權，形成大集團壟斷，可能會對生態(tài)的建設者的利益造成損害，不利于公鏈生態(tài)的價值沉淀，同樣和我們“公平性”的目標不相符。
PoI （Proof of Importance） 重要度證明共識算法最早由 Nem 提出，不同于 PoS，PoI 中引入了賬戶重要程度的概念，使用賬戶重要性評分來分配記賬權的概率。這種算法解決了 PoW 的高能耗弊端，減緩了 PoS 的資本壟斷危機，但暴露了 nothing-at-stake 的問題，作弊者逆轉一個區(qū)塊的成本被大大降低，和我們“不可逆”的目標不相符。
綜上，鑒于常用共識算法和我們目標存在差距，我們提出了基于賬戶貢獻度的 PoD （Proof of Devotion）算法，將評估賬戶綜合影響力的 PoI 和具有嚴格經(jīng)濟懲罰的 PoS 相融合，利用 PoS 強化 PoI 的不可逆性，使用 PoI 反向遏制了 PoS 的壟斷性，以此為生態(tài)自由快速發(fā)展助力。
PoD 算法設計
1. 新區(qū)塊產(chǎn)生
類似 PoI 共識算法選取重要性高的賬戶，PoD 將選取生態(tài)中貢獻度較高的賬戶，不同之處在于，PoD賦予選取出來的賬戶平等概率的記賬權來參與產(chǎn)生新區(qū)塊 （block），防?概率傾斜衍生壟斷。
在選擇貢獻度較高的賬戶時，我們使用了星云鏈原生的 NR 普適價值尺度評估。在 NR 的算法設計中，著重考慮了賬戶的流動性和傳播性，我們認為滿足這些性質(zhì)的賬戶對生態(tài)建設貢獻度較高。所以在 PoD 中，將選取 NR 排名 Top N 的賬戶，這些賬戶自愿繳納一定數(shù)量的 Nas 作為押金后則有資格成為新區(qū)塊的驗證者 （validator），參與記賬。
在給定驗證者集合 （validators set） 之后，PoD 算法通過偽隨機數(shù)來決定驗證者集合中誰是新的區(qū)塊的提議者 （proposer），提議者產(chǎn)生新區(qū)塊。驗證者集合不是固定不變的，有資格的賬戶可以選擇加入或者退出驗證者集合，而隨著周期性 NR 的變化，有資格的賬戶也會不一樣。所以我們在 PoD 設計了驗證者集合動態(tài)變化機制，來實現(xiàn)驗證者集合的更迭。
2. 驗證者集合更迭
驗證者集合的更迭就如朝代變更一樣，于是我們將驗證者集合按照朝代 （dynasty） 做劃分，一個朝代內(nèi)驗證者集合不會發(fā)生變化。一個朝代不能更迭地過快，至少要保持一段時間不做變更，因此我們將每 X 個區(qū)塊定義為一個 Epoch，在同一個 Epoch 中朝代不會發(fā)生變化。所以朝代的變更只會發(fā)生在 Epoch 交接時，在此時將會考察上一個 Epoch 的第一個區(qū)塊，如果此區(qū)塊到達了 finality 狀態(tài)，那么當前 Epoch 進入下一個朝代 D1，否則延續(xù)上一個朝代 D0 不變，如圖13所示。
由于網(wǎng)絡延遲，各個節(jié)點可能在朝代更迭時，看到的區(qū)塊 G 是否 finality 的狀態(tài)不一致，所以參考Casper 的動態(tài)驗證集策略，要求每一個朝代的共識過程將由當前朝代和上一個朝代的驗證者集合共同完成。因此在任意一個朝代，有資格的賬戶只能申請加入或者退出 D+2 朝代的驗證者集合，當朝代變更到D+2 時，才可加入新區(qū)塊的共識過程。
3. 共識過程
新的區(qū)塊被提出后，當前朝代驗證者集合中所有人將會參與一輪 BFT （ByzanTIne Fault Tolerant） ?式的投票，來確定此區(qū)塊的合法性。在投票最開始，每一個參與此區(qū)塊共識的驗證者將會被從押金中收取 2x（x 為激勵獎金?例） 的保證金，然后進入兩階段的投票過程。
? 第一階段，所有驗證者需要對新區(qū)塊投 P repare 票，投完 P repare 票的驗證者將獲得 1.5x 的獎勵，如果在當前朝代和上一個朝代中都有超過 2/3 的押金總額的驗證者對新區(qū)塊投了 P repare 票，那么該區(qū)塊進入投票的第二階段。此處需要說明，新區(qū)塊的提議者將被默認對新區(qū)塊投 P repare 票。
? 第二階段，所有驗證者需要對新區(qū)塊投 Commit 票，投完 Commit 票的驗證者，可以再獲得 1.5x 的獎勵，如果在當前朝代和上一個朝代中都有超過 2/3 的押金總額的驗證者對新區(qū)塊投了 Commit 票，那么該區(qū)塊到達 finality 狀態(tài)。
為了加速整個生態(tài)向前延展，如果區(qū)塊 b 的 P repare 和 Commit 票的時間戳和區(qū)塊 b 的時間戳相差超過 T，那么這些票將被視為過期，直接忽略。
4. 分叉選擇
PoD 算法以每個高度上區(qū)塊的得分來選擇權威鏈，總是選擇得分最高的區(qū)塊加入權威鏈，在高度 h 的區(qū)塊 b 的得分如下，
即為該區(qū)塊及其所有后代區(qū)塊收到的 commit 票對應的押金總和，如圖14所示。
5. 投票規(guī)則
為了避免共識過程被惡意破壞，導致共識過程沒法完成，阻礙生態(tài)發(fā)展，PoD 參考 Casper 的最小懲罰規(guī)則來約束驗證者的共識活動。
假設共識過程中的 P repare 和 Commit 票結構如下，
? P repare（H， v， vs），其中 H 為當前區(qū)塊 hash，v 表示當前區(qū)塊高度，vs 表示 v 的某個祖先區(qū)塊高度
? Commit（H， v），其中 H 為當前區(qū)塊 hash，v 表示當前區(qū)塊高度
PoD 算法為整個投票過程制定了如下 4 條基本規(guī)則，
? 單個區(qū)塊的兩階段共識過程存在嚴格的先后順序，只有在第一階段 P repare（H， v， vs） 票總權值達到2/3 后，驗證者們才可以投出第二階段的 Commit（H， v） 票，
? 多區(qū)塊間不強制一個區(qū)塊共識結束后才能開始后一個區(qū)塊的共識，允許交織共識 （interwoven consensus），但是不能完全沒有秩序只有高度vs 完成了第一階段過程，擁有 2/3 的 P repare（Hanc， vs， vs’）后，才可以基于 vs 對其后代區(qū)塊投 P repare（H， v， vs） 票，保證交織穩(wěn)步向前
? 為了避免有節(jié)點利用交織共識惡意跨多區(qū)塊投票，要求基于高度 u 投出了 P repare（H， w， u） 票之后，對于高度在跨度 u 和 w 之間的所有區(qū)塊，不能再投出 Commit（H， v） 票，保證共識過程的高效有序
? 為了制?節(jié)點用同一筆押金在多個分支上同時下注，導致 nothing at stake 的問題，要求在一個高度投出 P repare（H1， v， vs1） 票之后，不能再投出不一樣的 P repare（H2， v， vs2） 票違反上述規(guī)則的驗證者一旦被舉報核實，將會被罰掉所有押金，舉報者們將會共享罰金的 4% 作為獎勵，罰金的剩余部分將會被銷毀。
PoD 經(jīng)濟分析
1. 激勵分析
參與 PoD 算法的驗證者，在每一個合法區(qū)塊上可以獲得 1x 的星云幣獎勵，如果網(wǎng)絡不暢或者有人作弊導致 Prepare 階段沒有辦法完成進入 Commit 階段，那么所有驗證者將損失 0.5x。因此成為驗證者的價值節(jié)點在保持網(wǎng)絡暢通，不參與作弊的情況下，將共享大量記賬收益。
2. 作弊分析
雙重支付攻擊 （double spend）
假設商戶 merchant 等到新區(qū)塊到達 finality 狀態(tài)就確認交易發(fā)貨，那么 fraud 要在 PoD 共識算法下完成雙重支付攻擊實現(xiàn)零成本購物要付出的最小代價如下：
?先，fraud 需要提高自己的 Nebulas Rank 到 Top N，然后繳一定數(shù)的 NaS 作為押金成為驗證者，并申請參與 D+2 朝代區(qū)塊的驗證。
然后，fraud 需要被偽隨機算法選中為新區(qū)塊的提議者，此時 fraud 提出兩個高度相同的新區(qū)塊，一個哈希值為 hash1 包含 fraud 向 merchant 的轉賬交易，另一個哈希值為 hash2 包含 fraud 向 fraud 自己的轉賬交易。
最后，為了讓 hash1 和 hash2 區(qū)塊都到達 finality，如圖15所示，fraud 至少需要花費所有押金的 1/3來賄賂 1/3 的驗證者，讓他們給兩個區(qū)塊都投 Commit 票。
所以要完成一次成功的雙重支付攻擊，fraud 需要花費一定的精力和財力來提升自己的 Nebulas Rank排名，然后等到幸運地被選為提議者時，至少花費總押金的 1/3 來讓兩個塊同時到達finality 狀態(tài)。
51% 攻擊 （51% attack）
在 PoW 中要發(fā)起 51% 攻擊需要 51% 的算力，在 PoS 中則需要 51% 的押金，而在 PoD 中，則需要驗證者集合中 51% 的賬戶，這意味著擁有足夠多的高聲望用戶進入 Nebulas Rank 的 Top N，并且需要支付對應的押金，因此在 PoD 中 51% 攻擊將更為困難。
短程攻擊 （short-range attack）
PoD 中的每個高度上的區(qū)塊都有共識有效期，如果某個高度距離最新高度超過 100 時，該高度的所有區(qū)塊在共識過程中將被視為過期，那么這些區(qū)塊上的所有新的共識活動將會被直接忽略。因此要在 PoD 中完成長程攻擊 （long-range attack） ?乎不可能，但是在有效期內(nèi)依舊存在發(fā)起短程攻擊的可能性。
短程攻擊者 Attacker 試圖在高度 H+1 的區(qū)塊還沒有過期的情況下，偽造 A 鏈來替代 B 鏈成為權威鏈，Attacker 需要讓區(qū)塊 A1 的得分? B1 更高。由于多投會被嚴懲，所以 Attacker 將不可避免地要賄賂驗證者，否則無法完成短程攻擊。為了展現(xiàn) PoD 共識算法的安全性，下?分別分析使不同數(shù)量的區(qū)塊失效時，Attacker 需要付出的代價。
如果 Attacker 想要使 B1 失效，最小代價的情況如圖16，就相當一次雙重支付攻擊，Attacker 幸運地成為了 H+1 高度的區(qū)塊提議者，那么至少需要賄賂朝代 D0 中 1/3 的驗證者多投使 A1 達到 finality，最小代價為所有押金的 1/3。
如果 Attacker 想要使 B1-B2 失效，假設 B1 和 B2 都已到達 finality，塊中交易都已生效，為了讓這些交易失效，這?考慮兩種情況。第一種如圖17中 （a） 所示，高度 H+1 和 H+2 在同一個 Epoch 中，朝代相同，那么 Attacker ?先需要賄賂 D0 中 1/3 的驗證者使 A1 達到 finality，此時這 1/3 的驗證者將會被懲罰，押金被罰完。在 A2 的驗證中整體押金總和只有 A1 中的 2/3，此時 Attacker 想要讓 A2 到達和 B2同價值的 committ 票，需要賄賂剩下所有沒有作弊的驗證者，合起來至少需要損失總押金的 3/3，即使如此也不能保證 A1 得分? B1 高，攻擊失敗風險高。第二種情況如圖17中 （b） 所示，高度 H+1 和 H+2 正好在不同的 Epoch 中，且朝代不相同，那么此時 Attacker 需要賄賂 D0 中的 1/3 來讓 A1 到達 finality，然后賄賂 D1 中的 1/3 來讓 A2 達到 finality，完成一次這樣的攻擊至少需要損失總押金的 2/3。綜上，想要發(fā)起短程攻擊導致兩個 finality 區(qū)塊失效，至少需要花費總押金 2/3 的代價。
如果 Attacker 想要使 B1-B3 失效，如圖18所示，Attacker ?先需要賄賂 D0 中 1/3 的人完成 A1 的finality，然后賄賂 D1 中 1/3 的人完成 A2 的 finality，最后需要賄賂 D1 中剩下 2/3 中的所有人來完成A3 的 finality，綜上至少要損失總押金的 4/3。要完成這些攻擊準備將會十分困難，而且即使有幸做到了，也不定能保證 A1 的得分? B1 高，攻擊也可能會失敗。
如果 Attacker 想要使 B1-BN 失效，其中 N 受到區(qū)塊共識有效期的限制，不會很大，由于 N = 3 時當前朝代所有驗證者的押金就會被全部罰完，所以 N 》= 4 時，將沒法完成攻擊讓 B1 得分? A1 高，使B1-BN 失效，發(fā)起這樣的攻擊沒有任何意義。
下載文檔
