請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74300
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 蕭旭君(Hsu-Chun Hsiao) | |
dc.contributor.author | Tzu-Wei Chao | en |
dc.contributor.author | 趙子為 | zh_TW |
dc.date.accessioned | 2021-06-17T08:28:42Z | - |
dc.date.available | 2019-08-19 | |
dc.date.copyright | 2019-08-19 | |
dc.date.issued | 2019 | |
dc.date.submitted | 2019-08-12 | |
dc.identifier.citation | [1] General consensus platform. https://github.com/CheshireCatNick/consensus-simulator. Accessed: 2017-06-30.
[2] Hyperledger sawtooth pbft. https://github.com/hyperledger/sawtooth-pbft. Accessed: 2017-06-30. [3] Tendermint. https://tendermint.com/. Accessed: 2017-06-30. [4] I. Abraham, S. Devadas, D. Dolev, K. Nayak, and L. Ren. Synchronous byzantine agreement with expected O(1) rounds, expected O(n2) communication, and optimal resilience. IACR Cryptology ePrint Archive, 2018:1028, 2018. [5] M. Apostolaki, A. Zohar, and L. Vanbever. Hijacking bitcoin: Routing attacks on cryptocurrencies. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017, pages 375–392. IEEE Computer Society, 2017. [6] S. Bano, A. Sonnino, M. Al-Bassam, S. Azouvi, P. McCorry, S. Meiklejohn, and G. Danezis. Consensus in the age of blockchains. CoRR, abs/1711.03936, 2017. [7] G. Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130–143, 1987. [8] V. Buterin. Ethereum: A next-generation smart contract and decentralized application platform. 2014. [9] C. Cachin, K. Kursawe, and V. Shoup. Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography. J. Cryptology, 18(3):219–246, 2005. [10] C. Cachin and M. Vukolic. Blockchain consensus protocols in the wild. CoRR, abs/1707.01873, 2017. [11] M. Castro and B. Liskov. Practical byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI ’99, pages 173–186, Berkeley, CA, USA, 1999. USENIX Association. [12] T. H. Chan, R. Pass, and E. Shi. Communication-efficient byzantine agreement without erasures. CoRR, abs/1805.03391, 2018. [13] T.-W. Chao, H. Chung, and P.-C. Kuo. Fair Byzantine Agreements for Blockchains. arXiv e-prints, page arXiv:1907.03437, Jul 2019. [14] J. Chen, S. Gorbunov, S. Micali, and G. Vlachos. Algorand agreement: Super fast and partition resilient byzantine agreement. IACR Cryptology ePrint Archive, 2018:377, 2018. [15] A. Clement, E. L. Wong, L. Alvisi, M. Dahlin, and M. Marchetti. Making byzantine fault tolerant systems tolerate byzantine faults. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2009, April 22-24, 2009, Boston, MA, USA, pages 153–168. USENIX Association, 2009. [16] M. J. Fischer, N. A. Lynch, and M. Paterson. Impossibility of distributed consensus with one faulty process. In Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983, Colony Square Hotel, Atlanta, Georgia, USA, pages 1–7, 1983. [17] J. A. Garay and A. Kiayias. Sok: A consensus taxonomy in the blockchain era. IACR Cryptology ePrint Archive, 2018:754, 2018. [18] A. Gervais, G. O. Karame, K. Wüst, V. Glykantzis, H. Ritzdorf, and S. Capkun. On the security and performance of proof of work blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 3–16. ACM, 2016. [19] T. Hanke, M. Movahedi, and D. Williams. Dfinity technology overview seriesconsensus system. Whitepaper. https://dfinity.org/pdfviewer/pdfs/viewer?file=../library/dfinity-consensus.pdf. [20] L. Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133–169, 1998. [21] L. Lamport, R. E. Shostak, and M. C. Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982. [22] A. M. Law. Simulation Modeling and Analysis 5th Edition. McGraw-Hill Education, 2014. [23] K. Lee and H. T. Ewe. Performance study of byzantine agreement protocol with artificial neural network. Inf. Sci., 177(21):4785–4798, 2007. [24] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song. The honey badger of BFT protocols. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 31–42. ACM, 2016. [25] S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. [26] D. Ongaro and J. K. Ousterhout. In search of an understandable consensus algorithm. In 2014 USENIX Annual Technical Conference, USENIX ATC ’14, Philadelphia, PA, USA, June 19-20, 2014., pages 305–319. USENIX Association, 2014. [27] R. Pass and E. Shi. Hybrid consensus: Efficient consensus in the permissionless model. In 31st International Symposium on Distributed Computing, DISC 2017, October 16-20, 2017, Vienna, Austria, volume 91 of LIPIcs, pages 39:1–39:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. [28] R. Pass and E. Shi. Thunderella: Blockchains with optimistic instant confirmation. In Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, pages 3–33, 2018. [29] A. Singh, T. Das, P. Maniatis, P. Druschel, and T. Roscoe. BFT protocols under fire. In 5th USENIX Symposium on Networked Systems Design & Implementation, NSDI 2008, April 16-18, 2008, San Francisco, CA, USA, Proceedings, pages 189–204. USENIX Association, 2008. [30] B. Wang, S. Chen, L. Yao, B. Liu, X. Xu, and L. Zhu. A simulation approach for studying behavior and quality of blockchain networks. In Blockchain - ICBC 2018 - First International Conference, Held as Part of the Services Conference Federation, SCF 2018, Seattle, WA, USA, June 25-30, 2018, Proceedings, volume 10974 of Lecture Notes in Computer Science, pages 18–31. Springer, 2018. [31] S. Wang and S. H. Kao. A new approach for byzantine agreement. In The 15th International Conference on Information Networking, ICOIN 2001, Beppu City, Oita, Japan, January 31 - February 2, 2001, pages 518–528. IEEE Computer Society, 2001. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/74300 | - |
dc.description.abstract | 共識演算法在分散式系統中扮演了極其重要的角色。它能保護系統在遭到出錯或惡意的節點攻擊時仍能繼續運作,並保證系統中誠實節點的一致性 (consistency) 與活躍性(liveness)。一個共識演算法是否能達成這兩個保證需要嚴謹的安全性數學證明,否則一個設計不良的共識演算法很有可能在某些情況下無法達成保證的性質。然而,即使一個共識演算法可以達到這兩個性質,其效能仍有可能大幅被網路的狀態或惡意節點影響。即使一個演算法被證明最終能達成共識,若我們無法得知這些影響的嚴重性,我們就無法得知這個演算法是否實用。有時,單純透過理論分析去研究這些影響是很困難的,因此我們需要藉由模擬的方式去了解演算法在攻擊下的行為。本篇論文定義了一個共識演算法模擬器應有的重要特性,並設計實作了一個符合這些特性的模擬器。我們也整理了共識演算法研究領域中常見的網路模型與攻擊者模型。最後,我們在模擬器上實作了幾個共識演算法,評估它們在攻擊下的效能如何,展示我們設計的模擬器能模擬我們整理的所有網路模型與攻擊者模型。 | zh_TW |
dc.description.abstract | A consensus algorithm plays a crucial role in a distributed system. It protects a system from faulty or malicious participants and guarantees consistency and liveness among honest participants. These requirements should be mathematically proved, or a poorly-designed consensus algorithm can fail to achieve them. However, the performance of a consensus algorithm may be severely affected by factors such as different network conditions or malicious attackers. Even if an algorithm is proven to be able to reach consensus eventually, if we do not know how severe the impact is, we do not know if the algorithm is practical. It is sometimes difficult to theoretically analyze the impacts. This is why a simulation-based method is needed. In this paper, we define important requirements for a consensus simulator and design and implement a simulator based on these requirements. We also define common network models and attacker models for consensus algorithms. Finally, we implement several representative consensus algorithms on our simulator, evaluate their performance under attacks and show that our simulator can simulate attacks from all network models and attacker models we defined. | en |
dc.description.provenance | Made available in DSpace on 2021-06-17T08:28:42Z (GMT). No. of bitstreams: 1 ntu-108-R06922053-1.pdf: 1058060 bytes, checksum: 793265a3d2d7036e5e48cfcb25fb588d (MD5) Previous issue date: 2019 | en |
dc.description.tableofcontents | 口試委員會審定書 i
誌謝 ii 摘要 iii Abstract iv 1 Introduction 1 2 Background 5 2.1 Byzantine Agreement (BA) . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Taxonomy of BA: Network Environments and Assumptions . . . . . . . 6 2.2.1 Network Environment . . . . . . . . . . . . . . . . . . . . . . . 6 2.2.2 Trusted Setup Assumption . . . . . . . . . . . . . . . . . . . . . 7 2.3 Performance Metrics of BA . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3.1 Round Complexity . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3.2 Message Complexity . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Related Work 9 4 Attacker Model 11 4.1 Network Layer Attacker Model . . . . . . . . . . . . . . . . . . . . . . . 11 4.1.1 Partition Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.1.2 DDoS Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Protocol Layer Attacker Model . . . . . . . . . . . . . . . . . . . . . . . 12 4.2.1 Fail-Stop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2.2 Static and Adaptive . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2.3 Rushing and Strongly-Rushing . . . . . . . . . . . . . . . . . . . 13 4.2.4 Schedulable and Globally-Schedulable . . . . . . . . . . . . . . 14 5 General Consensus Platform 15 5.1 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.1.1 Generality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.1.2 Simplicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.1.3 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2 Challenge and Difficulty . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.3 Infrastructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.3.1 Simulator Module . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.3.2 Network Module . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.3.3 Node Module . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.3.4 Attacker Module . . . . . . . . . . . . . . . . . . . . . . . . . . 19 6 Evaluation 20 6.1 Generality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 6.1.1 Different Network Models . . . . . . . . . . . . . . . . . . . . . 20 6.1.2 Different Attacker Models . . . . . . . . . . . . . . . . . . . . . 21 6.1.3 Different Consensus Algorithms . . . . . . . . . . . . . . . . . . 22 6.1.4 Simplicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.1.5 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 7 Attack Implementation and Analysis 25 7.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 7.1.1 ADD+ BA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 7.1.2 Algorand Agreement . . . . . . . . . . . . . . . . . . . . . . . . 26 7.1.3 Async BA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 7.1.4 DEXON HBA . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 7.1.5 PBFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 7.2 Performance Without Attack . . . . . . . . . . . . . . . . . . . . . . . . 27 7.3 Performance With Attack . . . . . . . . . . . . . . . . . . . . . . . . . . 28 7.3.1 Network Partition . . . . . . . . . . . . . . . . . . . . . . . . . . 29 7.3.2 Static Fail-Stop Attack on ADD+v1 and ADD+v2 . . . . . . . . 31 7.3.3 Rushing Adaptive Attack on ADD+v2 and ADD+v3 . . . . . . . 33 7.3.4 Adaptive Attack on DEXON HBA . . . . . . . . . . . . . . . . . 34 8 Future Work and Potential Applications 40 8.1 Benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 8.2 Auto-Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 9 Conclusion 42 Bibliography 43 | |
dc.language.iso | en | |
dc.title | 為投票式共識演算法設計的安全測試模擬器及評估 | zh_TW |
dc.title | A Security Simulator and Evaluation for Voting-Based
Consensus Algorithms | en |
dc.type | Thesis | |
dc.date.schoolyear | 107-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 鄭欣明(Shin-Ming Cheng),林忠緯(Chung-Wei Lin),黃俊穎(Chun-Ying Huang) | |
dc.subject.keyword | 資訊安全,共識演算法,拜占庭協議,分散式系統,模擬測試工具, | zh_TW |
dc.subject.keyword | Security,Consensus Algorithms,Byzantine Agreement,Distributed System,Simulation Tool, | en |
dc.relation.page | 46 | |
dc.identifier.doi | 10.6342/NTU201902995 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2019-08-13 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf 目前未授權公開取用 | 1.03 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。