La présentation, la lisibilité, l'orthographe, la qualité de la rédaction, la clarté et la précision des raisonnements entreront pour une part importante dans l'appréciation des copies.
Les candidats sont invités à encadrer dans la mesure du possible les résultats de leurs calculs.
Aucun document n'est autorisé. L'utilisation de toute calculatrice et de tout matériel électronique est interdite. Seule l'utilisation d'une règle graduée est autorisée.
Si au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur d'énoncé, il la signalera sur sa copie et poursuivra sa composition en expliquant les raisons des initiatives qu'il sera amené à prendre.
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.
Partie I - Deux résultats généraux
On démontre dans cette partie deux résultats préliminaires, aux questions 5 et 6 . Ces résultats seront utilisés dans la suite du sujet et pourront être admis.
Calcul d'une probabilité
Soit et deux variables aléatoires sur un espace probabilisé, à densité et indépendantes.
On note et les fonctions de répartition de et .
On suppose que est à valeurs positives et possède une densité dont la restriction à est continue sur cet intervalle.
Pour tout , on pose .
a) Montrer que est une fonction croissante sur qui admet une limite finie en .
b) En utilisant la suite , montrer que .
Que vaut ?
2. Soit ( ) un couple de réels positifs tels que .
a) Montrer que puis que :
b) En déduire que pour tout est dérivable en et .
c) En conclure que pour tout réel positif, .
3. Montrer que .
4. En utilisant la fonction , on montrerait de même et nous l'admettrons que :
Que peut-on en déduire pour ?
5. Application aux lois exponentielles
On suppose que et sont deux variables aléatoires indépendantes suivant des lois exponentielles de paramètres respectifs et , réels strictement positifs.
Soit un réel positif ou nul.
a) Déterminer la fonction de répartition de la variable aléatoire .
b) En déduire que pour tout ,
Inégalité de Boole
On considère une famille d'événements d'un espace probabilisé.
a) Montrer par récurrence sur que .
b) On suppose que la série converge. Montrer que :
Partie II - Une compétition entre deux groupes
Dans toute la suite du sujet, on désigne par un réel de l'intervalle ] 0,1 [ et on pose .
On modélise une compétition entre deux groupes d'individus et avec les règles suivantes :
Le groupe doit résoudre une suite de problèmes dans l'ordre des indices. Au temps , le groupe commence la résolution du problème , ce qui lui prend un temps représenté par la variable aléatoire . Une fois résolu, le groupe aborde immédiatement le problème , et on note le temps consacré à la résolution de par le groupe , et ainsi de suite.
Pour tout , on note la variable aléatoire donnant le temps consacré à la résolution du problème par le groupe .
De même, le groupe doit résoudre dans l'ordre une suite de problèmes ; la résolution du premier problème commence au temps et on note, pour tout la variable aléatoire donnant le temps consacré par le groupe à la résolution du problème .
À ce jeu est associé un espace probabilisé ( ) sur lequel sont définies les suites de variables aléatoires et , et on fait les hypothèses suivantes :
pour tout suit la loi exponentielle de paramètre , notée , et suit la loi exponentielle ;
pour tout , les variables aléatoires 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 dans la liste puis celui résolu par .
Pour tout , on note la variable aléatoire de Bernoulli associée à l'événement « le -ème problème placé dans la liste est un problème résolu par le groupe ».
Par exemple, si la liste des cinq premiers problèmes résolus est ( ) alors et .
Pour tout , on note aussi la variable aléatoire donnant le nombre de problèmes qui ont été résolus par présents dans la liste des premiers problèmes résolus. En particulier, vaut toujours 0 .
a) Que représente la variable aléatoire ?
b) On suppose que . Déterminer .
Peut-on aussi en déduire la valeur de ?
c) Compléter le script Scilab suivant pour qu'il simule le jeu et, pour donnés, affiche la liste des valeurs
p = input('p=')
n = input('n=')
q = 1-p
U = zeros(1, n)
sommeX = grand(1, 1, "exp", 1/p)
sommeY = grand(1, 1, "exp", 1/q)
mini = min(sommeX, sommeY)
for k = 1:n
if sommeX == ...
U(k) = ...
sommeX = sommeX + grand(1, 1, "exp", 1/p)
else
sommeY = ...
end
mini = min(sommeX, sommeY)
end
...
d) Quelle(s) instruction(s) faut-il ajouter pour afficher la valeur de ?
8. Loi de
Dans cette question, on démontre par récurrence sur que .
a) Montrer que .
b) i. Montrer que pour tout réel .
ii. Soit un réel positif ou nul.
Établir : , puis calculer .
c) On peut interpréter ce résultat en disant que la loi conditionnelle de sachant est une loi exponentielle. Quel est son paramètre?
Par analogie, quelle est la loi conditionnelle de sachant ? (on n'attend pas une démonstration précise mais un argument de bon sens pour justifier le résultat proposé)
d) On suppose que et .
Déduire de cette hypothèse et de la question précédente que et .
e) Conclure.
9. On montrerait aussi par récurrence, et nous l'admettrons, que pour tout , les variables aléatoires sont mutuellement indépendantes.
En déduire la loi de .
Soit , on s'intéresse, dans les questions qui suivent, à la probabilité de l'événement, : « il existe un tel que, lorsque problèmes en tout ont été résolus, le groupe en a résolu de plus que le groupe .
10. a) Justifier que .
b) Montrer que pour tout et .
c) En déduire que pour tout .
d) En remarquant que , donner une expression de en fonction de et de deux constantes que l'on introduira.
11. Le cas .
Montrer que, dans les cas et , la suite est constante et égale à 1.
12. Le cas .
a) Soit un entier naturel.
i. Établir : .
ii. Montrer que pour tout , on a .
iii. Après avoir donné la valeur de la somme , montrer que : pour tout entier .
iv. En déduire l'inégalité :
b) Montrer en utilisant l'inégalité de Boole (voir question 6) que si , alors .
c) Conclure en utilisant la question 10.d. que si , alors: pour tout entier naturel .
On a ainsi établi dans les questions 11 et 12 :
Ce résultat pourra être admis et utilisé dans le suite du sujet.
Partie III - La blockchain et la stratégie de la double dépense
On utilise, dans cette partie, les notations et résultats de la partie II.
Soit 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 blocs le suivant soient aussi validés pour considérer que les transactions incluses dans le bloc soient honnêtes.
Un groupe de mineurs mal intentionnés, noté , peut essayer de dépenser deux fois les mêmes bitcoins en procédant ainsi :
Le groupe demande la validation de l'achat d'un bien d'un montant de bitcoins qu'il a en sa possession.
Lorsque le bloc incluant cette transaction est proposé à la validation sur le réseau, modifie ce bloc en , qu'il ne diffuse pas, en remplaçant l'achat par une vente des bitcoins en euros à 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 , représentant l'ensemble des autres mineurs du réseau, a validé ainsi que les blocs suivants, le vendeur du bien considère que la transaction est valide et fournit le bien.
Le groupe attend alors d'avoir une blockchain plus longue que celle de , 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 pour que cette probabilité soit faible.
Une première phase du jeu, décrit dans la partie II, s'achève à l'instant aléatoire où le problème est ajouté à la liste des problèmes résolus.
Le groupe de mineurs est ensuite déclaré vainqueur s'il se trouve un instant où le nombre de problèmes résolus par 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 dans cette même liste. On note cet événement.
On détermine, dans cette partie, la probabilité de en fonction de et de .
13. On s'intéresse tout d'abord à la loi de la variable aléatoire égale au nombre de problèmes résolus par le groupe lorsque l'on place dans la liste des problèmes résolus.
a) Montrer que pour tout .
b) En déduire que .
14. a) En utilisant la formule des probabilités totales, établir :
b) Dans le cas où , en déduire que .
c) De même lorsque , montrer que :
Une meilleure expression de lorsque
Pour tout et , on pose :
a) Vérifier que pour tout .
b) Pour tout et , établir la relation :
c) En déduire que pour tout .
d) Montrer par récurrence, que pour tout :
Application à la sécurisation des transactions
Connaissant , on cherche à limiter le risque que la stratégie mise en place par le groupe de mineurs réussisse.
a) Après avoir établi la formule lorsque , écrire une fonction Scilab qui calcule les coefficients binomiaux.
b) Écrire un script Scilab qui détermine , le plus petit entier tel que pour et saisis au clavier par l'utilisateur.
NB : Pour et variant entre et , on obtient pour la représentation de en fonction de :
LaTeX →
Word →