Testing and simulating consensus algorithms

Tutors : Philippe Bidinger and Eugen Zalinescu

Overview

A core component of a blockchain platform is its underlying consensus mechanism, ensuring that all participants agree on a chain of blocks. Since Bitcoin's breakthrough, many variants of the original proof-of-work design have been proposed. However, they all have the drawback that the safety property (i.e. all participants agree on the same chain) is a probabilistic property and is not immediate: all participants agree, with high probability, on a (growing) prefix of their chain. Furthermore, the safety property does not hold over an asynchronous network. For these reasons, in recent years many blockchain platforms have considered adopting classic BFT1 consensus algorithms, like DLS2 and PBFT3 , which do not have these drawbacks. And, starting with Tendermint4, the first adaptation of a classical BFT-like algorithms to blockchains, many variants have been proposed: Hotstuff, LibraBFT, Tenderbake5, and still others.

Goals

The goal of this internship is to write a (or adapt an existing) testing and simulation framework for distributed consensus algorithms, like OCaml-Raft6 and Twins7 used by the Libra blockchain. The framework should make it possible to test the OCaml implementation of at least one of the recent algorithms mentioned above, in particular the following aspects:

  • random message delays/loss, with certain degrees of control
  • if relevant, random clock skews
  • concrete scenarios, where certain messages are lost or delayed, and where Byzantine participants perform certain actions

Concretely, we expect you to proceed as follows:

  • get familiar with at least one existing simulation framework
  • implement (at least) one consensus algorithm in OCaml
  • write/adapt the simulator and extensively test the implemented algorithms
  • document the algorithm implementation and the simulator
  • write a report describing the strengths/weaknesses of the used simulator, and the findings obtained by using it on the implemented algorithm(s)

Requirements

You should be familiar with a functional programming language; a working knowledge of the OCaml programming language is a plus. Familiarity with distributed systems would be an advantage, though it is not required.

Internship Context

You will work at the Nomadic Labs' offices in Paris or Grenoble.

Participating in a large scale open-source project you will have to rapidly learn to use collaborative tools (Git, merge request, issues, gitlab, continuous integration, documentation) and to communicate about your work. The final results might be presented at an international conference or workshop.

You will have a designated advisor at Nomadic Labs and will have to work independently and to propose thoroughly-considered solutions to the different problems you will have to solve. You will be encouraged to seek advice from members of the team.

Intellectual Property

All material produced (essays, documentation, code, etc.) will be released under an open source license (e.g. MIT or CC).