Publications-Theses
Article View/Open
Publication Export
-
題名 基於多重簽章之拜占庭共識演算法
Multi-Signature Byzantine Agreement作者 陳俊瑋
Chen, Chun-Wei貢獻者 郭桐惟
Kuo, Tung-Wei
陳俊瑋
Chen, Chun-Wei關鍵詞 區塊鏈
共識演算法
拜占庭容錯
分散式系統
Blockchain
Consensus algorithm
Byzantine fault tolerance
Distributed system日期 2018 上傳時間 1-Oct-2018 12:10:58 (UTC+8) 摘要 在比特幣面世之後，分散式帳本技術被應用在各式各樣的領域上。 比特幣使用""工作量證明``來確保區塊鏈網路上的各節點狀態、資料的一致性。 除了""工作量證明``外，還有包括""權益證明``、""拜占庭容錯``等相關的演算法各有不同的特性，也可以應用在不同用途的區塊鏈設計上。 我們的研究關注在設計一個具有認許制性質的私有鏈、聯盟鏈上使用的區塊鏈系統，適合許多金融相關組織應用上的需求。 我們的方法能夠在較嚴格的部分網路同步模型 (partially synchronous model)，及拜占庭錯誤假設下保有足夠的安全性及活性，並具有相比目前相關工作更優秀的系統效能。
The distributed ledger has been widely used in different scenarios after the Bitcoin turns out. Unlike the Proof of work (PoW) approaches, there exist another mechanism that has been used on the decentralize database or fault-tolerate system that have great potential to be transplanted to nowadays consortium blockchain systems. Our research focuses on the applying of consensus algorithm to financial organizations with the partially synchronous model, byzantine attackers and permission policy in the system. We designed a novel consensus algorithm, Msig-BFT, that can tolerate one-third faulty nodes within the system and have better performance of the previous works.參考文獻 [1] Buterin, V. (2014). A next-generation smart contract and decentralized application platform. https://github.com/ethereum/wiki/wiki/White-Paper. [2] Buterin, V. and Griffith, V. (2017). Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437. [3] Cachin, C. and Vukolić, M. (2017). Blockchains consensus protocols in the wild. arXiv preprint arXiv:1707.01873. [4] Castro, M., Liskov, B., et al. (1999). Practical byzantine fault tolerance. In OSDI, volume 99, pages 173–186. [5] Crain, T., Gramoli, V., Larrea, M., and Raynal, M. (2017). (leader/randomization/signature)-free byzantine consensus for consortium blockchains. arXiv preprint arXiv:1702.03068. [6] Croman, K., Decker, C., Eyal, I., Gencer, A. E., Juels, A., Kosba, A. E., Miller, A., Saxena, P., Shi, E., Sirer, E. G., Song, D., and Wattenhofer, R. (2016). On scaling decentralized blockchains. pages 106–125. [7] Eyal, I., Gencer, A. E., Sirer, E. G., and Van Renesse, R. (2016). Bitcoin-ng: A scalable blockchain protocol. In NSDI, pages 45–59 [8] Gilbert, S. and Lynch, N. (2002). Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. Acm Sigact News, 33(2):51–59. [9] Johnson, D., Menezes, A., and Vanstone, S. (2001). The elliptic curve digital signature algorithm (ecdsa). International journal of information security, 1(1):36–63. [10] Kiayias, A., Konstantinou, I., Russell, A., David, B., and Oliynykov, R. (2016). A provably secure proof-of-stake blockchain protocol. IACR Cryptology ePrint Archive, 2016:889. [11] King, S. and Nadal, S. (2012). Ppcoin: Peer-to-peer crypto-currency with proof-ofstake. self-published paper, August, 19. [12] Kogias, E. K., Jovanovic, P., Gailly, N., Khoffi, I., Gasser, L., and Ford, B. (2016). Enhancing bitcoin security and performance with strong consistency via collective signing. In 25th USENIX Security Symposium (USENIX Security 16), pages 279–296. [13] Kwon, J. (August, 2014). Tendermint: Consensus without mining. https://cdn. relayto.com/media/files/LPgoWO18TCeMIggJVakt_tendermint.pdf. [14] Lee, C. (2011). Litecoin. [15] Liao, W.-T. (2018). A performance evaluation tool for the consensus mechanism of ethereum-based private blockchains. [16] Mazieres, D. (2015). The stellar consensus protocol: A federated model for internetlevel consensus. Stellar Development Foundation. [17] Micali, S. (2016). Algorand: The efficient and democratic ledger. arXiv preprint arXiv:1607.01341. [18] Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system. https:// bitcoin.org/bitcoin.pdf. [19] Pass, R. and Shi, E. (2017). Hybrid consensus: Efficient consensus in the permissionless model. In LIPIcs-Leibniz International Proceedings in Informatics, volume 91. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. [20] Ren, L., Nayak, K., Abraham, I., and Devadas, S. (2017). Practical synchronous byzantine consensus. arXiv preprint arXiv:1704.02397. [21] Schwartz, D., Youngs, N., and Britto, A. (2014). The ripple protocol consensus algorithm. https://prod.coss.io/documents/white-papers/ripple.pdf. [22] Shiu, Y.-J. (2017). Nccu bft for go ethereum. https://github.com/ NCCUCS-PLSM/NCCU-BFT-for-Go-Ethereum. [23] Syta, E., Tamas, I., Visher, D., Wolinsky, D. I., Jovanovic, P., Gasser, L., Gailly, N., Khoffi, I., and Ford, B. (2016). Keeping authorities” honest or bust” with decentralized witness cosigning. In Security and Privacy (SP), 2016 IEEE Symposium on, pages 526– 545. Ieee. [24] Tsai, W. T., Yu, L., Hu, C. J., Yao, Y. F., and Li, G. N. (2016). Hydrachain: Design of a private blockchain. https://github.com/HydraChain/hydrachain/blob/develop/ hc_consensus_explained.md. [25] Vasin, P. (2014). Blackcoin’s proof-of-stake protocol v2. URL: https://blackcoin. co/blackcoin-pos-protocolv2-whitepaper. pdf. [26] yutelin (2017). Istanbul byzantine fault tolerance. https://github.com/ethereum/ EIPs/issues/650. 描述 碩士
國立政治大學
資訊科學系
105753021資料來源 http://thesis.lib.nccu.edu.tw/record/#G0105753021 資料類型 thesis dc.contributor.advisor 郭桐惟 zh_TW dc.contributor.advisor Kuo, Tung-Wei en_US dc.contributor.author (Authors) 陳俊瑋 zh_TW dc.contributor.author (Authors) Chen, Chun-Wei en_US dc.creator (作者) 陳俊瑋 zh_TW dc.creator (作者) Chen, Chun-Wei en_US dc.date (日期) 2018 en_US dc.date.accessioned 1-Oct-2018 12:10:58 (UTC+8) - dc.date.available 1-Oct-2018 12:10:58 (UTC+8) - dc.date.issued (上傳時間) 1-Oct-2018 12:10:58 (UTC+8) - dc.identifier (Other Identifiers) G0105753021 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/120259 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 資訊科學系 zh_TW dc.description (描述) 105753021 zh_TW dc.description.abstract (摘要) 在比特幣面世之後，分散式帳本技術被應用在各式各樣的領域上。 比特幣使用""工作量證明``來確保區塊鏈網路上的各節點狀態、資料的一致性。 除了""工作量證明``外，還有包括""權益證明``、""拜占庭容錯``等相關的演算法各有不同的特性，也可以應用在不同用途的區塊鏈設計上。 我們的研究關注在設計一個具有認許制性質的私有鏈、聯盟鏈上使用的區塊鏈系統，適合許多金融相關組織應用上的需求。 我們的方法能夠在較嚴格的部分網路同步模型 (partially synchronous model)，及拜占庭錯誤假設下保有足夠的安全性及活性，並具有相比目前相關工作更優秀的系統效能。 zh_TW dc.description.abstract (摘要) The distributed ledger has been widely used in different scenarios after the Bitcoin turns out. Unlike the Proof of work (PoW) approaches, there exist another mechanism that has been used on the decentralize database or fault-tolerate system that have great potential to be transplanted to nowadays consortium blockchain systems. Our research focuses on the applying of consensus algorithm to financial organizations with the partially synchronous model, byzantine attackers and permission policy in the system. We designed a novel consensus algorithm, Msig-BFT, that can tolerate one-third faulty nodes within the system and have better performance of the previous works. en_US dc.description.tableofcontents 1 Introduction . . . 1 2 System Model . . . 4 3 MSig-BFT . . . 6 3.1 Discussion . . . 8 3.1.1 The Round Change Mechanism . . . . 8 3.1.2 Synchronization . . . . . 8 3.1.3 Double-Spending Attack . . . . 10 3.1.4 Broadcast Different Proposals . . . . 10 4 Analysis . . . . 11 4.1 Safety . . . . 11 4.2 Liveness . . . . 12 5 Implementation . . . . 14 6 Experiments . . . . 17 6.1 Experimental Setup . . . . 17 6.2 Experimental Results . . . . 18 7 Related Work . . . . 25 8 Conclusion . . . . 28 Reference . . . . 29 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0105753021 en_US dc.subject (關鍵詞) 區塊鏈 zh_TW 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.subject (關鍵詞) Distributed system en_US dc.title (題名) 基於多重簽章之拜占庭共識演算法 zh_TW dc.title (題名) Multi-Signature Byzantine Agreement en_US dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) [1] Buterin, V. (2014). A next-generation smart contract and decentralized application platform. https://github.com/ethereum/wiki/wiki/White-Paper. [2] Buterin, V. and Griffith, V. (2017). Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437. [3] Cachin, C. and Vukolić, M. (2017). Blockchains consensus protocols in the wild. arXiv preprint arXiv:1707.01873. [4] Castro, M., Liskov, B., et al. (1999). Practical byzantine fault tolerance. In OSDI, volume 99, pages 173–186. [5] Crain, T., Gramoli, V., Larrea, M., and Raynal, M. (2017). (leader/randomization/signature)-free byzantine consensus for consortium blockchains. arXiv preprint arXiv:1702.03068. [6] Croman, K., Decker, C., Eyal, I., Gencer, A. E., Juels, A., Kosba, A. E., Miller, A., Saxena, P., Shi, E., Sirer, E. G., Song, D., and Wattenhofer, R. (2016). On scaling decentralized blockchains. pages 106–125. [7] Eyal, I., Gencer, A. E., Sirer, E. G., and Van Renesse, R. (2016). Bitcoin-ng: A scalable blockchain protocol. In NSDI, pages 45–59 [8] Gilbert, S. and Lynch, N. (2002). Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. Acm Sigact News, 33(2):51–59. [9] Johnson, D., Menezes, A., and Vanstone, S. (2001). The elliptic curve digital signature algorithm (ecdsa). International journal of information security, 1(1):36–63. [10] Kiayias, A., Konstantinou, I., Russell, A., David, B., and Oliynykov, R. (2016). A provably secure proof-of-stake blockchain protocol. IACR Cryptology ePrint Archive, 2016:889. [11] King, S. and Nadal, S. (2012). Ppcoin: Peer-to-peer crypto-currency with proof-ofstake. self-published paper, August, 19. [12] Kogias, E. K., Jovanovic, P., Gailly, N., Khoffi, I., Gasser, L., and Ford, B. (2016). Enhancing bitcoin security and performance with strong consistency via collective signing. In 25th USENIX Security Symposium (USENIX Security 16), pages 279–296. [13] Kwon, J. (August, 2014). Tendermint: Consensus without mining. https://cdn. relayto.com/media/files/LPgoWO18TCeMIggJVakt_tendermint.pdf. [14] Lee, C. (2011). Litecoin. [15] Liao, W.-T. (2018). A performance evaluation tool for the consensus mechanism of ethereum-based private blockchains. [16] Mazieres, D. (2015). The stellar consensus protocol: A federated model for internetlevel consensus. Stellar Development Foundation. [17] Micali, S. (2016). Algorand: The efficient and democratic ledger. arXiv preprint arXiv:1607.01341. [18] Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system. https:// bitcoin.org/bitcoin.pdf. [19] Pass, R. and Shi, E. (2017). Hybrid consensus: Efficient consensus in the permissionless model. In LIPIcs-Leibniz International Proceedings in Informatics, volume 91. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. [20] Ren, L., Nayak, K., Abraham, I., and Devadas, S. (2017). Practical synchronous byzantine consensus. arXiv preprint arXiv:1704.02397. [21] Schwartz, D., Youngs, N., and Britto, A. (2014). The ripple protocol consensus algorithm. https://prod.coss.io/documents/white-papers/ripple.pdf. [22] Shiu, Y.-J. (2017). Nccu bft for go ethereum. https://github.com/ NCCUCS-PLSM/NCCU-BFT-for-Go-Ethereum. [23] Syta, E., Tamas, I., Visher, D., Wolinsky, D. I., Jovanovic, P., Gasser, L., Gailly, N., Khoffi, I., and Ford, B. (2016). Keeping authorities” honest or bust” with decentralized witness cosigning. In Security and Privacy (SP), 2016 IEEE Symposium on, pages 526– 545. Ieee. [24] Tsai, W. T., Yu, L., Hu, C. J., Yao, Y. F., and Li, G. N. (2016). Hydrachain: Design of a private blockchain. https://github.com/HydraChain/hydrachain/blob/develop/ hc_consensus_explained.md. [25] Vasin, P. (2014). Blackcoin’s proof-of-stake protocol v2. URL: https://blackcoin. co/blackcoin-pos-protocolv2-whitepaper. pdf. [26] yutelin (2017). Istanbul byzantine fault tolerance. https://github.com/ethereum/ EIPs/issues/650. zh_TW dc.identifier.doi (DOI) 10.6814/THE.NCCU.CS.018.2018.B02 en_US
