Le hash : quelques utilisations avec les crypto-monnaies

Le hash : quelques utilisations avec les crypto-monnaies

Je sais ce que vous pensez en voyant le titre, mais même s'il m'arrivera de parler de drogues dans le futur (à l'occasion de l'histoire de Silk Road), il s'agit contrairement aux apparences d'un concept cryptographique: les fonctions de hachage.

Une fonction de hachage est typiquement une fonction mathématique qui transforme un objet potentiellement très gros et compliqué en une suite de caractères de taille fixe. Par exemple, la fonction sha256 (dont nous reparlerons ici) transforme ce pdf de la constitution française, qui fait 368 533 octets (sachant qu'il faut un octet pour coder un caractère de l'alphabet) en la chaîne de 64 caractères[1] suivante:

21b18f3d68e39167da331fd3dbbf22fc49bc9be221f32cfff1634ebc8999499b

Vous allez me dire, c'est génial, on a réduit la constitution française à 64 caractères. Par contre, on a perdu pas mal de choses en route.. on ne demandera pas aux juristes de travailler avec cette version réduite.

Effectivement, l'intérêt d'une fonction de hachage ne réside pas dans la préservation de l'information. En général, on utilise une fonction de hachage pour l'un des deux buts suivants:
- créer un index de peu d'objets mais chacun étant très complexe et sans numérotation évidente: ce n'est pas l'objet de cet article; - cacher une information tout en pouvant prouver qu'on la possède. Toutes les fonctions de hachage utilisées dans ce but ont la propriété essentielle qu'il est impossible de retrouver le texte qui a été haché à partir de son hash.

Ce deuxième but se retrouve par exemple lorsque vous enregistrez un mot de passe sur un site auquel vous vous inscrivez: si le site est un minimum sérieux, il ne va pas stocker votre mot de passe directement, mais son hash. Quand vous vous reconnectez au site, le site vous demande votre mot de passe, mais au lieu de le comparer avec ce qu'il a enregistré, il en calcule le hash et compare ce hash avec le hash qu'il avait enregistré. Quel intérêt?
Supposons que le site se fasse attaquer et que quelqu'un arrive à voler la base de données du site. Si elle contient tous les mots de passe, l'attaquant peut ensuite se faire passer pour vous sur ce site ou un autre sur lequel vous utiliseriez le même mot de passe. Si elle contient seulement les hashs, l'attaquant ne peut même pas se faire passer pour vous sur ce site: il est incapable de retrouver votre mot de passe à partir de son hash[2].

Preuve sans révélation d'information

Supposons que vous êtes un journaliste d'investigation (profession qui se fait rare, diront les mauvaises langues) qui dispose d'un document numérique confidentiel appartenant à une entité X, que vous voulez marchander contre une certaine information. Ne voulant pas risquer un guet-apens, vous convenez de vous retrouver sur un site de chat, couvrant votre adresse IP par Tor, et vous vous retrouvez face à un interlocuteur dont vous n'avez aucun moyen d'établir l'identité et donc l'affiliation à X. Il pourrait s'agir d'un service secret, ou de n'importe qui d'autre qui est intéressé par l'information. Vous ne voulez donc pas risquer de perdre votre atout en le donnant à n'importe qui, mais votre interlocuteur n'acceptera de parler que si vous lui prouvez que vous la détenez. La solution? Calculez le hash du document, et donnez le hash à votre interlocuteur.
- S'il s'agit d'un imposteur: il lui est aussi facile de remonter au contenu que pour vous de retrouver la constitution à partir de 21b18f3d68e39167da331fd3dbbf22fc49bc9be221f32cfff1634ebc8999499b. - S'il s'agit de X: il saura immédiatemment, en calculant le hash de son côté, que vous ne bluffez pas.

Preuve de travail accompli

J'ai déjà parlé dans mon billet précédent des preuves de travail accompli, traduction libre du proof-of-work de Satoshi. Une des propriétés intéressantes qu'on attend d'une fonction de hash est que ses caractères soient équiprobables, c'est-à-dire qu'étant donné une suite de caractères aléatoire, la probabilité que disons la i-ème lettre du hash de cette suite de caractères soit un 0, un 1, ..., un e, un f soit la même en hexadécimal (1 / 16). Dans ce cas, supposons que je cherche un hash qui commence par un zéro en prenant le hash d'un texte généré au hasard (par exemple un nombre). Il me faudra en moyenne 16 essais avant de réussir.
Supposons à présent que je veuille un hash qui commence par 10 zéros. Il me faudra alors en moyenne 16^10 essais avant de réussir. Et ainsi de suite.
L'idée de Satoshi pour implémenter la preuve de travail est de demander aux mineurs de produire un hash d'un nombre aléatoire concaténé avec des informations spécifiques au mineur et au bloc et d'ajuster la difficulté du minage pour maintenir une production régulière de blocs (et donc de la récompense associée) toutes les dix minutes, en faisant augmenter le nombre de zéros à obtenir au fur et à mesure que la puissance totale fournie augmente.

Établir une chronologie

J'ai un peu mis sous le tapis la question de comment savoir si un nouveau bloc proposé sur le réseau a bien été miné après le dernier bloc de la blockchain actuelle. Pourquoi est-ce important? Supposons que l'on ne vérifie pour accepter un bloc que le fait que toutes les transactions qui figurent dedans sont valides étant donné l'historique; autrement dit que personne ne redépense deux fois de l'argent, ou ne dépense de l'argent qu'il ne possède pas.
Cela ne suffit pas.
Un mineur peut très bien créer un bloc contenant une seule transaction sûre, par exemple entre des comptes qu'il possède lui-même et qui ne pourront pas changer de solde sans son intervention. Il mine ce bloc longtemps à l'avance, sans être en compétition avec qui que ce soit, et puis dès qu'il l'a trouvé, il le propose au réseau. Le réseau l'accepte et le mineur touche la récompense. Ce comportement est nuisible au réseau puisque le mineur ne joue pas son rôle de validation des transactions, mais se comporte en "parasite" en touchant simplement la récompense. En gros, au lieu que tous les mineurs travaillent au prochain bloc, et que l'un d'eux gagne à la lotterie, tous les mineurs jouent à une lotterie différente en parallèle.
Pour éviter cela, le protocole Bitcoin demande au mineur d'inclure un hash du bloc précédent dans la chaîne de caractères sur laquelle il fait la preuve de travail. Ainsi, il n'est pas possible de commencer à travailler au minage du bloc actuel avant que le bloc précédent n'ait été miné: cela impose une chronologie (le mineur n'ayant pas plus de moyen de deviner le hash du prochain bloc que de retrouver la constitution à partir de la chaîne précédente...).

[1] Il s'agit de la représentation en hexadécimal, soit en base 16, pour laquelle chaque symbole code un nombre entre 0 et 2^4-1=15, il en faut donc 256/4 = 64 pour obtenir 256 bits [2] Sauf bien sûr si vous utilisez un mot de passe courant, par exemple "123456" ou "password" ou encore un mot du dictionnaire avec un numéro à la fin: la première chose que l'attaquant fera sera de calculer le hash de tout un tas de mots de passe connus, pour voir si votre hash correspond à l'un d'eux. Vous comprenez maintenant pourquoi on vous demande toujours de choisir un mot de passe compliqué..

comments powered by Disqus