💻 computer science

Parent-Hash DAG: A Cost Analysis of Constant-Time Append for On-Chain Registries

Cet article présente et analyse formellement le Parent-Hash DAG (PHDAG) en tant qu'alternative à temps constant et économique en gaz aux arbres de Merkle incrémentaux pour les registres on-chain, démontrant, par une modélisation théorique et des bancs d'essai empiriques, que le PHDAG maintient des coûts invariants par rapport à la profondeur alors que les coûts des arbres de Merkle croissent linéairement, rendant ainsi le PHDAG supérieur pour toutes les profondeurs de production pratiques.

Auteurs originaux : Ian C. Moore, Fernando Paredes Garcia

Publié 2026-06-09

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ian C. Moore, Fernando Paredes Garcia

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous gérez une bibliothèque numérique où les gens viennent enregistrer de nouveaux livres. Chaque fois que quelqu'un ajoute un livre, la bibliothèque doit mettre à jour sa liste maîtresse. La question posée par ce document est la suivante : Quelle est la manière la plus efficace de mettre à jour cette liste à mesure que la bibliothèque passe de quelques livres à des millions ?

Les auteurs comparent deux façons différentes d'organiser cette bibliothèque : l'Arbre de Merkle Incrémental (IMT) et le DAG de Hash de Parent (PHDAG).

Voici le détail de leurs conclusions en utilisant des analogies simples.

1. Les deux approches

L'Arbre de Merkle Incrémental (IMT) : La « Tour de Blocs »

Considérez l'IMT comme une gigantesque tour de blocs parfaitement symétrique.

Comment cela fonctionne : Chaque fois que vous ajoutez un nouveau livre (une feuille), vous devez grimper la tour, mettre à jour le bloc situé directement au-dessus, puis celui au-dessus, et ainsi de suite jusqu'au sommet (la racine).
Le Coût : Plus la tour devient haute, plus l'ascension est longue. Si la bibliothèque possède 1 000 livres, vous grimpez un court chemin. Si elle en possède 1 million, vous montez bien plus haut.
Le Problème : Le coût (en « gas », qui est comme les frais d'énergie pour effectuer la mise à jour) augmente à mesure que la bibliothèque grandit. C'est comme payer plus cher pour une course de taxi plus la distance est grande. De plus, le coût varie : parfois vous devez monter beaucoup d'escaliers, parfois moins, selon l'endroit exact où vous placez le nouveau livre.

Le DAG de Hash de Parent (PHDAG) : La « Chaîne de Lettres »

Considérez le PHDAG comme une chaîne de lettres échangées entre amis.

Comment cela fonctionne : Lorsque vous ajoutez un nouveau livre, vous écrivez simplement ses détails et vous rédigez une note disant : « Ce livre suit ce livre spécifique précédent ». Vous déposez cette note dans une boîte aux lettres publique (le journal d'événements de la blockchain). Vous n'avez pas besoin de grimper une tour ou de mettre à jour une racine centrale. Vous écrivez simplement votre note et vous la liez au passé.
Le Coût : Peu importe que la bibliothèque contienne 10 livres ou 10 millions. Vous écrivez toujours la même quantité de texte et vous la déposez dans la même boîte aux lettres.
Le Bénéfice : Le coût est constant. Il ne change jamais, peu importe la taille de la bibliothèque. C'est comme payer un tarif fixe pour envoyer une carte postale, quel que soit le nombre de cartes postales envoyées auparavant.

2. La Grande Découverte : Quand le changement s'opère-t-il ?

Les auteurs ont fait les calculs et mené des tests en conditions réelles sur un réseau de test (Base Sepolia) pour voir exactement quand la « Chaîne de Lettres » (PHDAG) devient moins chère que la « Tour de Blocs » (IMT).

Le Point de Bascule : Ils ont découvert que la « Tour » n'est moins chère que lorsque la bibliothèque est minuscule (environ 7 niveaux de profondeur).
La Réalité : Presque tous les systèmes réels qui utilisent ces registres (comme les outils de confidentialité ou les systèmes d'identité) sont beaucoup, beaucoup plus profonds que 7 niveaux. Ils font généralement entre 20 et 40 niveaux de profondeur.
Le Résultat : Dans le monde réel, la « Chaîne de Lettres » (PHDAG) est toujours moins chère et toujours prévisible.

3. Pourquoi est-ce important ? (Le problème de la « Variance »)

Imaginez que vous êtes un service de livraison facturant des frais fixes pour mettre à jour la bibliothèque.

Avec la Tour (IMT) : Parfois la mise à jour est peu coûteuse, parfois elle est coûteuse. Vous devez deviner le prix. Si vous vous trompez, vous pourriez perdre de l'argent lors des mises à jour coûteuses. Le coût « oscille » de haut en bas.
Avec la Chaîne (PHDAG) : Le prix est exactement le même. Il n'y a pas de devinette. Les auteurs ont constaté que le coût ne fluctue que d'environ 6 unités de gas (un montant infime), ce qui est pratiquement nul. Cela rend la chose incroyablement fiable pour les entreprises.

4. Le Superpouvoir de la « Reconstruction »

Il existe une autre différence majeure.

La Tour (IMT) : Pour prouver qu'un livre existe, vous avez besoin d'une « preuve » spécifique (un reçu montrant le chemin vers le haut de la tour). Si l'index central se brise, vous pourriez perdre la capacité de vérifier facilement toute la tour.
La Chaîne (PHDAG) : Toute l'histoire est écrite dans la boîte aux lettres publique (les journaux d'événements). Même si l'ordinateur qui gère la bibliothèque tombe en panne, n'importe qui peut parcourir la boîte aux lettres, lire les lettres dans l'ordre et reconstruire l'intégralité de la bibliothèque à partir de zéro. Elle est « indestructible » car l'histoire est dispersée à travers le registre public, et non verrouillée dans un seul emplacement de stockage.

5. Conclusion

Le document conclut que pour tout système à grande échelle du monde réel qui doit enregistrer un historique d'événements (comme prouver la propriété d'une œuvre d'art numérique ou suivre des chaînes d'approvisionnement) :

Arrêtez d'utiliser la Tour (IMT) pour ce travail spécifique. Elle devient trop coûteuse et imprévisible à mesure qu'elle grandit.
Commencez à utiliser la Chaîne (PHDAG). Elle est moins chère, son prix ne change jamais, et les données sont plus sûres car elles peuvent être reconstruites à partir des registres publics à tout moment.

Les auteurs suggèrent que la communauté blockchain adopte cette méthode de la « Chaîne de Lettres » comme règle standard pour tous les futurs registres de provenance, car c'est la manière la plus efficace et la plus robuste de gérer de grandes quantités de données.

Résumé Technique : Une Analyse des Coûts de l'Ajout à Temps Constant pour les Registres On-Chain

Énoncé du Problème

Les arbres de provenance (PTs) sont des graphes orientés acycliques (DAG) en mode ajout uniquement (append-only), utilisés comme substrat de données pour l'infrastructure de provenance à accès contrôlé par opérateur. Alors que des travaux antérieurs affirmaient que l'opération d'ajout sous-jacente pour les PT est de $O(1)$ en coût de gaz — indépendamment de la taille du registre et de la profondeur de l'arbre — cette affirmation manquait d'une isolation formelle en tant que primitive autonome, de bornes explicites et de tests empiriques par rapport au standard de l'industrie : l'Arbre de Merkle Incrémental (IMT).

L'IMT, dominant dans les protocoles zero-knowledge (ex: Tornado Cash, Semaphore) et les engagements d'état de rollups, offre des preuves d'inclusion succinctes en $O(\log N)$ mais incurre un coût d'ajout qui croît logarithmiquement avec la profondeur de l'arbre ( $\Theta(\log N)$ ). Pour les applications où les preuves d'appartenance succinctes ne sont pas la requête principale (telles que les registres de provenance), l'arbitrage de coût de l'IMT est moins favorable, pourtant le point de bascule où une alternative devient moins coûteuse n'a pas été rigoureusement établi.

Méthodologie

Le document isole le Parent-Hash Directed Acyclic Graph (PHDAG) en tant que primitive distincte et le compare à l'Incremental Merkle Tree (IMT) à travers trois perspectives :

Analyse de Complexité Formelle : Les auteurs formalisent l'opération d'ajout du PHDAG, prouvant qu'elle exécute un nombre borné d'opérations EVM indépendant de la taille du registre ( $n$ ) ou de la profondeur. Ils le contrastent avec la boucle de mise à jour de la frontière (frontier-update loop) de l'IMT, qui passe à l'échelle linéairement avec la profondeur ( $d$ ).
Modélisation Stochastique des Coûts : Reconnaissant que les coûts d'ajout de l'IMT varient selon la représentation binaire de l'indice de la feuille (poids de Hamming), les auteurs modélisent le coût par insertion comme une variable aléatoire. Ils dérivent des expressions en forme close pour la moyenne et la variance des coûts de l'IMT sous une distribution uniforme des indices de feuilles, distinguant les niveaux d'écriture ("write levels" pour la mise à jour de la frontière) et les niveaux de lecture ("read levels" pour la traversée sans écriture).
Validation Empirique : Des contrats indépendants pour les deux primitives ont été déployés sur le réseau de test Base Sepolia. Les expériences ont couvert des profondeurs d'arbres allant de 1 à 25.
- IMT : Testé via un "balayage de profondeur proportionnelle" effectuant $\max(d, 2)$ ajouts par profondeur pour capturer la variance.
- PHDAG : Testé via une série de 200 ajouts caractérisant la distribution des coûts et la variance.
- Métriques : La consommation de gaz a été mesurée à partir des reçus de transaction, excluant les coûts d'initialisation du stockage à froid (cold-storage) pour se concentrer sur la performance en régime permanent.

Principales Contributions

1. Complexité Formelle du PHDAG

Le document établit que l'ajout du PHDAG est strictement $O(1)$ en coût de gaz.

Mécanisme : Chaque ajout écrit dans trois emplacements de stockage précédemment non touchés (SSTOREs à froid) indexés par un identifiant unique, plus une écriture "chaude" (warm write) sur un compteur.
Invariance : Le coût est invariant par rapport à la taille globale du registre $n$ et à toute notion de profondeur d'arbre. La liste d'accès pour une transaction est réinitialisée au début de chaque transaction ; puisque le PHDAG écrit dans de nouveaux emplacements à chaque fois, le coût dépend uniquement du nombre fixe d'opérations, et non de l'état du contrat.
Reconstruction : Le document prouve que le registre complet peut être reconstruit à partir des journaux d'événements publics en temps $O(|V|)$ sans dépendance hors-chaîne, car le flux d'événements porte l'historique canonique.

2. Modèle Stochastique pour l'IMT

Les auteurs dérivent que le coût par insertion de l'IMT est une variable aléatoire $g$ dépendant de l'indice de la feuille $i$ :

Moyenne : $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$ , où $c_L$ et $c_R$ sont les coûts marginaux des niveaux d'écriture et de lecture, respectivement.
Variance : $Var[g] = (c_L - c_R)^2 \frac{d}{4}$ .
Implication : Bien que la variance relative (coefficient de variation) diminue à mesure que la profondeur augmente, l'écart-type absolu croît en $\Theta(\sqrt{d})$ , introduisant une imprévisibilité opérationnelle pour les registres de grande profondeur.

3. Point de Bascule Empirique et Validation

Performance du PHDAG : Mesurée à un taux constant de 76 276 gas par ajout (écart-type $\approx 6$ gas), confirmant l'invariance vis-à-vis de la profondeur.
Performance de l'IMT : Les coûts ont crû linéairement avec la profondeur.
Point de Bascule : La profondeur à laquelle le PHDAG devient moins cher que l'IMT a été identifiée à $d \approx 6$ à $7,2$.
- À $d=6$ , le coût mesuré de l'IMT ( $\approx 78 000$ gas) dépassait le coût du PHDAG.
- Le basculement moyen sur la durée de vie (distribution d'indice uniforme) est calculé à $d^* \approx 7,2$ .

Résultats

Les données empiriques valident les modèles théoriques :

Le PHDAG présente une variance négligeable et un coût constant à travers toutes les profondeurs testées.
L'IMT présente une croissance de coût linéaire et une variance absolue croissante avec la profondeur.
Contexte de Production : Chaque registre de production recensé (Tornado Cash, Semaphore, zkSync, Scroll, Linea) opère à des profondeurs $d \ge 20$ . Par conséquent, tous ces systèmes opèrent actuellement dans le régime où le PHDAG est strictement moins cher et offre des coûts prévisibles, à condition que l'application ne nécessite pas de preuves d'inclusion succinctes.

Signification et Revendications

Le document affirme que la primitive PHDAG est le meilleur choix pour les registres de provenance en mode ajout uniquement où :

Les preuves d'appartenance succinctes ne sont pas requises : Les requêtes de provenance impliquent généralement une traversée de la chaîne parente ou des vérifications d'existence par ID unique, ce qui est supporté par une reconstruction basée sur les logs en $O(|V|)$ plutôt que par des preuves de Merkle en $O(\log N)$ .
La prévisibilité des coûts est critique : Pour les opérateurs gérant des services d'ajout à haut volume, la variance quasi nulle du PHDAG élimine la nécessité de budgétiser pour les queues de distribution de gaz extrêmes (worst-case gas tails), un avantage opérationnel significatif par rapport à l'IMT aux profondeurs de production.
La robustesse est primordiale : La conception log-canonique du PHDAG garantit que l'historique du registre est indestructible et reconstructible à partir des seuls journaux d'événements publics, indépendamment de tout service d'indexation hors-chaîne ou de l'état actuel du stockage du contrat.

Les auteurs concluent que le PHDAG est un candidat sérieux pour une standardisation en tant qu'interface uniforme pour l'infrastructure de provenance sur Ethereum, offrant une alternative à coût constant et invariante par rapport à la profondeur, contrairement à l'IMT qui dépend de la profondeur pour les applications non-ZK.