Algorithms and Mechanisms for Blockchain (EPSRC CDT in Distributed Algorithms)

This PhD project is part of the CDT in Distributed Algorithms: The What, How and where of Next-Generation Data Science.

The University of Liverpool’s Centre for Doctoral Training in Distributed Algorithms (CDT) is working in partnership with the STFC Hartree Centre and 20+ external partners from the manufacturing, defence and security sectors to provide a 4-year innovative PhD training programme that will equip up to 60 students with: the essential skills needed to become future leaders in distributed algorithms; the technical and professional networks needed to launch a career in next generation data science and future computing; and the confidence to make a positive difference in society, the economy and beyond.

This studentship is open to Home and International students.

The successful PhD student will be co-supervised and work alongside our external partner TriliTech.

Do you want to be part of state-of-the-art exciting research work, related to algorithmic innovation in blockchain? Do you want to work with people who can see the capabilities that this initiative can offer? Blockchain development appears to be one of the fastest growing enterprises and a PhD in algorithms related to blockchains will give you the opportunity to work on innovative and state of the art research in the intersection of algorithmics, game theory, machine learning and blockchain technology.

Blockchain is a distributed ledger that stores records of peer-to-peer transactions, with the underlying goal that it is decentralised and publicly accessible. Blockchain usually implements its own native currency, cryptocurrency, which is an integral part of the protocol defining blockchain operation. Although, the most natural application of blockchain, given its native currency, is financial transactions, the nature of these transactions and recorded data need not only be financial. In fact, blockchains have multiple, diverse and growing list of applications, including finance, personal data, healthcare and medical data, supply chain, voting platforms, content creation, etc. The currently dominant and oldest blockchains are Bitcoin, historically the first such platform, and Ethereum.

Blockchain’s protocol is created and maintained by an underlying organisation, private or public, but it operates in a completely decentralised manner, whereby independent users can freely join it and contribute to the content of the stored pieces of data, called blocks. Because of possible malicious actions of the users and private nature of the stored data, the protocol must be secure, which means that it must withstand such attacks. Any user can freely join the blockchain and therefore each blockchain usually has millions of users. Given these requirements, blockchain protocols must be secure and efficient, and this is where Algorithmic Mechanism Design (AMD) comes into play.

Algorithmic Mechanism Design builds and analyses efficient truthful mechanisms, which are designed to align the incentives of the participating agents with the goal of the mechanism designer. It offers powerful algorithmic and game theoretic tools towards this goal of preventing such malicious attacks. Such mechanisms often solve a hard optimisation problem. Hence approximation algorithms and computational complexity are important part of their design. Therefore, AMD provides exactly the right tools to ensure security and efficiency of blockchain, and applying AMD to blockchain protocols is an important and growing research direction.

Tezos is one of the modern blockchains which has many attractive features and a potential to become one of the mainstream blockchains. This multidisciplinary PhD research project aims to research the existing protocols of the Tezos blockchain and to develop novel and improved blockchain protocols. We will study the distributed consensus protocols and define relevant AMD optimisation problems in blockchain settings.

We will use and develop state of the art techniques from modern optimisation, e.g., polynomial time approximation algorithms for hard optimisation problems, mathematical programming, randomised algorithms and probabilistic analysis, game theory, reinforcement learning, and deep learning and address the following AMD problems within this PhD project:

·      Blockchain setting is a dynamically changing and stochastic environment, with large number of users. We will design large scale, dynamic mechanisms and analyse their performance. Equilibria in repeated games and reinforcement learning will be used here.

·      Blockchain protocols, including Tezos’ protocols, are inherently randomised. We will model a problem of computing the probability that a blockchain protocol is successful. Probabilistic analysis and randomised algorithms will be applied here.

·      We will apply machine learning techniques to model and automatically find efficient mechanisms for blockchain. Reinforcement learning and deep learning approach can help finding the best mechanisms for problems related to blockchain protocols.

The integral part of the project will be an implementation, deployment and experimental evaluation, using Tezos data, of these novel mechanisms in the real Tezos operations.

TriliTech Limited is a London based company with a global mission to facilitate and enable the promotion and development of new technologies and applications, especially in the fields of novel, open and decentralized software architectures, including the promotion and development of the Tezos protocol and related technologies.

This PhD will be co-supervised by Mr Arthur Breitman, creator of the Tezos blockchain and director of TriliTech, and Professors Piotr Krysta and Rida Laraki from the SPG/Economics and Computation research group at the Department of Computer Science, and Dr Olga Gorelkina from the Economics Department, in the University of Liverpool.

The main aims of this PhD project are to research blockchain protocols, and in particular Tezos protocol, and identify and model novel optimisation Algorithmic Mechanism Design problems within these protocols and design efficient algorithmic solutions for these problems. These new solutions will lead to improved blockchain protocols. They will be evaluated by using theoretical and experimental means of algorithm analysis. The anticipated outcomes of this project are:

·      New algorithmic models of optimisation AMD problems in blockchain settings analysed theoretically and experimentally. This will lead to research publications in leading computer science venues.

·      Implementations of these new algorithmic solutions and the conduct of their experimental evaluation. This will lead to the deployment of these implementations in the real Tezos operations.

This project is due to commence on 1 October 2022 (Covid-19 Working Practices available).