# Inexact Simplification of Symbolic Regression Expressions with Locality-
sensitive Hashing

Guilherme Seidyo Imai Aldeia  0002-0102-4958 Federal University of ABCSanto
AndreSão PauloBrazil<EMAIL_ADDRESS>,  Fabrício Olivetti de
França  0000-0002-2741-8736 Federal University of ABCSanto AndreSão
PauloBrazil<EMAIL_ADDRESS>and  William G. La Cava
0000-0002-1332-2960 Boston Children’s HospitalHarvard Medical
SchoolBostonMassachusettsUSA<EMAIL_ADDRESS>
###### Abstract.

Symbolic regression (SR) searches for parametric models that accurately fit a
dataset, prioritizing simplicity and interpretability. Despite this secondary
objective, studies point out that the models are often overly complex due to
redundant operations, introns, and bloat that arise during the iterative
process, and can hinder the search with repeated exploration of bloated
segments. Applying a fast heuristic algebraic simplification may not fully
simplify the expression and exact methods can be infeasible depending on size
or complexity of the expressions. We propose a novel agnostic simplification
and bloat control for SR employing an efficient memoization with locality-
sensitive hashing (LHS). The idea is that expressions and their sub-
expressions traversed during the iterative simplification process are stored
in a dictionary using LHS, enabling efficient retrieval of similar structures.
We iterate through the expression, replacing subtrees with others of same hash
if they result in a smaller expression. Empirical results shows that applying
this simplification during evolution performs equal or better than without
simplification in minimization of error, significantly reducing the number of
nonlinear functions. This technique can learn simplification rules that work
in general or for a specific problem, and improves convergence while reducing
model complexity.

locality sensitive hashing, simplification, symbolic regression, genetic
programming

††copyright: none††ccs: Computing methodologies Symbolic and algebraic
algorithms††ccs: Mathematics of computing Genetic programming

##  1\. Introduction

Symbolic regression (SR) addresses the challenge of jointly optimizing the
parameters and structure of a function. Given a set of $d$-dimensional inputs
$\mathcal{X}$ and target outputs $\mathbf{y}$, it solves
$\mathbf{y}\approx\mathbf{\hat{y}}=\hat{f}(\mathcal{X},\mathbf{\hat{\theta}})$,
typically by minimizing the difference between $\mathbf{y}$ and
$\mathbf{\hat{y}}$ while concurrently prioritizing simplicity (La Cava et al.,
2021). Since first proposed by Koza as an application of genetic programming
(GP) (Koza, 1994), it has been successfully used in several fields, such as
clinical decision support (La Cava et al., 2023), financial modeling (Luo and
Yu, 2023), aerospace engineering (La Cava et al., 2016), and physical sciences
(Angelis et al., 2023).

Despite its success, SR is an NP-hard problem (Virgolin and Pissis, 2022),
meaning that searching for the best regression model is computationally
inefficient unless P=NP is proved. The search space is vast, containing
isomorphic mathematical expressions (Burlacu et al., 2021), introns (parts of
the model that do not influence predictions) (Affenzeller et al., 2014), bloat
(growth in model size with unjustified improvement in loss) (Luke and Panait,
2006), and model overparameterization (excessive number of parameters to tune)
(de Franca and Kronberger, 2023). While these do not directly affect model
accuracy, they can inflate model size, decreasing simplicity and
interpretability.

There are several different approaches in the literature for tackling this
problem, such as automatic simplification of models (Helmuth et al., 2017),
parametric rules to rewrite expressions (Kulunchakov, 2017), Bayesian loss
metric for model selection (Bomarito et al., 2022), constrained search space
by restricting model structure (de Franca and Aldeia, 2021), or application of
an exact simplification procedure such as equality saturation (de Franca and
Kronberger, 2023). Although all of those have their own benefits, they also
have limitations, chiefly the additional computational cost and the need to
manually write the algebraic simplification rules.

We propose a technique to dynamically build the simplification rules to
address these limitations by memoizing observed equivalences with hashing. In
short, we build a hash table where the key is created using locality-sensitive
hashing (LHS) (Gionis et al., [n. d.]) based on the prediction vector, and the
value is the smallest observed subtree corresponding to that vector. LHS is
often used to efficiently retrieve nearest-neighbor points in a database
system (Jafari et al., 2021). By analogy, our proposal transforms expressions
into similar expressions within the phenotype (i.e., behavior) space that are
smaller.

When integrating and applying the simplification into every expression
throughout the generations, we observed benefits such as faster convergence
and reduced mean squared error. The size of the returned expression remained
the same, but its complexity was significantly reduced when considering the
use and chaining of nonlinear functions. Furthermore, we analyzed the
expressions identified as equivalent and noticed that the algorithm
successfully captures many known algebraic identities.

The paper is organized as follows. Section 2 provides an overview of related
work in bloat control, hashing, and simplification methods in SR. Section 3
introduces the application of Locality-Sensitive Hashing (LSH) in our
simplification method. Section 4 details simplifying expressions through
memoization with LSH. Section 5 outlines the experimental methods, including
the SR framework used to test the method. Section 6 presents and discusses
empirical findings, focusing on the impact of our approach on solution
quality, expression size, and eliminating unnecessary operations. Finally,
Section 7 draws conclusive remarks, summarizing key contributions and
suggesting future work.

##  2\. Related work

Helmuth et al. (Helmuth et al., 2017) proposed an automatic simplification in
the program synthesis context by randomly removing subtrees and accepting the
change if that did not affect the final prediction. Burlacu et al. (Burlacu et
al., 2021) explored the idea of hashing an SR tree using some basic algebraic
rules for handling commutative operations, such that two equivalent subtrees
are hashed to the same value. Nguyen and Chu explored indirect simplification
through mutation (Nguyen and Chu, 2020), pruning a population percentage by
replacing subtrees with a newly small random tree with similar semantics.

Some previous work focuses on sets of rules to perform simplification.
Kulunchakov (Kulunchakov, 2017) defined equivalent algebraic models as those
that produce the same outputs over a small range and by evolving expressions
with GP to use as replacements. In (de Franca and Kronberger, 2023), de França
and Kronberger proposed using equality saturation, an enumerative
simplification algorithm, to remove redundant parameters of symbolic
expressions. They noticed that overparametrization and unnecessary complexity
are predominant in current SR algorithms. Some attempts rely on something
other than the manipulation of symbols. Bomarito et al. (Bomarito et al.,
2022) proposed to reduce bloat by using a custom Bayesian fitness metric with
regularization.

Contrary to previous work, our approach does not rely on sets of rules or
expensive computing resources. We propose a data-driven and computationally
efficient way of inexact simplification that can be embedded into any GP
framework, being agnostic because it only requires slicing the expressions and
replacing subtrees.

##  3\. Locality-Sensitive Hashing

Locality-sensitive Hashing (LSH) was first introduced in (Gionis et al., [n.
d.]) as a technique designed to efficiently find approximate neighbors in
high-dimensional spaces through the usage of hash functions that preserve
local proximity (Jafari et al., 2021). The main idea is to hash input vectors
so that similar vectors are more likely to be mapped to the same hash bucket,
while very distinct vectors are less likely to do so. Figure 1 illustrates
this process.

Figure 1. Given a set of vectors (i.e. the predictions), similar predictions
are mapped to the same hash. The two highlighted vectors present close values
in this example and are mapped into the same hash.

Here, we employ the SimHash LSH method as a proof of concept (Charikar, 2002),
as it has a straightforward implementation and requires few lines of code to
be incorporated into existing frameworks. This results in a trade-off between
computational efficiency and accuracy, beneficial in scenarios where exact
similarity search becomes impractical (Jafari et al., 2021) due to the curse
of dimensionality (Chávez et al., 2001).

Given a hash size of $b$ bits and a set of $d$-dimensional data
$\\{x_{i}\in\mathbb{R}^{d}\\}$, we first stipulate the hash size as $b$ bits.
Then, we create a plane $\mathbf{P}\in\mathbb{R}^{b\times d}$ where each
$\mathbf{P}_{(i,j)}\sim\mathcal{N}(0,1)$.

Whenever we want to query a data point $x_{i}$, we first calculate the matrix
multiplication $\mathbf{P}\cdot x_{i}$, resulting in the vector
$\mathbf{q}\in\mathbb{R}^{b\times 1}$, and the hash $h(x_{i})$ is calculated
as

$h(x_{i})_{j}=\begin{cases}1&q_{j}>0\\\ 0&\text{otherwise}\end{cases}$

This forms a bit string that is used as the key to the hash table. The main
property of this hash function is that the probability of two hashes being
equal, i.e., $Pr[h(x)==h(y)]=1-\frac{\theta(x,y)}{\pi}$, is proportional to
their cosine similarity, and cosine similarity is proportional to the
normalized $l_{2}$-euclidean distance.

Every hash table entry will store all queried objects with that same hash
value. After inserting many objects, similar objects will be clustered around
the same keys. The higher the number of bits used to generate the hash key,
the larger the number of less dense clusters, increasing the accuracy of the
similarity estimation.

##  4\. Simplifying expressions by memoization

The idea of inexact simplification consists of having a simplification table
where the key is the SimHash (as described in §3), and the values are a list
of expressions hashed to that particular key.

In the first step, we evaluate the expression, keeping a trace of the
evaluation at every node. At this point, every node will contain a vector of
predictions corresponding to the evaluation of that subtree. In the next step,
we traverse the tree again 111In practice, we only need to traverse the tree
once. hashing these vectors into the binary string key. Finally, if this key
contains any element in the hash table and the closest value to this subtree
is within a threshold, we replace this subtree with the smallest tree in this
table entry. If there is no entry for this key, we create a new entry with
this subtree. Figure 2 depicts the proposed algorithm to use LSH to simplify
symbolic expressions.

We force every constant vector to have the same hash by setting the prediction
to zero if the variance of the vector is zero. This avoids growing the hash
table unnecessarily. The threshold also alleviates the fact that nonlinear
equations can have non-unique solutions, so they are considered equivalent as
long as the predictions are within the threshold. Algorithm 1 describes the
initialization of the table, and Algorithm 2 describes the simplification
process.

Figure 2. In the first stage ($1$), we have a simplification table with only
the problem variables plus the constant. Every node is seen as the root of a
subtree and can generate a prediction vector. The second stage ($2$) uses the
predictions to get hash values for each node, updating the simplification
table. Finally, we get the simplified tree by replacing the nodes with the
smallest subtree of the same hash in the simplification table. Algorithm 1
initialize_table

0: Training data points $(\mathcal{X}^{t},\mathbf{y}^{t})$, single node
constant tree cte

0: simplification table st

1: $\texttt{st}\leftarrow\text{ empty mapping of (key : value)}$

2: for $\texttt{terminal}\in\\{\texttt{cte}\\}\cup\\{x\in\mathcal{X}^{t}\\}$
do

3: $\texttt{pred}\leftarrow\texttt{terminal}.\text{predict}(\mathcal{X}^{t})$

4: $\texttt{lhs}.\text{index}(\texttt{pred})$

5: $\texttt{hash},d\leftarrow\texttt{lhs}.\text{query}(\texttt{pred})$

6: $\texttt{st}[\texttt{hash}]=[\texttt{terminal}]$

7: return st

Algorithm 2 hash_simplify

0: individual ind, simplification table st, lhs instance lhs, tolerance $\tau$

0: simplified version of the individual $n$

1: for $\texttt{subtree}\in\texttt{ind}$ do

2: $\texttt{pred}\leftarrow\texttt{subtree}.\text{predict}(\mathcal{X})$

3: if $\text{Var}(\texttt{pred})=0$ then

4: $\texttt{pred}\leftarrow\texttt{pred}\times 0.0$

5: $\texttt{hash},d\leftarrow\texttt{lhs}.\text{query}(\texttt{pred})$

6: if $\texttt{hash}\in\texttt{st}\text{ and }d\leq\tau$ then

7:
$\texttt{st}[\texttt{hash}]\leftarrow\texttt{st}[\texttt{hash}]\cup\\{\texttt{subtree}\\}$

8: $\texttt{subtree}\leftarrow\text{argmin}\text{ size}(\texttt{tree})\text{
for }\texttt{tree}\in\texttt{st}[\texttt{hash}]$

9: else if $\texttt{hash}\not\in\texttt{st}$ then

10: $\texttt{lhs}.\text{index}(\texttt{pred})$

11: $\texttt{st}[\texttt{hash}]=[\texttt{subtree}]$

12: return ind

When simplifying the expression, we can traverse the tree either top-down or
bottom-up since we apply the replacements on the fly. The order of traversal
can generate different simplifications. The advantage of the top-down approach
is that it prunes large subtrees first (if it finds a hash entry in the first
levels). This may lead to fewer nodes being visited as it may stop at an
earlier level. On the other hand, the bottom-up traversal may require more
steps, as a node simplified at the bottom level may trigger a new
simplification at the upper level. Nevertheless, this fine-grained
simplification may lead to larger simplifications after simplifying the
smaller branches.

This simplification will not always return an algebraically equivalent
expression but rather an approximation. By imposing a maximum distance
threshold, we mitigate this issue by guaranteeing that this procedure will
replace subtrees with similar semantics. This is an advantage for practical
applications since we favor simpler expressions at the expense of minor
differences in the predictions.

##  5\. Methods

We implemented a standard evolutionary algorithm using the DEAP framework
(Fortin et al., 2012). The individuals are randomly initialized using the PTC2
method (Luke, 2000). Then, iteratively, we perform a fixed number of
generations of tournament selection with a tournament size of $3$. Possible
variations operators are the crossover and mutations insert node, remove node,
replace node, and replace subtree.

Three variants were implemented: without simplify; bottom up, and top down.
Simplification is done on the initial population and every offspring generated
by the variation operators — this way, we guarantee that every individual is
simplified at least once. The individuals also go into the nonlinear parameter
optimization method Levenberg-Marquardt (Levenberg, 1944; Marquardt, 1963)
algorithm using Scipy (Virtanen et al., 2020), which was shown to be effective
in previous SR algorithms (Aldeia and de França, 2022; Kommenda et al., 2019;
Worm and Chiu, 2013). After simplifying, we repeat the parameter optimization.

Our hash method is probabilistic (due to plane initialization); thus, the hash
size is set to avoid collisions. We tried to increase the hash size by powers
of two until the simplification table would not have any collision at its
initialization step. During initial experiments, we found that if the initial
table has a hash collision for the features or constant, the simplification
may replace features with a constant, which is undesirable unless a feature is
almost constant.

The threshold was set to a fixed value based on the smallest train MSE error
in preliminary experiments over all datasets and set to $0.01$, so it is one
order of magnitude below all the train errors. Population size and number of
generations were set so most runs would finish under a $3$ wall clock hours.
Table 1 describes the hyper-parameters used in the experiments.

Table 1. Symbolic regression algorithms hyper-parameters. Parameter | Value
---|---
pop size ($S$) | $80$
max gen ($G$) | $200$
max depth ($\text{max}_{d}$) | $7$
max size ($\text{max}_{s}$) |  $128$ ($2^{7})$
tolerance ($\tau$) | $1e-2$
hash_len |  $256$ bits
probabilities |  $1/5$ for each variation operator
objectives | [error (MSE), size (# nodes))]
Function set | [$+$, $-$, $*$, $\frac{\cdot}{\cdot}$, $|\cdot|$, $\cos^{-1}$, $\sin^{-1}$, $\tan^{-1}$,
|  $\cos$, $\sin$, $\tan$, $e^{(\cdot)}$, $\mathtt{min}$, $\mathtt{max}$,
|  $\log$, $\log{(1+\cdot)}$, $\exp{(1+\cdot)}$, $\sqrt{|\cdot|}$,
$(\cdot)^{2}$]

We used a selection of datasets to analyze the effect of simplification
throughout the evolutionary process. Table 2 shows the name and dimensionality
of the datasets used. We should note that our approach is agnostic to GP
implementation and the choice of LSH. We have chosen the basic implementations
to highlight the effects of such simplifications.

Table 2. Dimensionality of the six datasets used to perform an in-depth analysis. Dataset | # samples | # features
---|---|---
Airfoil | $1503$ | $5$
Concrete | $1030$ | $8$
Energy Cooling | $768$ | $8$
Energy Heating | $768$ | $8$
Housing | $506$ | $13$
Yacht | $308$ | $6$

The loss function is the mean squared error (MSE) between the predictions
$\mathbf{\widehat{y}}=f(\mathcal{X})$ and observed values $\mathbf{y}$:

(1)
$\text{MSE}(\mathbf{\widehat{y}},\mathbf{y})=\frac{1}{d}\sum_{i=1}^{d}\left(\widehat{y}_{i}-y_{i}\right)^{2}.$

As a measurement of simplicity, we also use the concept of complexity by La
Cava et al. (La Cava et al., 2019), defined for a node $n$ with $k$ arguments
as the recursive combination of complexity of children with its root/head
node:

(2) $C(n)=c_{n}*(\sum_{a=1}^{k}C(a)).$

By assigning high complexity values to hard-to-interpret operations, we can
measure —recursively— how this propagates through the tree. The complexity for
the operators is described in Table 3.

Table 3. Complexity of each operator. Complexity | Operators
---|---
2 |  $+$, $-$, $\mathtt{cte}$
3 |  $*$, $\mathtt{max}$, $\mathtt{min}$, $(\cdot)^{2}$, $|\cdot|$
4 |  $\frac{\cdot}{\cdot}$, $\sqrt{|\cdot|}$, $e^{(\cdot)}$
5 |  $\exp{(1+\cdot)}$, $\cos$, $\sin$, $\tan$
6 |  $\cos^{-1}$, $\sin^{-1}$, $\tan^{-1}$
8 | $\log{(1+\cdot)}$
9 | $\log$

Each method was run 30 times with different split seeds for each dataset on
the same hardware. The data was divided into three partitions: $50\%$ as train
(visible to the algorithm to perform the parameter and function optimization);
$25\%$ as validation (used to assess the loss during the evolution, but not
used during train); and $25\%$ test (held-out data used to obtain the final
values for the experiments). The validation split is also used to pick the
final model returned by the algorithm.

Statistical comparisons, when reported, use the non-parametric Wilcoxon test
with Holm-Bonferroni correction, and all comparisons made are explicitly
depicted in the figures. Table 4 shows the annotations used to show
statistical significance in the plots. When an annotation is shown as “*
(ns)”, it shows a statistical significance of one asterisk, but after
correction, it becomes non-significant.

Table 4. p-value annotations and their correspondences, after applying the alpha correction. Annotation | p-value
---|---
ns | $5\times 10^{-2}<\text{p}\leq 1.0$
| $1\times 10^{-2}<\text{p}\leq 5\times 10^{-2}$
* | $1\times 10^{-3}<\text{p}\leq 1\times 10^{-2}$
** | $1\times 10^{-4}<\text{p}\leq 1\times 10^{-3}$
*** |  $\text{p}\leq 1\times 10^{-4}$

All data and the source code for implementations, experiments, and post-
processing analysis are available at https://github.com/gAldeia/hashing-
symbolic-expressions.

##  6\. Results and Discussion

In this section we analyze different aspects of the experiment’s results.
First, we verify whether the simplification accelerates the convergence of GP
to a good local optimum; next, we compare the number of simplifications
performed by each traversal strategy; we show the distribution of the average
size, complexity, and goodness-of-fit of the final solutions. We also show the
relative difference of the solutions under these same criteria when paired
with the individual runs. Finally, we compare the differences in runtime and
explore some hand-picked simplification rules generated throughout the runs.

###  6.1. Convergence

The data was split into training and validation sets. While the model used the
training partition to perform parameter and model optimization, the validation
partition was used to compute the MSE with unseen data. Figure 3 reports the
minimum validation error during the evolution, estimated using the mean of 30
runs.

Figure 3. Validation error of the best individual during the evolution. $y$
axis is in log-scale.

These results show that the versions with simplification often outperform the
traditional GP throughout the run, leading to a better local optimum. The only
exception is the Yacht dataset, in which the top-down strategy performs worse
than the bottom-up and the version without simplification. In every other
dataset, both traversal strategies present similar performance.

The two traversal strategies, as conjectured before, perform a different
number of simplifications during the evolutionary process, as we can see in
Figure 4. The bottom-up strategy performs around $50\%$ more simplifications
with a little intersection in the estimated confidence interval. We believe
that the number of simplifications appears to diminish in later generations as
we effectively remove bloated and redundant subtrees; however, we also start
to have more specialized and complex models, which are harder to simplify.

Figure 4. Number of simplifications performed in each generation.

###  6.2. Goodness-of-fit and size trade-off

At the end of the run, every algorithm picks the final model with the best
performance on the validation split. Figures 5, 6, and 7 report the size,
complexity, and MSE on the test partition, respectively.

Figure 5. Final size of the solutions found by each method. The simplification
methods showed no statistically different significance related to without any
simplification. Figure 6. Final complexity of the solutions. There are several
cases where simplification can improve complexity.

Regarding the size, we cannot reject the null hypothesis that there are not
differences between the approaches — a counter-intuitive result, as the
simplification is expected to reduce the size of the expressions. However,
looking at the complexity boxplots, we observe a smaller variation (for the
best) using simplification strategies and the rejection of the null hypothesis
with a p-value between $[10^{-3},10^{-2}]$. As the models are simplified
during the evolution, it frees up space (within the limit of maximum nodes) to
accommodate more useful sub-expressions. As a by-product, the generated
expressions are also less complex when considering the definition of recursive
complexity. We also hypothesize that the simplification opens up space for
further improving the expressions, and the evolutionary process efficiently
takes care of that by generating expressions of the same size but with better
performance.

We find differences in complexity for the datasets Airfoil, Concrete, Energy
Cooling, Housing, and Yacht. Even though they are equivalent in size, the
simplification process led to finding solutions with better complexity without
explicitly trying to minimize it. Note that the simplified expression does not
exhibit higher errors than the original. Regarding the test set MSE, Airfoil,
Concrete, and Energy Cooling datasets show statistically significant
improvements in the bottom-up strategy. The top-down strategy shows
improvements only for Concrete.

Figure 7. MSE on the test partition. Simplification led to better performance
in error, with less complex models.

The simplification strategy shows only small differences and no clear better
option in terms of the results, except for the number of simplifications. The
bottom-up strategy will always iterate through the entire tree, while the top-
down strategy can cut large branches right away, ending up with a smaller
number of simplifications.

We believe that Yacht was the most challenging dataset due to the test MSE
error scale shown in Fig. 7, as it is closer to the threshold than any other
algorithm. Parameter optimization, especially the inexact simplification
threshold, seems important to be adjusted based on the error scale, and we
plan to investigate it further.

###  6.3. Relative change

Even though the differences in MSE seem modest, those are considering the mean
and median of the distribution. A better way to verify the benefits of the
simplification strategy is to pair the $30$ runs based on their seed and
calculate the percentage of variation between the simplification methods and
without any simplification (i.e., the baseline). This way, the variation
between datasets can be aggregated, and an overall measurement and a one-sided
$t$-test can be applied to verify whether the mean of the relative change is
different from zero. Figure 8 reports the variations for the bottom-up and
top-down strategies.

(a)  (b)  (c)

Figure 8. Percentage variation of size (8a), complexity (8b) and MSE on test
(8c) compared to without any simplification.

A t-test for the mean of the distributions was performed for each subfigure
with $180$ degrees of freedom ($6$ datasets and $30$ runs each).

Regarding size, we see the distribution with a median of $2.43\%$ for bottom-
up and $-2.13\%$ for top-down, but both presented a p-value greater than
$0.05$, so we cannot reject the null hypothesis. Complexity shows a median of
$-104.06\%$ and $-111.34\%$, with p-values of $2.94\times 10^{-7}$ and
$1.59\times 10^{-6}$ for bottom-up and top-down, respectively. This indicates
that for each individual run, we observe a reduction in complexity compared to
the baseline. For MSE, the medians are $-18.21\%$ and $-20.32\%$, and the
p-values are $8.165\times 10^{-7}$ and $1.85\times 10^{-5}$. Again, we can
reject the null hypothesis and conclude the simplification reduces the error
by $20\%$ on average.

###  6.4. Analysis of hashes and individuals

We performed a single run on the Yacht dataset to obtain a few insights on how
simplification is replacing nodes. We chose it because it has no statistically
significant differences in size and error and is also low-dimensional (for the
sake of the example). At the end of the run, we had a total of $5144$ hash
entries created from $7324$ expressions. This subsection will review some of
the entries of the simplification table. An entry is a tuple of a hash and a
list of equivalent trees. The hash will be truncated to simplify the
discussion, and expressions will be shown as string-formatted versions of the
expressions, ordered by smallest to largest — meaning that any of the subtrees
would be replaced by the first.

Let us take a look into the first case:

1010110111001101... \- square(x_5) \- multiply(x_5, x_5) \-
absolute(square(x_5)) \- maximum(square(x_5), x_0) \- maximum(add(-15.455,
x_1), square(x_5))

We first notice that, without explicit rules, our method started to replace
`multiply(x_5, x_5)` by `square(x_5)`, a shorter representation. It also
learned that the absolute value of the square is always positive, so
`absolute(square(x_5))` could also be simplified to `square(x_5)`. Some
simplifications there are based on data: that $x_{5}^{2}$ always dominates
$x_{0}$ in the $\mathtt{max}$ function. Algebraic rules would not capture this
simplification.

Some other interesting cases arise. Here, we have a permutation of arguments
on a $4$-ary commutative operation, as well as the chain of commutative
operations:

1110001011011111... \- multiply(x_1, x_7, x_0, x_4) \- multiply(x_0, x_4, x_1,
x_7) \- multiply(x_1, x_0, multiply(x_4, x_7))

Finally, some other cases are the simplification of redundant operations (as
in `minimum(x_2, x_2)`), the usage of the identity value of an operation as
argument (as in `add(0.0, x_2)`), and the chaining of $f$ with its $f^{-1}$
(as in `log(exp(x_2))`):

1010101111001001... \- x_2 \- absolute(x_2) \- minimum(x_2, x_2) \-
minimum(x_2, x_6) \- minimum(x_2, x_5) \- add(0.0, x_2) \- log(exp(x_2)) \-
sqrtabs(square(x_2)) \- maximum(-523.249, x_2)

Figure 9 shows the smallest expression found by the bottom-up strategy and
with GP without simplification for the Yacht dataset.

Figure 9. Smallest expression found by bottom-up (left) and without
simplification (right) for the Yacht dataset. The MSE for each expression was
$1.98$ using the bottom-up simplification and $2.08$ without simplification.

The bottom-up model obtained an MSE on the test set of $1.98$ with $9$ nodes,
and GP without simplification obtained a test error of $2.08$ using $15$
nodes. We can see more complex constructs when not applying simplification, as
well as the chaining of $\sqrt{\cdot}$ and $(\cdot)^{2}$.

The yacht dataset has errors that are one order of magnitude greater than the
simplification threshold, and besides not showing improvements in error, it
had improvements in complexity. By analyzing one single run, we proved that
the benefits of our simplification methods extend beyond size and error. The
method was able to minimize complexity without being explicitly told to do so.

###  6.5. Execution time

Figure 10 reports the execution time for each algorithm.

Figure 10. Variation of execution time (in seconds) for each method. The
subplots are sharing the $y$ axis.

We notice that the simplification methods take more time to run than without
any simplification, with statistical differences for all but the last dataset.
This happens because we perform a nonlinear optimization twice for every
individual, as they are re-optimized after the simplification, indicating that
the method would benefit from caching recent information to avoid re-
optimizing the entire tree after every simplification.

##  7\. Conclusions

In this paper, we propose an inexact simplification method using LSH to learn
substitution rules that are either well-known algebraic identities or
simplifications specific to the dataset domain. LSH efficiently stores and
queries expressions that behave similarly in the phenotypical space, enabling
us to apply the simplification process for every sampled expression throughout
the evolution.

With this approach, we can experimentally analyze the influence of
simplification and bloat control on the evolutionary process. The empirical
results showed that, on average, the versions with simplification returned
more accurate expressions of the same size but with less complex construct.
Comparing runs departing from the same seed, we observed a median of $20\%$
reduction in the mean squared error when using simplification.

This approach has some drawbacks. For example, the hash function can only
guarantee that similar expressions are clustered with high probability. We can
eventually include expressions with distinct behavior in the wrong cluster,
but this should be rare. Another issue is that the simplification is inexact,
so it can perform substitutions that slightly change the behavior of the
function or that are exact only on the training data.

On the other hand, since this is a data-driven approach, it can learn the
rules on the fly without any need to pre-determine the algebraic identities.
It can also learn rules specific to the dataset (e.g., $x_{1}$ is always
smaller than $x_{2}$).

As for the next steps, we intend to improve the influence of simplification by
making a “warm-up” step, where random individuals are generated and used to
initialize the table; we will also evaluate the influence of performing
simplification sporadically, only for a selection of individuals, or only at
the final generation; and how does the threshold affect the results. We will
also test some other hash functions with better guarantees than SimHash.
Finally, we will integrate this approach into a high-performance GP
implementation to make it possible to run more detailed tests, also including
other simplification methods into the benchmark.

###### Acknowledgements.

W.G.L. was supported by National Institutes of Health (NIH) grant
R00-LM012926, and Patient Centered Outcomes Research Institute (PCORI)
ME-2020C1D-19393. F.O.F. is supported by Fundação de Amparo à Pesquisa do
Estado de São Paulo (FAPESP) grant 2021/12706-1, and Conselho Nacional de
Desenvolvimento Científico e Tecnológico (CNPq) grant 301596/2022-0. G.S.I.A.
is supported by Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
(CAPES) finance Code 001 and grant 88887.802848/2023-00.

## References

  * (1)
  * Affenzeller et al. (2014) Michael Affenzeller, Stephan M Winkler, Gabriel Kronberger, Michael Kommenda, Bogdan Burlacu, and Stefan Wagner. 2014.  Gaining deeper insights in symbolic regression.  _Genetic Programming Theory and Practice XI_ (2014), 175–190.
  * Aldeia and de França (2022) Guilherme Seidyo Imai Aldeia and Fabrício Olivetti de França. 2022.  Interaction-Transformation Evolutionary Algorithm with Coefficients Optimization. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_ (Boston, Massachusetts) _(GECCO ’22)_. Association for Computing Machinery, New York, NY, USA, 2274–2281.  https://doi.org/10.1145/3520304.3533987
  * Angelis et al. (2023) Dimitrios Angelis, Filippos Sofos, and Theodoros E. Karakasidis. 2023.  Artificial Intelligence in Physical Sciences: Symbolic Regression Trends and Perspectives.  _Archives of Computational Methods in Engineering_ 30, 6 (April 2023), 3845–3865.  https://doi.org/10.1007/s11831-023-09922-z
  * Bomarito et al. (2022) G. F. Bomarito, P. E. Leser, N. C. M. Strauss, K. M. Garbrecht, and J. D. Hochhalter. 2022.  Bayesian model selection for reducing bloat and overfitting in genetic programming for symbolic regression. In _Proceedings of the Genetic and Evolutionary Computation Conference Companion_. ACM, Boston Massachusetts, 526–529.  https://doi.org/10.1145/3520304.3528899
  * Burlacu et al. (2021) Bogdan Burlacu, Lukas Kammerer, Michael Affenzeller, and Gabriel Kronberger. 2021.  Hash-Based Tree Similarity and Simplification in Genetic Programming for Symbolic Regression.  https://doi.org/10.1007/2F978-3-030-45093-9_44 arXiv:2107.10640 [cs].
  * Charikar (2002) Moses S Charikar. 2002.  Similarity estimation techniques from rounding algorithms. In _Proceedings of the thiry-fourth annual ACM symposium on Theory of computing_. 380–388.
  * Chávez et al. (2001) Edgar Chávez, Gonzalo Navarro, Ricardo Baeza-Yates, and José Luis Marroquín. 2001.  Searching in metric spaces.  _ACM Comput. Surv._ 33, 3 (sep 2001), 273–321.  https://doi.org/10.1145/502807.502808
  * de Franca and Aldeia (2021) F. O. de Franca and G. S. I. Aldeia. 2021.  Interaction–Transformation Evolutionary Algorithm for Symbolic Regression.  _Evolutionary Computation_ 29, 3 (09 2021), 367–390.  https://doi.org/10.1162/evco_a_00285 arXiv:https://direct.mit.edu/evco/article-pdf/29/3/367/1959462/evco_a_00285.pdf
  * de Franca and Kronberger (2023) Fabricio Olivetti de Franca and Gabriel Kronberger. 2023.  Reducing Overparameterization of Symbolic Regression Models with Equality Saturation. In _Proceedings of the Genetic and Evolutionary Computation Conference_ (Lisbon, Portugal) _(GECCO ’23)_. Association for Computing Machinery, New York, NY, USA, 1064–1072.  https://doi.org/10.1145/3583131.3590346
  * Fortin et al. (2012) Félix-Antoine Fortin, François-Michel De Rainville, Marc-André Gardner, Marc Parizeau, and Christian Gagné. 2012.  DEAP: Evolutionary Algorithms Made Easy.  _Journal of Machine Learning Research_ 13 (jul 2012), 2171–2175.
  * Gionis et al. ([n. d.]) Aristides Gionis, Piotr Indyk, and Rajeev Motwani. [n. d.].  Similarity Search in High Dimensions via Hashing.  ([n. d.]).
  * Helmuth et al. (2017) Thomas Helmuth, Nicholas Freitag McPhee, Edward Pantridge, and Lee Spector. 2017.  Improving generalization of evolved programs through automatic simplification. In _Proceedings of the Genetic and Evolutionary Computation Conference_. ACM, Berlin Germany, 937–944.  https://doi.org/10.1145/3071178.3071330
  * Jafari et al. (2021) Omid Jafari, Preeti Maurya, Parth Nagarkar, Khandker Mushfiqul Islam, and Chidambaram Crushev. 2021.  A Survey on Locality Sensitive Hashing Algorithms and their Applications.  http://arxiv.org/abs/2102.08942 arXiv:2102.08942 [cs].
  * Kommenda et al. (2019) Michael Kommenda, Bogdan Burlacu, Gabriel Kronberger, and Michael Affenzeller. 2019.  Parameter identification for symbolic regression using nonlinear least squares.  _Genetic Programming and Evolvable Machines_ 21, 3 (Dec. 2019), 471–501.  https://doi.org/10.1007/s10710-019-09371-3
  * Koza (1994) John R Koza. 1994.  Genetic programming as a means for programming computers by natural selection.  _Statistics and computing_ 4 (1994), 87–112.
  * Kulunchakov (2017) Kulunchakov. 2017.  Creation of parametric rules to rewrite algebraic expressions in Symbolic Regression.  _Machine Learning and Data Analysis_ 3, 1 (2017), 6–19.  https://doi.org/10.21469/22233792.3.1.01
  * La Cava et al. (2016) William La Cava, Kourosh Danai, Lee Spector, Paul Fleming, Alan Wright, and Matthew Lackner. 2016.  Automatic identification of wind turbine models using evolutionary multiobjective optimization.  _Renewable Energy_ 87 (2016), 892–902.  https://doi.org/10.1016/j.renene.2015.09.068 Optimization Methods in Renewable Energy Systems Design.
  * La Cava et al. (2021) William La Cava, Patryk Orzechowski, Bogdan Burlacu, Fabricio de França, Marco Virgolin, Ying Jin, Michael Kommenda, and Jason Moore. 2021.  Contemporary Symbolic Regression Methods and their Relative Performance. In _Proceedings of the Neural Information Processing Systems Track on Datasets and Benchmarks_ , J. Vanschoren and S. Yeung (Eds.), Vol. 1. Curran.
  * La Cava et al. (2019) William La Cava, Tilak Raj Singh, James Taggart, Srinivas Suri, and Jason H. Moore. 2019.  Learning concise representations for regression by evolving networks of trees.  http://arxiv.org/abs/1807.00981 arXiv:1807.00981 [cs].
  * La Cava et al. (2023) William G. La Cava, Paul C. Lee, Imran Ajmal, Xiruo Ding, Priyanka Solanki, Jordana B. Cohen, Jason H. Moore, and Daniel S. Herman. 2023.  A flexible symbolic regression method for constructing interpretable clinical prediction models.  _npj Digital Medicine_ 6, 1 (June 2023), 107.  https://doi.org/10.1038/s41746-023-00833-8
  * Levenberg (1944) Kenneth Levenberg. 1944.  A method for the solution of certain non-linear problems in least squares.  _Quarterly of applied mathematics_ 2, 2 (1944), 164–168.
  * Luke (2000) S. Luke. 2000.  Two fast tree-creation algorithms for genetic programming.  _IEEE Transactions on Evolutionary Computation_ 4, 3 (2000), 274–283.  https://doi.org/10.1109/4235.873237
  * Luke and Panait (2006) Sean Luke and Liviu Panait. 2006.  A Comparison of Bloat Control Methods for Genetic Programming.  _Evolutionary Computation_ 14, 3 (Sept. 2006), 309–344.  https://doi.org/10.1162/evco.2006.14.3.309
  * Luo and Yu (2023) Jiayi Luo and Cindy Long Yu. 2023.  The Application of Symbolic Regression on Identifying Implied Volatility Surface.  _Mathematics_ 11, 9 (2023).  https://doi.org/10.3390/math11092108
  * Marquardt (1963) Donald W Marquardt. 1963.  An algorithm for least-squares estimation of nonlinear parameters.  _Journal of the society for Industrial and Applied Mathematics_ 11, 2 (1963), 431–441.
  * Nguyen and Chu (2020) Quang Uy Nguyen and Thi Huong Chu. 2020.  Semantic approximation for reducing code bloat in Genetic Programming.  _Swarm and Evolutionary Computation_ 58 (Nov. 2020), 100729.  https://doi.org/10.1016/j.swevo.2020.100729
  * Virgolin and Pissis (2022) Marco Virgolin and Solon P. Pissis. 2022.  Symbolic Regression is NP-hard.  (2022).  https://doi.org/10.48550/ARXIV.2207.01018 Publisher: arXiv Version Number: 3.
  * Virtanen et al. (2020) Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, İlhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. 2020.  SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python.  _Nature Methods_ 17 (2020), 261–272.  https://doi.org/10.1038/s41592-019-0686-2
  * Worm and Chiu (2013) Tony Worm and Kenneth Chiu. 2013.  Prioritized Grammar Enumeration: Symbolic Regression by Dynamic Programming. In _Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation_ (Amsterdam, The Netherlands) _(GECCO ’13)_. Association for Computing Machinery, New York, NY, USA, 1021–1028.  https://doi.org/10.1145/2463372.2463486


# The Evolution Of Centralisation on Cryptocurrency Platforms

Carlo Campajola  DLT Science Foundation, London, United Kingdom  University of
Zurich, Blockchain & Distributed Ledger Technologies, Department of
Informatics, Zürich, Switzerland  UZH Blockchain Center, Zürich, Switzerland
Raffaele Cristodaro  University of Zurich, Blockchain & Distributed Ledger
Technologies, Department of Informatics, Zürich, Switzerland  Francesco Maria
De Collibus  University of Zurich, Blockchain & Distributed Ledger
Technologies, Department of Informatics, Zürich, Switzerland  Tao Yan
University of Zurich, Blockchain & Distributed Ledger Technologies, Department
of Informatics, Zürich, Switzerland  Nicolò Vallarano  University of Zurich,
Blockchain & Distributed Ledger Technologies, Department of Informatics,
Zürich, Switzerland  UZH Blockchain Center, Zürich, Switzerland  Claudio J.
Tessone  University of Zurich, Blockchain & Distributed Ledger Technologies,
Department of Informatics, Zürich, Switzerland  UZH Blockchain Center, Zürich,
Switzerland<EMAIL_ADDRESS>
###### Abstract

More than ten years ago the blockchain was acclaimed as the solution to
overcome centralised trusted third parties for online payments. Through the
years the crypto-movement changed and evolved, although decentralisation
remained the core ideology and the necessary feature every new crypto-project
should provide. In this paper we study the concept of centralisation in
cryptocurrencies using a wide array of methodologies from the complex systems
literature, on a comparative collection of blockchains, in order to define the
many different levels a blockchain system may display (de-)centralisation and
to question whether the present state of cryptocurrencies is, in a
technological and economical sense, actually decentralised.

###### keywords:

Blockchain, Cryptocurrency, Networks, Centralisation

## Introduction

In the wake of the 2008 Great Financial Crisis, the whitepaper “Bitcoin: A
Peer-to-Peer Electronic Cash System” [1] was published by the pseudonymous
Satoshi Nakamoto. The paper began with a direct attack to the state of
electronic payments on the internet: a critique on the central role of third
parties to provide trust among users and the complete absence of non-
reversible payments online. After describing the problem the paper proceeds to
present Nakamoto’s solution, a relatively old [2] and up to then fringe
technology: the blockchain, a distributed and decentralised ledger where
information is maintained consistent across the network by a peer-to-peer
consensus protocol and secured via cryptography. Bitcoin was the first and
thus far most successful platform of what have become commonly known as
“cryptocurrencies”, digital assets that rely on cryptographic security to
solve the double-spending problem, typically through a decentralised ledger
rather than a centralised authoritative server.

Following Bitcoin’s success, many more cryptocurrency projects started, each
one with its own specific quirk yet characterised by the same common goal: to
build a decentralised payment system, available to anyone without the need of
reciprocal trust (or a third party providing it). For this reason the
proponents of Bitcoin and other cryptocurrencies typically call it a “truly
democratic” form of money [3], as opposed to the “tyrannical money” issued by
governments.

The main purpose of our study is to question whether the initial aspirations
behind the creation of Bitcoin have been fulfilled. As pointed out by Taleb
[4], Bitcoin and the likes suffer from design problems that lead to intrinsic
fragilities, which in turn can compromise their utility. In our work we
investigate these fragilities: we perform a large scale comparative analysis
of multiple cryptocurrency platforms, sourcing the data directly from the
respective blockchains, and adopt methods from network and complex systems
science to define and investigate the concept of decentralisation in
cryptocurrencies systems.

The blockchains we analyse are Bitcoin, Ethereum, Bitcoin Cash, Litecoin,
Dogecoin, Monacoin and Feathercoin. We analyse data ranging from the systems
inceptions until December 2020, adopting state of the art methodologies [5] to
transform the raw blockchain data into a meaningful dataset of economic
transactions between “entities”. Entities are intended to be the closest
possible representation of distinct economic agents on the blockchain: they
can correspond to individuals, groups of individuals or businesses that
operate in the system, coping with the pseudonymous nature of
cryptocurrencies.

The entities on the blockchain interact through transactions, i.e. by sending
tokens to one another to exchange value. This interaction mechanism is
naturally suitable for a network representation, which has been widely adopted
in the literature [6], where entities are mapped to nodes and directed links
are established following the transactions flow. This provides a new
perspective to study a cryptocurrency as an interconnected system of agents
[7] of which we are able to quantitatively define and measure the
centralisation. As an example, the emergence of a giant connected component
[8] in the transaction networks of all the cryptocurrencies under study
signals how all the users participate to the same economic community. Another
interesting point is the detection of a core component [9] of the network, a
subset of highly inter-linked nodes which keep the network together, taking a
middle-men positioning in the networks. Moreover we are able to measure the
wealth of entities and relate it to their position in the transaction
networks. Similar analyses have been performed in the past for the
“cumulative” network, i.e. the network containing all transactions that
happened up to a given point in history [6]: we go beyond by splitting the
time-frame in weekly time-windows, thus reducing the reciprocal impact of
transactions spread far apart in time. It is indeed not particularly
reasonable to consider in the same static network transactions which happened
over 10 years apart. A similar approach in this respect has been recently
taken for Bitcoin [10, 11], and we generalise their analysis to six more
platforms, providing an unprecedented quantitative overview of the crypto
market.

In the following section we describe the impact that the identification of
entities has on the structure of the blockchain data and of transaction
networks. We then focus on the networks and their global properties, such as
the distribution of degrees and the identification of the network core, and
then tackle the problem of mining power concentration and how it affects the
distribution of wealths in the system. We conclude by discussing the results.
For readability purposes the technical details about the data and methods are
reported in the Materials and Methods section, following the discussion.

## Results

Figure 1: (a) Total number of addresses appeared on blockchain as function of
total number of identified entities. Each plot point corresponds to the totals
measured on the same block, with weekly frequency. Axes are logarithmic and
the dashed line is reference for $y=x$. (b) Average number of addresses per
entity over time. Figure 2: Size of the largest Strongly Connected Component
in UTXO-based cryptocurrencies.

### Clustering matters.

We begin by analysing the effect of applying address clustering on UTXO-based
blockchain data. Figure 1a shows the relation between the number of entities,
identified by adopting the heuristic address clustering logic described in the
Materials and Methods section, and the number of addresses that have appeared
on the blockchain. Each data point refers to the totals observed up to a given
block, with weekly frequency, and time “flows” from the bottom left to the top
right of the panel. The results show strong similarities across the six
platforms considered: this consistency is expected, as all these platforms
share the same architecture in the address management protocols. New addresses
are continuously generated with each transaction, and more active entities
will accumulate more addresses on average. It is interesting to notice that
there are several “regimes” in Figure 1a, with the slope of the curve changing
over time. We plot this slope, i.e. the average number of addresses per
entity, as a function of time in Figure 1b. Three regimes can be identified in
the history of these cryptocurrencies: an early stage where the average grows,
a relatively stable period between 2014 and 2017, followed by a decline after
2018. Interestingly, the transition from one regime to the other is marked by
two of the well-known “crypto bubbles”, in 2013 and 2017, that were possibly
the drivers of these shifts [12]. The first saw the creation of multiple so-
called “alt-coins”, alternative cryptocurrencies running on their own
blockchains which aimed to capitalise on the large influx of funds in the
ecosystem, a class which includes all non-BTC assets in our analysis. In the
period between the bubbles the average number of addresses owned by entities
stayed at a relatively high value: relatively few new participants were
entering the system since public interest had declined after the bubble burst,
which means that transactions (and thus address creation) were primarily
involving pre-existing entities. The picture changed after the 2017-18 bubble,
when cryptocurrencies entered the mainstream of financial assets, receiving
serious consideration by markets and institutions and leading to the
consolidation of major service providers like leading exchanges Coinbase,
Binance, etc. Since then public attention for the crypto ecosystem has stayed
high and a large number of new entities entered the system, most of the times
controlling just one or two addresses since they wouldn’t use the blockchain
to operate many transactions anymore. Indeed after 2018 blockchains started to
experience congestion problems [13], i.e. blocks reached capacity and thus
adding new transactions to the blockchain became more costly. This created
incentives to operate off-chain, mostly through service providers or so-called
“layer 2” technologies like the Lightning Network [14], thus reducing the
average number of addresses per entity.

We can then consider the effect that address clustering has on the structure
of transaction networks. We measure the size of the largest Strongly Connected
Component (SCC) in the address networks and compare it to the one in the
entity networks, shown in Fig. 2 for the six cryptocurrencies of our analysis.
Such a metric is essential to measure the fragmentation of the economy: if
many nodes don’t belong to the largest SCC it is a significant sign of
decentralisation, as it means that there are no bridges across different
communities; on the other hand if the vast majority of nodes belongs to the
largest SCC it signals that such bridges exist and that a token can travel
from one side of the network to the other. It is clear the address networks do
not show the so-called “giant component” (i.e. a SCC that spans the whole
network), which would suggest that these economies are highly fragmented and
decentralised; however the illusion becomes apparent as soon as one looks at
entity networks, where the largest SCC spans almost the entire network for
most of the time. We should stress out the emergence of a Giant Connected
Component is a necessary yet not sufficient condition for the economy to be
centralised: a disconnected economy composed of isolated communities which
keep money from flowing around cannot be centralised as a whole. A notable
outlier in this is Dogecoin, where the largest SCC seems to be of about the
same size in both representations, spanning approximately half the network.
This observation then provides evidence that address clustering is a necessary
step to take to get meaningful results about the economic structure of
cryptocurrencies, as the obfuscation of identities through multiple addresses
significantly affects the observations. In the following we will only present
results on the entity networks for UTXO-based cryptocurrencies, unless
specified otherwise.

|  | BTC | LTC | DOGE | BCH | FTC | MONA | ETH
---|---|---|---|---|---|---|---|---
$\alpha$ | Minimum | 1.74 | 1.31 | 1.45 | 1.47 | 1.60 | 1.49 | 1.50
Maximum | 10.99 | 5.84 | 3.83 | 9.89 | 4.81 | 7.69 | 3.42
1\. Quartile | 2.42 | 2.43 | 2.45 | 2.28 | 2.33 | 2.46 | 1.68
3\. Quartile | 2.93 | 3.08 | 3.09 | 2.94 | 3.18 | 3.21 | 1.81
Median | 2.69 | 2.71 | 2.88 | 2.65 | 2.68 | 2.72 | 1.76
$D_{Par}$ | Median | 0.03 | 0.05 | 0.05 | 0.04 | 0.08 | 0.10 | 0.03
$D_{Bin}$ | Median | 0.35 | 0.41 | 0.42 | 0.37 | 0.37 | 0.41 | 0.43
Table 1: Summary statistics on exponents of power-law fit of degree
distribution on the weekly transaction networks. Figure 3: Assortativity
coefficient for weekly transaction networks.

### Degree distributions.

The degree of a node represents the number of counterparts that entity
exchanges tokens with, and is typically considered a measure of importance
within the network. What is particularly relevant is to consider the
distribution of degrees, as its shape is a direct consequence of the way in
which the networks form. The degree distribution has been shown to be strongly
skewed, akin to a power-law Pareto type distribution, for many traditional
economic and financial systems such as interbank markets [15], corporate
payments [16] and in experiments [17]. This has also been observed in several
analyses of cryptocurrency networks of transactions that represent the whole
history [6, 18], and our results broadly agree with the literature on the much
shorter weekly timescale we select. We estimate the maximum likelihood
parameters of a Pareto distribution and a binomial distribution for the
degrees, which would be consistent with the null hypothesis of a Barabasi-
Albert-type network or an Erdos-Renyi random network respectively, and find
that the former is a much better description of the data than the latter in
all of our samples. While we do not find that either distribution properly
fits the data - indeed a Kolmogorov-Smirnov test rejects both null hypotheses
at the $20\%$ level in the vast majority of weeks - we still find that the
Kolmogorov-Smirnov distance is much lower for a Pareto-type distribution
($D_{Par}$ in Table 1) rather than a binomial ($D_{Bin}$), hinting to the
presence of fat tails. In Table 1 we report the statistics for the exponent
$\alpha$ of a Pareto fit of the degree distribution, averaged over the whole
sample. We find that in general the power-law exponent is between 2.5 and 3
for the UTXO-based cryptocurrencies - for which heuristic address clustering
is available - and around 1.76 for Ether. This stark similarity across
platforms points towards a scale-free structure of these transaction networks,
with few hubs and large amounts of lowly connected nodes. This is further
confirmed by computing the assortativity coefficient, which we report in Fig.
3. This is typically negative, with a tendency for smaller platforms like
Monacoin and Feathercoin to show stronger disassortativity. This simple
analysis is itself consistent with a strong centralisation in the flow of
tokens, where the vast majority of transactions happens between low-degree
nodes and large intermediaries like exchanges, custodians and service
providers. Our observations largely agree with the evidence presented by [11]
on the Bitcoin transaction network, where the authors find that most of on-
chain transactions (excluding self-transactions, which we also exclude)
involve exchanges.

Figure 4: Fraction of nodes in the network core as a function of time.

### Core-periphery structure.

Economic and financial networks often exhibit the so-called “core-periphery
structure” [19, 9, 20]. This is a macroscopic property of the network, that
presents a split between a minority of nodes (the “core”) with a strong
connectivity between themselves and the remaining nodes of the network (the
“periphery”) that are mostly connected to core nodes and have relatively few
links to other peripheral nodes. We apply the core-periphery classification
algorithm from [21] on the weekly transaction networks time-series and then
consider the size of the core group as a fraction of the total size of the
network. We report this quantity for each weekly transaction network in Figure
4. We find that the relative size of the core has consistently decreased over
time in all the analysed cryptocurrencies before 2018, and since then it has
stabilised, excluding the particular cases of Monacoin and Feathercoin. The
fact that the relative size of the core of these networks has been shrinking
is further evidence that the cryptocurrency economy has been shifting towards
a centralised model, becoming much closer to the traditional financial system
that it criticised heavily in its early days. A marked core-periphery
structure points towards the transformation of the blockchain ledger into a
kind of “interbank market”, where few large intermediaries move funds on
behalf of their many clients much like bank transfers and brokerage happen in
traditional banking. Indeed a shrinking core corresponds to a bigger
periphery, i.e. the vast majority of entities (up to 99.99% in the case of
Bitcoin and Ethereum) is loosely connected to the rest of the network and
relies on a small minority to intermediate transactions. This structure has
been consolidating since 2018, consistent with our observations about the SCC
and the amount of addresses per entity that we previously discussed.

The exception here, represented by Monacoin and Feathercoin, is mostly due to
the drop in popularity these two platforms have experienced after the burst of
the 2018 crypto bubble. Monacoin has also suffered from attacks on its mining
protocol [22], and the market capitalisation of both coins has not recovered
to its 2018 peak. The size of the core of both cryptocurrencies is extremely
small (less than 5 nodes from 2018 onwards) but the total size of the network
is also relatively small, with few hundreds of active entities, thus leading
to the observed results.

### Mining concentration.

An analysis of centralisation on cryptocurrency platforms would not be
complete without reporting measures of mining power concentration. All
blockchains in this study are based on the Proof-of-Work (PoW) consensus
mechanism, where the right to add a new block to the blockchain is granted to
whoever finds the solution to a cryptographic puzzle. These entities are
typically called “miners”, and have an incentive to operate given by a
coinbase transaction that mints new tokens attributed directly to the miner.
The consistency of blockchain data relies on the assumption that mining power
is distributed and decentralised: if at any point in time a single miner (or a
pool of miners) holds more than $50\%$ of the total computational power
devoted to solving the PoW puzzle, the blockchain can be subjected to a so-
called “51% attack” where the majority miner writes false information on the
blocks (e.g. double spending transactions) without anybody being able to
counteract, since the majority miner will always produce the longest chain
with no opposition. A short-term “51% attack“ may lead to a huge decrease of
confidence in a blockchain’s content; the persistence of such an attack could
mean the end of a blockchain project.

Figure 5: Nakamoto index estimated weekly for the analysed cryptocurrencies.

The Nakamoto index provides us with a measure of the system’s distance from a
51% attack: named after the pseudonymous author of the Bitcoin whitepaper, it
is defined as the minimum number of miners that need to coordinate at any
point in time to run a $51\%$ attack. There have been several reports of
hashing power centralisation on Bitcoin [23, 11]: based on blockchain data
alone, we are able to estimate this index for all the analysed
cryptocurrencies, and we show the result in Figure 5. We estimate the hashing
power of miners by measuring the fraction of blocks they mine in a week, and
then calculate the Nakamoto index over that same week. Miners are identified
as the entities receiving the coinbase transaction: differently from other
parts of this work, in Figure 5 we show results that are obtained using only
the multiple inputs heuristic method for address clustering, in order to avoid
merging too many pools and miners together. We report similar results for the
combined heuristics in the Supplementary Information.

The majority of analysed platforms shows worrying results. The most striking
case is Ethereum, with a Nakamoto index that is almost never above 3 and in
some weeks drops to 2: this is particularly concerning since Ethereum is used
as the base protocol for many decentralised applications, including
decentralised exchanges and other decentralised finance instruments which
could introduce additional incentives for miners to coordinate in a $51\%$
attack [24, 25]. The picture looks marginally better for Bitcoin and Litecoin,
where the mining power appears relatively less centralised (although it still
is very concentrated at times), while on Dogecoin, Feathercoin, Monacoin and
Bitcoin Cash (after it forked from Bitcoin in August 2017) the Nakamoto index
is always low, and at times even goes to 1, meaning a single miner could have
(and maybe has) successfully run a $51\%$ attack on some weeks. Our evidence
qualitatively agrees with previously presented models [23] and evidence for
Bitcoin [11], where in the latter the authors had additional information
available from deanonymisation services specific to Bitcoin, which we don’t
have access to.

Figure 6: Wealth inequality and spatial distribution. (a) Evolution of the
Gini index of wealths in analysed cryptocurrencies. (b) Distribution of tokens
as a function of distance from the miner. Plot points identify the mean
fraction of wealth, averaged over time, that is held by nodes at a given
distance from the nearest miner. Error bars give the 90% confidence band, i.e.
in 90% of weeks the fraction of tokens held at a given distance is within the
error bars.

### Wealth inequality and spatial distribution.

Our final analysis concerns the distribution of tokens among entities. We
define as wealth the balance held by an entity (address or cluster of
addresses) at a given point in time, representing the funds that they are
entitled to spend according to the blockchain ledger. To avoid considering
inactive wallets, our statistics only consider addresses or entities with non-
zero balance. Clearly, if cryptocurrencies were used simply as a peer-to-peer
payment system as implied by the Bitcoin whitepaper [1] (and many other
whitepapers), the level of centralisation and inequality of wealths should not
be very different from what is measured in traditional economic systems [26].
This is very far from what can be measured on the system we analyse. In Figure
6a we show the Gini coefficient of wealths, measured weekly on each
cryptocurrency throughout our sample. This coefficient is a standard measure
of economic inequality and is related to the area between the Lorenz curve -
which plots the cumulative share of wealth as a function of the fraction of
population owning that share - and the equality line - i.e. the straight 45
degrees Lorenz curve. A Gini coefficient of 0 means perfect equality, i.e.
each individual has the same wealth, whereas a Gini coefficient of 1 means
total inequality, with one individual owning everything. Remarkably, only
Bitcoin in its early years has a Gini coefficient that is lower than the world
average wealth inequality Gini coefficient (which is around 0.9, according to
[26]). After 2012, for all the cryptocurrencies in our analysis the Gini index
is basically indistinguishable from 1, meaning that the distribution of wealth
is extremely unequal across active wallets. We want to stress that this is not
due to having many zero-wealth entities in the sample, as we remove these
before calculating the Gini coefficient.

Finally, we characterise the spatial distribution of wealth on our transaction
networks. To this end we calculate, for each weekly transaction network, the
minimum distance that each node has from a miner. Miners are special entities
in cryptocurrencies because they are the ones that generate new tokens, as
every time they successfully solve the Proof of Work validation puzzle they
are entitled to a reward that is created by the protocol. This means that all
tokens start their “life” in a miner’s wallet and then diffuse from there into
the rest of the economy, which is why they are a meaningful reference node to
consider in transaction networks. We then proceed to calculate the amount of
wealth that is held by nodes at the same distance from a miner, normalised by
the total amount of cryptocurrency circulating, and then consider this
quantity across all weeks in our sample. We plot the result in Figure 6b. The
plot points represent the average wealth share owned by entities at a given
distance from a miner, while the error bars show the 90% confidence band, i.e.
the range of values within which the wealth share lies in 90% of weeks in our
sample. We find remarkable similarities between the analysed cryptocurrencies:
the average wealth share is a decreasing function of distance from miners,
with a behaviour that is close to an exponential, and miners (at distance 0)
are almost always the wealthiest nodes. The only platform where this doesn’t
happen is Ethereum, where the largest wealth share is at a distance of 2 from
miners. This is likely due to the difference in the accounting protocol
between UTXO-based systems and Ethereum’s account-based system, but we lack
conclusive evidence about this. What appears clear from our analysis though is
that the largest fraction of wealth is held by relatively few entities - as
summarised by the Gini coefficient - that are in the immediate vicinity of
miners, with a tail that is quickly vanishing as distance grows.

## Discussion

In this paper we have presented multiple evidences of the centralised nature
of major cryptocurrencies, despite their statutory technological
decentralisation. We described how the protocol of Bitcoin and similar UTXO-
based blockchains works to preserve anonymity and how this can be partially
reverse-engineered to cluster addresses that are likely belonging to the same
entity, and how switching from a raw address-based description to an entity-
based description radically changes the observations. In particular we found
interesting dynamics in the evolution of the average number of addresses per
entity, which is remarkably similar across platforms and experiences
breakpoints in conjunction with large price movements. A first circumstantial
evidence of the centralisation process comes from these dynamics, namely the
decrease of the average number of addresses per entity after 2018, together
with the consolidation of cryptocurrencies as popular speculative assets and
the growth of large intermediaries. The result is consistent with a shift in
the platforms usage, with new entities entering the system through centralised
access points rather than independently.

The introduction of weekly transaction networks allowed us to analyse the
structural properties of cryptocurrency economies. We found further evidence
of the importance of address clustering by measuring the size of the largest
Strongly Connected Component (LSCC) of the networks: while on address networks
the LSCC contains less than half of active addresses, when considering
entities the LSCC includes almost all the nodes of the networks. We take this
as a further sign that there are entities which control multiple addresses,
acting as “bridges” between different sub-components of the economy. The
networks we studied exhibit a fat-tailed degree distribution, with few
entities participating in a large number of transactions each week while the
vast majority only performs very few, and a negative assortativity
coefficient, which constitutes further evidence of the existence of large
intermediaries that centralise the flow of tokens [27]. Furthermore these
networks exhibit a marked core-periphery structure, much like other trading
networks from traditional economic and financial systems, and as time goes on
the cores become increasingly smaller compared to the total size of the
network.

Finally we focused our analysis on the role of miners, which are particularly
important actors in these systems as they hold the responsibility of keeping
the ledger consistent. We find that in all the studied platforms the mining
power, namely the estimated share of hashing rate that each miner holds, is
worryingly concentrated in the hands of few entities to the point that the
Nakamoto index often drops to few units, implying a high risk of a successful
$51\%$ attack on the blockchain. We also found that miners are typically the
wealthiest entities in the system, and that the stark inequality in wealths is
incompatible with the typical narrative of a decentralised, peer-to-peer
payments system.

Overall we argue that these economies have grown into something that is very
different from what they were originally designed to be. The popular
narratives, also seen in some mainstream media, that cryptocurrencies are a
decentralised solution for payments where financial institutions hold no power
over money creation and distribution, are largely false. Similar processes
have been reported in second-layer solutions, such as the Lightning Network
[28, 14]. As a matter of fact, we see that miners and intermediaries hold a
huge power in these systems, both technically and economically speaking, which
turns them into an unregulated financial sector, a new “shadow banking” system
[29]. This unchecked concentration of power is potentially dangerous for the
many retail investors that have holdings in cryptocurrency, and proper
regulation regarding the activities and products that service providers can
offer is overdue.

## Materials and Methods

Blockchain | BTC | ETH | BCH | LTC | DOGE | MONA | FTC
---|---|---|---|---|---|---|---
Height | 661386 | 12950000 | 664161 | 1969743 | 3927743 | 2212711 | 3491853
Date of collection | 14.12.2020 | 03.08.2021 | 02.12.2020 | 23.12.2020 | 07.10.2021 | 07.01.2021 | 07.01.2021

Table 2: Summary information on data collection from public blockchains.

### Data.

Blockchain data for the seven cryptocurrencies of our analysis is sourced
directly from the respective networks by running consensus nodes, collecting
data at block heights reported in Table 2. The figures presented in the paper
show results until the last date that is available for all blockchains,
December 2, 2020.

The blockchain protocols analysed in this study belong to two different
families when it comes to their accounting standard: the Unspent Transaction
Output (UTXO) standard and the account-based standard, the latter being
specific of Ethereum alone in our sample, while all others belong to the
former. In UTXO blockchains transactions are recorded as transfers of access
rights to a certain amount of tokens, stored on an address: this is done by
referencing one or more addresses currently owned by the transaction sender,
and directing the related tokens to one or more addresses owned by the
transaction receiver. Typically the first set of addresses is called the
“input” of the transaction, while the second is its “output”. Outputs can only
be used (“spent”) once as inputs to a transaction, hence the name of Unspent
Transaction Output accounting. Ownership of addresses is proven by public-
private key cryptography: in order to access funds from an address, the
private key is needed to sign the transaction in a way that any other user can
verify via the public key. The same entity can own any number of addresses,
thus making tracing of transactions between entities more challenging, as
there is no guarantee that a transaction involves addresses from one, two or
many different entities. Multiple heuristic algorithms have been developed
over the years to exploit common patterns in transactions input-output
structures to cluster together addresses that are likely to belong to the same
entity. We adopt multiple combinations of these algorithms in our analysis,
and report the details below.

In contrast to the UTXO model described above, the account-based blockchains
use a different and perhaps more intuitive mechanism for exchanging amounts of
cryptocurrencies and other cryptoassets. Instead of holding the private key
that can unlock the unspent output for a new transaction where it will be used
as input, account-based blockchains have their public key directly transformed
as an address, and that address has a specific balance associated. There is
then a reduced need to apply address clustering to account-based blockchains,
since new addresses are not often created within the same wallet. The first
and up to the time of writing most successful example of account-based
blockchains is Ethereum, with its native cryptocurrency Ether [30].

### Address clustering in UTXO blockchains.

The entities, i.e. clusters of addresses, have been generated using the C++
library BlockSci, which is an open-source software package for blockchain
analysis [31]. We combined multiple heuristic algorithms that are provided
within the library to produce our own heuristic methods; we briefly summarise
them below and direct the reader to BlockSci’s
documentation111https://citp.github.io/BlockSci/ for further details. Most of
the methods rely on the identification of change addresses, i.e. outputs of a
transaction that belong to the sender, to which excess input is directed.
Indeed the protocol design imposes that the input value of a transaction
exactly matches the output value plus the fee, which makes change addresses
very common.

The heuristic methods we adopted are the following:

  * •

Multiple inputs - if multiple addresses appear as inputs to the same
transaction, they are likely to belong to the same entity that had to sign
them all to create the transaction;

  * •

Reuse of an address - if an address appears as an input but also as an output,
the address has been reused as change;

  * •

Optimal change: if the transaction has multiple inputs and the value of
exactly one output is lower than any of the inputs, then it is likely the
change. This is based on the argument that if a bigger output was the change,
then one or more inputs would have not been needed to transfer the same amount
to another wallet;

  * •

Creation of a new address - in case an output address is appearing for the
first time on the blockchain, that address has likely been generated to be the
change address;

  * •

Peeling chains - a transaction is considered a potential peeling chain if it
includes one input and two outputs, and the chain is identified if one of the
outputs is used as input to a future transaction with the same structure. In
that case, the output that continues the chain is the change address. These
chains are commonly seen when addresses with large UTXO values are spent in
many smaller value transactions.

Figure 7: Schematic representation of transaction networks construction. On
the left, an archetypal UTXO blockchain block is represented, with coloured
transaction input/outputs identifying clusters according to common heuristics.
This is parsed through BlockSci into the middle representation, the
transaction network at the addresses level, which is then further reduced to
the entity network on the right when multiple addresses/nodes belonging to the
same entity are merged.

Our main clustering methodology combines the above heuristics through logical
operators that aim to reduce the chance that a false positive occurs. In
particular we identify a change address only if all heuristics identify the
same address as potential change, except for peeling chains which can never be
compatible with other patterns by design. Hence a change address is identified
if it is the only one that respects one of the following conditions: i) it is
a reused input address; ii) it is a new address with a value smaller than any
of the inputs; iii) it is the continuation of a peeling chain. If a change is
identified, it is added to the same cluster to which the input addresses
belong. A robustness analysis adopting a more conservative choice of
clustering strategy is presented in the Supplementary Information.

### Transaction networks.

We construct transaction networks to obtain a general representation of
different blockchains. We choose a weekly aggregation to remove intraweek
seasonalities, as we notice that the number of active entities and
transactions is lower during weekends. We then consider all transactions
between entities - i.e. removing self-transactions like change outputs -
happening in a given week, adding the involved entities as nodes and
connecting them through directed links from inputs to outputs. This process is
summarised by Figure 7. Differently from previous literature on cryptocurrency
transaction networks [6, 18], we consider non-cumulative network
representations, meaning that links represent only the transactions happening
on that specific week, similarly to what is done in [11] at monthly
aggregation. This allows us to obtain a more representative structure for the
state of the economy, avoiding considering in the same way connections that
may have happened years apart from each other.

## Acknowledgments

C.C. acknowledges support from the Swiss National Science Foundation grant
#200021_182659. N.V. acknowledges support from the IOTA foundation.

## References

  * [1] Nakamoto, S.  Bitcoin: A peer-to-peer electronic cash system.  _Decentralized Business Review_ 21260 (2008).
  * [2] Chaum, D. L.  _Computer Systems established, maintained and trusted by mutually suspicious groups_ (Electronics Research Laboratory, University of California, 1979).
  * [3] Bollier, D. & Conaty, P.  Democratic money and capital for the commons.  In _Commons Strategies Group Workshop Report, Berlin, Germany_ , 8–10 (2015).
  * [4] Taleb, N. N.  Bitcoin, currencies, and fragility.  _Quantitative Finance_ 21, 1249–1255 (2021).
  * [5] Fischer, J. A., Palechor, A., Dell’Aglio, D., Bernstein, A. & Tessone, C. J.  The complex community structure of the bitcoin address correspondence network.  _Frontiers in Physics_ 9, 363 (2021).
  * [6] Kondor, D., Pósfai, M., Csabai, I. & Vattay, G.  Do the rich get richer? an empirical analysis of the bitcoin transaction network.  _PloS one_ 9, e86197 (2014).
  * [7] Newman, M. E., Barabási, A.-L. E. & Watts, D. J.  _The structure and dynamics of networks._ (Princeton university press, 2006).
  * [8] Newman, M. E.  Assortative mixing in networks.  _Physical review letters_ 89, 208701 (2002).
  * [9] Barucca, P. & Lillo, F.  Disentangling bipartite and core-periphery structure in financial networks.  _Chaos, Solitons & Fractals_ 88, 244–253 (2016).
  * [10] Bovet, A. _et al._ The evolving liaisons between the transaction networks of bitcoin and its price dynamics.  _arXiv preprint arXiv:1907.03577_ (2019).
  * [11] Makarov, I. & Schoar, A.  Blockchain analysis of the bitcoin market.  Tech. Rep., National Bureau of Economic Research (2021).
  * [12] Huber, T. A. & Sornette, D.  Boom, bust, and bitcoin: Bitcoin-bubbles as innovation accelerators.  _Journal of Economic Issues_ 56, 113–136 (2022).
  * [13] Brown, C., Chiu, J. & Koeppl, T. V.  What drives bitcoin fees? using segwit to assess bitcoin’s long-run sustainability.  _Journal of Financial Market Infrastructures_ 9 (2021).
  * [14] Lin, J.-H., Marchese, E., Tessone, C. J. & Squartini, T.  The weighted bitcoin lightning network.  _arXiv preprint arXiv:2111.13494_ (2021).
  * [15] Bargigli, L., Di Iasio, G., Infante, L., Lillo, F. & Pierobon, F.  The multiplex structure of interbank networks.  _Quantitative Finance_ 15, 673–691 (2015).
  * [16] Sugiyama, K., Honda, O., Ohsaki, H. & Imase, M.  Application of network analysis techniques for japanese corporate transaction network.  In _6th Asia-Pacific Symposium on Information and Telecommunication Technologies_ , 387–392 (IEEE, 2005).
  * [17] Tseng, J.-J., Li, S.-P. & Wang, S.-C.  Experimental evidence for the interplay between individual wealth and transaction network.  _The European Physical Journal B_ 73, 69–74 (2010).
  * [18] De Collibus, F. M., Partida, A., Piškorec, M. & Tessone, C. J.  Heterogeneous preferential attachment in key ethereum-based cryptoassets.  _Frontiers in Physics_ 568 (2021).
  * [19] Borgatti, S. P. & Everett, M. G.  Models of core/periphery structures.  _Social networks_ 21, 375–395 (2000).
  * [20] Bardoscia, M., Battiston, S., Caccioli, F. & Caldarelli, G.  Pathways towards instability in financial networks.  _Nature communications_ 8, 1–7 (2017).
  * [21] Lip, S. Z.  A fast algorithm for the discrete core/periphery bipartitioning problem.  _arXiv preprint arXiv:1102.5511_ (2011).
  * [22] 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).
  * [23] Alsabah, H. & Capponi, A.  Pitfalls of bitcoin’s proof-of-work: R&d arms race and mining centralization.  _Available at SSRN 3273982_ (2020).
  * [24] Daian, P. _et al._ Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability.  In _2020 IEEE Symposium on Security and Privacy (SP)_ , 910–927 (IEEE, 2020).
  * [25] Piet, J., Fairoze, J. & Weaver, N.  Extracting godl [sic] from the salt mines: Ethereum miners extracting value.  _arXiv preprint arXiv:2203.15930_ (2022).
  * [26] Davies, J., Shorrocks, A. _et al._ Comparing global inequality of income and wealth.  _Inequality in the Developing World_ 49–73 (2018).
  * [27] Campajola, C., D’Errico, M. & Tessone, C. J.  Microvelocity: rethinking the velocity of money for digital currencies.  _arXiv preprint arXiv:2201.13416_ (2022).
  * [28] Lin, J.-H., Primicerio, K., Squartini, T., Decker, C. & Tessone, C. J.  Lightning network: a second path towards centralisation of the bitcoin economy.  _New Journal of Physics_ 22, 083022, DOI: 10.1088/1367-2630/aba062 (2020).
  * [29] Aramonte, S., Huang, W. & Schrimpf, A.  Defi risks and the decentralisation illusion.  _BIS Quarterly Review_ (2021).
  * [30] Buterin, V.  Ethereum white paper (2013).  https://ethereum.org/en/whitepaper/. Online. Accessed 2022-05-12.
  * [31] Kalodner, H. _et al._ Blocksci: Design and applications of a blockchain analysis platform.  In _29th USENIX Security Symposium (USENIX Security 20)_ , 2721–2738 (USENIX Association, 2020).

## Supplementary Information: Robustness to address clustering

In this document we present additional results that complement the main text,
changing the address clustering algorithm to an alternative strategy that
tends to aggregate less. These results provide a robustness check against the
relatively arbitrary choice of heuristic algorithms that are used to identify
entities, and in particular to the potential critical point that our results
in the main text are tainted by excessive aggregation of addresses under the
Combined Heuristics (CH) strategy.

For this reason we choose to present here the results adopting only the
“Multiple Inputs” (MI) heuristic described in the main text, which follows the
logic that if multiple addresses appear as inputs to the same transaction,
they are likely to belong to the same entity that had to sign them all to
create the transaction.

In summary, our results are mostly qualitatively unchanged when changing the
address clustering strategy. Here we highlight the key similarities and
differences by referencing the tables and results from the main text in
comparison to the ones presented in this Supplementary Information.

  * •

in Figure S1 we show the comparison between the size of the largest Strongly
Connected Component of the Addresses network and the Entities network under
the MI heuristic. We see that it is qualitatively similar to Figure 2 of the
main text for all coins with the notable exceptions of Bitcoin and Bitcoin
Cash. Here the SCC of the MI Entities network does not span the entire set of
nodes, whereas the CH Entities did;

  * •

in Table S1 we report the equivalent of Table 1 in the main text for the MI
Entities networks (except for ETH which is the same). We find that the fitted
Pareto exponents are typically smaller and the fitted Pareto distributions are
closer to the empirical ones according to the Kolmogorov-Smirnov distance,
while the fitted binomials are typically worse fits, suggesting that degree
distributions are even more fat-tailed in the case of MI Entities. Figure S2
shows the degree assortativity coefficient which we find to be slightly closer
to $0$ than what we see for the CH Entities, although it still is always
negative;

  * •

The core size shown in Figure S3 is remarkably similar to the one shown in
Figure 4 of the main text;

  * •

The Nakamoto index, which in the main text is shown for Entities identified
through the MI heuristic, is much smaller in the case of CH Entities as shown
in Figure S4. We chose to report the “safer” figure in the main text as the CH
Entities might be subject to over-aggregation, which in this particular case
would depict a more troublesome situation than the already worrying picture of
Figure 5 in the main text.

Figure S1: Size of the largest Strongly Connected Component in UTXO-based cryptocurrencies. |  | BTC | LTC | DOGE | BCH | FTC | MONA | ETH
---|---|---|---|---|---|---|---|---
$\alpha$ | Minimum | 1.64 | 1.31 | 1.64 | 1.58 | 1.52 | 1.66 | 1.50
Maximum | 4.93 | 3.66 | 3.36 | 4.93 | 5.67 | 3.97 | 3.42
1\. Quartile | 2.04 | 1.87 | 1.86 | 1.96 | 1.93 | 1.97 | 1.68
3\. Quartile | 2.46 | 2.52 | 2.33 | 2.43 | 2.76 | 2.21 | 1.81
Median | 2.25 | 2.07 | 1.97 | 2.19 | 2.26 | 2.09 | 1.76
$D_{Par}$ | Median | 0.03 | 0.05 | 0.04 | 0.03 | 0.07 | 0.06 | 0.03
$D_{Bin}$ | Median | 0.35 | 0.41 | 0.49 | 0.37 | 0.44 | 0.41 | 0.43
Table S1: Summary statistics on exponents of power-law fit of degree
distribution on the weekly transaction networks. Figure S2: Assortativity
coefficient for weekly transaction networks. Figure S3: Fraction of nodes in
the network core as a function of time. Figure S4: Nakamoto index estimated
weekly for the analysed cryptocurrencies.