以視域為基底的聯合拜占庭容錯共識系統

View-­Based Federated Byzantine Agreement System

廖彥智(Yen-Chih Liao)

指導教授 ： 廖世偉

國立臺灣大學/電機資訊學院/資訊網路與多媒體研究所/碩士(2021年)

https://doi.org/10.6342/NTU202100717

摘要

共識演算法已經經歷了數十年的研究，且被廣泛的使用在各種分散式系統當 中，他在區塊鏈中也就想當然地佔據了一個關鍵的環節。不同的共識演算法都有 不盡相同的優點以及缺點，也因此適用的範疇也不盡相同。由恆星發展基金會所 提出的聯合拜占庭容錯共識系統便是一種較為獨特的共識設定。這個共識系統賦 予了相較於一般其他拜占庭容錯的複製狀態機任意選擇所信任的節點的彈性，但 是也因為這個彈性的選擇權，實作聯合拜占庭容錯共識系統的恆星共識協定需要 採用以投票為基的協定經由額外的幾輪訊息交換作為犧牲才能達成共識。
在本篇研究中，藉由引入以視域為基的拜占庭共識演算法以及恆星共識協定 當中的部分功能，達到能在不存在所有人共同直接信任的領袖的情況下藉由推舉 領袖來產稱提案的方法。藉此，該以視域為基底的聯合拜占庭容錯共識系統就成 為了一個更加簡單且容易理解的聯合拜占庭容錯共識系統。
我們展示了本研究的做法只要作惡的節點不超過總結點數的 7% 就能比同為 聯合拜占庭容錯共識系統實作的恆星共識協定更有效率，儘管 7% 出錯比率下才 有比較好的效能在具有高達三分之一容錯的演算法當中顯得較為嚴苛，具有高公 信力節點的系統，好比政府部門或是知名公司等比較不會違規的單位就能採用本 篇研究的演算法以獲得更高的吞吐量;相反的，如果是預期會變得更多元的系統， 或只是系統內的互信基礎較為薄弱的話，就應該優先採用原本的恆星共識協定。

關鍵字

區塊鏈 ； 恆星共識協定 ； 聯合拜占庭容錯共識系統 ； 共識演算法

並列摘要

Consensus algorithms have been researched for decades and they are crucial to a va­riety of a distributed system. Needless to say, consensus algorithms are also a critical part of the blockchain. Each of them has its advantages and disadvantages and is suitable for dif­ferent applications. The Federated Byzantine Agreement System(FBAS)[15] introduced by Stellar foundation is one of consensus algorithm frameworks that has a rather unique setting. It is a Byzantine Fault Tolerant(BFT) state machine replica(SMR) which allows nodes to choose whoever they want to trust compared to its counterparts. Due to this flexibility, the Stellar Consensus Protocol(SCP), which is an implementation of FBAS by Stellar foundation, requires a few more rounds of message exchange by adopting a ballot­based protocol as a trade­off.
This study introduces a new methodology, view­based FBAS(vFBAS), which adopts certain functions from both view­based BFT algorithms and SCP in order to generate a faster proposal by electing a leader when there is no unanimously trusted leader. By doing so, this work turns out to be a less complex and easier to be understood version of FBAS implementation.
We show that vFBAS can be a more efficient version of FBAS implementation than SCP when the faulty nodes consist of less than 7% of the network. Although the 7% mark for this work to perform better is rather strict considering the algorithm is designed to hold up to less than a third of faulty behaviors. Networks with nodes that hold high credibility such as government or renowned companies, which are less likely to break the rules, could adapt vFBAS for higher throughput. On the other hand, networks that expect to have more variety or networks that have less mutual trust should adopt the original SCP.

並列關鍵字

Blockchain ； SCP ； FBAS ； consensus algorithm

參考文獻

[1] livelock issue. https://github.com/tendermint/tendermint/issues/1047. Accessed: 2021­01­07.

[2] Stellar network api. https://api.stellarbeat.io/v1/network/ stellar-public. Accessed: 2021­01­15.

[3] Ukraine government picks stellar development foundation to help build national digital currency. https://finance.yahoo.com/news/ ukraine-government-picks-stellar-help-140028973.html.

[4] M. Abd­El­Malek, G. R. Ganger, G. R. Goodson, M. K. Reiter, and J. J. Wylie. Fault­scalable byzantine fault­tolerant services. ACM SIGOPS Operating Systems Review, 39(5):59–74, 2005.

[5] Y. Amoussou­Guenou, A. Del Pozzo, M. Potop­Butucaru, and S. Tucci­ Piergiovanni. Dissecting tendermint. In International Conference on Networked Systems, pages 166–182. Springer, 2019.