學術專欄——Harmony快速拜占庭容錯_區塊鏈

在過去的一個月里，我們一直致力于我們的視圖更改協議。這是任何區塊鏈的核心部分，我們可以從中判斷協議是經過許可的還是無許可的，以及它是如何實現去中心化。

代碼在這里：harmony/consensus。?

我們在6月28日在4個分片上推出了DayONE主網，共有600個節點。在過去的830,000個區塊中，它一直運行順暢。

在我們之前的測試中，我們觀察到由于網絡狀況不佳而在某些分片中發生了視圖更改。我們還通過殺死領導者節點以及其他類型的攻擊來手動觸發視圖更改。攻擊發生后視圖發生了變化，網絡按預期繼續運行?-耶！！

在下文中，我們將首先解釋拜占庭容錯的基本概念，然后我們會介紹如何做出改進使得能夠在實踐中處理大量節點，最后介紹一下整體的代碼結構和一些實現細節。

什么是拜占庭容錯？

一個分布式系統是由多個節點組成，其中每個節點都是獨立的服務器。它們通過網絡發送消息并根據它們遵循的協議執行某些任務來相互通信。

這個過程中會出現很多類型的錯誤的類型，但它們基本上可以分為兩大類。第一種錯誤是節點崩潰、網絡故障、丟包等，這種錯誤類型的節點是沒有惡意的，屬于非拜占庭錯誤。

第二種類型是節點可能是惡意的。它們可以任意行動，不遵守協議規則。例如，驗證器可以延遲或拒絕中繼網絡中的消息、領導者可以提出無效塊、或者節點可以向不同的對等體發送不同的消息。在最壞的情況下，惡意節點可能會相互協作。這些被稱為拜占庭錯誤。

考慮到這兩種錯誤，我們希望系統始終能夠保持兩個屬性：一致性(consistency)和活性(liveness)。

在區塊鏈術語中，一致性意味著誠實的節點必須為任何給定的塊數/高度提交相同的塊；活性意味著鏈高度必須保持增長而不會停滯。

一個被許可的網絡中只會出現第一類錯誤，這比較容易解決。例如，我們可以選擇一個性能很強的節點作為領導者，所有其他節點將只聽取領導者廣播的內容并信任領導者建議的任何塊。在這種情況下，我們只需要注意第一類錯誤，特別是當錯誤發生在領導者身上時。

聲音 | 中國人民大學曲強：學術界目前不主張馬上將數字貨幣應用于國內市場:金色財經報道，中國人民大學國際貨幣研究所所長助理曲強表示，實際上，學術界目前不主張馬上將數字貨幣應用于國內市場，央行也很慎重，因為這是一條沒有人走過的路。數字貨幣發行會不會導致貨幣乘數下降？影響信貸貨幣怎么辦？很多問題還需解決。目前，應用數字貨幣做跨境支付比較現實。在海外，通過數字貨幣可以跳過西方主導的金融轉賬系統。其中數字貨幣的作用類似跨境記賬憑證，這是數字貨幣目前比較穩妥的應用途徑。央行發行法定數字貨幣，一定會保證商業銀行運行穩定。[2019/12/28]

對于去中心化的網絡，我們不能信任任何節點，因為第二種錯誤可能發生在任何節點中。這樣我們只能基于一個基本假設，即惡意節點無法偽造其他節點的簽名。密碼學理論證明偽造簽名的難度非常高，以至于今天的計算機在任何的實際時間長度內都無法破解。當量子計算機準備就緒時，情況可能會改變。但那時，我們將使用量子抗性加密算法。

拜占庭容錯協議是一種即使系統中存在惡意節點也能保證分布式系統的一致性和活性的協議。所有這些協議都有一個基本假設，即惡意節點的數量小于某個閾值。這很容易理解，如果有超過50％的惡意節點，那么網絡完全由惡意節點控制。

比特幣的工作量證明要求不到50％的節點是惡意的。然而，自私挖礦將基本假設降低到25％。當只有少于在總計算能力小于25％的節點（是惡意的，PoW系統才是安全的。

在傳統的分布式系統中有著對拜占庭容錯協議深入的研究。事實證明，在Lamport的經典論文中，惡意節點應少于網絡的33％。后來，著名的實用拜占庭容錯論文讓這種系統變得可實用化。

但是，依然還有兩個問題。首先，這樣的系統是經過許可的，不允許任意節點加入和離開。其次，它不能擴展到超過數百個節點。第一個問題源于女巫攻擊，惡意用戶可以輕松創建許多假身份并接管大部分網絡。不過，這個問題首先在中本村的比特幣白皮書中被解決了，主要是從經濟效應的角度考量。在工作量證明之后，有許多新的設計，例如股權證明，權威證明等。我們不計算節點的數量，而是計算投票權的數量。在PoS中，節點的投票能力與其放樣量(staking)成比例。第二個問題可以通過使用BLS簽名方案的聚合簽名解決，這在FBFT部分中有解釋。

動態 | 阿聯酋大學推出區塊鏈應用程序來管理學術憑證:據itp報道，阿聯酋大學（UAEU）推出區塊鏈應用程序，來管理和共享憑證，如成績單和文憑等，使用戶可以輕松申請工作以及研究機會等。[2019/2/20]

實用拜占庭容錯

像Raft和Paxos這樣的協議主要用于處理第一類系統錯誤。實用拜占庭容錯算法是現實世界里首批能夠同時處理第一類和第二類錯誤的拜占庭容錯協議之一。

我們將始終假設有N個節點最多有f個惡意節點，其中N=3f1。PBFT中有兩種模式，即普通共識模式和視圖更改模式。正常模式看起來像這樣：

在一個視圖中，有3個步驟/階段：預先準備、準備和提交。

1.在預準備階段，領導者將向其他節點廣播宣布消息(announcemessage)。當驗證者收到宣布消息時，它進入準備階段。

2.在準備階段，在驗證者接收到宣布消息之后，它將向每個節點廣播準備消息。當驗證者收到足夠的準備消息時，它將進入提交階段。

3.在提交階段，驗證者將發送提交消息當驗證者收到足夠的提交消息時。它可以安全地提交區塊。這結束了一輪正常的共識過程。

請注意，一般PBFT和區塊鏈PBFT之間存在一些差異。主要區別在于區塊鏈在兩個區塊之間是“同步的”，即我們不能在提交h(區塊號)之前繼續提交區塊h1。在傳統的PBFT中，我們可以在請求h之前提交客戶請求h1。PBFT將保證所有節點的一致性。

從這個意義上說，區塊鏈使共識過程更簡單。確切地說，PBFT中有一個被稱為“檢查點過程”的步驟。檢查點(checkpoint)是一個證書，其中序列號小于或等于檢查點的區塊都被視作已經最終確定，不可更改。在區塊鏈中，每個已經確定的區塊，都可以被視為檢查點。

當驗證者在共識超時之前，如果還沒有提交新塊，驗證器將開始發送視圖更改信息，每個驗證者都會選擇一樣的新的領導者。如果視圖更改無法在超時之前完成，則驗證者將建議另一個新的視圖更改。

視圖更改模式有兩個步驟/階段：

動態 | Blocktech和亞美尼亞法語機構合作推出區塊鏈學術實驗室:據armradio消息，總部位于紐約的區塊鏈技術公司Blocktech和亞美尼亞法語高等教育機構French University of Armenia（UFAR）宣布將合作推出亞美尼亞首個學術區塊鏈實驗室。[2018/11/8]

1.驗證者通過向新領導者發送包含≥2f1個準備消息的視圖更改消息來啟動視圖更改。如果它并沒有收到足夠的準備消息，它只需發送空的視圖更改消息，給新的領導者。

2.新領導者收集足夠的視圖更改消息并廣播接收到的所有視圖更改消息。然后新領導者切換到正常模式。驗證在收到來自新領導者的新視圖消息時切換到正常模式，同時停止視圖更改計時器并啟動共識計時器。如果驗證程序在視圖更改超時之前未收到新的視圖消息，則會將viewID增加1并開始另一個新的視圖更改。

視圖更改可以確保網絡的活性。在視圖更改過程中，我們需要確保提交的區塊在整個視圖更改中也是一致的。簡單來說，接收2f1準備消息(preparemessage)只能確保同一視圖中的一致性。接收2f1個提交消息(commitmessage)可確保不同視圖之間的一致性。當節點收到2f1提交消息時，它可以安全地將塊提交到區塊鏈中。PBFT協議確保即使在視圖更改的情況下，任何誠實節點都提交相同的區塊。

一致性和活性

PBFT的一個關鍵概念是法定人數。法定人數是具有至少2f1個節點的任何子集。由于總共有3f1個節點，因此任何兩個法定人數將至少有f1個節點相交。因為最多有f個惡意節點，故在兩個法定人數的交集中將至少包含一個誠實節點。這就是我們需要法定人數來采取任何行動的原因。

一個視圖中的一致性指的是：假設一個節點收到2f1準備消息，這些2f1個節點將形成一個法定人數。請注意，任何兩個法定人數中將至少有一個共同的誠實節點，這意味著任何兩個這樣的法定人數在其準備消息中不能包含不同的區塊哈希，否則共同的誠實節點允許兩個相同高度的不同區塊，這與它誠實的事實相矛盾。

動態 | 韓國生產力協會與企業和學術界共同創辦區塊鏈管理協會:據chosun消息，近日韓國首爾鐘路區舉行了“區塊鏈精英協會”成立儀式，該協會成立是為了建立生態系統和促進商業發展。協會今后目的是開發企業技術，并設法解決因扭曲區塊鏈商業化的社會問題。此外，同時引入業務模式，提供區塊鏈技術的咨詢，并推出定制化的培訓和區塊鏈認證評估服務。[2018/10/21]

不同視圖的一致性指的是：假設一個節點收到2f1提交消息，這些2f1個節點形成一個法定人數，將其表示為Q1。當一個誠實的節點開始視圖更改時，它會將準備好的消息發送給新的領導者。新領導者需要收集2f1個視圖更改消息才能發送新的試圖消息。Q1和Q2再次包含至少一個誠實節點。此節點包含2f1個準備消息，因為它在發送其提交消息之前必須先收到了足夠的準備消息。這確保了不同視圖中的誠實節點將提交相同的區塊。

活性?：每個節點都有一個用于正常共識過程的計時器和用于視圖更改過程的計時器。當計時器超時時，節點將通過增加一個視圖來啟動視圖更改。在連續的領導者未能發送正確的新視圖消息的情況下，視圖更改計時器的超時時段將增加，以避免頻繁的視圖更改并確保最終足夠的誠實節點將與誠實的新領導者具有相同的viewID。

快速拜占庭容錯

作為對PBFT的改進，Harmony的共識協議在通信復雜性方面是線性可擴展的，因此我們將其稱為快速拜占庭容錯。在FBFT中，領導者不是要求所有驗證者廣播他們的投票，而是運行多簽名的簽名過程以在O(1)大小的多簽名中收集驗證者的投票，然后廣而播之。因此，和接收O(N)簽名不同，每個驗證器僅接收一個多簽名，從而將通信復雜度從O(N2)減小到O(N)。通過對視圖更改消息的一些修改，視圖改變復雜度也可以減少到O(N)。

BLS簽名方案

在這里，我們對Boneh-Lynn-Shacham簽名方案進行了非常簡短的數學介紹，這是FBFT和PBFT之間的主要區別。BLS簽名方案基于橢圓曲線配對。令E(Fp)為有限域Fp上的橢圓曲線，其中p為大質數。我們在此曲線上選擇一個基本參考點g。私有BLS密鑰是從Fp采樣的隨機數α，公鑰是α?g，是橢圓曲線E上的一個點。給定一個消息m，簽名計算為σ=α?H(m)，這也是E上一個點，其中H是哈希到E的函數。在兩條橢圓曲線E1和E2上的雙線性映射e滿足一下情況：

瑞士將利用區塊鏈技術核實學術證書:5月23日， Finance Magnates報道稱，瑞士正在實施一個將使用區塊鏈技術保護和核實學術資格的新項目。這一項目由巴塞爾大學創新金融中心和一家名為Proxeus金融科技公司合作進行。[2018/5/24]

e(α?g1,g2)=e(g1,α?g2),g1∈E1,g2∈E2

e(g0g1,g2)=e(g0,g2)e(g1,g2),g0,g1∈E1,g2∈E2

e(g1,g2g3)=e(g1,g2)e(g1,g3),g1∈E1,g2,g3∈E2

現在我們可以看到如何通過聚合公鑰來驗證k個簽名。

e(g1,σ1?σk)=e(g1,α1?H(m)?αk?H(m))

=e(α1?g1?αk?g1,H(m))

請注意，聚合簽名就是一個普通簽名，也就是橢圓曲線上的一個點，聚合公鑰就是一個普通公鑰，也是橢圓曲線上的一個點。這將2f1簽名簡化為僅1個聚合簽名，這對于減少共識協議中的網絡流量至關重要。

正常模式

在傳統的PBFT中，節點在每輪共識中發送或接收的總消息大小是O(N2)。這是因為在準備和提交階段，每個節點需要收集2f1=O(N)個簽名并將它們廣播到網絡中的每個節點。通過使用BLS簽名方案，我們將2f1個簽名聚合成一個簽名，這樣，準備和提交階段的消息大小為O(1)，從而將總大小從O(N2)減少到O(1)回合。為了從BLS方案中受益，每個驗證器將僅向領導者發送準備和提交消息，并且領導者負責收集足夠的>=2f1個簽名并將它們聚合成一個聚合簽名，之后領導者分別在準備/提交階段發送準備好/已提交的消息。從領導者的角度來看，這三個階段是同步的，但從驗證者的角度來看，他們仍然可以不按順序接收消息，例如：驗證者可以在宣布消息之前接收準備好的消息，但是在這種情況下，其準備簽名將不會在準備好的消息中包含。

正常模式分為三個階段：

1.在宣布階段，領導者將向驗證者廣播宣布消息。當驗證器收到宣布消息時，它進入準備階段

2.在準備階段，驗證器向領導者發送準備消息。當領導者收到足夠多的準備消息時，它會聚合從驗證者收到的準備消息上的簽名，并發出準備好的消息，其中包含聚合的準備簽名。然后領導者進入提交階段。驗證器在收到來自領導者的準備好的消息時進入提交階段。

3.在提交階段，驗證器向leader發送提交消息。當領導者收到足夠的提交消息時，它會聚合從驗證器接收的提交消息的簽名，并發出提交消息，其中包含聚合的提交簽名。然后領導者完成一個視圖/回合。驗證器在收到已提交的消息后完成一個視圖/回合。當領導者或驗證者完成一輪時，它將重新啟動共識計時器。

在步驟3，也就是提交階段，驗證者在blockNum和blockHash上發送帶有簽名的提交消息。這可用于新加入網絡的節點確認它是否和當前網絡同步，同時不至于被惡意領導者欺騙。在狀態同步模式部分中解釋了共識過程如何與狀態同步進行交互。

領導者選舉

驗證程序啟動視圖更改過程有兩個原因。一個原因是當驗證器檢測到領導者在一個視圖中提出兩個不同的宣布消息時，它將立即開始視圖更改。另一個原因是驗證者在超時后沒有任何進展。有兩種超時：正常共識模式下的超時和視圖更改模式下的超時。

在我們的區塊鏈中，我們有了epoch的概念。每個epoch包含X個塊。在每個epoch的開始階段，委員會成員都是由在信標鏈中為這個epoch下注的人決定的。委員會成員的順序由該時期的VDF隨機性唯一確定。在一個epoch中，委員會將始終保持不變。假設順序列表是，然后在epoch一開始，領導者是v0。如果發生視圖更改，則下一個領導者是v1，依此類推。在這里，我們假設每個驗證者具有相同的投票權。

視圖更改模式

視圖更改過程如下：

1.當共識定時器超時，節點通過向新的領導者發送包括視圖ID(viewID)和準備好(preparedmessage)的消息的視圖更改消息來開始視圖更改。如果它沒有收到準備好的消息，那它就只是發送空的視圖更改消息，只包括viewID上的簽名但不包括準備好的消息。

2.當新領導者收到足夠的視圖更改消息時，它會聚合viewID的簽名，并從視圖更改消息中選擇一個準備好的消息。它廣播新的視圖消息，包括聚合簽名以及選擇出的準備消息。然后新領導者切換到正常共識模式。驗證者在收到來自新領導者的新視圖消息時切換到正常共識節點，同時停止視圖更改計時器并啟動共識計時器。如果驗證程序在視圖更改超時之前未收到新的視圖消息，則會將viewID增加1并開始另一個新的視圖更改。

第二步要求每個驗證器在viewID上發送簽名。目的是用于防備惡意領導者。確切地說，前一個領導者可以在準備階段向不同的驗證者發送不同的聚合簽名。只要聚合簽名有效，驗證器就會接受它并在發生視圖更改時提出它。在這種情況下，每個視圖更改消息都包含不同的簽名，新領導者不能進行簽名聚合，所以新視圖消息的大小為O(N)，這是因為新的領導者必須證明接收到足夠的有效視圖更改消息。如果每個人都在viewID上簽名，新的領導者很容易聚集簽名，這樣可以將新的試圖消息的大小減少到O(1)。只有這樣，我們才能在視圖更改的情況下擴大網絡中的節點數量。

狀態同步模式

我們允許節點在區塊鏈中自由加入和離開。當新節點加入共識時，它必須先進行狀態同步，然后才能驗證共識消息。此外，還存在節點在視圖更改模式下卡住的情況。例如，當驗證程序網絡連接速度較慢時，可能無法在超時之前取得任何進展。在這種情況下，它將開始視圖更改。但是，它無法從視圖更改模式中退出，因為所有其他節點都在向前移動，視圖更改會失敗。在這種情況下，此節點需要執行狀態同步才能趕上。

基本過程很簡單。節點通過將其當前塊高度和已提交消息中的最新塊高度進行比較，如果檢測出它不同步時，它將切換到狀態同步模式并開始執行狀態同步。完成狀態同步后，它會切換到正常模式。

為了在狀態同步完成后加入共識，節點需要知道誰是當前的領導者以及當前的viewID是什么。一種解決方案是盲目地接受來自共識消息的領導者和viewID。這種方法使惡意領導者有機會在共識消息中發送很大的viewID，強制使得每個驗證者開始狀態同步。更好的方法是僅在接收提交消息的時候接受領導者和viewID信息。在這種情況下，惡意領導者不能欺騙新節點。但它減緩了新節點加入共識的過程，因為在更新領導者和viewID之前，它無法驗證宣布消息和準備好的消息。我們選擇的方法是將領導者和viewID信息添加到區塊頭中。當節點完成狀態同步時，它可以從最新的區塊頭中讀取信息。如果在狀態同步期間發生視圖更改，那么來自最新塊的信息已經過時。在這種情況下，新節點在收到提交的消息時通過更新領導者和viewID信息仍然可以得到最新的信息。

狀態轉換

下圖是驗證器的狀態轉換圖。?領導者的狀態轉換相對比較簡單在此省略。

有5種模式：3種正常模式，視圖更改模式和狀態同步模式。

模式之間的轉換由不同的條件觸發，例如接收特定類型的消息或滿足某些條件，如超時。

條件列表：am，pm，cm，tc，to，nv，is，os。

歡迎大家掃碼加社群管理員好友，進入官方微信群，了解Harmony最新動向！

Tags：區塊鏈VIEVIEWBFT區塊鏈dapp開發公司Xaviera TechBscviewbft幣價格

Ethereum