[논문 리뷰] The Honey Badger of BFT protocols
Author: Miller, A., Xia, Y., Croman, K., Shi, E., & Song, D.
Journal/Conference: Proceedings of the 2016 ACM SIGSAC conference on computer and communications security
source: https://dl.acm.org/doi/abs/10.1145/2976749.2978399
[Abstract]
The surprising success of cryptocurrencies has led to a surge of interest in deploying large scale, highly robust, Byzantine fault tolerant (BFT) protocols for mission-critical applications, such as financial transactions. Although the conventional wisdom is to build atop a (weakly) synchronous protocol such as PBFT (or a variation thereof), such protocols rely critically on network timing assumptions, and only guarantee liveness when the network behaves as expected. We argue these protocols are ill-suited for this deployment scenario. We present an alternative, HoneyBadgerBFT, the first practical asynchronous BFT protocol, which guarantees liveness without making any timing assumptions. We base our solution on a novel atomic broadcast protocol that achieves optimal asymptotic efficiency. We present an implementation and experimental results to show our system can achieve throughput of tens of thousands of transactions per second, and scales to over a hundred nodes on a wide area network. We even conduct BFT experiments over Tor, without needing to tune any parameters. Unlike the alternatives, HoneyBadgerBFT simply does not care about the underlying network.
[Introduction]
- "Confederation Cryptocurrency"-like deployment environment
: In the environment in which network bandwidth is the scarce resource but computation is relatively ample, throughput and robustness is the most important property rather than response time and latency. - Permissioned Blockchain
: The number of nodes is fixed and some clients propose transactions to those nodes, who are responsible for carrying out the submitted transactions. - Fully asynchronous network assumption
: Previous BFT protocols having weak synchrony assumption such as PBFT may be completely failed. If it may be not, when the underlying network is fluctuated, those protocols degrade significantly in throughput.
[Contributions]
- Solve asynchronous Common Subset(ACS) problem by reduction AVID-RBC(C. Cachin and S. Tessaro. Asynchronous verifiable information dispersal. In Reliable Distributed Systems, 2005. SRDS 2005. 24th IEEE Symposium on, pages 191–201. IEEE, 2005.) and BA(A. Mostefaoui, H. Moumen, and M. Raynal. Signature-free asynchronous byzantine consensus with t< n/3 and o (n 2) messages. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 2–9. ACM, 2014.) based upon previous approach(M. Ben-Or, B. Kelmer, and T. Rabin. Asynchronous secure computations with optimal resilience. In Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, pages 183–192. ACM, 1994.), without expensive MVBA(C. Cachin, K. Kursawe, F. Petzold, and V. Shoup. Secure and efficient asynchronous broadcast protocols. In Advances in Cryptology– Crypto 2001, pages 524–541. Springer, 2001.) used in SINTRA(C. Cachin, J. Poritz, et al. Secure intrusion-tolerant replication on the internet. In Dependable Systems and Networks, 2002. DSN2002. Proceedings. International Conference on, pages 167–176. IEEE, 2002.).
- Improve Ben-Or's ACS protocols by not waiting for 0 output of BAs.
- Reduce message communication complexity of RBC in ACS by erasure coding.
- Reduce asymtatic cost per node of ACS to \(O(1)\) from \(O(n^2)\).
- Achieve Censorship resilience using thrshold encryption, which prevents the adversry from learning which transactions are propsed by which nodes, until after agreement is already reached.
[Building blocks]
(1) each node encrypts a batch of transactions and output corresponding ciphertexts.
(2) each node exchanges their ciphertexts(encrypted transactions) through RBC protocols.
(3) after delivering, each node make a vector which has indexes of correct nodes through BA protocols.
(4) each node constructs a vector containing ciphertexts of whom all node have decided previously by BA.
(5) finally decrypt the ciphertexts using threshold encryption scheme.
[Performance]
Review
- permissioned blockchain 상황에서만 사용가능하다는 한계. dynamic 하게 node 들이 참여하고 빠지는 곳에서 전체 노드 숫자(n)을 알아야 BA 프로토콜이 제대로 작동할 수 있음.
- 논문 중간에 ACS 를 통해 throuput 을 더 증가시키려면 mostly disjoint set 을 만들어야하고, 이를 위해서 buffer 로부터 tx들을 랜덤하게 뽑아와야한다고 했는데, 이런 경우에는 tx 간의 의존성을 해결해야만 하는 문제가 있음. 만약 그걸 해결한다고 해도, Front-running attack 은 어떻게 방지?
- 또 redundant transaction 문제가 있음. 클라이언트가 최소 n-f 개의 노드에게 트랜잭션을 제시해야함. 그렇다면 최소 n-f 개의 노드는 해당 트랜잭션을 중복으로 들고 있을 것. 실제 의미있는 throughput은 훨씬 낮음.
- threshold encryption scheme에 사용되는 symmetric bilinear group을 ss512로 선택함 -> 80bits 정도의 안정성. 이 정도는 금방 뚫림. 최소 128bits 정도는 되어야하는데, 그렇게 설정하더라고 과연 PBFT보다 좋은 성능을 낼 수 있는지?
- ACS 에 대한 최적화는 잘 한것 같은데, 수반되는 암호학 라이브러리들이 너무 무거워서 overhead가 더 큰 것처럼 보임.
- 구현을 파이썬으로 했는데, multi-process 가 아니라 multi-thread 방식으로 구현함. -> 파이썬의 GIL 특성상 cpu bound job을 multi-thread로 구현하면 성능저하가 더 심한데, 왜 그랬지..?