a16z : Sur l'impossibilité de la « Blockchain apatride »

Écrit à l'origine par Miranda Christ et Joseph Bonneau

Compilation du texte original : Deep Tide TechFlow

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

À mesure que la blockchain se développe avec suffisamment de comptes ou d'UTXO pour prendre en charge les transactions quotidiennes réelles d'une partie importante de la population, cette charge de stockage deviendra ingérable, ce qui rendra difficile le rôle de validateur et constituera une menace pour la décentralisation. Une solution intéressante consiste à se tourner vers la cryptographie, où des outils tels que les arbres de Merkle et les preuves sans connaissance nous aident à réaliser des choses qui étaient auparavant inimaginables.

C’est exactement l’objectif d’une « blockchain apatride ». Mais malgré de nombreuses recherches à leur sujet, 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 constructions et l’aspect pratique ne sera jamais comblé. Nos travaux récents montrent que toute proposition de blockchain apatride, aussi intelligente soit-elle, n’est pas réalisable sans mesures supplémentaires pour gérer l’état. Cependant, comme nous le montrons à la fin de cet article, ce résultat d’improbabilité ne doit pas être décourageant.

pas de statut

Aujourd’hui, l’État est immense 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 de manière à peu près linéaire avec le débit de la chaîne (transactions par seconde, ou TPS), ce qui est encore inacceptable aujourd'hui. Tel qu’il est conçu actuellement, l’État requis pour réellement prendre en charge les transactions quotidiennes (des dizaines à des centaines de milliers de transactions par seconde) deviendrait ingérable, nécessitant des gigaoctets, voire des pétaoctets de stockage.

Cela a motivé les gens à trouver des moyens techniques pour réduire considérablement la quantité d'état requise par les validateurs. La mise en œuvre d'une blockchain sans état est cruciale, ce qui 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 être pratique à tout moment). débit - taille généralement constante). Cette exigence de stockage léger facilitera l'exécution d'un nœud de validation ; avec un certain optimisme, tout le monde pourra exécuter un nœud sur son téléphone. Puisque l’augmentation du nombre de validateurs augmente la sécurité de la chaîne, il est important d’abaisser la barrière à l’entrée des validateurs.

Malgré de nombreuses recherches sur les blockchains apatrides (par exemple par Todd, Buterin, Boneh et al., et 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 et le solde de l'utilisateur sont inclus dans l'engagement global de l'État. Lorsque les utilisateurs effectuent des transactions, ils soumettent ce témoin aux validateurs pour montrer que leurs comptes ont des soldes suffisants.

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 surveilliez constamment toutes les autres transactions par carte de crédit dans le monde et mettiez à 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 interagir avec la blockchain hors ligne et 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 ne nécessite pas de mises à jour fréquentes des témoins (ou une blockchain qui ne nécessite que des mises à jour peu fréquentes des témoins) ? Pour répondre à cette question, nous développons un nouveau cadre théorique (Revocable Proof System) qui généralise les blockchains apatrides. En utilisant ce cadre, nous démontrons un résultat improbable : le compromis entre un état global compact et des mises à jour fréquentes des témoins est intrinsèquement difficile à concilier. 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 construction d’une blockchain apatride et l’aspect pratique ne sera jamais comblé.

Contexte de nos recherches

Pour vous aider à comprendre nos résultats d’impossibilité, nous décrivons d’abord une manière naturelle mais inefficace de construire des blockchains apatrides à l’aide d’arbres 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 de compte suffisant 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 en tant que nœud feuille. L'état de taille constante V stocké par les validateurs est la racine de cet arbre, qui agit comme un engagement envers un ensemble de paires de soldes de comptes. Chaque utilisateur conserve son témoignage comme preuve d'inclusion Merkle. Une preuve d'inclusion Merkle pour une feuille (a,b) se compose de nœuds partenaires (v1,...,vk) le long du chemin allant de cette feuille à la racine de l'arbre. Étant donné une transaction par compte a et un solde réclamé b, un vérificateur peut vérifier que b est bien le solde du compte a en vérifiant la preuve (v1,...,vk) de (a,b) par rapport à son état actuel V. Si tel est le cas, le validateur exécute la transaction et doit mettre à jour le solde du compte en conséquence. Une propriété pratique des arbres de Merkle est que, étant donné une preuve d'inclusion de Merkle pour une feuille, il est facile de calculer la racine du résultat lorsque cette feuille change. En d'autres termes, le vérificateur peut facilement calculer un état V' mis à jour qui capture le nouveau solde du compte a après l'exécution de la transaction.

Ce schéma d'arbre de Merkle présente deux inconvénients majeurs. Premièrement, le témoignage d'un utilisateur est relativement important et croît de manière logarithmique avec le nombre total de comptes dans le système. Idéalement, ils devraient être de taille constante, et nous pouvons y parvenir en utilisant des systèmes tels que les accumulateurs RSA.

Le deuxième inconvénient est plus difficile à éviter : chaque fois qu'un autre utilisateur effectue une transaction, la preuve du solde du compte change. Rappelez-vous que la preuve d'un nœud feuille se compose des nœuds partenaires sur le chemin allant de ce nœud feuille à la racine de l'arbre. Si les autres nœuds feuilles changent, l’un des nœuds changera, provoquant un réel problème. La plupart des utilisateurs de blockchain souhaitent conserver passivement leurs pièces dans des portefeuilles et se connecter uniquement lorsqu'ils souhaitent effectuer des transactions. Cependant, dans une telle blockchain apatride, les utilisateurs doivent constamment surveiller les transactions des autres pour maintenir à jour les informations de leurs témoins. Bien qu’un tiers puisse effectuer cette surveillance au nom de l’utilisateur, cela s’écarte du modèle standard de blockchain apatride. En pratique, il s’agit d’un défi insurmontable pour les blockchains apatrides, qui impose une lourde charge aux utilisateurs.

Notre conclusion : l’apatridie n’est pas possible

Ce phénomène ne s'applique pas uniquement à ce type d'arborescence Merkle : tous les systèmes de blockchain apatrides connus exigent que les utilisateurs mettent fréquemment à jour leurs informations de témoin, ce que nous démontrons ici. Plus précisément, nous montrons que le nombre d’utilisateurs devant mettre à jour leurs informations de témoin croît de manière à peu près linéaire avec le nombre total de transactions effectuées par tous les utilisateurs.

Cela signifie que même si l'utilisateur Alice n'effectue aucune transaction, ses informations de témoin peuvent devoir 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), l’augmentation de la taille de l’état compact n’aide pas. Nous traçons cette relation ci-dessous sur la base de notre théorème, ainsi que du nombre de changements de témoins requis par jour pour les blockchains avec des débits différents. Ces graphiques montrent le nombre de fois qu’une blockchain apatride optimale aurait besoin de modifier les informations des témoins. Ici, l'univers de données fait référence au nombre total de comptes dans le modèle de compte ou au nombre total d'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, formalisé 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 apatride dans lequel les utilisateurs mettent rarement à jour les informations de leurs témoins, Alice peut indiquer à Bob quel objet elle a choisi avec moins de n bits, ce qui est impossible, comme l'a prouvé Shannon. Par conséquent, une telle blockchain apatride n’existe pas.

Par souci de simplicité, nous décrivons ici une preuve d’une affirmation légèrement plus faible : il n’existe pas de blockchain apatride où les utilisateurs n’ont jamais besoin de mettre à jour les informations de leurs témoins. Le fait est qu'Alice utilise un système de blockchain sans état pour coder son message à Bob. Initialement, Alice et Bob connaissent l'ensemble complet des paires de soldes de comptes 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 apatride et les témoins wi de toutes les paires de soldes de comptes (ai, bi). Alice et Bob s'accordent également sur un mappage entre les messages et les ensembles de comptes. Alice choisira un ensemble A de comptes correspondant à son message, et elle dépensera ensuite les pièces de ces comptes. Elle utilisera la blockchain apatride pour communiquer à Bob l'ensemble de son choix à partir duquel il pourra en apprendre davantage sur elle.

Encodage : Alice dépense une pièce de chaque compte en A. À l'aide d'un schéma de blockchain sans état, Alice calcule l'état mis à jour V' et l'envoie à Bob.

Décodage : Pour chaque i, Bob vérifie si Verify(wi, (ai, bi)) est vrai. 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, observez que si Alice dépense une pièce du compte ai, le témoin de son ancien solde ne devrait plus être accepté, sinon Alice pourrait dépenser deux fois. Par conséquent, pour chaque compte ai dans A, Verify(wi, (ai, bi)) = false, et Bob inclura ce compte dans B. D'un autre côté, Bob n'inclura jamais dans B les comptes à partir desquels Alice n'a pas dépensé de pièces, car les soldes de ces comptes restent les mêmes et (rappelez-vous la déclaration décontractée que nous voulons prouver) leurs témoins ne changeront jamais. Donc B est exactement égal à A.

Enfin, nous résolvons notre contradiction en calculant le nombre de bits qu'Alice devrait envoyer à Bob. Elle peut choisir 2 ^ n sous-ensembles, donc selon la loi de Shannon, elle devrait envoyer au moins n bits à Bob. Cependant, elle n'envoie qu'un état V' de taille constante, bien plus court que n bits.

Bien que nous ayons utilisé une blockchain sans état pour décrire notre preuve, Alice et Bob peuvent effectuer une communication efficace similaire en utilisant diverses autres structures de données authentifiées, notamment des accumulateurs, des engagements vectoriels et des dictionnaires authentifiés. Nous formalisons de telles structures de données en utilisant une nouvelle abstraction que nous appelons un système de preuve réversible.

Effet du résultat

Nos résultats montrent que vous ne pouvez pas « éliminer cryptographiquement l'état » et qu'il n'existe pas de solution miracle pour un système d'engagement qui nous permette de construire une blockchain sans état dans laquelle les utilisateurs n'ont jamais à mettre à jour leurs témoins. L'état ne disparaît pas, mais est transféré des validateurs et transmis aux utilisateurs sous la forme de mises à jour fréquentes des témoins.

Il existe d’autres solutions prometteuses qui s’écartent du modèle blockchain strictement apatride. Un assouplissement naturel de ce modèle est de permettre à un tiers (ni utilisateurs ni validateurs) d'être responsable du stockage de l'état complet. Ce tiers, appelé nœud de service d'attestation, utilise l'état complet pour générer les dernières informations de témoin pour l'utilisateur. Les utilisateurs peuvent ensuite effectuer des transactions en utilisant ces témoins comme dans une blockchain apatride classique, où les validateurs ne stockent toujours que l'état compact. Le mécanisme d’incitation de ce 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 Rollup. Les cumuls (qu'ils soient optimistes ou ZK) stockent généralement un engagement envers un grand état sur L1 avec une petite valeur. 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 courant de leur compte. Cette configuration est également une instance d'un système de preuve réversible dans notre modèle. En fait, on peut affirmer que les blockchains apatrides sont déjà mises en œuvre dans la pratique, sous la forme de L2 Rollups.

Malheureusement, cela signifie que nos résultats d’impossibilité s’appliquent directement. Le témoin de récupération 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 Rollups supposent aujourd'hui généralement l'existence d'un comité de disponibilité des données (parfois appelé « validium »), similaire à un « nœud de service de preuve » qui aide les utilisateurs à calculer de nouveaux témoins lorsqu'ils sont prêts à les extraire. Nos résultats montrent que l'avertissement adressé aux utilisateurs dans la documentation Ethereum : "Sans données de transaction, les utilisateurs ne peuvent pas calculer les preuves Merkle pour prouver la propriété des fonds et effectuer des retraits." s'appliquera toujours.