Consenso bizantino y Blockchain

Abstract

Los sistemas blockchain han despertado un gran interés desde su aparición por su utili- zación en las divisas criptográficas, de las que Bitcoin es la pionera y la más icónica. Sus aplicaciones se extienden a cualquier sistema que requiera mantener un registro replicado de documentos o transacciones, garantizando la consistencia eventual del estado compartido, la integridad de los datos y la tolerancia a fallos por medio de un algoritmo de consenso. El presente trabajo versa acerca de Trebizond, un algoritmo de consenso tolerante a fallos bizantinos especialmente apropiado para su aplicación en sistemas blockchain permisiona- dos. Su diseño está influenciado principalmente por Raft y PBFT. Del primero toma sus principios de diseño, que se fundamentan en la separación de problemas, la reducción del espacio de estados y la inteligibilidad del algoritmo. Del segundo toma algunos de los ele- mentos que permiten dotar al algoritmo de tolerancia a fallos en un escenario bizantino. Tras realizar un estudio detallado del problema del consenso distribuido y otros problemas estrechamente relacionados propios de los sistemas distribuidos, seguido por una crónica de las principales plataformas de blockchain permisionado actualmente en explotación, se enuncia la especificación funcional de Trebizond. Este algoritmo permite alcanzar consenso en un escenario eventualmente síncrono, autenticado y con presencia de fallos bizantinos. Respecto al estado actual de la investigación en este área, su principal contribución es la combinación de la detección de fallos activa y la validación semántica. Mientras que otros algoritmos utilizan la detección activa de fallos como una forma de mejorar el factor de tolerancia a fallos frente a la táctica de enmascaramiento habitualmente usada, y otros algoritmos hacen uso de técnicas de validación semántica o externa a la hora de valorar si es lícito ejecutar una operación sobre el estado compartido, Trebizond propone fusionar ambas técnicas. Su finalidad es utilizar la validación semántica, dependiente del protocolo de nivel superior que se ejecuta sobre el algoritmo de consenso, como parte del propio mecanismo de detección activa de fallos, de tal forma que se mejore su eficacia y completitud. Este refinamiento del detector de fallos permite, por ejemplo, deponer a un líder cuando los nodos detectan que éste está enviando operaciones que son coherentes con el propio algoritmo de consenso pero que violan la semántica del protocolo de nivel de aplicación, o aislar a una réplica del grupo de difusión cuando se tienen evidencias de comportamiento bizantino por su parte. El establecimiento de las propiedades de seguridad y viveza del algoritmo y su diseño se detallan pormenorizadamente utilizando autómatas de entrada/salida, una técnica bien cono- cida para la elaboración de algoritmos distribuidos. Este diseño encuentra su correspondencia en una implementación, realizada como caso práctico con el ánimo de mostrar paradigmas y patrones que facilitan la codificación de algoritmos distribuidos a partir de un diseño bien especificado.

Blockchain systems have been drawing a great deal of interest since their first appearance due to their use in cryptocurrencies, having Bitcoin as their pioneer and the most iconic of them. Their applications spread to any system which requires to keep a replicated log of documents or transactions, ensuring eventual consistency on the state shared among the replicas, data integrity, and fault tolerance by means of a consensus algorithm. The present work deals with Trebizond, a fault tolerant algorithm particularly suitable for its application in permissioned blockchain systems. It is influenced by Raft and PBFT. From the former it takes its design principles, which lay on problem separation, state space reduc- tion, and the algorithm¿s own intelligibility. From the latter it takes some of the elements which enable the algorithm to be provided with fault tolerance in the byzantine setting. After carrying out a detailed study about the problem of distributed consensus and other typical problems of distributed systems which are tightly bound to it, followed by a sum- mary of the main permissioned blockchain platforms currently in exploitation, Trebizond¿s functional specification is formulated. This algorithm tries to reach consensus in an even- tually synchronous authenticated setting, where byzantine failures may arise. Regarding the current state of research in this area, Trebizond¿s main contribution is its combination of active failure detection and semantic validation. While other algorithms make use of active failure detection as a means of improving their fault tolerance degree in relation to the fai- lure masking strategy commonly used, and other algorithms rely on semantic or external validation when it comes to appreciate whether an operation is legal to be executed on the shared state, Trebizond proposes to fuse both techniques. It aims to use semantic validation, this being dependent from the higher level protocol which execu- tes on top of the consensus algorithm, as a part of the active failure detection system, thus improving its effectiveness and completeness. This polished failure detector makes possible to perform actions such as deposing a leader when it is detected for having been sending messages which are coherent with the consensus algorithm itself but violate the application level protocol, or isolating a replica from the communication group when evidences exist that it has featured byzantine behavior. The algorithm¿s safety and liveness properties are first outlined and subsequently high- lighted by means of input/output automatons, a well-known technique for crafting distribu- ted algorithms. Such a design finds its match in an implementation case, whose goal is to show some paradigms and patterns which make easier to code distributed algorithms from a properly stated design.