Date of Award
10-1-2023
Thesis Type
phd
Document Type
Thesis (Restricted Access)
Divisions
fsktm
Department
Department of Computer System & Technology
Institution
Universiti Malaya
Abstract
Existing consensus protocols suffer from high latency (Nakamoto Consensus (NC) based) and complexity (Classical Byzantine Fault Tolerance (BFT) based) in terms of communication. Therefore, Directed Acyclic Graph (DAG) based BFT solutions become popular to resolve these deficiencies. However, they usually trade-off with either the security or liveness due to the inherent Fischer- Lynch-Paterson (FLP) impossibility theorem in dealing with asynchronous consensus-based protocol. Timing assumption was employed to circumvent the FLP impossibility, otherwise partialsynchronous mode to exploit the synchronous steady phase that comes after Global Stabilization Time (GST) for achieving low latency fast-path. Yet, timing assumption does have its shortfalls since it is provably impossible to guarantee liveness in the adversarial Byzantine settings where artificial time-based delays/attacks such as Botnets and Distributed Denial-of-service (DDoS), are common in the modern Internet context. To address these consensus-based issues, recent studies found that Byzantine Reliable Broadcast protocol (BRB) could achieve the same assettransfer capabilities in a deterministic full asynchronous mode. This is possible as asset-transfer application like cryptocurrency has Herlihy’s hierarchy consensus number 1 which does not need consensus, in which a broadcast-based protocol is sufficient. Nonetheless, this partial-ordered BRB cannot handle generalized application like smart-contract, which need a global total order that has Herlihy’s hierarchy consensus number infinity. In this thesis, a DAG-based BFT - BRAPTOR - an efficient method for instant asset-transfer and generic-application in blockchain is designed. This requires partial-order consensusless BRB to be extended with applying efficient Byzantine total order broadcast (BTOB) consensus component. That is, BRAPTOR (Byzantine Resistant Asynchronous Partial-order to Total-Order with Randomization) is a hybrid system with two components: BRAPTOR-fp (fast-path) and BRAPTOR-np (normal-path). The main idea employed is to decouple data dissemination from metadata ordering (partial or total) interpretation for scalable and high throughput results. Evaluation shows that BRAPTOR achieves instant assettransfer, asynchronous liveness, optimal resilience, optimum communication complexity using reliable-point-to-point link abstraction, constant time complexity and post quantum safety.
Note
Thesis (PhD) – Faculty of Computer Science & Information Technology, Universiti Malaya, 2023.
Recommended Citation
Yeow, Kim Chai, "Braptor - an efficient method for instant asset-transfer and generic application in blockchain / Yeow Kim Chai" (2023). Student Works (2020-2029). 1547.
https://knova.um.edu.my/student_works_2020s/1547