為投票式共識演算法設計的安全測試模擬器及評估

A Security Simulator and Evaluation for Voting-Based Consensus Algorithms

趙子為(Tzu-Wei Chao)

指導教授 ： 蕭旭君

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2019年)

https://doi.org/10.6342/NTU201902995

摘要

共識演算法在分散式系統中扮演了極其重要的角色。它能保護系統在遭到出錯或惡意的節點攻擊時仍能繼續運作，並保證系統中誠實節點的一致性 (consistency) 與活躍性(liveness)。一個共識演算法是否能達成這兩個保證需要嚴謹的安全性數學證明，否則一個設計不良的共識演算法很有可能在某些情況下無法達成保證的性質。然而，即使一個共識演算法可以達到這兩個性質，其效能仍有可能大幅被網路的狀態或惡意節點影響。即使一個演算法被證明最終能達成共識，若我們無法得知這些影響的嚴重性，我們就無法得知這個演算法是否實用。有時，單純透過理論分析去研究這些影響是很困難的，因此我們需要藉由模擬的方式去了解演算法在攻擊下的行為。本篇論文定義了一個共識演算法模擬器應有的重要特性，並設計實作了一個符合這些特性的模擬器。我們也整理了共識演算法研究領域中常見的網路模型與攻擊者模型。最後，我們在模擬器上實作了幾個共識演算法，評估它們在攻擊下的效能如何，展示我們設計的模擬器能模擬我們整理的所有網路模型與攻擊者模型。

關鍵字

資訊安全 ； 共識演算法 ； 拜占庭協議 ； 分散式系統 ； 模擬測試工具

並列摘要

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.

並列關鍵字

Security ； Consensus Algorithms ； Byzantine Agreement ； Distributed System ； Simulation Tool

參考文獻

[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.