a16z : Sur l'impossibilité des blockchains « sans état »
TechFlow SélectionTechFlow Sélection
a16z : Sur l'impossibilité des blockchains « sans état »
L'état n'a pas disparu, mais a été transféré hors des mains des validateurs et poussé aux utilisateurs sous forme de mises à jour de témoignage fréquentes.
Dédié à des analyses Web3 approfondiesRédaction : Miranda Christ, Joseph Bonneau
Traduction : TechFlow
À mesure que les blockchains prennent en charge davantage d'utilisateurs et des transactions plus fréquentes, la quantité d'informations stockées par les validateurs pour vérifier ces transactions (c'est-à-dire « l'état ») augmente également. Par exemple, dans Bitcoin, l'état est constitué d'un ensemble de sorties de transaction non dépensées (UTXO). Dans Ethereum, l'état comprend le solde de chaque compte ainsi que le code et le stockage de chaque contrat intelligent.
Lorsque le nombre de comptes ou d'UTXO croît suffisamment pour prendre en charge un volume de transactions quotidien important au sein d'une population, ce fardeau de stockage devient ingérable, rendant difficile la participation en tant que validateur et menaçant ainsi la décentralisation. Une solution attrayante consiste à recourir à la cryptographie, où des outils tels que les arbres de Merkle ou les preuves à divulgation nulle de connaissance nous permettent d'accomplir des tâches auparavant inimaginables.
C'est précisément cet objectif que poursuivent les « blockchains sans état ». Toutefois, malgré de nombreuses recherches sur le sujet, elles restent encore loin d'être pratiques. En réalité, ce retard dans les progrès est inhérent : l'écart entre ces constructions et leur applicabilité pratique ne pourra jamais être comblé. Nos travaux récents montrent que toute proposition de blockchain sans état, aussi ingénieuse soit-elle, est irréalisable sans mesures supplémentaires pour gérer l'état. Cependant, comme nous le montrerons à la fin de cet article, ce résultat d'impossibilité ne doit pas décourager.
Sans état
Aujourd'hui, l'état est volumineux mais gérable. Par exemple, un nœud Bitcoin stocke environ 7 Go de données, tandis qu'un nœud Ethereum en stocke environ 650 Go. Toutefois, la charge de stockage supportée par les nœuds complets croît approximativement linéairement avec le débit de la chaîne (transactions par seconde, TPS), or ce débit actuel reste inacceptable. Selon les conceptions actuelles, l'état requis pour supporter efficacement des transactions quotidiennes (des dizaines de milliers à plusieurs centaines de milliers de TPS) deviendrait ingérable, nécessitant des capacités de stockage allant jusqu'aux téraoctets voire aux pétaoctets.
Cela pousse à chercher des solutions techniques permettant de réduire drastiquement la quantité d'état nécessaire aux validateurs. L’objectif crucial est d’atteindre une blockchain sans état, qui obligerait les validateurs à ne stocker qu’une taille d’état constante, indépendamment du débit des transactions (en réalité, ce terme est quelque peu trompeur : l’état existe toujours, mais il est suffisamment petit pour rester praticable à tout niveau futur de débit — généralement de taille fixe). Cette exigence légère en matière de stockage rendrait beaucoup plus facile l’exécution d’un nœud validateur ; idéalement, chacun pourrait exécuter un tel nœud depuis son téléphone portable. Étant donné que l’augmentation du nombre de validateurs renforce la sécurité de la chaîne, abaisser le seuil d’entrée pour les validateurs est essentiel.
Malgré de nombreuses recherches sur les blockchains sans état (par exemple, des travaux menés par Todd, Buterin, Boneh et al., ainsi que Srinivasan et al.), elles sont encore loin d’être utilisables, et à notre connaissance, aucune n’a été déployée. Le problème fondamental de toutes les blockchains sans état connues réside dans le fait qu’elles exigent que les utilisateurs stockent des données supplémentaires appelées « témoins » (witness), afin d’aider les validateurs à valider les transactions liées à leurs comptes. Par exemple, ce témoin peut être une preuve d’appartenance dans un arbre de Merkle, montrant que le compte et le solde de l’utilisateur sont inclus dans l’engagement global de l’état. Lorsqu’un utilisateur effectue une transaction, il soumet ce témoin au validateur pour prouver que son compte dispose d’un solde suffisant.
Contrairement à la clé privée, qui n’a jamais besoin d’être modifiée, ces témoins changent fréquemment, même pour les utilisateurs n’effectuant aucune transaction active, ce qui représente une charge très lourde pour eux. Imaginez, par analogie, que vous deviez constamment surveiller toutes les autres transactions de cartes bancaires dans le monde entier, et mettre à jour localement certaines données chaque fois, simplement pour pouvoir utiliser votre propre carte. Pour qu’une blockchain soit utilisable, les utilisateurs doivent pouvoir rester hors ligne et interagir uniquement avec la blockchain au moment de soumettre une transaction. Dans de nombreux cas, notamment avec les portefeuilles matériels, la mise à jour du témoin n’est pas seulement gênante, elle est carrément impossible.
Cela nous amène à poser une question naturelle de recherche : est-il possible de construire une blockchain sans état qui ne nécessite pas de mises à jour fréquentes des témoins (ou seulement très rares) ? Pour répondre à cette question, nous avons développé un nouveau cadre théorique (les systèmes de preuve révocables), qui généralise les blockchains sans état. À l’aide de ce cadre, nous démontrons un résultat d’impossibilité : le compromis entre un état global concis et des mises à jour fréquentes des témoins est fondamentalement difficile à résoudre. Notre technique de preuve relève de la théorie de l’information, ce qui signifie que même les ordinateurs futurs ne disposeront pas de capacités suffisantes pour contourner ce problème : l’écart entre les constructions de blockchains sans état et leur viabilité pratique ne sera jamais comblé.
Contexte de notre étude
Pour mieux comprendre notre résultat d’impossibilité, commençons par décrire une méthode naturelle mais inefficace de construction d’une blockchain sans état à l’aide d’un arbre de Merkle. Notre objectif est de permettre aux validateurs de déterminer si une transaction soumise par un utilisateur est valide — par exemple, si l’utilisateur dispose d’un solde suffisant pour effectuer cette transaction. Dans un schéma de blockchain sans état, les validateurs stockent un état de taille constante. Lorsqu’un utilisateur effectue une transaction, il doit inclure un témoin dans celle-ci. Le validateur peut alors utiliser cet état courant et le couple (transaction, témoin) fourni par l’utilisateur pour vérifier que ce dernier possède bien un solde suffisant.
Nous construisons d’abord un arbre de Merkle, dans lequel chaque paire (identifiant du compte, solde) (a, b) est incluse comme feuille. L’état V de taille constante stocké par le validateur est la racine de cet arbre, servant d’engagement pour l’ensemble des paires (solde, compte). Chaque utilisateur conserve son témoin sous forme de preuve d’appartenance dans l’arbre de Merkle. La preuve d’appartenance d’une feuille (a, b) est composée des nœuds voisins (v₁, …, vₖ) situés sur le chemin reliant cette feuille à la racine. Étant donnée une transaction émanant du compte a et affirmant un solde b, le validateur peut vérifier si b correspond bien au solde actuel du compte a en contrôlant la preuve (v₁, …, vₖ) associée à (a, b) par rapport à son état courant V. Si c’est le cas, le validateur exécute la transaction et met à jour en conséquence le solde du compte. Une propriété utile des arbres de Merkle est qu’à partir de la preuve d’appartenance d’une feuille, il est facile de recalculer la nouvelle racine lorsque cette feuille change. Autrement dit, le validateur peut aisément calculer un nouvel état V’ reflétant le nouveau solde du compte a après exécution de la transaction.
Ce schéma basé sur les arbres de Merkle présente deux inconvénients majeurs. Premièrement, les témoins des utilisateurs sont relativement volumineux, croissant logarithmiquement avec le nombre total de comptes dans le système. Idéalement, ils devraient être de taille constante, ce que l’on peut atteindre avec des constructions telles que les accumulateurs RSA.
Le second inconvénient est plus difficile à éviter : chaque fois qu’un autre utilisateur effectue une transaction, la preuve associée à une paire (compte, solde) change. Rappelons que la preuve d’une feuille est constituée des nœuds voisins sur le chemin vers la racine. Si l’un de ces nœuds change à cause d’une modification d’une autre feuille, la preuve est invalidée, ce qui pose un problème pratique majeur. La plupart des utilisateurs de blockchains souhaitent simplement conserver passivement leurs fonds dans un portefeuille, et ne se connecter qu’au moment d’effectuer une transaction. Or, dans une telle blockchain sans état, les utilisateurs doivent continuellement surveiller toutes les transactions des autres pour maintenir leurs témoins à jour. Bien qu’un tiers puisse assurer ce suivi pour leur compte, cela s’écarte du modèle standard de blockchain sans état. En pratique, c’est un obstacle insurmontable qui impose un fardeau excessif aux utilisateurs.
Notre conclusion : sans état est impossible
Ce phénomène ne se limite pas à cette structure d’arbre de Merkle — tous les schémas connus de blockchains sans état exigent que les utilisateurs mettent fréquemment à jour leurs témoins, comme nous le démontrons ici. Plus précisément, nous montrons que le nombre d’utilisateurs devant mettre à jour leurs témoins croît approximativement de manière linéaire avec le nombre total de transactions effectuées par tous les utilisateurs.
Cela signifie que même si l’utilisatrice Alice n’effectue aucune transaction, son témoin peut néanmoins devoir être mis à jour à cause des transactions d’autres utilisateurs. Aussi longtemps que l’état concis stocké par les validateurs est trop petit pour capturer l’intégralité de l’état (c’est-à-dire l’ensemble complet des soldes des comptes), augmenter légèrement la taille de cet état n’apporte que peu d’amélioration. Nous illustrons ci-dessous, selon notre théorème, cette relation ainsi que le nombre de modifications de témoins requis quotidiennement pour différentes capacités de traitement des blockchains. Ces graphiques montrent le nombre minimal de modifications de témoins nécessaires même pour la meilleure blockchain sans état possible. Ici, « univers des données » désigne le nombre total de comptes dans le modèle par compte, ou le nombre total d’UTXO dans le modèle UTXO.
Au cœur de notre preuve se trouve un argument issu de la théorie de l’information. Un principe fondamental de cette théorie, formalisé par Claude Shannon, stipule que si Alice choisit aléatoirement un objet parmi un ensemble de taille 2ⁿ et souhaite indiquer à Bob lequel elle a choisi, elle doit lui envoyer au moins n bits. Si un schéma de blockchain sans état existait dans lequel les utilisateurs mettent rarement à jour leurs témoins, Alice pourrait transmettre son choix à Bob en moins de n bits — ce qui contredirait le résultat de Shannon. Une telle blockchain sans état ne peut donc pas exister.
Pour simplifier, nous décrivons ici une version légèrement affaiblie de la preuve : il n’existe aucune blockchain sans état dans laquelle les utilisateurs n’auraient jamais besoin de mettre à jour leurs témoins. L'idée centrale est qu'Alice utilise un schéma de blockchain sans état pour encoder un message destiné à Bob. Initialement, Alice et Bob connaissent tous deux l'ensemble complet des paires (solde, compte) des n utilisateurs. Supposons que chaque compte possède au moins une unité monétaire. Alice et Bob connaissent également l'état concis V de la blockchain sans état, ainsi que les témoins wi associés à chaque paire (ai, bi). Ils conviennent par ailleurs d'une correspondance entre les messages possibles et les sous-ensembles de comptes. Alice choisit un sous-ensemble A de comptes correspondant à son message, puis dépense une unité depuis chacun de ces comptes. Elle utilise la blockchain sans état pour communiquer ce choix à Bob, qui pourra ainsi retrouver le message.
Codage : Alice dépense une unité depuis chaque compte appartenant à A. En utilisant le schéma de blockchain sans état, elle calcule le nouvel état V’ et l’envoie à Bob.
Décodage : Pour chaque i, Bob vérifie si Verify(wi, (ai, bi)) est vrai. Il construit l’ensemble B des comptes ai pour lesquels Verify(wi, (ai, bi)) = false.
Bob réussit à reconstruire exactement l’ensemble choisi par Alice : B = A. D’abord, observons que si Alice a dépensé depuis le compte ai, la preuve associée à l’ancien solde ne devrait plus être acceptée — sinon, Alice pourrait réaliser un double dépense. Ainsi, pour chaque compte ai dans A, on a Verify(wi, (ai, bi)) = false, donc Bob inclut ai dans B. En revanche, Bob n’inclura jamais un compte dont Alice n’a pas dépensé, car le solde de ce compte n’a pas changé, et (rappelons-le, dans cette version affaiblie de l’énoncé) son témoin n’a jamais été mis à jour. Par conséquent, B est exactement égal à A.
Enfin, nous aboutissons à une contradiction en examinant le nombre de bits envoyés par Alice à Bob. Elle pouvait choisir parmi 2ⁿ sous-ensembles différents, donc selon la loi de Shannon, elle devrait envoyer au moins n bits à Bob. Or, elle n’envoie que l’état V’ de taille constante, qui est bien plus court que n bits.
Bien que nous ayons formulé cette preuve autour des blockchains sans état, Alice et Bob pourraient employer diverses autres structures de données authentifiées pour réaliser une communication similaire efficace, y compris des accumulateurs, des engagements vectoriels ou des dictionnaires authentifiés. Nous formalisons ces structures à l’aide d’une nouvelle abstraction appelée système de preuve révocable.
Conséquences des résultats
Nos résultats montrent que l’on ne peut pas « éliminer l’état par la cryptographie » : il n’existe aucune solution magique permettant de construire une blockchain sans état où les utilisateurs n’auraient jamais à mettre à jour leurs témoins. L’état ne disparaît pas ; il est simplement transféré des épaules des validateurs vers celles des utilisateurs, sous la forme de mises à jour fréquentes des témoins.
D’autres solutions prometteuses existent, qui s’écartent du modèle strict de blockchain sans état. Un relâchement naturel de ce modèle consiste à autoriser un tiers (ni utilisateur ni validateur) à stocker l’état complet. Ce tiers, appelé nœud de service de preuve, utilise l’état complet pour générer les témoins à jour destinés aux utilisateurs. Les utilisateurs peuvent ensuite utiliser ces témoins pour effectuer des transactions comme dans une blockchain sans état classique, tandis que les validateurs continuent de n’entretenir qu’un état concis. La conception des incitations dans ce système, notamment la manière dont les utilisateurs rémunèrent le nœud de service de preuve, constitue une direction de recherche ouverte intéressante.
Bien que notre discussion se soit concentrée jusqu’ici sur les blockchains de niveau 1 (L1), nos résultats ont également des implications pour les systèmes de niveau 2 (L2), tels que les serveurs de Rollup. Les rollups (qu’ils soient optimistes ou ZK) stockent généralement sur le L1 un engagement compact représentant un état volumineux sur le L2, comprenant les comptes de chaque utilisateur du L2. On souhaite que ces utilisateurs puissent retirer directement leurs fonds sur le L1 (sans dépendre du serveur L2), en publiant un témoin attestant de leur solde actuel. Ce mécanisme relève également de notre modèle de système de preuve révocable. En fait, on pourrait dire que les blockchains sans état existent déjà en pratique, sous la forme de rollups L2.
Malheureusement, cela signifie que notre résultat d’impossibilité s’applique directement : les témoins de retrait des utilisateurs dans un rollup doivent être fréquemment mis à jour, faute de quoi presque tout l’état du L2 devrait être écrit sur le L1. Ainsi, les rollups actuels supposent souvent l’existence d’un comité de disponibilité des données (parfois appelé « validium »), similaire au « nœud de service de preuve », qui aide les utilisateurs à calculer de nouveaux témoins lorsqu’ils préparent un retrait. Nos résultats confirment donc que l’avertissement figurant dans la documentation d’Ethereum — « Sans les données des transactions, les utilisateurs ne peuvent pas calculer les preuves de Merkle prouvant leur propriété des fonds et effectuer un retrait » — restera toujours valable.
Bienvenue dans la communauté officielle TechFlow
Groupe Telegram :https://t.me/TechFlowDaily
Compte Twitter officiel :https://x.com/TechFlowPost
Compte Twitter anglais :https://x.com/BlockFlow_News
a16z
