Dumbo-ng: Fast asynchronous bft consensus with throughput-oblivious latency
Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications …, 2022•dl.acm.org
Despite recent progresses of practical asynchronous Byzantine-fault tolerant (BFT)
consensus, the state-of-the-art designs still suffer from suboptimal performance. Particularly,
to obtain maximum throughput, most existing protocols\rev with guaranteed linear amortized
communication complexity require each participating node to broadcast a huge batch of
transactions, which dramatically sacrifices latency. Worse still, the ƒ slowest nodes'
broadcasts might never be agreed to output and thus can be censored (where ƒ is the …
consensus, the state-of-the-art designs still suffer from suboptimal performance. Particularly,
to obtain maximum throughput, most existing protocols\rev with guaranteed linear amortized
communication complexity require each participating node to broadcast a huge batch of
transactions, which dramatically sacrifices latency. Worse still, the ƒ slowest nodes'
broadcasts might never be agreed to output and thus can be censored (where ƒ is the …
Despite recent progresses of practical asynchronous Byzantine-fault tolerant (BFT) consensus, the state-of-the-art designs still suffer from suboptimal performance. Particularly, to obtain maximum throughput, most existing protocols \rev with guaranteed linear amortized communication complexity require each participating node to broadcast a huge batch of transactions, which dramatically sacrifices latency. Worse still, the ƒ slowest nodes' broadcasts might never be agreed to output and thus can be censored (where ƒ is the number of faults). Implementable mitigation to the threat either uses computationally costly threshold encryption or incurs communication blow-up by letting the honest nodes to broadcast redundant transactions, thus causing further efficiency issues.
We present Dumbo NG, a novel asynchronous BFT consensus (atomic broadcast) to solve the remaining practical issues. Its technical core is a non-trivial direct reduction from asynchronous atomic broadcast to multi-valued validated Byzantine agreement (MVBA) with quality property (which ensures the MVBA output is from honest nodes with 1/2 probability). Most interestingly, the new protocol structure empowers concurrent execution of transaction dissemination and asynchronous agreement. This brings about two benefits: (i) the throughput-latency tension is resolved to approach peak throughput with minimal increase in latency; (ii) the transactions broadcasted by any honest node can be agreed to output, thus conquering the censorship threat with no extra cost.
We implement Dumbo-NG with using the current fastest GLL+22 MVBA with quality (NDSS'22) and compare it to the state-of-the-art asynchronous BFT with guaranteed censorship resilience including Dumbo (CCS'20) and Speeding-Dumbo (NDSS'22). Along the way, we apply the techniques from Speeding-Dumbo to DispersedLedger (NSDI'22) and obtain an improved variant of DispersedLedger called Dumbo-DLfor a comprehensive comparison. Extensive experiments (over up to 64 AWS EC2 nodes across 16 AWS regions) reveal: Dumbo-NG realizes a peak throughput 4-8x over Dumbo, 2-4x over Speeding-Dumbo, and 2-3x over sDumbo-DL for varying scales; More importantly, Dumbo-NG's latency, which is lowest among all tested protocols, can almost remain stable when throughput grows.
ACM Digital Library