a16z : Pourquoi les blockchains apatrides ne peuvent pas exister

Auteur : Miranda Christ (doctorante en informatique à l'Université de Columbia/stagiaire de recherche sur le cryptage a16z), Joseph Bonneau (a16zcrypto) Source : a16z crypto ; Compilateur : Yvonne, MarsBit

À mesure que la blockchain prend en charge davantage d'utilisateurs et des transactions plus fréquentes, la quantité d'informations (« état ») stockées par les validateurs pour vérifier les transactions augmente. Par exemple, dans Bitcoin, l’état consiste en un ensemble de résultats de transaction non dépensés (utxo). Dans Ethereum, l’état se compose du solde de chaque compte ainsi que du code et du stockage de chaque contrat intelligent.

Cette charge de stockage deviendrait ingérable pour une blockchain avec suffisamment de comptes ou d'UTXO pour prendre en charge les transactions quotidiennes réelles de la plupart des gens, ce qui rendrait difficile le rôle de validateur et constituerait une menace pour la décentralisation. Il est tentant de considérer la cryptographie comme une solution, et des outils tels que les arbres de Merkle et les preuves sans connaissance nous ont aidé à atteindre des objectifs auparavant incroyables.

C’est exactement l’objectif d’une « blockchain apatride ». Cependant, malgré de nombreux travaux dans ce domaine, ils sont encore loin d’être pratiques. Mais il s’avère que ce retard dans les progrès est inhérent : le fossé entre ces structures et l’aspect pratique ne pourra jamais être comblé. Nos travaux récents montrent que tout système de blockchain apatride, aussi intelligent soit-il, n’est pas réalisable sans mesures supplémentaires pour gérer l’État. Comme nous le démontrerons à la fin de cet article, cette issue improbable ne devrait pas être décourageante.

État apatride

Aujourd’hui, la taille de l’État est grande mais gérable. Par exemple, un nœud Bitcoin stocke environ 7 Go de données et un nœud Ethereum stocke environ 650 Go de données. Cependant, la charge de stockage sur les nœuds complets évolue à peu près de manière linéaire avec le débit de la chaîne (transactions par seconde, ou TPS), qui est actuellement inacceptablement faible. Selon la conception actuelle, l’état requis pour réellement prendre en charge les transactions quotidiennes (des centaines de milliers à des millions de TPS) deviendra ingérable, nécessitant l’utilisation de plusieurs téraoctets, voire pétaoctets d’espace de stockage.

Cela a incité les gens à rechercher des moyens techniques pour réduire considérablement la quantité d'état requise par les validateurs - une blockchain sans état obligerait les validateurs à stocker uniquement un état de taille constante, quel que soit le débit de la transaction. (En fait, le terme est un abus de langage : il existe toujours un état, juste assez petit pour s'adapter à tout débit futur, souvent de taille constante.) Cette exigence de stockage léger facilitera l'exécution des nœuds de validation ; avec un certain optimisme, chacun pourra exécuter un nœud sur son propre réseau. téléphone. Puisque l’augmentation du nombre de validateurs augmentera la sécurité de la chaîne, il est important de réduire les barrières à l’entrée des validateurs.

Malgré de nombreuses recherches sur les blockchains apatrides (par exemple Todd, Buterin, Boneh et al., Srinivasan et al.), elles sont loin d’être pratiques et, à notre connaissance, aucune n’a été déployée. Le problème fondamental de toutes les blockchains apatrides connues est qu’elles obligent les utilisateurs à stocker des données supplémentaires appelées témoins pour aider les validateurs à vérifier les transactions impliquant leurs comptes. Par exemple, ce témoin pourrait être une preuve d'inclusion Merkle, montrant que le compte de l'utilisateur et son solde sont inclus dans l'engagement global de l'État. Lorsqu'un utilisateur effectue une transaction, il soumet ce témoin à un validateur, montrant que son compte dispose d'un solde suffisant.

Contrairement au stockage des clés privées qui n'ont jamais besoin d'être modifiées, ces témoins changent fréquemment, même pour les utilisateurs qui n'effectuent pas activement de transactions, ce qui impose une charge irréaliste aux utilisateurs. De même, imaginez si vous deviez constamment surveiller toutes les autres transactions par carte de crédit dans le monde et mettre à jour certaines données locales en conséquence pour utiliser votre propre carte de crédit. Pour qu’une blockchain soit pratique, les utilisateurs doivent pouvoir rester hors ligne et interagir avec la blockchain uniquement lors de la soumission de transactions. Dans de nombreux cas, comme dans le cas des portefeuilles matériels, la mise à jour des témoins est non seulement peu pratique, mais impossible.

Cela nous amène à une question de recherche naturelle : pouvons-nous construire une blockchain apatride qui n'a pas besoin de mettre à jour les témoins (ou qui a rarement besoin de mettre à jour les témoins) ? Pour répondre à cette question, nous développons un nouveau cadre théorique (qui peut être un système de preuve de révocation), qui généralise les blockchains apatrides. En utilisant ce cadre, nous démontrons un résultat définitivement impossible : le compromis entre un état global compact et des mises à jour fréquentes des témoins est fondamental. Notre technique de preuve est basée sur la théorie de l’information, ce qui signifie que les futurs ordinateurs ne seront pas assez puissants pour résoudre ce problème : le fossé entre la structure de la blockchain apatride et l’aspect pratique ne sera jamais comblé.

Fond de recherche

Pour aider à développer l’intuition des résultats impossibles, nous décrirons d’abord la construction naturelle mais inefficace d’une blockchain apatride à l’aide d’arbres Merkle. Notre objectif est que les validateurs déterminent si une transaction soumise par un utilisateur est valide — par exemple, si l'utilisateur dispose d'un solde de compte suffisamment important pour effectuer la transaction. Dans un système de blockchain sans état, les validateurs stockent un état de taille constante. Lorsque les utilisateurs effectuent une transaction, ils doivent inclure un témoin dans la transaction. Un validateur peut utiliser l'état actuel et la paire (transaction, témoin) soumise par l'utilisateur pour vérifier que l'utilisateur dispose d'un solde de compte suffisant pour effectuer la transaction.

Nous construisons d'abord un arbre Merkle où chaque paire (identifiant de compte, solde) (a, b) est incluse sous forme de feuille. L'état de taille constante V stocké par les validateurs est la racine de cet arbre, qui agit comme un engagement envers l'ensemble des paires de soldes de comptes. Chaque utilisateur conserve sa preuve Merkle d'inclusion de la paire (identifiant de compte, solde) comme témoin. La preuve Merkle d'inclusion d'une feuille ( a , b ) se compose de nœuds partenaires ( v 1 , …, vk ) le long de son chemin jusqu'à la racine de l'arbre. Étant donné une transaction effectuée par un utilisateur utilisant le compte a et réclamant un solde b, un validateur peut vérifier que b est bien le solde du compte a en vérifiant que (a, b) prouve (v 1 , …, vk ) avec son état actuel V . Si tel est le cas, le validateur exécutera la transaction et devra mettre à jour le solde du compte en conséquence. Une propriété pratique des arbres Merkle est que, étant donné la preuve de confinement Merkle d'une feuille, il est facile de calculer la racine résultante lorsque cette feuille change. En d'autres termes, un validateur peut facilement calculer un état V' mis à jour qui capture le nouveau solde du compte a après l'exécution de la transaction.

L'approche de l'arbre de Merkle présente deux inconvénients majeurs. Premièrement, le nombre de témoins utilisateurs est relativement important et augmente de manière logarithmique par rapport au nombre total de comptes dans le système. Idéalement, ils devraient être de taille constante, ce que nous pouvons réaliser en utilisant des schémas tels que les accumulateurs RSA (Boneh et al. dans le contexte des blockchains apatrides).

Le deuxième inconvénient est plus difficile à éviter : chaque fois que d'autres utilisateurs effectuent une transaction, la preuve du couple compte-solde change. Rappelez-vous que la preuve d'une feuille est constituée de nœuds partenaires sur le chemin allant de cette feuille à la racine de l'arbre. Si une autre feuille change, l’un de ces nœuds change, ce qui pose des problèmes en pratique. La plupart des utilisateurs de blockchain souhaitent conserver passivement leurs pièces dans un portefeuille, en se connectant uniquement lorsqu'ils souhaitent effectuer une transaction. Cependant, dans la pratique de cette blockchain apatride, les utilisateurs doivent surveiller en permanence les transactions des autres pour tenir leurs témoins au courant. (Bien que des tiers puissent effectuer cette surveillance pour le compte des utilisateurs, cela s'écarte du modèle standard de blockchain apatride. Nous aborderons cette question à la fin de cet article.) En fait, il s'agit d'un problème pour les blockchains apatrides. impose une lourde charge aux utilisateurs.

Notre conclusion : l'apatridie est impossible

Ce phénomène n'est pas propre aux structures arborescentes de Merkle : tous les systèmes de blockchain apatrides connus exigent que les utilisateurs mettent fréquemment à jour leurs témoins. Nous illustrons cela dans cet article. Plus précisément, nous montrons que le nombre d’utilisateurs devant mettre à jour leur témoin croît de manière à peu près linéaire avec le nombre total de transactions effectuées par l’ensemble des utilisateurs.

Cela signifie que même si l'utilisateur Alice n'a effectué aucune transaction, son témoin devra peut-être changer avec les transactions des autres utilisateurs. Tant que l’état compact stocké par les validateurs est trop petit pour capturer l’état complet (c’est-à-dire l’ensemble de tous les soldes des comptes), augmenter la taille de l’état compact n’aide pas beaucoup. Nous traçons cette relation en suivant le théorème ci-dessous, ainsi que le nombre de changements de témoins requis par jour pour les blockchains de différents débits. Ces graphiques montrent combien de fois le témoin doit changer pour une blockchain apatride optimale. Ici, le champ de données fait référence au nombre total de comptes (dans le modèle de compte) ou UTXO (dans le modèle UTXO).

Au cœur de notre preuve se trouve un argument de théorie de l’information. Un principe central de la théorie de l'information proposé par Claude Shannon est que si Alice choisit un objet au hasard dans un ensemble de taille 2n et souhaite dire à Bob quel objet elle a choisi, elle doit lui envoyer au moins n bits. S'il existe un système de blockchain sans état dans lequel les utilisateurs mettent rarement à jour leurs témoins, alors Alice peut dire à Bob quel objet elle a choisi en moins de n bits - Shannon prouve que cela est impossible. Par conséquent, une telle blockchain apatride ne peut pas exister.

Par souci de simplicité, nous décrirons ici une preuve d’une affirmation légèrement plus faible : il ne peut pas y avoir de blockchain apatride où les utilisateurs n’ont jamais besoin de mettre à jour leurs témoins. L'idée clé est qu'Alice code son message à Bob en utilisant un système de blockchain sans état. Initialement, Alice et Bob connaissent tous deux les paires complètes de soldes de compte pour les n utilisateurs. Supposons que chaque compte possède au moins une pièce. Alice et Bob connaissent également l'état succinct V de la blockchain sans état et les témoins wi de toutes les paires de soldes de compte ( ai , bi ). Alice et Bob s'accordent également sur un mappage entre les messages et les ensembles de comptes. Alice choisirait un ensemble de comptes A correspondant à son message et dépenserait les jetons de ces comptes. Elle utilisera la blockchain apatride pour communiquer avec Bob l'ensemble qu'elle choisit, et à partir de cet ensemble, il pourra apprendre quels sont ses messages.

Encodage : Alice dépense un jeton de chacun des comptes de A. À l'aide d'un schéma de blockchain sans état, Alice calcule un état V' mis à jour et envoie V' à Bob.

Décodage : Pour chaque i, Bob vérifie si Verify( wi , ( ai , bi )) . Bob génère l'ensemble de comptes B tel que Verify( wi , ( ai , bi )) = false.

Bob génère avec succès le même ensemble qu'Alice a choisi : B = A. Tout d'abord, notez que si Alice a dépensé un jeton du compte ai, aucun témoin supplémentaire de son ancien solde ne devrait être accepté - sinon, Alice pourrait doubler sa dépense. Par conséquent, pour chaque compte ai dans A, Verify( wi , ( ai , bi )) = false, et Bob inclura ce compte dans B. En revanche, Bob n'inclura jamais dans B le compte identifié par Alice. Il n'est pas possible de dépenser une pièce de monnaie, car les soldes de ces comptes restent les mêmes et (rappelez-vous la déclaration vague que nous essayions de prouver) leurs témoins ne changent jamais. Donc B est exactement égal à A.

Enfin, la contradiction est résolue en calculant le nombre de bits qu'Alice doit envoyer à Bob. Elle peut choisir 2n sous-ensembles de comptes possibles et, selon la loi de Shannon, elle doit envoyer au moins n bits à Bob. Cependant, elle n'envoie qu'un état V' de taille constante, bien plus court que n bits.

(Les lecteurs familiers avec la cryptographie remarqueront peut-être que nous passons ici sous silence certains détails ; par exemple, le décodage de Bob échoue avec une probabilité négligeable. Notre article comprend une preuve complète.)

Alors que nous décrivons nos preuves en termes de blockchains apatrides, Alice et Bob peuvent effectuer une communication similaire, trop efficace, en utilisant diverses autres structures de données authentifiées (par exemple, des accumulateurs, des engagements vectoriels). Nous formalisons ces structures de données en utilisant une nouvelle abstraction, que nous appelons systèmes de preuve réversibles.

IMPACT DES RÉSULTATS

Nos résultats montrent qu'il est impossible de « chiffrer l'état » : il n'existe pas de solution miracle qui nous permettrait de construire une blockchain sans état dans laquelle les utilisateurs n'auraient jamais à mettre à jour leurs témoins. L'état ne disparaît pas, mais est transféré du validateur à l'utilisateur, et poussé vers l'utilisateur sous la forme de témoins fréquemment mis à jour.

Certaines solutions potentielles existent, mais celles-ci s’éloignent du modèle blockchain strictement apatride. Ce modèle permet à un tiers (ni un utilisateur ni un validateur) d'être responsable du stockage de l'état complet. Cette partie est appelée nœud de service de preuve (avec les contrôles les plus stricts effectués par Srinivasan et al.), et elle utilise l'état complet pour générer des témoins à jour au nom des utilisateurs. Les utilisateurs peuvent ensuite utiliser ces témoins pour effectuer des transactions, tout comme dans une blockchain apatride classique, où les validateurs ne stockent toujours qu'un état compact. Le mécanisme d'incitation du système, en particulier la manière dont les utilisateurs rémunèrent les nœuds de preuve de service, constitue une direction de recherche ouverte et intéressante.

Bien que notre discussion se soit jusqu'à présent concentrée sur les blockchains L1, nos résultats ont également des implications pour les systèmes L2 tels que les serveurs de cumul. Un cumul (qu'il soit optimiste ou ZK) prend généralement un état important et le valide en utilisant une petite valeur stockée sur L1. Cet état inclut le compte de chaque utilisateur sur L2. Nous souhaitons que ces utilisateurs puissent retirer des fonds directement sur L1 (sans la coopération des serveurs L2) en publiant un témoin du solde de leur compte courant. Cette configuration est également une instance du système de preuve réversible dans notre modèle. En fait, on pourrait affirmer que les blockchains apatrides sont déjà mises en œuvre dans la pratique sous la forme de rollups L2.

Malheureusement, cela signifie que nos résultats d’impossibilité s’appliquent directement. Le témoin de retrait de cumul d'un utilisateur doit changer fréquemment, sinon la quasi-totalité de l'état L2 devrait être écrite dans L1. En conséquence, les collections d'aujourd'hui supposent généralement un comité de disponibilité des données (parfois appelé « comité de validité ») qui fonctionne comme un « nœud de service de preuve » qui aide les utilisateurs à calculer de nouveaux témoins lorsqu'ils sont prêts à quitter. Nos résultats suggèrent que les avertissements adressés aux utilisateurs dans la documentation Ethereum – « Sans accès aux données de transaction, les utilisateurs ne peuvent pas calculer les preuves Merkle requises pour prouver la propriété des fonds et effectuer des retraits. » – s'appliqueront toujours.

À mesure que les systèmes blockchain se développent, il deviendra encore plus important de développer des moyens plus efficaces de gérer l’état de la blockchain. Bien que nos résultats concernant l'exclusion des blockchains apatrides puissent sembler négatifs, les résultats d'impossibilité sont utiles pour les concepteurs de blockchain, car ils nous disent de concentrer nos recherches ailleurs, nous aidant idéalement à trouver des solutions viables plus rapidement.