Cairn · étude de l'existant
Avant d'écrire une ligne du protocole de démarrage léger, il fallait savoir ce que d'autres ont fait, publié et cassé. Voici l'état du terrain, et la position exacte de Cairn dessus.
Cairn n'a pas inventé le problème. Il est documenté depuis des années et chacun le traite à sa façon, sans que personne ne s'en soit débarrassé.
L'ensemble des sorties non dépensées de Bitcoin dépasse aujourd'hui 170 millions d'entrées, pour environ 11 gigaoctets sur disque, et il ne cesse de grandir. Ethereum poursuit depuis des années un chantier appelé statelessness qui, de l'aveu de sa propre documentation, reste à plusieurs années du réseau principal et dépend d'au moins deux autres chantiers pour aboutir. Une branche de ce chantier, l'expiration d'état, ressemble assez à Cairn pour mériter mieux qu'une ligne : elle a sa section à elle, plus bas.
La conséquence est celle que Cairn met en avant depuis le début : plus une chaîne réussit, plus il devient cher de la vérifier soi-même, et moins il reste de gens capables de le faire.
Chaque encart indique ce que Cairn en reprend, et ce qui l'en sépare. Le trait bleu marque un travail dont nous nous inspirons, le trait vert un endroit où nous divergeons volontairement, le trait ambre une approche que nous refusons. Une huitième famille, la plus proche de toutes par la construction, a sa section à elle juste après.
Remplace l'ensemble des sorties non dépensées par une forêt d'arbres de Merkle parfaits. Onze gigaoctets deviennent moins d'un kilooctet de racines. Le dépensier fournit une preuve d'appartenance avec sa transaction. Coût mesuré en rejouant la synchronisation complète : environ 25 % de téléchargement en plus.
Même objectif avec des accumulateurs RSA. CompactChain tient tout l'état dans deux engagements de taille constante, l'un sur les sorties créées, l'autre sur les dépensées ; MiniChain n'y met que les dépensées, les créées vivant dans une chaîne de Merkle en montagne. Les preuves d'appartenance RSA sont de taille constante, plus courtes que celles d'une forêt d'empreintes.
Chaque bloc porte une preuve à divulgation nulle que toute l'histoire précédente est valide. Vérifier la chaîne entière tient dans environ 22 kilooctets, constants ; le décompte technique du projet donne aujourd'hui un peu moins. C'est la réponse la plus complète au problème que Cairn attaque, et elle fonctionne.
Une boîte inactive depuis quatre ans doit un loyer, environ 0,14 ERG. Depuis le bloc 1 051 200, un mineur peut prélever ce loyer, ou prendre la boîte entière si elle ne le couvre pas.
Un régulateur asservi ajuste, à chaque période de difficulté, un plancher de valeur sous lequel une sortie devient définitivement indépensable. Six à douze mois de grâce pour consolider, puis c'est perdu. L'accueil de la liste a été franchement sceptique.
Un nœud neuf part d'un instantané de l'état plutôt que de l'origine : utilisable en une heure et demie au lieu de dix heures et plus. L'empreinte de cet instantané est écrite en dur dans le code source, et la vérification complète se poursuit ensuite en arrière-plan.
Prouve qu'un travail considérable a eu lieu en ne montrant que les blocs exceptionnellement lourds, dits superblocs. Ressources logarithmiques en la longueur de la chaîne. Le client de référence d'Ergo l'implémente et s'en sert pour ses nœuds légers.
Chaque en-tête engage un accumulateur de tous les en-têtes précédents. Un nouveau venu tire au sort un nombre logarithmique d'en-têtes, avec un tirage pondéré par le travail accumulé, et vérifie chacun contre cet engagement. Preuve de synchronisation inférieure à 500 kilooctets sur Ethereum, environ 6 600 fois plus petite qu'une preuve classique. Sécurité établie sous l'hypothèse d'un attaquant contrôlant moins de la moitié de la puissance de calcul. Zcash grave l'engagement d'en-têtes qu'il exige depuis 2020 ; le client complet n'y a été construit qu'en 2026, et c'est l'encart suivant.
Une équipe raconte ce qu'implanter FlyClient dans le nœud de Zcash coûte vraiment. Trois constats. Le modèle d'adversaire d'origine, à deux paramètres, n'a pas d'interprétation économique et se prête mal au déploiement ; un modèle à un seul paramètre, le budget de l'attaquant, réduit l'échantillonnage d'environ 37 % à sécurité égale. Les preuves sont dominées par la taille des en-têtes, 1 487 octets chacun sur cette chaîne, dont 1 344 pour la seule solution de preuve de travail. Et restructurer les en-têtes pour n'y garder que le nécessaire réduit les preuves de 71 %, au prix d'un changement de consensus.
Chaîne post-quantique lancée cette année, qui emploie les mêmes mots que nous : bounded state, arbre de Merkle creux, accumulateur en ajout seul pour l'historique. Signatures à usage unique, montants contraints à des puissances de deux, machine à covenants.
La première version de cette page rangeait ce chantier dans la file d'attente d'Ethereum et n'en disait rien de plus. Une relecture extérieure a corrigé cette paresse : sur le papier, c'est la construction la plus proche de la nôtre, et elle mérite d'être comparée point par point plutôt que citée en passant.
La proposition la plus aboutie de cette ligne date de 2021. Un arbre d'état par période, environ un an chacune. Seul l'arbre de la période en cours s'écrit ; les précédents sont gelés, et un nœud complet n'en garde que les racines. Un compte que personne n'a touché depuis une période est expiré : le réveiller demande un témoin, fourni par le dépensier ou par un tiers, vérifié contre ces racines. Et les producteurs de blocs sont censés garder l'arbre de la période précédente, pour que ce qui vient d'expirer ne demande de témoin à personne.
Il faut le dire tel que c'est : deux étages, un plafond tenu par le consensus sur la partie active, des preuves à la charge du dépensier, les racines seules chez le validateur, et même un amorti pour ce qui vient de tomber. La forme de Cairn, dessinée pour Ethereum, cinq ans avant nous. Nous ne l'avons pas apprise là, mais elle y était d'abord, et le taire serait la revendication excessive que cette étude s'interdit.
| Expiration d'état, proposition de 2021 | Cairn | |
|---|---|---|
| Ce qui est plafonné | L'état actif d'une période ; sa taille suit ce que le gaz laisse écrire en un an | Le tiroir : 131 072 billets, un nombre |
| La règle qui fait descendre | L'âge : une période sans être touché | La place : tiroir plein, le plus ancien descend |
| Ce que devient l'expiré | Des arbres gelés, un par période, que quelqu'un doit détenir quelque part | Une forêt dont chaque nœud garde 64 empreintes ; les feuilles chez les seuls archivistes |
| Qui fournit le témoin | Le dépensier, ou un tiers ; la proposition cite Etherscan | Le dépensier ; son portefeuille l'entretient seul, depuis les blocs |
| Ce que coûte le témoin | Une appartenance, plus une absence par période traversée : il s'allonge avec le sommeil | Une seule appartenance, 263 à 586 octets mesurés ; la durée du sommeil n'y change rien |
| Le retour d'absence | Trouver qui détient les arbres gelés | Trouver un archiviste : même dette, même question de rémunération ouverte |
| Ce dont ça dépend | Un nouvel arbre d'engagement, Verkle dans le texte et peut-être un autre depuis, des adresses allongées, et la migration d'une chaîne vivante | Des arbres de hachage, et une règle posée avant que le réseau ne porte de valeur |
| Statut | Recherche ; jamais implémenté sur le réseau principal | Implémenté ; réseau de test seulement |
Le plafond est un nombre, pas un âge. Une période d'un an borne un rythme, remis à zéro chaque année : la partie active grandit avec l'activité à l'intérieur de la période, et un an de succès pèse plus lourd qu'un an de calme. 131 072 est un effectif ; le succès n'y change rien, et c'est toute la thèse de ce projet.
Le témoin ne connaît pas le calendrier. Dans un modèle de comptes, une adresse peut renaître, donc réveiller un compte exige de prouver aussi qu'il n'a rien fait dans aucune des périodes traversées, et la proposition allonge les adresses pour rendre ces conflits tenables. Un billet naît une fois et meurt une fois : une preuve d'appartenance suffit, aucune preuve d'absence, rien à changer aux adresses. C'est le modèle en billets qui paie ici.
Le porteur peut se garder lui-même. Chez nous, tout ce qu'il faut pour tenir sa preuve à jour passe dans les blocs, et le portefeuille le fait sans rien demander à personne. Fabriquer un témoin de réveil demande les arbres gelés, que le dépensier ordinaire ne détient pas ; la proposition nomme un tiers qui les détiendrait.
La grâce est une règle, pas une attente. Les producteurs sont censés garder la période précédente ; rien ne les y oblige. Nos soixante-quatre blocs de grâce sont engagés dans la racine d'état que chaque bloc porte : un nœud qui en divergerait quitterait la chaîne.
Rien de neuf en dessous. Pas de nouvel arbre d'engagement à faire mûrir, pas de séparation des rôles à inventer : des hachages, et une frontière.
Leur utilisateur a un an devant lui avant la première friction ; le nôtre, sur une chaîne chargée, quelques heures avant la cave. C'est le prix du plafond en nombre, le whitepaper le chiffre, et l'expiration par l'âge est plus douce pour celui qui dort.
Et leur problème est plus dur que le nôtre. Des comptes qui se modifient sur place, des contrats qui ne peuvent pas garder leurs preuves eux-mêmes, et une chaîne vivante qui porte des centaines de milliards : poser une règle pareille après coup casse des choses, et c'est très exactement pour cela que ce chantier dure. Cairn n'a eu qu'à écrire la règle avant de porter quoi que ce soit. La comparaison flatte la chaîne jeune, pas ses auteurs.
C'est la découverte importante de cette étude, et il faut la regarder en face plutôt que la ranger en note de bas de page.
Il n'existe aucun point de compromis utile : un système doit soit garder un état global de taille linéaire en le nombre de comptes, soit exiger un rythme quasi linéaire de mises à jour de preuves chez ses utilisateurs.
Le résultat est de théorie de l'information, donc il ne dépend d'aucune hypothèse cryptographique et aucune construction future ne l'annulera. Les auteurs ajoutent une phrase qui nous concerne directement : tant que l'état succinct est trop petit pour contenir l'état complet, l'agrandir n'aide guère.
Traduit : on ne peut pas faire disparaître l'état par la cryptographie. On peut seulement décider qui le porte. Si les validateurs ne le portent plus, ce sont les détenteurs qui doivent tenir leurs preuves à jour, et un utilisateur qui ne fait rien voit malgré tout sa preuve vieillir parce que les autres, eux, transigent.
Cairn tombe de ce côté du dilemme, et l'avait déjà accepté sans savoir que c'était démontré. La cave est succincte, donc les preuves doivent être entretenues. Notre portefeuille le fait à chaque bloc, tout seul, et c'est très exactement le prix que le théorème rend inévitable.
Les auteurs nomment ensuite la seule relaxation praticable : des proof-serving nodes, des tiers qui détiennent l'état complet et fabriquent des preuves à jour pour les autres. Ils appellent à des travaux sur la façon dont ces tiers seraient rémunérés.
Ce sont nos archivistes. Ils sont dans la conception de Cairn depuis le premier jour, ouverts à tous et que personne ne paie, et ils y ont été mis pour une intuition. L'étude montre qu'ils n'étaient pas un confort mais une nécessité structurelle, et que la question de leur modèle économique est ouverte pour tout le monde, pas seulement pour nous.
Il ne fait pas tomber le théorème, et il faut le dire clairement. Ce qu'il change, c'est la population concernée. Les billets récents, qui sont ceux que l'on dépense le plus souvent, sont détenus en entier par tous les nœuds et ne demandent aucune preuve. L'entretien ne pèse que sur ce qui dort depuis longtemps.
Autrement dit : le théorème dit que quelqu'un doit payer. Cairn ne fait pas payer celui qui utilise sa monnaie normalement.
Le tableau ci-dessous ne compare pas des qualités mais des choix. Une colonne seule décide de tout le reste : le plafond est-il une règle du réseau, ou une préférence d'opérateur.
| Système | État plafonné par règle | Rien n'est détruit | Sans cérémonie ni valeur crue | Démarrage sans confiance |
|---|---|---|---|---|
| Bitcoin | Non | Oui | Oui | Intégral, ou instantané cru |
| Utreexo | Non, choix du nœud | Oui | Oui | Intégral |
| CompactChain | Non | Oui | Cérémonie RSA | Intégral |
| Ethereum, expiration d'état | En projet, par période | Oui, réveil sur témoin | Preuve d'enjeu, distribution | Point de contrôle cru |
| Mina | Vérifier oui, produire non | Oui | Preuve d'enjeu, distribution | Oui, preuve de 22 ko |
| Ergo | Non, découragé | Non, loyer | Oui | Intégral |
| Midstate | Non, mémoire seule | Oui | Oui | Instantané plus mille blocs |
| Cairn | Oui, 131 072 billets | Oui | Oui | Oui, 4 096 en-têtes ouverts |
Aucune de ces quatre pièces n'est une invention cryptographique. Ce sont des choix de protocole, et c'est là que doit être la nouveauté si elle doit être quelque part : la cryptographie de Cairn est délibérément ordinaire et bien connue.
Une réserve de méthode, qui vaut d'être écrite. Une recherche ne prouve pas une absence, et cette page en est elle-même la preuve : sa première version rangeait l'expiration d'état dans une file d'attente, et il a fallu une relecture extérieure pour la remettre à sa place, en section 3. Ce qui reste revendiqué sans équivalent l'est après cette correction, pas avant, et il restera utile de faire relire cette page par quelqu'un du domaine avant de la publier telle quelle.