基于區(qū)塊鏈解決方案的Exonum共識(shí)算法機(jī)制探討

Exonum平臺(tái)是構(gòu)建區(qū)塊鏈解決方案的領(lǐng)先開(kāi)源框架。它是拜占庭式的容錯(cuò)算法，專注于效率合安全性，不需要您的區(qū)塊鏈來(lái)“挖掘”塊。

以下是我們的共識(shí)算法的不同之處。

求解一個(gè)共識(shí)算法

區(qū)塊鏈?zhǔn)且环N數(shù)字分布式數(shù)據(jù)賬本，以區(qū)塊鏈的形式組織起來(lái)。只有在下列情況下才有可能向鏈中添加新塊：a）網(wǎng)絡(luò)成員節(jié)點(diǎn)就相同的建議塊達(dá)成協(xié)議;b）建議的塊是準(zhǔn)確的。

要做出此決定，節(jié)點(diǎn)需要遵循規(guī)則。這些規(guī)則還允許網(wǎng)絡(luò)管理員評(píng)估成員節(jié)點(diǎn)的活動(dòng)。

簡(jiǎn)而言之：需要一種共識(shí)算法，以確保對(duì)等網(wǎng)絡(luò)成員能夠?qū)π碌馁~本狀態(tài)達(dá)成一致意見(jiàn)（換句話說(shuō)，對(duì)區(qū)塊鏈中的新塊的內(nèi)容達(dá)成聯(lián)合決策）。

比特幣區(qū)塊鏈的普遍算法是工作量證明（PoW）算法。在這里，確定參與者（礦工）執(zhí)行的新塊的復(fù)雜計(jì)算工作，以及他為此獲得的報(bào)酬，保證了網(wǎng)絡(luò)當(dāng)前狀態(tài)的正確性。PoW算法為系統(tǒng)的正常運(yùn)行提供了經(jīng)濟(jì)保證。PoW、PoS證明及其混合形式的下一個(gè)主要替代方案也提供了通過(guò)投資或花費(fèi)參與者自己的物質(zhì)資源達(dá)成共識(shí)的機(jī)會(huì)。在這種情況下，人們認(rèn)為，即使不是完全無(wú)利可圖，不公平的活動(dòng)至少也會(huì)變得極其昂貴。

然而，盡管比特幣被認(rèn)為是目前存在的最可靠的分布式系統(tǒng)，但它和它的替代品都沒(méi)有從根本上解決拜占庭式節(jié)點(diǎn)行為的問(wèn)題。拜占庭將軍的故事大家都知道，所以我們就不解釋了。就本文而言，我們的意思是試圖為任何“拜占庭節(jié)點(diǎn)行為”（即任何故意惡意的、旨在破壞或完全停止共識(shí)算法操作的活動(dòng)）找到一個(gè)解決方案。

當(dāng)在私有區(qū)塊鏈網(wǎng)絡(luò)中處理這個(gè)問(wèn)題時(shí)，您必須用數(shù)學(xué)方法表示協(xié)商一致的屬性。這是通過(guò)在網(wǎng)絡(luò)中創(chuàng)建嚴(yán)格的行為規(guī)則來(lái)實(shí)現(xiàn)的，與PoW和其他基于經(jīng)濟(jì)的協(xié)商一致算法相比，這些算法幾乎不需要自發(fā)地運(yùn)行。其中一些基于數(shù)學(xué)的共識(shí)（特別是拜占庭容錯(cuò)共識(shí)（BFT））有一個(gè)明確的算法，可以選擇提出新塊建議的領(lǐng)導(dǎo)節(jié)點(diǎn)。

共識(shí)算法還必須考慮到區(qū)塊鏈中可能出現(xiàn)的常見(jiàn)問(wèn)題，即：節(jié)點(diǎn)與網(wǎng)絡(luò)失去連接（網(wǎng)絡(luò)參與者之間的通信失敗）、節(jié)點(diǎn)沒(méi)有在任意時(shí)間點(diǎn)運(yùn)行（斷開(kāi)連接）以及節(jié)點(diǎn)工作時(shí)的不正確。所有這些問(wèn)題都描述了節(jié)點(diǎn)的“拜占庭行為”。此外，不影響在區(qū)塊鏈中采用新塊的最大允許異常數(shù)取決于網(wǎng)絡(luò)及其處理器/節(jié)點(diǎn)的屬性。例如，網(wǎng)絡(luò)中節(jié)點(diǎn)之間通信的同步。

20世紀(jì)80年代的經(jīng)典研究表明，要在包含拜占庭行為節(jié)點(diǎn)的異步網(wǎng)絡(luò)中實(shí)現(xiàn)共識(shí)性的穩(wěn)定運(yùn)行是不可能的。網(wǎng)絡(luò)中誠(chéng)實(shí)的成員將無(wú)法區(qū)分拜占庭節(jié)點(diǎn)和不活躍的節(jié)點(diǎn)（所謂的“FLP Impossibili”），為了保證系統(tǒng)對(duì)上述故障的穩(wěn)定性，必須至少部分同步。同時(shí)，為了正確工作，共識(shí)算法至少應(yīng)該具有以下屬性：

· 活躍性-在有限的時(shí)間內(nèi)隨時(shí)接受新區(qū)塊進(jìn)入鏈條的能力。換句話說(shuō)，每個(gè)節(jié)點(diǎn)最終都會(huì)決定下一個(gè)塊;

· 一致性-網(wǎng)絡(luò)中所有節(jié)點(diǎn)上的基本狀態(tài)的標(biāo)識(shí)。換句話說(shuō)，最終，關(guān)于下一個(gè)塊的所有誠(chéng)實(shí)節(jié)點(diǎn)的決策將是相同的。

如果我們說(shuō)到共識(shí)算法是專門應(yīng)用于區(qū)塊鏈的，那么另一個(gè)特性就變得很重要。這就是審查阻力，這意味著缺乏對(duì)交易的審查，這是區(qū)塊鏈共識(shí)的一個(gè)特定特征。它防止節(jié)點(diǎn)故意只為塊選擇某些交易，而將其他交易留在未經(jīng)確認(rèn)的交易池中。

基于相同的研究結(jié)果，對(duì)于一個(gè)已知節(jié)點(diǎn)數(shù)量的網(wǎng)絡(luò)，最優(yōu)的是一個(gè)抵抗拜占庭節(jié)點(diǎn)行為的算法模型。在具有部分同步節(jié)點(diǎn)的網(wǎng)絡(luò)中，該模型最多可以容忍網(wǎng)絡(luò)中三分之一的惡意（拜占庭式）成員。

鑒于我們的目標(biāo)和Exonum框架的目標(biāo)，我們選擇這個(gè)模型來(lái)形成我們的共識(shí)算法。

總之，我們?cè)O(shè)計(jì)的共識(shí)算法能夠確定網(wǎng)絡(luò)中每個(gè)誠(chéng)實(shí)成員的行為，在這種情況下，大多數(shù)成員的行為都是誠(chéng)實(shí)的，有些成員的行為可能是任意的。

我們需要設(shè)計(jì)一個(gè)誠(chéng)實(shí)節(jié)點(diǎn)對(duì)傳入事件（來(lái)自其他節(jié)點(diǎn)的消息）的響應(yīng)方案。這些反應(yīng)包括發(fā)送適當(dāng)?shù)捻憫?yīng)消息或“意識(shí)到”某個(gè)決定已經(jīng)由網(wǎng)絡(luò)做出。這決定了區(qū)塊鏈的日常操作。

達(dá)成共識(shí)的關(guān)鍵門檻： 2/3對(duì)1/3的選票

共識(shí)算法的基本操作有兩個(gè)步驟。首先，某個(gè)驗(yàn)證器節(jié)點(diǎn)（參與協(xié)商一致的節(jié)點(diǎn)）提出一個(gè)新的塊建議，并在網(wǎng)絡(luò)中的所有節(jié)點(diǎn)之間進(jìn)行廣播。其次，其余的驗(yàn)證器節(jié)點(diǎn)為這個(gè)提議投票（“贊成”/“反對(duì)”）。

當(dāng)其中一個(gè)節(jié)點(diǎn)首先從其他驗(yàn)證器接收到一定數(shù)量的相同響應(yīng)時(shí)，該決策對(duì)整個(gè)網(wǎng)絡(luò)有效。

與現(xiàn)實(shí)世界中這一進(jìn)程最接近的類比是總統(tǒng)選舉的情況。這是在兩位候選人之間做出的選擇。選民的數(shù)量是有限的，有些人可能會(huì)投給一個(gè)候選人，有些人會(huì)投給另一個(gè)候選人。

在非拜占庭系統(tǒng)（例如，Cassandra）中，當(dāng)提案獲得超過(guò)50%的選票時(shí)，就會(huì)被認(rèn)為是做出了決定。由于每個(gè)成員只投票一次，其余的選票不計(jì)算在內(nèi)。值得一提的是，由于投票的數(shù)量與網(wǎng)絡(luò)參與者的數(shù)量一致，因此在這種情況下不需要確定選民。

然而，在拜占庭系統(tǒng)中情況就不同了。在這里，投票是公開(kāi)的，即每個(gè)人都知道成員的身份。然而，只要我們假設(shè)某些節(jié)點(diǎn)可能以任意方式運(yùn)行，我們就會(huì)面臨許多問(wèn)題。拜占庭節(jié)點(diǎn)可以通過(guò)忽略投票過(guò)程來(lái)破壞投票過(guò)程，或者向不同的成員發(fā)送關(guān)于其決策的不同數(shù)據(jù)。事實(shí)上，這種情況類似于選舉中的選票造假。基于50%以上多數(shù)投票的決定違反了系統(tǒng)一致性的性質(zhì)。這是因?yàn)楝F(xiàn)在選票的數(shù)量（或選票的數(shù)量）不等于選民的數(shù)量（網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量）。

在這種情況下，節(jié)點(diǎn)在某個(gè)時(shí)間點(diǎn)上沒(méi)有系統(tǒng)狀態(tài)的統(tǒng)一視圖。而系統(tǒng)本身并沒(méi)有一個(gè)單獨(dú)的中心來(lái)收集和溝通最終的決定。因此，拜占庭共識(shí)的問(wèn)題不在于選擇的正確與否，而在于：

· 整個(gè)系統(tǒng)必須對(duì)最終結(jié)果達(dá)成一致決定。

· 只要至少有一些網(wǎng)絡(luò)成員有興趣這樣做，最終的結(jié)果必須是可以達(dá)到的。

讓我們來(lái)確定網(wǎng)絡(luò)中誠(chéng)實(shí)驗(yàn)證器的臨界質(zhì)量，它將允許系統(tǒng)達(dá)成共識(shí)并接受區(qū)塊鏈中的新塊。

假設(shè)我們有‘ h ’誠(chéng)實(shí)的驗(yàn)證器節(jié)點(diǎn)和‘ f ’（錯(cuò)誤的）拜占庭節(jié)點(diǎn)，那么驗(yàn)證器的總數(shù)是‘ N = h + f ’。如上所述，所有驗(yàn)證器都為兩個(gè)提名候選人中的一個(gè)投票。每個(gè)人都從投票過(guò)程中的其他成員那里收集選票。每個(gè)人都可以根據(jù)閾值規(guī)則來(lái)決定誰(shuí)是贏家。規(guī)則說(shuō)：數(shù)量的選票獲勝的候選人必須“≥α* N”、“α”的范圍從“0”到“1”。例如，絕對(duì)多數(shù)選票時(shí)達(dá)到“α》 1/2”。

在投票結(jié)束時(shí)，每個(gè)驗(yàn)證器獨(dú)立決定哪位候選人獲勝。值得注意的是，驗(yàn)證器可能無(wú)法做出決策。例如，如果太少的驗(yàn)證器廣播了他們的投票，就會(huì)發(fā)生這種情況。這可能會(huì)發(fā)生，特別是因?yàn)榘菡纪ヲ?yàn)證器可以向不同的誠(chéng)實(shí)驗(yàn)證器廣播不同的投票，或者完全跳過(guò)投票。

為了避免這種情況，在我們的推理中，我們必須觀察兩個(gè)條件：

1. 誠(chéng)實(shí)的驗(yàn)證器應(yīng)該能夠做出選擇，即使沒(méi)有拜占庭節(jié)點(diǎn)的參與。這意味著即使拜占庭節(jié)點(diǎn)有意跳過(guò)投票，共識(shí)性算法的活性也得到了保留。這種情況可以通過(guò)下列不等式表示：“h≥α* N ‘;

2. 投票給少數(shù)誠(chéng)實(shí)驗(yàn)證者的替代方案不能克服“α* N”的門檻。也就是說(shuō)，即使拜占庭節(jié)點(diǎn)有意且一貫地將一名候選人的選票廣播給一些誠(chéng)實(shí)的驗(yàn)證者，并且投票給第二個(gè)候選人 ，也保留共識(shí)算法的一致性屬性 - 其余為誠(chéng)實(shí)驗(yàn)證。讓我們將這種情況表達(dá)如下：’［h / 2］ = f ［= = N‘，其中”{h / 2}“是數(shù)字”h / 2“的整數(shù)部分。

解1和2的不等式，我們得到：

h f 》 2，

α》 2/3，

N≥3f + 1

因此，網(wǎng)絡(luò)中允許正確一致操作的拜占庭節(jié)點(diǎn)的最大數(shù)量是驗(yàn)證器總數(shù)的’ 《1/3 ‘。

這個(gè)結(jié)果很容易驗(yàn)證。假設(shè)所有拜占庭節(jié)點(diǎn)都決定投票兩次。他們向一些誠(chéng)實(shí)的驗(yàn)證者廣播一個(gè)候選人的投票，并向其余誠(chéng)實(shí)的驗(yàn)證者廣播第二個(gè)候選人的投票。如果拜占庭節(jié)點(diǎn)的數(shù)量是驗(yàn)證器總數(shù)的1/3，那么根據(jù)投票結(jié)果得到的投票總數(shù)將是4/3。因此，只投票一次（2/3）的誠(chéng)實(shí)節(jié)點(diǎn)的數(shù)量將恰好占總投票數(shù)的50%。這樣，為了獲得大多數(shù)誠(chéng)實(shí)投票并達(dá)成共識(shí)，誠(chéng)實(shí)節(jié)點(diǎn)的數(shù)量至少應(yīng)該是驗(yàn)證器總數(shù)的“2/3 +1”。

共識(shí)算法的階段

在現(xiàn)代區(qū)塊鏈操作中，用戶對(duì)系統(tǒng)速度和性能的期望很高。經(jīng)典的算法解決方案沒(méi)有提供這些特性。我們回顧了其他幾個(gè)升級(jí)的替代方案，但是它們也不能完全滿足我們的研究團(tuán)隊(duì)，因?yàn)檫@些算法不能滿足專家對(duì)框架的所有要求。因此，我們開(kāi)發(fā)了自己的算法。

Exonum的共識(shí)算法依賴于inTendermint提出的一些思想。然而，它包含了許多特性，使它有別于Tendermint和其他用于基于區(qū)塊鏈的解決方案的一致算法。

達(dá)成一致意見(jiàn)的過(guò)程首先由一個(gè)領(lǐng)導(dǎo)節(jié)點(diǎn)（一個(gè)領(lǐng)導(dǎo)者）形成一個(gè)必須添加到區(qū)塊鏈的交易列表（創(chuàng)建一個(gè)建議）。領(lǐng)導(dǎo)者是通過(guò)一個(gè)單獨(dú)的算法來(lái)選擇的。根據(jù)我們的算法，領(lǐng)導(dǎo)者每輪都會(huì)改變。然后，將提案通過(guò)網(wǎng)絡(luò)廣播到驗(yàn)證器節(jié)點(diǎn)（驗(yàn)證器）。

驗(yàn)證器檢查接收到的消息是否與序列化格式相對(duì)應(yīng)。如果出現(xiàn)錯(cuò)誤，節(jié)點(diǎn)將完全忽略接收到的消息。例如，驗(yàn)證器忽略向區(qū)塊鏈中間添加塊或復(fù)制已存在事務(wù)的建議。如果一切就緒，那么投票階段就開(kāi)始了。

提案獲得驗(yàn)證者2/3以上批準(zhǔn)的節(jié)點(diǎn)，將失去對(duì)其他驗(yàn)證者提案投票的機(jī)會(huì)，并且無(wú)法更改自己的提案。這種狀態(tài)稱為鎖的驗(yàn)證。

在領(lǐng)導(dǎo)者從驗(yàn)證器收集到所需的投票數(shù)之后，它將批準(zhǔn)的交易放入一個(gè)塊中，并廣播一條特殊的消息——precommit。

precommit包含更新后的區(qū)塊鏈狀態(tài)的哈希值，指示節(jié)點(diǎn)準(zhǔn)備將建議的塊添加到區(qū)塊鏈。當(dāng)大多數(shù)驗(yàn)證器響應(yīng)類似的預(yù)提交消息時(shí)（使用相同的哈希值），塊就被添加到區(qū)塊鏈中。達(dá)成一致意見(jiàn)，并對(duì)隨后的每個(gè)塊重復(fù)該過(guò)程。

為了提高系統(tǒng)的穩(wěn)定性，驗(yàn)證器之間會(huì)周期性地交換和阻塞消息。如果節(jié)點(diǎn)缺少任何事務(wù)數(shù)據(jù)，則需要使用前者。后者用于將關(guān)于一個(gè)事務(wù)塊的信息傳輸?shù)揭粋€(gè)滯后節(jié)點(diǎn)（例如，節(jié)點(diǎn)關(guān)閉了一段時(shí)間）。這允許同步整個(gè)網(wǎng)絡(luò)的工作。

所提出的共識(shí)性算法對(duì)每個(gè)高度都是正確的，即滿足了活動(dòng)性、一致性和抗審查性。共識(shí)屬性的正式證明可以在我們的白皮書(shū)中找到。

性能測(cè)試

為了評(píng)估Exonum共識(shí)性算法的效率，我們檢查了區(qū)塊鏈如何使用它使用兩種配置。這些配置包括一個(gè)數(shù)據(jù)中心和幾個(gè)地理上分布的數(shù)據(jù)中心。在測(cè)試期間，對(duì)不同數(shù)量的驗(yàn)證器估計(jì)了TPS參數(shù)（每秒交易數(shù)）。下面的圖表顯示了使用加密貨幣的區(qū)塊鏈（黑色圖表）和使用時(shí)間戳的區(qū)塊鏈（藍(lán)色圖表）中的網(wǎng)絡(luò)性能變化。

TPS是單個(gè)數(shù)據(jù)中心中驗(yàn)證器數(shù)量的函數(shù)

TPS是多個(gè)數(shù)據(jù)中心中驗(yàn)證器數(shù)量的函數(shù)

根據(jù)網(wǎng)絡(luò)配置的不同，Exonum及其針對(duì)區(qū)塊鏈的新拜占庭容錯(cuò)共識(shí)性算法平均每秒可以處理2，000到13，000個(gè)交易。在生產(chǎn)解決方案方面，該算法可以在全球分布式網(wǎng)絡(luò)上以0.5秒的塊接受時(shí)間每秒處理4000個(gè)交易。Exonum的性能在出現(xiàn)故障停止驗(yàn)證器時(shí)是穩(wěn)定的，但是隨著驗(yàn)證器總數(shù)的增加，Exonum的性能會(huì)顯著下降。