# Qu'est-ce qu'on attend pour converger

Thomas Lelièvre, Quentin Bramas

► To cite this version:

Thomas Lelièvre, Quentin Bramas. Qu'est-ce qu'on attend pour converger. ALGOTEL 2025 – 27èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Jun 2025, Saint Valéry-sur-Somme, France. hal-05029380

HAL Id: hal-05029380

https://hal.science/hal-05029380v1

Submitted on 10 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# *Qu'est-ce qu'on attend pour converger*

**Thomas Lelièvre<fnref n="1" /> et Quentin Bramas<fnref n="1" />**

¹ Université de Strasbourg, ICube, CNRS

Dans les réseaux blockchain, l'apparition de fourches — ces divisions temporaires de la chaîne causées par la découverte simultanée de blocs — impacte directement la performance et la sécurité du système. Si l'on sait que des paramètres comme la latence réseau ou la taille des blocs influencent leur probabilité d'apparition, un facteur reste souvent sous-estimé : la distribution de probabilité du temps de minage des blocs. Ce travail propose une analyse théorique de l'impact de cette distribution sur la probabilité d'apparition de fourches. Contrairement à Bitcoin, où le temps de minage suit une loi géométrique, certaines blockchains pourraient ajuster cette distribution et ainsi réduire la fréquence des fourches. Nous proposons une approche d'optimisation permettant d'identifier les distributions de temps de minage minimisant les fourches dans différents scénarios. Nos résultats ouvrent des perspectives pour améliorer la fiabilité des protocoles blockchain en ajustant finement leurs paramètres de consensus.

**Mots-clefs** : Blockchain, Sécurité, Fork

## **1 Introduction<fnref n="1" />**

La technologie blockchain est le mécanisme permettant le fonctionnement des cryptomonnaies en offrant un registre distribué, sécurisé et transparent. Un aspect de la performance et de la sécurité des blockchains est l'apparition de fourches (fork), où la chaîne se divise temporairement en chaînes distinctes. Les fourches résultent principalement de la découverte quasi simultanée de blocs par différents mineurs<fnref n="2" />, ce qui crée un état d'incohérence jusqu'à ce que l'une des deux chaînes devienne la plus longue et soit acceptée comme chaîne canonique résultant en la perte des blocs des chaînes concurrentes.

Bien que de nombreuses études aient exploré les divers facteurs contribuant à l'apparition de fourches, notamment les délais de propagation du réseau, la connectivité des nœuds et la taille des blocs, cet article se concentre sur une question plus spécifique. Nous étudions la probabilité de fourche résultant de la découverte quasi simultanée de blocs en fonction du nombre de mineurs dans le réseau, de la répartition de leur puissance de hachage et, de manière surprenante, de la distribution probabiliste du temps nécessaire à un mineur pour trouver un bloc. Cette étude théorique pourrait influencer la conception future des blockchains, en particulier lorsqu'une distribution personnalisée pourrait être configurée dans le protocole afin de minimiser la probabilité de fourche. Une telle personnalisation est impossible dans les blockchains PoW comme Bitcoin, mais pourrait être envisagée dans des protocoles spécifiques tels que Proof-of-Interactions [ABN21].

**Travaux existants.** Des recherches antérieures ont largement examiné la relation entre les caractéristiques des réseaux et les probabilités de fourches. Croman et al. [Cro+16] ont analysé l'évolutivité de Bitcoin et identifié que les délais de propagation du réseau sont un facteur critique augmentant les taux de fourches. Decker et Wattenhofer [DW13] ont réalisé une analyse empirique montrant qu'une propagation plus rapide des blocs réduit la probabilité de fourche, mettant en évidence l'importance de l'infrastructure réseau pour maintenir l'intégrité de la blockchain.

Des recherches ont également exploré comment la répartition de la puissance de hachage entre les mineurs impacte les occurrences de fourches. Eyal et Sirer [ES18] ont montré que la présence de pools de minage disposant d'une puissance de hachage significative peut encourager des comportements

<footnote n="1">¹Les résultats présentés ici ont été acceptés en version courte à la conférence BRAINS 2024 [LB24] et la version complète est disponible à cette url : https://hal.science/hal-04675227v1/document</footnote>

<footnote n="2">²Les autres causes possibles des fourches ne sont pas considérées dans notre travail.</footnote>
stratégiques comme le « selfish mining », qui exacerbent les occurrences de fourches en retardant intentionnellement la propagation des blocs. Zhang et Preneel [ZP17] ont par ailleurs analysé l'impact de l'ajustement de l'algorithme de sélection de branches pour réduire le risque de « selfish mining ». Ces travaux diffèrent de notre étude, car nous nous concentrons sur l'impact de la distribution du temps de minage sur les fourches légitimes, même lorsque tous les nœuds sont honnêtes.

Yahya et al. [SZT19] ont présenté un cadre théorique majeur pour analyser la probabilité de fourche dans les réseaux blockchain. Ils ont développé un modèle mathématique permettant de prédire la probabilité de fourche en considérant l'interaction entre les délais de propagation des blocs et la concurrence entre mineurs. Leur modèle traite les arrivées de blocs comme un processus de Poisson et utilise des méthodes stochastiques pour estimer la probabilité de fourche en fonction de la latence réseau et du taux de découverte des blocs. Cependant, ce travail ne considère pas comment les variations dans les distributions des temps de minage affectent la probabilité de découvertes simultanées de blocs.

**Contributions.** Cet article apporte trois contributions clés : (1) Nous présentons un modèle formel pour analyser comment les distributions des temps de minage (BMT) affectent la probabilité de fourche. (2) Nous développons une approche d'optimisation pour identifier les distributions BMT minimisant les occurrences de fourches. (3) Nous fournissons des perspectives pouvant guider la conception de proto-coles blockchain afin d'améliorer la fiabilité du consensus et les performances du réseau.

## 2 Modèle

**Temps de minage des blocs.** Soit un ensemble $\mathcal{U} = \{u_i\}_{i \in [1,n]}$ composé de $n$ nœuds connectés les uns les autres et cherchant simultanément le prochain bloc. Le temps nécessaire au nœud $u_i$ pour trouver le prochain bloc est une variable aléatoire positive $X_i$ suivant une loi de probabilité $D_i$. On suppose les variables $X_i$ indépendantes. Les distributions $D_i$ dépendent de l'algorithme de consensus choisi. Dans le cas d'une blockchain, comme le Bitcoin, utilisant la preuve de travail, la distribution $D_i$ dépendra de la puissance de calcul du nœud. Et dans le cas d'une blockchain utilisant la preuve d'enjeux $D_i$ dépendra de la quantité d'argent mis en jeu.

**Temps inter-bloc.** Certaines blockchains comme le Bitcoin ajustent leur algorithme tel que le temps moyen entre deux blocs est une valeur m fixe (10 minutes dans le cas du Bitcoin). Formellement, soit $X_{(i)}$ le temps de création du i-ème bloc parmi les $n$ nœuds, aussi appelée statistique d'ordre de rang $i$, en particulier $X_{(1)} = \min_{i \in [1,n]} X_i$. Par hypothèse, $X_{(1)} = m$.

**Probabilité de fourche.** Dans cet article, nous considérons que la probabilité qu'un fourche advienne est inversement proportionnelle à la différence de temps entre la création du premier et du second bloc. Comme nous cherchons à minimiser la probabilité de fourche, nous cherchons une distribution qui maximise l'espérance de la différence entre les temps de minage du premier et du second bloc. Nous nommerons cette différence *premier intervalle*, que l'on notera $Y = X_{(2)} - X_{(1)}$.

Pour calculer la valeur $Y$, nous utilisons la proposition suivante dont on peut trouver une démonstration dans [DN03].

**Proposition 1** Soit $X_1, \dots, X_n$ une suite de variables aléatoires indépendantes identiquement distribuées sur un espace de probabilité $(\Omega, \mathcal{A}, \mathbb{P})$. On considère également la statistique d'ordre $X_{(1)}, \dots, X_{(n)}$. Alors la fonction de répartition $F_{X_{(r)}}$ associé à $X_{(r)}, r = 1, \dots, n$ est donnée par

$$ \forall r \in \{1, \dots, n\}, F_{X_{(r)}} = \sum_{k=r}^{n} \binom{n}{k} F_X^k (1 - F_X)^{n-k} $$

On se place à présent dans la cadre où les $X_i$ suivent tous une même loi $D$ de probabilité discrète à valeur dans un intervalle borné $[0, T]$ et on note $p_k$ la probabilité d'obtenir un temps $k \in [0, T]$. Sous l'hypothèse que les variables $X_i$ admettent une espérance, la variable $Y$ admet également une espérance donnée par :
$$
\begin{align*}
\mathbb{E}(Y) &= \mathbb{E}(X_{(2)}) - \mathbb{E}(X_{(1)}) \\
&= \sum_{k=0}^{T-1} \left( \sum_{i=1}^{n} \binom{n}{i} F_X^i(k) (1-F_X(k))^{n-1} - \sum_{i=2}^{n} \binom{n}{i} F_X^i(k) (1-F_X(k))^{n-1} \right) \\
&= \sum_{k=0}^{T-1} n F_X(k) (1-F_X(k))^{n-1} \\
&= \sum_{k=1}^{T-1} n \left( \sum_{i=0}^{k} p_i \right) \left( 1 - \sum_{i=0}^{k} p_i \right)^{n-1}
\end{align*}
$$

3 Problème d'optimisation et solution

Posons la fonction $J : [0, 1]^{T+1} \rightarrow \mathbb{R}$ définie par

$$
J(p) = n \sum_{k=0}^{T-1} S_k(p) (1 - S_k(p))^{n-1}
$$

où $S_k(p) = \sum_{i=0}^{k} p_i$. Ainsi le problème d'optimisation que l'on cherche à résoudre est donné par

$$
(\mathcal{P}) : \argmax_{p \in [0,1]^{T+1}} J(p) \quad \text{tel que} \quad \sum_{i=0}^{T} p_i = 1 \quad \text{et} \quad \mathbb{E}(X_{(1)}) = \mathbf{m} .
$$

On peut montrer que le problème $(\mathcal{P})$ possède une solution unique $\bar{p} = (\frac{1}{n}, 0, \dots, 0, 1 - \frac{1}{n})$ lorsque :

$$
T = \left(1 - \frac{1}{n}\right)^{-n} \mathbf{m}
$$

Si on se restreint aux distributions de Bernoulli, on peut définir pour un entier positif $T$ quelconque représentant la durée maximale pour trouver un bloc, la distribution de Bernoulli échelonnée $D$ telle que $P(X_i = 0) = 1 - p$ et $P(X_i = T) = p$, avec $p = (\frac{m}{T})^{\frac{1}{n}}$. Dans ce cas, $D$ vérifie bien les contraintes du problème et nous pouvons facilement calculer le premier intervalle en remarquant que cet intervalle est nul sauf s'il existe exactement un nœud $i$ tel que $X_i = 0$. Par conséquent :

$$
E(Y) = T \mathbb{P} \left( \bigcup_{i=1}^{n} \left( [X_i = 0] \cap \bigcap_{\substack{j \in [1,n] \\ j \neq i}} [X_j = 1] \right) \right) = T n (1-p) p^{n-1}
$$

Ainsi, lorsque $n$ tend vers l'infini, $\mathbb{E}(Y)$ tend vers $\mathbf{m} \log(\frac{T}{m})$. Il est donc possible de choisir $T$ suffisamment grand pour que l'espérance du premier intervalle soit arbitrairement grande.

4 Distributions non identiques

Nous considérons maintenant un scénario plus général où la distribution des participants peut différer.
Chaque participant est associé à un poids constant dans le système, même si ce participant crée plusieurs
identités virtuelles, à condition que la somme de leurs poids reste identique. Ce principe est visible dans
Bitcoin, où la distribution de la puissance de calcul entre plusieurs identités ne modifie ni le temps de
découverte du bloc ni sa distribution.

Supposons que le nœud *i* possède un poids $W_i \in \mathbb{N} \setminus \{0\}$. La propriété précédente peut être obtenue en considérant que le nœud *i* effectue $W_i$ essais suivant une distribution de base $\mathcal{D}$ (celle d'un nœud avec un poids 1) et prend le minimum parmi les valeurs obtenues. Formellement, la distribution du temps de minage de bloc pour le nœud *i* est donnée par :

$$
X_i = \min\left( (X^j)_{j \in [1, W_i]} \right)
$$

où $(X^j)_{j \in [1, W_i]}$ sont des variables aléatoires indépendantes et identiquement distribuées suivant la distri-
bution $\mathcal{D}$. Dans ce contexte, la distribution de chaque participant diffère de la distribution de base $\mathcal{D}$. Par
exemple, si $\mathcal{D}$ est une distribution Bernoulli échelonnée par $T$ avec un paramètre $p$, la distribution du nœud $i$ est également une Bernoulli échelonnée par $T$ mais avec un paramètre $p^{W_i}$. Cela implique que nous retrouvons la même propriété que dans le cas simple : en choisissant $T$ suffisamment grand, il est possible d'obtenir un premier intervalle attendu arbitrairement grand.

La contrainte sur la valeur attendue du minimum $E(X_{(1)}) = m$ permet de déterminer la valeur de $p$ dans la distribution de base $\mathcal{D}$, où $W = \sum_{i=0}^{n-1} W_i$ :

$$E(X_{(1)}) = T p^W = m \Rightarrow p = \left(\frac{m}{T}\right)^{\frac{1}{W}}$$

**Comparaison avec Bitcoin.** Dans le cas de Bitcoin, la distribution de BMT pour un participant suit une distribution géométrique, dont le paramètre dépend de la puissance de hachage $W_i$ du nœud. Comme dans notre cas, cette distribution est équivalente au minimum de $W_i$ distributions géométriques indépendantes, chacune avec un paramètre 1. En effet, cela équivaut à supposer que le participant effectue chaque hachage à la même vitesse, mais réalise simplement $W_i$ hachages en parallèle.

Dans ce cas, la difficulté est définie de sorte que le minimum parmi toutes les $W = \sum_{i=0}^{n-1} W_i$ variables aléatoires suivant une distribution géométrique de base soit une distribution géométrique avec un paramètre $\frac{1}{m}$. La distribution de base $\mathcal{D}$ dans Bitcoin est donc une distribution géométrique avec un paramètre :

$$p = 1 - \left(\frac{m-1}{m}\right)^{\frac{1}{W}}$$

La variable aléatoire $X_i$ d'un nœud ayant une puissance de hachage $W_i$ suit une distribution géométrique de paramètre $1 - (1-p)^{W_i}$.

Bien que la manière dont la puissance de hachage est répartie parmi les nœuds n'ait aucun impact sur la distribution de base utilisée, elle influence considérablement le premier intervalle et la probabilité de fourche. Plus la répartition est importante, plus la probabilité de fourche augmente. Pour visualiser ce comportement, nous avons simulé un réseau de 100 nœuds où la puissance de hachage est distribuée selon une distribution de Zipf, avec un paramètre allant de 0, 01 à 10. Lorsque le paramètre de Zipf est très faible, la puissance de hachage est uniformément répartie, ce qui constitue le pire cas, car chaque nœud a la même distribution BMT. Dans ce cas, l'espérance du premier intervalle est inférieure à 10 minutes en moyenne (ce qui est déjà assez élevé). Lorsque quelques nœuds concentrent presque toute la puissance de hachage (paramètre de Zipf élevé), le premier intervalle atteint une valeur encore meilleure dépassant les 100 minutes (les unités choisies ici correspondent au fait que $m = 10$ minutes).

Pour finir, rappelons qu'avec notre distribution de Bernoulli, même dans la pire répartition des poids, c'est-à-dire, dans le cas où $W$ nœuds ont un poids de 1, nous pouvons choisir $T$ de manière à avoir une espérance du premier intervalle arbitrairement grande.

# 5 Conclusion et Discussion

Dans cet article, nous avons étudié comment la distribution du temps de minage (BMT) impacte la probabilité de fourche dans les réseaux blockchain. Notre analyse, basée sur un modèle formel, a révélé que des distributions BMT personnalisées peuvent significativement réduire les occurrences de fourches en augmentant la différence de temps entre la découverte du premier et du second bloc. Ces résultats suggèrent que l'optimisation des distributions BMT pourrait améliorer les mécanismes de consensus des blockchains, conduisant à de meilleures performances et une sécurité accrue du réseau.

Cependant, la modélisation de la probabilité de fourche utilisée ici (comme proportionnelle à l'espérance du premier intervalle) n'est pas réaliste et conduit à une solution qui ne fonctionnerait pas en pratique. En effet, le temps de moyen de résolution d'un fourche peut dans notre cas être absurdement grand. Les travaux futurs se concentreront donc sur l'extension de ses résultats dans un formalisme plus réaliste. D'autres recherches futures pourraient aussi explorer les implémentations pratiques de ces résultats, car les distributions BMT ne peuvent généralement pas être personnalisées, sauf dans des protocoles spécifiques comme Proof-of-Interactions.
Bibliographie

[LB24] T. Lelièvre et Q. Bramas, « The impact of block mining time distribution on the probability of forks », in *6th Conference on Blockchain Research & Applications for Innovative Networks and Services*, BRAINS 2024, Berlin, Germany, October 9-11, 2024, IEEE, 2024, p. 1-4. doi: 10.1109/BRAINS63024.2024.10732759.

[ABN21] J.-P. Abegg, Q. Bramas, et T. Noël, « Blockchain Using Proof-of-Interaction », in *Networked Systems: 9th International Conference, NETYS 2021, Virtual Event, May 19-21, 2021, Proceedings*, 2021, p. 129-143.

[Cro+16] K. Croman et al., « On Scaling Decentralized Blockchains: (A Position Paper) », in *International conference on financial cryptography and data security*, 2016, p. 106-125.

[DW13] C. Decker et R. Wattenhofer, « Information propagation in the bitcoin network », in *IEEE P2P 2013 Proceedings*, 2013, p. 1-10.

[ES18] I. Eyal et E. G. Sirer, « Majority is not enough: Bitcoin mining is vulnerable », *Communications of the ACM*, vol. 61, n° 7, p. 95-102, 2018.

[ZP17] R. Zhang et B. Preneel, « Publish or perish: A backward-compatible defense against selfish mining in bitcoin », in *Topics in Cryptology–CT-RSA 2017: The Cryptographers’ Track at the RSA Conference 2017, San Francisco, CA, USA, February 14–17, 2017, Proceedings*, 2017, p. 277-292.

[SZT19] Y. Shahsavari, K. Zhang, et C. Talhi, « A Theoretical Model for Fork Analysis in the Bitcoin Network », in *2019 IEEE International Conference on Blockchain (Blockchain)*, 2019, p. 237-244. doi: 10.1109/Blockchain.2019.00038.

[DN03] H. A. David et H. N. Nagaraja, *Order statistics*, 3rd ed. Hoboken (N.J.): John Wiley, 2003.