Consensus Byzantin et blockchain : Modèles unifiés et nouveaux protocoles

Les applications distribuées utilisent des protocoles de consensus afin de maintenir un état consistent sur plusieurs machines dans un réseau. L'avènement récent de bitcoin et des algorithmes basés sur la blockchain a suscité un regain d'intérêt pour ces protocoles, notamment en ce qui concerne leur capacité à passer à l'échelle et à tolérer les participants malicieux. Cependant, cette attention a été source de confusion, submergeant un sujet déjà vaste et complexe avec des assertions imprécises et une terminologie variable. Dans cette thèse, nous proposons une unification des fondamentaux de la blockchain, grâce à un formalisme capturant un large éventail de modèles communs pour les protocoles de consensus. Nous utilisons ce formalisme pour décrire les spécifications de divers protocoles de consensus d'intérêt pour la blockchain. Nous recadrons et précisons les théorèmes qui décrivent les conditions dans lesquelles un protocole est possible ou non. Nous utilisons également notre formalisme pour décrire le modèle de plusieurs blockchains de référence malgré leurs différences fondamentales, et nous pouvons également évaluer et comparer finement leurs caractéristiques de performance. Ensuite, nous faisons une proposition pour une blockchain, StakeCube. La sécurité de StakeCube est basée sur le modèle de preuve d'enjeu (Proof-of-Stake), et sa capacité de passage à l'échelle repose sur un principe du partitionnement (sharding), qui est mis en œuvre par une table de hachage distribuée. Nous avons également implémenté une version restreinte de StakeCube et évalué ses performances, validant ainsi sa propriété de passage à l'échelle. Notamment, comme StakeCube troque la preuve de travail (Proof-of-Work) contre la preuve d'enjeu sans sacrifier le passage à l'échelle, ce protocole est particulièrement bien adapté aux applications IoT. Pour mieux démontrer cet aspect, nous avons implémenté une application IoT de marché d'énergie dans StakeCube et avons pu tester avec succès sa viabilité.Any distributed application makes use of agreement protocols in order to maintain a consistent state across multiple machines in a network. With the recent advent of Bitcoin and blockchain-based algorithms, there has been a renewed interest around such agreement protocols, especially regarding their ability to scale and tolerate malicious participants. However this attention has been a source of misunderstanding, flooding an already large and complex subject with vague claims and different terminology.In this thesis, we make a unifying view of the blockchain landscape, by proposing a formulation capturing a wide range of accepted models for agreement protocols. We use this formalism to describe the specifications of various agreement protocols of interest for blockchain. We reframe and make precise the theorems that describe the conditions under which a protocol is possible or not. We also use our framework to describe the model of several prominent blockchains despite their fundamental differences, and we are able to make a fine-grained assessment and comparison of their performance characteristics.Then, we make a proposal for a scalable blockchain, StakeCube. StakeCube's security is based on the Proof-of-Stake model, and its scalability relies on the sharding paradigm, implemented through a distributed hash table.We also implemented (a restricted version of) StakeCube and evaluated its performance, thus validating its scalability property.Notably, because StakeCube trades Proof-of-Work for Proof-of-Stake without sacrificing scalability, it is particularly well suited for IoT applications. To further demonstrate this aspect, we implemented an energy marketplace IoT application in StakeCube and were able to successfully test its viability