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