VT2021 Merkle Trees fiche - Revision history

Corentin.Humbert at 13:29, 13 December 2021

2021-12-13T13:29:25Z

← Older revision		Revision as of 13:29, 13 December 2021
Line 135:		Line 135:

	Dynamo DB est une base de données distribuée provenant en partie de la plateforme Amazon Web Services. C'est une base de données clé-valeur NoSQL, entièrement managée et serverless qui est conçue pour exécuter des applications hautes performances à n'importe quelle échelle. Dynamo DB héberge les données (values) dans des data nodes qui sont aussi appelés "virtual nodes" et chaque virtual nodes héberge une key-range (gamme de clés). Un Merkle tree est construit pour chaque key-range, où les feuilles de l'arbre sont les valeurs de la key-range data. La Merkle Root contient donc un résumé des données de chaque nœuds. De ce fait, en comparant les Merkle Roots de chaque virtual nodes qui possèdent les mêmes key-range, on peut donc surveiller la moindre différence et de repérer l'endroit divergent.		Dynamo DB est une base de données distribuée provenant en partie de la plateforme Amazon Web Services. C'est une base de données clé-valeur NoSQL, entièrement managée et serverless qui est conçue pour exécuter des applications hautes performances à n'importe quelle échelle. Dynamo DB héberge les données (values) dans des data nodes qui sont aussi appelés "virtual nodes" et chaque virtual nodes héberge une key-range (gamme de clés). Un Merkle tree est construit pour chaque key-range, où les feuilles de l'arbre sont les valeurs de la key-range data. La Merkle Root contient donc un résumé des données de chaque nœuds. De ce fait, en comparant les Merkle Roots de chaque virtual nodes qui possèdent les mêmes key-range, on peut donc surveiller la moindre différence et de repérer l'endroit divergent.
	=== File System (ZFS) ===

Corentin.Humbert at 10:42, 13 December 2021

2021-12-13T10:42:32Z

← Older revision		Revision as of 10:42, 13 December 2021
Line 120:		Line 120:
	=== Git ===		=== Git ===

	Git est un logiciel de gestion de versions décentralisé qui est beaucoup utilisé aujourd'hui. Tous les fichiers sont enregistrés sur l'ordinateur de tous les utilisateurs, à tout moment. Les Merkle trees permettent d'assurer que tout changement soit cohérent sur les ordinateurs de tous les utilisateurs. En comparant simplement le ~~hashages~~ des fichiers ou dossiers entre 2 différents commits, on peut facilement et surtout rapidement savoir si celui-ci a été modifié ou non.		Git est un logiciel de gestion de versions décentralisé qui est beaucoup utilisé aujourd'hui. Tous les fichiers sont enregistrés sur l'ordinateur de tous les utilisateurs, à tout moment. Les Merkle trees permettent d'assurer que tout changement soit cohérent sur les ordinateurs de tous les utilisateurs. En comparant simplement le hachage des fichiers ou dossiers entre 2 différents commits, on peut facilement et surtout rapidement savoir si celui-ci a été modifié ou non.

	=== Cryptomonnaie ===		=== Cryptomonnaie ===

	La cryptomonnaie a été très ~~popularisé~~ récemment, et continuer de s'étendre, notamment le bitcoin.		La cryptomonnaie a été très popularisée récemment, et continuer de s'étendre, notamment le bitcoin.
	Toutes les transactions de cryptomonnaie sont stockées dans des blocks, aussi appelés blockchain.		Toutes les transactions de cryptomonnaie sont stockées dans des blocks, aussi appelés blockchain.
	La cryptomonnaie utilise les Merkle Trees pour s'assurer la validation des transactions dans les blocks. En effet, les ~~blocks~~ contiennent un ID, qui ~~est~~ le ~~header~~ fields ~~hashé~~ (cf. image), et ~~parmi~~ ce ~~header~~ ~~hashé~~, une partie contient la racine de du Merkle Tree. De ce fait, elle permet de s'assurer de l'unicité de l'enregistrement des transactions dans le block.		La cryptomonnaie utilise les Merkle Trees pour s'assurer la validation des transactions dans les blocks. En effet, les blocs contiennent un ID, qui correspond à l'en-tête fields haché (cf. image), et au sein de cet en-tête haché, une partie contient la racine de du Merkle Tree. De ce fait, elle permet de s'assurer de l'unicité de l'enregistrement des transactions dans le block.

	=== Blockchain pruning ===		=== Blockchain pruning ===

	Pour continuer sur le sujet des cryptomonnaies, l'émondation ou l'élagage des blockchains est un sujet qui reste d'affût de nos jours. En effet, sachant que les blockchains grandissent de plus en plus actuellement, cela veut également dire que celles-ci prennent de plus en plus de place en terme de stockage. Par exemple, en Février 2021, la taille de la blockchain du Bitcoin est d'environ ~~380Go~~. De ce fait, l'élagage de la blockchain consiste à épurer l'arbre, en supprimant les informations de la blockchain non critiques de l'espace de stockage. Les ~~noeuds~~ pleins gardent une copie de tous ce qui est stockés dans la blockchain, notamment des informations qui ne sont plus forcément utiles. Sachant que l'objectif d'un Merkle Tree est de synthétiser et de relier de grandes quantités d'informations. Chaque ~~noeud~~ contient l'information de ses fils, et donc la proposition est d'élaguer les informations qui ne sont plus utiles ~~commes~~ les transactions utilisées, ne laissant que les branches contenant les ~~hashages~~ pour vérifier les autres transactions.		Pour continuer sur le sujet des cryptomonnaies, l'émondation ou l'élagage des blockchains est un sujet qui reste d'affût de nos jours. En effet, sachant que les blockchains grandissent de plus en plus actuellement, cela veut également dire que celles-ci prennent de plus en plus de place en terme de stockage. Par exemple, en Février 2021, la taille de la blockchain du Bitcoin est d'environ 380 Go. De ce fait, l'élagage de la blockchain consiste à épurer l'arbre, en supprimant les informations de la blockchain non-critiques de l'espace de stockage. Les nœuds pleins gardent une copie de tous ce qui est stockés dans la blockchain, notamment des informations qui ne sont plus forcément utiles. Sachant que l'objectif d'un Merkle Tree est de synthétiser et de relier de grandes quantités d'informations. Chaque nœud contient l'information de ses fils, et donc la proposition est d'élaguer les informations qui ne sont plus utiles comme les transactions utilisées, ne laissant que les branches contenant les hachages pour vérifier les autres transactions.

	=== Base de données (AWS Dynamo DB) ===		=== Base de données (AWS Dynamo DB) ===

	Dynamo DB est une base de données distribuée provenant en partie de la plateforme Amazon Web Services. C'est une base de données ~~key~~-~~value~~ NoSQL, entièrement managée et serverless qui est ~~designé~~ pour exécuter des applications hautes performances à n'importe quelle échelle. Dynamo DB héberge les données (values) dans des data nodes qui sont aussi appelés "virtual nodes" et chaque virtual nodes héberge une key-range (gamme de clés). Un Merkle tree est construit pour chaque key-range, où les feuilles de l'arbre sont les valeurs de la key-range data. La Merkle Root contient donc un résumé des données de chaque ~~noeuds~~. De ce fait, en comparant les Merkle Roots de chaque virtual nodes qui possèdent les mêmes key-range, on peut donc ~~monitorer~~ la moindre ~~différences~~ et de repérer l'endroit divergent.		Dynamo DB est une base de données distribuée provenant en partie de la plateforme Amazon Web Services. C'est une base de données clé-valeur NoSQL, entièrement managée et serverless qui est conçue pour exécuter des applications hautes performances à n'importe quelle échelle. Dynamo DB héberge les données (values) dans des data nodes qui sont aussi appelés "virtual nodes" et chaque virtual nodes héberge une key-range (gamme de clés). Un Merkle tree est construit pour chaque key-range, où les feuilles de l'arbre sont les valeurs de la key-range data. La Merkle Root contient donc un résumé des données de chaque nœuds. De ce fait, en comparant les Merkle Roots de chaque virtual nodes qui possèdent les mêmes key-range, on peut donc surveiller la moindre différence et de repérer l'endroit divergent.
	=== File System (ZFS) ===		=== File System (ZFS) ===

Line 141:		Line 141:
	=== Conclusion ===		=== Conclusion ===

	Les arbres de Merkle sont très pratiques pour effectuer de la validation de données dans un système pair à pair. Ils ne sont pas ~~difficile~~ à stocker puisque les seules données qu'ils contiennent (en dehors des blocs de données) vont être des hachages dont la taille varie autour de la centaine d'octets en fonction des algorithmes de hachage utilisés. Leur simplicité permet également une validation rapide des données puisqu'il suffit de faire des opérations de concaténation (très faible coût) et de calcul de hachage (coût faible en moyenne, peut varier suivant la fonction de hachage utilisée). La structure en arbre permet également d'apporter une certaine granularité et l'ajout de fonctionnement annexe par rapport à une simple concaténation des hachages de chaque bloc de données.		Les arbres de Merkle sont très pratiques pour effectuer de la validation de données dans un système pair à pair. Ils ne sont pas difficiles à stocker puisque les seules données qu'ils contiennent (en dehors des blocs de données) vont être des hachages dont la taille varie autour de la centaine d'octets en fonction des algorithmes de hachage utilisés. Leur simplicité permet également une validation rapide des données puisqu'il suffit de faire des opérations de concaténation (très faible coût) et de calcul de hachage (coût faible en moyenne, peut varier suivant la fonction de hachage utilisée). La structure en arbre permet également d'apporter une certaine granularité et l'ajout de fonctionnement annexe par rapport à une simple concaténation des hachages de chaque bloc de données.
	Enfin, la robustesse d'un arbre va entièrement dépendre des fonctions de hachages utilisées. Par exemple, si l'on voulait valider des données sensibles comme des transactions sur la blockchain, on ~~préferera~~ utiliser des fonctions sécurisées comme celles de la famille SHA plutôt qu'un simple md5.		Enfin, la robustesse d'un arbre va entièrement dépendre des fonctions de hachages utilisées. Par exemple, si l'on voulait valider des données sensibles comme des transactions sur la blockchain, on préférera utiliser des fonctions sécurisées comme celles de la famille SHA plutôt qu'un simple md5.

Corentin.Humbert at 10:28, 13 December 2021

2021-12-13T10:28:27Z

← Older revision		Revision as of 10:28, 13 December 2021
Line 18:		Line 18:

	'''Keywords:''' Merkle trees, binary trees, hash, data structure, validation, peer to peer		'''Keywords:''' Merkle trees, binary trees, hash, data structure, validation, peer to peer


	== Fonctionnement ==		== Fonctionnement ==
Line 63:		Line 64:

	Enfin, il est important de garder à l'esprit que toutes les méthodes mises en place ne résolvent pas le problème, elles visent simplement à ralentir considérablement les attaquants. Un attaquant disposant de suffisamment de temps et de puissance de calcul finira par retrouver n'importe quel mot de passe. Il y a également les récentes innovations au niveau des ordinateurs quantiques qui sont vouées à compromettre significativement les dispositifs de sécurité mis en place sur Internet aujourd'hui. Nous ne nous étendrons pas plus sur le sujet du hachage dans ce document, si vous désirez en apprendre davantage, je vous invite à cliquer sur les différents liens hypertextes présents dans cette partie.		Enfin, il est important de garder à l'esprit que toutes les méthodes mises en place ne résolvent pas le problème, elles visent simplement à ralentir considérablement les attaquants. Un attaquant disposant de suffisamment de temps et de puissance de calcul finira par retrouver n'importe quel mot de passe. Il y a également les récentes innovations au niveau des ordinateurs quantiques qui sont vouées à compromettre significativement les dispositifs de sécurité mis en place sur Internet aujourd'hui. Nous ne nous étendrons pas plus sur le sujet du hachage dans ce document, si vous désirez en apprendre davantage, je vous invite à cliquer sur les différents liens hypertextes présents dans cette partie.



Line 143:		Line 143:
	Les arbres de Merkle sont très pratiques pour effectuer de la validation de données dans un système pair à pair. Ils ne sont pas difficile à stocker puisque les seules données qu'ils contiennent (en dehors des blocs de données) vont être des hachages dont la taille varie autour de la centaine d'octets en fonction des algorithmes de hachage utilisés. Leur simplicité permet également une validation rapide des données puisqu'il suffit de faire des opérations de concaténation (très faible coût) et de calcul de hachage (coût faible en moyenne, peut varier suivant la fonction de hachage utilisée). La structure en arbre permet également d'apporter une certaine granularité et l'ajout de fonctionnement annexe par rapport à une simple concaténation des hachages de chaque bloc de données.		Les arbres de Merkle sont très pratiques pour effectuer de la validation de données dans un système pair à pair. Ils ne sont pas difficile à stocker puisque les seules données qu'ils contiennent (en dehors des blocs de données) vont être des hachages dont la taille varie autour de la centaine d'octets en fonction des algorithmes de hachage utilisés. Leur simplicité permet également une validation rapide des données puisqu'il suffit de faire des opérations de concaténation (très faible coût) et de calcul de hachage (coût faible en moyenne, peut varier suivant la fonction de hachage utilisée). La structure en arbre permet également d'apporter une certaine granularité et l'ajout de fonctionnement annexe par rapport à une simple concaténation des hachages de chaque bloc de données.
	Enfin, la robustesse d'un arbre va entièrement dépendre des fonctions de hachages utilisées. Par exemple, si l'on voulait valider des données sensibles comme des transactions sur la blockchain, on préferera utiliser des fonctions sécurisées comme celles de la famille SHA plutôt qu'un simple md5.		Enfin, la robustesse d'un arbre va entièrement dépendre des fonctions de hachages utilisées. Par exemple, si l'on voulait valider des données sensibles comme des transactions sur la blockchain, on préferera utiliser des fonctions sécurisées comme celles de la famille SHA plutôt qu'un simple md5.


	== Références ==		== Références ==

Corentin.Humbert at 10:27, 13 December 2021

2021-12-13T10:27:21Z

← Older revision		Revision as of 10:27, 13 December 2021
Line 111:		Line 111:
	[[File:Merkle_Tree_Validation.png\|500px\|thumb\|right\|'''Figure 5 :''' Validation de l'arbre de Merkle identifié par '''"b74b3"'''. L'arbre reçu (à droite) contient Data5 à la place de Data4, cette erreur est immédiatement détectée lors de la comparaison du hachage racine avec celui du fichier désiré]]		[[File:Merkle_Tree_Validation.png\|500px\|thumb\|right\|'''Figure 5 :''' Validation de l'arbre de Merkle identifié par '''"b74b3"'''. L'arbre reçu (à droite) contient Data5 à la place de Data4, cette erreur est immédiatement détectée lors de la comparaison du hachage racine avec celui du fichier désiré]]

	Dans les parties précédentes, nous avons vu ce qu'étaient les arbres de Merkle, et comment procéder pour en construire un. Toutefois, nous n'avons pas encore vu comment les ~~uiliser~~. Nous avons parlé brièvement du fait qu'ils servaient à faire de la validation de données mais nous n'avons pas encore détaillé ~~exactement~~ comment. C'est ce dont nous allons parler dans cette partie.		Dans les parties précédentes, nous avons vu ce qu'étaient les arbres de Merkle, et comment procéder pour les construire. Toutefois, nous n'avons pas encore vu comment les utiliser. Nous avons parlé brièvement du fait qu'ils servaient à faire de la validation de données, mais nous n'avons pas encore détaillé comment. C'est ce dont nous allons parler dans cette partie.

	~~Imaginons~~ ~~que~~ ~~nous~~ ~~voulions~~ ~~télécharger~~ un ~~fichier~~ ~~assez~~ ~~conséquent~~ ~~depuis~~ ~~Internet.~~ On ~~veut utiliser~~ un ~~système~~ pair à pair ~~pour télécharger le fichier~~. On ne va donc pas se connecter à un serveur unique qui détient le fichier désiré mais à une multitude de machines dans un réseau qui vont participer au téléchargement. Le ~~pair~~ à ~~pair~~ a de ~~nombreux~~ ~~avantages~~ ~~mais~~ nous ne ~~rentrerons~~ ~~pas~~ en ~~détail~~ ~~sur~~ ~~son~~ ~~fonctionnement~~ ~~dans~~ ce ~~document~~. L'un ~~des~~ ~~problèmes~~ ~~majeurs~~ ~~des~~ ~~architectures~~ ~~pair~~ à ~~pair~~ ~~est~~ la ~~confiance~~ que l'on ~~accorde~~ à ~~chaque~~ ~~machine.~~ En ~~effet~~, ~~contrairement~~ à ~~une~~ ~~architecture~~ ~~client-serveur~~ ~~classique~~ où le ~~serveur~~ ~~est~~ ~~une~~ ~~machine~~ ~~identifiée~~ et à ~~laquelle~~ on ~~fait~~ ~~généralement~~ ~~confiance,~~ la ~~modularité~~ des ~~systèmes~~ ~~pair~~ à ~~pair~~ ~~fait~~ que nous ~~soyions~~ ~~obligé~~ de nous ~~reposer~~ ~~sur~~ ~~des~~ ~~machines~~ ~~anonymes~~ et ~~potentiellement~~ ~~malicieuses.~~ Il ~~est~~ ~~impossible~~ de ~~vérifier~~ si ~~chaque~~ ~~machine~~ est ~~légitime~~ ou si l'une ~~d'entre~~ ~~elles~~ ~~tente~~ de nous envoyer un ~~fichier~~ ~~corrompu~~. ~~C'est~~ ~~justement~~ ~~pour~~ ~~pallier~~ ce ~~problème~~ ~~que~~ ~~nous~~ ~~pouvons~~ ~~utiliser~~ ~~les~~ ~~arbres~~ de ~~Merkle~~.		Prenons un exemple très simple : on veut télécharger un fichier en utilisant un réseau pair à pair. On ne va donc pas se connecter à un serveur unique qui détient le fichier désiré, mais à une multitude de machines dans un réseau qui vont participer au téléchargement. On dispose du hachage unique permettant d'identifier le fichier, ce hachage nous a été envoyé par une machine connue à laquelle on fait confiance. Le hachage, un peu à la manière d'un URL va permettre d'identifier le fichier au sein du réseau. On va donc indiquer le fichier que l'on désire télécharger en fournissant son hachage, et les machines du réseau vont s'occuper de nous envoyer les blocs de données. À ce niveau-là, nous ne pouvons rien dire sur la légitimité des machines qui nous envoient les blocs de données, il est possible que certaines d'entres elles soient malicieuses mais impossible pour nous de le vérifier. Toutefois, lorsque nous aurons reçu tous les blocs de données, nous allons pouvoir les valider en reconstruisant l'arbre de Merkle et en vérifiant que le hachage racine de l'arbre reconstruit est identique à celui que nous avions à l'origine. S'il s'agit du même hachage, alors le fichier est bien conforme. Si l'une des machines du réseau pair à pair a tenté de nous envoyer des données non-légitimes, on va pouvoir très facilement le détecter. En effet, comme chaque nœud dépend des nœuds qui le précèdent, le moindre changement va se propager et changer completement le hachage racine.

	Reprenons notre problèmatique de téléchargement de fichier. Ici, le fichier que l'on veut obtenir va être transformé en un arbre de Merkle. En d'autres termes, il va être divisé en un certain nombre de blocs que l'on va hacher un à un jusqu'à obtenir un hachage unique qui permet d'identifier l'intégralité du fichier (il s'agit de la racine de l'arbre). Nous avons donc un arbre plus ou moins massifs qui va représenter le fichier que nous voulons télécharger. Mais comment-va-t'on faire pour vérifier que le fichier que nous avons demandé est bien celui que nous avons reçu ?
	Tout repose sur le hachage racine. Si on part du principe que nous avons obtenu le hachage racine d'un tier auquel nous faisons confiance, nous allons pouvoir, par ce seul hachage, s'assurer que le fichier que nous obtenons soit bel et bien celui que nous voulions.


	Prenons un exemple très simple: On veut télécharger un fichier F en utilisant un réseau pair à pair. On dispose du hachage unique permettant d'identifier le fichier grâce à un tier à qui nous faisons confiance. Ce hachage, un peu à la manière d'un URL va permettre d'identifier le fichier au sein du réseau. On va donc indiquer le fichier que l'on désire télécharger en fournissant son hachage et les pairs vont s'occuper de nous envoyer les blocs de données. A ce niveau-là, nous ne pouvons rien dire sur la légitimité des machines qui nous envoient les blocs de données, il est possible que certaines d'entres elles soient malicieuses mais impossible pour nous de vérifier. Toutefois, lorsque nous aurons reçu tous les blocs de données, nous allons pouvoir les valider en reconstruisant l'arbre de Merkle et en vérifiant que le hachage racine obtenu est identique à celui que nous avions à l'origine. S'il s'agit du même hachage, alors le fichier est bien conforme. Si l'une des machines du réseau pair à pair a tenté de nous envoyer des données non légitimes, on va pouvoir très facilement le détecter. En effet, comme chaque noeud dépend des noeuds qui le précède, le moindre changement va se propager et changer completement le hachage racine.



	L'efficacité des arbres de Merkle a détecter le moindre changement de bit dans un fichier repose sur la nature des fonctions de hachage qu'il utilise. En effet, une particularité des fonctions de hachage est qu'elles sont très chaotiques et que le changement du moindre bit va complètement changer le hachage résultant.

Corentin.Humbert at 10:20, 13 December 2021

2021-12-13T10:20:48Z

Corentin.Humbert at 10:08, 13 December 2021

2021-12-13T10:08:19Z

Corentin.Humbert at 10:02, 13 December 2021

2021-12-13T10:02:24Z

← Older revision		Revision as of 10:02, 13 December 2021
Line 15:		Line 15:
	== Abstract ==		== Abstract ==

	Merkle trees are [https://en.wikipedia.org/wiki/Binary_tree binary trees] used in data validation. A tree consists of nodes and leaves. ~~the~~ leaves contain the cryptographic hash corresponding to a part of the data we want to validate. The nodes contain a hash obtained by concatenating the hashes of the two child nodes and passing the concatenated string through a hashing function. This overall process creates a dependance between the nodes where each node's hash depends on the hash values of the underlying nodes. Each Merkle tree is unique and specific data will always give the same tree. A common use for Merkle trees is the download of files in [https://en.wikipedia.org/wiki/Peer-to-peer peer-to-peer] networks. As it is impossible to verify the identity of machines in the network, it is necessary to use validation structures such as Merkle trees to ensure that the received data is the desired one.		Merkle trees are [https://en.wikipedia.org/wiki/Binary_tree binary trees] used in data validation. A tree consists of nodes and leaves. The leaves contain the cryptographic hash corresponding to a part of the data we want to validate. The nodes contain a hash obtained by concatenating the hashes of the two child nodes and passing the concatenated string through a hashing function. This overall process creates a dependance between the nodes where each node's hash depends on the hash values of the underlying nodes. Each Merkle tree is unique and specific data will always give the same tree. A common use for Merkle trees is the download of files in [https://en.wikipedia.org/wiki/Peer-to-peer peer-to-peer] networks. As it is impossible to verify the identity of machines in the network, it is necessary to use validation structures such as Merkle trees to ensure that the received data is the desired one.

	'''Keywords:''' Merkle trees, binary trees, hash, data structure, validation, peer to peer		'''Keywords:''' Merkle trees, binary trees, hash, data structure, validation, peer to peer
Line 23:		Line 23:
	=== Principe ===		=== Principe ===

	Imaginons que nous voulions télécharger un fichier dans un réseau pair-à-pair, comme on ne peut ~~pas~~ pas vérifier l'identité des machines sur le réseau, il est fort probable que certaines d'entre elles tentent d'envoyer des fichiers malveillants. Il faudrait donc mettre en place un ~~méchanisme~~ permettant d'identifier ces fichiers non désirés. Les arbres de Merkle sont une solution à ce problème. Un arbre de Merkle est un arbre binaire qui va permettre d'identifier de manière unique et sûre une ressource sur un réseau.		Imaginons que nous voulions télécharger un fichier dans un réseau pair-à-pair, comme on ne peut pas vérifier l'identité des machines sur le réseau, il est fort probable que certaines d'entre elles tentent d'envoyer des fichiers malveillants. Il faudrait donc mettre en place un mécanisme permettant d'identifier ces fichiers non désirés. Les arbres de Merkle sont une solution à ce problème. Un arbre de Merkle est un arbre binaire qui va permettre d'identifier de manière unique et sûre une ressource sur un réseau.

	Une fois qu'une donnée aura été mise en ligne sur un réseau pair-à-pair, on va la découper en plusieurs blocs et calculer les hachages pour chacun des blocs. Ces hachages de premier niveau vont constituer les feuilles de l'arbre de Merkle. Les feuilles vont ensuite être fusionnées deux à deux pour former un parent commun avec un hachage différent, et ce même parent va fusionner avec son voisin de la même manière et réitérer le processus jusqu'à obtenir la racine de l'arbre contenant le hachage unique qui va permettre d'identifier la donnée dans son intégrité.		Une fois qu'une donnée aura été mise en ligne sur un réseau pair-à-pair, on va la découper en plusieurs blocs et calculer les hachages pour chacun des blocs. Ces hachages de premier niveau vont constituer les feuilles de l'arbre de Merkle. Les feuilles vont ensuite être fusionnées deux à deux pour former un parent commun avec un hachage différent, et ce même parent va fusionner avec son voisin de la même manière et réitérer le processus jusqu'à obtenir la racine de l'arbre contenant le hachage unique qui va permettre d'identifier la donnée dans son intégrité.

	La racine de l'arbre servant d'identifiant pour la donnée va être une manière fiable et rapide de rechercher la donnée sur le réseau. La racine va également servir à vérifier que la donnée téléchargée correspondant bien à la donnée désirée. Cela solutionne le problème initial puisque ~~malgré~~ ~~que~~ nous ne ~~puissions~~ vérifier l'identité des machines, nous sommes en mesure de déterminer si la donnée ~~est~~ reçue correspond bien à celle voulue.		La racine de l'arbre servant d'identifiant pour la donnée va être une manière fiable et rapide de rechercher la donnée sur le réseau. La racine va également servir à vérifier que la donnée téléchargée correspondant bien à la donnée désirée. Cela solutionne le problème initial puisque même si nous ne pouvons pas vérifier l'identité des machines, nous sommes en mesure de déterminer si la donnée reçue correspond bien à celle voulue.

	[[File:Merkle_Tree.png\|thumb\|right\|'''Figure 1 :''' Exemple d'arbre de Merkle]]		[[File:Merkle_Tree.png\|thumb\|right\|'''Figure 1 :''' Exemple d'arbre de Merkle]]

	L'image ci-contre ('''figure 1''') contient l'arbre de Merkle d'une donnée découpée en quatre blocs (Data Nodes). Juste au dessus des blocs, on retrouve les feuilles de l'arbre (Merkle leaves) contenant les hachages des blocs. Encore au dessus, on va retrouver les nœuds intermédiaires (Merkle branches) qui correspondent à la fusion des deux hachages du niveau précédent. Enfin, tout en haut, on retrouve la racine de l'arbre (Merkle root) qui contient le hachage final servant à identifier la donnée.		L'image ci-contre ('''figure 1''') contient l'arbre de Merkle d'une donnée découpée en quatre blocs (Data Nodes). Juste au-dessus des blocs, on retrouve les feuilles de l'arbre (Merkle leaves) contenant les hachages des blocs. Encore au-dessus, on va retrouver les nœuds intermédiaires (Merkle branches) qui correspondent à la fusion des deux hachages du niveau précédent. Enfin, tout en haut, on retrouve la racine de l'arbre (Merkle root) qui contient le hachage final servant à identifier la donnée.

⚫	Dans la suite de ce document, nous allons présenter plus en détails les arbres de Merkle et expliquer leur fonctionnement ainsi que leurs domaines d'applications. Nous commencerons par introduire les fonctions de hachage et par décrire leur fonctionnement général ainsi que leurs avantages et désavantages. Ensuite, nous expliquerons le processus de construction d'un arbre de Merkle et tous les différents scénarios qui peuvent altérer la façon dont l'arbre va être construit. Nous enchaînerons ensuite sur la partie validation avec un exemple ~~concrèt~~. Enfin, nous parlerons de différentes implémentations des arbres de Merkle dans des infrastructures réelles telles que la sécurité des transactions des ~~crypto-monnaies~~.

		⚫	Dans la suite de ce document, nous allons présenter plus en détails les arbres de Merkle et expliquer leur fonctionnement ainsi que leurs domaines d'applications. Nous commencerons par introduire les fonctions de hachage et par décrire leur fonctionnement général ainsi que leurs avantages et désavantages. Ensuite, nous expliquerons le processus de construction d'un arbre de Merkle et tous les différents scénarios qui peuvent altérer la façon dont l'arbre va être construit. Nous enchaînerons ensuite sur la partie validation avec un exemple concret. Enfin, nous parlerons de différentes implémentations des arbres de Merkle dans des infrastructures réelles telles que la sécurité des transactions des cryptomonnaies.

	Commençons sans plus attendre par faire un point sur le hachage !		Commençons sans plus attendre par faire un point sur le hachage !
Line 133:		Line 132:
	Git est un logiciel de gestion de versions décentralisé qui est beaucoup utilisé aujourd'hui. Tous les fichiers sont enregistrés sur l'ordinateur de tous les utilisateurs, à tout moment. Les Merkle trees permettent d'assurer que tout changement soit cohérent sur les ordinateurs de tous les utilisateurs. En comparant simplement le hashages des fichiers ou dossiers entre 2 différents commits, on peut facilement et surtout rapidement savoir si celui-ci a été modifié ou non.		Git est un logiciel de gestion de versions décentralisé qui est beaucoup utilisé aujourd'hui. Tous les fichiers sont enregistrés sur l'ordinateur de tous les utilisateurs, à tout moment. Les Merkle trees permettent d'assurer que tout changement soit cohérent sur les ordinateurs de tous les utilisateurs. En comparant simplement le hashages des fichiers ou dossiers entre 2 différents commits, on peut facilement et surtout rapidement savoir si celui-ci a été modifié ou non.

	=== ~~Crypto-monnaie~~ ===		=== Cryptomonnaie ===

	La ~~crypto monnaie~~ a été très popularisé récemment, et continuer de s'étendre, notamment le bitcoin.		La cryptomonnaie a été très popularisé récemment, et continuer de s'étendre, notamment le bitcoin.
	Toutes les transactions de ~~crypto monnaie~~ sont stockées dans des blocks, aussi appelés blockchain.		Toutes les transactions de cryptomonnaie sont stockées dans des blocks, aussi appelés blockchain.
	La ~~crypto monnaie~~ utilise les Merkle Trees pour s'assurer la validation des transactions dans les blocks. En effet, les blocks contiennent un ID, qui est le header fields hashé (cf. image), et parmi ce header hashé, une partie contient la racine de du Merkle Tree. De ce fait, elle permet de s'assurer de l'unicité de l'enregistrement des transactions dans le block.		La cryptomonnaie utilise les Merkle Trees pour s'assurer la validation des transactions dans les blocks. En effet, les blocks contiennent un ID, qui est le header fields hashé (cf. image), et parmi ce header hashé, une partie contient la racine de du Merkle Tree. De ce fait, elle permet de s'assurer de l'unicité de l'enregistrement des transactions dans le block.

	=== Blockchain pruning ===		=== Blockchain pruning ===

	Pour continuer sur le sujet de ~~crypto~~, l'émondation ou l'élagage des blockchains est un sujet qui reste d'affût de nos jours. En effet, sachant que les blockchains grandissent de plus en plus actuellement, cela veut également dire que celles-ci prennent de plus en plus de place en terme de stockage. Par exemple, en Février 2021, la taille de la blockchain du Bitcoin est d'environ 380Go. De ce fait, l'élagage de la blockchain consiste à épurer l'arbre, en supprimant les informations de la blockchain non critiques de l'espace de stockage. Les noeuds pleins gardent une copie de tous ce qui est stockés dans la blockchain, notamment des informations qui ne sont plus forcément utiles. Sachant que l'objectif d'un Merkle Tree est de synthétiser et de relier de grandes quantités d'informations. Chaque noeud contient l'information de ses fils, et donc la proposition est d'élaguer les informations qui ne sont plus utiles commes les transactions utilisées, ne laissant que les branches contenant les hashages pour vérifier les autres transactions.		Pour continuer sur le sujet des cryptomonnaies, l'émondation ou l'élagage des blockchains est un sujet qui reste d'affût de nos jours. En effet, sachant que les blockchains grandissent de plus en plus actuellement, cela veut également dire que celles-ci prennent de plus en plus de place en terme de stockage. Par exemple, en Février 2021, la taille de la blockchain du Bitcoin est d'environ 380Go. De ce fait, l'élagage de la blockchain consiste à épurer l'arbre, en supprimant les informations de la blockchain non critiques de l'espace de stockage. Les noeuds pleins gardent une copie de tous ce qui est stockés dans la blockchain, notamment des informations qui ne sont plus forcément utiles. Sachant que l'objectif d'un Merkle Tree est de synthétiser et de relier de grandes quantités d'informations. Chaque noeud contient l'information de ses fils, et donc la proposition est d'élaguer les informations qui ne sont plus utiles commes les transactions utilisées, ne laissant que les branches contenant les hashages pour vérifier les autres transactions.

	=== Base de données (AWS Dynamo DB) ===		=== Base de données (AWS Dynamo DB) ===

Corentin.Humbert at 09:53, 13 December 2021

2021-12-13T09:53:58Z

← Older revision		Revision as of 09:53, 13 December 2021
Line 23:		Line 23:
	=== Principe ===		=== Principe ===

			Imaginons que nous voulions télécharger un fichier dans un réseau pair-à-pair, comme on ne peut pas pas vérifier l'identité des machines sur le réseau, il est fort probable que certaines d'entre elles tentent d'envoyer des fichiers malveillants. Il faudrait donc mettre en place un méchanisme permettant d'identifier ces fichiers non désirés. Les arbres de Merkle sont une solution à ce problème. Un arbre de Merkle est un arbre binaire qui va permettre d'identifier de manière unique et sûre une ressource sur un réseau.
⚫	[[File:Merkle_Tree.png\|thumb\|right\|'''Figure 1 :''' Exemple d'arbre de Merkle]]

			Une fois qu'une donnée aura été mise en ligne sur un réseau pair-à-pair, on va la découper en plusieurs blocs et calculer les hachages pour chacun des blocs. Ces hachages de premier niveau vont constituer les feuilles de l'arbre de Merkle. Les feuilles vont ensuite être fusionnées deux à deux pour former un parent commun avec un hachage différent, et ce même parent va fusionner avec son voisin de la même manière et réitérer le processus jusqu'à obtenir la racine de l'arbre contenant le hachage unique qui va permettre d'identifier la donnée dans son intégrité.
	Les arbres de Merkle sont des [https://fr.wikipedia.org/wiki/Arbre_binaire arbres binaires] utilisés pour effectuer de la validation de données. Pour ce faire, chaque feuille de l'arbre va contenir le hachage correspondant à une partie de la donnée à valider. Chaque nœud de l'arbre va également contenir un hachage. Ce hachage est obtenu en concaténant le hachage des deux enfants et en passant le résultat dans une fonction pour créer un tout nouveau hachage. Il se construit alors une dépendance générale où la valeur de chaque nœud dépend des valeurs de ses nœuds enfants.

			La racine de l'arbre servant d'identifiant pour la donnée va être une manière fiable et rapide de rechercher la donnée sur le réseau. La racine va également servir à vérifier que la donnée téléchargée correspondant bien à la donnée désirée. Cela solutionne le problème initial puisque malgré que nous ne puissions vérifier l'identité des machines, nous sommes en mesure de déterminer si la donnée est reçue correspond bien à celle voulue.
⚫	L'image ci-~~dessous~~ ~~contient~~ un arbre de Merkle ~~servant à valider~~ une donnée découpée en quatre blocs (Data Nodes). ~~Les~~ feuilles de l'~~abre~~ (Merkle leaves) ~~vont~~ ~~contenir~~ le ~~hachage~~ ~~correspondant~~ ~~pour~~ ~~chaque~~ ~~bloc.~~ ~~Les~~ nœuds intermédiaires (Merkle branches) ~~vont~~ ~~contenir~~ ~~le hachage issu de~~ la ~~concaténation~~ des hachages de ~~leurs~~ ~~deux enfants~~. Enfin, la racine de l'arbre (Merkle root) va ~~contenir~~ le hachage final servant à identifier ~~l'arbre~~ ~~de Merkle~~.

		⚫	[[File:Merkle_Tree.png\|thumb\|right\|'''Figure 1 :''' Exemple d'arbre de Merkle]]

		⚫	L'image ci-contre ('''figure 1''') contient l'arbre de Merkle d'une donnée découpée en quatre blocs (Data Nodes). Juste au dessus des blocs, on retrouve les feuilles de l'arbre (Merkle leaves) contenant les hachages des blocs. Encore au dessus, on va retrouver les nœuds intermédiaires (Merkle branches) qui correspondent à la fusion des deux hachages du niveau précédent. Enfin, tout en haut, on retrouve la racine de l'arbre (Merkle root) qui contient le hachage final servant à identifier la donnée.

			Dans la suite de ce document, nous allons présenter plus en détails les arbres de Merkle et expliquer leur fonctionnement ainsi que leurs domaines d'applications. Nous commencerons par introduire les fonctions de hachage et par décrire leur fonctionnement général ainsi que leurs avantages et désavantages. Ensuite, nous expliquerons le processus de construction d'un arbre de Merkle et tous les différents scénarios qui peuvent altérer la façon dont l'arbre va être construit. Nous enchaînerons ensuite sur la partie validation avec un exemple concrèt. Enfin, nous parlerons de différentes implémentations des arbres de Merkle dans des infrastructures réelles telles que la sécurité des transactions des crypto-monnaies.


			Commençons sans plus attendre par faire un point sur le hachage !

Corentin.Humbert at 09:32, 13 December 2021

2021-12-13T09:32:55Z

← Older revision		Revision as of 09:32, 13 December 2021
Line 9:		Line 9:
	== Résumé ==		== Résumé ==

	Les arbres de Merkle sont des arbres binaires utilisés pour effectuer de la validation de données. Pour ce faire, chaque feuille de l'arbre va contenir le hachage correspondant à une partie de la donnée à valider. Chaque nœud de l'arbre va également contenir un hachage. Ce hachage est obtenu en concaténant le hachage des deux enfants et en passant le résultat dans une fonction pour créer un tout nouveau hachage. Il se construit alors une dépendance générale où la valeur de chaque nœud dépend des valeurs de ses nœuds enfants. Chaque arbre est unique et une donnée donnera toujours le même arbre. On retrouvera typiquement les arbres de Merkle lorsqu'on voudra faire du téléchargement de fichiers sur un réseau pair à pair. Comme on ne peut pas vérifier l'identité des machines participant à l'envoi de fichier, il est indispensable de mettre en place une structure de vérification comme les arbres de Merkle pour s'assurer que les données reçues correspondent bien à celles désirées.		Les arbres de Merkle sont des [https://fr.wikipedia.org/wiki/Arbre_binaire arbres binaires] utilisés pour effectuer de la validation de données. Pour ce faire, chaque feuille de l'arbre va contenir le hachage correspondant à une partie de la donnée à valider. Chaque nœud de l'arbre va également contenir un hachage. Ce hachage est obtenu en concaténant le hachage des deux enfants et en passant le résultat dans une fonction pour créer un tout nouveau hachage. Il se construit alors une dépendance générale où la valeur de chaque nœud dépend des valeurs de ses nœuds enfants. Chaque arbre est unique et une donnée donnera toujours le même arbre. On retrouvera typiquement les arbres de Merkle lorsqu'on voudra faire du téléchargement de fichiers sur un réseau [https://fr.wikipedia.org/wiki/Pair-%C3%A0-pair pair-à-pair]. Comme on ne peut pas vérifier l'identité des machines participant à l'envoi de fichier, il est indispensable de mettre en place une structure de vérification comme les arbres de Merkle pour s'assurer que les données reçues correspondent bien à celles désirées.

	'''Mots-clé :''' arbres de Merkle, arbres binaires, hachage, structure de données, validation, pair à pair		'''Mots-clé :''' arbres de Merkle, arbres binaires, hachage, structure de données, validation, pair à pair
Line 15:		Line 15:
	== Abstract ==		== Abstract ==

	Merkle trees are binary trees used in data validation. A tree consists of nodes and leaves. the leaves contain the hash corresponding to a part of the data we want to validate. The nodes contain a hash obtained by concatenating the hashes of the two child nodes and passing the concatenated string through a hashing function. This overall process creates a dependance between the nodes where each node's hash depends on the hash values of the underlying nodes. Each Merkle tree is unique and specific data will always give the same tree. A common use for Merkle trees is the download of files in peer to peer networks. As it is impossible to verify the identity of machines in the network, it is necessary to use validation structures such as Merkle trees to ensure that the received data is the desired one.		Merkle trees are [https://en.wikipedia.org/wiki/Binary_tree binary trees] used in data validation. A tree consists of nodes and leaves. the leaves contain the cryptographic hash corresponding to a part of the data we want to validate. The nodes contain a hash obtained by concatenating the hashes of the two child nodes and passing the concatenated string through a hashing function. This overall process creates a dependance between the nodes where each node's hash depends on the hash values of the underlying nodes. Each Merkle tree is unique and specific data will always give the same tree. A common use for Merkle trees is the download of files in [https://en.wikipedia.org/wiki/Peer-to-peer peer-to-peer] networks. As it is impossible to verify the identity of machines in the network, it is necessary to use validation structures such as Merkle trees to ensure that the received data is the desired one.

	Merkle Trees are binary trees in which every node is labelled with a cryptographic hash.

	'''Keywords:''' Merkle trees, binary trees, hash, data structure, validation, peer to peer		'''Keywords:''' Merkle trees, binary trees, hash, data structure, validation, peer to peer
Line 27:		Line 25:
	[[File:Merkle_Tree.png\|thumb\|right\|'''Figure 1 :''' Exemple d'arbre de Merkle]]		[[File:Merkle_Tree.png\|thumb\|right\|'''Figure 1 :''' Exemple d'arbre de Merkle]]

	Les arbres de Merkle sont des arbres binaires utilisés pour effectuer de la validation de données. Pour ce faire, chaque feuille de l'arbre va contenir le hachage correspondant à une partie de la donnée à valider. Chaque nœud de l'arbre va également contenir un hachage. Ce hachage est obtenu en concaténant le hachage des deux enfants et en passant le résultat dans une fonction pour créer un tout nouveau hachage. Il se construit alors une dépendance générale où la valeur de chaque nœud dépend des valeurs de ses nœuds enfants.		Les arbres de Merkle sont des [https://fr.wikipedia.org/wiki/Arbre_binaire arbres binaires] utilisés pour effectuer de la validation de données. Pour ce faire, chaque feuille de l'arbre va contenir le hachage correspondant à une partie de la donnée à valider. Chaque nœud de l'arbre va également contenir un hachage. Ce hachage est obtenu en concaténant le hachage des deux enfants et en passant le résultat dans une fonction pour créer un tout nouveau hachage. Il se construit alors une dépendance générale où la valeur de chaque nœud dépend des valeurs de ses nœuds enfants.

	L'image ci-dessous contient un arbre de Merkle servant à valider une donnée découpée en quatre blocs (Data Nodes). Les feuilles de l'abre (Merkle leaves) vont contenir le hachage correspondant pour chaque bloc. Les nœuds intermédiaires (Merkle branches) vont contenir le hachage issu de la concaténation des hachages de leurs deux enfants. Enfin, la racine de l'arbre (Merkle root) va contenir le hachage final servant à identifier l'arbre de Merkle.		L'image ci-dessous contient un arbre de Merkle servant à valider une donnée découpée en quatre blocs (Data Nodes). Les feuilles de l'abre (Merkle leaves) vont contenir le hachage correspondant pour chaque bloc. Les nœuds intermédiaires (Merkle branches) vont contenir le hachage issu de la concaténation des hachages de leurs deux enfants. Enfin, la racine de l'arbre (Merkle root) va contenir le hachage final servant à identifier l'arbre de Merkle.

Corentin.Humbert at 09:28, 13 December 2021

2021-12-13T09:28:07Z

← Older revision		Revision as of 09:28, 13 December 2021
Line 11:		Line 11:
	Les arbres de Merkle sont des arbres binaires utilisés pour effectuer de la validation de données. Pour ce faire, chaque feuille de l'arbre va contenir le hachage correspondant à une partie de la donnée à valider. Chaque nœud de l'arbre va également contenir un hachage. Ce hachage est obtenu en concaténant le hachage des deux enfants et en passant le résultat dans une fonction pour créer un tout nouveau hachage. Il se construit alors une dépendance générale où la valeur de chaque nœud dépend des valeurs de ses nœuds enfants. Chaque arbre est unique et une donnée donnera toujours le même arbre. On retrouvera typiquement les arbres de Merkle lorsqu'on voudra faire du téléchargement de fichiers sur un réseau pair à pair. Comme on ne peut pas vérifier l'identité des machines participant à l'envoi de fichier, il est indispensable de mettre en place une structure de vérification comme les arbres de Merkle pour s'assurer que les données reçues correspondent bien à celles désirées.		Les arbres de Merkle sont des arbres binaires utilisés pour effectuer de la validation de données. Pour ce faire, chaque feuille de l'arbre va contenir le hachage correspondant à une partie de la donnée à valider. Chaque nœud de l'arbre va également contenir un hachage. Ce hachage est obtenu en concaténant le hachage des deux enfants et en passant le résultat dans une fonction pour créer un tout nouveau hachage. Il se construit alors une dépendance générale où la valeur de chaque nœud dépend des valeurs de ses nœuds enfants. Chaque arbre est unique et une donnée donnera toujours le même arbre. On retrouvera typiquement les arbres de Merkle lorsqu'on voudra faire du téléchargement de fichiers sur un réseau pair à pair. Comme on ne peut pas vérifier l'identité des machines participant à l'envoi de fichier, il est indispensable de mettre en place une structure de vérification comme les arbres de Merkle pour s'assurer que les données reçues correspondent bien à celles désirées.

	'''Mots-clé''': ~~arbre~~ de Merkle, arbres binaires, hachage, structure de données, validation, pair à pair		'''Mots-clé :''' arbres de Merkle, arbres binaires, hachage, structure de données, validation, pair à pair

	== Abstract ==		== Abstract ==
Line 19:		Line 19:
	Merkle Trees are binary trees in which every node is labelled with a cryptographic hash.		Merkle Trees are binary trees in which every node is labelled with a cryptographic hash.

	'''Keywords''': Merkle trees, binary trees, hash, data structure, validation, peer to peer		'''Keywords:''' Merkle trees, binary trees, hash, data structure, validation, peer to peer

	== Fonctionnement ==		== Fonctionnement ==

← Older revision		Revision as of 10:20, 13 December 2021
Line 68:		Line 68:
	=== Création d'un arbre ===		=== Création d'un arbre ===

	Pour réaliser un arbre de Merkle pour une donnée particulière, on va commencer par découper la donnée en entrée en un certain nombres de blocs. Le nombre de blocs va varier en fonction de la taille de la donnée. Une fois la donnée scindée en blocs, on va calculer pour chaque bloc son hachage et l'ajouter à l'arbre de Merkle. Deux blocs consécutifs vont être reliés par un nouveau nœud parent dont le hachage sera calculé en effectuant la concaténation des deux hachages enfant et en hachant une dernière fois ce résultat. On va réitérer cette opération pour chaque bloc, jusqu'à ce que tous les blocs de données hachés appartiennent à l'~~abre~~ et qu'une racine soit calculée. Une fois la racine obtenue, la construction de l'arbre est terminée.		Pour réaliser un arbre de Merkle pour une donnée particulière, on va commencer par découper la donnée en entrée en un certain nombres de blocs. Le nombre de blocs va varier en fonction de la taille de la donnée. Une fois la donnée scindée en blocs, on va calculer pour chaque bloc son hachage et l'ajouter à l'arbre de Merkle. Deux blocs consécutifs vont être reliés par un nouveau nœud parent dont le hachage sera calculé en effectuant la concaténation des deux hachages enfant et en hachant une dernière fois ce résultat. On va réitérer cette opération pour chaque bloc, jusqu'à ce que tous les blocs de données hachés appartiennent à l'arbre et qu'une racine soit calculée. Une fois la racine obtenue, la construction de l'arbre est terminée.

	Pour ce qui est de l'algorithme de hachage utilisé, celui-ci va varier en fonction des implémentations. Généralement, on utilisera des fonctions de hachage robustes tel que le SHA2 ou SHA3.		Pour ce qui est de l'algorithme de hachage utilisé, celui-ci va varier en fonction des implémentations. Généralement, on utilisera des fonctions de hachage robustes tel que le SHA2 ou SHA3.
Line 74:		Line 74:
	=== Arbre de Merkle déséquilibré ===		=== Arbre de Merkle déséquilibré ===

	Nous avons parlé précédemment de comment les arbres de Merkel étaient construits mais nous avons oublié d'évoquer un point. L'algorithme décrit marche très bien lorsque le nombre de blocs en entrée est une puissance de 2. Par exemple, avec quatre blocs, on aura quatre feuilles (nœud de hauteur 2), deux nœuds de hauteur 1 et un nœud de hauteur 0 (la racine). Mais que se passe-t-il si au lieu d'avoir quatre blocs, nous en avions six ? Nous aurions alors six feuilles, trois nœuds de hauteur 1 et...		Nous avons parlé précédemment de comment les arbres de Merkel étaient construits, mais nous avons oublié d'évoquer un point. L'algorithme décrit marche très bien lorsque le nombre de blocs en entrée est une puissance de 2. Par exemple, avec quatre blocs, on aura quatre feuilles (nœud de hauteur 2), deux nœuds de hauteur 1 et un nœud de hauteur 0 (la racine). Mais que se passe-t-il si au lieu d'avoir quatre blocs, nous en avions six ? Nous aurions alors six feuilles, trois nœuds de hauteur 1 et...
	Comment faire? Chaque nœud ne peut avoir que deux enfants et nous nous trouvons avec un nombre impair de nœud, devons-nous changer la structure de l'arbre et autoriser des nœuds à avoir trois enfants ?		Comment faire ? Chaque nœud ne peut avoir que deux enfants et nous nous trouvons avec un nombre impair de nœud, devons-nous changer la structure de l'arbre et autoriser des nœuds à avoir trois enfants ?

	Ils existent différentes approches permettant de pallier ce problème.		Ils existent différentes approches permettant de pallier ce problème.
Line 83:		Line 83:
	[[File:Merkle_Tree_Duplicating_Node.png\|thumb\|right\|'''Figure 3 :''' Équilibrage d'un arbre de Merkle en utilisant la technique de duplication (source: Medium)]]		[[File:Merkle_Tree_Duplicating_Node.png\|thumb\|right\|'''Figure 3 :''' Équilibrage d'un arbre de Merkle en utilisant la technique de duplication (source: Medium)]]

	Pour cette première approche, on va dupliquer les nœuds qui se retrouvent tout seul. Sur la '''figure 3''', on peut observer que l'arbre de Merkle contient cinq feuilles. Cinq étant un chiffre impair, notre arbre de Merkle se retrouve déséquilibré. On va donc choisir de dupliquer la feuille se retrouvant toute seule pour ré-équilibrer l'arbre. Ici, il va s'agir de la feuille contenant le hachage du cinquième bloc de donnée : Hash5. La feuille va donc être copiée de manière à faire apparaître une sixième feuille contenant également Hash5. Il n'y a plus de problème au niveau des feuilles de l'arbre puisqu'il y en a désormais une quantité paire. Cependant, nous allons rencontrer un problème au niveau supérieur. En effet, nos six feuilles vont se transformer en trois nœuds et on retombe encore une fois sur une quantité impaire. On va donc ré-itérer le procédé et dupliquer cette fois le troisième nœud contenant Hash55 (On remarque que ce hachage est obtenu en appliquant la fonction de hachage sur la concaténation de deux hachages identiques.). Cela nous permet de faire un quatrième nœud, le nombre de nœuds du niveau étant paire, on peut passer au niveau suivant. Pour l'avant dernier niveau, on va avoir deux fois moins de nœuds que le niveau précédent, ce qui nous ramène à deux nœuds. Comme la quantité de nœuds est paire, pas besoin de dupliquer de nœud. L'algorithme de duplication prend fin ici puisque le prochain niveau va simplement contenir la racine.		Pour cette première approche, on va dupliquer les nœuds qui se retrouvent tout seul. Sur la '''figure 3''', on peut observer que l'arbre de Merkle contient cinq feuilles. Cinq étant un chiffre impair, notre arbre de Merkle se retrouve déséquilibré. On va donc choisir de dupliquer la feuille se retrouvant toute seule pour ré-équilibrer l'arbre. Ici, il va s'agir de la feuille contenant le hachage du cinquième bloc de donnée : Hash5. La feuille va donc être copiée de manière à faire apparaître une sixième feuille contenant également Hash5. Il n'y a plus de problème au niveau des feuilles de l'arbre puisqu'il y en a désormais une quantité paire. Cependant, nous allons rencontrer un problème au niveau supérieur. En effet, nos six feuilles vont se transformer en trois nœuds et on retombe encore une fois sur une quantité impaire. On va donc ré-itérer le procédé et dupliquer cette fois le troisième nœud contenant Hash55 (On remarque que ce hachage est obtenu en appliquant la fonction de hachage sur la concaténation de deux hachages identiques.). Cela nous permet de faire un quatrième nœud, le nombre de nœuds du niveau étant paire, on peut passer au niveau suivant. Pour l'avant-dernier niveau, on va avoir deux fois moins de nœuds que le niveau précédent, ce qui nous ramène à deux nœuds. Comme la quantité de nœuds est paire, pas besoin de dupliquer de nœud. L'algorithme de duplication prend fin ici puisque le prochain niveau va simplement contenir la racine.

	Notre arbre de Merkle est donc désormais équilibré et exploitable. On pourrait cependant se poser des questions sur la fiabilité de cette solution de duplication. En effet, celle-ci est assez simple à mettre en place, mais il introduit une faille de sécurité notable car certains nœuds ne contiendront en réalité qu'un seul hachage. (copié deux fois)		Notre arbre de Merkle est donc désormais équilibré et exploitable. On pourrait cependant se poser des questions sur la fiabilité de cette solution de duplication. En effet, celle-ci est assez simple à mettre en place, mais il introduit une faille de sécurité notable, car certains nœuds ne contiendront en réalité qu'un seul hachage. (copié deux fois)

	==== Création d'un arbre parfait (Monero) ====		==== Création d'un arbre parfait (Monero) ====
Line 91:		Line 91:
	[[File:Merkle_Tree_Perfect_Tree.png\|thumb\|right\|'''Figure 4 :''' Équilibrage d'un arbre de Merkle en utilisant la technique de création d'arbre parfait (source: Medium)]]		[[File:Merkle_Tree_Perfect_Tree.png\|thumb\|right\|'''Figure 4 :''' Équilibrage d'un arbre de Merkle en utilisant la technique de création d'arbre parfait (source: Medium)]]

	Cette seconde méthode va consister à transformer n'importe quel arbre déséquilibré en un arbre parfait dès la première itération. En d'autres termes, ~~quelque~~ soit le nombre de blocs de données en entrée, on aura un arbre équilibré dès le premier niveau de branches (juste au dessus des feuilles). La différence avec la précédente approche où l'on ~~duplicait~~ les nœuds impairs et les fusionnait avec eux-~~même~~ est notable puisqu'ici on ne va pas avoir à vérifier la parité du nombre de nœuds à chaque niveau mais seulement au tout début. L'idée va donc être de pré-calculer le nombre de transformations nécessaires sur les feuilles pour que l'on obtienne une quantité de nœuds au niveau suivant les feuilles qui soit une puissance de deux.		Cette seconde méthode va consister à transformer n'importe quel arbre déséquilibré en un arbre parfait dès la première itération. En d'autres termes, quel que soit le nombre de blocs de données en entrée, on aura un arbre équilibré dès le premier niveau de branches (juste au dessus des feuilles). La différence avec la précédente approche où l'on dupliquait les nœuds impairs et les fusionnait avec eux-mêmes est notable puisqu'ici, on ne va pas avoir à vérifier la parité du nombre de nœuds à chaque niveau, mais seulement au tout début. L'idée va donc être de pré-calculer le nombre de transformations nécessaires sur les feuilles pour que l'on obtienne une quantité de nœuds au niveau suivant les feuilles qui soit une puissance de deux.


Line 101:		Line 101:


	Pour nous aider à visualiser le fonctionnement de cette approche, nous allons travailler avec l'exemple de la '''figure 4'''. Au premier coup d'œil on remarque que l'arbre a une structure un peu bizarre; on a deux niveaux de feuilles. ~~Executons~~ l'algorithme sans attendre pour comprendre ce qu'il se passe :		Pour nous aider à visualiser le fonctionnement de cette approche, nous allons travailler avec l'exemple de la '''figure 4'''. Au premier coup d'œil on remarque que l'arbre a une structure un peu bizarre; on a deux niveaux de feuilles. Exécutons l'algorithme sans attendre pour comprendre ce qu'il se passe :
	* On dispose de cinq blocs de données (Data1 jusqu'à Data5). Si on cherche ''x'' tel que ''2^x > 5'', on trouve ''2^3 = 8 > 4'', soit ''x = 3''.		* On dispose de cinq blocs de données (Data1 jusqu'à Data5). Si on cherche ''x'' tel que ''2^x > 5'', on trouve ''2^3 = 8 > 4'', soit ''x = 3''.
	* On soustrait désormais le nombre de blocs à la puissance trouvée, soit ''8 - 5 = 3'', ce qui nous donne l'indice de départ pour la première itération. On ~~commencant~~ à compter les indices à partir de zéro, l'indice 3 va correspondre à Data4. Tous les blocs qui suivent Data4, lui y compris vont participer à la première itération. Tandis que tous ceux qui le ~~précède~~ vont attendre l'itération d'après.		* On soustrait désormais le nombre de blocs à la puissance trouvée, soit ''8 - 5 = 3'', ce qui nous donne l'indice de départ pour la première itération. On commençant à compter les indices à partir de zéro, l'indice 3 va correspondre à Data4. Tous les blocs qui suivent Data4, lui y compris vont participer à la première itération. Tandis que tous ceux qui le précèdent vont attendre l'itération d'après.
	* On lance la première itération qui ne concerne ici que Data4 et Data5. On va donc naturellement calculer leur hachage respectif, ce qui nous donne Hash4 et Hash5, que l'on va concaténer et hacher de manière à obtenir Hash45, qui lui, appartient à la seconde itération. La première itération est désormais terminée puisque Data5 était le dernier nœud.		* On lance la première itération qui ne concerne ici que Data4 et Data5. On va donc naturellement calculer leur hachage respectif, ce qui nous donne Hash4 et Hash5, que l'on va concaténer et hacher de manière à obtenir Hash45, qui lui, appartient à la seconde itération. La première itération est désormais terminée puisque Data5 était le dernier nœud.
	* On commence la seconde itération, avec cette fois non pas cinq nœuds mais quatre: Hash1, Hash2, Hash3 et le hachage Hash45 obtenu lors de l'itération précédente. Comme le nombre de nœuds est une puissance de deux, rien de plus simple, on va concaténer Hash1 et Hash2 pour obtenir Hash12, et Hash3 et Hash45 pour obtenir Hash345. La ~~seoncde~~ itération se termine. La dernière itération va concaténer Hash12 et Hash345, ce qui va nous permettre d'obtenir Hash12345.		* On commence la seconde itération, avec cette fois non pas cinq nœuds, mais quatre : Hash1, Hash2, Hash3 et le hachage Hash45 obtenu lors de l'itération précédente. Comme le nombre de nœuds est une puissance de deux, rien de plus simple, on va concaténer Hash1 et Hash2 pour obtenir Hash12, et Hash3 et Hash45 pour obtenir Hash345. La seconde itération se termine. La dernière itération va concaténer Hash12 et Hash345, ce qui va nous permettre d'obtenir Hash12345.

	=== Validation de données ===		=== Validation de données ===

← Older revision		Revision as of 10:08, 13 December 2021
Line 29:		Line 29:
	La racine de l'arbre servant d'identifiant pour la donnée va être une manière fiable et rapide de rechercher la donnée sur le réseau. La racine va également servir à vérifier que la donnée téléchargée correspondant bien à la donnée désirée. Cela solutionne le problème initial puisque même si nous ne pouvons pas vérifier l'identité des machines, nous sommes en mesure de déterminer si la donnée reçue correspond bien à celle voulue.		La racine de l'arbre servant d'identifiant pour la donnée va être une manière fiable et rapide de rechercher la donnée sur le réseau. La racine va également servir à vérifier que la donnée téléchargée correspondant bien à la donnée désirée. Cela solutionne le problème initial puisque même si nous ne pouvons pas vérifier l'identité des machines, nous sommes en mesure de déterminer si la donnée reçue correspond bien à celle voulue.

	[[File:Merkle_Tree.png\|thumb\|right\|'''Figure 1 :''' ~~Exemple~~ d'arbre de Merkle]]		[[File:Merkle_Tree.png\|thumb\|right\|'''Figure 1 :''' Diagramme représentant la structure générique d'un arbre de Merkle]]

	L'image ci-contre ('''figure 1''') contient l'arbre de Merkle d'une donnée découpée en quatre blocs (Data Nodes). Juste au-dessus des blocs, on retrouve les feuilles de l'arbre (Merkle leaves) contenant les hachages des blocs. Encore au-dessus, on va retrouver les nœuds intermédiaires (Merkle branches) qui correspondent à la fusion des deux hachages du niveau précédent. Enfin, tout en haut, on retrouve la racine de l'arbre (Merkle root) qui contient le hachage final servant à identifier la donnée.		L'image ci-contre ('''figure 1''') contient l'arbre de Merkle d'une donnée découpée en quatre blocs (Data Nodes). Juste au-dessus des blocs, on retrouve les feuilles de l'arbre (Merkle leaves) contenant les hachages des blocs. Encore au-dessus, on va retrouver les nœuds intermédiaires (Merkle branches) qui correspondent à la fusion des deux hachages du niveau précédent. Enfin, tout en haut, on retrouve la racine de l'arbre (Merkle root) qui contient le hachage final servant à identifier la donnée.
Line 68:		Line 68:
	=== Création d'un arbre ===		=== Création d'un arbre ===

	Pour réaliser un arbre de Merkle pour une donnée particulière, on va commencer par découper la donnée en entrée en un certain nombres de blocs. Le nombre de blocs va varier en fonction de la taille de la donnée. Une fois la donnée scindée en blocs, on va calculer pour chaque bloc son hachage et l'ajouter à l'arbre de Merkle. Deux blocs consécutifs vont être reliés par un nouveau nœud parent dont le hachage sera calculé en effectuant la concaténation des deux hachages enfant et en hachant une dernière fois ce résultat. On va réitérer cette opération pour chaque bloc, jusqu'à ce que tous les blocs de données hachés appartiennent à l'abre et qu'une racine soit calculée. Une fois la racine obtenue, la construction de l'~~abre~~ est terminée.		Pour réaliser un arbre de Merkle pour une donnée particulière, on va commencer par découper la donnée en entrée en un certain nombres de blocs. Le nombre de blocs va varier en fonction de la taille de la donnée. Une fois la donnée scindée en blocs, on va calculer pour chaque bloc son hachage et l'ajouter à l'arbre de Merkle. Deux blocs consécutifs vont être reliés par un nouveau nœud parent dont le hachage sera calculé en effectuant la concaténation des deux hachages enfant et en hachant une dernière fois ce résultat. On va réitérer cette opération pour chaque bloc, jusqu'à ce que tous les blocs de données hachés appartiennent à l'abre et qu'une racine soit calculée. Une fois la racine obtenue, la construction de l'arbre est terminée.

	Pour ce qui est de l'algorithme de hachage utilisé, celui-ci va varier en fonction des implémentations. Généralement, on utilisera des fonctions de hachage robustes tel que le SHA2 ou SHA3.		Pour ce qui est de l'algorithme de hachage utilisé, celui-ci va varier en fonction des implémentations. Généralement, on utilisera des fonctions de hachage robustes tel que le SHA2 ou SHA3.
Line 74:		Line 74:
	=== Arbre de Merkle déséquilibré ===		=== Arbre de Merkle déséquilibré ===

	Nous avons parlé précédemment de comment les ~~abres~~ de Merkel étaient construits mais nous avons oublié d'évoquer un point. L'algorithme décrit marche très bien lorsque le nombre de blocs en entrée est une puissance de 2. Par exemple, avec quatre blocs, on aura quatre feuilles (nœud de hauteur 2), deux nœuds de hauteur 1 et un nœud de hauteur 0 (la racine). Mais que se passe-t-il si au lieu d'avoir quatre blocs, nous en avions six ? Nous aurions alors six feuilles, trois nœuds de hauteur 1 et...		Nous avons parlé précédemment de comment les arbres de Merkel étaient construits mais nous avons oublié d'évoquer un point. L'algorithme décrit marche très bien lorsque le nombre de blocs en entrée est une puissance de 2. Par exemple, avec quatre blocs, on aura quatre feuilles (nœud de hauteur 2), deux nœuds de hauteur 1 et un nœud de hauteur 0 (la racine). Mais que se passe-t-il si au lieu d'avoir quatre blocs, nous en avions six ? Nous aurions alors six feuilles, trois nœuds de hauteur 1 et...
	Comment faire? Chaque nœud ne peut avoir que deux enfants et nous nous trouvons avec un nombre impair de nœud, devons-nous changer la structure de l'~~abre~~ et autoriser des nœuds à avoir trois enfants ?		Comment faire? Chaque nœud ne peut avoir que deux enfants et nous nous trouvons avec un nombre impair de nœud, devons-nous changer la structure de l'arbre et autoriser des nœuds à avoir trois enfants ?

	Ils existent différentes approches permettant de pallier ce problème.		Ils existent différentes approches permettant de pallier ce problème.
Line 81:		Line 81:
	==== Duplication du nœud impair (Bitcoin) ====		==== Duplication du nœud impair (Bitcoin) ====

	[[File:Merkle_Tree_Duplicating_Node.png\|thumb\|right\|'''Figure 3 :''' Équilibrage d'un ~~abre~~ de Merkle en utilisant la technique de duplication (source: Medium)]]		[[File:Merkle_Tree_Duplicating_Node.png\|thumb\|right\|'''Figure 3 :''' Équilibrage d'un arbre de Merkle en utilisant la technique de duplication (source: Medium)]]

	Pour cette première approche, on va dupliquer les nœuds qui se retrouvent tout seul. Sur la '''figure 3''', on peut observer que l'arbre de Merkle contient cinq feuilles. Cinq étant un chiffre impair, notre arbre de Merkle se retrouve déséquilibré. On va donc choisir de dupliquer la feuille se retrouvant toute seule pour ré-équilibrer l'arbre. Ici, il va s'agir de la feuille contenant le hachage du cinquième bloc de donnée : Hash5. La feuille va donc être copiée de manière à faire apparaître une sixième feuille contenant également Hash5. Il n'y a plus de problème au niveau des feuilles de l'arbre puisqu'il y en a désormais une quantité paire. Cependant, nous allons rencontrer un problème au niveau supérieur. En effet, nos six feuilles vont se transformer en trois nœuds et on retombe encore une fois sur une quantité impaire. On va donc ré-itérer le procédé et dupliquer cette fois le troisième nœud contenant Hash55 (On remarque que ce hachage est obtenu en appliquant la fonction de hachage sur la concaténation de deux hachages identiques.). Cela nous permet de faire un quatrième nœud, le nombre de nœuds du niveau étant paire, on peut passer au niveau suivant. Pour l'avant dernier niveau, on va avoir deux fois moins de nœuds que le niveau précédent, ce qui nous ramène à deux nœuds. Comme la quantité de nœuds est paire, pas besoin de dupliquer de nœud. L'algorithme de duplication prend fin ici puisque le prochain niveau va simplement contenir la racine.		Pour cette première approche, on va dupliquer les nœuds qui se retrouvent tout seul. Sur la '''figure 3''', on peut observer que l'arbre de Merkle contient cinq feuilles. Cinq étant un chiffre impair, notre arbre de Merkle se retrouve déséquilibré. On va donc choisir de dupliquer la feuille se retrouvant toute seule pour ré-équilibrer l'arbre. Ici, il va s'agir de la feuille contenant le hachage du cinquième bloc de donnée : Hash5. La feuille va donc être copiée de manière à faire apparaître une sixième feuille contenant également Hash5. Il n'y a plus de problème au niveau des feuilles de l'arbre puisqu'il y en a désormais une quantité paire. Cependant, nous allons rencontrer un problème au niveau supérieur. En effet, nos six feuilles vont se transformer en trois nœuds et on retombe encore une fois sur une quantité impaire. On va donc ré-itérer le procédé et dupliquer cette fois le troisième nœud contenant Hash55 (On remarque que ce hachage est obtenu en appliquant la fonction de hachage sur la concaténation de deux hachages identiques.). Cela nous permet de faire un quatrième nœud, le nombre de nœuds du niveau étant paire, on peut passer au niveau suivant. Pour l'avant dernier niveau, on va avoir deux fois moins de nœuds que le niveau précédent, ce qui nous ramène à deux nœuds. Comme la quantité de nœuds est paire, pas besoin de dupliquer de nœud. L'algorithme de duplication prend fin ici puisque le prochain niveau va simplement contenir la racine.
Line 89:		Line 89:
	==== Création d'un arbre parfait (Monero) ====		==== Création d'un arbre parfait (Monero) ====

	[[File:Merkle_Tree_Perfect_Tree.png\|thumb\|right\|'''Figure 4 :''' Équilibrage d'un ~~abre~~ de Merkle en utilisant la technique de création d'arbre parfait (source: Medium)]]		[[File:Merkle_Tree_Perfect_Tree.png\|thumb\|right\|'''Figure 4 :''' Équilibrage d'un arbre de Merkle en utilisant la technique de création d'arbre parfait (source: Medium)]]

	Cette seconde méthode va consister à transformer n'importe quel arbre déséquilibré en un arbre parfait dès la première itération. En d'autres termes, quelque soit le nombre de blocs de données en entrée, on aura un arbre équilibré dès le premier niveau de branches (juste au dessus des feuilles). La différence avec la précédente approche où l'on duplicait les nœuds impairs et les fusionnait avec eux-même est notable puisqu'ici on ne va pas avoir à vérifier la parité du nombre de nœuds à chaque niveau mais seulement au tout début. L'idée va donc être de pré-calculer le nombre de transformations nécessaires sur les feuilles pour que l'on obtienne une quantité de nœuds au niveau suivant les feuilles qui soit une puissance de deux.		Cette seconde méthode va consister à transformer n'importe quel arbre déséquilibré en un arbre parfait dès la première itération. En d'autres termes, quelque soit le nombre de blocs de données en entrée, on aura un arbre équilibré dès le premier niveau de branches (juste au dessus des feuilles). La différence avec la précédente approche où l'on duplicait les nœuds impairs et les fusionnait avec eux-même est notable puisqu'ici on ne va pas avoir à vérifier la parité du nombre de nœuds à chaque niveau mais seulement au tout début. L'idée va donc être de pré-calculer le nombre de transformations nécessaires sur les feuilles pour que l'on obtienne une quantité de nœuds au niveau suivant les feuilles qui soit une puissance de deux.
Line 101:		Line 101:


	Pour nous aider à visualiser le fonctionnement de cette approche, nous allons travailler avec l'exemple de la '''figure 4'''. Au premier coup d'œil on remarque que l'~~abre~~ a une structure un peu bizarre; on a deux niveaux de feuilles. Executons l'algorithme sans attendre pour comprendre ce qu'il se passe :		Pour nous aider à visualiser le fonctionnement de cette approche, nous allons travailler avec l'exemple de la '''figure 4'''. Au premier coup d'œil on remarque que l'arbre a une structure un peu bizarre; on a deux niveaux de feuilles. Executons l'algorithme sans attendre pour comprendre ce qu'il se passe :
	* On dispose de cinq blocs de données (Data1 jusqu'à Data5). Si on cherche ''x'' tel que ''2^x > 5'', on trouve ''2^3 = 8 > 4'', soit ''x = 3''.		* On dispose de cinq blocs de données (Data1 jusqu'à Data5). Si on cherche ''x'' tel que ''2^x > 5'', on trouve ''2^3 = 8 > 4'', soit ''x = 3''.
	* On soustrait désormais le nombre de blocs à la puissance trouvée, soit ''8 - 5 = 3'', ce qui nous donne l'indice de départ pour la première itération. On commencant à compter les indices à partir de zéro, l'indice 3 va correspondre à Data4. Tous les blocs qui suivent Data4, lui y compris vont participer à la première itération. Tandis que tous ceux qui le précède vont attendre l'itération d'après.		* On soustrait désormais le nombre de blocs à la puissance trouvée, soit ''8 - 5 = 3'', ce qui nous donne l'indice de départ pour la première itération. On commencant à compter les indices à partir de zéro, l'indice 3 va correspondre à Data4. Tous les blocs qui suivent Data4, lui y compris vont participer à la première itération. Tandis que tous ceux qui le précède vont attendre l'itération d'après.
Line 113:		Line 113:
	Dans les parties précédentes, nous avons vu ce qu'étaient les arbres de Merkle, et comment procéder pour en construire un. Toutefois, nous n'avons pas encore vu comment les uiliser. Nous avons parlé brièvement du fait qu'ils servaient à faire de la validation de données mais nous n'avons pas encore détaillé exactement comment. C'est ce dont nous allons parler dans cette partie.		Dans les parties précédentes, nous avons vu ce qu'étaient les arbres de Merkle, et comment procéder pour en construire un. Toutefois, nous n'avons pas encore vu comment les uiliser. Nous avons parlé brièvement du fait qu'ils servaient à faire de la validation de données mais nous n'avons pas encore détaillé exactement comment. C'est ce dont nous allons parler dans cette partie.

	Imaginons que nous voulions télécharger un fichier assez conséquent depuis Internet. On veut utiliser un système pair à pair pour télécharger le fichier. On ne va donc pas se connecter à un serveur unique qui détient le fichier désiré mais à une multitude de machines dans un réseau qui vont participer au téléchargement. Le pair à pair a de nombreux avantages mais nous ne rentrerons pas en détail sur son fonctionnement dans ce document. L'un des problèmes majeurs des architectures pair à pair est la confiance que l'on accorde à chaque machine. En effet, contrairement à une architecture client-serveur classique où le serveur est une machine identifiée et à laquelle on fait généralement confiance, la modularité des systèmes pair à pair fait que nous soyions obligé de nous reposer sur des machines anonymes et potentiellement malicieuses. Il est impossible de vérifier si chaque machine est légitime ou si l'une d'entre elles tente de nous envoyer un fichier corrompu. C'est justement pour pallier ce problème que nous pouvons utiliser les ~~abres~~ de Merkle.		Imaginons que nous voulions télécharger un fichier assez conséquent depuis Internet. On veut utiliser un système pair à pair pour télécharger le fichier. On ne va donc pas se connecter à un serveur unique qui détient le fichier désiré mais à une multitude de machines dans un réseau qui vont participer au téléchargement. Le pair à pair a de nombreux avantages mais nous ne rentrerons pas en détail sur son fonctionnement dans ce document. L'un des problèmes majeurs des architectures pair à pair est la confiance que l'on accorde à chaque machine. En effet, contrairement à une architecture client-serveur classique où le serveur est une machine identifiée et à laquelle on fait généralement confiance, la modularité des systèmes pair à pair fait que nous soyions obligé de nous reposer sur des machines anonymes et potentiellement malicieuses. Il est impossible de vérifier si chaque machine est légitime ou si l'une d'entre elles tente de nous envoyer un fichier corrompu. C'est justement pour pallier ce problème que nous pouvons utiliser les arbres de Merkle.

	Reprenons notre problèmatique de téléchargement de fichier. Ici, le fichier que l'on veut obtenir va être transformé en un ~~abre~~ de Merkle. En d'autres termes, il va être divisé en un certain nombre de blocs que l'on va hacher un à un jusqu'à obtenir un hachage unique qui permet d'identifier l'intégralité du fichier (il s'agit de la racine de l'arbre). Nous avons donc un arbre plus ou moins massifs qui va représenter le fichier que nous voulons télécharger. Mais comment-va-t'on faire pour vérifier que le fichier que nous avons demandé est bien celui que nous avons reçu ?		Reprenons notre problèmatique de téléchargement de fichier. Ici, le fichier que l'on veut obtenir va être transformé en un arbre de Merkle. En d'autres termes, il va être divisé en un certain nombre de blocs que l'on va hacher un à un jusqu'à obtenir un hachage unique qui permet d'identifier l'intégralité du fichier (il s'agit de la racine de l'arbre). Nous avons donc un arbre plus ou moins massifs qui va représenter le fichier que nous voulons télécharger. Mais comment-va-t'on faire pour vérifier que le fichier que nous avons demandé est bien celui que nous avons reçu ?
	Tout repose sur le hachage racine. Si on part du principe que nous avons obtenu le hachage racine d'un tier auquel nous faisons confiance, nous allons pouvoir, par ce seul hachage, s'assurer que le fichier que nous obtenons soit bel et bien celui que nous voulions.		Tout repose sur le hachage racine. Si on part du principe que nous avons obtenu le hachage racine d'un tier auquel nous faisons confiance, nous allons pouvoir, par ce seul hachage, s'assurer que le fichier que nous obtenons soit bel et bien celui que nous voulions.