TryAlgo

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$ : .

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)

Bitcoin (2009)

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

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

Commentaires