Connectez-vous pour consulter le corrigé.
On s’intéresse dans ce sujet au problème de la double dépense de bitcoins par un groupe d’individus mal intentionnés.
On rappelle que le bitcoin est une monnaie virtuelle dont l’utilisation pour des transactions est associée à une structure unique appelée blockchain, partagée sur le réseau des usagers de cette monnaie et ayant pour but de sécuriser ces transactions.
La modélisation étudiée ne nécessite pas de connaissances particulières sur le bitcoin et la blockchain.
On démontre dans cette partie deux résultats préliminaires, aux questions ??? et ???. Ces résultats seront utilisés dans la suite du sujet et pourront être admis.
Soit \(X\) et \(Y\) deux variables aléatoires sur un espace probabilisé, à densité et indépendantes.
On note \(F_{X}\) et \(F_{Y}\) les fonctions de répartition de \(X\) et \(Y\).
On suppose que \(Y\) est à valeurs positives et possède une densité \(f_{Y}\) dont la restriction à \([0,+\infty[\) est continue sur cet intervalle.
Pour tout \(x \in \mathbb{R}^+\), on pose \(H(x)=\mathbb{P}([X \leqslant Y] \cap[Y \leqslant x])\).
On admet que, si \((A_n)_{n\in\mathbb{N}}\) est une suite d’événements telle que, pour tout \(n\in\mathbb{N}\), \(A_n \subset A_{n+1}\), alors on a : \[\mathbb{P}\! \left( \bigcup_{n=0}^{+\infty}A_n \right) = \lim\limits_{n\to+\infty}\mathbb{P}(A_n)\]
Montrer que \(H\) est une fonction croissante sur \(\mathbb{R}^{+}\) qui admet une limite finie en \(+\infty\).
En utilisant la suite \((H(n))_{n\in\mathbb{N}}\), montrer que \(\displaystyle \lim_{x \to +\infty} H(x)=\mathbb{P}(X \leqslant Y)\).
Que vaut \(H(0)\) ?
Soit \((u, v)\) un couple de réels positifs tels que \(u<v\).
Montrer que \(H(v)-H(u)=\mathbb{P}([X \leqslant Y] \cap[u<Y \leqslant v])\) puis que : \[F_{X}(u) \, \dfrac{F_{Y}(v)-F_{Y}(u)}{v-u} \leqslant \dfrac{H(v)-H(u)}{v-u} \leqslant F_{X}(v) \, \dfrac{F_{Y}(v)-F_{Y}(u)}{v-u}\]
En déduire que, pour tout \(x \in \mathbb{R}^{+}, H\) est dérivable en \(x\) et que \(H'(x)=F_{X}(x) \, f_{Y}(x)\).
En conclure que pour tout \(x\) réel positif, \(H(x)=\displaystyle \int_{0}^{x} F_{X}(t) \, f_{Y}(t)\,\mathrm{d}t\).
Montrer que : \(\mathbb{P}(X \leqslant Y)=\displaystyle \int_{0}^{+\infty} F_{X}(t) \, f_{Y}(t) \,\mathrm{d}t\).
En utilisant la fonction \(K: x \mapsto \mathbb{P}([ X<Y] \cap[Y \leqslant x ]),\) on montrerait de même et nous l’admettrons que: \[\mathbb{P}(X<Y)=\int_{0}^{+\infty} F_{X}(t) \, f_{Y}(t) \,\mathrm{d}t=\mathbb{P}(X \leqslant Y)\]
Que peut-on en déduire pour \(\mathbb{P}(X=Y)\)?
Application aux lois exponentielles.
On suppose que \(U\) et \(V\) sont deux variables aléatoires indépendantes suivant des lois exponentielles de paramètres respectifs \(\lambda\) et \(\mu\), réels strictement positifs. Soit \(\theta\) un réel positif ou nul.
Déterminer la fonction de répartition de la variable aléatoire \(X=U-\theta\).
En déduire que : \[\mathbb{P}(U-\theta \leqslant V)=1-\dfrac{\mu}{\lambda +\mu} \,\mathrm{e}^{-\lambda \theta }\]
On considère une famille d’événements \(\left(B_{k}\right)_{k \in \mathbb{N}^{*}}\) d’un même espace probabilisé.
Montrer par récurrence sur \(n \in \mathbb{N}^{*}\) que \(\displaystyle \mathbb{P} \! \left(\bigcup_{k=1}^{n} B_{k}\right)\leqslant \sum_{k=1}^{n} \mathbb P\left(B_{k}\right)\).
On suppose que la série \(\displaystyle \sum_{k\geqslant 1} \mathbb{P}\left(B_{k}\right)\) converge. Montrer que : \[\mathbb{P}\! \left(\bigcup_{k= 1}^{+\infty}B_{k}\right) \leqslant \sum_{k=1}^{+\infty} \mathbb{P}\left(B_{k}\right)\]
Dans toute la suite du sujet, on désigne par \(p\) un réel de l’intervalle \(] 0,1[\), et on pose \(q=1-p\).
On modélise une compétition entre deux groupes d’individus \(A\) et \(B\) avec les règles suivantes :
Le groupe \(A\) doit résoudre une suite de problèmes \(\left(P_{k}\right)_{k\geqslant 1}\) dans l’ordre des indices. Au temps \(t=0,\) le groupe commence la résolution du problème \(P_{1},\) ce qui lui prend un temps représenté par la variable aléatoire \(X_{1}\). Une fois \(P_{1}\) résolu, le groupe aborde immédiatement le problème \(P_{2}\), et on note \(X_{2}\) le temps consacré à la résolution de \(P_{2}\) par le groupe \(A,\) et ainsi de suite.
Pour tout \(k \in \mathbb{N}^{*}\), on note \(X_{k}\) la variable aléatoire donnant le temps consacré à la résolution du problème \(P_k\) par le groupe \(A\).
De même, le groupe \(B\) doit résoudre dans l’ordre une suite de problèmes \(\left(Q_{k}\right)_{k\geqslant 1} ;\) la résolution du premier problème \(Q_{1}\) commence au temps \(t=0\) et on note, pour tout \(k \in \mathbb{N}^{*}, Y_{k}\) la variable aléatoire donnant le temps consacré par le groupe \(B\) a la résolution du problème \(Q_{k}\).
À ce jeu est associé un espace probabilisé \((\Omega, \mathcal{A}, \mathbb{P})\) sur lequel sont définies les suites de variables aléatoires \(\left(X_{k}\right)_{k\geqslant 1}\) et \(\left(Y_{k}\right)_{k\geqslant 1}\), et on fait les hypothèses suivantes :
pour tout \(k \in \mathbb{N}^{*}, X_{k}\) suit la loi exponentielle de paramètre \(p\), noté \(\mathcal{E}(p),\) et \(Y_{k}\) suit la loi exponentielle \(\mathcal{E}(q)\) ;
pour tout \(k \in \mathbb{N}^{*},\) les variables aléatoires \(X_{1}, \ldots, X_{k}, Y_{1}, \ldots, Y_{k}\) sont indépendantes.
On établit alors la liste de tous les problèmes résolus dans l’ordre où ils le sont par les deux groupes. En cas de simultanéité temporelle de la résolution par les deux groupes d’un de leurs problèmes, on placera d’abord le problème résolu par \(A\) dans la liste puis celui résolu par \(B\).
Pour tout \(n \in \mathbb{N}^{*}\), on note \(U_{n}\) la variable aléatoire de Bernoulli associée à l’événement « le \(n\)-ème problème placé dans la liste est un problème résolu par le groupe \(A\) ».
Par exemple, si la liste des cinq premiers problèmes résolus est \(\left(P_{1}, P_{2}, Q_{1}, P_{3}, Q_{2}\right)\) alors \(U_{1}=1\), \(U_{2}=1,~U_{3}=0,~U_{4}=1 \text { et } U_{5}=0\).
Pour tout \(n \geqslant 0,\) on note aussi \(S_{n}\) la variable aléatoire donnant le nombre de problèmes qui ont été résolus par \(A\) présents dans la liste des \(n\) premiers problèmes résolus. En particulier, \(S_{0}\) vaut toujours 0.
Que représente la variable aléatoire \(\displaystyle \sum_{k=1}^{n} X_{k}\) ?
On suppose que \(X_{1}=5, X_{2}=2,~X_{3}=3,~X_{4}=2,~Y_{1}=2,~Y_{2}=2,~Y_{3}=4,~Y_{4}=2\). Déterminer \(U_{1}, \ldots, U_{7}\). Peut-on aussi en déduire la valeur de \(U_{8}\) ?
Compléter le script Python suivant pour
qu’il simule le jeu et, pour \(n, p\)
donnés, affiche la liste des valeurs \(U_{1},
U_{2}, \ldots, U_{n}\) :
import numpy.random as rd
import numpy as np
p=float(eval(input("p=")))
n=int(input("n="))
q=1-p
U=np.zeros(n)
sommeX=rd.exponential(1/p)
sommeY=rd.exponential(1/q)
mini=np.min([sommeX,sommeY])
for k in range(n):
if sommeX==..........
U[k]=............
sommeX=..........
else:
sommeY=..........
mini=np.min([sommeX,sommeY])
print(...................)Quelle(s) instruction(s) faut-il ajouter pour afficher la valeur de \(S_{n}\) ?
Loi de \(U_{n}\).
Dans cette question, on démontre par récurrence sur \(n \geqslant 1\) que \(\mathbb P(U_{n}=1)=p\).
Montrer que \(\mathbb{P}( U_{1}=1 )=\mathbb{P}( X_{1} \leqslant Y_{1} )=p\).
Montrer que, pour tout réel \(x<0\) : \(\mathbb{P}_{\left[U_{1}=1\right]} ( Y_{1}-X_{1} \leqslant x )=0\).
Soit \(x\) un réel positif ou nul. Établir : \(\mathbb{P}_{[U_1=1]} ( Y_{1}-X_{1} \leqslant x )=\dfrac{1}{p} \, \mathbb{P}( X_{1} \leqslant Y_{1} \leqslant X_{1}+x)\), puis calculer \(\mathbb{P}_{[ U_{1}=1]} ( Y_{1}-X_{1} \leqslant x )\).
On peut interpréter ce résultat en disant que la loi conditionnelle de \(Y_{1}-X_{1}\) sachant \(\left[U_{1}=1\right]\) est une loi exponentielle. Quel est son paramètre?
Par analogie, quelle est la loi conditionnelle de \(X_{1}-Y_{1}\) sachant \(\left[U_{1}=0\right]\) ? (on n’attend pas une démonstration précise mais un argument de bon sens pour justifier le résultat proposé)
On suppose que \(n \in \mathbb{N}^{*}\) et \(\mathbb{P}( U_{n}=1 )=p\).
Déduire de cette hypothèse et de la question précédente que \(\mathbb{P}_{\left[U_{1}=1\right]} ( U_{n+1}=1 )=p\) et \(\mathbb{P}_{\left[U_{1}=0\right]} ( U_{n+1}=1 )=p\).
Conclure.
On montrerait aussi par récurrence, et nous l’admettrons, que pour tout \(n \in \mathbb{N}^{*},\) les variables aléatoires \(U_{1}, \ldots, U_{n}\) sont mutuellement indépendantes.
En déduire la loi de \(S_{n}\).
Soit \(r \in \mathbb{N}\), on s’intéresse, dans les questions qui suivent, à la probabilité \(a_{r}\) de l’événement \(A_{r}\) : « il existe un \(n \geqslant r\) tel que, lorsque \(n\) problèmes en tout ont été résolus, le groupe \(A\) en a résolu \(r\) de plus que le groupe \(B\) ».
Justifier que \(a_{0}=1\).
Montrer que pour tout \(r \geqslant 1\), \(\mathbb{P}_{\left[U_{1}=1\right]} (A_{r} )= \mathbb{P}(A_{r-1})\) et \(\mathbb{P}_{\left[U_{1}=0\right]} (A_{r} )=\mathbb{P}(A_{r+1} )\).
En déduire que pour tout \(r \geqslant 1\) : \(a_{r+1}=\dfrac{1}{q} \,a_{r}-\dfrac{p}{q} \,a_{r-1}\).
En remarquant que \(1-4 p q=(1-2 p)^{2},\) donner une expression de \(a_{r}\) en fonction de \(p, q, r\) et de deux constantes que l’on introduira.
Le cas \(p \geqslant \frac{1}{2}\). Montrer que, dans les cas \(p=\frac{1}{2}\) et \(p>\frac{1}{2},\) la suite \(\left(a_{r}\right)_{r \in \mathbb{N}}\) est constante et égale a 1.
Le cas \(p<\frac{1}{2}\).
Soit \(k\) un entier naturel.
Établir: \(A_{2 k}=\displaystyle \bigcup_{i\geqslant k}\left[S_{2 i}=i+k\right]\).
Montrer que pour tout \(i \geqslant k,\) on a \(\displaystyle \mathbb{P}( S_{2 i}=i+k )=\binom{2 i}{i+k} p^{i+k} q^{i-k}\).
Après avoir donné la valeur de la somme \(\displaystyle \sum_{j=0}^{2 i}\binom{2i}j\), montrer que : \[\forall i \geqslant k, \ \binom{2i}{i+k} \leqslant 4^{i}\]
En déduire l’inégalité: \[\sum_{i=k}^{+\infty} \mathbb{P}( S_{2 i}=k+i ) \leqslant \left(\dfrac{p}{q}\right)^{k} \frac{(4 p q)^{k}}{1-4 p q}\]
Montrer en utilisant l’inégalité de Boole (voir question ???) que si \(p<\frac{1}{2},\) alors \(\displaystyle \lim _{k \to +\infty} a_{2 k}=0\).
Conclure en utilisant la question 10d que si \(p<\frac{1}{2},\) alors, pour tout entier naturel \(r\) : \(a_{r}=\left(\dfrac{p}{q}\right)^{r}\).
On a ainsi établi dans les questions ??? et ??? : \[\forall r \in \mathbb{N}, \ a_{r}= \begin{cases} \left(\dfrac{p}{q}\right)^{r} & \text { si } p<\dfrac{1}{2} \\ \hfill 1 \hfill & \text { si } p \geqslant \dfrac{1}{2} \rule[0pt]{0pt}{20pt} \end{cases}\] Ce résultat pourra être admis et utilisé dans le suite du sujet.
On utilise, dans cette partie, les notations et résultats de la partie II.
Soit \(n\) un entier supérieur ou égal 1.
La blockchain est formée d’une suite de blocs, chacun associé à plusieurs transactions. Elle contient l’historique de toutes les transactions effectuées depuis la création du bitcoin.
Avant d’être placé dans la blockchain, un nouveau bloc doit être validé. Cette validation nécessite la mise en œuvre d’une grande puissance de calcul pour résoudre un problème dépendant fortement du contenu du bloc et des blocs qui le précèdent.
Les individus qui valident les blocs sont appelés mineurs.
Il est possible qu’à un instant donné, coexistent sur le réseau deux blockchains, valides et différentes. Dans ce cas, le réseau choisira celle qui comporte le plus de blocs et l’autre sera abandonnée.
Par prudence, lorsqu’un bloc est validé, il est recommandé d’attendre que les \(n-1\) blocs suivants soient aussi validés pour considérer que les transactions incluses dans le bloc sont honnêtes.
Un groupe de mineurs mal intentionnés, noté \(A\), peut essayer de dépenser deux fois les mêmes bitcoins en procédant ainsi :
Le groupe \(A\) demande la validation de l’achat d’un bien d’un montant de \(s\) bitcoins qu’il a en sa possession.
Lorsque le bloc \(K\) incluant cette transaction est proposé à la validation sur le réseau, \(A\) modifie ce bloc en \(K'\), qu’il ne diffuse pas, en remplaçant l’achat par une vente des \(s\) bitcoins en euros a son profit par exemple. Il se met alors à la validation de ce nouveau bloc et crée ainsi une deuxième instance de la blockchain qu’il continue à développer sans la diffuser.
Lorsque le groupe \(B\), représentant l’ensemble des autres mineurs du réseau, a validé \(K\) ainsi que les \(n-1\) blocs suivants, le vendeur du bien considère que la transaction est valide et fournit le bien.
Le groupe \(A\) attend alors d’avoir une blockchain plus longue que celle de \(B\), qui est publique, pour la diffuser donc invalider la blockchain publique et l’achat du bien. Le crédit en bitcoins du vendeur du bien est alors annulé.
On reprend et on complète la modélisation de la partie précédente pour déterminer la probabilité que la stratégie de la double dépense réussisse et le choix de \(n\) pour que cette probabilité soit faible.
Une première phase du jeu, décrit dans la partie II, s’achève a l’instant aléatoire \(t\) où le problème \(Q_{n}\) est ajouté à la liste des problèmes résolus.
Le groupe de mineurs \(A\) est ensuite déclaré vainqueur s’il se trouve un instant \(t' \geqslant t\) où le nombre de problèmes résolus par \(A\) dans la liste des problèmes résolus depuis le début du jeu, est strictement supérieur au nombre de ceux résolus par \(B\) dans cette même liste. On note \(G_{n}\) cet événement.
On détermine, dans cette partie, la probabilité de \(G_{n}\) en fonction de \(n\) et de \(p\).
On s’intéresse tout d’abord à la loi de la variable aléatoire \(T_{n}\) égale au nombre de problèmes résolus par le groupe \(A\) lorsque l’on place \(Q_{n}\) dans la liste des problèmes résolus.
Montrer que, pour tout \(k \in \mathbb{N}\) : \(\left[T_{n}=k\right]=\left[S_{n+k-1}=k\right] \cap\left[U_{n+k}=0\right]\).
En déduire que, pour tout \(k \in \mathbb{N}\) : \(\displaystyle \mathbb{P}( T_{n}=k )=\binom{n+k-1}k p^{k} q^{n}\).
En utilisant la formule des probabilités totales, établir: \[\mathbb{P}(G_{n} )=\mathbb{P}( T_{n} \geqslant n+1 )+\sum_{k=0}^{n} \mathbb{P}( T_{n}=k ) \, a_{n+1-k}\]
Dans le cas où \(p \geqslant \frac{1}{2},\) en déduire que \(\mathbb{P}(G_{n} )=1\).
De même lorsque \(p<\frac{1}{2},\) montrer que: \[\mathbb{P}( G_{n} )=1-\sum_{k=0}^{n}\binom{n+k-1}k \, (p^{k} q^{n}-p^{n+1} q^{k-1} )\]
Une meilleure expression de \(\mathbb{P}(G_n)\) lorsque \(p<\frac{1}{2}\).
Pour tout \(x \in[0,1]\) et \(n \in \mathbb{N}^{*},\) on pose : \[u_{n}(x)=(1-x)^{n} \sum_{k=0}^{n}\binom{n+k-1}k x^{k}\]
Vérifier que pour tout \(n \in \mathbb{N}^{*}: \mathbb{P}(G_n)=1-u_{n}(p)+\dfrac{p}{q} \, u_{n}(q)\).
Pour tout \(x \in[0,1]\) et \(n \in \mathbb{N}^{*},\) établir la relation: \[u_{n+1}(x)=u_{n}(x)+(1-x)^{n} x^{n+1}\left[ \binom{2 n}{n+1}-\binom{2 n+1}{n+1} x \right]\]
En déduire que pour tout \(n \in \mathbb{N}^{*}: \mathbb{P}\left(G_{n+1}\right)=\mathbb{P}(G_n)-\left(1-\dfrac{p}{q}\right)(p q)^{n+1}\displaystyle \binom{2 n+1}{n+1}\).
Montrer par récurrence, que pour tout \(n \in \mathbb{N}^{*}\) : \[\mathbb{P}(G_n)=\dfrac{p}{q}-\left(1-\dfrac{p}{q}\right) \sum_{k=1}^{n}\binom{2 k-1}k(p q)^{k}\]
Application à la sécurisation des transactions.
Connaissant \(p<\frac{1}{2},\) on cherche a limiter le risque que la stratégie mise en place par le groupe de mineurs \(A\) réussisse.
Après avoir établi la formule \(\displaystyle \binom nk
=\dfrac{n}{k}\binom{n-1}{k-1}\) lorsque \(k \in \left[\kern-0.15em\left[ {1,n}
\right]\kern-0.15em\right]\), écrire une fonction en langage
Python qui calcule les coefficients
binomiaux.
Écrire un script Python qui détermine
\(n_{p}\), le plus petit entier \(n\) tel que \(\mathbb{P}(G_n) \leqslant \varepsilon\)
pour \(p<\frac{1}{2}\) et \(\varepsilon>0\) saisis au clavier par
l’utilisateur.
\(\mathrm{NB}:\) Pour \(\varepsilon=10^{-4}=0,1\) et \(p\) variant entre 10% et 32%, on obtient pour la représentation de \(n_{p}\) en fonction de \(p\) :
Le corrigé pas à pas, les aides et les explications sont disponibles dans la plateforme.