Beyond Blockchain: Byzantine and Sybil Tolerance in Open Systems

Since the introduction of Bitcoin, blockchain platforms have attracted enormous interest from the general public, the government, the industry, and the research community. A number of actors have thus proposed a variety of alternative solutions either introducing new features [1,2] or improving on aspects such as privacy [3], or computational cost [4,5]. Despite the hype, however, the very notion of a distributed ledger (the abstraction that blockchains implement) remains fuzzy. 

Recent work has attempted to formalize blockchain and distributed ledgers in various ways [6,7], but we are still far from a clear understanding of the best abstractions to support applications. For example, a recent paper at PODC [8] proved that popular applications like cryptocurrencies do not need a ledger abstraction and can be implemented with more lightweight broadcast primitives.

Even if not for cryptocurrency, the concept of a distributed ledger remains interesting for a wide range of distributed applications like traceable data sharing, identity management, or any application that benefits from tamper-proof verifiable storage. But practictioners still lack a clear undestanding of which application requires which abstraction. Although many people appear to see blockchain technology as the solution for every decentralized system, many applications rely on different abstractions than ledgers.   In addition, practically all existing blockchain implementations operate by fully replicating data across the network. While this approach can provide the strongest guarantees, it results in huge costs both in terms of computation (when using proof of work) and storage, resulting in significant energy waste. 

Finally, the very concept of a blockchain has been for years associated with the notion of Byzantine-tolerant Consensus in Distributed Algorithms [9]. But as several researchers have observed [6,7], existing blockchain platform often implement abstractions different from consensus, and tolerate different adversaries from the classical byzantine scenario. In particular, in open, or permissionless, systems, the possibility of the attacker to create multiple identities (Sybils) poses challenges that go beyond classical byzantine fault tolerance, bearing more resemblance to work on sybil-proof large-scale peer-to-peer systems.

Problem Statement

This thesis will tackle the blockchain domain from a distributed systems perspective, leveraging decades of research on decentralized applications. From a conceptual perspective the thesis has two major goals. First, it aims at better formalizing the concept of a distributed ledger both by describing existing systems and by identifying new requirements for better ones. Second, it aims to explore the extension of Sybil- and Byzantine tolerant properties to other abstractions and data structures than ledgers. From a systems perspective the thesis will explore the design of novel systems that fit the defined abstractions in the permissionless domain, but also in more restrictive settings.

Methodology

The thesis will leverage the expertise of researchers in the WIDE team in the domain of distributed algorithms and large-scale systems. The selected PhD student will thus conduct both theoretical and systems work. On the theoretical side he/she will work on the formalization of blockchain abstractions and other Sybil/Byzantine-tolerant data structures in order to clarify the requirements of existing and potentially new applications. On the systems side, the student will explore the design of different flavors of applications benefiting from the formalized abstractions.