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)绾伪Ｕ蠈?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é)

以上是生活随笔為你收集整理的NEO共识算法图解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。