A Novel Framework for the Analysis of Unknown Transactions in Bitcoin: Theory, Model, and Experimental Results

Our contributions are both theoretical and applied. At glance, we are the first, to the best of our knowledge, to provide a navigation tool within the Bitcoin blockchain that: does not rely on addresses and explores all the transactions stored in the blockchain. In detail, our contributions can be summarized as follow:

• •

  we introduce the general concept of unknown transactions, subsuming the less rigorous definition of non-standard transactions provided by the Bitcoin protocol;

• •

  we extend the definition of user network $\mathcal{U}$ by including unknown transactions;

• •

  we design a novel (theoretically sound) parsing methodology to study, and likely understand for the first time, unknown transaction patterns by using a specific class of graphs called T-DAGs;

• •

  we show that T-DAGs can be efficiently compared via isomorphism, offering a new mechanism for clustering similar transaction patterns.

• •

  we test our algorithms over the Bitcoin network, collecting and analysing all unknown transactions in the ledger from Bitcoin origins until block 591,872;

• •

  we further refine our results by removing trivial non-standard transactions already observed in the literature, revealing classes of hidden unknown transaction patterns never considered before;

• •

  to the best of our knowledge, this is the first study of the Bitcoin transaction network which includes unknown transactions.

With reference to the Bitcoin context, our contribution can be used to collect and observe the existing unknown transaction patterns in the ledger, as well as those that will be generated in the future. These patterns, previously ignored by any transactions analysis work, can be used to complete the user network $\mathcal{U}$ and the transaction network $\mathcal{T}$. Our methodology can be applied to any clustering and de-anonymization technique to improve its effectiveness by leveraging a complete and reliable Bitcoin transactions database. Moreover, our novel solution can be extended immediately to any other system where transaction patterns can be modeled using T-DAGs.

Organization: The rest of the paper is organized as follows. In Section II we introduce preliminary concepts used in the paper. In Section III we summarize the state of the art for Bitcoin addresses clustering and graph isomorphism problem. In Section IV we define our theoretical model capable of extending user network in order to identify those sub-graphs that involve unknown transactions. In Section V, we describe the application of our theoretical model to the Bitcoin network, discussing the results achieved during our experimental evaluation. Finally, in Section VI we summarize our results, discuss the possible implications, and suggest future research lines.

Let $G=(V,E)$ be a graph with nodes $V$ and edges $E$. We will consider both undirected graphs with $E\subseteq\binom{V}{2}$, and directed graphs with $E\subseteq V\times V$. An undirected graph $G$ is said to be connected if, for any $u,v\in V$, there is a path from $u$ to $v$. In a directed graph, edges are sometimes called arcs and the first vertex of an arc is referred to as the tail and the second one as the head. Given a directed graph $D=(V,E)$, the underlying graph $G=(V,E^{\prime})$ is the undirected graph obtained with the same vertex set and an edge set corresponding of each arc in $E$. That is, if $(u,v)$ is an arc in $D$ then both $(u,v)$ and $(v,u)$ are edges in $G$. A directed graph is weakly connected if the underlying graph is connected. From now on, we will always refer to directed graphs and use edges and arcs interchangeably.

For an edge $e=\{u,v\}\in E$, we say that $u$ is adjacent to $v$, and vice-versa. If there exists a sequence of edges connecting two vertices $u$ and $v$, we say that these two vertices are reachable. If $u$ is reachable starting from itself (through a non-empty sequence of edges) we say $G$ contains a cycle. If $G$ contains no cycles, $G$ is said to be acyclic. We call directed acyclic graphs DAGs. A tree is an undirected, connected, and acyclic graph. We use $K_{x,y}$ to indicate the complete bipartite graph between two sets of nodes $X$ and $Y$ with $|X|=x$ and $|Y|=y$. Given a vertex $v\in V$, $v$’s indegree, $\Gamma^{-}(v)$, is the cardinal of edges (or arcs) that have $v$ as its head. Symmetrically, $v$’s outdegree, $\Gamma^{+}(v)$, is the cardinal of edges (or arcs) that have $v$ as its tail. We call a vertex with zero indegree a source, and one with zero outdegree a sink. Given two graphs $G_{1}=(V_{1},E_{1})$ and $G_{2}=(V_{2},E_{2})$, an isomorphism is a bijection function $f(.)$ between the sets of vertices, $V_{1}$ and $V_{2}$, such that it maintains adjacency. That is, $(u_{1},u_{2})\in E_{1}\Rightarrow(f(u_{1}),f(u_{2}))\in E_{2}$. A graph labeling is the assignment of labels to the vertices, edges, or both, of a graph. Given a graph $G$, a canonical form is a labeled graph $\bar{G}$, isomorphic to $G$, such that $H$ is isomorphic to $G$ iff $\bar{G}=\bar{H}$—i.e, they have identical canonical forms. An equivalence relation $\sim$, is a binary relation on a set $S$ that is: (i) reflexive; (ii) symmetric; and, (iii) transitive. For any elements $a,b$ and $c$ in $S$ it holds: (i) $a\sim a$, (ii) $a\sim b\Rightarrow b\sim a$ and (iii) $a\sim b\wedge b\sim c\Rightarrow a\sim c$. An equivalence relation, $\sim$, partitions a set in equivalence classes. A total ordering, $\prec$, is a binary relation on a set $S$ that is: (i) antisymmetric; (ii) transitive; and, (iii) connex. That is, $\forall a,b,c\in S$: (i) $a\prec b\wedge b\prec a\Rightarrow a=b$; (ii) $a\prec b\wedge b\prec c\Rightarrow a\prec c$; and, (iii) $a\prec b\cup b\prec a$.

The Bitcoin network is composed by peers which can be either full nodes or clients, with full nodes validating transactions and blocks [10]. The Bitcoin protocol stores every transaction in a publicly distributed ledger, thus allowing everyone to read the transactions occurred among Bitcoin users. To ease the analysis of the money flow contained in the Bitcoin ledger, the Bitcoin data-set can be modeled with two different graphs (Transaction and User Network) as introduced in [37].
The Transaction Network $\mathcal{T}$ describes the Bitcoin flow between transactions over time [32]. Each node represents a transaction, and each directed edge between two nodes n1 and n2 represents a money flow that is an output for n1 and an input for n2. The network is a directed acyclic graph (DAG) since the output of a transaction can never be an input (either directly or indirectly) to the same transaction.
The User Network $\mathcal{U}$ describes the Bitcoin flow between users over time [28]. Each node represents a Bitcoin user, and each directed edge between two nodes $n_{1}$ and $n_{2}$ represents an inputs-outputs pair of a single transaction, where the inputs belongs to $n_{1}$ and the outputs belongs to $n_{2}$. More in detail, the User Network is a weighted directed hypergraph $\mathcal{U}=(\mathcal{A},\mathcal{T})$ where $\mathcal{A}$ is the set of all the addresses used in the Bitcoin network, and $\mathcal{T}$ is the set of transactions. Every transaction $t\in\mathcal{T}$ can be modeled as a pair of ordered sets $(X,Y)$ with $X,Y\subseteq\mathcal{A}$ , where addresses included in $X$ are inputs of $t$ and addresses in $Y$ are outputs of $t$.

Recently, security properties of blockchain-based protocols, with particular attention on the Bitcoin network, received increasing attention [15, 22, 24, 16, 12]. Among the different topics covered, several methods have been proposed to cluster bitcoin addresses [17]. These contributions build $\mathcal{U}$ by applying different heuristics to $\mathcal{T}$. The most used heuristic, the Common Input, is based on the observation that all the inputs of a multi-input transaction belong to the same user [37]. This heuristic has been used to cluster Bitcoin addresses with the aim of deanonymizing users by using off-chain data [25] and study the Bitcoin network to uncover different properties [27, 35, 23]. Later, a more advanced heuristic called One-time Change was introduced [31, 14, 1, 39], based on the detection of the change among the output addresses.

All of these approaches built the transaction network $\mathcal{T}$ and the user network $\mathcal{U}$ by parsing the Bitcoin blockchain using the reference implementation (i.e. Bitcoin Core) or other blockchain explorer software. As explained in Section IV-A, current parsing algorithms, due to some incomplete assumptions, do not consider unknown transactions, providing incomplete and in some cases incorrect data to clustering and deanonymization algorithms.
Table I shows a comparison between the p0roposed solution and: (i) the Bitcoin reference implementation, i.e., Bitcoincore; (ii) blockchain explorer services, represented by the most popular one, blockchain.com; (iii) other platforms to analyze the Bitcoin blockchain, e.g., Blocksci; and, (iv) the most representative contributions in the literature that already used the user network $\mathcal{U}$ or the transaction network $\mathcal{T}$.

The graph isomorphism (GI) problem consists in determining whether given two graphs $\mathcal{G}$ and $\mathcal{V}$ there exists a bijection between both sets of vertices that preserves adjacencies. The lowest time bound for general GI stood since 1983 and until very recently at $\exp{\mathcal{O}\left(\sqrt{n\log n}\right)}$ [5]. However, polynomial time algorithms have long been known for different families of graphs. Among others, for graphs with bounded valence, the first polynomial time test dates from 1980 [26]. This work was used to solve the problem for graphs with bounded eigenvalue multiplicity [4] in $\mathcal{O}\left(n^{4m+c}\right)$. For circulant graphs, a $\mathcal{O}(n^{2})$ testing algorithm is known [33]. The tree isomorphism problem was proven [18] to be linear in the number of vertices, that is, two trees $T_{1}$ and $T_{2}$ can be tested for isomorphism in $\mathcal{O}(n)$ comparing them in a bottom-up fashion. A result from 2016 [3] improved the 1983 bound for the GI problem to quasipolynomial time. The author proved an upper bound of $\exp{\left(\log n\right)^{\mathcal{O}(1)}}$ for testing wether two arbitrary graphs are isomoprphic or not.

A possible test of graph isomorphism is performed through canonical forms and canonical labelings. A canonical form of a graph is a representative of a class of graphs closed under isomorphisms, and with a linearly ordered vertex set [6]. That is, two graphs are isomorphic if and only if they yield the same canonical form. A canonical labeling is a string derived from a canonical form of a graph obtained through a defined mapping. The problem of obtaining canonical labelings for general graphs remains quasi-exponential in the number of vertices. A combinatorial method that runs in $\exp{n^{2/3}+o(1)}$ has long been known [6]. In the same paper the authors give a procedure to compute the canonical form of graphs of bounded valence (or degree) in polynomial time. Due to its relevant applications and the urge for practical solutions, implementations of graph canonization packaged in different software has proven to be successful. The McKay canonical labeling algorithm [30] packaged in the nauty software is one of the most celebrated solutions. It was the most popular solution from the early 80s until 2004, when a modern re-implementation [13], saucy, was introduced. Exploiting symmetry and sparsity in the search space pruning the latter managed to outperform the former by several orders of magnitude. The refinements later introduced in bliss [20] concluded in the release of Traces. The definition of the latter piece of software together with a comparison of all the software packages presented is discussed by its authors in [29].

When restricting the problem to rooted or un-rooted trees, linear is the best possible sequential runtime [18]. However, tree canonization has been proven to be in alternating logarithmic time [11]. The labeling therein defined is depth-first and the approach presented in this paper is breadth-first. In spite of that, the ordering relation we define is based on the same principles. However, a more recent approach [41] for tree canonical labeling uses a breadth-first approach. The authors therein do provide a less verbose labeling (at most $3n$) than ours, but this is due to the fact that they deal with specialized trees: ones where each vertex has an in-degree of at most 1.

The Bitcoin protocol provides its community with standard templates that must be used to create the locking and unlocking scripts that make up a transaction. The use of such templates is then enforced by miners using two functions, isStandardTx() and isStandard(), which check the compliance of each transaction’s inputs and outputs, respectively. In fact, a transaction is considered standard, and therefore accepted by the network, only if both functions return TRUE. If even one of them returns FALSE, the transaction is considered non-standard and discarded. This mechanism should prevent any use of Bitcoin transactions other than the ones conceived by the protocol, to avoid the spread of malicious transactions. However, even non-standard transactions can be included in the blockchain, thanks to miners who relax these controls [8].
Similar to the concept of non-standard transaction, we define unknown transactions as follow:

For elaborated blockchain analysis, it is a good idea to initially parse all the data from a running miner and, once the data is organized in a more accessible manner, apply further and more complex post-processing. However, we have discovered several imprecisions in the blockchain’s parsing process:

• (i)

  Excess of abstraction Blockchain parsers such as BlockSCI [21] introduce a completely new level of abstraction over the one already specified in the reference implementation [9]. Defining new wrappers, lots of different classes, and incomplete references can make a parser difficult to use and debug. Additionally, we discovered that, in the particular case of BlockSCI, there are errors in their parsing methodology;

• (ii)

  Excess of identifiers Bitcoin’s blockchain is an environment based on uniqueness. Every item must be uniquely identified and hashing algorithms already provide a way to do so. However, some parsers [21] insist on giving an alternative enumeration for transactions and addresses. This makes databases harder to navigate and makes it non-intuitive to mimic the client’s behavior or debug the processed data;

• (iii)

  Using Public Keys as Identifiers As introduced in Section I, to the best of our knowledge, existing works [27, 1], clustering Bitcoin Addresses to find real end-users, assume that each transaction output must have an address assigned to it. This is false. In fact, up to block with height $481823$, Bitcoin’s blockchain contains $3255688$ unknown transactions.

Given the above problems, our proposed framework aims to provide a reference for storing Bitcoin’s data in a database; minimizing the amount of abstraction involved, reusing whenever possible the identifiers provided by the reference implementation, and keeping the structure simple and clear.

To be consistent with both (i) and (ii), we only introduce the critical functionalities not covered by the Bitcoin core ¹¹1The core client cannot find which transaction input is spending a given unspent output.. This way, parsers using our framework can be easily compared against each other, the Bitcoin Core Client, or even web explorers. Further layers of abstraction depending on the application should be detached from the parsing phase to avoid situations where complex post-processing is discredited by incorrect data parsing. This means that all non-relevant information for blockchain navigation is not included in the framework.

The Framework Our framework uses only minimal abstraction and provides a robust, reliable, and fast way to navigate through the Bitcoin’s blockchain. It is also easily portable: all applications that query or do some sort of post-processing with Bitcoin’s data can use it. To fulfill these conditions and to preserve minimality, only the necessary attributes are included. All other features included in the reference implementation, that provide key information about each transaction, but do not improve the exploration of the blockchain, are discarded. In fact, they can be easily obtained by using the identifiers provided by our framework, together with any Bitcoin client.

We present a database layout that only contains two types of entities: block and tx.

• (i)

  block: represents a block in the blockchain. It is uniquely identified by two parameters: hash and height. Both the parameters can be used to retrieve a block element from the database without ambiguity. Each block element has an additional parameter, tx. tx is an array of hashes, each one referencing a transaction included in the block (see next item for a description on the tx entity). Each element in the array can be uniquely identified, and accessed, by the index of their position within the array. This way, the $m$-th transaction of the $n$-th block can be identified without uncertainty;

• (ii)

  tx: represents a confirmed transaction (TX) in the blockchain. Since the Bitcoin’s ledger contains different cases of transactions with the same hash²²2Blocks 91812 and 91842 contain a transaction with hash: “d5d27987d2a3dfc724e359870c6644b40e497bdc0589a033220fe15429d88599”., this attribute cannot be used as a unique identifier. We realized that the Bitcoin Core client still uses the hash attribute to uniquely identify a transaction, causing a loss of information: searching for a particular transaction hash, the Core client returns only the last occurrence of that hash in the ledger. As a result, any transaction stored in the blockchain with a hash equal to a more recent transaction will never be returned by the client. For this reason, we uniquely identify a transaction using its attribute pair <blockhash, hash> which represents the hash of the block they belong to and its hash, respectively. The vin attribute is an array of pairs <txID, txID[vout]>. It represents the set of inputs contained in the transaction. Each input can be uniquely identified by their index within the transaction input array ³³3Since inputs do not have a global unique identifier, and since the reference client implementation does not define input entities, we have chosen not to do so either.. The txID attribute from the pair is the hash attribute of the TX that contains the output that the input is spending and txID[vout] is the index of the spent output within the TX that contains it. Symmetrically, the vout attribute is an array of pairs <txID, txID[vin]> where, if the output is spent by some input in the future, the TX hash, and the index within the transaction where the output is spent, are included. If the TX is unspent, both attributes are set to null. Each output can be uniquely identified through the hash of the transaction they are contained in and their index in the output array (tx.vout).

The above introduced structure leads to Definition 2, which we will use often in the rest of the paper.

A first contribution of our framework is the possibility to travel to the future in the blockchain. This allows us to easily identify the paths followed by bitcoins through the blockchain history. Definition 3 formalizes some new terminology related to our traveling mechanism.

A brief summary of the data structure used in our framework is provided in Table II.

In this section, we lay the blockchain data in a graph using the framework defined in IV-A, introduce the concept of Unknown TX graphs and study the derived T-DAGs. The study of these directed graphs will enable us to describe, tailor and identify unknown transaction patterns on the Blockchain.

The introduction of $\alpha$-nodes and the previous remark identifies a natural contracted graph of $G_{\text{TIO{}}}$.

To define the subgraphs in the TIO graph relevant for our research, we still have to introduce some more concepts.

Unknown TX graphs will be our object of study for the rest of the paper. From their construction, we observe the following points.

From now on, we will refer to Unknown TX graphs as Unknown TX T-DAGs⁵⁵5Unlike trees, a vertex in a T-DAG may have more than one parent..

Algorithm 1 presents a procedure to generate the Unknown TX T-DAG given an $\alpha$-node $s$.

An example of an Unknown TX DAG is presented in Figure 1. Note that, we attach the associated address for each node.

After compressing an Unknown TX DAG, we need to store it. To do so, we will use a canonical representation of our graph. A canonical labeling is a string derived from a graph such that two different graphs are isomorphic if and only if they yield the same string. A canonical representation (i.e. the canonical labeling associated to a set of isomorphic graphs) is then the representative of a graph isomorphism class. In this section we present a total ordering for T-DAG isomorphism classes and a canonical labeling for T-DAGs.

Complete and reliable Bitcoin blockchain data are essential to correctly build the TX T-DAGs. The official software release used by the Bitcoin protocol, i.e. Bitcoincore, is not suitable for this purpose as it is not designed for the analysis of the data contained in the blockchain. To the best of our knowledge, all freely available blockchain explorer tools suffer from the problems described in Section IV-A. That is, they do not properly handle custom transactions. For this reason, we have designed a MySQL database to store transaction data retrieved by parsing the Bitcoin ledger using our model discussed in Section IV-A. We imported all the Bitcoin blockchain data starting from the genesis block 0 (mined on 2009-01-03), up to block 591,872 (mined on 2019-08-26). Our database consists of more than 448 million Bitcoin transactions, over 1.1 billion transaction inputs, over 1.2 billion transaction outputs and around 550 million Bitcoin addresses. We hosted our MySQL database on a Dell Poweredge R740 Server, equipped with 2 CPU Intel® Xeon® Gold 6144 3.5G, RAM 512GB, running Ubuntu Server 18.04.4 LTS. To parse the Bitcoin ledger, we used Bitcoin Core Daemon v.0.18.0.0, running on a Dell XPS laptop equipped with an Intel® Xeon® CPU E3-1505M 2.80GHz, RAM 32GB - OS: Ubuntu 18.04.4 LTS.