Outils cryptographiques 101 — Comprendre les fonctions de hachage et les arbres de Merkle

Quel est le sujet de cet article ?

Les blockchains permettent aux humains de s’accorder sans avoir recours à des intermédiaires. Au lieu de reposer sur la confiance, elles s’appuient sur des preuves cryptographiques. Les primitives cryptographiques servent à fournir ces preuves. Mais de quoi s’agit-il ?

Dans cet article, nous étudions deux primitives cryptographiques essentielles aux preuves cryptographiques sur les blockchains : les fonctions de hachage et les arbres de Merkle. Nous explorerons les mécanismes fondamentaux des fonctions de hachage, verrons pourquoi elles sont importantes pour les blockchains et découvrirons les pointeurs de hachage. Nous examinerons ensuite les arbres de Merkle traditionnels et concurrents, en soulignant leur importance pour Solana.

Qu’est-ce qu’une primitive cryptographique ?

Une primitive cryptographique est une opération ou un algorithme fondamental pour construire des protocoles et des systèmes cryptographiques. Les primitives sont aux protocoles cryptographiques ce que les atomes sont aux molécules : les composants de base de solutions plus complexes. Les générateurs de nombres aléatoires, les schémas d’engagement et la cryptographie à clé publique sont autant d’exemples de primitives cryptographiques.

Seules, les primitives cryptographiques sont assez limitées. Combinées, elles assurent des fonctions de sécurité élémentaires telles que l’authentification, la confidentialité et l’intégrité. Leur combinaison est un processus très subtil qui exige une planification rigoureuse et une compréhension approfondie des interactions entre chaque primitive. Lors de ce processus, vous devez tenir compte des considérations de sécurité au regard des objectifs que vous souhaitez atteindre. Les méthodes de combinaison des primitives cryptographiques peuvent être réparties en trois grandes catégories :

• Composition séquentielle : application d’une primitive après une autre (p. ex. chaînage de hachages)
• Composition parallèle : utilisation simultanée et indépendante de primitives (p. ex. chiffrement et hachage simultanés des données)
• Composition hiérarchique : utilisation d’une primitive cryptographique à l’intérieur d’une autre (p. ex. arbres de Merkle)

Comprendre ce qu’est une primitive cryptographique, comment elle fonctionne et les subtilités liées à la combinaison de plusieurs primitives vous aide à comprendre et à concevoir des systèmes sécurisés et efficaces. La fonction de hachage est l’une des primitives cryptographiques les plus couramment utilisées et combinées.

Qu’est-ce qu’une fonction de hachage ?

Une fonction de hachage est une fonction cryptographique qui accepte des données de n’importe quelle taille et renvoie une valeur de taille fixe. La valeur renvoyée par cette fonction est appelée condensat, ou hash. Parmi les algorithmes de hachage populaires figurent : SHA-1, SHA-2, SHA-3, MD5 et Argon2. Les fonctions de hachage sont omniprésentes dans les blockchains. Il est donc essentiel de comprendre ce qu’elles sont et comment elles fonctionnent.

Une analogie simple

Imaginez que vous prépariez un somptueux gâteau au chocolat. Il comporte plusieurs couches, chacune composée de ses propres ingrédients. Pendant la cuisson, un ami vous envoie un message pour savoir ce que vous faites. Lui expliquer en détail comment vous avez préparé le gâteau et énumérer tous les ingrédients utilisés serait assez fastidieux. Vous décidez donc de lui envoyer une photo du gâteau au chocolat.

Ici, la photo du gâteau sert de hash : c’est une représentation simple et compacte de quelque chose de bien plus complexe. Votre ami ne connaîtra pas le moindre ingrédient utilisé, mais il aura une bonne idée de ce que vous venez de préparer. Supposons que votre gâteau au chocolat soit garni de framboises. Si vous les retiriez ou les remplaciez par des fraises, la photo de votre gâteau serait totalement différente du produit final. De même, toute modification des données hachées produirait une nouvelle valeur de hachage.

Propriétés d’une bonne fonction de hachage cryptographique

Reconnaissons que la définition précédente d’une fonction de hachage est trompeuse. Une fonction de hachage pourrait renvoyer un hash de taille variable. Elle pourrait aussi renvoyer le même hash pour deux entrées différentes. Il pourrait également être extrêmement facile de remonter le hash pour retrouver l’entrée d’origine. La définition précédente décrivait une bonne fonction de hachage cryptographique. Mais qu’est-ce qui rend une fonction de hachage cryptographique bonne ?

Une bonne fonction de hachage est déterministe : une même entrée produit toujours la même sortie. Si je hache l’entrée « baseball », cette fonction de hachage produira toujours le même hash, quel que soit le système. Cela signifie aussi, en partie, que le hash conservera la même taille, quelle que soit celle de l’entrée. C’est important pour l’efficacité du traitement et le stockage des données. Savoir qu’une entrée unique produira toujours une sortie unique et que ces sorties auront toujours une taille fixe est un signe évident d’une bonne fonction de hachage cryptographique.

Une bonne fonction de hachage résiste à la préimage. Cela signifie qu’il est irréalisable, sur le plan informatique, de retrouver l’entrée à partir de son hash. Ainsi, si une personne vous donne un hash, vous ne devriez pas pouvoir déterminer quelles données l’ont produit. Cela conduit également à l’idée que deux ensembles de données distincts ne doivent pas produire le même hash. Une bonne fonction de hachage est dite résistante aux collisions lorsque deux entrées quelconques ne produisent jamais le même hash.

Une bonne fonction de hachage obéit à l’effet avalanche : une légère modification de l’entrée doit produire un hash radicalement différent. Modifier un seul caractère doit générer un hash complètement différent. Ainsi, le résultat d’un hachage ne doit révéler aucune information sur l’entrée ni présenter de motifs reconnaissables. Observez la différence entre les hash dans la figure ci-dessus. Le renard roux qui « court » crée un hash radicalement différent de celui du renard roux qui « marche ». Rien n’indique non plus que ces deux hash contiennent des informations presque identiques.

Une bonne fonction de hachage doit être rapide à calculer. Les fonctions de hachage lentes ne sont pas adaptées aux calculs en temps réel ou quasi réel, comme la vérification des transactions. Une fonction lente pourrait devenir un sérieux goulot d’étranglement et limiter à la fois le débit et les performances du réseau. Une fonction de hachage rapide est indispensable à des performances efficaces et sécurisées sur la blockchain.

Pourquoi est-ce important pour les blockchains ?

Une blockchain est un registre décentralisé et distribué qui enregistre les transactions sur son réseau. Ces transactions sont regroupées dans des blocs, reliés de manière sécurisée au moyen d’une bonne fonction de hachage. Chaque bloc contient les données des transactions, un horodatage et le hash du bloc précédent. Comme le hash de chaque bloc dépend de celui du bloc précédent, toute modification du contenu d’un bloc changerait son hash et invaliderait tous les blocs suivants. Ce processus qui consiste à utiliser les hash précédents pour en générer un nouveau est appelé chaînage de hachages.

L’ajout d’un nouveau bloc à une blockchain est appelé une confirmation. Une confirmation vérifie et sécurise toutes les transactions du nouveau bloc ainsi que tous les blocs précédents. En effet, chaque nouvelle confirmation rend plus difficile la modification des blocs antérieurs. Pour modifier un bloc précédent, un attaquant devrait recalculer tous les hash précédents. Le chaînage de hachages garantit donc qu’il serait irréalisable de modifier la blockchain une fois qu’un bloc a reçu un nombre conséquent de confirmations.

En termes simples, une blockchain est une chaîne de blocs sécurisée par des fonctions de hachage. Mais comment pointe-t-on exactement d’un bloc vers un autre ? Certes, une fonction de hachage cryptographique sert à chaîner les blocs, mais comment pouvons-nous consulter les données des blocs précédents ? Je pensais qu’une bonne fonction de hachage cryptographique résistait à la préimage.

Qu’est-ce qu’un pointeur de hachage ?

Un pointeur est une variable qui contient l’emplacement où des données précises sont stockées en mémoire. Les données situées à cette adresse mémoire sont facilement accessibles puisque le pointeur « pointe vers » leur emplacement. Un pointeur de hachage est une structure de données similaire à un pointeur, mais il contient également un hash cryptographique des données référencées. Il vous indique donc où accéder à une donnée précise et vous permet de vérifier l’intégrité des données consultées.

La structure d’une blockchain peut être décrite plus précisément comme une liste chaînée utilisant des pointeurs de hachage. Le hash du bloc précédent est un pointeur de hachage qui désigne un ensemble de transactions ainsi qu’un hash de toutes ces transactions. Les pointeurs de hachage facilitent la liaison des blocs, garantissent l’intégrité de chaque bloc et permettent de vérifier que les nouveaux blocs ajoutés suivent correctement les précédents.

Les pointeurs de hachage servent à chaîner efficacement les blocs. Mais qu’en est-il des transactions contenues dans le bloc ? Si un bloc contenait mille transactions, ne serait-il pas coûteux de les vérifier individuellement ?

Qu’est-ce qu’un arbre de Merkle ?

Un arbre de Merkle est une structure de données utilisée pour organiser et vérifier de grands ensembles de données. Les données sont organisées en une structure arborescente dans laquelle chaque feuille, ou nœud, est étiquetée avec le hash d’un ensemble de données. Chaque nœud qui n’est pas une feuille correspond au hash de ses nœuds enfants. Les arbres de Merkle servent à vérifier les transactions incluses dans des blocs précis qui sont propagés sur la blockchain. Alors, comment fonctionnent-ils ?

Les transactions sont regroupées dans une liste pour former un bloc. Chaque transaction de la liste est hachée à l’aide d’une bonne fonction de hachage. Ces hash constituent les nœuds feuilles. Ces nœuds feuilles sont ensuite hachés deux par deux pour créer une nouvelle couche de hash. Ce processus se poursuit de façon itérative jusqu’à ce qu’il ne reste plus qu’un seul hash, appelé racine de Merkle. La racine de Merkle est stockée dans l’en-tête du bloc et fait office d’empreinte numérique de toutes les transactions de ce bloc. Nous pouvons également désigner la racine de Merkle comme le hash du bloc. Ainsi, lorsque nous disons qu’un nouveau bloc est relié au précédent au moyen du blockhash de ce dernier, nous affirmons que le bloc utilise la racine de Merkle du bloc précédent pour générer une partie du hash du nouveau bloc.

Les arbres de Merkle permettent de vérifier efficacement les transactions individuelles d’un bloc. Traditionnellement, pour vérifier une transaction précise, il faudrait vérifier chaque transaction, ce qui est coûteux et chronophage. Les arbres de Merkle fournissent un « raccourci » cryptographique, appelé preuve de Merkle, qui facilite ce processus. Une preuve de Merkle est un chemin allant du nœud feuille de la transaction jusqu’à la racine de Merkle. En vous appuyant sur la figure ci-dessus, imaginez un chemin allant de Data A à la racine de Merkle. Ce chemin inclut également les nœuds frères, c’est-à-dire les feuilles adjacentes à chaque nœud du chemin sans faire elles-mêmes partie de celui-ci. Un vérificateur peut calculer un hash en suivant le chemin de preuve, puis vérifier s’il correspond à la racine de Merkle. Si le hash obtenu correspond, le vérificateur peut être certain que la transaction est légitime et n’a pas été altérée.

Une feuille peut être modifiée en hachant les nouvelles données de la feuille et en recalculant la racine de Merkle. Cette nouvelle racine sert à vérifier les changements et invalide la preuve précédente. Sur un réseau à haut débit comme Solana, les validateurs peuvent recevoir très rapidement plusieurs demandes de modification des arbres de Merkle on-chain, par exemple au sein d’un même slot. Chaque modification des données devrait être recalculée séquentiellement, sans quoi chaque demande suivante serait invalidée par la demande précédente effectuée dans le slot. La modification des données d’une feuille et le calcul d’une nouvelle racine de Merkle sont très courants dans les blockchains. Alors, comment gérer des changements rapides ?

Qu’est-ce qu’un arbre de Merkle concurrent ?

Un arbre de Merkle concurrent est un arbre de Merkle optimisé pour les lectures et écritures simultanées. Il stocke un journal sécurisé des changements les plus récents, leur hash racine et la preuve permettant de le dériver. Ce journal est stocké on-chain dans un compte propre à l’arbre, avec un nombre maximal de modifications pouvant lui être apportées tant que la racine de Merkle reste valide. Ce nombre maximal de modifications est appelé maxBufferSize. Ainsi, lorsqu’un validateur reçoit rapidement plusieurs demandes de modification d’un arbre de Merkle on-chain, il peut utiliser ce journal comme source de vérité et autoriser jusqu’à maxBufferSize modifications de l’arbre dans le même slot.

Les arbres de Merkle concurrents améliorent les arbres de Merkle traditionnels et les rendent adaptés aux environnements à haut débit tels que Solana. Pour créer un arbre de Merkle concurrent on-chain sur Solana, trois propriétés influencent la taille de l’arbre, son coût de création et le nombre de modifications simultanées qui peuvent lui être apportées :

• Profondeur maximale
• Taille maximale du tampon
• Profondeur de la canopée

La profondeur maximale désigne le nombre maximal de sauts nécessaires pour aller de n’importe quelle feuille à la racine de Merkle. maxDepth sert à déterminer le nombre maximal de nœuds à stocker dans l’arbre. Il peut être calculé avec la formule suivante : numberOfNodes = 2 ^ maxDepth. La profondeur d’un arbre doit être définie lors de sa création. Il est donc important d’utiliser cette formule pour déterminer le nombre de données que vous souhaitez y stocker.

Comme indiqué précédemment, la taille maximale du tampon désigne le nombre maximal de modifications pouvant être apportées à un arbre tout en maintenant la validité de sa racine de Merkle.

La profondeur de la canopée désigne un sous-ensemble de l’arbre de Merkle stocké on-chain. Ces preuves mises en cache servent à comparer un hash à la racine de Merkle on-chain. Le chemin de preuve complet doit être utilisé pour vérifier la propriété d’origine d’une feuille lors d’une opération d’écriture sur celle-ci. Par exemple, vous écririez dans l’arbre lors du transfert d’un NFT. La canopée permet de réduire la taille de la preuve et évite d’utiliser une preuve de taille maxDepth pour vérifier l’arbre. Un arbre dont la maxDepth est de 20 nécessiterait une preuve de taille 20. Avec une canopée de 15, il suffit de soumettre une preuve de taille 5 pour chaque transaction d’écriture. Une canopée plus profonde implique donc un coût initial plus élevé, mais permet de soumettre ultérieurement des preuves plus petites.

La profondeur de la canopée est l’un des principaux facteurs déterminant le coût de création d’un arbre. En effet, plus elle est grande, plus le compte requis est volumineux. Les développeurs peuvent utiliser le package @solana/spl-account-compression pour calculer l’espace requis pour une taille d’arbre donnée et le coût d’allocation de cet espace à l’arbre on-chain. Ils peuvent utiliser la fonction getConcurrentMerkleTreeAccountSize pour calculer l’espace requis par un compte donné selon ses paramètres, puis utiliser getMinimumBalanceForRentExemption sur l’espace requis afin d’obtenir le coût final en lamports.

Solana utilise des arbres de Merkle concurrents pour la compression d’état. La compression d’état consiste à créer un hash des données off-chain et à le stocker on-chain afin de permettre une vérification sécurisée. Les NFT compressés sont le cas d’usage le plus courant de la compression d’état, car celle-ci réduit considérablement le coût de création. Par exemple, la création d’un milliard de NFT sur Solana coûterait 507 $SOL, contre 12 000 000 $SOL avec des NFT « classiques ». Maintenant que vous comprenez bien le hachage et les arbres de Merkle, nous étudierons les NFT compressés dans un prochain article !

Conclusion

Félicitations ! Dans cet article, nous avons analysé les fonctions de hachage et les arbres de Merkle, deux primitives cryptographiques essentielles aux blockchains. Comprendre les blockchains n’est pas une mince affaire : ce sont des systèmes distribués complexes qui exigent de vastes connaissances techniques. Souvent, on suppose que le développeur, l’utilisateur ou l’investisseur moyen possède déjà ces connaissances. Cet article ne suppose aucune connaissance préalable des primitives cryptographiques. Nous commençons au contraire par les notions de base avant de progresser vers des explications plus complexes sur les arbres de Merkle traditionnels et concurrents. Il est indispensable de maîtriser ces fondamentaux avant d’aborder des sujets plus complexes tels que les NFT compressés. Grâce à ces nouvelles connaissances, vous êtes mieux préparé à explorer des bases de code ou à participer à des discussions sur les primitives cryptographiques et les solutions cryptographiques plus complexes.

Si vous avez lu jusqu’ici, anon, merci !

Ressources supplémentaires / Pour aller plus loin

• Chapitre détaillé consacré aux primitives cryptographiques
• Article comparant les algorithmes de hachage sécurisés
• Algorithmes de hachage et sécurité — vidéo YouTube de Computerphile
• Vidéo YouTube concise sur les arbres de Merkle
• Découvrir la compression des NFT sur Solana