Delay analysis of BFT consensus: Case study of Narwhal and Bullshark protocols

Acknowledging the critical influence of consensus delays on blockchain performance, this paper presents an analytical and simulation-based exploration of delay characteristics in Byzantine Fault Tolerant (BFT) consensus mechanisms. Our focus is on SUI, a blockchain system that employs a Directed Acyclic Graph (DAG) structure to support parallel transaction execution. SUI relies on two integrated protocols: Narwhal, a mempool protocol responsible for efficient block dissemination and DAG construction; and Bullshark, which organizes DAG vertices to produce a consistent total order of transactions without incurring additional communication overhead. While our previous work modeled Narwhal's delay characteristics under various message propagation distributions, this study shifts attention to Bullshark—the protocol responsible for reaching consensus. We propose a probabilistic analytical model that estimates the number of rounds required to reach consensus. In this model, each validator's decision is treated as a Bernoulli trial, and we apply the binomial distribution to determine the probability of reaching quorum. This framework enables us to analyze the expected delay of the protocol. To validate our model, we implemented both Narwhal and Bullshark and conducted extensive simulations. The simulation results show strong agreement with our analytical predictions, confirming the accuracy of our model. For instance, under a Gaussian delay model with mean μ=1ms and standard deviation σ=0.25 ms—values representative of short-range wireless communication in real-world IoT or LAN settings [1]—we predict an average round duration of approximately 3.26 ms. Furthermore, based on our binomial-based model of block commitment, the expected number of rounds to reach consensus is approximately 1 when f=10, indicating that blocks typically commit in a single round with high probability. To the best of our knowledge, this is the first study to model Bullshark's consensus process using Bernoulli trials and binomial distributions. Our contributions offer a novel framework for evaluating its efficiency and provide insights that can guide future optimization and scalability efforts for DAG-based BFT protocols.