Ray Neiheiser

Co-advisors: M. Matos e C. Montez

Scalable and Resilient Byzantine Fault Tolerant Consensus

Tese submetida para provas de doutoramento em Engenharia Informática e de Computadores Instituto Superior Técnico, Universidade de Lisboa e no Programa de Pós-Graduação em Engenharia de Automação e Sistemas – PPGEAS, Centro Tecnológico, da Universidade Federal de Santa Catarina.

Abstract

The increasing popularity of blockchains in addressing an expanding set of use cases, from enterprise to governmental applications, led to a growing interest in permissioned blockchains. In contrast to their permissionless counterparts, permissioned blockchains can ensure deterministic transaction finality which is a key requirement in many settings and can offer high throughput in small-sized systems. Some emerging use cases for per- missioned blockchains require the system to scale to hundreds of participants. However, most permissioned blockchains are based on variants of classical byzantine fault-tolerant (BFT) consensus protocols that scale poorly with the number of participants. Such scal- ability limitations stem from bottlenecks both at the network and processing levels that result from the large number of messages that need to be sent, received and processed to reach consensus. Most attempts to solve this problem on a large scale end up reducing the overall resilience of the system and endanger both safety and liveness in the pres- ence of byzantine failures. An approach that distributes the load equally among a set of processes are tree-based algorithms. However, due to the additional communication steps, tree-based approaches still display insufficient throughput on a geographic scale. Tree structures are also inherently more sensitive to byzantine faults, and constructing robust trees in the presence of failures is not a trivial matter. This thesis proposes new techniques that address these problems. We leverage extensive pipelining to achieve high throughput on a geographic scale independently of the depth of the tree and present a reconfiguration algorithm that is able to construct a robust tree in optimal steps in the presence of failures. Experimental results show that Kauri, a prototype that incorpo- rates the proposed techniques, can efficiently execute consensus in settings with more than 500 participants and can achieve up to over 58 times the throughput of competing approaches.

Selected Publications

Scalable and Resilient Byzantine Fault Tolerant Consensus: PhD Thesis. Instituto Superior Técnico, Universidade de Lisboa and Universidade Federal de Santa Catarina.; March, 2022.; Available BibTeX and PhD Thesis
Kauri: Scalable BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation.: R. Neiheiser, M. Matos, and L. Rodrigues.; Proceedings of the 28th ACM Symposium on Operating Systems Principles (SOSP), Online, October, 2021.; Presentation video: short and long.; pdf.

Luís Rodrigues