Abstract
Existing consensus protocols for blockchain technology have issues with high latency and complexity. Directed Acyclic Graph(DAG)-based Byzantine Fault Tolerance(BFT) solutions have become popular to address these issues, but they often trade off security or liveness. Many employ timing assumptions to circumvent these issues, but these are not always reliable in an adversarial setting. Recent studies have found that Byzantine Reliable Broadcast(BRB) protocol can achieve asset-transfer capabilities in a deterministic, full asynchronous mode. However, BRB cannot handle generalized applications like smart-contracts, which require a global total order. A new solution called BRAPTOR has been proposed and developed that addresses these issues. BRAPTOR is a hybrid system that combines the partial-order consensusless BRB with an efficient Byzantine total order broadcast consensus component. It decouples data dissemination from metadata ordering for scalable and high throughput results. Theoretical analysis with correctness proofs and evaluation show that BRAPTOR achieves instant asset-transfer, asynchronous liveness, optimal resilience, optimum communication complexity, constant time complexity and post quantum safety.
Introduction
Distributed Ledger Technology (DLT) [1], [2] based on Nakamoto Consensus (NC) blockchain is widely adopted with the advent of the Bitcoin [3](cryptocurrency) in 2007 and Ethereum [4](smart contract) in 2015 [5]. New use cases arise with AI-enabled or ChatGPT-like Web3’s promise [6] to power future digital societies with Decentralized Autonomous Organization (DAO), Decentralized Finance (Defi)1 and Non-Fungible-Token (NFT). Others efficiently employ spectrum sensing cognitive radio that detect unused spectrum and exploit the licensed band opportunistically, as radio spectrum asset is now transferable and tradeable using blockchain [8], [9]. The following explanations are to clarify the keyword terms in the title BR-AP-TOR and the reasoning behind the design choices.
BR: Byzantine-Resistance
The NC2 faces challenges like slow transaction settlement and low transaction scalability, which are impractical for applications requiring low-latency transactions. Classical Byzantine Fault Tolerance (BFT) [10] does not have these issues but struggles with a quadratic communication On2 problem, hindering global adoption due to poor node scalability. To combine the strengths of both approaches , a modern Directed Acyclic Graph-based (DAG-based) BFT system is proposed. Recent studies in [11], [12], [13] separate transaction distribution from ordering logic by using a DAG-based Mempool protocol for reliable transaction dissemination. This significantly boosts network speed and throughput, as blocks of transactions and (2f + 1) references to earlier messages are included in DAG-based BFT messages, forming a structured directed acyclic graph(DAG) that encodes communication history. Here, 2f + 1 DAG references form the Byzantine resistance (BR) majority (67%) for a 3f + 1 BFT system where f = maximum number of byzantine/faulty nodes.
AP: Asynchronous Partial-order
DLT, particularly DAG-based BFT State Machine Replication (SMR) solutions, are favored in the modern Internet landscape to enhance security against Distributed-denial-of-service (DDoS) and botnet attacks by eliminating the need for synchrony or timing assumptions [13]. These solutions thrive in a robust total asynchronous environment, enabling parallel transaction processing. Extant studies, such as [14], [15], have shown that for asset transfers applications like cryptocurrency, possess a consensus number of 1 in Herlihy’s hierarchy [15], can maintain consistency and reliability without cumbersome consensus mechanisms. Instead, a partial-order consensusless Byzantine Reliable Broadcast (BRB) approach is deemed adequate as it is able to eliminate the need for low-latency paths during synchronous periods and overcoming FLP impossibility [16] issues. This deterministic and fully asynchronous approach with weak consistency, allows faster and consensus-free execution of cryptocurrency transactions compared to traditional cumbersome consensus methods. This first section of BRAPTOR refers as the fast-path or BRAPTOR-fp.
TOR: Total-Order with Randomization
BRAPTOR-fp cannot handle generic applications like smart-contract. It needs a global total order that has Herlihy’s hierarchy consensus number infinity [15] with strong consistency. Therefore, the second section of BRAPTOR refers as the normal path or BRAPTOR-np which employs asynchronous consensus-based total-order protocol with randomization that uses common random-coin to circumvent FLP [16] impossibility results. The high latency issue in this asynchronous consensus protocol is addressed by having the processes off-line interpret their blockDAGs locally and total-order all proposals without incurring additional communication costs. A more efficient Byzantine Total-Order Broadcast (BTOB) algorithm is introduced by overlapping the first round of hop h with fourth round of hop h-1 in the total-order protocol.
In essence, BRAPTOR is an efficient method for instant asset-transfer and generic-application in blockchain. Both types of applications are accomplished via BRAPTOR-fp and BRAPTOR-np respectively.
Contribution as compared with state-of-the-art:
- •Edge-centric computing in IoT [1], [2] give rise to idea of locally interpreting the protocol. To the best of researchers’ knowledge, there are few studies on this approach. That is, splitting monolithic solution into separate DAG mempool and locally off-line interpreting layer coupled with horizontal scalability structure improve the throughput significantly.
- •A suite of locally interpreted consensusless partial-order solutions for instant asset transfer and consensus total-order solution with randomization for efficient generic application in blockchain using submit/guarantee/commit model.
- •Interpret/simulate instances of protocols BRB1 achieves totality property without hassle, thereby prevent partial-payment issue. Since there is no asymmetric cryptography used in agreement in BRB and BTOB, BRAPTOR is post quantum secure (safety and liveness) in fast-path and post quantum safe in normal-path.
- •Using off-line interpreting BRB2 on top of blockDAG as reliable point-to-point (pt2pt) link, together with the overlapping of the 1st round of hop h with 4th round of hop h-1, render BTOB very efficient.