Exonum平臺是構(gòu)建區(qū)塊鏈解決方案的領先開源框架。它是拜占庭式的容錯算法,專注于效率合安全性,不需要您的區(qū)塊鏈來挖掘塊。以下是我們的共
Exonum平臺是構(gòu)建區(qū)塊鏈解決方案的領先開源框架。它是拜占庭式的容錯算法,專注于效率合安全性,不需要您的區(qū)塊鏈來“挖掘”塊。
以下是我們的共識算法的不同之處。
求解一個共識算法
區(qū)塊鏈是一種數(shù)字分布式數(shù)據(jù)賬本,以區(qū)塊鏈的形式組織起來。只有在下列情況下才有可能向鏈中添加新塊:a)網(wǎng)絡成員節(jié)點就相同的建議塊達成協(xié)議;b)建議的塊是準確的。
要做出此決定,節(jié)點需要遵循規(guī)則。這些規(guī)則還允許網(wǎng)絡管理員評估成員節(jié)點的活動。
簡而言之:需要一種共識算法,以確保對等網(wǎng)絡成員能夠?qū)π碌馁~本狀態(tài)達成一致意見(換句話說,對區(qū)塊鏈中的新塊的內(nèi)容達成聯(lián)合決策)。
比特幣區(qū)塊鏈的普遍算法是工作量證明(PoW)算法。在這里,確定參與者(礦工)執(zhí)行的新塊的復雜計算工作,以及他為此獲得的報酬,保證了網(wǎng)絡當前狀態(tài)的正確性。PoW算法為系統(tǒng)的正常運行提供了經(jīng)濟保證。PoW、PoS證明及其混合形式的下一個主要替代方案也提供了通過投資或花費參與者自己的物質(zhì)資源達成共識的機會。在這種情況下,人們認為,即使不是完全無利可圖,不公平的活動至少也會變得極其昂貴。
然而,盡管比特幣被認為是目前存在的最可靠的分布式系統(tǒng),但它和它的替代品都沒有從根本上解決拜占庭式節(jié)點行為的問題。拜占庭將軍的故事大家都知道,所以我們就不解釋了。就本文而言,我們的意思是試圖為任何“拜占庭節(jié)點行為”(即任何故意惡意的、旨在破壞或完全停止共識算法操作的活動)找到一個解決方案。
當在私有區(qū)塊鏈網(wǎng)絡中處理這個問題時,您必須用數(shù)學方法表示協(xié)商一致的屬性。這是通過在網(wǎng)絡中創(chuàng)建嚴格的行為規(guī)則來實現(xiàn)的,與PoW和其他基于經(jīng)濟的協(xié)商一致算法相比,這些算法幾乎不需要自發(fā)地運行。其中一些基于數(shù)學的共識(特別是拜占庭容錯共識(BFT))有一個明確的算法,可以選擇提出新塊建議的領導節(jié)點。
共識算法還必須考慮到區(qū)塊鏈中可能出現(xiàn)的常見問題,即:節(jié)點與網(wǎng)絡失去連接(網(wǎng)絡參與者之間的通信失敗)、節(jié)點沒有在任意時間點運行(斷開連接)以及節(jié)點工作時的不正確。所有這些問題都描述了節(jié)點的“拜占庭行為”。此外,不影響在區(qū)塊鏈中采用新塊的最大允許異常數(shù)取決于網(wǎng)絡及其處理器/節(jié)點的屬性。例如,網(wǎng)絡中節(jié)點之間通信的同步。
20世紀80年代的經(jīng)典研究表明,要在包含拜占庭行為節(jié)點的異步網(wǎng)絡中實現(xiàn)共識性的穩(wěn)定運行是不可能的。網(wǎng)絡中誠實的成員將無法區(qū)分拜占庭節(jié)點和不活躍的節(jié)點(所謂的“FLP Impossibili”),為了保證系統(tǒng)對上述故障的穩(wěn)定性,必須至少部分同步。同時,為了正確工作,共識算法至少應該具有以下屬性:
· 活躍性-在有限的時間內(nèi)隨時接受新區(qū)塊進入鏈條的能力。換句話說,每個節(jié)點最終都會決定下一個塊;
· 一致性-網(wǎng)絡中所有節(jié)點上的基本狀態(tài)的標識。換句話說,最終,關于下一個塊的所有誠實節(jié)點的決策將是相同的。
如果我們說到共識算法是專門應用于區(qū)塊鏈的,那么另一個特性就變得很重要。這就是審查阻力,這意味著缺乏對交易的審查,這是區(qū)塊鏈共識的一個特定特征。它防止節(jié)點故意只為塊選擇某些交易,而將其他交易留在未經(jīng)確認的交易池中。
基于相同的研究結(jié)果,對于一個已知節(jié)點數(shù)量的網(wǎng)絡,最優(yōu)的是一個抵抗拜占庭節(jié)點行為的算法模型。在具有部分同步節(jié)點的網(wǎng)絡中,該模型最多可以容忍網(wǎng)絡中三分之一的惡意(拜占庭式)成員。
鑒于我們的目標和Exonum框架的目標,我們選擇這個模型來形成我們的共識算法。
總之,我們設計的共識算法能夠確定網(wǎng)絡中每個誠實成員的行為,在這種情況下,大多數(shù)成員的行為都是誠實的,有些成員的行為可能是任意的。
我們需要設計一個誠實節(jié)點對傳入事件(來自其他節(jié)點的消息)的響應方案。這些反應包括發(fā)送適當?shù)捻憫⒒?ldquo;意識到”某個決定已經(jīng)由網(wǎng)絡做出。這決定了區(qū)塊鏈的日常操作。
達成共識的關鍵門檻: 2/3對1/3的選票
共識算法的基本操作有兩個步驟。首先,某個驗證器節(jié)點(參與協(xié)商一致的節(jié)點)提出一個新的塊建議,并在網(wǎng)絡中的所有節(jié)點之間進行廣播。其次,其余的驗證器節(jié)點為這個提議投票(“贊成”/“反對”)。
當其中一個節(jié)點首先從其他驗證器接收到一定數(shù)量的相同響應時,該決策對整個網(wǎng)絡有效。
與現(xiàn)實世界中這一進程最接近的類比是總統(tǒng)選舉的情況。這是在兩位候選人之間做出的選擇。選民的數(shù)量是有限的,有些人可能會投給一個候選人,有些人會投給另一個候選人。
在非拜占庭系統(tǒng)(例如,Cassandra)中,當提案獲得超過50%的選票時,就會被認為是做出了決定。由于每個成員只投票一次,其余的選票不計算在內(nèi)。值得一提的是,由于投票的數(shù)量與網(wǎng)絡參與者的數(shù)量一致,因此在這種情況下不需要確定選民。
然而,在拜占庭系統(tǒng)中情況就不同了。在這里,投票是公開的,即每個人都知道成員的身份。然而,只要我們假設某些節(jié)點可能以任意方式運行,我們就會面臨許多問題。拜占庭節(jié)點可以通過忽略投票過程來破壞投票過程,或者向不同的成員發(fā)送關于其決策的不同數(shù)據(jù)。事實上,這種情況類似于選舉中的選票造假。基于50%以上多數(shù)投票的決定違反了系統(tǒng)一致性的性質(zhì)。這是因為現(xiàn)在選票的數(shù)量(或選票的數(shù)量)不等于選民的數(shù)量(網(wǎng)絡中的節(jié)點數(shù)量)。
在這種情況下,節(jié)點在某個時間點上沒有系統(tǒng)狀態(tài)的統(tǒng)一視圖。而系統(tǒng)本身并沒有一個單獨的中心來收集和溝通最終的決定。因此,拜占庭共識的問題不在于選擇的正確與否,而在于:
· 整個系統(tǒng)必須對最終結(jié)果達成一致決定。
· 只要至少有一些網(wǎng)絡成員有興趣這樣做,最終的結(jié)果必須是可以達到的。
讓我們來確定網(wǎng)絡中誠實驗證器的臨界質(zhì)量,它將允許系統(tǒng)達成共識并接受區(qū)塊鏈中的新塊。
假設我們有' h '誠實的驗證器節(jié)點和' f '(錯誤的)拜占庭節(jié)點,那么驗證器的總數(shù)是' N = h + f '。如上所述,所有驗證器都為兩個提名候選人中的一個投票。每個人都從投票過程中的其他成員那里收集選票。每個人都可以根據(jù)閾值規(guī)則來決定誰是贏家。規(guī)則說:數(shù)量的選票獲勝的候選人必須“≥α* N”、“α”的范圍從“0”到“1”。例如,絕對多數(shù)選票時達到“α> 1/2”。
在投票結(jié)束時,每個驗證器獨立決定哪位候選人獲勝。值得注意的是,驗證器可能無法做出決策。例如,如果太少的驗證器廣播了他們的投票,就會發(fā)生這種情況。這可能會發(fā)生,特別是因為拜占庭驗證器可以向不同的誠實驗證器廣播不同的投票,或者完全跳過投票。
為了避免這種情況,在我們的推理中,我們必須觀察兩個條件:
1. 誠實的驗證器應該能夠做出選擇,即使沒有拜占庭節(jié)點的參與。這意味著即使拜占庭節(jié)點有意跳過投票,共識性算法的活性也得到了保留。這種情況可以通過下列不等式表示:“h≥α* N ';
2. 投票給少數(shù)誠實驗證者的替代方案不能克服"α* N”的門檻。也就是說,即使拜占庭節(jié)點有意且一貫地將一名候選人的選票廣播給一些誠實的驗證者,并且投票給第二個候選人 ,也保留共識算法的一致性屬性 - 其余為誠實驗證。讓我們將這種情況表達如下:'[h / 2] = f [= = N',其中"{h / 2}"是數(shù)字"h / 2"的整數(shù)部分。
解1和2的不等式,我們得到:
h f > 2,
α> 2/3,
N≥3f + 1
因此,網(wǎng)絡中允許正確一致操作的拜占庭節(jié)點的最大數(shù)量是驗證器總數(shù)的' <1/3 '。
這個結(jié)果很容易驗證。假設所有拜占庭節(jié)點都決定投票兩次。他們向一些誠實的驗證者廣播一個候選人的投票,并向其余誠實的驗證者廣播第二個候選人的投票。如果拜占庭節(jié)點的數(shù)量是驗證器總數(shù)的1/3,那么根據(jù)投票結(jié)果得到的投票總數(shù)將是4/3。因此,只投票一次(2/3)的誠實節(jié)點的數(shù)量將恰好占總投票數(shù)的50%。這樣,為了獲得大多數(shù)誠實投票并達成共識,誠實節(jié)點的數(shù)量至少應該是驗證器總數(shù)的“2/3 +1”。
共識算法的階段
在現(xiàn)代區(qū)塊鏈操作中,用戶對系統(tǒng)速度和性能的期望很高。經(jīng)典的算法解決方案沒有提供這些特性。我們回顧了其他幾個升級的替代方案,但是它們也不能完全滿足我們的研究團隊,因為這些算法不能滿足專家對框架的所有要求。因此,我們開發(fā)了自己的算法。
Exonum的共識算法依賴于inTendermint提出的一些思想。然而,它包含了許多特性,使它有別于Tendermint和其他用于基于區(qū)塊鏈的解決方案的一致算法。
下面我們將討論Exonum共識算法的機制。一般來說,計劃如下:
達成一致意見的過程首先由一個領導節(jié)點(一個領導者)形成一個必須添加到區(qū)塊鏈的交易列表(創(chuàng)建一個建議)。領導者是通過一個單獨的算法來選擇的。根據(jù)我們的算法,領導者每輪都會改變。然后,將提案通過網(wǎng)絡廣播到驗證器節(jié)點(驗證器)。
驗證器檢查接收到的消息是否與序列化格式相對應。如果出現(xiàn)錯誤,節(jié)點將完全忽略接收到的消息。例如,驗證器忽略向區(qū)塊鏈中間添加塊或復制已存在事務的建議。如果一切就緒,那么投票階段就開始了。
提案獲得驗證者2/3以上批準的節(jié)點,將失去對其他驗證者提案投票的機會,并且無法更改自己的提案。這種狀態(tài)稱為鎖的驗證。
在領導者從驗證器收集到所需的投票數(shù)之后,它將批準的交易放入一個塊中,并廣播一條特殊的消息——precommit。
precommit包含更新后的區(qū)塊鏈狀態(tài)的哈希值,指示節(jié)點準備將建議的塊添加到區(qū)塊鏈。當大多數(shù)驗證器響應類似的預提交消息時(使用相同的哈希值),塊就被添加到區(qū)塊鏈中。達成一致意見,并對隨后的每個塊重復該過程。
為了提高系統(tǒng)的穩(wěn)定性,驗證器之間會周期性地交換和阻塞消息。如果節(jié)點缺少任何事務數(shù)據(jù),則需要使用前者。后者用于將關于一個事務塊的信息傳輸?shù)揭粋€滯后節(jié)點(例如,節(jié)點關閉了一段時間)。這允許同步整個網(wǎng)絡的工作。
所提出的共識性算法對每個高度都是正確的,即滿足了活動性、一致性和抗審查性。共識屬性的正式證明可以在我們的白皮書中找到。
性能測試
為了評估Exonum共識性算法的效率,我們檢查了區(qū)塊鏈如何使用它使用兩種配置。這些配置包括一個數(shù)據(jù)中心和幾個地理上分布的數(shù)據(jù)中心。在測試期間,對不同數(shù)量的驗證器估計了TPS參數(shù)(每秒交易數(shù))。下面的圖表顯示了使用加密貨幣的區(qū)塊鏈(黑色圖表)和使用時間戳的區(qū)塊鏈(藍色圖表)中的網(wǎng)絡性能變化。
TPS是單個數(shù)據(jù)中心中驗證器數(shù)量的函數(shù)
TPS是多個數(shù)據(jù)中心中驗證器數(shù)量的函數(shù)
根據(jù)網(wǎng)絡配置的不同,Exonum及其針對區(qū)塊鏈的新拜占庭容錯共識性算法平均每秒可以處理2,000到13,000個交易。在生產(chǎn)解決方案方面,該算法可以在全球分布式網(wǎng)絡上以0.5秒的塊接受時間每秒處理4000個交易。Exonum的性能在出現(xiàn)故障停止驗證器時是穩(wěn)定的,但是隨著驗證器總數(shù)的增加,Exonum的性能會顯著下降。(考拉)