NEO共识算法图解
2019獨角獸企業重金招聘Python工程師標準>>>
共識機制
術語說明
-
權益證明?PoS?：一種利用網絡協商一致來處理容錯的算法。
-
工作量證明?PoW?：一種利用計算能力來處理容錯的算法。
-
拜占庭錯誤?BF： 一個節點保持功能，但以不誠實甚至是惡意的方式來工作。
-
dBFT（一種改進的拜占庭容錯算法）?dBFT?：NEO 區塊鏈中的共識算法，該算法通過多個共識節點的協商來達成共識，有良好的可用性和最終性。
-
視圖?V?：在 dBFT 算法中，一次共識從開始到結束所使用的數據集合，稱為視圖。
規則
在 NEO 的共識算法中，共識節點由 NEO 持有人投票選出，并對區塊鏈中交易的有效性進行驗證。過去這些節點被稱作“記賬人”，現在他們被稱作”共識節點”。
- ?共識節點：此節點參與共識行為。 在共識行為中, 共識節點輪流擔任以下兩個角色：
- ?議長?（一人）?：議長?負責向系統發送一個新的區塊的提案。
- ?議員?（多人）?：議員?負責對議長的提案進行投票，大于等于2/3的議員投票時，提案通過。
介紹
眾多區塊鏈共識算法的根本區別是他們如何保障對系統中的故障節點、惡意節點的容錯能力。
傳統的 PoW 方法可以提供這種容錯能力，只要網絡的大多數算力是誠實的。
然而，由于這種模式依賴于大量的計算，這種機制可能會非常低效且不環保（算力消耗能源，需要硬件）。 這些依賴就是 PoW 方法的限制所在，最主要的就是擴展的成本。
NEO實現了一種委托的拜占庭容錯共識算法，它借鑒了一些 PoS 的特點（NEO持有人需要對共識節點進行投票） 利用最小的資源來保障網絡免受拜占庭故障的影響，同時也彌補了 PoS 的一些問題。該解決方案解決了與當前塊鏈實現相關的性能和可擴展性問題，而不會對容錯產生重大影響。
理論
拜占庭位于如今的土耳其的伊斯坦布爾，是東羅馬帝國的首都。由于當時拜占庭羅馬帝國國土遼闊，為了防御目的，因此每個軍隊都分隔很遠，將軍與將軍之間只能靠信差傳消息。 在戰爭的時候，拜占庭軍隊內所有將軍和副官必需達成一致的共識，決定是否有贏的機會才去攻打敵人的陣營。但是，在軍隊內有可能存有叛徒和敵軍的間諜，左右將軍們的決定又擾亂整體軍隊的秩序。在進行共識時，結果并不代表大多數人的意見。這時候，在已知有成員謀反的情況下，其余忠誠的將軍在不受叛徒的影響下如何達成一致的協議，拜占庭問題就此形成。
為了描述 DBFT 的工作原理，我們將本節重點放在第 5 部分中的證明 66.66％ 的共識率的正確性。請記住，不誠實的節點不需要主動惡意，因為它根本不可能是按預期運作。
為了討論，我們將描述一些情景。 在這些簡單的例子中，我們假設每個節點沿著從?議長?發送過來的消息發送。 此技工也用于DBFT，對系統至關重要。 我們將僅描述功能系統與功能失效系統之間的區別。 有關更詳細的說明，請參閱參考資料。
誠實的議長
圖 1：?一個 n = 3 的例子中存在一個不誠實的?議員。
在圖 1 中，我們有一個誠實的?議員?(50%)。兩個?議員?從?議長?那里收到相同的消息，然而，由于其中一個?議員?不是誠實的，誠實的議員只能確定有不誠實的節點，但無法識別它是?議長?還是?議員。因此?議員?必須棄票，改變視圖。
圖 2：?一個 n =4 的例子中存在一個不誠實的?議員。
在圖 2 中，我們有兩個誠實的?議員?(66%)。所有的?議員?從?議長?那里收到相同的消息，然后向其它?議員?發送消息和自己的驗證結果。根據兩位誠實?議員?的共識，我們可以確定?議長?或者右邊的?議員?在系統中是不誠實的。
不誠實的議長
圖 3：?一個 n = 3 的例子中存在一個不誠實的?議長。
在圖 3 中，不誠實的是?議長，這和圖 1 中描述的案例有同樣的結論。議員?無法確定哪個節點是不誠實的。
圖 4：?一個 n = 4 的例子中存在一個不誠實的?議長。
在圖 4 所示的例子中，中間的節點和右邊的節點接收的區塊不可驗證， 由于他們占到多數（66%），導致更換視圖選舉新議長。在這個例子中，如果誠實的議長向三名議員中的兩名發送了誠實的數據，那么它將被驗證而不需要改變視圖。
實際實施
DBFT 在 NEO 中的實際實現使用迭代共識方法來保證達成共識。算法的性能取決于系統中誠實節點的分數。圖5描繪了作為不誠實節點的函數的期望迭代。
請注意，圖5沒有低于66.66%的共識節點誠信。在這個臨界點和33.33%的共識節點誠信之間，有一個無人地帶，那里無法達成共識。低于33.33%的共識節點誠信，不誠實的節點（假設它們達成共識）能夠自己達成共識，并成為系統中新的真理點。
圖5:?DBFT算法的 Monto-Carlo 模擬，描繪了達成共識所需的迭代。 {100 個節點；100,000 個模擬區塊隨機選擇誠實節點}
定義
在算法中有如下定義：
- t：分配給區塊生成的時間總量，以秒為單位。
- 當前時間：?t = 15 秒
- 這個值可以用來粗略估計單個視圖迭代的持續時間，因為共識活動和通信事件相對于這個時間常數是快速的。
- n： 有效的共識節點數量。
- f：系統中故障共識節點的最小閾值。
- f = (n - 1) / 3
- h?: 在共識活動期間的當前塊高度。
-
i?: 共識節點索引。
-
v?: 共識節點視圖。該視圖包含節點在一輪共識中收到的匯總信息。 這包括所有議員發起的投票（prepareResponse?或?ChangeView）。
-
k?: 視圖?v?的索引。共識活動可能需要多輪。在共識失敗時，k值增加，新一輪的共識開始。
-
p?: 選為議長的共識節點索引。這個索引的計算機制在共識節點間輪流，以防止單個節點成為系統內的指令器。
- p = (h - k) mod (n)
-
s: 安全共識的閾值。 低于這個閾值，表示網絡故障。
- s = ((n - 1) - f)
要求
在NEO中，共識容錯有三項主要要求：
- s?議員必須就一項交易達成共識，然后區塊才可以實施。
- 不誠實的共識節點不能說服故障交易的誠實共識節點。
- 至少s?Congressmen?處于同一狀態 (h,k) ，開始達成共識。
算法
該算法工作原理如下：
共識節點使用發送者的簽名向全網廣播一個交易。
圖 6:一個?共識節點?收到交易并在系統中廣播
共識節點將交易數據記錄到本地存儲器中。
共識活動的第一個視圖?v?被初始化。
議長確定。
圖 7:?議長?確定且設置好視圖
等待?t?秒。 ?
議長廣播提案?<prepareRequest, h, k, p, bloc, [block]sigp>
圖 8:議長?提出區塊提案，由眾議員審閱。
議員收到提案并驗證：
-
數據格式與系統規則是否一致?
-
交易是否已經在鏈上?
-
合同腳本是否正確執行?
- 交易是否只包含一筆開支（即交易是否避免了雙重開支的情況？)
-
如果是有效的提案廣播:?<prepareResponse, h, k, i, [block]sigi>
-
如果是無效的提案廣播:?<ChangeView, h,k,i,k+1> ? ‘
圖 9:議員?審閱區塊提案并響應?
在收到?s?數量的 'prepareResponse' 廣播后，眾議員達成共識并發布一個區塊。
議員簽名該區塊
圖 10:?達成共識，獲批議員簽名區塊，并將其綁定到鏈上。
當一個共識節點收到一個完整區塊時，當前的視圖數據被清除，并開始新一輪的共識。
- k = 0
NOTE
如果 (?) 秒后在同一視圖沒有達成共識：
-
?共識節點進行廣播：<ChangeView, h,k,i,k+1>
-
一旦共識節點接收到至少?s?個表示相同視圖改變的廣播，就會增加視圖?v， 并引發新一輪的共識。
引用
- A Byzantine Fault Tolerance Algorithm for Blockchain
- Practical Byzantine Fault Tolerance
- The Byzantine Generals Problem
原文：http://docs.neo.org/zh-cn/basic/consensus/consensus.html
轉載于:https://my.oschina.net/u/4005186/blog/2990508
總結
- 上一篇： 洛谷P4382 劈配
- 下一篇： cordova使用cordova-plu