Si vous avez suivi la dernière fois, j'expliquais que toutes les transactions entre les utilisateurs de Bitcoin sont répertoriées dans un registre commun, la blockchain.

Après avoir écarté la possibilité de créer de fausses transactions des comptes d'autres personnes vers le sien, il n'est pas encore clair de savoir comment les transactions, même valides, sont ajoutées à la blockchain.

Ce problème est difficile à résoudre dans la mesure où il faut que des milliers d'individus (ou plus exactement, leurs ordinateurs) se mettent d'accord sur une séquence de transactions. L'ordre précis est important, par exemple pour éviter la situation où Alice et Bob ont chacun les blockchains suivantes:

Alice:

Charlie envoie 1 BTC à Alice

Alice envoie 1 BTC à Bob

et Bob:

Alice envoie 1 BTC à Bob

Charlie envoie 1 BTC à Alice

Dans le premier cas il est clair qu'Alice possède assez pour donner 1 bitcoin à Bob (en supposant que Charlie possédait ce bitcoin), dans le second cela l'est moins.
En réalité, une transaction n'est valide que dans un contexte donné: pour savoir si elle l'est réellement, la liste de toutes les transactions dans l'ordre dans lequel elles se sont produites est nécessaire.
En d'autres termes, s'il est nécessaire que tous aient le même ensemble de transactions, ce n'est pas suffisant: Il faut en plus qu'elles soient dans le bon ordre.

Il faut donc un consensus global sur ce qui constitue la vraie blockchain, avec une liste de transactions valides dans un ordre immuable.

La Preuve de Travail Accompli

L'inventeur de Bitcoin, Satoshi Nakamoto, a choisi d'utiliser le concept de preuve de travail accompli (PTA [1]), pour réaliser ce consensus.

L'idée est que les transactions vont être regroupées par blocs (d'où le nom de blockchain).
Pour construire un bloc, il faut trouver une solution à un problème mathématique très compliqué, conçu de telle sorte qu'en moyenne, lorsque tous les membres du réseau essaient de le résoudre, une personne y arrive toutes les dix minutes environ. L'avantage de ce problème est qu'il très facile de vérifier une solution une fois qu'elle a été trouvée. Ainsi, lorsque Alice prétend l'avoir résolu, elle envoie sa solution à tout le monde. Lorsque disons Bob la reçoit, il vérifie qu'elle est correcte et alors seulement il l'ajoute à sa blockchain.
Par consensus, Alice reçoit en contribuant un bloc à la blockchain

• un montant fixe en bitcoin qui ne dépend que du moment où elle a trouvé le bloc (en ce moment, 25 bitcoins par bloc);
• des commissions versées par ceux qui effectuent les transactions.

L'opération consistant à chercher des blocs (et donc des solutions de problèmes mathématiques associés) s'appelle le minage, par analogie avec l'or: comme pour le métal précieux, il contribue à l'augmentation de la masse de Bitcoins en circulation et demande beaucoup d'efforts.

Qu'est-ce qui empêche Bob de voler la solution d'Alice pour lui voler sa récompense?

En réalité, le problème mathématique à résoudre n'est pas le même pour chacun, même s'il est du même niveau de difficulté. Je rentrerai dans les détails dans un autre article pour ne pas perdre trop de monde, mais il suffit de comprendre qu'en voyant la solution, on sait immédiatement que le problème résolu est celui d'Alice et que la récompense lui revient.

Et si Bob reçoit en même temps deux blocs B1 et B2 contenant des solutions valides?

Bob ne peut pas les recevoir exactement en même temps, mais il est possible qu'il les reçoive à un très petit intervalle de temps. Dans ce cas, il choisit le premier qu'il a reçu, disons B1, et continue à miner par-dessus la blockchain ainsi augmentée.
Il est tout à fait possible qu'au même moment, Charlie ait reçu les deux mêmes blocs, mais avec B2 en premier.
On se retrouve alors dans la situation d'un fork: deux blockchains coexistent.

Bien sûr, si cette situation venait à durer, ce serait catastrophique: il n'y aurait plus de consensus sur qui a quoi, et il serait possible de dépenser deux fois le même argent, par exemple:

Blockchain 1 (ce qui est entre parenthèses est pour information, mais pas dans la blockchain comme expliqué dans l'article Premiers pas):

---

Bloc de X

(Jeanine a 0 BTC)

Jean-Paul envoie 1 BTC à Jeanine

---

Bloc de Alice

Jeanine envoie 1 BTC à Joséphine

---

Blockchain 2:

---

Bloc de X

(Jeanine a 0 BTC)

Jean-Paul envoie 1 BTC à Jeanine

---

Bloc de Alice

Jeanine envoie 1 BTC à Jean-Claude

---

Dans cette situation, le même bitcoin a été envoyé à Joséphine et Jean-Claude! Cela est possible parce qu'ils utilisent des blockchains différentes.

Heureusement, cette situation ne va pas durer: quelqu'un va finir par miner un nouveau bloc par-dessus une des deux blockchains, qui deviendra donc plus longue, et les mineurs vont abandonner la blockchain plus courte. Bien sûr, il pourrait de nouveau y avoir deux blocs minés quasiment en même temps, mais la probabilité que cela se produise deux fois de suite est très faible, et devient astronomiquement petite très rapidement [2].

Dès lors, le meilleur moyen pour être sûr qu'on n'a pas été payé en monnaie de singe est d'attendre que quelques blocs supplémentaires aient été minés (on entend souvent parler de confirmations). Si on est paranoïaque, attendre 6 confirmations (soit une heure) garantit avec une certitude quasi-absolue que l'on est sur la blockchain principale.

Ah bon? Et pourquoi les mineurs abandonneraient-ils la blockchain la plus courte?

Parce qu'ils y ont intérêt: les seuls bitcoins qui ont de la valeur sont ceux qui sont sur la chaîne principale, les autres sont comme un chèque raturé: personne n'en veut.

Or, l'hypothèse que fait Satoshi, et qui s'est révélée tout à fait raisonnable, est que la majorité des ordinateurs du réseau joue le jeu de garder la chaîne la plus longue: la blockchain principale s'établit par consensus majoritaire. Les mathématiques empêchent alors quelqu'un qui est en minorité d'avoir suffisament de puissance de calcul pour miner des blocs plus vite que le reste des utilisateurs.

Mais si je possède plus de la moitié des ordinateurs du réseau, je peux choisir la blockchain principale?

Si vous possédez la majorité des ordinateurs du réseau, vous pouvez effectivement tricher, mais pas tant que ça: vous pouvez redépenser plusieurs fois des bitcoins, mais vous ne pouvez ni en créer ni en voler à qui que ce soit.

De plus, quelqu'un va très rapidement se rendre compte que vous faites cela, et le bitcoin risque de perdre toute sa valeur. Vous avez bien plus intérêt à miner en suivant les règles avec toute cette puissance de calcul, vous deviendrez riche rapidement!

Oui, mais je suis juste méchant et je veux juste détruire le réseau Bitcoin

Ok, pas de souci, mais préparez-vous à de solides investissements. D'après Forbes [3], en Novembre 2013, la puissance totale des ordinateurs du réseau Bitcoin dépassait par un facteur 256 les 500 plus puissants superordinateurs du monde! Même si vous avez la carte adhérent à la Fnac, ça risque d'être ric-rac, comme on dit.
En plus d'être méchant, vous avez donc intérêt à être vraiment très très très riche.

La suite au prochain épisode!

1.  Proof of Work en anglais
2. J'essaierai de couvrir ce point un de ces jours. Mais comme toujours, j'essaie de ne pas parler de tout en même temps :-)
3. http://www.forbes.com/sites/reuvencohen/2013/11/28/global-bitcoin-computing-power-now-256-times-faster-than-top-500-supercomputers-combined/