[논문 리뷰] Scaling Blockchain Consensus via a Robust Shared Mempool

Author: Fangyu Gai, Jianyu Niu, Ivan Beschastnikh, Chen Feng, Sheng Wang

Journal/Conference: ICDE 2023

Source: https://arxiv.org/abs/2203.05158

 

---

Abstract

There is a resurgence of interest in Byzantine fault-tolerant (BFT) systems due to blockchains. However, leader-based BFT consensus protocols used by permissioned blockchains have limited scalability and robustness. To alleviate the leader bottleneck in BFT consensus, we introduce Stratus, a robust shared mempool protocol that decouples transaction distribution from consensus. Our idea is to have replicas disseminate transactions in a distributed manner and have the leader only propose transaction ids. Stratus uses a provably available broadcast (PAB) protocol to ensure the availability of the referenced transactions.We implemented and evaluated Stratus by integrating it with state-of-the-art BFT-based blockchain protocols and evaluated these protocols in both LAN and WAN settings. Our results show that Stratus-based protocols achieve up to 5∼20× more throughput than their native counterparts in a network with hundreds of replicas. In addition, the performance of Stratus degrades gracefully in the presence of network asynchrony, Byzantine attackers, and unbalanced workloads. Our design provides easy-to-use APIs so that other BFT systems suffering from leader bottlenecks can use Stratus.

---

Introduction

• LBFT has two phases which are propose phase and commit phase. Key scalability challenge is the leader bottleneck since both phases are handled by a leader.
• Prior works has mainly focused on increasing LBFT performance by improving the commit phase. As recents works reveal that proposing phase has more significant factor limiting LBFT's scalability, this paper aims to optimize proposing phase by decoupling transaction distribution from consensus with shared mempool (SMP).
• Prior works using SMP have passed over two challenges.
    (1) ensuring the availability of transactions referenced in a proposal 
    (2) dealing with unbalanced load acreoss replicas 
  this paper proposes new primitives "provably available broadcast (PAB)" and "distributed load-balancing (DLB)" to solve such challenges respectively. 

---

Contributions

• Provide a shared mempool abstraction that decouples network-based synchronization from ordering for LBFT.
• To ensure the availability of transactions, introduce PAB, which allows replicas to process proposals without waiting for transaction data.
• To balance load acreoss replicas, introduce a DLB, which allows busy replicas to transfer their excess load to under-utilized replicas.
• Implemented Stratus and integrated it with HotStuff, Streamlet, and PBFT. Stratus-based protocols substatntially outperform the native protocols.

---

System models

• Partially synchronous network.
• A replica can become a leader replica via view-changes or leader-rotation.
• assume that each transaction has a unique ID.
• assume that every client know about all the replicas. (permissioned or private network?)
• assume that clients send each transaction to exactly one replica, but they are free to choose the replica for each transaction.
• Byzantine replicas can censor transactions, however, so a client may need to switch to another replica (using a timeout mechanism) until a correct replica is found.
• not considering duplicate attack by sending identical transactions to muliple replicas.

---

Challenge1

 

(1) SMP abstraction

SMP properties

  - The implementation of the SMP abstraction modifies the two primitives ReceiveTx(tx) and MakeProposal() used in the traditional Mempool and adds two new primitives ShareTx(tx) and FillProposal(p)

  - ShareTx, ReceiveTx 에서 PAB(provably available broadcast) 를 사용한다.

 

(2) PAB

---

 

Challenge2

(1) Load Forwarding

use Power-of-d-choices (Pod) algorithm: replica randomly samples load status from \(d\) replicas.

Stable time = until receiving f+1 ack for a microblock (a batch of transactions from a client)

---

Implementation

---

Review

• Censorship resilience 를 위해서는 클라이언트가 자신이 요청한 트랜잭션이 제대로 처리되었는지 직접 확인해야하고, 최악의 경우 f 번의 timeout 을 통해 f개의 byzantine replicas 들을 걸러내야한다. -> 합의 프로토콜 자체가 censorship에 resilient 한 것은 아님. 또 timeout 에 의존한다는 것이 synchrony 를 강화함. 결국 liveness 가 저해되는 결과임. HoneyBadgerBFT 와 비슷한 계열의 asynchronous BFT 는 client 가 n-f 개의 노드에 트랜잭션을 요청함으로써 합의 프로토콜 자체가 censorship resilience를 보장함.
• view-change 를 진행하는 것 자체가 단점임. Narwhal 같은 DAG-based BFT 는 view-change 가 없기 때문에, 이와 비교했을 때 매우 큰 오버헤드를 갖는다고 볼 수 있음.
• shared mempool 을 설계하는 과정에서, RBC 를 PAB로 대체할 때의 observation("We observe that some properties of reliable broadcast are not needed by SMP since they can be provided by the consensus protocol itself (i.e., consistency and totality).")이 인상 깊음.
• PAB가 TCP retransmittion 과 매우 유사하다는 점, DLB의 workload estimation이 process scheduling, packet scheduling 에서 전통적으로 사용되던 개념을 도입했다는 점 등으로부터 친숙한 느낌을 받았다.
• Ban-list 에 포함된 replica 가 일시적인 network fluctuation 때문이었다면, 나중에 restore 되어야 할텐데, 이는 어떻게 처리할건지에 대한 언급은 없다 -> 운영 기간이 길어질수록 ban_list 가 커지기 때문에, 실용적이지 않음.
• 모든 replicas 에 대한 ip 를 서로가 다 알고있어야 한다는 가정.. 이 실용적이지는 않은 것 같다. 
• LBFT 는 network 가 변동성이 심할때 throughput 이 안나오는 경우가 있는데, 그것을 DLB로 어느 정도 해결했다고는 하지만, 최대 딜레이를 300ms 정도로만 설정했음. 별로 의미있는 contribution은 아닌듯.