Survey on Byzantine Fault Tolerance Accountability Mechanisms

doi:10.3969/j.issn.1671-1122.2024.01.002

Abstract

Abstract:

The Byzantine Fault Tolerance (BFT) protocol plays a crucial role in ensuring the consistency and reliability of blockchain or distributed systems in the face of node failures and malicious behavior. The BFT accountability mechanism aims to identify Byzantine nodes by recording and sharing the behavior of consensus nodes during the consensus process. It is designed to effectively address the security and liveness issues that traditional BFT protocols cannot guarantee when the number of Byzantine nodes exceeds 1/3. This paper systematically summarized existing BFT accountability protocols, including server-side accountability mechanisms, client-side accountability mechanisms, and embedded BFT accountability mechanisms. Through a comprehensive comparison and analysis of these involved mechanisms, this paper delved into the challenges and anticipated possible future directions.

Key words: BFT, accountability mechanism, client-side accountability, server-side accountability

CLC Number:

TP309

SUN Huiping, ZHOU Jinjue, LIU Shuxuan, CHEN Zhong. Survey on Byzantine Fault Tolerance Accountability Mechanisms[J]. Netinfo Security, 2024, 24(1): 14-23.

Figures/Tables 6

References 25

[1]	CASTRO M, LISKOV B. Practical Byzantine Fault Tolerance[C]// ACM. Proceedings of the Third Symposium on Operating Systems Design and Implementatio. New York: ACM, 1999: 173-186.
[2]	YIN Maofan, MALKHI D, REITER M K, et al. HotStuff: BFT Consensus with Linearity and Responsiveness[C]// ACM. Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. New York: ACM, 2019: 347-356.
[3]	BUCHMAN E. Tendermint: Byzantine Fault Tolerance in the Age of Blockchains[D]. Guelph: University of Guelph, 2016.
[4]	GILAD Y, HEMO R, MICALI S, et al. Algorand: Scaling Byzantine Agreements for Cryptocurrencies[C]// ACM. Proceedings of the 26th Symposium on Operating Systems Principles. New York: ACM, 2017: 51-68.
[5]	MAO Zhilai, LIU Yanan, SUN Huiping, et al. Research on Blockchain Performance Scalability and SecuritylJ]. Netinfo Security, 2020, 20(3): 56-64.
	毛志来, 刘亚楠, 孙惠平, 等. 区块链性能扩展与安全研究. 信息网络安全, 2020, 20(3):56-64.
[6]	LAMPORT L, SHOSTAK R, PEASE M. The Byzantine Generals Problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3): 382-401. doi: 10.1145/357172.357176 URL
[7]	HAEBERLEN A, KOUZNETSOV P, DRUSCHEL P. PeerReview: Practical Accountability for Distributed Systems[J]. ACM SIGOPS Operating Systems Review, 2007, 41(6): 175-188.
[8]	CIVIT P, GILBERT S, GRAMOLI V. Polygraph: Accountable Byzantine Agreement[C]// IEEE. 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS). New York: IEEE, 2021: 403-413.
[9]	SHENG Peiyao, WANG Gerui, NAYAK K, et al. BFT Protocol Forensics[C]// ACM. Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. New York: IEEE, 2021: 1722-1743.
[10]	SHAMIS A, PIETZUCH P, CANAKCI B, et al. IA-CCF: Individual Accountability for Permissioned Ledgers[C]// USENIX. 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22). Renton: USENIX Association, 2022: 467-491.
[11]	BUTERIN V, GRIFFITH V. Casper the Friendly Finality Gadget[EB/OL]. (2019-01-22) [2023-12-01]. https://arxiv.org/abs/1710.09437.
[12]	ABRAHAM I, MALKHI D. The Blockchain Consensus Layer and BFT[EB/OL]. (2017-10-20) [2023-12-01]. http://eatcs.org/beatcs/index.php/beatcs/article/view/506/495.
[13]	ZHENG Min, WANG Hong, LIU Hong, et al. Survey on Consensus Algorithms of Blockchain[J]. Netinfo Security, 2019, 19(7): 8-24.
	郑敏, 王虹, 刘洪, 等. 区块链共识算法研究综述[J]. 信息网络安全, 2019, 19(7):8-24.
[14]	WANG Gang. SoK: Understanding BFT Consensus in the Age of Blockchains[EB/OL]. (2021-07-05) [2023-12-01]. https://eprint.iacr.org/2021/911.
[15]	FENG Liaoliao, DING Yan, LIU Kunlin, et al. Research Progress on Blockchain BFT Consensus Algorithm[J]. Computer Science, 2022, 49(4): 329-339. doi: 10.11896/jsjkx.210700011
	冯了了, 丁滟, 刘坤林, 等. 区块链BFT共识算法研究进展[J]. 计算机科学, 2022, 49(4):329-339. doi: 10.11896/jsjkx.210700011
[16]	DWORK C, LYNCH N. Stockmeyer L: Consensus in the Presence of Partial Synchrony[J]. Journal of the ACM, 2002, 35(2): 288-323. doi: 10.1145/42282.42283 URL
[17]	BEN-OR M. Another Advantage of Free Choice (Extended Abstract)Completely Asynchronous Agreement Protocols[C]// ACM. Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing. New York: ACM, 1983: 27-30.
[18]	ZENG Shuai, YUAN Yong, NI Xiaochun, et al. Scaling Blockchain towards Bitcoin: Key Technologies, Constraints and Related Issues[J]. Acta Automatica Sinica, 2019, 45(6): 1015-1030.
	曾帅, 袁勇, 倪晓春, 等. 面向比特币的区块链扩容:关键技术,制约因素与衍生问题[J]. 自动化学报, 2019, 45(6):1015-1030.
[19]	RUSSINOVICH M, ASHTON E, AVANESSIANS C, et al. CCF: A Framework for Building Confidential Verifiable Replicated Services[EB/OL]. (2019-06-11) [2023-12-01]. https://www.microsoft.com/en-us/research/publication/ccf-a-framework-for-building-confidential-verifiable-replicated-services/.
[20]	NAKAMOTO S. Bitcoin: A Peer to Peer Electronic Cash System[EB/OL]. (2018-04-10) [2023-12-01]. http://bitcoins.info/bitcoin.pdf.
[21]	ZAMFIR V, RUSH N, ASGAONKAR A, et al. Introducing the Minimal CBC Casper Family of Consensus Protocols. [EB/OL]. (2018-11-17) [2023-12-01]. https://github.com/cbc-casper/cbc-casper-paper/blob/master/cbc-casper-paper-draft.pdf.
[22]	CIVIT P, GILBERT S, GRAMOLI V, et al. As Easy As ABC: Optimal (A) Ccountable (B) Yzantine (C) Onsensus is Easy![J]. Journal of Parallel and Distributed Computing, 2023, 181: 560-570.
[23]	TANG Weizhao, SHENG Peiyao, ROY P, et al. Raft-Forensics: High Performance CFT Consensus with Accountability for Byzantine Faults[EB/OL]. (2023-11-02) [2023-12-01]. https://arxiv.org/abs/2305.09123.
[24]	ONGARO D, OUSTERHOUT J. In Search of an Understandable Consensus Algorithm[C]// USENIX. 2014 USENIX Annual Technical Conference (USENIX ATC 14). Renton: USENIX Association, 2014: 305-319.
[25]	TOBIAS D. Byzantine Fault-Tolerant State-Machine Replication from a Systems Perspective[J]. ACM Computing Surveys, 2021, 54(1): 1-38.

参数	含义
m	问责机制能找出的拜占庭节点数量上限
k	生成作恶证据所需的诚实节点记录数量下限
d	发生共识错误时，能找到的拜占庭节点数量
f	系统能容忍的最多作恶节点数量
n	系统中的节点总数，n = 3f + 1

问责机制	问责检测方	问责能力			问责复杂度
问责机制	问责检测方	m	k	d	问责复杂度
PeerReview	服务端	n	1	1	O(rn²) ≥ O(n³)
Polygraph	服务端	n-2	1	f+1	O(n⁴)
BFT-Forensics	客户端	2f	1	f+1	O(n²)
IA-CCF	客户端	n	1	f+1	O(n²)