Horodatage par arbre de Merkle : explication

Si vous vous êtes demandé comment un service peut horodater des fichiers sur Bitcoin gratuitement alors qu'une transaction Bitcoin n'est pas gratuite, la réponse réside dans l'arbre de Merkle. Il est utile de comprendre ce mécanisme, car le compromis qu'il implique constitue la principale différence entre les services d'horodatage disponibles sur le marché.

Le problème résolu

Écrire une empreinte numérique sur une blockchain coûte de l'argent — des frais de transaction, payés dans la devise de la chaîne. Si chaque fichier nécessite sa propre transaction, chaque horodatage a un coût minimum incompressible.

Le groupement de nombreuses empreintes numériques en une seule transaction supprime ce plancher. La difficulté consiste à effectuer cette opération tout en permettant à quiconque de prouver que son empreinte spécifique figurait bien dans le lot, sans pour autant publier l'intégralité du groupe.

Fonctionnement d'un arbre de Merkle

Prenons un ensemble d'empreintes numériques. Associez-les deux par deux et hachez chaque paire. Associez ensuite les résultats et hachez-les à nouveau. Continuez jusqu'à ce qu'il ne reste qu'une seule empreinte.

h(A)  h(B)   h(C)  h(D)
   \  /         \  /
  h(AB)         h(CD)
      \        /
       h(ABCD)   ← la racine de Merkle

Cette valeur finale est la racine de Merkle, et elle engage toutes les données d'entrée. Modifiez l'une des empreintes originales et la racine change complètement.

Seule la racine est inscrite sur la chaîne. Une seule transaction, quel que soit le nombre de fichiers dans le lot.

Prouver que votre fichier a été inclus

Pour montrer que h(A) se trouve sous la racine, vous n'avez pas besoin de l'arbre entier. Vous avez besoin des frères situés le long du chemin allant de votre feuille jusqu'en haut — ici, h(B) et h(CD). N'importe qui peut recalculer :

h( h( h(A), h(B) ), h(CD) ) == la racine sur la chaîne ?

Cette courte liste de frères constitue la preuve de Merkle ou preuve d'inclusion. Pour un lot d'un million de fichiers, il s'agit d'environ vingt empreintes numériques, car la longueur du chemin croît avec le logarithme de la taille du lot, et non avec le lot lui-même.

C'est véritablement élégant. C'est le mécanisme derrière OpenTimestamps, et derrière la plupart des services d'horodatage gratuits.

Ce que vous abandonnez

Trois éléments, tous opérationnels plutôt que cryptographiques.

Vous devez conserver le fichier de preuve. La chaîne contient la racine, et non votre empreinte. Sans le chemin des frères, il est impossible de relier votre fichier à la transaction. Perdez la preuve et l'horodatage disparaît — la transaction seule ne vous sera d'aucune aide.

Il y a généralement un délai et une étape supplémentaire. Les lots sont fermés selon un calendrier. Tant que le lot n'est pas validé et confirmé, votre preuve est incomplète, et dans certaines conceptions, vous devez revenir plus tard pour la « mettre à niveau ». Beaucoup de gens ne le font jamais et s'en rendent compte des années plus tard.

La vérification demande des explications. Recalculer un chemin de Merkle est une opération simple pour un développeur, mais une surprise désagréable pour toute autre personne. Un enregistrement dont la vérification nécessite un tutoriel est un enregistrement plus faible face à un public non technique.

L'alternative : une transaction par fichier

L'autre approche consiste à inscrire chaque empreinte numérique dans sa propre transaction. C'est ce que nous faisons : l'empreinte de votre contenu va dans les données d'entrée d'une transaction Ethereum dédiée, où quiconque peut la lire sur Etherscan avec l'option « Afficher en UTF-8 ».

Aucune n'est cryptographiquement plus forte. Une preuve de Merkle est aussi solide qu'une écriture directe. La différence porte entièrement sur ce qui se passe ensuite, pour une personne qui n'est pas vous, tenant un artefact qu'elle ne comprend pas.

Quel choix faire

Si vous horodatez à grande échelle, si vous êtes à l'aise techniquement et fiable quant au stockage des fichiers, le groupement est excellent et le prix imbattable.

Si vous horodatez un petit nombre de documents importants, et que l'audience finale est un client, un assureur ou un tribunal, payer pour une écriture directe vous achète une preuve sans rien à perdre et sans rien à expliquer.

Le groupement est également le moyen sensé d'offrir un niveau gratuit, ce qu'il est utile de savoir lors de la comparaison des prix : un service facturant quelques centimes par certificat utilise presque certainement le groupement, tandis qu'un service facturant des dollars ne le fait probablement pas.