Merkle Trees: de plus en plus en usage – EricB10
Ralph C. Merkle ( photo ci-dessus), né en 1952, est l’un des pères fondateurs de la cryptographie à clé publique. Tout au long de sa carrière, il a développé et contribué à une liste de systèmes cryptographiques monumentaux, dont certains sont intégrés dans l’épine dorsale des protocoles et applications en ligne sur lesquels nous comptons dans la vie quotidienne. Dans cet article, nous examinerons son travail sur les arbres Merkle, comment ils fonctionnent, pourquoi et comment ils se développent.
La structure globale d’un arbre de Merkle est assez simple et est très familière aux informaticiens: un . Les arbres de données en ont un (fichier principal ou élément de données) qui est ensuite divisé ou divisé en – dans ce cas exactement un ou deux. En se ramifiant à nouveau, ces enfants deviennent alors aux enfants suivants et ainsi de suite. Le nœud enfant final de toute branche est appelé . Inversement, chaque nœud feuille en combinaison avec son (s’il en a un) donne son nœud parent et ainsi de suite, jusqu’à ce que le nœud racine d’origine soit reconstruit.
Les arbres Merkle diffèrent des arbres de données traditionnels d’une manière simple: ils utilisent le chiffrement de chaque élément de données plutôt que les données elles-mêmes. Des nœuds feuilles jusqu’à la racine, le processus fonctionne comme tel:
- Chaque nœud feuille est haché
- En remontant l’arbre vers la racine, chaque feuille ou hachage enfant est (combiné cryptographiquement) avec le hachage de son nœud frère
- Enfin, le hachage des nœuds parents supérieurs est XOR’d dans le nœud racine, ce qui équivaut précisément au hachage agrégé du morceau de données
Pendant de nombreuses années, les arbres de Merkle n’étaient guère plus qu’un tour de magie cryptographique. Mais comme cela est courant avec les percées mathématiques et informatiques, des années plus tard, il a commencé à jouer un rôle critique dans divers protocoles et projets logiciels. Les arbres Merkle sont principalement utilisés pour deux raisons:
- Ils permettent à un client ou à un serveur de valider efficacement le contenu de fichiers / données volumineux
- Ils permettent à un client ou à un serveur de valider n’importe quel segment ou sous-segment du fichier / des données sans posséder d’autres segments
Pour comprendre pourquoi Merkle Trees possède ces propriétés, il est important d’en savoir un peu plus sur les fonctions de hachage cryptographique. Les fonctions de hachage sont faciles à calculer dans une direction mais extrêmement difficiles à calculer dans la direction opposée. Par exemple, la norme industrielle SHA-256 peut être hachée en millisecondes, mais il faudrait théoriquement environ 3,85 × 10²⁹ ans pour inverser, selon l’informaticien Luke Dash Jr.
Dans le cas de Merkle Trees, la fonction de hachage est utilisée pour calculer le hachage de chaque segment de données qui devient les nœuds feuilles, puis XOR chaque nœud feuille avec les nœuds feuille / enfant frères dans les nœuds parents et ainsi de suite, jusqu’à le nœud racine ou . Si chaque segment des données est intact et inchangé, la racine de Merkle est exactement égale au hachage agrégé de l’ensemble du fichier ou de la donnée. Si même un bit d’information est modifié dans un segment, le hachage est complètement différent, ce qui se propage dans l’arborescence, résultant en une racine Merkle entièrement différente. Cette racine peut ensuite être comparée à la racine réelle / souhaitée et ainsi toute incohérence est détectée.
Une utilisation importante des arbres Merkle est des dossiers. Si un utilisateur / client tente de télécharger un fichier volumineux d’un coup et que quelque chose ne va pas, le fichier entier peut être corrompu et le processus de téléchargement complet devra être redémarré. À l’aide de Merkle Trees, l’utilisateur peut télécharger un segment plus petit des données et le hacher. En combinant ce hachage avec les hachages de chaque autre segment (trivialement petit à télécharger / vérifier par rapport aux données elles-mêmes), ils peuvent vérifier si des données ont été corrompues pendant le processus de téléchargement. Ces étapes se poursuivent pour chaque segment, de sorte que si la racine Merkle ne correspond à aucune étape du processus de téléchargement, elles savent quel segment des données a été corrompu. Il est important de noter que ce processus se déroule automatiquement en arrière-plan et ne nécessite aucune action de l’utilisateur réel.
Un autre endroit où nous voyons Merkle Trees utilisé est le système de contrôle de version distribué . Git gère et réconcilie de nombreuses versions différentes d’un logiciel tel qu’il est construit, modifié et mis à jour simultanément par de nombreux contributeurs. Git est à la fois rapide et sécurisé car au lieu de stocker et de comparer chaque instance du logiciel réel, il stocke et compare les hachages de chaque segment et version sous la forme d’un arbre Merkle. L’implémentation de Git est légèrement plus compliquée car il s’agit de quelques le long du chemin, mais la structure globale est celle d’un arbre Merkle.
Enfin, les arbres Merkle jouent un rôle clé dans la construction du blockchain. Lorsqu’un nœud Bitcoin diffuse une transaction vers le reste du réseau peer-to-peer et est inclus dans un bloc par un nœud d’exploration de données, le mineur hache cet ID de transaction avec tous les autres ID de transaction dans ce bloc. Ces hachages sont ensuite mis en paires et XOR’d dans un nouveau hachage et ainsi de suite sous la forme d’un arbre, jusqu’à la racine de Merkle. La racine est ensuite XOR’d une fois de plus avec quelques données supplémentaires concernant le bloc lui-même et le hachage du bloc précédent (formant la chaîne), ce qui aboutit finalement à un nouveau hachage de bloc. Bien qu’il soit impossible d’en déduire les détails d’une transaction particulière, les détails de toutes les transactions dans le bloc sont nécessaires pour calculer le hachage final du bloc.
En conclusion, Merkle Trees est un moyen très intelligent de maintenir et de vérifier les bases de données et les fichiers volumineux sur les réseaux d’utilisateurs / appareils. Lorsqu’elle est comparée à la racine Merkle d’origine, chaque élément de données doit rester complètement inchangé, sinon les racines ne s’aligneront pas. Alors que nous vivons à une époque de plus en plus numérique et que les systèmes distribués gagnent en popularité, il est probable que nous commencerons à voir de plus en plus d’arbres Merkle germer dans des endroits nouveaux et passionnants.
