Publications-Theses
Article View/Open
Publication Export
-
題名 私有區塊鏈上的兩步驟拜占庭共識演算法
A Simple TwoStep Byzantine Fault Tolerance in Private Blockchains作者 蘇鑑微
Su, Jian-Wei貢獻者 郭桐惟
Kuo, Tung-Wei
蘇鑑微
Su, Jian-Wei關鍵詞 區塊鏈
共識演算法
拜占庭容錯
Blockchain
Consensus Algorithm
Byzantine Fault Tolerance日期 2019 上傳時間 6-Nov-2019 15:27:27 (UTC+8) 摘要 區塊鏈技術至今已發展十多年歷程。區塊鏈應用也從一開始數位貨幣衍伸生出多樣化的應用與服務。區塊鏈是一種分散式帳本技術，帳本內容是由多個網路節點共同維護，而非受到單一節點所控制。為了確保安全性，系統內所有節點需要擁有相同帳本資料;換句話說，節點間須對帳本內容達成共識，而達成共識的方法稱共識演算法。為因應不同的應用情境，區塊鏈分為公有鏈與私有鏈。公有鏈對所有人皆開放，而私有鏈只開放特定人群或企業加入。本篇論文針對私有鏈上的共識演算法進行探討及研究。一般而言，私有鏈共識演算法需要三個步驟的訊息交流，才能確保共識結果是正確的。我們設計了一個兩步驟的共識演算法-TwoStepBFT。此演算法能夠容許拜占庭節點錯誤，且保有安全性及活性。為了架設大規模節點的私有鏈，我們整合了多樣的自動化雲端部署套件，此套件幫助我們在雲端平台上自動產生多個節點。實驗結果顯示我們的方法在一百個節點依舊能有300TPS的共識效率。
Blockchains have been developed for more than a decade. The very first application of blockchains is digital currency. Within a decade, blockchains have found applications in various fields. A blockchain can be viewed as a distributed ledger, whose content is maintained by multiple network nodes rather than by a single node. In order to ensure correctness, all nodes in the blockchain need to have the same content of the ledger. In other words, all nodes must reach consensus on the content of the blockchain. Toward this goal, all nodes must execute the same protocol that specifies the rules of adding new blocks to Blockchain. Such a protocol is called a consensus algorithm. There are two types of blockchains, public blockchains and private blockchains. Public blockchains have no access control, and is open to everyone. On the other hand, private blockchains can only be accessed by admitted nodes. This thesis focuses on the design and analysis of consensus algorithms for private blockchains. In general, consensus algorithms for private blockchains involve three steps of information exchange to ensure correctness. In this thesis, we design a two-step Byzantine tolerant consensus algorithm, TwoStepBFT. In order to evaluate the performance of TwoStepBFT on a 100-node blockchain, we integrate a variety of automated tools to deploy blockchains. Experimental results have shown that our consensus algorithm can reach a throughput of 300 TPS on a 100-node Blockchain.參考文獻 參考文獻[1] R3 corda, 2016. https://www.r3.com.[2] Librawhitepaper, 2019. https://libra.org/en-US/wp-content/uploads/sites/23/2019/06/LibraWhitePaper_en_US.pdf.[3] I. Abraham, G. Gueta, D. Malkhi, and J.P.Martin. Revisiting fast practical byzantinefault tolerance: Thelma, velma, and zelma. arXiv preprint arXiv:1801.10022, 2018.[4] V. Buterin. A nextgenerationsmart contract and decentralized application platform.https://github.com/ethereum/wiki/wiki/White-Paper, 2014.[5] V. Buterin. clique for go ethereum. https://github.com/ethereum/go-ethereum/tree/master/consensus/clique, 2016.[6] M. Castro, B. Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99,pages 173–186, 1999.[7] C.W.Chen, J.W.Su, T.W.Kuo, and K. Chen. Msigbft:A witnessbasedconsensus algorithm for private blockchains. In 2018 IEEE 24th International Conferenceon Parallel and Distributed Systems (ICPADS), pages 992–997. IEEE, 2018.[8] K. Croman, C. Decker, I. Eyal, A. E. Gencer, A. Juels, A. E. Kosba, A. Miller,P. Saxena, E. Shi, E. G. Sirer, D. Song, and R. Wattenhofer. On scaling decentralizedblockchains. pages 106–125, 2016.[9] dexon org. dexon whitepaper. https://dexon.org/whitepaper, 2018.[10] I. Eyal, A. E. Gencer, E. G. Sirer, and R. Van Renesse. Bitcoinng:A scalableblockchain protocol. In NSDI, pages 45–59, 2016.[11] M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensuswith one faulty process. Technical report, Massachusetts Inst of Tech Cambridge labfor Computer Science, 1982.[12] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich. Algorand: Scalingbyzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposiumon Operating Systems Principles, pages 51–68. ACM, 2017.[13] D. Johnson, A. Menezes, and S. Vanstone. The elliptic curve digital signature algorithm(ecdsa). International journal of information security, 1(1):36–63, 2001.[14] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: speculativebyzantine fault tolerance. In ACM SIGOPS Operating Systems Review, volume 41,pages 45–58. ACM, 2007.[15] C. Lee. Litecoin, 2011.[16] J.P.Martin and L. Alvisi. Fast byzantine consensus. IEEE Transactions on Dependableand Secure Computing, 3(3):202–215, 2006.[17] S. Nakamoto. Bitcoin: A peertopeerelectronic cash system. https://bitcoin.org/bitcoin.pdf, 2008.[18] Y.J.Shiu. Nccu bft for go ethereum. https://github.com/ethereum/EIPs/issues/650, 2017.[19] W. T. Tsai, L. Yu, C. J. Hu, Y. F. Yao, and G. N. Li. Hydrachain: Design of a privateblockchain. https://github.com/HydraChain/hydrachain/blob/develop/hc_consensus_explained.md, 2016.[20] P. Vasin. Blackcoin＇s proofofstakeprotocol v2. URL: https://blackcoin.co/blackcoinposprotocolv2whitepaper.pdf, 71, 2014.[21] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham. Hotstuff: Bft consensusin the lens of blockchain. arXiv preprint arXiv:1803.05069, 2018. 描述 碩士
國立政治大學
資訊科學系
106753006資料來源 http://thesis.lib.nccu.edu.tw/record/#G0106753006 資料類型 thesis dc.contributor.advisor 郭桐惟 zh_TW dc.contributor.advisor Kuo, Tung-Wei en_US dc.contributor.author (Authors) 蘇鑑微 zh_TW dc.contributor.author (Authors) Su, Jian-Wei en_US dc.creator (作者) 蘇鑑微 zh_TW dc.creator (作者) Su, Jian-Wei en_US dc.date (日期) 2019 en_US dc.date.accessioned 6-Nov-2019 15:27:27 (UTC+8) - dc.date.available 6-Nov-2019 15:27:27 (UTC+8) - dc.date.issued (上傳時間) 6-Nov-2019 15:27:27 (UTC+8) - dc.identifier (Other Identifiers) G0106753006 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/127216 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系 zh_TW dc.description (描述) 106753006 zh_TW dc.description.abstract (摘要) 區塊鏈技術至今已發展十多年歷程。區塊鏈應用也從一開始數位貨幣衍伸生出多樣化的應用與服務。區塊鏈是一種分散式帳本技術，帳本內容是由多個網路節點共同維護，而非受到單一節點所控制。為了確保安全性，系統內所有節點需要擁有相同帳本資料;換句話說，節點間須對帳本內容達成共識，而達成共識的方法稱共識演算法。為因應不同的應用情境，區塊鏈分為公有鏈與私有鏈。公有鏈對所有人皆開放，而私有鏈只開放特定人群或企業加入。本篇論文針對私有鏈上的共識演算法進行探討及研究。一般而言，私有鏈共識演算法需要三個步驟的訊息交流，才能確保共識結果是正確的。我們設計了一個兩步驟的共識演算法-TwoStepBFT。此演算法能夠容許拜占庭節點錯誤，且保有安全性及活性。為了架設大規模節點的私有鏈，我們整合了多樣的自動化雲端部署套件，此套件幫助我們在雲端平台上自動產生多個節點。實驗結果顯示我們的方法在一百個節點依舊能有300TPS的共識效率。 zh_TW dc.description.abstract (摘要) Blockchains have been developed for more than a decade. The very first application of blockchains is digital currency. Within a decade, blockchains have found applications in various fields. A blockchain can be viewed as a distributed ledger, whose content is maintained by multiple network nodes rather than by a single node. In order to ensure correctness, all nodes in the blockchain need to have the same content of the ledger. In other words, all nodes must reach consensus on the content of the blockchain. Toward this goal, all nodes must execute the same protocol that specifies the rules of adding new blocks to Blockchain. Such a protocol is called a consensus algorithm. There are two types of blockchains, public blockchains and private blockchains. Public blockchains have no access control, and is open to everyone. On the other hand, private blockchains can only be accessed by admitted nodes. This thesis focuses on the design and analysis of consensus algorithms for private blockchains. In general, consensus algorithms for private blockchains involve three steps of information exchange to ensure correctness. In this thesis, we design a two-step Byzantine tolerant consensus algorithm, TwoStepBFT. In order to evaluate the performance of TwoStepBFT on a 100-node blockchain, we integrate a variety of automated tools to deploy blockchains. Experimental results have shown that our consensus algorithm can reach a throughput of 300 TPS on a 100-node Blockchain. en_US dc.description.tableofcontents 目錄誌謝. . . . . . . . . . . . . . . . . . . . .i摘要. . . . . . . . . . . . . . . . . . . . .iiAbstract . . . . . . . . . . . . . . . . . . iii目錄. . . . . . . . . . . . . . . . . . . . .v圖目錄. . . . . . . . . . . . . . . . . . . .vii1 緒論. . . . . . . . . . . . . . . . . . . .12 系統模型. . . . . . . . . . . . . . . . . .52.1 網路模型與系統假設. . . . . . . . . . . .52.2 共識假設與定義. . . . . . . . . . . . . .53 共識演算法. . . . . . . . . . . . . . . . .73.1 共識流程. . . . . . . . . . . . . . . . .73.1.1 Propose . . . . . . . . . . . . . . . 73.1.2 Vote . . . . . . . . . . . . . . . . . 83.1.3 Commit . . . . . . . . . . . . . . . . 93.2 Timeout . . . . . . . . . . . . . . . . 94 演算法分析. . . . . . . . . . . . . . . . 114.1 安全性（Safety） . . . . . . . . . . . . 114.2 活性（Liveness） . . . . . . . . . . . . 125 Geth 共識模組程式架構與私有鏈系統部署. . . 135.1 Geth 共識模組程式架構. . . . . . . . . . 135.1.1 Consensus Manager . . . . . . . . . . .145.1.2 Height Manager . . . . . . . . . . . . 145.1.3 Round Manager . . . . . . . . . . . . .155.1.4 Message Handler . . . . . . . . . . . .155.1.5 Synchronizer . . . . . . . . . . . . . 155.2 私有鏈系統部署. . . . . . . . . . . . . .155.2.1 雲端虛擬機器設定. . . . . . . . . . . .165.2.2 私有鏈系統設定. . . . . . . . . . . . .176 實驗結果. . . . . . . . . . . . . . . . . .196.1 環境建設. . . . . . . . . . . . . . . . .196.2 同資料中心吞吐量與延遲性測試. . . . . . .196.3 跨資料中心吞吐量與延遲性測試. . . . . . .227 相關研究. . . . . . . . . . . . . . . . . .277.1 公有鏈上共識演算法. . . . . . . . . . . .277.1.1 ProofofWork. . . . . . . . . . . . . . 277.1.2 ProofofStack . . . . . . . . . . . . . 277.1.3 混合型共識演算法. . . . . . . . . . . .287.2 私有鏈上共識演算法. . . . . . . . . . . 287.2.1 ProofofAuthority. . . . . . . . . . . 287.2.2 三步驟拜占庭共識演算法. . . . . . . . .287.2.3 兩步驟拜占庭共識演算法. . . . . . . . .298 討論與結論. . . . . . . . . . . . . . . . .308.1 討論. . . . . . . . . . . . . . . . . . .308.2 結論. . . . . . . . . . . . . . . . . . .30參考文獻. . . . . . . . . . . . . . . . . . .32 zh_TW dc.format.extent 1796383 bytes - dc.format.mimetype application/pdf - dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0106753006 en_US dc.subject (關鍵詞) 區塊鏈 zh_TW dc.subject (關鍵詞) 共識演算法 zh_TW dc.subject (關鍵詞) 拜占庭容錯 zh_TW dc.subject (關鍵詞) Blockchain en_US dc.subject (關鍵詞) Consensus Algorithm en_US dc.subject (關鍵詞) Byzantine Fault Tolerance en_US dc.title (題名) 私有區塊鏈上的兩步驟拜占庭共識演算法 zh_TW dc.title (題名) A Simple TwoStep Byzantine Fault Tolerance in Private Blockchains en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) 參考文獻[1] R3 corda, 2016. https://www.r3.com.[2] Librawhitepaper, 2019. https://libra.org/en-US/wp-content/uploads/sites/23/2019/06/LibraWhitePaper_en_US.pdf.[3] I. Abraham, G. Gueta, D. Malkhi, and J.P.Martin. Revisiting fast practical byzantinefault tolerance: Thelma, velma, and zelma. arXiv preprint arXiv:1801.10022, 2018.[4] V. Buterin. A nextgenerationsmart contract and decentralized application platform.https://github.com/ethereum/wiki/wiki/White-Paper, 2014.[5] V. Buterin. clique for go ethereum. https://github.com/ethereum/go-ethereum/tree/master/consensus/clique, 2016.[6] M. Castro, B. Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99,pages 173–186, 1999.[7] C.W.Chen, J.W.Su, T.W.Kuo, and K. Chen. Msigbft:A witnessbasedconsensus algorithm for private blockchains. In 2018 IEEE 24th International Conferenceon Parallel and Distributed Systems (ICPADS), pages 992–997. IEEE, 2018.[8] K. Croman, C. Decker, I. Eyal, A. E. Gencer, A. Juels, A. E. Kosba, A. Miller,P. Saxena, E. Shi, E. G. Sirer, D. Song, and R. Wattenhofer. On scaling decentralizedblockchains. pages 106–125, 2016.[9] dexon org. dexon whitepaper. https://dexon.org/whitepaper, 2018.[10] I. Eyal, A. E. Gencer, E. G. Sirer, and R. Van Renesse. Bitcoinng:A scalableblockchain protocol. In NSDI, pages 45–59, 2016.[11] M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensuswith one faulty process. Technical report, Massachusetts Inst of Tech Cambridge labfor Computer Science, 1982.[12] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich. Algorand: Scalingbyzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposiumon Operating Systems Principles, pages 51–68. ACM, 2017.[13] D. Johnson, A. Menezes, and S. Vanstone. The elliptic curve digital signature algorithm(ecdsa). International journal of information security, 1(1):36–63, 2001.[14] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: speculativebyzantine fault tolerance. In ACM SIGOPS Operating Systems Review, volume 41,pages 45–58. ACM, 2007.[15] C. Lee. Litecoin, 2011.[16] J.P.Martin and L. Alvisi. Fast byzantine consensus. IEEE Transactions on Dependableand Secure Computing, 3(3):202–215, 2006.[17] S. Nakamoto. Bitcoin: A peertopeerelectronic cash system. https://bitcoin.org/bitcoin.pdf, 2008.[18] Y.J.Shiu. Nccu bft for go ethereum. https://github.com/ethereum/EIPs/issues/650, 2017.[19] W. T. Tsai, L. Yu, C. J. Hu, Y. F. Yao, and G. N. Li. Hydrachain: Design of a privateblockchain. https://github.com/HydraChain/hydrachain/blob/develop/hc_consensus_explained.md, 2016.[20] P. Vasin. Blackcoin＇s proofofstakeprotocol v2. URL: https://blackcoin.co/blackcoinposprotocolv2whitepaper.pdf, 71, 2014.[21] M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham. Hotstuff: Bft consensusin the lens of blockchain. arXiv preprint arXiv:1803.05069, 2018. zh_TW dc.identifier.doi (DOI) 10.6814/NCCU201901225 en_US
