Note
This repository contains the LaTeX source code of "Timing and Fairness Considerations in Blockchain Systems." It is advised by Prof. Aggelos Kiayias and Dr. Michele Ciampi in the School of Informatics at the University of Edinburgh.
Since 2009, Nakamoto's Bitcoin whitepaper ignites the research of permissionless blockchain protocols. Nakamoto Consensus (i.e., the underlying consensus layer of Bitcoin) is of strong theoretical interest in terms of offering an ever-lasting, large-scale and permissionless computing service, which turns out to be challenging in the classical setting. Yet, despite these unprecedented features, Nakamoto Consensus still suffers from significant security and performance bottlenecks in terms of timing and fairness. To highlight a few: Transaction settlement is asymptotically slow. Clients need to wait for their transactions to be buried sufficiently deep for at least poly-logarithmically many blocks in terms of the security parameter. The protocol is built assuming parties having access to a shared notion of time, which might be problematic due to a single point failure, considering in the real-world it is implemented by the NTP protocol. In addition, the system still bears ephemeral centralization at the point of block production, creating opportunities for the adversary to seek profit by unfairly ordering transactions and adaptively injecting new ones.
This thesis serves as a proposal for improving the timing and fairness aspects of Nakamoto Consensus, via a cryptographic treatment of a family of permissionless protocols detailed as follows.
First, we study the blockchain trichotomy --- i.e., how a distributed ledger can simultaneously admit cryptographic security, permissionless participation, and (expected-)constant processing time for all incoming transactions. Our approach employs the parallel blockchain construction, which we adapt as an intermediate to cast classical Byzantine Agreement (BA) protocols terminating in expected-constant time. Further, we show how to apply sequential composition on BA invocations, thus yielding permissionless ledgers with fast transaction settlement.
Second, we explore how a dynamically changing number of parties can jointly maintain a shared notion of protocol time without access to a global clock. We consider two clock models. On one hand, we show that when parties possess local clocks with additive drifts, a fresh new party with no knowledge other than the genesis block can synchronize with other parties after passively listening to the protocol execution. On the other hand, when equipped with drifting local clocks running within a bounded ratio of real time, we show how the synchronization procedure can cope with parallel chains, hence maintaining a bounded skew among all parties.
Third, we focus on blockchain order fairness in terms of transaction serialization. Our treatment considers both the temporal and causal aspect of order fairness. Regarding the temporal aspect, we propose the most refined notion of receiver order fairness which we term bounded unfairness; we also explore the complexity of realizing it. Then, we capture both sender and receiver order fairness in the Universal-Composability framework. We build two permissionless protocols assuring input causality. The first protocol, utilizing trusted hardware, allows clients to encrypt transactions which will be decrypted after a pre-determined period of time, measured by the blockchain progression. The second protocol, while achieving the same functionality, obviates the need for hardware enclaves and employs ephemeral committees that send only one message thus achieving input causality alongside adaptive security.