{'fraction_non_alphanumeric': 0.03540352654113531, 'fraction_numerical': 0.004695916394272823, 'mean_word_length': 4.5385007649158595, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Modeling a Double-Spending Detection System for the Bitcoin Network

The Bitcoin protocol prevents the occurrence of double-spending (DS), i.e. the utilization of the same currency unit more than once. At the same time a DS attack, where more conflicting transactions are generated, might be performed to defraud a user, e.g. a merchant. Therefore, in this work, we propose a model for detecting the presence of conflicting transactions by means of an 'oracle' that polls a subset of nodes of the Bitcoin network. We assume that the latter has a complex structure. So, we investigate the relation between the topology of several complex networks and the optimal amount, and distribution, of a subset of nodes chosen by the oracle for polling. Results show that small-world networks require to poll a smaller amount of nodes than regular networks. In addition, in random topologies, a small number of polled nodes can make a detection system fast and reliable even if the underlying network grows.


I. INTRODUCTION
Nowadays, the Blockchain [1] and the world of cryptocurrencies represent a vibrant area in industry and academia. Notably, new studies (e.g. [3][4][5][6][7]) are enriching the scientific literature and new services, based on this technology, are pervading different sectors [8]. In few words, the Blockchain can be described as a distributed ledger composed of 'blocks' containing a list of transactions. Its structure is simple, i.e. its blocks connect generating a growing chain. Notably, each new block connects to the head of the chain. Users can easily generate a new block by collecting a set of transactions (not yet recorded in the previous blocks). However, adding a new block to the Blockchain is all but easy, and many users (called 'miners') take part in this process, in a challenging competition. Notably, the first miner that completes a process of 'Proof-Of-Work' (POW) [2] succeeds and can add her/his block to the Blockchain. Then, miners move to the formation of a new block, that will be connected to the latest 'discovered' block (i.e. the one on the head of the chain). The POW requires the availability of computational power, only the successful miner (i.e. the first one that completes the POW) receives a reward in Bitcoin [1]. It is worth to highlight that more than one block can be 'discovered' (by performing the POW) at the same time.
So, occasionally a 'fork' can emerge in the Blockchain. However, forks are easily solved by the system since, according to the spreading dynamics in the Bitcoin network and to the possibility to connect a new block to only one head of the fork, one branch will soon become longer than the others. Thus, according to the protocol, only the longest branch will be considered by miners, while the others will be cut. Looking at the recent dynamics of the cryptocurrency market (see for instance [3]), we can appreciate the high impact that Bitcoin is experiencing also at societal level. However, like any other digitalized system, it can be subjected to various attacks. It is important to highlight that double-spending (DS), i.e. the fraudulent attempt to use the same Bitcoin more than once, cannot succeed in the Bitcoin network [1,2]. However, the generation of conflicting transactions, following the basic mechanism of a DS attack, can be adopted to defraud users. Therefore, the detection of DS attempts is of paramount relevance for increasing the safety of users, like merchants, that are willing to accept payment in Bitcoin. A complete knowledge of the structure of the Bitcoin network would be extremely useful for the design of a system that identifies a promptly reports DS attacks. In addition, even by collecting data related to a fraction of the network to infer its topological structure [6], we have to consider that the latter can evolve over time, e.g. new users can join the network and new connections can be generated. As result, only a limited information can be actually available. Furthermore, the early phases of a DS attack can involve each time different nodes of the network. Beyond that, it is worth to remind that a central core of nodes is highly connected, i.e. the set of miners. For these reasons, we suggest that a reliable DS detection system can be modeled by using the framework of the modern theory of networks [9], exploiting in particular the core composed of miners. Thus, assuming that the Bitcoin network has a non-trivial structure, we aim to investigate the performance of an oracle that polls a subset of nodes in order to verify the presence of conflicting transactions. With this goal in mind, we focus on relation between the topology of different complex networks and the definition of a random subset of nodes to be polled for the detection task. Since the analysis considers global properties of a network, we deem that the related results can be useful for implementing a DS detection system in the Bitcoin network. Accordingly, the target of our investigation is estimating the optimal amount of polled nodes for a rapid detection of DS attacks. Notably, we analyze different complex topologies, and a random distribution of polled nodes over each network.
The reminder of the paper is organized as follows: Section II provides a more detailed description of Bitcoin transactions and the mechanism of a DS. Section III introduces the proposed model. Section IV shows results of numerical simulations. Eventually, Section V ends the paper.

II. BITCOIN TRANSACTIONS
In this section, we provide a more detailed description of Bitcoin transactions [2], then we focus on the basic mechanism of a DS attack, performed by the generation of conflicting transactions. Transactions are described by different parameters, e.g. keys, signatures, and so on, and contain one or more inputs and, in general, one or two outputs. A set of inputs is used to define the amount of Bitcoin of a transaction, which has the related outputs, indicating where these Bitcoin are sent. Accordingly, users can spend Bitcoin accumulated during previous transactions. For instance, a user A has a total of 6 Bitcoin collected during two transactions, i.e. one whose value was 2 Bitcoin and another one of 4 Bitcoin. Now, if the user A has to send 5 Bitcoin to the user B, can define a transaction whose input corresponds to the set of transactions previously received. Then, in this case, the new transaction has two outputs: one whose value is equal to 5, sent to B, and another one directed toward herself/himself (i.e. the A's wallet) equal to (or smaller than) 1. If the value of the second output is smaller than 1, the difference constitutes the 'fee' claimed by the winning miner (fee = input − output). Thus, after the described transaction, A has only (or less than) 1 Bitcoin, while B can now spend the received 5 Bitcoin. Transactions are broadcast through the Bitcoin network, to be included as soon as possible into the Blockchain. At the beginning of this process, they are unverified, i.e. they are defined as 0-confirmation transactions. Here, a fraudulent user could try to perform a DS. As above reported, it is not possible to spend twice the same Bitcoin. So, a DS attack to the network fails. However, here we focus on the utilization of a DS attack to defraud another user.
Notably, let us now consider the presence of a third user, say C, that cooperates with A.
As before, the latter performs a first transaction sending Bitcoin to her/his accomplice (i.e. user C). Then, few instant later, A performs a second transaction addressed to B. If the inputs of the two transactions correspond, completely or only in part (i.e. a subset of input), A is attempting a fraud. The same, in principle, applies if the first transaction is addressed to user B, and few instant later a second one (always using same input) is addressed to user C. During a DS attack, two (or more) conflicting transactions (i.e. that share a subset of the input) spread over the network, and only one will be added into the Blockchain. Considering the previous example, if the recorded transaction is the honest one (i.e. that sent to B) the fraud fails whereas, in the opposite case, A and C accomplish their goal, and B does not receive her/his 5 Bitcoin. A pictorial representation of this scenario is provided on the top of Figure 1.

III. MODEL
As above described, transactions are broadcast into the Bitcoin network, then (if valid) are recorded into the Blockchain. For the sake of simplicity, broadcasting a transaction can be modeled as a spreading process. A wide number of investigations analyzed these dynamics in complex networks, spanning from social dynamics [10][11][12] to epidemic processes [13,14].
Therefore, a similar approach can be adopted also for studying our problem. At the same time, it is worth to remind that the detection of a DS attack is a bit different from a classical spreading process, e.g. epidemic dynamics. For instance, in viral spreading we can measure the amount of time steps a virus takes for infecting all nodes of a network, on varying different parameters. In a similar way, in social dynamics we can study the amount of time steps required for sharing information through a social media, and so on and so forth. Instead, in our case, we need to consider the dynamics of two (or even more) spreading processes to evaluate the time required for their detection by means of a polling. It is important to mention that miners cannot be aware whether a transaction results from a fraudulent attack and, in addition, they are 'rational' [15], i.e. they only aim to generate blocks collecting transactions that release a high fee. We remind that a DS attack entails that two, or more, conflicting transactions are broadcast. However, the higher the amount of these conflicting transactions, the shorter the time required to detect a fraudulent attempt (as only two of them are detected, the fraud is discovered). So, the worse case is based on the presence of only two conflicting transactions. For that reason, the proposed model considers only that case. Furthermore, for the sake of simplicity, our fraudulent user broadcasts the two transactions only to two different nodes in the Bitcoin network (although, in the real system, nodes have usually more than one neighbor). Then, the two selected nodes play the role of source or, using the epidemilogist jargon, they are a sort of 'patient-0'. Since we aim to study the relation between the topology of a network and the amount of polled nodes, for an early detection, our investigation focuses on the time our oracle should wait before performing the poll on a randomly defined set of nodes. Here, the time is computed in terms of time steps (the actual equivalence between 'time' and 'time steps' requires further details not provided in this work). The waiting time considered by our model allows to satisfy both scenarios related to the fraudulent case above described, i.e. when the malicious transaction is performed before than the honest one, and when it is performed a bit later. In both cases, we assume the the temporal lag between the two transaction is extremely small. In addition, the concept of time step and that of distance are strongly connected. Notably, given two nodes, say x and y, the amount of time steps required for sending a transaction from x to y corresponds to the amount of links a transaction has to go through for moving from node x to node y. Thus, since the oracle needs both transactions, the amount of time steps required is equal to the distance between a polled node and the farer source (i.e. the farer patient-0). Summarizing, the proposed model is then defined as follows: we generate a network with N nodes; two of them are randomly selected as sources (i.e. those receiving the two transactions at t = 0), and Z nodes are randomly chosen to perform a poll. In doing so, with a very low probability, a node can be both a source and a polled node at the same time. Then, we compute the amount of time steps required by the set of the Z polled nodes for receiving both transactions (i.e. the system needs that only one of these nodes receives both transactions). Figure 1 shows the basic configuration of the model in two different networks (i.e. a regular ring on the left and a small-world network on the right). As we know from previous investigations (e.g. [16,17]), small-world networks and scale-free networks support spreading processes. In particular, small-world networks have an average shortest-path length that scales with the logarithm of the size of a network (i.e. the shortest distance between two randomly chosen nodes x and y is, on average, d x,y ∼ ln(N ), with N number of nodes. Instead, scale-free networks can be even faster than small-world networks, in spreading processes, given the presence of highly connected hubs (i.e. nodes with a huge amount of connections). For that reason, both small-world and scale-free networks are expected to support a quick detection of conflicting transactions.
The pictorial representation in Figure 1 shows two networks with red nodes, i.e. sources s 1 and s 2 , and green nodes, labeled by D * , to indicate polled nodes. In both networks, polled nodes occupy an optimal position (i.e. as a transaction spreads from s 1 and one from s 2 , polled nodes are located in positions that ensure the fastest detection). It is interesting to note that, according to the topology of a network and to the amount its nodes, given the position of sources (i.e. s 1 and s 2 ), the optimal locations for a quick detection might vary case by case. For instance, the regular ring on the left-hand side of Figure 1 indicates the presence of two optimal nodes, while the small-world network on the right-hand side shows only one optimal node. So, assuming that in the proposed model polled nodes are randomly selected, as well as the two sources, we implement a Monte Carlo simulation. Notably, from a theoretical point of view, being N * the number of optimal positions in the network, the probability that a polled node occupies that position is p(D * ) = N * N . Thus, increasing the amount of polled nodes, we have more chances to select one located in a convenient position.
Hence, since for each network configuration the amount of time steps required for a rapid detection has a minimum (i.e. that obtained when polled nodes are located in convenient positions), increasing the set of polled nodes the average amount of time steps gets closer to the minimum value.

IV. RESULTS
Numerical simulations are based on the following topologies: regular lattices, small-word networks, and scale-free networks. In particular, the regular lattice and the small-world network have been achieved by implementing the Watts-Strogatz model [18], while the scale-free configuration has been implemented via the Barabasi-Albert model [19]. Using the Watts-Strogatz model, the connectivity pattern of the resulting network is controlled by a re-wiring parameter, usually known as β, whose range is β ∈ [0, 1]. For instance, with β = 0, the network keeps its initial configuration (i.e. a regular ring lattice), whereas by increasing β the resulting network gets provided with a small-world structure. Eventually, β = 1 leads the network to achieve a completely random structure. Before illustrating the results, we emphasize that for each configuration we perform different simulation runs, computing both the average value (shown in following figures, and standard deviation as reported in the Table I). In particular, for each topology, we consider 150 different random pairs (i.e. source nodes), and for each single pair of sources we test 50 different sets of polled nodes (randomly selected). In addition, random topologies (i.e. small-world and scale-free) are re-generated 6 times during each single simulation, so that the process is measured on different networks having the same pattern. Finally, the proposed model has been studied considering networks with the following sizes: N = [10 2 , 10 3 , 10 4 ]. Figure 2 shows results of numerical simulations performed on networks with N = 10 4 nodes. A rapid inspection of Figure 2 suggests that the first configuration, i.e. the regular ring lattice, requires much more time steps than all the others (in full accordance with the theoretical description before provided). However, we decided to analyze also the worse case, i.e. setting the position of the two sources (randomly arranged in the previous simulations) in two opposite nodes of the lattice. For instance, labeling nodes with a number from 1 to 10 4 , the most time consuming scenario occurs every time they have the maximum distance, e.g. one source in the node 1 (on the top of the ring) and the other source on the node 5000 (on the bottom of the ring). Results of this brief analysis confirm the theoretical expectation, i.e. the average amount of time steps gets closer to 1250 as the the amount of polled nodes increases. It is worth to remind that the 8 regular lattice here considered has an average degree equal to 4. Networks with a smaller amount of nodes have a behavior similar to that shown in Figure 2 -see also Table I. It is worth to highlight that all networks show a similar behavior, i.e. the first part of each line in Figure 2 rapidly decreases until a kind of elbow makes it almost flat, indicating that after a given number of polled nodes (i.e. Z) the performance of the system becomes almost constant. So, in principle, it is possible to find an optimal Z that allows to implement a reliable oracle. Then, we study the behavior of the model, scaling the size of the networks.
Remarkably, in random networks, few polled nodes are able to keep a good performance even

V. DISCUSSION AND CONCLUSION
In this work, we investigate the dynamics of DS attacks in different complex topologies, in order to design a detection system for the Bitcoin network. Notably, we aim to quantify the relation between the topology of a network and the amount of nodes that need to be polled by an 'oracle' devised for identifying the presence of conflicting transactions. Since it is not possible to double spend the same Bitcoin, the issue to consider is only related to possible attempts in defrauding users like merchants, willing to accept payments in Bitcoin. Here, we assume that the Bitcoin network has a non-trivial topology (see also [6]). For this reason, we deem useful to investigate this kind of fraudulent behavior by using the framework of complex networks, so that the related outcomes can constitute a reference for implementing a detection system in the real network. In order to evaluate how random topologies affect the analyzed process, our analysis considers also regular ring graphs. Thus, the motivation of this choice goes beyond the scientific curiosity. Then, we analyze also famous topologies as small-world networks and scale-free networks. Moreover, we remind that when implementing small-world networks according to the Watts-Strogatz model (as in our case), the first step is the definition of a regular ring lattice. Looking at results, we observe that random networks, as small-world and scale-free networks, are faster than regular graphs in the detection of DS attacks. That result, as above reported, is quite expected. Notably, the broadcasting of transactions is similar to a spreading process on networks, and the latter has been proven being faster in the above mentioned random topologies than in the those regular. However, results show that both small-world networks and scale-free networks require to poll very few nodes for ensuring a rapid detection. In addition, it is worth to highlight that the performance of an oracle polling few nodes is poorly affected by the scaling of the network (i.e. the same amount of polled nodes can be used even when the network substantially grows). So, we deem that the achieved outcomes can be used as reference for implementing a DS detection system on the Bitcoin network. Notably, estimating the connectivity pattern of the Bitcoin network might allow to evaluate the minimum amount of nodes when polling.
In addition, the proposed model assumes that polled nodes are randomly selected so, in principle, the same approach can be applied also in the real system. Before to conclude, we provide some further observations. First, the Bitcoin network is a direct network (i.e. the edges can be represented as arrows) instead, in the proposed model, for the sake of simplicity we considered undirected networks. The central core of Bitcoin miners is not represented in our model. However, we suggest that an oracle working in the Bitcoin network should perform the polling only considering miners, since they can store a very high amount of connections. In particular, when the network grows, their average degree increases (i.e. d<km> dt > 0, with < k m > average degree of miners). It is worth to clarify that, even if we have analyzed also the case with only one polled node, in the real system at least three nodes should be selected, as only one could collude with a fraudulent user. Furthermore, we emphasize that when implementing a real oracle, the 'honest transaction' can be used as reference during the poll, i.e. an oracle would had only to evaluate if polled nodes received transactions that are conflicting with the honest one it knows. Eventually, beyond the specific application of our model to the problem of conflicting transactions, we suggest that it might be exploited also for facing problems in other fields, e.g. when the topology of a network can only be inferred and a spreading process involves more than one entity.