Scalable and resilient byzantine fault tolerant consensus

Abstract

A utilização cada vez mais frequente de blockchains para desenvolver aplicações distribuídas de cariz comercial e governamental, tem aumentado o interesse nas blockchains fechadas, em que os nós necessitam de uma autorização prévia para participar no sistema, o que permite controlar o número e características dos participantes. Isto permite executar protocolos de consenso que garantem finalidade, isto é, em que o acordo não pode ser revertido. Estes protocolos conseguem também oferecer bom desempenho quando o número de participantes é reduzido (na ordem das dezenas). No entanto, é hoje possível encontrar aplicações baseadas em blockchain que precisam de suportar centenas de participantes. Infelizmente, a maioria das blockchain fechadas usam variantes do protocolo de consenso byzantino PBFT, que tem pouca capacidade de escala, devido à utilização de padrões de comunicação que obrigam um ou vários nós a enviar, receber e processar um elevado número de mensagens que cresce linear ou quadraticamente com o tamanho do sistema. As soluções anteriores para mitigar estes problems sofrem de várias limitações, comprometendo a segurança e/ou a disponibilidade do sistema na presença de faltas. Esta dissertação apresenta novas técnicas para abordar estes problemas, baseadas na construção de árvores que podem ser reconfiguradas num número óptimo de passos e que suportam a execução concorrente, em ?pipeline?, de múltiplas instâncias de consenso. Resultados experimentais mostram que um sistema que concretiza estas técnicas, denominado Kauri, consegue suportar de forma eficiente o consenso em grupos com mais de 500 participantes, oferecendo um débito 58 vezes superior ao de trabalhos anteriores.

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 permissioned 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 scalability 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 presence 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 \thesystem, a prototype that incorporates 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.