Skip to main content Link Search Menu Expand Document (external link)
    

Arbres de Merkle : la structure de données à l'origine de git, BitTorrent, Bitcoin, Ethereum, The DAO et autres blockchains

•

Merkle trees (1979)

Le principe est simple : calculer le hash d’un nœud à partir d’un hash de ses fils. Dans un arbre binaire, pour un nœud ayant pour fils $h_1$ et $h_2$ : \(h(noeud) = h(h1, h2)\).

Cette structure de données sera à l’origine de tout ce que je vais présenter.

git (2005)

Logiciel de gestion de versions centralisé. Mais comment garantir l’intégrité des données ? On calcule une hiérarchie de hashes :

Slide tirée de la présentation Code is not text! How graph technologies can help us to understand our code better.

Quelqu’un sur GitHub qui est parvenu à reverse-engineer le hash de git. Ce n’est pas secret, mais c’est un peu compliqué.

BitTorrent (2001)

  • Tribler qui explique qu’on a besoin qu’un nombre $\log n$ de hashes de pour certifier un tronçon parmi $n$ d’un fichier torrent (authentifié par le hash de la racine) : pas besoin de calculer tous les hashes de l’arbre.
  • Notez qu’on a également besoin du numéro du tronçon : sa décomposition en binaire permet de dire si les tronçons sont gauche ou droite, cf. cette réponse sur Bitcoin Stack Exchange.
  • Fun fact : git + BitTorrent = IPFS (InterPlanetary File System)

Bitcoin (2009)

Tiens mais c’est pas mal ces arbres de Merkle, et si je fabriquais une monnaie avec ?

  • Papier fondateur : bitcoin.org/bitcoin.pdf
  • Curieusement, ce papier ne fait pas mention de la règle : « Pour construire un bloc, il faut trouver une nonce telle que le hash obtenu $< 2^{187}$. Si vous y parvenez, vous remportez 25 BTC soit à peu près 17500 $. » (La valeur 187 dépend du nombre de mineurs.)
  • Ce qui me fascine, c’est que lorsqu’on construit un bloc, on ne sait pas encore si on est dans la bonne ligne de temps. C’est la popularité de notre chaîne de blocs qui nous dit si on a gagné ou pas. La chaîne la plus longue gagne.

Ethereum (2014)

Tiens mais c’est pas mal ces arbres de Merkle, et si je fabriquais un langage Turing-complet avec ?
What could possibly go wrong?

Ethereum sur Wikipédia

Leur site avec tellement de CSS qu’on croirait qu’ils peuvent sauver le monde du réchauffement climatique

The DAO (2016)

Tiens mais c’est pas mal ces arbres de Merkle, et si je fabriquais un fonds d’investissement décentralisé avec ?

DAO : decentralized autonomous organization. Bah oui tiens, pourquoi centraliser les votes lors d’une élection alors qu’on pourrait utiliser le même principe que pour les Bitcoin ?

The DAO sur Wikipédia

Certificate Transparency vs. DNSChain

Un autre lieu où on aimerait se passer de tiers de confiance, c’est pour les certificats SSL.

Le but de Google’s Certificate Transparency :

Make it impossible (or at least very difficult) for a CA to issue a SSL certificate for a domain without the certificate being visible to the owner of that domain.

« Et alors, il y en a qui font ça dans la recherche académique ? » demande Tito

Oui ! Andrew Miller, Michael Hicks, Jonathan Katz, and Elaine Shi. “Authenticated Data Structures, Generically”, POPL 2014.

Et la grande classe, c’est qu’ils proposent une implémentation en Caml sur GitHub.

Ledit Andrew Miller expose également son analyse d’Ethereum.

Des conférences pipeau à l’IHP (16/11/2016) et moins pipeau à Télécom ParisTech (15/11/2016) (lol ils abusent, ils pourraient communiquer).

Add-ons

  • Namecoin, un fork de Bitcoin pour les noms de domaine et d’autres types de données
  • Tezos, un peu méta : les joueurs peuvent voter pour changer les règles

Commentaires

Sujets similaires