Merkle Root et Merkle Preuves

En lisant votre question, je soupçonne que la cause de votre confusion concerne le cadre dans lequel les arbres Merkle sont utilisés. Je pense que vous avez raison de dire que dans le monde Bitcoin, le paramètre est pris pour acquis et n’est généralement pas expliqué clairement.

Voici mes deux cents. Pour comprendre l’aspect efficacité des arbres Merkle, considérez les deux parties qui sont réellement impliquées dans le protocole  :

Un nœud complet Bitcoin qui a des blocs complets

Un nœud léger Bitcoin qui a des en-têtes mais qui veut vérifier qu’une transaction se trouve dans l’un des blocs complets

(Il peut être utile de mentionner que le protocole Bitcoin actuel ne fait pas permettre à un nœud léger de vérifier efficacement qu’une transaction est ne pas dans l’un des blocs.)

Premièrerappelez-vous que lors de la réception d’un nouveau bloc B avec l’en-tête de bloc H et les transactions T, le nœud complet fait ce qui suit  :

calcule h = SHA256(H), vérifie la preuve de travail en h et vérifie l’horodatage en H, etc

pour chaque transaction t \in T, vérifie la ou les signatures de t, vérifie que t ne double pas les dépenses et ajoute t comme feuille la plus à droite de l’arbre de Merkle du bloc actuel. (Rappelons qu’un arbre Merkle différent est calculé pour chaque bloc. Bien sûr, l’ajout de la transaction doit être fait dans un ordre canonique, de manière à obtenir le même hachage racine que dans l’en-tête de bloc H.)

après que tous les t \in T ont été vérifiés et ajoutés, calcule et magasins l’arbre Merkel, bien sûr tout calculer les hachages de nœuds intérieurs et le hachage racine r (comme illustré dans votre figure d’arbre de Merkle)

Crucialementvérifie que le hachage racine calculé r est égal au hachage racine dans l’en-tête de bloc H

Morale de l’histoire  : oui, vous avez raison de dire que pour prouver l’appartenance d’une feuille par rapport à une racine de Merkle r, le prouveur (dans ce cas, le nœud complet) a besoin des hachages de nœuds intérieurs  : il peut les mettre en cache ou les recalculer ( il y a de la littérature sur les compromis ici). (Je pense) Les nœuds complets Bitcoin mettent simplement en cache tous les hachages, comme détaillé à l’étape 3. Surtout, les hachages intérieurs ne sont pas partie du bloc B de 1 Mo  : ce serait une perte d’espace, car les nœuds complets peuvent simplement les recalculer à partir des feuilles (c’est-à-dire les TXN) et faire correspondre le hachage racine recalculé avec celui de l’en-tête du bloc. Notez que cela empêche les adversaires du réseau de falsifier les transactions.

Deuxièmerappelez-vous que lors de la réception d’un nouvel en-tête de bloc H, un nœud léger ne fait que l’étape (1) d’en haut.

Maintenant, voici le réglage dans Bitcoin  :

Le nœud complet contient tous les blocs, y compris les hachages de nœuds intérieurs calculés à l’étape 3 ci-dessus

Le nœud fin a tous les en-têtes de bloc. Rappelez-vous que chaque en-tête inclut la racine Merkle

Le nœud complet veut convaincre le nœud léger qu’une transaction t se trouve dans un bloc B avec l’en-tête de bloc H (que le nœud léger a bien sûr)

Thèse : Les arbres de Merkle permettent au nœud complet d’en convaincre efficacement les nœuds finsempêchant le nœud complet de changer t en t’ (ce qui permettrait à un nœud complet de tromper un nœud léger en lui faisant croire qu’il a été payé).

Preuve : Soit r la racine de Merkle dans H. Le nœud fin a les mêmes H et r. Le nœud complet a les nœuds intérieurs « sous » r mis en cache (rappelez-vous l’étape 3 du nœud complet). Le nœud complet extractions le chemin frère (déjà mis en cache) commençant à la feuille contenant la transaction t et remontant jusqu’à la racine r, en l’envoyant au nœud léger. Le nœud fin hache récursivement t avec les frères et sœurs reçus, obtenant un hachage racine r ‘(agitant la main ici, en supposant que vous comprenez les preuves de Merkle). Le noeud fin vérifie que r == r’.

qui n’a qu’un hachage racine de 256 bits r. (Bien sûr, le prouveur doit avoir toutes les feuilles et tous les nœuds intérieurs, comme indiqué précédemment.)

Naturellement, ce protocole garantit que le nœud complet ne peut pas « mentir » sur une transaction « sous » la racine r. De manière informelle, si une transaction est là, le nœud complet ne peut pas la changer en une transaction différente et forger une preuve pour celle-ci (c’est-à-dire, un chemin frère). Également de manière informelle, si une transaction n’est pas là du tout, le nœud complet ne peut pas falsifier une preuve de sa présence.

Pour répondre à vos questions:

Question A semble concerner le fonctionnement de l’adhésion à une transaction. Vous dites,

Pour ce faire, ne regarderiez-vous pas simplement la liste des hachages de feuilles pour déterminer si H(D) est là ? Pourquoi faire quoi que ce soit avec la racine Merkle ?

Je pense que tu as mal compris le réglage. Gardez à l’esprit que lorsque vous discutez de protocoles cryptographiques, il est tout à fait nécessaire de se référer aux parties par leur nom, plutôt que d’utiliser des pronoms ambigus comme « vous » et « je ». « Prover » et « verifier » peuvent être laconiques et ennuyeux, mais ils sont précis.

Question B devrait être répondu maintenant: le nœud complet a tous les hachages de nœud intérieurs. Il envoie le chemin frère au nœud fin, qui se contente de hacher de manière récursive à partir de la feuille en cours de vérification. Le nœud léger vérifie que la racine qu’il a obtenue correspond à la racine dans l’en-tête de bloc.

Questions C :

Bitcoin conserve-t-il les hachages de l’arbre Merkle non seulement pour les nœuds feuilles, mais pour l’ensemble de l’arbre jusqu’à la racine ?

Pas dans les blocs eux-mêmes : ce serait une perte d’espace comme mentionné précédemment. Les nœuds complets calculent les hachages intérieurs et le hachage racine et mettent tout en cache localement sur le disque (vraisemblablement, je n’ai pas réellement regardé le code source). Ensuite, ils sont prêts à fournir des preuves pour n’importe quelle transaction dans n’importe quel bloc à n’importe quel nœud léger.

Où exactement et comment stocke-t-il exactement ces informations ? Tout ce que je vois, c’est la racine de Merkle dans le bloc.

Vraisemblablement, sur disque dans la base de données du nœud complet. Mais pas dans le bloc  : ce sont des informations redondantes car les blocs contiennent des feuilles => peuvent calculer les hachages des nœuds intérieurs et du nœud racine.

Je pense avoir vu une fois une valeur Merkle pour un nœud de transaction, mais je n’ai jamais vu de métadonnées liées à des nœuds Merkle non arborescents dans la blockchain Bitcoin.

Ugh, je veux dire « Oui, car ce serait une perte d’espace pour stocker les hachages de nœuds intérieurs dans les blocs. » mais en lisant de plus près, je ne sais pas vraiment ce que vous entendez par « valeur Merkle pour un nœud de transaction » et « métadonnées liées aux nœuds Merkle non arborescents ».

J’espère que cela t’aides !