# Pointer Networks with Q-Learning for OP Combinatorial Optimization

Alessandro Barro<EMAIL_ADDRESS>
Politecnico di Milano,
Piazza Leonardo da Vinci 32, Milan 20133 IT

###### Abstract

The Orienteering Problem (OP) presents a unique challenge in combinatorial
optimization, emphasized by its widespread use in logistics, delivery, and
transportation planning. Given the NP-hard nature of OP, obtaining optimal
solutions is inherently complex. While Pointer Networks (Ptr-Nets) have
exhibited prowess in various combinatorial tasks, their performance in the
context of OP leaves room for improvement. Recognizing the potency of
Q-learning, especially when paired with deep neural structures, this research
unveils the Pointer Q-Network (PQN). This innovative method combines Ptr-Nets
and Q-learning, effectively addressing the specific challenges presented by
OP. We deeply explore the architecture and efficiency of PQN, showcasing its
superior capability in managing OP situations.

##  1 Introduction

###  1.1 Motivation

The Orienteering Problem (OP) holds significance in combinatorial
optimization, notable for its applications in logistics, sightseeing, and
location-based tasks. Its NP-hard nature underscores the difficulty in
securing optimal solutions for expansive OP instances. While Ptr-Nets alone or
integrated with actor-critic frameworks like Hierarchical RL have been
effective for problems like TSP, there’s a noticeable gap when it comes to OP.
In such situations, the focused nature of critic-only methods, which center on
value estimation, can be particularly advantageous. These approaches can
potentially offer more stable learning in environments riddled with sparse
rewards or where policy fluctuations might be disruptive. With these
considerations, we introduce the Pointer Q-Network (PQN)—a blend of Ptr-Nets
and Q-learning. While not crafted exclusively for OP, PQN demonstrates a
marked improvement in handling OP tasks compared to the mentioned approaches.
The subsequent sections will detail PQN’s architecture and its proficiency in
managing the intricacies of OP.

###  1.2 Contribution

Amid rising real-world challenges, scalable methods that maintain solution
quality are essential. Enter Pointer Networks (Ptr-Nets), which revolutionized
sequence-to-sequence modeling for combinatorial problems using deep learning
[Vinyals et al., 2015]. Concurrently, Q-learning’s capabilities, amplified by
deep architectures in Deep Q-Networks (DQN) [Mnih et al., 2015], heralded new
avenues for innovation. Innovations like S2V-DQN and ECO-DQN blended graph
embeddings with reinforcement learning for enhanced combinatorial
optimization. Furthermore, merging Ptr-Nets with Hierarchical RL [Qiang Ma et
al. 2019] showcased their potency in this domain. Collectively, these
advancements highlight deep learning’s adaptability and the continuous
evolution in optimization techniques.

##  2 Background and problem formulation

In this section, we delve into the technical intricacies of the Orienteering
Problem (OP) and investigate its interplay with Markov Decision Processes
(MDP). A precise and adept integration between these two paradigms is pivotal,
as it establishes the sequence that determines affinity with the proposed
system, PQN.

###  2.1 Orienteering Problem (OP)

Definitions The OP is a combinatorial optimization problem which entails
identifying a route that initiates from a specified starting vertex,
potentially traverses through a subset of accessible vertices, and aims to
maximize the accrued prize, all while not exceeding a given budget (or time
constraint). The problem can be described formally using the tuple
$\mathcal{O}=\langle\mathcal{V},\mathcal{E},p,c,B,s,t\rangle$, where
$\mathcal{V}$ signifies the set of vertices $v$, which includes the starting
and potential end points; $\mathcal{E}$ represents the set of edges $e$ or
connections between the vertices; $p:\mathcal{V}\rightarrow\mathbb{R}^{+}$ is
the prize function that associates each vertex with a non-negative prize
value; $c:\mathcal{E}\rightarrow\mathbb{R}^{+}$ stands for the cost function,
attributing a non-negative cost to each edge in $\mathcal{E}$; $B$ is the set
ceiling for the route in terms of budget or time; $s$ (optional) is the
designated onset vertex; and $t$ (optional) can indicate a specific ending
vertex, if the route is intended to conclude at a distinct point.

For our solution, we’ll define the decision variables as follows: $x_{ij}$ is
a binary variable that is 1 if edge $(i,j)$ is included in the chosen route
and 0 otherwise; $u_{v}$ is an auxiliary variable indicating the sequence or
position of the vertex $v$ in the route.

Our objective function, which gauges the merit of a solution via the rewards
of various routes, is:

$\max\sum_{v\in\mathcal{V}}p_{v}\cdot\delta_{v}$ (1)

Where $\delta_{v}$ is 1 if vertex $v$ is visited and 0 otherwise.

Constraints The following set of constraints is crucial to guarantee that our
solutions are viable for OP:

  * •

Route originates at vertex $s$:

$\sum_{j\in\mathcal{V}}x_{sj}=1$ (2)

  * •

Flow conservation:

$\sum_{i\in\mathcal{V}}x_{iv}-\sum_{j\in\mathcal{V}}x_{vj}=0,\quad\forall
v\in\mathcal{V}$ (3)

  * •

Travel cost must not surpass the designated maximum:

$\sum_{i\in\mathcal{V}}\sum_{j\in\mathcal{V}}c_{ij}\cdot x_{ij}\leq B$ (4)

  * •

Subtour elimination:

$u_{i}-u_{j}+|\mathcal{V}|\cdot
x_{ij}\leq|\mathcal{V}|-1,\quad\forall(i,j)\in\mathcal{E},i\neq j$ (5) $1\leq
u_{v}\leq|\mathcal{V}|,\quad\forall v\in\mathcal{V}$ (6)

  * •

Avoid revisiting a vertex:

$\sum_{i\in\mathcal{V}}x_{iv}+\sum_{j\in\mathcal{V}}x_{vj}\leq 2,\quad\forall
v\in\mathcal{V}$ (7)

  * •

Optionally, not concluding at the starting vertex:

$v_{\text{end}}\neq v_{\text{start}}$ (8)

###  2.2 Integrating OP with MDP

In a similar vein to the structure2vec (S2V) method [Khalil et al. 2018], we
embed a given graph into a vector. Instead of crafting a recursive network
directly, we utilize an MDP. Our representation is meticulously constructed,
allowing for later approximation of Q-values via a hybrid network. Details of
this will be elaborated upon in the sections to follow.

MDP The reinforcement learning agent’s playground is an environment defined as
a Markov Decision Process. In our scenario, this MDP is given by the tuple
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,R,\gamma\rangle$, where
$\mathcal{S}$ embodies the state space; $\mathcal{A}$ is the action space;
$P:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\mapsto[0,1]$ characterizes
the state transition probability function; $R:\mathcal{S}\mapsto\mathbb{R}$ is
the reward function; and $\gamma\in[0,1]$ signifies the discount factor, which
determines the present value of future rewards. Furthermore, the episode
tuple, $E=\langle s,a,r,s^{\prime}\rangle$, will prove crucial in later parts
of the text, especially when illustrating the model’s training regimen.

Embedding of OP into an MDP Drawing parallels from graph embedding and
sequence2vec, it becomes essential to recast the graph into a familiar
construct like an MDP. This reshaping paves the way for the agent’s seamless
interactions, empowering it to draw lessons effectively from every interaction
within the organized environment. The state in our defined MDP encapsulates
the ongoing status of the evolving route. The state is delineated as
$s=\langle\mathcal{R},B,\mathbf{X}\rangle$, where $\mathcal{R}$ stands for the
ongoing route, and the last vertex in $\mathcal{R}$ signifies the present
vertex $v_{\text{current}}$. The term $B$ denotes the outstanding budget,
while $\mathbf{X}$ is a binary indicator vector. Here, $X_{i}=1$ if vertex
$v_{i}$ is already visited and $0$ otherwise. Every action $a$ in our MDP is
analogous to choosing a vertex $v$. Formally, the action space $\mathcal{A}$
is captured as $\mathcal{A}(s)=\\{a:v|v\in V\land X_{v}=0\\}$, ensuring only
unvisited vertices emerge as valid actions for any existing state. Transition
dynamics encapsulate the potential of migrating from a state to another in
light of a particular action. Given OP’s deterministic characteristic, our
transitions are deterministic. Thus, $P(s^{\prime}|s,a)=1$ if a new state
emerges by picking a vertex, and $P(s^{\prime}|s,a)=0$ otherwise. The reward
function gauges the gain from executing an action from a particular state to
reach a new one. The reward is deduced from the prize of the accessed vertex,
and can be mathematically portrayed as $R(s,a,s^{\prime})=p_{a}$, where
$p_{a}$ is the prize associated with vertex $a$. Embedding the OP into MDP
ensures a systematic framework for our problem, enabling its resolution via
reinforcement learning techniques.

##  3 Proposed approach

In the sections ahead, we will delve into the intricacies of constructing the
PQN system. We aim to illuminate the synergistic blend of Ptr-Nets and
Q-learning function approximation, furnishing comprehensive explanations
complemented by practical model visualizations.

###  3.1 Critic-Only Reinforcement Learning

Reinforcement learning (RL) techniques are primarily divided into two main
categories: Actor-only and Critic-only methods. The Actor-only approach has
seen the application of Ptr-Nets (in combinatorial optimization landscapes) by
leveraging the capabilities of Hierarchical Reinforcement Learning [Qiang Ma
et al. 2019], directly deriving and optimizing the policy. Our research is
centered on the Critic-only methods, which revolve around the concepts of
Value and Q-value.

At its core, the Value function, $V^{\pi}(s)$, represents the expected reward
when starting in state $s$ and following a specific policy $\pi$. In contrast,
the Q-value function $Q^{\pi}(s,a)$, builds upon this concept by considering
the action taken. The underlying principle of Critic-only methods is based on
the Bellman equation Definitions and proofs.

For the purpose of integration with the Ptr-Net framework, it is imperative to
delineate the primary strengths and shortcomings of both proposed models.
Understanding these nuances is pivotal, as they will influence later deepened
design decisions.

Tabular Q-Learning This is indeed a model-free reinforcement learning
technique that stores Q-values for every state-action pair in a
straightforward table. It employs simplicity, iteratively updating Q-values
using the Bellman equation. The Temporal Difference (TD) error, $\delta$,
represents the gap between the newly observed Q-value and the existing
estimate. Specifically, $\delta=Q(s^{\prime},a^{\prime})-Q(s,a)$. By
continuously refining Q-values based on this TD error, tabular Q-learning is
guaranteed to converge to the optimal policy in deterministic settings
Definitions and proofs.

Strengths

  * •

Transparency: The tabular approach offers a clear and interpretable
representation of Q-values.

  * •

Convergence: As previously mentioned, given enough time and a suitable policy,
tabular Q-learning is guaranteed to converge to the optimal Q-values.

  * •

Simplicity: Without the complexities of neural networks, it’s straightforward
to implement and understand.

Weaknesses

  * •

Scalability: The method struggles with large state and action spaces due to
the need for a table entry for each state-action pair.

  * •

Generalization: Unlike DQNs, the tabular method cannot generalize across
states. It requires explicit exploration of each state-action pair for
learning.

Deep Q-Networks DQNs emblematically exemplify the confluence of RL and deep
learning (DL). Within the architecture of a DQN, each layer possesses its
distinctive weights that undergo training within the primary training loop.
Serving as function approximators, DQNs eclipse the traditional practice of
storing Q-values in tabular form. A salient component of the DQN framework is
the target network. Periodically, this network assimilates the Q-values from
the primary DQN to compute the target Q-value. Consequently, the Temporal
Difference (TD) error $\delta$ emerges as the difference between this target
Q-value and the Q-value derived from the optimal policy, in this way
$\delta=Q^{\text{target}}(s,a)-Q^{\pi}(s,a)$. We refresh Q-values iterating
the update rule, which indeed makes use of $\delta$ Definitions and proofs.

Strengths

  * •

Scalability: DQNs can manage high-dimensional state spaces, making them apt
for complex problems.

  * •

Generalization: They can generalize across states, meaning they don’t need to
see every state to make reasonable predictions.

  * •

Stability: With techniques like experience replay and target networks, DQNs
address the inherent instability of neural networks in reinforcement learning.

Weaknesses

  * •

Training Complexity: DQNs require significant computational resources and
time.

  * •

Hyperparameter Sensitivity: The performance of DQNs can be sensitive to the
choice of hyperparameters.

  * •

Overestimation: They have a known tendency to overestimate Q-values.

###  3.2 Merging Pointer Networks with Q-learning for OP

Overview Pointer Networks (Ptr-Nets), developed by [Vinyals et al. 2015],
represent an advancement from traditional sequence-to-sequence models as they
adeptly handle varying sequence lengths. Ptr-Nets generate variable-length
outputs by referencing positions within the input sequence. Their ability to
form sequences based on the importance of each element in the input makes them
especially suitable for optimization problems where the length of the optimal
solution may vary.

Ptr-Nets have showcased their prowess in handling combinatorial optimization
tasks like the Travelling Salesman Problem (TSP). However, in tasks such as
OPs, where the sequence length isn’t fixed and the need of capturing
relationships between nodes (reward-wise) is imperative, performance drops are
noticeable. Recognizing the complexities of such optimization problems, we
suggest blending the deterministic vertex selection of Ptr-Nets with the
probabilistic Q-value approximation of Q-Learning methods. Instead of
exclusively highlighting a single vertex, the Ptr-Net provides a permutation,
spotlighting the top $\lambda\in[1,|\mathcal{V}|]$ vertices based on attention
scores. Q-Learning then evaluates the Q-values for each state-action
combination, leading to the optimal action’s selection and consequently
building the optimal route $\pi^{*}$ until the budget is finished.

Figure 1: PQN procedure schematization

Pointing Batch Dynamics Introducing the concept of ‘pointing batch‘ denoted by
$\lambda\in\mathbb{Z^{+}}$ (which could also take positive real values in
continuous contexts), we define the number of vertices the Ptr-Net
concentrates on during each selection phase. This allows Q-learning to
evaluate these potential actions based on expected outcomes. Depending on the
value of $\lambda$, various scenarios emerge:

  * •

$\lambda=1$, the system would merely replicate the traditional approach of
pointing to the single most favorable vertex. While this might be
computationally efficient, it might not fully harness the capabilities of the
Ptr-Net, potentially leaving out other vertices that could be nearly as
favorable or even more favorable in certain situations.

  * •

$\lambda\rightarrow 1$: As $\lambda$ leans closer to 1, the problem becomes
more discrete and deterministic, but the final policy $\pi$ will likely be
suboptimal ($\pi^{-}$). Given $a=v_{\text{unvisited}}$, we can symbolically
state that:

$\lim_{\lambda\rightarrow
1}\bigg{\\{}a_{j}^{-}:\arg\max_{a^{\prime}}\sum_{a^{\prime}\in\mathcal{A^{\prime}}}Q^{\pi}(s,a^{\prime})\bigg{\\}}^{L}_{j=1}=\pi^{-}$
(9)

where
$a^{\prime}=\sum_{i=1}^{\lambda}\arg\max_{i}P(c_{i}|\mathcal{V}_{\text{unvisited}},R)e_{i}$,
$L$ is the final route length, $e\in\\{0,1\\}^{\lambda}$ the canonical basis.
In such cases, tabular Q-learning is better suited. Tabular Q-learning works
well when the action and state spaces are relatively small, allowing for a
more exhaustive exploration of the state-action pairs.

  * •

$\lambda\rightarrow\mathcal{V}$: As $\lambda$ approaches the size of
$\mathcal{V}$, the action space becomes broader and more complex. Although the
effort of calculation grows significantly, we should point out that the
resulting final route in this case will more likely converge to the optimal
one ($\pi^{*}$):

$\lim_{\lambda\rightarrow|\mathcal{V}|}\bigg{\\{}a_{j}^{*}:\arg\max_{a^{\prime}}\sum_{a^{\prime}\in\mathcal{A^{\prime}}}Q^{\pi}(s,a^{\prime})\bigg{\\}}^{L}_{j=1}=\pi^{*}$
(10)

DQNs are apt for such situations, since they can handle large action spaces
effectively.

  * •

$\lambda=|\mathcal{V}|$, the Ptr-Net would consider every possible vertex,
rendering the action space vast and computationally challenging to handle in
the Q-values estimation process by the DQN subsequently. While this approach
ensures a comprehensive assessment of all vertices, it becomes computationally
expensive and may introduce redundancy.

Building PQN The Ptr-Net design is split into an encoder $e$ and a decoder
$d$. The encoder converts the input sequence into hidden states, while the
decoder uses these hidden states to construct the output sequence. To
elucidate further, consider an input sequence $\\{s_{1},s_{2},\dots,s_{N}\\}$.
An RNN updates its hidden state $h$ iteratively, encapsulating the input
sequence’s representation:

$h_{i}=\text{tanh}(W_{e}h^{i-1}_{e,v}+W_{d}s_{i}+b_{h})$ (11)

Here $W$ and $b$ are learnable weights.

For each vertex in the set of unvisited vertices, the encoder generates a
corresponding hidden state $h_{e,v}^{i}$.

$h_{e,v}^{i}=\text{RNN}_{\text{encoder}}(v)\quad\forall
v\in\mathcal{V}_{\text{unvisited}}$ (12)

For each decoding step $t$, the decoder leverages attention over the encoder’s
hidden states to derive its hidden state

$h_{d}^{t}=\text{RNN}_{\text{decoder}}(h_{d}^{t-1},c^{t})$ (13)

The attention mechanism computes a context vector $c^{t}$:

$c^{t}=\sum_{v}\alpha^{t}_{v}h_{e,v}^{i}$ (14)

With attention weights derived from:

$\alpha^{t}_{v}=\frac{\exp(e^{t}_{v})}{\sum_{v^{\prime}}\exp(e^{t}_{v^{\prime}})}$
(15)

Here $e$ symbolizes the attention energy, which is no less than a ‘raw
attention score‘, computed as follows:

$e^{t}_{v}=(h_{t-1}^{d})^{T}\cdot h_{i}^{e,v}$ (16)

The interplay of the context vector and the current decoder state determines
the probability distribution over potential actions:

$P(c_{i}|\mathcal{V}_{\text{unvisited}},\mathcal{R})=\text{softmax}(f(h_{d}^{t},c^{t}))$
(17)

We employ a feed-forward neural network $f$ in the attention system as it
efficiently captures the non-linear relationships and interactions between the
decoder state and the context, aiding in generating precise attention scores.
The set of subsequent vertex actions, $\mathcal{A}^{\prime}$, is inferred from
this distribution:

$\mathcal{A}^{\prime}=\\{a_{i}:\arg\max_{i}P(c_{i}|\mathcal{V}_{\text{unvisited}},R)\\}_{i=1}^{\lambda}$
(18)

Where $\arg\max_{i}$ retrieves the indices corresponding to the top $\lambda$
values of the conditional probabilities, striking a balance between
computational efficiency and decision-making richness.

To finalize the process, after obtaining the set of top actions
$\mathcal{A}^{\prime}$ from the Ptr-Net, Q-learning approximates the expected
return for each action in $\mathcal{A}^{\prime}$, given the current state.
Formally, the Q-value for each action $a_{i}$ in $\mathcal{A}^{\prime}$ is
given by:

$Q(s,a_{i})=R(s^{\prime},a_{i},s)+\gamma\max_{a^{\prime}\in\mathcal{A}^{\prime}}Q(s^{\prime},a^{\prime})$
(19)

Here, $R(s^{\prime},a_{i},s)$ is the expected reward when taking action
$a_{i}$ in state $s$ and transitioning to state $s^{\prime}$. The term
$\max_{a^{\prime}\in\mathcal{A}^{\prime}}Q(s^{\prime},a^{\prime})$ denotes the
maximum Q-value over all potential subsequent actions in
$\mathcal{A}^{\prime}$, reflecting the agent’s future value estimation.

From this set of Q-values, the action $a^{*}$ with the highest Q-value is
selected as the optimal action:

$a^{*}=\arg\max_{a_{i}\in\mathcal{A}^{\prime}}Q(s,a_{i})$ (20)

Policy retrieval post termination Upon reaching the termination condition, the
agent has traversed a series of actions that form a tentative route,
potentially optimal. It is now essential to extract this policy sequence,
represented by $\pi^{*}$, to evaluate its performance concerning the problem’s
constraints and objectives. The derived policy should not only conform to the
budgetary constraints but also maximize the accrued rewards throughout the
episode. Retrieving the policy can be mathematically formulated as:

$\pi^{*}=\\{a_{j}^{*}\\}_{j=1}^{L}\quad\text{where}\quad
L=\text{dim}(\pi^{*})\quad\text{and}\quad\sum_{j=1}^{L}c_{a_{j}^{*}}\leq B$

In the above expression, $c_{a_{j}^{*}}$ represents the cost associated with
action $a_{j}^{*}$. The total cost of the derived policy $\pi^{*}$ should not
exceed the available budget $B$. This retrieval process ensures that the
extracted policy is both feasible and aligns with the agent’s learning over
the episode.

Addressing challenges The Orienteering Problem (OP) requires a delicate
balance between cost minimization and reward maximization within a set budget,
a scenario where Ptr-Nets can sometimes fall short, especially when compared
to their performance in problems like the TSP. The intricacies of OP can lead
Ptr-Nets to favor one objective over the other, potentially neglecting
rewarding paths in favor of immediate cost savings.

This is where the integration of Q-learning becomes crucial. With its inherent
capability to recognize and prioritize routes with better future rewards,
Q-learning offers a more holistic view. When coupled with Ptr-Nets, this
combination aids in capturing both immediate and long-term benefits. Adjusting
the pointing batch $\lambda$ further refines the process, allowing for optimal
scaling of computations based on the specific complexities of the problem at
hand.

The resulting Pointer Q-Networks (PQNs) effectively bridge the gap in Ptr-
Nets’ approach to OP. While Ptr-Nets point to promising actions in the
immediate state, Q-learning evaluates their future implications in terms of
both cost and rewards. In increasingly intricate OP scenarios, PQNs offer
solutions that seamlessly merge computational efficiency with a balanced
consideration of costs and rewards.

Algorithm 1 PQN Algorithm

0: Input sequence $\\{s_{1},s_{2},\dots,s_{N}\\}$

0: Pointing batch size $\lambda$

1: Initialize Pointer Network (Ptr-Net) with weights $\theta$

2: Initialize Q-function with weights $\phi$

3: while episode not terminated do

4: Encode input sequence using Ptr-Net encoder to get hidden states
$h_{e,v}^{i}$

5: for each decoding step $t$ do

6: Calculate attention scores and context vector $c^{t}$

7: Decode using context vector to get $h_{d}^{t}$

8: Calculate action probabilities
$P(c_{i}|\mathcal{V}_{\text{unvisited}},\mathcal{R})$

9: Select top $\lambda$ actions as $\mathcal{A}^{\prime}$

10: for each action $a_{i}$ in $\mathcal{A}^{\prime}$ do

11: Compute Q-value $Q(s,a_{i})$ using current episode $E$

12: end for

13: Select optimal action $a^{*}$ with highest Q-value

14: Update the state based on chosen action

15: end for

16: Update Ptr-Net and Q-function weights using respective losses

17: end while

##  4 Experiment

Our experiment focuses primarily on comparing the performances of Ptr-Net and
PQN in extracting the optimal route based on cumulative reward, while
considering various evaluation metrics.

###  4.1 Setup and Hyperparameters

We conducted experiments in two different settings, denoted as
$\mathcal{O}_{20}$ and $\mathcal{O}_{50}$, each with train, evaluation, and
test instances. In $\mathcal{O}_{20}$, we set $\mathcal{V}=20$,
$\mathcal{E}=190$, and other parameters as $p,c,B,s=0$. In $\mathcal{O}_{50}$,
we increased the complexity with $\mathcal{V}=50$, $\mathcal{E}=1225$, and the
same other parameters.

In both settings, the graphs are fully connected, resembling real-world
scenarios. The prize values $p$ are randomly chosen from the interval [0, 15],
while the cost values $c$ range from 0 to 10. The budget $B$ is calculated as
$B=\frac{\mathcal{V}}{4}(\langle p\rangle-\langle c\rangle)$, where $\langle
p\rangle$ and $\langle c\rangle$ are the average prizes and costs,
respectively. We set the sequence length $L_{s}$ equal to $|\mathcal{V}|$,
reflecting the number of vertices. The termination node $t$ remains undefined.

Both algorithms operate on the same graph to eliminate potential biases. The
aim is to study the model’s decision-making process within budget constraints.

The hyperparameters include:

  * •

$L_{s}$ (sequence length) = $|\mathcal{V}|$

  * •

RNN = LSTM Definitions and proofs

  * •

$H$ (hidden layer size) = 128

  * •

$\lambda$ (pointing batch) = $\frac{L_{s}}{2}$

  * •

$O_{s}$ (output size) = $L_{s}$, but varies due to the satisfaction of
termination conditions

  * •

$\eta$ (learning rate) = $10^{-3}$

  * •

Episodes = 20 for $\mathcal{V}=20$ and 50 for $\mathcal{V}=50$

###  4.2 Losses

In our experimental setup, we utilize distinct loss functions tailored to the
specific learning mechanisms of the Pointer Q-Network (PQN) and the Pointer
Network (Ptr-Net).

For PQN, the loss function is derived from the standard Q-learning Mean
Squared Error (MSE) loss $J$, which originates from the Bellman equation:

$J(\delta)=\sum_{a^{\prime}}\delta^{2}=\sum_{a^{\prime}}\left(Q(s,a)-\left(r+\gamma\max_{a^{\prime}}Q(s,a^{\prime})\right)\right)^{2}$
(21)

Here, $\delta$ signifies the temporal difference, capturing the discrepancy
between the current Q-value estimate $Q(s,a)$ and the expected return
$r+\gamma\max_{a^{\prime}}Q(s,a^{\prime})$. PQN’s loss formulation directly
aligns with the Q-learning framework, optimizing the Q-values through the
minimization of this MSE loss.

In contrast, Ptr-Net employs a different loss function based on Cross-Entropy
(CE) likelihood $l$ of the computed probabilities. The CE loss, $l(P||Q)$, is
computed as follows:

$l(P||Q)=-\sum_{i=1}^{N}\sum_{j=1}^{L_{s}}q_{ij}\log(p_{ij})$ (22)

Here, $P$ and $Q$ represent the probability distributions for the action
selection. $P$ is the model’s prediction, and $Q$ is the ground truth
distribution. Ptr-Net’s loss function quantifies the dissimilarity between the
predicted action probabilities and the actual action distributions.

It is essential to note that these loss functions are not directly comparable
due to their inherent differences. While PQN’s loss function aligns with
Q-learning principles and focuses on Q-value optimization, Ptr-Net’s loss
centers around probability distribution matching. Using the CE loss for PQN
backpropagation might not be suitable, as it does not fully capture the
essence of its learning process, which involves comprehensive Q-value
computation. These distinct loss functions reflect the diverse learning
strategies and objectives of PQN and Ptr-Net in addressing the Orienteering
Problem.

###  4.3 Comparison Metrics

To assess and compare the models, we utilize several metrics, including:

  * •

Cumulative reward $\mathbf{R}=\sum_{k}R_{k}$, where $k$ is a step

  * •

Average loss $\langle l\rangle$ (average CE loss), $\langle J\rangle$ (average
Q-MSE loss)

  * •

Convergence speed $t$ expressed in seconds

  * •

Action-selection distribution $\pi$ (indicating action preferences for both
models)

###  4.4 Results and Discussion

We will now present the results of our experiments and provide a comprehensive
discussion of the outcomes.

Cumulative Reward

  * •

For $\mathcal{O}_{20}$, Ptr-Net achieved a cumulative reward of
$\mathbf{R}=12$ after training and fine-tuning during evaluation, while PQN
attained a cumulative reward of $\mathbf{R}=21$.

  * •

For $\mathcal{O}_{50}$, Ptr-Net achieved a cumulative reward of
$\mathbf{R}=40$ after training and fine-tuning during evaluation, while PQN
attained a cumulative reward of $\mathbf{R}=68$.

The cumulative reward ($\mathbf{R}$) serves as a critical metric to evaluate
the performance of Ptr-Net and PQN in solving the Orienteering Problem
($\mathcal{O}$). These results indicate that PQN exhibits a more effective
decision-making process, resulting in higher cumulative rewards. A closer
examination of action sequences reveals an interesting pattern. Ptr-Net tends
to select consecutive nodes, possibly due to its limited ability to explore
non-sequential but rewarding paths. In contrast, PQN shows a less greedy
approach, recognizing the potential benefits of visiting non-sequential nodes
and ultimately achieving higher cumulative rewards.

Average Loss

In our experiments, we observed distinct patterns in the average loss values
between Ptr-Net and PQN:

  * •

For $\mathcal{O}_{20}$, Ptr-Net exhibited an average loss of $\langle
l\rangle=10.0924$, while PQN encountered an average loss of $\langle
J\rangle=59.3423$.

  * •

In the context of $\mathcal{O}_{50}$, Ptr-Net recorded an average loss of
$\langle l\rangle=32.2944$, whereas PQN grappled with an average loss of
$\langle J\rangle=132.1646$.

It is important to note that, in general, PQN’s loss might take more time to
stabilize compared to Ptr-Net. With the same number of episodes, Ptr-Net
exhibited quicker convergence to a stable loss value, indicating its ability
to adjust rapidly to the given problem settings. However, it is crucial to
acknowledge that the speed of convergence in loss values does not necessarily
correlate with the effectiveness of a model’s learning strategy. Ptr-Net’s
relatively quicker stabilization does not imply that it effectively captures
the intricate relationships between nodes within the OP. It may optimize its
policy more rapidly but potentially overlook essential nuances in the
problem’s structure. Conversely, PQN’s longer stabilization suggests a more
deliberate learning process, where the model takes the time to explore various
action sequences and evaluate their long-term implications.

Convergence Speed

  * •

For $\mathcal{O}_{20}$, Ptr-Net took $t=13.83s$ to converge, while PQN
required $t=40.01s$ for convergence.

  * •

For $\mathcal{O}_{50}$, Ptr-Net took $t=114.37s$ to converge, whereas PQN
exhibited a longer convergence time of $t=483.32s$.

This discrepancy in convergence speed can be attributed to the time complexity
$\mathbf{O}$ of each approach. Ptr-Net maintains a relatively lower time
complexity due to its direct modeling of the policy using the pointing
mechanism. In contrast, PQN, which integrates Ptr-Net with Q-learning,
inherits the time complexity of both components, resulting in longer
convergence times (as deepened in the previous point).

Action-Selection Distribution

  * •

For $\mathcal{O}_{20}$, Ptr-Net often favored sequential actions, indicating a
preference for deterministic path selection. In contrast, PQN demonstrated a
more diverse approach, exploring non-sequential paths strategically.

  * •

For $\mathcal{O}_{50}$, Ptr-Net continued to favor sequential actions,
maintaining its deterministic pattern. PQN, however, retained its preference
for non-sequential actions, showcasing its adaptability to complex scenarios.

In our experiment, Ptr-Net and PQN exhibited distinct action-selection
preferences when solving the OP. Ptr-Net displays a bias toward sequential
actions, often favoring choices that follow a specific order, even in
intricate scenarios. In contrast, PQN maintains a preference for actions that
underscores its capacity to explore non-sequential nodes. The action sequences
from PQN emphasize its tendency to select paths involving non-consecutive
nodes. This inclination toward diverse action selection reveals PQN’s robust
adaptability to complex OP settings, where sequential decisions may not always
lead to the most rewarding solutions.

We can formalize these concepts using the entropy of the distributions
Definitions and proofs

$H(\pi_{\text{Ptr-Net}})<H(\pi_{\text{PQN}})$

The inequality then reflects the greater diversity and non-sequential nature
of action selections in PQN compared to Ptr-Net.

| $\pi_{\text{Ptr-Net}}$ | $\pi_{\text{PQN}}$
---|---|---
$\mathcal{O}_{20}$ | {16→17→18→19} | {1→3→4→5}
$\mathcal{O}_{50}$ | {0→1→2→3→4→5→6→7→8} | {31→30→13→8→39→38→37→36→35}
Table 1: Comparison of the obtained action sequences $\pi$ from both models

(a) $\mathcal{O}_{20}$

(b) $\mathcal{O}_{50}$

Figure 2: Visualization of the retrieved action sequences $\pi$, Ptr-Net (in
red), PQN (in blue)

##  5 Conclusions

In this paper, we introduced the Pointer Q-Network (PQN) as a novel approach
to addressing the Orienteering Problem (OP), a challenging problem in
combinatorial optimization with applications in logistics, sightseeing, and
location-based tasks. While Pointer Networks (Ptr-Nets) and related methods
have shown success in other combinatorial optimization tasks like the
Traveling Salesman Problem (TSP), their performance in the context of OP left
room for improvement.

PQN merges Pointer Networks with Q-learning to create a new approach to OP. We
have demonstrated the advantages of PQN over traditional Ptr-Nets in solving
OP instances. Our experimental results show that PQN outperforms Ptr-Net in
terms of cumulative rewards, indicating a more effective decision-making
process. PQN’s preference for non-sequential actions highlights its
adaptability to complex OP scenarios, where sequential decision-making might
not always lead to optimal solutions.

The use of Q-learning within the PQN framework helps address the challenges
associated with OP. By considering both immediate rewards and long-term
benefits, PQN offers a more holistic approach to solving the problem. The
choice of the pointing batch parameter $\lambda$ further allows for the fine-
tuning of the algorithm’s behavior based on the complexity of the specific
problem.

However, it’s important to acknowledge that PQN comes with a trade-off, which
is the longer convergence time compared to Ptr-Net. This is due to the
integration of two distinct learning processes, pointing mechanisms, and
Q-value approximations. The choice between Ptr-Net and PQN should depend on
the specific requirements of the problem, where Ptr-Net might be preferred for
quicker convergence, while PQN is the better choice for more complex OP
scenarios.

In conclusion, the introduced PQNs represent a significant advancement in
addressing the Orienteering Problem. PQNs bridge the gap in Ptr-Nets’ approach
to OP by offering a balance between computational efficiency and a thorough
consideration of costs and rewards. This research opens up exciting avenues
for the use of reinforcement learning techniques in solving complex
combinatorial optimization problems with budget constraints, benefiting
industries such as logistics and tourism.

The continued exploration of PQN’s potential and further research into fine-
tuning its parameters to optimize its performance in various OP scenarios are
promising areas for future work.

## Acknowledgements

We would like to express our heartfelt gratitude to the following individuals
who played a significant role in the development of this research:

  * •

Park Kwanyoung from Seoul National University provided invaluable insights by
identifying critical issues and shortcomings in the paper, both in terms of
content and technical aspects.

  * •

Valerio Romano Cadura from Luiss Guido Carli offered valuable guidance related
to the experimental setup and practical implementation of our research.

  * •

Professor Cristiana Bolchini from Politecnico di Milano provided exceptional
insights into the structure and review of this paper. Her constructive
feedback greatly enhanced the quality of our research.

  * •

Professor Anand Avati from Stanford University deserves special recognition
for his invaluable teachings in machine learning. His guidance and expertise
laid the strong foundations for this work.

  * •

We extend our appreciation to the broader academic community and the readers
of this paper for their interest and support. Your engagement and interest in
our work are highly valued.

These contributions have been instrumental in our research journey, and we are
deeply grateful for their assistance and guidance.

## Definitions and proofs

Definition: Values and Q-Values Values $V^{\pi}(s)$ represent the expected
return from a given state, while Q-values $Q^{\pi}(s,a)$ represent the
expected return from taking a specific action in a given state.

$\displaystyle V^{\pi}(s)$ $\displaystyle=\mathbb{E}_{\pi}\bigg{[}\sum_{t\geq
0}\gamma^{t}R_{t}|S_{0}=s\bigg{]}$ (23) $\displaystyle Q^{\pi}(s,a)$
$\displaystyle=\mathbb{E}_{\pi}\bigg{[}\sum_{t\geq
0}\gamma^{t}R_{t}|S_{0}=s,A_{0}=a\bigg{]}$ (24)

Definition: Bellman equation The Bellman equation expresses the relationship
between the value of a state and the values of its successor states, providing
a recursive formulation for dynamic programming in reinforcement learning.

$Q(s,a)=r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})$ (25)

Definition: Long Short-Term Memory (LSTM) LSTM is a type of recurrent neural
network (RNN) architecture designed to overcome the vanishing gradient problem
and capture long-range dependencies in sequential data. It employs a memory
cell and three gating mechanisms to control the flow of information. LSTM
networks are widely used in tasks involving sequential data due to their
ability to capture and retain information over long sequences. An LSTM unit’s
computations can be summarized as follows:

$\displaystyle f_{t}$
$\displaystyle=\sigma(W_{f}\cdot[h_{t-1},x_{t}]+b_{f})\text{ (Forget Gate)}$
(26) $\displaystyle i_{t}$
$\displaystyle=\sigma(W_{i}\cdot[h_{t-1},x_{t}]+b_{i})\text{ (Input Gate)}$
(27) $\displaystyle\tilde{C}_{t}$
$\displaystyle=\tanh(W_{C}\cdot[h_{t-1},x_{t}]+b_{C})\text{ (Candidate Cell
State)}$ (28) $\displaystyle C_{t}$ $\displaystyle=f_{t}\cdot
C_{t-1}+i_{t}\cdot\tilde{C}_{t}\text{ (Cell State)}$ (29) $\displaystyle
o_{t}$ $\displaystyle=\sigma(W_{o}\cdot[h_{t-1},x_{t}]+b_{o})\text{ (Output
Gate)}$ (30) $\displaystyle h_{t}$ $\displaystyle=o_{t}\cdot\tanh(C_{t})\text{
(Hidden State)}$ (31)

Definition: Entropy of an Action Distribution The entropy ($H$) of an action
distribution ($\pi$) measures the level of uncertainty or randomness in the
selection of actions. It is defined as follows:

$H(\pi)=-\sum_{i=1}^{N}\pi_{i}\log(\pi_{i})$ (32)

Proof: Convergence of Tabular Q-learning

  * •

The Q-learning update rule is:

$Q(s,a)\leftarrow
Q(s,a)+\alpha\left[r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})-Q(s,a)\right].$
(33)

  * •

For convergence in tabular Q-learning, certain conditions are crucial:

    * –

Every state-action pair $(s,a)$ is visited infinitely often to ensure all
Q-values are updated.

    * –

A sufficiently small and decreasing learning rate to ensure stability, e.g.,
$\alpha_{t}=\frac{1}{t}$ for the t-th visit of $(s,a)$.

    * –

A policy that allows exploration, such as the $\epsilon$-greedy policy,
ensuring all state-action pairs are explored.

  * •

Given these conditions and the fixed point property of the Bellman optimality
equation, the Q-values converge to the optimal action-values, $Q^{*}$. This is
formalized in the convergence theorem for Q-learning.$\quad\Box$

Proof: From the Bellman equation to the Q-Learning (DQN included) update rule

  * •

Recall the Bellman equation for estimating Q-values by following a policy
$\pi$:

$Q^{\pi}(s,a)=\mathbb{E}_{\pi}[r(s,a)+\gamma Q^{\pi}(s^{\prime},a^{\prime})]$
(34)

  * •

The TD error is:

$\delta=r+\gamma\max_{a^{\prime}_{i}}Q^{\pi}(s^{\prime},a^{\prime})-Q^{\pi}(s,a).$
(35)

  * •

Using the TD error, the Q-value is updated as:

$Q^{\pi}(s,a)\leftarrow Q^{\pi}(s,a)+\alpha\delta.$ (36)

  * •

Here, $\alpha\in\mathbb{R}$ is the learning rate. Substituting the value of
$\delta$ from above, we get:

$Q^{\pi}(s,a)\leftarrow
Q^{\pi}(s,a)+\alpha\left[r+\gamma\max_{a^{\prime}}Q^{\pi}(s^{\prime},a^{\prime})-Q^{\pi}(s,a)\right].$
(37)

  * •

Which corresponds to the final DQN update rule for Q-values. The convergence
of this formula hinges on the nature of interactions between agents and the
exploration strategies they employ.$\quad\Box$

## References

Human-level control through deep reinforcement learning.
Nature, 518(7540), 529-533.
Mnih, V., Kavukcuoglu, K., Silver, D., et al. (2015).

Reinforcement learning: An introduction.
MIT press.
Sutton, R. S., Barto, A. G. et al. (2018).

Multi-agent actor-critic for mixed cooperative-competitive environments.
In Advances in neural information processing systems (pp. 6379-6390).
Lowe, R., Wu, Y., Tamar, A., et al. (2017).

Q-learning.
Machine learning, 8(3-4), 279-292.
Watkins, C. J., Dayan, P. et al. (1992).

Neuronlike adaptive elements that can solve difficult learning control
problems.
IEEE transactions on systems, man, and cybernetics, 5, 834-846. Barto, A.
G., Sutton, R. S., Anderson, C. W. et al. (1989).

Mastering the game of Go with deep neural networks and tree search.
Nature, 529(7587), 484-489.
Silver, D., Huang, A., Maddison, C. J., et al. (2016).

Learning to communicate with deep multi-agent reinforcement learning.
In Advances in Neural Information Processing Systems (pp. 2137-2145).
Foerster, J., Assael, I. A., de Freitas, N., & Whiteson, S. et al. (2016).

Learning Combinatorial Optimization Algorithms over Graphs
E. Khalil, H. Dai, Y. Zhang, B. Dilkina, Le Song et al. (2017).

Exploratory Combinatorial Optimization with Reinforcement Learning
T. D. Barrett, W. R. Clements, J. N. Foerster, A. I. Lvovsky et al. (2019).

Pointer Networks
O. Vinyals, M. Fortunato, N. Jaitly et al. (2015).

Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem
J. Zheng, J. Zhong, M. Chen, K. He. et al. (2017).

Combinatorial Optimization by Graph Pointer Networks and Hierarchical
Reinforcement Learning
Q. Ma Suwen, Ge Danyang, He Darshan, T. I. Drori et al. (2019).

Reinforcement Learning.
In CS229: Machine Learning, Avati A. (Lecturer), Stanford University.
Unpublished lecture notes.
A. Barro (2023).


# Twisted by the Pools: Detection of Selfish Anomalies in Proof-of-Work Mining

Sheng-Nan Li  Blockchain & Distributed Ledger Technologies, Faculty of
Business, Economics and Informatics, University of Zurich, CH-8050,
Switzerland  UZH Blockchain Center, Faculty of Business, Economics and
Informatics, University of Zurich, CH-8050, Switzerland<EMAIL_ADDRESS>Carlo Campajola  DLT Science Foundation, London, United Kingdom  Blockchain &
Distributed Ledger Technologies, Faculty of Business, Economics and
Informatics, University of Zurich, CH-8050, Switzerland  UZH Blockchain
Center, Faculty of Business, Economics and Informatics, University of Zurich,
CH-8050, Switzerland  Claudio J. Tessone  Blockchain & Distributed Ledger
Technologies, Faculty of Business, Economics and Informatics, University of
Zurich, CH-8050, Switzerland  UZH Blockchain Center, Faculty of Business,
Economics and Informatics, University of Zurich, CH-8050, Switzerland

###### Abstract

The core of many cryptocurrencies is the decentralised validation network
operating on proof-of-work technology. In these systems, validation is done by
so-called miners who can digitally sign blocks once they solve a
computationally-hard problem. Conventional wisdom generally considers this
protocol as secure and stable as miners are incentivised to follow the
behaviour of the majority. However, whether some strategic mining behaviours
occur in practice is still a major concern. In this paper we target this
question by focusing on a security threat: a selfish mining attack in which
malicious miners deviate from protocol by not immediately revealing their
newly mined blocks. We propose a statistical test to analyse each miner’s
behaviour in five popular cryptocurrencies: Bitcoin, Litecoin, Monacoin,
Ethereum and Bitcoin Cash. Our method is based on the realisation that selfish
mining behaviour will cause identifiable anomalies in the statistics of
miner’s successive blocks discovery. Secondly, we apply heuristics-based
address clustering to improve the detectability of this kind of behaviour. We
find a marked presence of abnormal miners in Monacoin and Bitcoin Cash, and,
to a lesser extent, in Ethereum. Finally, we extend our method to detect
coordinated selfish mining attacks, finding mining cartels in Monacoin where
miners might secretly share information about newly mined blocks in advance.
Our analysis contributes to the research on security in cryptocurrency systems
by providing the first empirical evidence that the aforementioned strategic
mining behaviours do take place in practice.

## Introduction

Blockchains are decentralised and distributed systems, where sequential,
verified data in blocks of a chain and securing data transmission from
manipulation through cryptography. Among all the blockchain-based
technologies, cryptocurrencies are the most famous ones. The original crypto
consensus mechanism is called “Proof-of-Work”(PoW) and is employed in the
majority of cryptocurrency systems[1, 2]. The consistency of a PoW system’s
ledger is maintained by all participants solving hash puzzles, a process
usually called “block mining”. In order to solve the puzzles, attempts have to
be made through brute force and therefore, a priori, the probability of
finding a solution is proportional to the number of tries per unit of time a
miner is able to perform, measured in hashes per second (H/s). Each miner is
then rewarded by a nominal amount of cryptocurrency if they are the first
acknowledged miner to find a valid block in the longest chain of the network.
This type of rewarding system provides an incentive for miners to contribute
their resources to the system, and is essential to the cryptocurrency’s
decentralised nature. According to this mechanism, the more mining power
(resources) a miner invests, the bigger their chance to mine the next block
first[3]: as a result miners often join in mining pools to share their mining
powers, thus reducing the variance of their rewards.

PoW mining protocols in principle are tailored to be resistant towards
multiple kinds of attacks, but several potentially harmful strategies have
been analysed in the literature and some of them have been shown to be
profitable under proper conditions. Some attacks might influence the
information propagation in the peer-to-peer network, as is the case for Sybil
attacks, eclipse attacks [4] and routing attacks[5]; others could threaten
data consistency, such as double-spending attacks [6] or block withholding
attacks [7], which are the focus of this paper. According to the PoW protocol,
when miners find a block they should submit it to their peer nodes
unconditionally. However, in a block withholding attack, miners could decide
to not submit the block, or to postpone submitting it. While in the first
case, which is also named as sabotage, there is no direct benefit for the
attacker but can harm the other miners, the latter one, which is also known as
selfish mining (SM), is potentially profitable for the attacker.

The selfish mining attack was first described by Eyal and Sirer[8] in 2014.
They defined the SM strategy as follows: “the selfish mining pool keeps its
mined blocks private, secretly bifurcating the blockchain and creating a
private branch. […] their private branch will not remain ahead of the public
branch indefinitely. Consequently, selfish mining judiciously reveals blocks
from the private branch to the public, such that the honest miners will switch
to the recently revealed blocks, abandoning the shorter public branch.”. The
different strategies of SM are shown in Fig. 1. Let’s classify the miners in a
stylised P2P mining network in two groups: selfish (red node) and honest
(green and black nodes). At $t_{1}$, a selfish miner mines a block (in red)
after the longest chain terminating at $t_{0}$, but withholds it and secretly
mines on the private branch. Then, if the selfish miner finds the next block
($t_{2A}$), the attack is successful and they can choose whether to publish
the new chain or continue mining selfishly; however, if a honest miner also
finds a block (in green) at the same height ($t_{2B}$), the selfish miner will
immediately publish its secret block, and there will be a competition. Later
($t_{3}$, $t_{3A}$), if the selfish miner finds the next block after its own
block, it is also a successful attack, whereas if ($t_{3B}$) an honest miner
finds the next block after the selfish miner’s block, the selfish miner still
enjoys the revenue of the first block. The only negative outcome for the
selfish miner is ($t_{3C}$), where an honest miner finds the next block after
the honest miner’s block, resulting in the selfish miner gaining nothing. Eyal
and Sirer point out another problem caused by the SM attack which is the waste
of resources by honest miners on the shorter public branch: if the rewards of
selfish miners encourage more honest miners to join the selfish mining pool,
it may eventually lead to the selfish pool holding the majority of mining
power (51% attack) and the failure of the cryptocurrency ecosystem.

Figure 1: Visualisation of selfish mining strategy.

The formulation of the SM attack has drawn a lot of attention and many
extended mining strategies have been proposed, such as stubborn mining [9] and
the publish-n strategy [10]. Many of these extended strategies use Markov
Decision Processes (MDP) solving to compute optimal selfish mining strategies
and have managed to lower the profitability threshold of running a SM attack
from 25% hash power [8], to 23.21% [11], or even 21.48% [12]. Meanwhile,
various countermeasures have been proposed against SM attacks. Zhang [13] has
categorised the existing defence methods into two approaches: 1) making
fundamental changes to the block validity rules, as for example adopting the
ZeroBlock [14] timestamp-free solution which requires that each block must be
generated and received by the network within a maximum acceptable time
interval, or 2) lowering the chance of honest miners working on the selfish
miner’s chain during a forked situation, as in the case of the Freshness
Preferred defence [15] which uses unforgeable timestamps issued by a trusted
party, providing an incentive for miners to immediately publish newly mined
blocks. To replace the original Bitcoin Fork-Resolving Policy (FRP), denoted
by length FRP, Zhang [13] proposed weighted FRP : it asks miners to compare
the weight of the chains instead of their length, where the weight is the
number of “in time" blocks in the chain, and a block is considered “in time"
based on an upper bound on the block propagation time. However selfish miners’
timely reaction to another competitive block, and the high cost of changing
the blockchain’s fundamental design, might be obstacles to efficiently
implement the defence against SM attack. More essentially, the problem of how
to detect these selfish miners and quantify the size of the attack is a more
urgent problem for the already running blockchain platforms. Recently, in the
end of 2020, Nicolas summarised 20 primary selfish mining attack
countermeasures using the proposed taxonomy of defensive strategies[16], and
analysed the benefits and limitations of 6 models under his detection
category. From his summary one can easily find that most of the existing
detection methods have not been tested on real blockchain systems. A framework
using deep reinforcement learning to analyse attacks on blockchain incentive
mechanisms, called SquirRL, has also been proposed by Hou [17]. When using
SquirRL to evaluate both single and multiple agent selfish mining attack in
Bitcoin, Monacoin, Vertcoin and Litecoin, Hou only scraped the estimated total
hash power hourly from real cryptocurrencies. However, none of these previous
studies has detected selfish miners in any real blockchain platforms. The
question of whether selfish mining exists in practice or not is largely left
unanswered so far. Stochastic modelling of the mechanism, has shown that
attackers can actually also leverage on their location in the P2P network [18,
19].

Although selfish mining attacks have not been empirically discovered by
academic research, Monacoin, a cryptocurrency developed in Japan, reportedly
has suffered a selfish mining attack that caused roughly $90,000 in
damages[20]. Therefore, the empirical evidence on whether miners do deviate
from the mining protocols in practice is important to the security and
stability of cryptocurrencies [21], and it is thus necessary to direct
research towards refining detection methods.

In our previous work[22, 23], we had tried to identify the selfish miners in
real cryptocurrency systems by using the Miner Sequence Bootstrapping
model(MSB), the core of which is to shuffle simulations of the sequence of
miners’ block discoveries. Based on this insight, in this paper we propose a
more interpretable statistical test to evaluate miners’ behaviour in five
popular PoW-based cryptocurrencies: Bitcoin, Litecoin, Ethereum, Monacoin and
Bitcoin Cash. We hypothesise that selfish miners’ behaviour of selectively
revealing their mined blocks would cause abnormal probabilities of successive
block discovery, diverging from normal behaviour of statistical independence
of mining outcomes. As we show in the following, under the null hypothesis of
“honest" mining the probability of observing two blocks in a row mined by the
same miner is given by the type II binomial distribution of order 2[24], which
we use to construct a statistical test to detect mining anomalies. In order to
optimise the detection results, we also apply heuristics-based address
clustering techniques on all UTXO blockchain datasets. Furthermore, we
extended the object of our method from single miner (mining pool) to pairs of
miners that may constitute a mining cartel, in which miners secretly share
information related to blocks discovery before publishing. Our main
contributions are listed as follows :

  1. 1.

To the best of our knowledge, our empirical research on selfish mining attacks
and mining cartels in real cryptocurrency systems is presented for the first
time. Mining attack detection is important for maintaining blockchain security
and could be a fundamental index for cryptocurrencies ranking in the future.

  2. 2.

In our mining behaviour detection test, we use a type II binomial distribution
of order 2 to compute each miner’s probability of successive block discovery.
This can be widely applied in various competitive consensus protocols,
including but not limited to PoW and PoS.

  3. 3.

Our results show that in some cryptocurrencies abnormal miners do secretly
collaborate in mining cartels; this could raise concerns about concentration
of mining power which has been ignored by most of previous studies.

  4. 4.

We highlight the importance of heuristic address clustering for empirical
studies in real blockchain systems, especially for user behaviour analysis.

  5. 5.

Our empirical analyses also reveal that mathematical or economical models that
focus on cost-benefit analysis could fail to detect some behaviours, as
participants of cryptocurrencies might have bounded rationality or be risk
seeking.

## Results

### Dashboard of Datasets

The mining difficulty adjustment in the PoW protocol ensures a fixed average
time between each block, called “block time”. Since Bitcoin (BTC), Litecoin
(LTC), Monacoin (MONA), Ethereum (ETH) and Bitcoin Cash (BCH) have different
block times, in order to have compatible datasets we split the blockchain in
different time intervals tailored to maintain a similar number of blocks
($\sim$ 5000) in each sample. This amounts to monthly (BTC and BCH), weekly
(LTC), 5 days (MONA) and daily (ETH) splits. In Fig. 2 we show the number of
blocks mined in each time interval for the five cryptocurrencies from the
genesis block until the end of our dataset on December 2020. One can find that
the mining markets of all the five cryptocurrencies have unstable stages of
block mining with different lengths after launch. However, because of the
difficulty adjustment, the amount of blocks in each stated period is similar
in five coins (as shown in Fig.2(a)). In our Ethereum and Monacoin datasets we
only have information about each block miner’s address, while miners’
addresses were tagged to named mining pools in the Bitcoin, Litecoin and
Bitcoin Cash datasets.

Figure 2: Number of miners and blocks during each period in five
cryptocurrencies.

We further show the revenue (amount of mined blocks) distributions in each
period in Fig. 3. The “Unknown” miner are some mining addresses whose
identities cannot be traced back to any known pool. It is worth mentioning
that some of the unknown mining addresses might be owned by named pools (e.g.
to hide their activities such as selfish mining). In detail, one can observe
that in BTC and LTC as time flows more and more blocks were mined by named
pools, while in BCH there are more than 20% of blocks that are mined by
“Unknown” miners all the time. Comparing MONA and ETH where we lack the
information about mining pool identity, we find that in MONA the revenue
distributions among miners’ addresses is more volatile.

In addition, according to the “PoW” mechanism, the fair proportion of blocks a
miner may discover during a time period (i.e. their blocks share) is equal to
their share of mining power. Since we lack better estimators of hash rates,
for the rest of this paper we use a miner’s share of blocks as a proxy for its
mining power.

Figure 3: Periodic hashing power (share of blocks) distribution in BTC, LTC,
BCH, MONA and ETH.

### Address Cluster

After finding the “Unknown” miners and large fluctuation of hashing power
distribution, to enhance the datasets we adopt known methodologies to cluster
addresses controlled by the same miner[25, 26, 27, 28]. All the heuristic
methods we applied exploit inherent properties of UTXO-based transactions,
which can include multiple inputs and multiple outputs and generate patterns
that allow to cluster addresses together. This was not possible on the
account-based blockchain of Ethereum, where only one input and one output can
appear in the same transaction. Further details of the three applied
methodologies ($H_{1}$, $H_{2}$, $H_{p}$) are provided in the Methods section.

We apply the most basic method, $H_{1}$, to cluster the miners’ addresses in
the Monacoin dataset. The distribution of mined blocks share among different
entities (addresses or clusters) is shown in Fig. 4, and the outcome of
clustering in MONA is shown in the subplot of network in Fig.4. In the latter
dots are addresses, connected and marked in the same colour if they belong to
the same cluster, and the highlighted communities are the larger clusters with
more than 10 addresses. It can be seen that the $H_{1}$ methodology aggregates
miner’s addresses into clusters of different size, effectively changing the
estimation of hashing power attributed to them.

Figure 4: Address Clustering in Monacoin

For the Bitcoin, Litecoin and Bitcoin cash datasets where we already knew the
named-pools of part of the blocks, we try all the three mentioned heuristics
to tag the “Unknown” miners to named pools, with the priority order as
$H_{1}>H_{2}>H_{p}$. In other words, in each among the BTC, LTC, and BCH
datasets, firstly we apply $H_{1}$ to cluster the miners’ addresses, and then
each “Unknown” miner whose address could be clustered together with all the
addresses of a named mining pool will be tagged to this named pool. We then do
the same using the $H_{2}$ and $H_{p}$ methods to complement the tagging.

The result of this procedure is shown in Fig. 5, where it is clear that
although it’s difficult for address clustering heuristics to tag all the
“Unknown” miners, a significant fraction of blocks can be attributed to a
tagged pool, which is important for a more accurate estimation of miners’
actual computing (hashing) power.

Figure 5: Periodic share of blocks owned by “Unknown” miners before and after
clustering in BTC, LTC, BCH

### Detection of Selfish Miners

To detect abnormal selfish mining behaviour, we devise a statistical test that
we apply on each miner’s sequence of mined blocks, the null hypothesis being
that miners are “honest", i.e. they act without selfish behaviour. As we show
in the Methods section, under the null hypothesis the event of whether a miner
mines a block or not is a Bernoulli random variable, with the success
probability equal to the miner’s hashing power share. However a successful
selfish mining attack could lead to anomalies in a miner’s outcome of
discovering blocks in sequence. Therefore, we design our test statistic to
identify suspicious miners by the amount of times in which they mine
successive blocks, i.e. the number of success runs of length 2, whose
probability distribution under the null is given by a type II binomial
distribution of order 2 [24]. To account for multiple hypothesis testing
errors we apply the Benjamini-Hochberg correction [29] for the $p$-values to
control for excess false positives, setting the target False Discovery Rate
(FDR) to 5%.

The results of our tests (before address clustering) are shown in aggregate in
Fig. 6. In Fig.6a, each bar shows the proportion of abnormal miners (with the
corrected $p$-values, $\hat{p}<0.05$) in the five cryptocurrencies. Bars in
different colours represent results under different classification criteria:
the blue, orange, green, yellow and the grey bar respectively show the
fraction of miners for whom at least 25%, 50%, 75% or all (max) tests on the
considered time periods reject the null hypothesis at 5% FDR. For example, in
Monacoin, the result expressed by the grey bar shows that about half of miners
have behaved selfishly in all the periods they were active.

We then compare the detection results before and after address clustering,
shown in Fig. 6b. Following address clustering the ratio of abnormal miners in
each coin decreases; however, even after clustering, there were more than 46%
miners who always engaged in strategic mining behaviour in Monacoin. The
reduction in abnormal ratio when changing the criterion from lower quartile
(25%) to maximum (max) is larger in Bitcoin cash than in Monacoin, which shows
the abnormal miners in Monacoin might be more likely to continuously behave
with the selfish strategy, or alternatively that many malicious miners entered
Monacoin only to run a SM attack, leaving the system right after.

Figure 6: Ratio of abnormal miners in BTC, LTC, MONA, ETH and BCH. In (a), the
bar in different colors respectively shows the percentage of unique miners,
whose minimum value, first, second, and third quartile, as well as maximum
values of the $\hat{p}$ in different period is less than 0.05. In (b), the red
dashed lines display the comparison between results after address clustering
and the original results shown in (a) of BTC, LTC, MONA and BCH.

In addition, we show the number of abnormal miners for each period in
Monacoin, Ethereum and Bitcoin cash in Fig. 7. The result of each period
includes all miners whose corrected $p$-value, $\hat{p}$, is smaller than 0.05
in that period. The empirical results of Monacoin (7a) show that the period
with the most abnormal miners is around June-July 2018, which is near but much
longer than the period 13-15 May 2018 when Monacoin announced they had
suffered from a selfish mining attack. Besides, a part of miners might have
been trying the selfish mining attack throughout time, not only during the
mentioned periods. It seems that the selfish mining attack on Monacoin was
contained after 2019 as we see a downward trend in the amount of abnormal
miners. The result in Fig. 7c shows that several miners in Bitcoin cash might
try to conduct the selfish mining attack much more erratically, and a large
number of abnormal miners appeared in Nov. 2018 in Bitcoin cash, with still a
few abnormal miners persisting into more recent years. Similarly in Ethereum
(Fig.7b), there were more abnormal miners at ETH’s launch, with SM attacks
being more frequent in 2018 and occasionally occurring during the run time.

Figure 7: Number of abnormal miners during each time period in MONA, ETH and
BCH. The black lines present the results before doing address clustering,
while the red dashed lines show the results after address clustering.

To further research the effect of increasing mining power on the potential of
doing SM attack, we group active miners in each period by their corresponding
hashing power in that period, and calculate the proportion of abnormal miners
in each hashing power interval. In Fig. 8, one can find that in Monacoin the
incidence of SM behaviour increases with miners’ power when below 50% hashing
power, and this increasing incidence also exists in Ethereum when below 30%
hashing power, as well as in Bitcoin Cash below 25% power.

Figure 8: Fraction of abnormally behaving miners sorted by hashing power
ranges in MONA, ETH and BCH.

### Network of Mining Cartels

In order to detect the existence of a mining cartel where different miners
share the information in advance among themselves and perform a coordinated
selfish mining attack, we have extended our methods from testing single miners
to pairs of miners. Considering pairs of miners $i$ and $j$ as a group $ij$,
we conduct the similar hypothesis tests as above for each pair of miners and
also calculate their corrected $p$-values, $\hat{p}_{ij}$ in each period. Then
we consider the pairs with $\hat{p_{ij}}<0.05$ (but both $\hat{p}_{i}$ and
$\hat{p}_{j}$ are greater than 0.05 in the given period) as potential cartels
composed by miners $i$ and $j$. After testing each pair of miners in five
cryptocurrencies, we show the network of identified mining cartel for each
cryptocurrency in Fig. 9, where in each network a link represents an
identified cartel between two miners and the weight (width) of the link is the
number of times this pair of miners were detected as a cartel in different
periods. The size of the node reflects the miner’s average hashing power among
all his active periods.

As shown in Fig.9(a) and 9(b), we find two abnormal cartels in Bitcoin and
only one in Litecoin, and each of these cartels only includes two members. In
Bitcoin cash as shown in Fig.9(c), there are a few cartels, most of which are
in a connected subgraph, and the four most powerful mining pools AntPool,
BTC.com, ViaBTC and Bitcoin.com (the four biggest blue nodes) are fully
connected with each other. We identified many abnormal cartels in both
Monacoin (in Fig. 9(d)) and Ethereum (in Fig. 9(e)), but the connectivity of
cartel networks in Monacoin and Ethereum is totally different. In Monacoin, a
bit like in Bitcoin cash, we find large cartels containing two or three
powerful miners and many small miners, with a very high connectivity. In
addition, there are also some separated small cartels with a few miners.
However, the whole cartel network of Ethereum has a low connectivity. There
are two separated large cartels, each of which contains several powerful
miners, as well as a few cartels of varying size and with a generally low
connectivity.

(a) BTC

(b) LTC

(c) BCH

(d) MONA

(e) ETH

Figure 9: Networks of Mining Cartel in BTC, LTC, BCH, MONA and ETH. Each node
represents a pool (in BTC, LTC and BCH) or an address (in MONA and ETH), and
each link represents an identified cartel between two miners. The weight of
each link is the number of times the pair of miners has been detected as a
cartel in all periods.

## Discussion

The ledger of cryptocurrencies is always maintained through distributed
consensus. Proof-of-work (PoW) is the most widely used consensus mechanism,
maintaining the consistency of the system’s ledger by requiring validators to
solve an arbitrary mathematical puzzle to earn the right to verify
transactions. Following the tremendous increase in market capitalisation of
cryptocurrencies these years, defence from potential attacks on blockchain
system has become an important topic. We considered the problem of selfish
mining, one of the attacks which breaks information symmetry in blockchain
systems, proposed by Eyal and Sirer in 2014. When employing the selfish mining
(SM) strategy, malicious miners selectively keep their newly mined blocks
temporarily private instead of publishing them immediately. To our knowledge,
most of the previous studies on detection of selfish mining attacks are
analytical models without empirical tests on real blockchain systems.

In this study, we proposed a statistical method to conduct empirical research
on detection of selfish miners in five “PoW”-based cryptocurrencies, namely
Bitcoin (BTC), Litecoin (LTC), Monacoin (MONA), Ethereum (ETH) and Bitcoin
cash (BCH). Regardless of whether SM actually leads to monetary gains or not,
we emphasise that the strategy could lead to anomalies in the frequency with
which a miner discovers successive blocks. We also investigated mining
cartels, where miners secretly share information about new blocks among
partners to pursue a collective SM strategy. Given the fact that existence of
mining cartels may cause certain threats to the security of blockchain-based
systems but has been ignored in many previous studies, we also proposed our
methods to test miners pairwise, in order to detect at least some potential
cartels. Our results suggest that although the SM strategy was proposed as an
attack to the Bitcoin system, it was employed by more miners in Monacoin and
Bitcoin cash. In particular in Monacoin there are about 50% potential selfish
miners. Our detection results are consistent with Monacoin’s own report about
having suffered selfish mining attacks. We also detect more mining cartels in
Monacoin, Ethereum and Bitcoin cash compared with the two in Bitcoin and only
one in Litecoin. The cartel network in Monacoin has a very high connectivity,
but the cartels in Ethereum are more separated and most of them are in a tree
structure. In addition to that, our results also show the importance of
address clustering when conducting empirical studies in real blockchain
systems.

There are some limitations to our work. First of all, selfish mining attacks
and forming mining cartels are only two of the possible reasons for the
anomalies we detect in miner’s rates of successive block discoveries;
alternatives include for example finite diffusion times[30]. Secondly, we
relied on the empirical frequency of mined blocks to estimate miners’ hash
rates: while this is the best estimator we can obtain from blockchain data, it
is not necessarily accurate.

Our next step is to analyse the miner’s (validator) selfish behaviour in
cryptocurrencies that apply other consensus mechanisms [31]. In addition, a
further empirical research based on this paper is whether an “uncle block
reward" could cause Ethereum to be more vulnerable to selfish mining attacks
[32, 33]. Finally, our methods can also be applied as a forensics tool to
characterise strategic mining behaviours, contributing to monitoring the
security in current cryptocurrency ecosystems.

## Methods

### Anomalies in Selfish Mining Attack

Following the “PoW" protocol, a miner’s discovery of each block should be
random and independent without any influence from the previous blocks, if the
information diffuses through the network instantaneously [30]. Thus, during a
certain time period where each miner’s hashing power $h_{i}$ is assumed
constant, the event whether miner $i$ mined block $t$ or not follows a
Bernoulli distribution with probability $h_{i}$. However, when doing a
strategic mining attack (e.g. selfish mining), the miners selectively publish
their mined blocks to keep their leading height in block competition. This
could lead to identifiable anomalies in statistics of successive blocks
discovery.

How many consecutive blocks an attacker could mine is important to blockchain
security and also to attack detection. As we can imagine when selfish miners
keep mining on their private chain, they also take risks of losing the
expected revenue. In the competition of solving hash-puzzle, in order to
ensure a fair revenue, most of the attacks in PoW systems won’t have a long
private chain. According to the strategies of selfish mining [8], when the
private chain falls behind the public chain or the lead drops to 1, the
attacker will immediately publish their private block. Furthermore, in the
research on the alternative “stubborn mining"[9], the authors did not observe
any case where a selfish miner could earn more revenue if they don’t merge
with public when they fall behind by more than 1 block. In addition, there is
a heuristic using the NS3 bitcoin simulator to detect malicious miners by
observing the fork height [34]. The results show that if the mean height of
the fork is higher than 2, the blockchain system can be considered under
selfish mining attack. All the arguments above then indicate that the length
of a private chain would not be very long, usually no more than 2 blocks.

Therefore, in this paper the statistical analysis of selfish mining behaviour
focuses on the case of the same miner mining two consecutive blocks. Although
a selfish mining strategy may not significantly increase the proportion of
blocks mined by strategic miners [35], using our methodology we can detect the
abnormal miners by testing the probability of miners’ successive block
discovery.

### Probability of Successive Block Discovery

Assume there are $N$ miners in the system, identified by index $i=1,\dots,N$.
Define a random variable $X(t)$, where $t=1,\dots,T$ is the block index and
$X(t)=i$ if miner $i$ mined block $t$. Assuming over the given time period the
miner’s hashing power $h_{i}$ is constant, $X(t)$ is characterised by a
multinomial probability distribution with unit size,
$X(t)\sim\mathcal{M}(h,1)$ where $P[X(t)=i]=h_{i}$ is proportional to miner
$i$’s hashing power and, of course, $\sum_{i}h_{i}=1$. The auxiliary random
variable $Y_{i}(t)$ which is $1$ if $X(t)=i$ and $0$ otherwise then follows a
Bernoulli distribution with probability $h_{i}$. We can then define our test
statistic as the number of times $c_{i}$ that the event
$Y_{i}(t)=Y_{i}(t+1)=1$ has occurred, i.e. that miner $i$ has mined $c_{i}$
consecutive pairs of blocks among the $T$ total blocks.

The probability distribution that characterises $c_{i}$ is given by Ling [24].
Indeed the random variable $c_{i}$ follows what is called a type II binomial
distribution of order 2, and the expression below (Equation 1 ) for the
probability mass function is also given in the original paper. Calling
$c_{i}^{(T)}$ the random variable $c_{i}$ for a sequence of length $T$,

$P(c_{i}^{(T)}=x)=\begin{cases}h_{i}^{T}&\text{if}\;x=T-1\\\
2h_{i}^{T-1}(1-h_{i})&\text{if}\;x=T-2(>0)\\\
\sum_{j=1}^{x+2}h_{i}^{j-1}(1-h_{i})P(c_{i}^{(T-j)}=x-\max\\{0,j-2\\})&\text{if}\;0\leq
x<T-2\end{cases}$ (1)

In applying the above formula, Ling also put $P(c_{i}^{(T)}=0)=1$ if $T<2$. In
Fig. 10a, we show an example that probability distribution of variable $c$
under different hashing powers $h$ where the amount of blocks $T$ is 100. The
most probable value of miner’s runs $c$ increases with their hashing power,
where a run is defined as two consecutively mined blocks.

Figure 10: Illustrative diagrams of the statistical method used to detect
abnormal mining behaviour in Proof-of-Work protocols

### Detection of Abnormal Miners

One of the main purposes of this paper is to obtain empirical evidence about
whether selfish mining behaviours occur in practice or not. To achieve this
purpose, we conducted hypothesis tests for every miner in various
cryptocurrencies under the null hypothesis that the miner is honest, such that
rejections of the null would identify a potential selfish miner in a certain
period. Our null hypothesis means that miner $i$ acts non-selfishly in
compliance with the protocol, i.e. all blocks are mined randomly and
independently. Under this null, the $p$-value is going to be the probability
that miner $i$ has at least $c_{i}$ runs of two consecutively mined blocks
occurring in a sample of $T$ blocks. Thus, the $p$-value corresponding to the
observation of $c_{i}$ consecutively mined block pairs is $p_{i}=P(x\geq
c_{i})$, or

$p_{i}=\sum_{x=c_{i}}^{T-1}P(c_{i}^{(T)}=x)=1-\sum_{x=0}^{c_{i}-1}P(c_{i}^{(T)}=x)$
(2)

To give better intuition, in Fig. 10b, we report the critical values $c^{*}$
of the number of consecutively mined blocks at significance level
$\alpha=0.05$, for different values of mining power $h$ and amount of blocks
$T$. That is to say, for example in the purple line, when the amount of the
block is 5000 , the miner with less than 30% hash power but more than 491 runs
of two consecutive blocks might conduct strategic mining behaviours whitin the
95% confidence interval.

When running multiple hypothesis tests the probability of obtaining one or
more false positives (in this case identifying honest miners as abnormal)
quickly becomes very high. For this reason it is important to adjust the
$p$-values of each test to control for the False Discovery Rate (FDR), i.e.
the expected fraction of false rejections among all rejected null hypotheses.
We then adjust the $p$-values according to the procedure by Benjamini and
Hochberg (BH) [29], where the corrected p-value reads

$\hat{p}_{k}=\frac{p_{k}*T}{k}$ (3)

with $p_{k}$ being the $k$-th smallest $p$-value out of $T$ total $p$-values
in the test. After getting the $\hat{p}$ for all the miners, we can reject the
null with a $5\%$ FDR for miners $k<k^{*}$, where $k^{*}$ is the maximum $k$
such that $\hat{p}_{k^{*}}<0.05$, i.e. our results is expected to return a
$5\%$ rate of false positives out of all rejected nulls.

### Detect Mining Cartels

Either an individual miner or a mining pool doing strategic mining could be
considered as a single attacker. However, if some attackers share information
earlier or only among themselves and collaborate to achieve the attack, they
will be seen as a cartel. A mining cartel is then a secretly coordinating
group where miners get together and share timely information related to the
blocks mined. In the previous papers [22, 23], Li et al. already pointed out
that the existence of mining cartels has always been ignored so far.
Considering a mining protocol secure as long as the pool’s mining power is
limited below a certain threshold always relies on the assumption that the
miners (or pools) are operating independently. However, strategic miners may
have incentives to associate in cartels, such as to benefit from the increased
mining power and having information in advance about the blocks mined by the
other members. On the other hand, detection of mining cartels contributes to
revealing the potential relationships between attackers.

Based on the assumption that the collaboration in a cartel will cause the same
anomalies of successive blocks discovery by cartel members, we run our test
method on pairs of miners to detect potential cartels in five cryptocurrency
systems. Therefore, we would like to verify whether a cartel has formed
between two miners, $i$ and $j$, by measuring the anomalies in their
consecutive blocks’ statistics. Specifically, we use $c_{ij}$ which is the
number of times that two consecutive blocks is mined by the pair of miners $i$
and $j$ (regardless of the order), to replace $c_{i}$ in Eq. 1. Likewise, we
replace $h_{i}$ by $h_{ij}=h_{i}+h_{j}$ which is the estimated aggregated
mining power. As a result we can calculate the $p$-value of a pair of miners
$i$ and $j$, $p_{ij}$ to which we also apply the usual FDR correction, and
then use the corrected $\hat{p}_{ij}$-value to detect the cartel between miner
$i$ and $j$.

Of course one may identify a cartel because each miner is independently
selfish. For this reason we only consider a cartel if neither of them is
individually selfish, i.e. $i$ and $j$ form a cartel if $\hat{p}_{ij}<0.05$,
while $\hat{p}_{i}\geq 0.05$ and $\hat{p}_{j}\geq 0.05$.

### Address Clustering

The blockchain protocol adopted by all the analysed cryptocurrencies except
Ethereum allows users to have more than one address linked to their wallet,
which might be used to hide the track of their transactions and balances.
Thus, accurately clustering together the different addresses of a miner is
very important to estimate the mining powers and detect miner behaviour. We
applied three known methodologies to the different cryptocurrencies in our
dataset [36, 37, 38] which are available from the blockchain analytics library
BlockSci [25]:

  * •

Heuristic 1 ($H_{1}$): Multi-input Addresses
If two (or more) addresses are inputs to the same transaction, they are
controlled by the same user.

  * •

Heuristic 2 ($H_{2}$): Optimal Change Address
If the amount of an output addresses is lower than any of the inputs used in
the transaction, then it is reasonable to state that the output address is
used for the transaction change and is controlled by the same user as the
inputs.

  * •

Heuristic p ($H_{p}$): Peeling chain
A transaction is considered to be in a peeling chain if it includes one input
and two outputs, and both the previous and the following transaction follow
this structure. It is reasonable to state that the outputs linking the peeling
chain are change addresses.

Specifically, in the implementation, when using the first heuristic method
($H_{1}$), different addresses used as inputs to one transaction are treated
as being controlled by the same user. Then in $H_{2}$, the identified so-
called change addresses are treated as being controlled by the same user as
the inputs. Finally in $H_{p}$, the “peeling chain” structure is used as a
different definition to identify change addresses.

### Dataset

Our empirical analysis focuses on five popular PoW-based cryptocurrencies
which are Bitcoin (BTC), Litecoin (LTC), Monacoin (MONA), Ethereum (ETH) and
Bitcoin Cash (BCH). Our dataset contains information of blocks from their
launch to the end of 2020, including blocks’ height, mined time, the tag of
corresponding miners (miner address/ pool name). In detail, datasets of
Monacoin and Ethereum only have the miner address of each block, while the
datasets of other three cryptocurrencies already have the labeled name of
mining pools 111https://gz.blockchair.com/. In this research, we define time
windows for each cryptocurrency depending on the block time to ensure a
similar amount of blocks in each detection interval. We present a summary
description of the five datasets in Table 1, and further enumerate each
crytocurrency for detailed introduction.

Coin | Launch time | Block time | Height of blocks | Interval | Miners
---|---|---|---|---|---
Bitcoin | 2009-01-03 | 10 minutes | 663913 | monthly | Named pool
Litecoin | 2011-10-07 | 2.5 minutes | 1974760 | weekly | Named pool
Monacoin | 2013-12-31 | 1.5 minutes | 2206670 | 5 days | Address
Ethereum | 2015-07-30 | 14 seconds | 11564743 | daily | Address
Bitcoin cash | 2017-08-01 | 10 minutes | 189735 | monthly | Named pool
Table 1: Summary description of datasets

  * •

Bitcoin was started on 3 January 2009 when the internet persona Satoshi
Nakamoto mined the first (so-called genesis) block of the chain, known as the
genesis block. Nowadays, this most famous digital asset has a rich and
extensive ecosystem with a total market capitalisation of about 800 billions
US dollars. About every 10 minutes, a new block is created and quickly
published to all nodes, without requiring central oversight.

  * •

Litecoin was a fork of the Bitcoin Core client released by Charlie Lee, a
Google employee and former Engineering Director at Coinbase. The Litecoin
network went live on 13 October 2011 differing primarily by having a decreased
block generation time (2.5 minutes), increased maximum number of coins,
different hashing algorithm, and a slightly modified GUI.

  * •

Monacoin was a fork of Litecoin launched on 31 December 2013 by an anonymous
person under the moniker of Mr. Watanabe. It bills itself as the first
Japanese cryptocurrency and is predominantly used in Japan. Monacoin has an
average block creation time of 1.5 minutes. Most notably, Monacoin was
reported to have suffered from selfish mining attacks between May 13th and
15th in 2018 that caused roughly 90,000 dollars in damages [20].

  * •

Ethereum is the second largest cryptocurrency after Bitcoin, with currently
over 300 billions US Dollars market capitalisation. Ethereum is the blockchain
that issues Ether and was proposed in late 2013 by Vitalik Buterin, a
cryptocurrency researcher and programmer, and the system went live on 30 July
2015 featuring smart contract functionality. The block time of Ethereum is
around 14 seconds. In 2022, Ethereum will be moving from PoW to proof of stake
(PoS) as part of its “Ethereum 2.0” upgrade.

  * •

Bitcoin Cash was a hard fork of Bitcoin that seeks to add more transaction
capacity to the network. On 1 August 2017, Amaury Séchet released the first
Bitcoin Cash software implementation. As in Bitcoin, new blocks are on average
generated every 10 minutes by using a difficulty adjustment algorithm (DAA).
Bitcoin Cash also uses an Emergency Difficulty Adjustment (EDA) [39],
algorithm which has caused an instability in mining difficulty of the Bitcoin
Cash system, resulting in Bitcoin Cash being thousands of blocks ahead of
Bitcoin.

## References

  * [1] Tasca, P. & Tessone, C. J.  A taxonomy of blockchain technologies: Principles of identification and classification.  _Ledger_ 4, DOI: 10.5195/ledger.2019.140 (2019).
  * [2] Spychiger, F., Tasca, P. & Tessone, C. J.  Unveiling the importance and evolution of design components through the “tree of blockchain”.  _Frontiers in Blockchain_ 3, DOI: 10.3389/fbloc.2020.613476 (2021).
  * [3] Nakamoto, S.  Bitcoin: A peer-to-peer electronic cash system.  _Decentralized Business Review_ 21260 (2008).
  * [4] Alangot, B., Reijsbergen, D., Venugopalan, S. & Szalachowski, P.  Decentralized lightweight detection of eclipse attacks on bitcoin clients.  In _2020 IEEE International Conference on Blockchain (Blockchain)_ , 337–342 (IEEE, 2020).
  * [5] Apostolaki, M., Zohar, A. & Vanbever, L.  Hijacking bitcoin: Routing attacks on cryptocurrencies.  In _2017 IEEE symposium on security and privacy (SP)_ , 375–392 (IEEE, 2017).
  * [6] Karame, G. O., Androulaki, E. & Capkun, S.  Double-spending fast payments in bitcoin.  In _Proceedings of the 2012 ACM conference on Computer and communications security_ , 906–917 (2012).
  * [7] Bag, S., Ruj, S. & Sakurai, K.  Bitcoin block withholding attack: Analysis and mitigation.  _IEEE Transactions on Information Forensics and Security_ 12, 1967–1978 (2016).
  * [8] Eyal, I. & Sirer, E. G.  Majority is not enough: Bitcoin mining is vulnerable.  In _International conference on financial cryptography and data security_ , 436–454 (Springer, 2014).
  * [9] Nayak, K., Kumar, S., Miller, A. & Shi, E.  Stubborn mining: Generalizing selfish mining and combining with an eclipse attack.  In _2016 IEEE European Symposium on Security and Privacy (EuroS &P)_, 305–320 (IEEE, 2016).
  * [10] Liu, H., Ruan, N., Du, R. & Jia, W.  On the strategy and behavior of bitcoin mining with n-attackers.  In _Proceedings of the 2018 on Asia Conference on Computer and Communications Security_ , 357–368 (2018).
  * [11] Sapirshtein, A., Sompolinsky, Y. & Zohar, A.  Optimal selfish mining strategies in bitcoin.  In _International Conference on Financial Cryptography and Data Security_ , 515–532 (Springer, 2016).
  * [12] Bai, Q. _et al._ A deep dive into blockchain selfish mining.  In _ICC 2019-2019 IEEE International Conference on Communications (ICC)_ , 1–6 (IEEE, 2019).
  * [13] Zhang, R. & Preneel, B.  Publish or perish: A backward-compatible defense against selfish mining in bitcoin.  In _Cryptographers’ Track at the RSA Conference_ , 277–292 (Springer, 2017).
  * [14] Solat, S. & Potop-Butucaru, M.  Brief announcement: Zeroblock: Timestamp-free prevention of block-withholding attack in bitcoin.  In _International Symposium on Stabilization, Safety, and Security of Distributed Systems_ , 356–360 (Springer, 2017).
  * [15] Heilman, E.  One weird trick to stop selfish miners: Fresh bitcoins, a solution for the honest miner.  In _International Conference on Financial Cryptography and Data Security_ , 161–162 (Springer, 2014).
  * [16] Nicolas, K., Wang, Y., Giakos, G. C., Wei, B. & Shen, H.  Blockchain system defensive overview for double-spend and selfish mining attacks: A systematic approach.  _IEEE Access_ 9, 3838–3857 (2020).
  * [17] Hou, C. _et al._ Squirrl: Automating attack analysis on blockchain incentive mechanisms with deep reinforcement learning.  _arXiv preprint arXiv:1912.01798_ (2019).
  * [18] Schwarz-Schilling, C., Li, S.-N. & Tessone, C. J.  Agent-based modelling of strategic behavior in pow protocols.  In _2021 Third International Conference on Blockchain Computing and Applications (BCCA)_ , 111–118, DOI: 10.1109/BCCA53669.2021.9657011 (2021).
  * [19] Schwarz-Schilling, C., Li, S.-N. & Tessone, C. J.  Stochastic modelling of selfish mining in proof-of-work protocols.  _Journal of Cybersecurity and Privacy_ 2, 292–310, DOI: 10.3390/jcp2020016 (2022).
  * [20] Saad, M., Njilla, L., Kamhoua, C. & Mohaisen, A.  Countering selfish mining in blockchains.  In _2019 International Conference on Computing, Networking and Communications (ICNC)_ , 360–364 (IEEE, 2019).
  * [21] Bonneau, J. _et al._ Sok: Research perspectives and challenges for bitcoin and cryptocurrencies.  In _2015 IEEE symposium on security and privacy_ , 104–121 (IEEE, 2015).
  * [22] Li, S.-N., Yang, Z. & Tessone, C. J.  Mining blocks in a row: A statistical study of fairness in bitcoin mining.  In _2020 IEEE International Conference on Blockchain and Cryptocurrency (ICBC)_ , 1–4 (IEEE, 2020).
  * [23] Li, S.-N., Yang, Z. & Tessone, C. J.  Proof-of-work cryptocurrency mining: a statistical approach to fairness.  In _2020 IEEE/CIC International Conference on Communications in China (ICCC Workshops)_ , 156–161 (IEEE, 2020).
  * [24] Ling, K.  On binomial distributions of order $k$.  _Statistics & Probability Letters_ 6, 247–250 (1988).
  * [25] Kalodner, H. _et al._ Blocksci: Design and applications of a blockchain analysis platform.  In _29th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 20)_, 2721–2738 (2020).
  * [26] Vallarano, N., Tessone, C. J. & Squartini, T.  Bitcoin transaction networks: an overview of recent results.  _Frontiers in Physics_ 8, 286 (2020).
  * [27] Campajola, C. _et al._ The evolution of centralisation on cryptocurrency platforms.  _arXiv preprint arXiv:2206.05081_ (2022).
  * [28] Campajola, C., D’Errico, M. & Tessone, C. J.  Microvelocity: rethinking the velocity of money for digital currencies.  _arXiv preprint arXiv:2201.13416_ (2022).
  * [29] Benjamini, Y. & Hochberg, Y.  Controlling the false discovery rate: a practical and powerful approach to multiple testing.  _Journal of the Royal statistical society: series B (Methodological)_ 57, 289–300 (1995).
  * [30] Decker, C. & Wattenhofer, R.  Information propagation in the bitcoin network.  In _IEEE P2P 2013 Proceedings_ , 1–10 (IEEE, 2013).
  * [31] Neuder, M., Moroz, D. J., Rao, R. & Parkes, D. C.  Selfish behavior in the tezos proof-of-stake protocol.  _arXiv preprint arXiv:1912.02954_ (2019).
  * [32] Feng, C. & Niu, J.  Selfish mining in ethereum.  In _2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS)_ , 1306–1316 (IEEE, 2019).
  * [33] Ritz, F. & Zugenmaier, A.  The impact of uncle rewards on selfish mining in ethereum.  In _2018 IEEE European Symposium on Security and Privacy Workshops (EuroS &PW)_, 50–57 (IEEE, 2018).
  * [34] Chicarino, V., Albuquerque, C., Jesus, E. & Rocha, A.  On the detection of selfish mining and stalker attacks in blockchain networks.  _Annals of Telecommunications_ 1–10 (2020).
  * [35] Wright, C. S. & Savanah, S.  The fallacy of the selfish miner in bitcoin: An economic critique.  _Available at SSRN 3009466_ (2017).
  * [36] Meiklejohn, S. _et al._ A fistful of bitcoins: characterizing payments among men with no names.  In _Proceedings of the 2013 conference on Internet measurement conference_ , 127–140 (2013).
  * [37] Androulaki, E., Karame, G. O., Roeschlin, M., Scherer, T. & Capkun, S.  Evaluating user privacy in bitcoin.  In _International conference on financial cryptography and data security_ , 34–51 (Springer, 2013).
  * [38] Ermilov, D., Panov, M. & Yanovich, Y.  Automatic bitcoin address clustering.  In _2017 16th IEEE International Conference on Machine Learning and Applications (ICMLA)_ , 461–466 (IEEE, 2017).
  * [39] Kwon, Y., Kim, H., Shin, J. & Kim, Y.  Bitcoin vs. bitcoin cash: Coexistence or downfall of bitcoin cash?  In _2019 IEEE Symposium on Security and Privacy (SP)_ , 935–951 (IEEE, 2019).

## Acknowledgements

S.-N.L. acknowledges funding from the China Scholarship Council (CSC)
(No.201808310212).
C.C. acknowledges support from the Swiss National Science Foundation grant
#200021_182659.

## Author contributions statement

C.J.T and S.-N.L. conceived the experiment(s). C.C and S.-N.L. developed the
methodology, S.-N.L. and C.J.T retrieved the data. S.-N.L. performed the data
analysis. and C.C wrote a first draft. All authors completed and reviewed the
final version of this paper.

## Competing interests

The authors declare no competing interests.