Mois : février 2017

Supplément à l’étude du Bitcoin

Voici (en anglais) l’article que j’ai coécrit avec Ricardo Perez-Marco sur l’étude des probabilités de double-dépense dans le réseau Bitcoin. Il s’agit notamment d’une correction à l’article fondateur du Bitcoin, Bitcoin: A Peer-to-Peer Electronic Cash System. Nous donnons une formule fermée pour la probabilité de réussite de double-dépense et nous prouvons le fait que cette probabilité tend exponentiellement vers zéro en fonction du nombre z de confirmations requises, un résultat souvent cité mais jamais démontré. Enfin, nous menons une analyse plus fine de cette tentative de double dépense en prenant en compte le temps mis par les honnêtes mineurs pour miner z blocs, une information disponible par le marchand qui s’apprête à envoyer son bien de consommation au possible attaquant.

J’ai écrit « correction ». C’est un mot un peu fort mais pourtant, on a beau le tourner dans tous les sens, la partie mathématique de l’article (section 11 « Calculations ») est légèrement incorrecte.

Le raisonnement de Satoshi

Son approximation

Satoshi estime que les mineurs honnêtes qui disposent d’une puissance de calcul relative égale à p mettent exactement \frac{z.\tau_0}{p} pour miner z blocs avec \tau_0 = 10 minutes. C’est évidemment une grossière approximation. En réalité, les honnêtes mineurs mettent en moyenne \frac{\tau_0}{p} pour miner un bloc et \frac{z.\tau_0}{p} pour miner z blocs. Cette approximation sert ensuite à Satoshi pour dire que pendant ce temps, l’attaquant qui cherche à réaliser une double-dépense a réussi à miner {\bf N'}(\frac{z\tau_0}{p}) où {\bf N'} est un processus de Poisson d’intensité q où q = 1-p est la puissance de calcul relative dont dispose l’attaquant. Le fait qu’il y ait ici un processus de Poisson est tout à fait naturel. Cela vient du fait que la fonction de hachage SHA256 est supposée parfaite. Cette hypothèse a pour conséquence que le temps de minage inter-bloc suit une loi exponentielle et que le processus de comptage qui compte le nombre de blocs minés est un processus de Poisson. Par suite, le nombre de blocs minés par l’attaquant suit une loi de Poisson d’intensité \frac{q.z\tau_0}{p}. C’est ce qu’a écrit Satoshi.

Le calcul final

La probabilité de réussite de double-dépense s’obtient ensuite simplement en utilisant la formule des probabilités totales : P(A) = \sum_{k} P(A | B_k).P(B_k). Ici, A désigne l’événement « l’attaquant réussit son attaque » et B_k désigne l’événement « l’attaquant a réussi a miné k blocs au moment où les honnêtes mineurs viennent de miner z blocs ». La probabilité P(B_k) a été vue plus haut. Ici z est fixé.

Lorsque k>z, on a bien sûr P(A | B_k) = 1 et lorsque k<z, l’attaquant a autant de chance qu’un joueur qui joue contre la banque à pile ou face avec un retard de z-k : à chaque lancer de pièce de monnaie truquée en faveur de la banque (la banque a une probabilité p de gagner) le joueur avance ou recule de 1. S’il finit par rattraper la banque, il a gagné. Ce calcul est classique. Satoshi renvoie au célèbre livre de Feller An introduction to probability theory and its applications. C’est un exemple élémentaire de marche aléatoire. On a P(A | B_k) = (\frac{q}{p})^{z-k}. D’où la formule finale que donne Satoshi en réarrangeant un peu les termes de sa somme : P(A) = 1-\sum_{k=0}^{z}\frac{\lambda^k e^{-\lambda}}{k!}(1-(\frac{q}{p})^{z-k}) à la suite de quoi, Satoshi présente un petit code en C pour calculer numériquement cette somme.

Le vrai calcul

Une loi binomiale négative

Seulement voilà, le temps mis par les honnêtes mineurs est aléatoire et n’a aucune raison d’être égale à sa moyenne \frac{z.\tau_0}{p}. La formule donnée plus haut pour P(A) est fausse. En réalité, si l’on désigne par {\bf S}_z le temps mis par les honnêtes mineurs pour miner z blocs, la loi de {\bf S}_z est une loi Gamma de paramètre (z,\tau_0) et le nombre de blocs minés par l’attaquant au moment où les honnêtes mineurs découvrent leur zème bloc est {\bf N'}({\bf S}_z). Un petit calcul montre que la loi de {\bf N'}({\bf S}_z) est une loi binomiale négative de paramètre (z,p). C’est normal. Tout se passe en effet comme si la course au minage était un tirage multiple avec remise d’une urne remplie de boules noires et blanches jusqu’à l’obtention de z boules blanches. Tirer une boule noire signifie : « l’attaquant découvre un nouveau bloc » et tirer une boule blanche signifie « les honnêtes mineurs découvrent un nouveau bloc ». Au total, le nombre de boules noires tirées représente le nombre de blocs minés par l’attaquant au moment où les honnêtes mineurs découvrent leur zème bloc…

La formule de Meni Rosenfeld

La véritable probabilité de réussite P(z) de double dépense est P(z) = P[{\bf N'}({\bf S}_z) >z]+\sum_{k=0}^{z} P[{\bf N'}({\bf S}_z) = k] (\frac{q}{p})^{z-k}. En utilisant le fait que {\bf N'}({\bf S}_z) est une loi binomiale négative de paramètre (z,p) comme expliqué ci-dessus, on en déduit que  P(z) = 1-\sum_{k=0}^{z-1}(p^z.q^k-q^z.p^k)\dbinom{k+z-1}{k}. Nous ne le savions pas au moment de la rédaction de notre article, nous ne l’avons découvert qu’après mais cette formule avait déjà été publiée par Meni Rosenfled dès décembre 2012 dans Analysis of hashrate-based double-spending… Notons que Meni Rosenfeld vient tout juste de publier un article qui a l’air fort intéressant : Decentralized Prediction Market without Arbiters.

Une formule fermée

En fait, on peut triturer la formule de Rosenfeld pour obtenir une formule fermée. Cela vient de ce que la fonction de répartition d’une loi binomiale négative est une certaine fonction bêta incomplète régularisée. On montre que la probabilité de réussite de double-dépense est tout simplement P(z) = I_{s}(z,\frac{1}{2}) avec s = 4 p q, q = 1-p et I_x(a,b) = \frac{\Gamma(a+b)}{\Gamma(a).\Gamma(b)}.\int_0^x t^{a-1} (1-t)^{b-1} dt où \Gamma est la célèbre fonction Gamma : \Gamma(x) = \int_{0}^{\infty} t^{x-1} e^{-t} dt pour x>0. Notons que la fonction beta régularisée incomplète est une fonction extrêmement classique et implémentée dans tous les logiciels de calcul moderne. En R par exemple, la fonction qu’il suffit d’invoquer est « pbeta ». Et inutile pour cela de charger des packages…

Autrement dit, Satoshi s’est fatigué pour rien ! En menant un calcul correct, sans aucune approximation, on obtient une formule élémentaire pour la probabilité de réussite de double-dépense. La conclusion que l’on peut en tirer, je crois, est que Satoshi était un génie mais n’était pas un vrai mathématicien. Certains avaient avancé le nom de John Nash mais cela nous semble impossible.

Des asymptotiques…

Ensuite, nous avons calculé l’asymptotique de P(z). Grâce à notre formule fermée mettant en jeu une fonction bêta, il est facile de montrer que P(z)\sim \frac{s^z}{\sqrt{\pi (1-s) z}} avec toujours s= 4 p q. Quant à la probabilité (erronée) de Satoshi que l’on note P_{SN} (z), nous montrons que l’on a P_{SN} (z)\sim \frac{e^{-z c(\frac{q}{p})}}{2} avec c(x)=x-1-\log(x). Il est vrai que cette probabilité tend exponentiellement vers 0 mais simplement, la formule est fausse !

Comparaison entre les deux probabilités

D’après les formules données pour P(z) et P_{SN}(z), il s’avère que Satoshi a sous-estimé la probabilité de double-dépense. On a clairement d’après les formules ci-dessus : P(z)\prec P_{SN}(z). On peut aussi s’amuser à calculer un rang explicite à partir duquel Satoshi s’est (vraiment) trompé, i.e., un rang à partir duquel on a P(z)< P_{SN}(z)… Cela donne lieu à des calculs d’inégalités un peu pénible avec les fonctions Gamma. Il ne s’agit que d’un jeu mathématique…

Une analyse plus fine

Enfin, on calcule la probabilité de réussite de double-dépense P(z,\kappa) sachant que les honnêtes mineurs ont mis \kappa \tau pour miner z blocs avec \tau = \frac{z.\tau_0}{p} (cf plus haut). Autrement dit, \kappa mesure l’écart par rapport à l’hypothèse de Satoshi… Là encore, on obtient une formule fermée bien que légèrement plus compliquée que celle donnant P(z). Explicitement, on a P(z,\kappa) = 1 - Q(z,\kappa z\frac{q}{p}) + (\frac{q}{p})^z e^{\kappa z \frac{p-q}{p}} Q(z,\kappa z) où Q désigne la fonction Gamma régularisée incomplète. On analyse cette fonction de \kappa, P(z,\kappa). Notons que P_{SN}(z) = P(z,1).

A la fin de l’article, nous avons publié des tables pour P(z,\kappa) en fonction de z et q = 1-p.

Author’s Bitcoin Beer Address

Je dois dire que ce fut un plaisir pour moi de travailler avec Ricardo. J’espère que notre collaboration ne se terminera pas là. Les maths du bitcoin sont évidemment loin d’être finies d’explorer !

Si vous avez aimé notre travail et souhaitez encourager notre recherche (au pub), vous pouvez nous envoyer des sous ! Voici notre ABBA (Author’s Bitcoin Beer Address) :

1KrqVxqQFyUY9WuWcR5EHGVvhCS841LPLn

Vous pouvez aussi plus sobrement financer notre séminaire de cryptofinance pour nous donner les moyens de développer la recherche académique autour du bitcoin et de la blockchain.

Séminaire de Cryptofinance

Last, but not least, nous avons naturellement dédié cet article à André Warusfel qui fut notre professeur de mathématiques bien-aimé et qui est décédé récemment. Cher Warus, vous auriez certainement apprécié le bitcoin et ses mathématiques !