Cet article propose une méthode utilisant la blockchain (protocole BitCoin) pour effectuer des tirages au sort de façon équitable, non répudiable, reproductible, horodatée et sans recourir à un tiers de confiance.

• 1) Tirage au sort et démocratie
• 2) L'idée
• 3) Introduction à Bitcoin
• 4) Application au tirage au sort
• 5) Robustesse du système

1) Tirage au sort et démocratie

Dans une démocratie idéale, le tirage au sort complète ou remplace le système des élections.

L'enjeu étant très important, il faut une procédure de tirage au sort qui soit au dessus de tout soupçon. L'appel à un tiers de confiance (autorité, huissier de justice, etc) n'est pas suffisant.

2) L'idée

Pour être irréfutable, un tirage au sort doit s'appuyer sur un phénomène totalement aléatoire, observable par tous et sur lequel personne ne puisse influer.

Le tirage au sort se passe en deux temps :

1. L'annonce : Une autorité publie par avance la liste des candidats au tirage au sort (typiquement l'ensemble des citoyens) et leur attribue un numéro. Cette autorité publie aussi le phénomène aléatoire choisi, le protocole utilisé pour transformer cette valeur aléatoire en liste de résultats, et l'échéance du tirage au sort. Pour être fiable, ces informations ne doivent pas pouvoir être modifiées après leur publication.
2. Le tirage au sort : A échéance, la valeur du phénomène aléatoire est mesurée et convertie en une suite de numéros, correspondant à la liste des candidats.

Pour les phénomènes aléatoires, on peut penser par exemple à :

• Naturels : Température à un instant donné et un lieu donné
• Humains mais non prévisibles : Cours du CAC 40 à la fermeture de la bourse
• Informatique : Valeur du hash du nième block Bitcoin miné (voir plus bas)

Pour les phénomènes naturels, les organismes responsables de la mesure et la publication de ces valeurs sont susceptibles de les falsifier. En outre, l'entropie de chaque mesure (= le champ des valeurs possibles) étant plus faible que les combinaisons possibles de tirage au sort, elles ne peuvent être converties de manière équiprobable en résultat de tirage au sort. La mesure de la valuer du CAC40 à un instant donné souffre des mêmes écueils.

Dans la suite de cet article, nous verrons que le réseau Bitcoin présente des propriétés très intéressantes qui peuvent être utilisées pour assurer à la fois :

• La publication non falsifiable et persistante des candidats au tirage au sort
• Un générateur publique (partagé) de nombres aléatoires, non falsifiable

3) Introduction à Bitcoin

Bitcoin est une monnaie virtuelle, décentralisée, qui permet le transfert d'argent, de pair à pair, de manière anonyme et pratiquement sans frais.

Dans notre cas, le transfert d'argent ne nous intéresse pas : Nous détournons le protocole Bitcoin pour l'utiliser comme un notaire qui va enregistrer de manière permanente et publique l'annonce d'un tirage au sort.

Le protocole bitcoin

Bitcoin est basé sur une architecture distribuée : Aucun organisme ou site web ne contrôle le système bitcoin : Le réseau est constitué d'une multitude de noeuds, qui partagent et maintiennent une copie de toutes les transactions BitCoin émises à ce jour.

Le protocole Bitcoin, basé sur des techniques de cryptographie et des fonctions de hashage éprouvées (SHA), garantit par construction que chaque noeud du réseau aura la même copie de la liste des transactions, sans possibilité de répudiation (falsification d'une transaction à postériori).

La blockchain

Les transactions bitcoin sont groupées par bloc dans ce qu'on appelle la blockchain. Toutes les dix minutes environ, le réseau génère un nouveau bloc dans lequel les nouvelles transactions sont ajoutées.

La robustesse du bitcoin réside dans le chainage de ces blocs : Chaque bloc contient en entête le hash du bloc précédent (=somme de hashage de son entête + toutes ses transactions).

Ainsi pour falsifier une transaction passée de la blochain, il faut changer le hash du bloc la contenant, ainsi que les hash de tous les blocs suivants, et il faut parvenir à propager ce changement à tous les noeuds du réseau.

Or, la génération d'un nouveau bloc bitcoin est concue pour être une opération extrêmement couteuse en puissance de calcul.

La blockchain bitcoin

Le minage de bitcoins

Pour être valide, un nouveau bloc bitcoin doit contenir la résolution d'un problème mathématique très couteux en temps de calcul, et changeant à chaque nouveau bloc : C'est la preuve de travail.

Le problème est le suivant : Trouver un nombre (le nonce) tel que :
hash(nonce + hash(bloc-précédent) ) = hash-avec-N-zéros-en-prefixe = 00000000000????????????????

La fonction de hash n'étant pas inversible, il est impossible de deviner le nonce en fonction du résultat attendu : Il est nécessaire d'en essayer au hasard, plusieurs centaines de milliards.

Le nombre de zéros préfixant le hash de résultat est appelé la difficulté : Plus ce nombre est élévé, et plus le nonce est difficile à trouver. Le réseau adapte régulièrement la difficulté à la puissance de calcul de tous les mineurs pour que la génération d'un nouveau bloc prenne environ 10 minutes.

Les acteurs du réseau cherchant de nouveaux blocs sont appelés des mineurs.

Le premier mineur à trouver un bloc valide (donc un nonce répondant au problème en cours) se voit récompensé par des bitcoins. C'est d'ailleurs le seul moyen de créer de nouveaux bitcoin : A l'instar des métaux précieux, la difficulté de minage des nouveaux blocs (et donc des bitcoins) en font la rareté, et donc la valeur.

Les transactions

Les transactions bitcoin sont à la fois publiques et anonymes : Elles sont signées avec des clefs asymétriques :

Chaque transaction se compose de :

• la clef publique de l'émetteur
• la clef publique du récepteur
• le montant de la transaction

Le tout, signé avec la clef privée de l'émetteur.

Ce système peut être détourné pour enregistrer des données arbritraires dans la blockchain :

En effet, aucune vérification n'est faite (et ne peut être faite) sur la clef publique de destination : Il est donc possible de dépenser une somme d'argent vers un identifiant de son choix ne correspondant à aucune clef privée existante. Les bitcoins correspondants ne seont jamais réclamé et sont détruits. La transaction correspondante sera à jamais inscrite sur la blockchain, et signé par son émetteur.

En mettant comme identifiant de destinatire le hash d'un document, on peut ainsi procéder à une signature horodatée de ce document, qui laissera a jamais sa trace dans la blocchain.

4) Application au tirage au sort

Le réseau bitcoin présente donc les deux propriétés nécessaires à notre système de tirage au sort :

• Publication non répudiable d'une annonce de tirage au sort, par détournement des transaction et publication du hash de l'annonce.
• Le hash de chaque bloc est totalement aléatoire : Il n'est contrôlable par personne, vérifiable par tous, et dispose dune grande entropie (environs 2^200 valeurs possibles) : C'est une bonne variable aléatoire.

Nous pouvons ainsi utiliser le réseau bitcoin pour un tirage au sort, comme suit :

1. L'organisme organisant le tirage au sort publie largement sa clef publique (sur son site) pour qu'elle soit connue de tous . Il publie aussi l'annonce du tirage au sort sur son site. Cette annonce se compose de :
   • La liste ordonnée des candidats
   • Le numéro du futur bloc bitcoin choisi pour le tirage au sort: égal à la durée de l'échéance divisée par 10 minutes (soit 1000 blocs = 7 jours)
   • Le nombre de personnes à tirer au sort
2. L'organisme publie une signature de cette anonnce sur le réseau bitcoin en émettant une transactiom d'une fraction de bitcoin au bénéfice du hash de cette annonce, et signée de sa clef privée. L'annonce est ainsi gravée dans le marbre, irrépudiable.
3. Lorque le bloc futur choisi est créé , on utilise son hash comme variable aléatoire: Cette valeur est totalement imprédictible et vérifiable, car partagée par tous les noeuds du réseau. Pour transformer ce hash en liste de résultats, on peut utiliser la méthode (algorithme) suivante :

Pour chaque personne à tirer:

• Prendre le reste de la division euclidienne du hash courant par le nombre de personnes non encore tirées au sort
• Le candidat correspondant à ce nombre est le prochain tiré au sort
• hash_courant = hash(hash_courant) (cette action équivaut à un mélange déterministe de cartes)

5) Robustesse du système

Pour pirater ce système, il faudrait pouvoir corrompre soit:

• L'annonce du tirage au sort
• Le bloc cible pris pour variable aléatoire

Dans les deux cas, cela revient à pouvoir générer un bloc valide, comportant l'annonce falsifiée, ou un hash nous arrangeant (sélectionnant un candidat particulier), avant qu'un autre bloc valide ne soit découvert par un autre mineur et propagé / validé par le réseau.

Il faudrait donc avoir une puissance de calcul sensiblement supérieure à l'ensemble de la puissance de tous les autres mineurs réunis.
Aujourd'hui cette puissance est estimée à : 7000 fois la somme de la puissance des 500 plus gros super calculateurs au monde !

Ainsi, la falsification d'un tirage au sort nécessiterait des équipements informatiques de plusieurs dizaines de milliards d'euros, ainsi que leur mise en oeuvre : Ce sont des resources infiniment supérieures à celles nécessaires pour falsifier un tirage au sort traditionnel (trucage de machine, corruption d'hussier).