請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8122
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 廖世偉(Shih-Wei Liao) | |
dc.contributor.author | Yen-Chih Liao | en |
dc.contributor.author | 廖彥智 | zh_TW |
dc.date.accessioned | 2021-05-20T00:49:04Z | - |
dc.date.available | 2021-02-19 | |
dc.date.available | 2021-05-20T00:49:04Z | - |
dc.date.copyright | 2021-02-19 | |
dc.date.issued | 2021 | |
dc.date.submitted | 2021-02-18 | |
dc.identifier.citation | [1] livelock issue. https://github.com/tendermint/tendermint/issues/1047. Accessed: 20210107. [2] Stellar network api. https://api.stellarbeat.io/v1/network/ stellar-public. Accessed: 20210115. [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. AbdElMalek, G. R. Ganger, G. R. Goodson, M. K. Reiter, and J. J. Wylie. Faultscalable byzantine faulttolerant services. ACM SIGOPS Operating Systems Review, 39(5):59–74, 2005. [5] Y. AmoussouGuenou, A. Del Pozzo, M. PotopButucaru, and S. Tucci Piergiovanni. Dissecting tendermint. In International Conference on Networked Systems, pages 166–182. Springer, 2019. [6] E. Buchman. Tendermint: Byzantine fault tolerance in the age of blockchains. PhD thesis, 2016. [7] J. Cowling, D. Myers, B. Liskov, R. Rodrigues, and L. Shrira. Hq replication: A hybrid quorum protocol for byzantine fault tolerance. In Proceedings of the 7th symposium on Operating systems design and implementation, pages 177–190, 2006. [8] C. Dwork, N. Lynch, and L. Stockmeyer. Consensus in the presence of partial syn chrony. Journal of the ACM (JACM), 35(2):288–323, 1988. [9] M.J.Fischer,N.A.Lynch,andM.S.Paterson.Impossibilityofdistributedconsensus with one faulty process. Journal of the ACM (JACM), 32(2):374–382, 1985. [10] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: speculative byzantine fault tolerance. In Proceedings of twentyfirst ACM SIGOPS symposium on Operating systems principles, pages 45–58, 2007. [11] J. Kwon. Tendermint: Consensus without mining. Draft v. 0.6, fall, 1(11), 2014. [12] L.Lamport.Theparttimeparliament.InConcurrency:theWorksofLeslieLamport, pages 277–317, 2019. [13] J. Li and D. Maziéres. Beyond onethird faulty replicas in byzantine fault tolerant systems. In NSDI, 2007. [14] G. Losa, E. Gafni, and D. Mazières. Stellar consensus by instantiation. In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss DagstuhlLeibnizZentrum fuer Informatik, 2019. [15] D. Mazières. The Stellar Consensus Protocol: A Federated Model for Internetlevel Consensus, 2015. [16] S. Nakamoto. Bitcoin: A peertopeer electronic cash system. Technical report, Manubot, 2019. [17] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999. [18] R.PassandE.Shi.Thunderella: Blockchains with optimistic instant confirmation.In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 3–33. Springer, 2018. [19] M.Yin,D.Malkhi,M.K.Reiter,G.G.Gueta,andI.Abraham.Hotstuff:Bft consensus with linearity and responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 347–356, 2019. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/8122 | - |
dc.description.abstract | 共識演算法已經經歷了數十年的研究,且被廣泛的使用在各種分散式系統當 中,他在區塊鏈中也就想當然地佔據了一個關鍵的環節。不同的共識演算法都有 不盡相同的優點以及缺點,也因此適用的範疇也不盡相同。由恆星發展基金會所 提出的聯合拜占庭容錯共識系統便是一種較為獨特的共識設定。這個共識系統賦 予了相較於一般其他拜占庭容錯的複製狀態機任意選擇所信任的節點的彈性,但 是也因為這個彈性的選擇權,實作聯合拜占庭容錯共識系統的恆星共識協定需要 採用以投票為基的協定經由額外的幾輪訊息交換作為犧牲才能達成共識。 在本篇研究中,藉由引入以視域為基的拜占庭共識演算法以及恆星共識協定 當中的部分功能,達到能在不存在所有人共同直接信任的領袖的情況下藉由推舉 領袖來產稱提案的方法。藉此,該以視域為基底的聯合拜占庭容錯共識系統就成 為了一個更加簡單且容易理解的聯合拜占庭容錯共識系統。 我們展示了本研究的做法只要作惡的節點不超過總結點數的 7% 就能比同為 聯合拜占庭容錯共識系統實作的恆星共識協定更有效率,儘管 7% 出錯比率下才 有比較好的效能在具有高達三分之一容錯的演算法當中顯得較為嚴苛,具有高公 信力節點的系統,好比政府部門或是知名公司等比較不會違規的單位就能採用本 篇研究的演算法以獲得更高的吞吐量;相反的,如果是預期會變得更多元的系統, 或只是系統內的互信基礎較為薄弱的話,就應該優先採用原本的恆星共識協定。 | zh_TW |
dc.description.abstract | Consensus algorithms have been researched for decades and they are crucial to a variety 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 different 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 ballotbased protocol as a tradeoff. This study introduces a new methodology, viewbased FBAS(vFBAS), which adopts certain functions from both viewbased 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. | en |
dc.description.provenance | Made available in DSpace on 2021-05-20T00:49:04Z (GMT). No. of bitstreams: 1 U0001-1702202111162100.pdf: 1119465 bytes, checksum: b11bcb3b1424cf2c667ba269d33c465b (MD5) Previous issue date: 2021 | en |
dc.description.tableofcontents | Verification Letter from the Oral Examination Committee i Acknowledgements i 摘要 iii Abstract v Contents vii List of Figures ix List of Tables xi Chapter 1 Introduction 1 Chapter 2 Related Work 5 2.1 PBFT 6 2.2 Tendermint 6 2.3 HotStuff 7 2.4 FBAS 8 2.5 SCP 9 Chapter 3 View-based FBAS 13 3.1 Modified Nomination Protocol 13 3.1.1 Original nomination protocol 14 3.1.2 The modification 15 3.1.3 Differences 16 3.2 Adopting view-based variants 17 3.2.1 View-based variants 17 3.2.2 Adopting 19 Chapter 4 Experiments 23 Chapter 5 Conclusions 29 References 31 | |
dc.language.iso | zh-TW | |
dc.title | 以視域為基底的聯合拜占庭容錯共識系統 | zh_TW |
dc.title | View-Based Federated Byzantine Agreement System | en |
dc.type | Thesis | |
dc.date.schoolyear | 109-1 | |
dc.description.degree | 碩士 | |
dc.contributor.author-orcid | 0000-0001-8235-4133 | |
dc.contributor.oralexamcommittee | 周承復(Cheng-Fu Chou),池明洋(Ming-Yang Chih),許孟祥(Meng-Hsiang Hsu),黃敬群(Ching-Chun Huang) | |
dc.subject.keyword | 區塊鏈,恆星共識協定,聯合拜占庭容錯共識系統,共識演算法, | zh_TW |
dc.subject.keyword | Blockchain,SCP,FBAS,consensus algorithm, | en |
dc.relation.page | 33 | |
dc.identifier.doi | 10.6342/NTU202100717 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2021-02-18 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊網路與多媒體研究所 | zh_TW |
顯示於系所單位: | 資訊網路與多媒體研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
U0001-1702202111162100.pdf | 1.09 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。