Table Of Content

Utrecht University Faculty of Science Department of Mathematics Bitcoin mining as cooperative network A pool of money Bachelor Thesis Wicorel van der Pol Student number 4174801 Supervisor: Dr. M. Ruijgrok June 15, 2017 Abstract Nowadays, cryptocurrencies are thriving. Due to the enormous growth of the Bitcoin Network, it was getting harder for miners to obtain Bitcoins and maintain a steady income. Therefore, mining pools were founded. Multiple miners combined their computational power and divided the rewards proportionally or by pay-per-share. In this thesis we will focus on the proportional distribution according to the computational power of each miner and analyse if there exists a way to optimally divide the profits among the miners. We will mold the Bitcoin network to a model of cooperative games with coalitional structures. The examination of the distribution within the pools led to a surprising conclusion: under certain con- ditions the DMS-CS-core will always be empty. When the partition function is constant-sum, monotonic and nonlinear with respect to the computational power, there exists no imputation which will satisfy each miner. In other words: there will always be an incentive for at least one miner to switch pools. It turns out that the delay of communication within a pool is crucial in this case. When the delay is below certain boundaries, the three beforementioned conditions will always apply, meaning the DMS-CS-core will always be empty. Thus, under certain conditions the network will never stabilize. i CONTENTS ii Contents 1 The Bitcoin Network 1 1.1 Public ledger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Block Chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Conflicting histories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 Pools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.6 (Dis)advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Miner Coalitional Game 7 2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 The rate of block addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Pools share . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 CS-core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 DMS-CS-core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Delay: the key parameter 14 3.1 Boundary d1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Boundary d2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 A Proof-of-work 18 B Notation overview 19 References I Credits for the illustration on the front page go to Manouk Locher. 1 THE BITCOIN NETWORK 1 Introduction Cryptocurrencies are on the march: since the appearance of Blackcoin, Dogecoin, Litecoin and many others an interesting new digital market has arisen. In 2009, the first cryptocurrency was brought to life: the Bitcoin Network. This innovative network uses bitcoins, which only consists of one’s and zero’s. The virtual money is transferred in a similar way information across the internet is transferred: from one individual to the other (also referred to as peer-to-peer) and hence has no or small transaction fees. The second innovative part about Bitcoin is that the network is decentralized; no central authority controls the flow of bitcoins. The Bitcoin Network has miners who use their computational power to protect the system agains malicious users. They are rewarded with freshly produced bitcoins. This way, no central authority is needed to decide when to release more bitcoins into the market. However, an unexpected growth of this network brought many miners to despair. It was getting harder, even impossible, to get a steady income of bitcoins by mining. This was fixed by working together in pools and splitting the profits. The rewards became lower, but more frequent. The manner in which the profits are divided, differ greatly between pools, which means that some miners might feel the need to switch strategy. Due to the establishment of pools, the structure of the network has become more complex. This raised ques- tions as whether an ideal strategy to divide the profits within a pool exists and which factors do influence the decision of the miners to switch between pools or even work solo. Therefore, this thesis will focus on certain tools from cooperative game theory to study the behaviour of the miners. Assuming that every miner wants a maximal payoff, we will examine when a miner is inclined to switch pools. During this process, multiple factors of the network will be considered. Eventually, it all comes down to the question whether there exists a cooperative miner game, with coalition structures, that doesn’t have an empty core. As it will turn out, when the communication between miners is efficient enough, there exists no distribution of the shares that will keep every miner satisfied. Therefore, the network of pools will always be in motion. 1 The Bitcoin Network Before we head on to the game theory of the Bitcoin Network, it will be quite useful to go through the basics first. Bitcoin is a digital cryptocurrency created by Satoshi Nakamoto. Creating a Bitcoin address (equivalent to a banking account) is free. Bitcoins can be bought with euros, dollars or other currency. Among other options can this be done at currency exchanges online, after which one can use it like any other currency; purchase anything you like in the form of transactions. The only difference is that bitcoins consist solely out of one’s and zero’s. Another unique aspect of the currency is the absence of a global authority that regulates the distribution of the money; the Bitcoin Network is completely decentralized. There is no central authority that subordinates a monetary policy. The total number of bitcoins that eventually will circulate in the market has already been set by Nakamoto: never will there be more than 21 million bitcoins. [[7] p.105] Considering the fact that the virtual, decentralized currency was a first and that is was not supported by the government, one might not be surprised that many people in Wall Street were sceptical about its endurance. In the beginning there were not many places where bitcoins were accepted as legal payment and many bitcoin exchanges failed. [[7] p.105] All in all, it had a rough start. However, what seemed to start as a quirky experiment suddenly flourished into something big: ”In the late spring of 2011, the price of [a] bitcoin had reached parity with the U.S. dollar, and by July, one bitcoin was worth $31.” [[3] p.2] This process has not deteriorated: on april the fifth 2017 one bitcoin was approximately worth $1118,- and on july the eleventh 2017 about $2902,- dollar. More and more people became aware of the profitable currency and started investing in it. Meanwhile, well-known companies like Subway, Steam, Wikipedia and Tesla started accepting bitcoins, which aided the network’s growth even more. [1] 1 THE BITCOIN NETWORK 2 1.1 Public ledger Digital money is faster to transmit than regular money. Still, every digital currency has one huge disadvan- tage: the double spending problem. Due to the absence of physical tokens (e.g. watermarks on papermoney), virtual money is quite easy to replicate. One can keep a copy of the string of bits, that represents your payment, and use this copy to pay for something else. This is referred to as the double spending problem. A solution to this problem is to list all holdings of each Bitcoin address in a public ledger. A transaction simply changes the records on this ledger. However, this inevitably leads to the neccessity of a record keeper. This third party has much influence: it can demand high fees and block or run transactions without consent. As stated before, the Bitcoin Network strives to keep it decentralized. Therefore, the third party has been replaced by miners. The network thus consists of two kinds of agents: the clients (bitcoin owners who make bitcoin transactions) and the miners. Together, all the miners authorize the bitcoin transfers. They check for double spending and other inconsistencies in the transactions using the information of the ledger. Meanwhile they compete to authorize a share of the transactions, so they are rewarded with a small amount of ’new’ bitcoins. Usually, a central authority decides when to print more money, but since the Bitcoin Network is decentralized, more bitcoins are added to the network by rewarding miners. Because all miners work together without a central authority, no unreasonably high fees can be demanded by one miner, nor can one of them decide to block transactions. Thus, all miners form a peer-to-peer network that keeps the Bitcoin Network secure. 1.2 Block Chain Each miner keeps a copy of the ledger and is continuously updated with all transactions that take place. Consequently, these transactions are public and therefore the ledger is transparent. The workload is not distributed. Every miner has to do the same verification. Now, what if two miners obtain a different ledger, because of double spending? Their information somehow has to be synchronized. In order to show how this is done in the Bitcoin Network, we first have to obtain more information about the details of Bitcoin’s main data structure: the block chain. All verified transactions of the Bitcoin Network are stored in the block chain. As the name suggests it consists of blocks linked together. It starts with the first block that was created at the beginning of the Bitcoin network and it is therefore called the genesis block. Every other block has a parent block, which is a predecessor of either one or two other blocks. A block in the chain contains the following: • batches of approved transactions, • a (unique) cryptographic hash to indicate the preceding block (the cryptographic hash can be seen as an identifier for the Bitcoin addresses which requested the transfer), • and a coinbase transaction (the reward for the lucky miner). Each miner verifies the signatures of the Bitcoin addresses which requested the transfer of bitcoins. The miner then forwards it to peers in the network. A block is called valid when the included transactions are not in conflict with the current balances which are given by the preceding blocks. Together, all these blocks keep a record of all the transactions since the creation of Bitcoin. Therefore, we can see the chain as the virtual representation of the transparent ledger. More information about how miners exactly verify a block, is available in Appendix A. 1.3 Conflicting histories Since blocks are created quite randomly, it often occurs that two miners extend the same parent block. When different miners extend this block at approximately the same time a fork is created in the block chain. The result is different ledgers spread throughout the network. However, the Bitcoin Network has two main rules that solve the problem of conflicting histories. 1. The use of proof-of-work To mine a block miners need to solve a computationally hard problem. The solution of this problem is 1 THE BITCOIN NETWORK 3 called the proof-of-work and is easy verifiable by every miner. Still, finding this solution is far from easy. A miner will simply have to let his computer try out many guesses until he finds the right one. When a proof-of-work is found, the miner adds it to the block and sends it to the other miners (by adding it to the block chain), so they can verify his solution. The miner who mined this block is rewarded with bitcoins. Because there is no simpler way of finding the proof-of-work, it is hard to create a block. The difficulty of the computational problem is set such that every ten minutes a block will be created by the entire network. This means that the time interval to update the other miners is hopefully long enough to notify each miner, before one of them creates a second block for the same parent. The proof-of-work therefore prevents forks in the block chain. 2. The longest chain concept When miners notice that different versions of the ledger exist, it means the chain has split and according to Bitcoin policy every miner must adopt the longest chain. This chain has the longest transaction history. The other version of the chain will be abandoned. Transactions that were included within this branch become invalid and are taken out of the ledger, by which the fork dissappears. The concept of the longest chain therefore resolves fork-situations. 1.4 Attacks Unfortunately, like any other system, there are people who try to find it’s weaknesses and exploit them. The fork-problem has been used by some to their advantage. Let’s consider such a person (an attacker) who just bought something, but suddenly wants to reverse his transaction, which has already been approved. He creates a fork in the block chain by adding a block to some part in the chain before the block that contains his approved transaction. (Remember that the ledger is transparent, so an attacker can easily figure out where this block is.) If this branch becomes long enough, the longest chain concept ensures that the blocks of the other branch will be removed from the block chain, thereby erasing all the transactions in these blocks from the public ledger. This includes the transaction the attacker wanted to reverse and so he had his way. This is called a double spending attack. However, we already learned that creating a block is very difficult. Being a succesful miner requires a lot of computational power. This means that if an attacker wants to create a fork, he needs to mine at a higher rate than the rest of the network. In other words, he must be incredibly well technologically equiped. Since the peer-to-peer network is far from a small community an attacker must posses at least 50% of the computational power of the entire network. Otherwise, his chances are nil. [[7] p.108] When a miner does obtain at least 50% of the network’s computational power, he can launch a 50% attack. Because he creates blocks at a faster pace than the rest of the network, he can adjust the block chain anyway he likes by double spending attacks. The attacker can even stop all transactions by generating a chain full of empty blocks. The only thing he can’t do is move funds he doesn’t control, because transactions always have a cryptographical signature of the sender. Still, it is a worrying concept. These attacks stress the need for a well-connected peer-to-peer network. If enough honest miners join the network, it will get less likely that an attacker has enough computational power to force a fork in the chain. In other words: the more honest miners, the more resilient the network is to double spending attacks. Miners keep the network safe. 1.5 Pools Due to the vast growth of the network it was getting harder and harder for miners to mine bitcoins. In the beginning people could mine using the processors of their computers. Then more and more people discovered that graphics cards (which are used for gaming) were more efficient. The downside is that they use a lot of electricity and therefore generate a lot of heat. Eventually, special chips were developed for mining bitcoins: ASIC (Application-Specific Integrated Circuit chips). Figure 1 shows the best Bitcoin mining hardware options based on the current (02/05/17) price per hash and electrical efficiency. 1 THE BITCOIN NETWORK 4 Figure 1: The best Bitcoin mining devices. Source: www.bitcoinmining.com Still, it could take years for slower miners to mine a block. Those who wanted a steady income, needed a new approach. Therefore, the idea arose to form groups of miners who can combine their computational power and share the profit, hence mining pools were set up. When a member mines a block the profit is divided among the entire pool, such that all the miners have a lower but more steady income. The reward for mining a block is included in the block as the coinbase transaction and consists of a small fee that is paid for adding transactions to the block and new bitcoins which are added to the market. Remember that there will never be more than 21 million bitcoins, so the number of bitcoins rewarded to the miners decreases with every mined block. The first blocks added to the Genesis Block were rewarded with 50 bitcoins. Every 210,000 blocks this number is halved. This means that the currency is deflationary: bitcoins may be lost and never replaced because of the fixed number that is available. [[7] p.110] The structure of each pool is as follows. Each pool has a pool manager and miners. The miners only communicate via their pool manager (also called a pool operator). The pool manager is able to send block headers (a hash to indicate the previous block) to his miners. First, the pool manager will run a Bitcoin node on behalf of the other miners in his pool, collecting transactions and assembling them into a block. He then adds his own address to this block and sends it to the miners in his pool. In return the miners send back nonce fields which are suitable according to the information in the received block headers. These nonce fields are basically attempts to find the beforementioned proof-of-work and they are used to show that every miner is working on this block. Each nonce that is sent, is called a share. When the right nonce is found the pool manager will receive the rewards and divide them among the miners in his pools. [[5] p.125,126] Their are multiple ways to divide the profits in a pool. The two most basic models are the proportional and pay-per-share model (see table 1). In the first model the payoff is distributed according to one’s relative computational power in the pool. This proportional model is low risk for the pool managers, because they only have to pay out when a valid block is found and they have received bitcoins. In a pay-per-share model the pool manager has to pay the miners for the shares they send, even when they are still working on a block. Of course the pool manager will also keep a part of the profit, but in this thesis we will focus on the share of the miners. Pool managers can communicate with one another, but instead of a header, they have to send an entire block to each other. Miners within their pool only need the block headers. These forms of communication cause delays in the network, which will later on turn out to be extremely important for our main question. 1 THE BITCOIN NETWORK 5 Method Approach PPS: The Pay-per-Share (PPS) approach offers an instant, guaranteed payout for each share that is solved by a miner. Miners are paid out from the pools existing balance and can withdraw their payout immediately. This model allows for the least possible variance in payment for miners while also transferring much of the risk to the pool’s operator. PROP: The Proportional approach offers a proportional distribution of the reward when a block is found amongst all workers, based off of the number of shares they have each found. Table 1: Distribution methods As you can see in figure 2 many different pools of varying sizes exist. Each pool has his own model to divide the rewards. Returning to the problem of the attackers, it is recommended to join the smaller pools. When a pool approaches 50% of the network’s block creation rate, it is a threat to the system. Even when the members of the pool are good-natured, it is still possible that a hacker manages to compromise the pool’s servers, risking a 50% attack. Therefore, many miners chose to join the smaller pools. Nevertheless, large mining pools are not completely undesirable. In March of 2013 a bug occured in the code, which resulted in a long-lasting fork in the block chain. The large mining pools were askes to downgrade to an older version of the protocol and due to this the fork dissolved. [[7] p.112] (a) Pie chart of current recommended pools (b) Origin of mentioned pools Figure 2: Source: https://www.bitcoinmining.com/bitcoin-mining-pools/ 1.6 (Dis)advantages All in all, the Bitcoin Network is a system that keeps evolving. Improvements certainly are desirable. One huge disadvantage is that every miner keeps a copy of the ledger, which means a lot of useless data is being stored. Some have suggested that this wasteful replication can be reduced to some extent. For example, everyday users of the currency don’t need the entire history of transactions, because some are too old to be of use. When a part of the chain is removed, they have to store less data and thus have lower storage costs. The economic influences are also getting stronger: large miners are profiting from their increasing bank accounts (e.g. they can produce their own hardware) and thereby eliminating smaller miners from the market. Another disadvantage is the loss of privacy. All transactions are made public in the ledger, so anyone can verify them. This transparancy is useful for organizations who want to show their clients how they are using 1 THE BITCOIN NETWORK 6 their money. Still, the privacy of individuals is at risk. Bitcoin users can create new pseudonyms for each transaction, but full anonymity will never be reached. Nevertheless, there are many advantages: spreading money like information across the internet is relatively fast, anyone can join the network (as a miner and as a client) and every transaction is verifiable because of the ledger. More importantly, there is no third party or central government which can demand high fees. Decentralization is the essence of the Bitcoin Network. Its ongoing goals are to maintain this decentralization while protocol changes and other developments take place. We have seen how the miners make the network more resilient against double spending attacks and therefore keep it secure. When the network began to grow and profits were obtained less often and more randomly, the miners chose to evolve with the system by creating pools. Maybe this one of the reasons why the Wall Street critics were shown wrong about Bitcoin: it is not a perfect system, but every member (miners, developers, regulators and adopters) can reveal its shortcomings and is involved in its innovation. Step-by-step Bitcoin is proving its worth. 2 MINER COALITIONAL GAME 7 2 Miner Coalitional Game We will now analyse the structure of the bitcoin miner network as a cooperative game. The pools will be called coalitions. Our miners can join a pool or work solo. They can only be part of one pool, so there is no overlap between the coalitions. A few other assumptions are made: • the reward for a mined block is fixed, • the miners follow the protocol as described in Chapter 1, • the delay in communication between miners is fixed, • and every miner i mines blocks according to a Poisson proces with parameter λpi. 2.1 Notation We start off with a general introduction to the notations1 commonly used in Game Theory. For now, we leave out the coalitional structures. There always is a grand coalition, I = {1, 2, . . . , n}, containing all agents. Every subset C ⊆ I, |C| > 1 is a coalition. We define the characteristic function v : 2I → R. For every coalition this function determines the payment that can be achieved because of the collaboration. Furthermore, an imputation is a vector x ∈ R|I| that divides all the gains of the grand coalition among the miners. It has the following properties: 1. the payoff of a player i is xi ≥ 0; 2. the payoff of a coalition x(C) = � i∈C xi; 3. x(I) = � i∈I xi = v(I). Furthermore, we define a weight vector w ∈ R|I|, with ∀i ∈ I : wi ≥ 0 and � i∈I wi = 1. Again, the definition for the coalitions is similar: w(C) = � i∈C wi. Now, we will consider a game with coalitional structures. The grand coalition will be divided by some partition S = {C1, C2, . . . , Cm}, with m coalitions and ∪m i=1Ci = I. Since no overlap is assumed, we know that Ci ∩ Cj = ∅ for i ̸= j. The utility of a coalition under the partition S of other agents is given by the partition function v(S, Ci) = vs(Ci). The set of all possible partitions of I is denoted by CS(I). This set contains all the possible coalitional structures over I. The delay between two coalitions Ci, Cj (i ̸= j) is denoted by D and the delay within a coalition Ci is denoted by d. So in case a miner wants to announce that he or she has succesfully mined a block, it will take d seconds for the poolmanager to be notified and an extra D seconds before the other poolmanagers receive the information. After 2d + D seconds all the other miners will be aware of this progress. We define P = {p1, p2, . . . , pn} as the distribution of the relative computational power among the miners. This will be used to determine the share of a miner in the pool. The computational power of agent i is denoted by pi ∈ [0, 1] and � i∈I pi = 1. Finally, we will use λ to indicate the number of blocks which is expected to be mined by the network per second. We can now define a Miner Network as Γ = ⟨M, S, P, D, d, λ⟩, where M is the set of miners instead of I. 1All the notations are collected in appendix B. 2 MINER COALITIONAL GAME 8 2.2 The rate of block addition We define β as the desired rate of block addition to the longest chain per second. The actual rate of block addition is defined by β(Γ), where Γ is a Miner Network. When β(Γ) increases, the network becomes more efficient, because more transactions are verified per second. A Miner Coalitional Game with Coalition Structures is defined as C = ⟨M, P, D, d, β⟩. In the network a threshold (t) is often adjusted such that every 10 minutes a block is mined. This concept is called retargeting and makes sure that β(Γ) stays close to β. For example, a lower t means a miner needs more attempts to obtain the nonce that produces the right hash (pt decreases). Therefore, more computational power is needed and thus the rate of longest chain growth (β(Γ)) decreases and the network can process less transactions in the same time. The adjustment of the threshold t results in a β(Γ) ≈ β. Therefore, we have set β(Γ) = β in our Miner Coalitional Game. Now let’s explore the boundaries of β(Γ). Proposition 2.2.1. Let Γ = ⟨M, S, P, D, d, λ⟩ be a Miner Network with |M| > 1 miners and D, d > 0. For every solo miner i, it holds that λ ≥ β(Γ) ≥ piλ. Proof. We will split the proof in two cases: • λ ≥ β(Γ) We know that β(Γ) is the rate of block addition to the longest chain. In the best case scenario each block that is mined per second (λ) will have a hash below the threshold. So each mined block will be added to the longest chain. This means β(Γ) = λ in the best case. In reality, not every mined block will be added to the longest chain, so therefore λ ≥ β(Γ). • β(Γ) ≥ piλ Remember that every miner i mines blocks according to a Poisson process with parameter piλ. Hence, the rate of block addition cannot be smaller than the speed at which an arbitrarily miner i is mining. If every miner mines blocks just as fast as the others, then β(Γ) = piλ for every i ∈ M. 2.3 Pools share Joining a pool makes it easier to mine, but the payoff must be divided in a suitable way. In this model each miner strives to obtain as many bitcoins as possible. Therefore, we define γ(Γ)i as the chance that a miner i has succesfully mined a block in a Miner Network Γ. We will sometimes just write γi instead of γ(Γ)i. Every miner wants to increase his or her γi, because you only receive bitcoins for mining a block which be- comes part of the longest chain. Thus, γi is the total share of a miner i in the network. The shares are divided proportionally, so ∀i : γi ∈ [0, 1]. Furthermore, the total share of a coalition is defined by γC = � i∈C γi. An increase of one’s share in the longest chain means an increase in one’s payoff in bitcoins. We can therefore set γi as our payoff function: ∀C ∈ S : vs(C) = γC. Now, let’s explore two extreme examples of a Miner Network and observe what this will do to β(Γ). We start off with a network that consists of one large pool, containing all the miners in the network: Proposition 2.3.1. Let Γ = ⟨M, {M}, P, D, d, λ⟩ be a Miner Network, then β(Γ) = λ 1+2dλ. Proof. Since S = {M}, we have a Miner Network with one pool and no solo miners. With one pool there only exists a delay between the pool manager and the miners (d). Let’s assume that a block X was mined and added to the longest chain. We want to know how long it takes to mine a second block which will be added to the longest chain in order to calculate β(Γ). When the pool manager becomes aware of block X, he will need d seconds to update the miners with a new target. Since λ is the expected number of blocks mined by the network per second, a new block Y will be created after approximately 1 λ seconds. It takes another d second for the miner i to notify the manager. 2 MINER COALITIONAL GAME 9 In the meantime (2d + λ−1) seconds have passed since the creation of block X. Therefore, the rate of block addition to the longest chain (β(Γ)) is equal to (2d + λ−1)−1 = 1 2d+ 1 λ = λ 2dλ+1. The other extreme example is a network with only two solo miners. From Sompolinsky and Zohar [6] we obtain Theorem 2.3.2. Let Γ be a Miner Network with two solo miners. Then β = β(Γ) = (λp1)2e2Dp1λ − (λp2)2e2Dp2λ λp1e2Dp1λ − λp2e2Dp2λ (1) and when p1 = p2 = 1 2 then it holds that β(Γ) = λ 2+Dλ 2+2Dλ. Proof. For the extensive complete proof of equation (1) we refer to [6] Appendix E. The special case of p1 = p2 = 1 2 is easier to explain. Note that by substituting p1 = p2 = 1 2 in equation (1), we would divide by zero. We need another approach. First, we write p2 = 1 − p1. We substitute this into equation (1): β(p1) = (λp1)2e2Dp1λ − (λ(1 − p1))2e2D(1−p1)λ λp1e2Dp1λ − λ(1 − p1)e2D(1−p1)λ = λ2p2 1e2Dp1λ − λ2(1 − p1)2e2Dλ−2Dp1λ λp1e2Dp1λ − λ(1 − p1)e2Dλ−2Dp1λ = λp2 1e2Dp1λ − λ(1 − p1)2e2Dλ−2Dp1λ p1e2Dp1λ − (1 − p1)e2Dλe−2Dp1λ (λ > 0) = λp2 1 − λ(1 − p1)2e2Dλ(1−2p1) p1 − (1 − p1)e2Dλ(1−2p1) (Divide everything by e2Dp1λ ̸= 0) = λ � p2 1 − (1 − p1)2e2Dλ(1−2p1)� p1 − (1 − p1)e2Dλ(1−2p1) . Then we use l’Hˆopital’s rule by taking the derivatives of p1 and calculating the limit of p1 → 1 2. [Numerator] β′ 1(p1) = λ � 2p1 + 2(1 − p1)e2Dλ(1−2p1) + (1 − p1)24Dλe2Dλ(1−2p1)� [Denominator] β′ 2(p1) = 1 + e2Dλ(1−2p1) + (1 − p1)4Dλe2Dλ(1−2p1) β(p1) = lim p1→ 1 2 β′ 1(p1) β′ 1(p1) = λ �1 + 1 + 1 4 · 4Dλ 1 + 1 + 1 2 · 4Dλ � = λ � 2 + Dλ 2 + 2Dλ � . In this Two Miner Network we can also provide a formula for the share of each player. Theorem 2.3.3. Let Γ be a Miner Network with two solo miners. Then γ(Γ)1 = p2 1eµp1 − p1p2( 2eµ−2 eµp1+eµp2−2 − 1) p2 1eµp1 − p2 2eµp2 (2) where µ = 2Dλ and γ(Γ)2 = 1 − γ(Γ)1. Proof. Again we refer to [6] Appendix E for the involved proof. In the case of p1 = p2 = 1 2 we can again use L’Hˆopital’s rule to obtain γ1 = γ2 = 1 2. This means that when the computational power of both solo miners is equal, they payoff will also be split equally. When for example p1 > p2 we know that µp1 > µp2. Therefore, eµp1 > eµp2 and also p2 1eµp1 > p2 2eµp2. Considering this 2 MINER COALITIONAL GAME 10 we can see that γ1 of equation (2) will increase and therefore γ2 = 1 − γ1 will decrease. This is in agreement with our proportional payoff system. More importantly, we will see a remarkable result when the difference between p1 and p2 is relatively small. To obtain figure 3a we fixed λ = 1. Furthermore we set p1 = 0.55, p2 = 0.45 and then plotted γ1 as a function of Dλ. Despite the small difference in computational power the first solo miner has a significant higher payoff when the delay increases. Note that the threshold of the bitcoin network is set such that every ten minutes a block will be mined, so in this case the expected number of blocks mined by the network per second would be 1 600. In figure 3b we can see for the same values of p1, p2 the function of the share has stabilized to the computational power of miner 1. However, we couldn’t plot D = 0, because this would involve dividing by zero. To calculate γi for µ = 2Dλ = 0 we use l’Hˆopital again and obtain: lim µ→0 γ(Γ)1 = lim µ→0 p2 1eµp1 − p1p2( 2eµ−2 eµp1+eµp2−2 − 1) p2 1eµp1 − p2 2eµp2 = p2 1 − p1p2(limµ→0( 2eµ−2 eµp1+eµp2−2 − 1)) p2 1 − p2 2 = p2 1 − p1p2(limµ→0( 2eµ−2 eµp1+eµp2−2 − 1)) p2 1 − p2 2 , L’Hˆopital: lim µ→0( 2eµ − 2 eµp1 + eµp2 − 2 − 1) = lim µ→0( 2eµ p1eµp1 + p2eµp2 − 2 − 1) = 2 p1 + p2 − 1 (p1 + p2 = 1) = 1. Substituting this back into the first equation gives us: lim µ→0 γ(Γ)1 = p2 1 − 2p1p2 p2 1 − p2 2 = p1(p1 − p2) (p1 − p2)(p1 + p2) = p1(p1 − p2) (p1 − p2) = p1. Thus, when Dλ = 0, the share of each miner becomes the proportion of computational power held by him or her (γi = pi). Corollary 2.3.4. Let Γ be a Miner Network with two solo miners as defined in theorems 2.3.2 and 2.3.3. If pi > 1 2, then γi ≥ pi and if Dλ > 0 then γi > pi. (a) λ = 1 (b) λ = 1 600 Figure 3: The share γ1 as a function of D ∈ [1, 20] for p1 = 0.55, p2 = 0.45. 2 MINER COALITIONAL GAME 11 2.4 CS-core We will now focus on Miner Networks with Coalitional Structures and investigate if there are imputations that divide the gains in a satisfying way for all the miners. Otherwise, the CS-core will be empty. In this section we won’t consider γi as our payoff function yet. We first want to study the general case. An imputation x is blocked when there exists a coalition B ⊆ M such that v(B) > � i∈B xi = x(B). This means that the miners are better off working as a group B, than when they stick to the situation of the grand coalition with the given imputation x. From here it follows that an imputation x belongs to the core if it is not blocked by any coalition: ∀C ⊂ I we have x(C) ≥ v(C). We don’t just want to look at the core of one coalition. The CS-core is defined for the entire partition S ∈ CS(M), so we have to consider every possible deviation from this partition. Only then can we make general conclusions about the Miner Network. The CS-core is defined by: {x ∈ R|I| | xi ≥ 0, ∀C ⊂ I : x(C) ≥ vSC(C)}, (3) where SC = {C} ∪ {{D \ C} | D ∈ S, D \ C ̸= ∅}. Note that: x(C) = vS(C), but not neccessarily: x(C) = vSC(C). An imputation only defines the payoff for the current coalition structure. The partition SC consists of a new coalition C and the same coalitions as S, but without the miners collected in C. Example 2.4.1. Let S = {{a, b}, {c, d}, {e}}. Now let’s say that miners a and e decide that they are better off working together. By creating their new coalition we get SC = {{a, e}, {b}, {c, d}}. An imputation is in the CS-core of the partition S if the for every SC we create, the payoff will be lower for the coalition C. △ Now we will see that under certain conditions this core will always be empty. We use the conditions as defined by Lewenberg et al. [4]. Assume that the payoff function v satisfies: 1. Constant-sum For every S ∈ CS(I) we have � C∈S vs(C) = c. This means that the total payoff to be distributed among the grand coalition is always equal to a constant positive number c. 2. Nonlinearity with respect to a weight vector w ∈ R+ A partition function v is nonlinear (with respect to a weight vector w) if: for every partition S with maxC∈S w(C) > minC∈S w(C), we have vs(Ci) > w(Ci) · � C∈S vs(C) for the maximum coalition Ci ∈ arg(maxC∈S w(C)). In other words: for every partition with different weights for the coalitions, the coalition with the biggest share (highest weight) has a payoff bigger than all the payoffs of the coalitions times its weight. This means its profit is higher than its share in the network. Let’s consider a partition S = {C1, . . . , Cm} of the Miner Network Γ = ⟨M, S, P, D, d, λ⟩ and apply these conditions to it. The proportional distribution of the computational power will be our weight vector. We are now ready to prove the emptiness of the CS-core of S. Theorem 2.4.2 (Emptiness of CS-core). Let v be the partition function of a coalitional game with coalition structures (CS) of M. Let p be a weight vector satisfying ∀i ∈ I : pi < 1 2. If v is constant-sum (1) and nonlinear (2) for p, then the CS-core is empty for every coalition structure of M. Proof. Let v be a partition function as described in the theorem. Recall that the CS-core of S is: {x ∈ R|M| | xi ≥ 0, ∀C ⊂ I : x(C) ≥ vSC(C)}, with SC = {C} ∪ {{D \ C} | D ∈ S, {D \ C} ̸= {∅}}. The proof consists of taking a partition S of a coalition structure and then proving for every imputation x that there exists a C ⊂ I such that vSC(C) > x(C). Take S ∈ CS(M) and let x be an imputation associated with S. Without loss of generality we can assume that M = {1, . . . , n} and � A∈S vS(A) = 1, ∀S ∈ CS(M). The exact number of miners is not essential and for every partition the payoff function must be constant for c > 0, so we choose c = 1. 2 MINER COALITIONAL GAME 12 Now, let ϵi = xi − pi for every i and assume without loss of generality that ϵ1 ≤ ϵ2 ≤ · · · ≤ ϵn. Note that � i∈M ϵi = (x1 − p1) + · · · + (xn − pn) = x1 + x2 + · · · + xn − (p1 + p2 + · · · + pn) = � i∈M xi − � i∈M pi = 1 − 1 = 0. Let’s now set D = M \ {n}. This coalition will disrupt the core. Since ϵn is the greatest ϵ we know that ϵn ≥ 0. This means � i∈D ϵi = � i∈M ϵi − ϵn ≤ 0 and so x(D) ≤ p(D). Likewise, pn < 1 2 and therefore � i∈D pi > 1 2. Thus, our coalition D has the highest weight vector (D ∈ arg(maxC∈S w(C)) and because v is non-linear with respect to p: vSC(D) > p(D) · � C∈S vs(C) > p(D) · 1 = p(D) ≥ x(D). This means that for every imputation x we can always construct a coalition D such that vSC(D) > x(D). Therefore, the CS-core is empty. The condition of constant-sum is crucial, because this means we can assume � C∈S vSC(C) is constant. The condition of nonlinearity is necessary in order to prove vSC(C) > p(C), which will lead to the desired result: vSC(C) > x(C). What does the emptiness of this core mean? We considered a grand coalition of miners M, who were divided into multiple coalitions {C1, . . . , Cm}. The total amount of bitcoins which are to be distributed is constant (condition 1). Furthermore, the partition function v is nonlinear with respect to a weight vector (condition 2), namely the computational power of each miner (and no miner has an overbalance in computational power). The result is an empty CS-core of S, so there will always be a coalition which benefits from deviating from the current situation S. In short, there exist no distribution of the payoffs that will keep the miners in every coalition satisfied. 2.5 DMS-CS-core The emptiness of the CS-core is a strong notion. An imputation mustn’t be blocked by any possible coalition. Yet, there might be situations where certain subsets of agents can’t form a new coalition. We will constrain the number of possible partitions by only allowing the coalitions to split or merge. Therefore, we will introduce the concept of D-stability. We define D : CS(M) → 2M as the defection function. This function maps each partition to a set of possible coalitions. This means that a coalition C can only deviate from the current partition of S if C ∈ D(S). With this additional demand we might find an imputation that isn’t blocked by any coalition. There are two options for a coalition C: • a subset of C canmerge with a subset of another coalition {C′ ∪ D′ | C′ ⊂ C, D′ ⊂ D}; • C can split into two subsets C = C1 ∪ C2. An imputation x is DMS-stable if for every C ∈ D(S)MS we have x(C) ≥ vSC(C). The DMS-CS-core exists of all the DMS-stable imputations that are associated with S. Example 2.5.1. To illustrate that there are less constraints on an imputation x for the DMS-CS-core, consider a partition S = {{a}, {b}, {c}, {d, e}}. While checking if an imputation x is in a core of S, we must consider each possible alternative partition (SC) of S. The partition S2 = {{a}, {b}, {c, d}, {e}} is the result

ebook img

Thesis Bitcoin PDF

23 Pages·2021·2.07 MB·English
by  
#bitcoin #bitcoin mining
Save to my drive
Quick download
Download
Upgrade Premium
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview Thesis Bitcoin

Utrecht University Faculty of Science Department of Mathematics Bitcoin mining as cooperative network A pool of money Bachelor Thesis Wicorel van der Pol Student number 4174801 Supervisor: Dr. M. Ruijgrok June 15, 2017 Abstract Nowadays, cryptocurrencies are thriving. Due to the enormous growth of the Bitcoin Network, it was getting harder for miners to obtain Bitcoins and maintain a steady income. Therefore, mining pools were founded. Multiple miners combined their computational power and divided the rewards proportionally or by pay-per-share. In this thesis we will focus on the proportional distribution according to the computational power of each miner and analyse if there exists a way to optimally divide the profits among the miners. We will mold the Bitcoin network to a model of cooperative games with coalitional structures. The examination of the distribution within the pools led to a surprising conclusion: under certain con- ditions the DMS-CS-core will always be empty. When the partition function is constant-sum, monotonic and nonlinear with respect to the computational power, there exists no imputation which will satisfy each miner. In other words: there will always be an incentive for at least one miner to switch pools. It turns out that the delay of communication within a pool is crucial in this case. When the delay is below certain boundaries, the three beforementioned conditions will always apply, meaning the DMS-CS-core will always be empty. Thus, under certain conditions the network will never stabilize. i CONTENTS ii Contents 1 The Bitcoin Network 1 1.1 Public ledger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Block Chain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Conflicting histories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 Pools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.6 (Dis)advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Miner Coalitional Game 7 2.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 The rate of block addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 Pools share . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 CS-core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 DMS-CS-core . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Delay: the key parameter 14 3.1 Boundary d1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Boundary d2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 A Proof-of-work 18 B Notation overview 19 References I Credits for the illustration on the front page go to Manouk Locher. 1 THE BITCOIN NETWORK 1 Introduction Cryptocurrencies are on the march: since the appearance of Blackcoin, Dogecoin, Litecoin and many others an interesting new digital market has arisen. In 2009, the first cryptocurrency was brought to life: the Bitcoin Network. This innovative network uses bitcoins, which only consists of one’s and zero’s. The virtual money is transferred in a similar way information across the internet is transferred: from one individual to the other (also referred to as peer-to-peer) and hence has no or small transaction fees. The second innovative part about Bitcoin is that the network is decentralized; no central authority controls the flow of bitcoins. The Bitcoin Network has miners who use their computational power to protect the system agains malicious users. They are rewarded with freshly produced bitcoins. This way, no central authority is needed to decide when to release more bitcoins into the market. However, an unexpected growth of this network brought many miners to despair. It was getting harder, even impossible, to get a steady income of bitcoins by mining. This was fixed by working together in pools and splitting the profits. The rewards became lower, but more frequent. The manner in which the profits are divided, differ greatly between pools, which means that some miners might feel the need to switch strategy. Due to the establishment of pools, the structure of the network has become more complex. This raised ques- tions as whether an ideal strategy to divide the profits within a pool exists and which factors do influence the decision of the miners to switch between pools or even work solo. Therefore, this thesis will focus on certain tools from cooperative game theory to study the behaviour of the miners. Assuming that every miner wants a maximal payoff, we will examine when a miner is inclined to switch pools. During this process, multiple factors of the network will be considered. Eventually, it all comes down to the question whether there exists a cooperative miner game, with coalition structures, that doesn’t have an empty core. As it will turn out, when the communication between miners is efficient enough, there exists no distribution of the shares that will keep every miner satisfied. Therefore, the network of pools will always be in motion. 1 The Bitcoin Network Before we head on to the game theory of the Bitcoin Network, it will be quite useful to go through the basics first. Bitcoin is a digital cryptocurrency created by Satoshi Nakamoto. Creating a Bitcoin address (equivalent to a banking account) is free. Bitcoins can be bought with euros, dollars or other currency. Among other options can this be done at currency exchanges online, after which one can use it like any other currency; purchase anything you like in the form of transactions. The only difference is that bitcoins consist solely out of one’s and zero’s. Another unique aspect of the currency is the absence of a global authority that regulates the distribution of the money; the Bitcoin Network is completely decentralized. There is no central authority that subordinates a monetary policy. The total number of bitcoins that eventually will circulate in the market has already been set by Nakamoto: never will there be more than 21 million bitcoins. [[7] p.105] Considering the fact that the virtual, decentralized currency was a first and that is was not supported by the government, one might not be surprised that many people in Wall Street were sceptical about its endurance. In the beginning there were not many places where bitcoins were accepted as legal payment and many bitcoin exchanges failed. [[7] p.105] All in all, it had a rough start. However, what seemed to start as a quirky experiment suddenly flourished into something big: ”In the late spring of 2011, the price of [a] bitcoin had reached parity with the U.S. dollar, and by July, one bitcoin was worth $31.” [[3] p.2] This process has not deteriorated: on april the fifth 2017 one bitcoin was approximately worth $1118,- and on july the eleventh 2017 about $2902,- dollar. More and more people became aware of the profitable currency and started investing in it. Meanwhile, well-known companies like Subway, Steam, Wikipedia and Tesla started accepting bitcoins, which aided the network’s growth even more. [1] 1 THE BITCOIN NETWORK 2 1.1 Public ledger Digital money is faster to transmit than regular money. Still, every digital currency has one huge disadvan- tage: the double spending problem. Due to the absence of physical tokens (e.g. watermarks on papermoney), virtual money is quite easy to replicate. One can keep a copy of the string of bits, that represents your payment, and use this copy to pay for something else. This is referred to as the double spending problem. A solution to this problem is to list all holdings of each Bitcoin address in a public ledger. A transaction simply changes the records on this ledger. However, this inevitably leads to the neccessity of a record keeper. This third party has much influence: it can demand high fees and block or run transactions without consent. As stated before, the Bitcoin Network strives to keep it decentralized. Therefore, the third party has been replaced by miners. The network thus consists of two kinds of agents: the clients (bitcoin owners who make bitcoin transactions) and the miners. Together, all the miners authorize the bitcoin transfers. They check for double spending and other inconsistencies in the transactions using the information of the ledger. Meanwhile they compete to authorize a share of the transactions, so they are rewarded with a small amount of ’new’ bitcoins. Usually, a central authority decides when to print more money, but since the Bitcoin Network is decentralized, more bitcoins are added to the network by rewarding miners. Because all miners work together without a central authority, no unreasonably high fees can be demanded by one miner, nor can one of them decide to block transactions. Thus, all miners form a peer-to-peer network that keeps the Bitcoin Network secure. 1.2 Block Chain Each miner keeps a copy of the ledger and is continuously updated with all transactions that take place. Consequently, these transactions are public and therefore the ledger is transparent. The workload is not distributed. Every miner has to do the same verification. Now, what if two miners obtain a different ledger, because of double spending? Their information somehow has to be synchronized. In order to show how this is done in the Bitcoin Network, we first have to obtain more information about the details of Bitcoin’s main data structure: the block chain. All verified transactions of the Bitcoin Network are stored in the block chain. As the name suggests it consists of blocks linked together. It starts with the first block that was created at the beginning of the Bitcoin network and it is therefore called the genesis block. Every other block has a parent block, which is a predecessor of either one or two other blocks. A block in the chain contains the following: • batches of approved transactions, • a (unique) cryptographic hash to indicate the preceding block (the cryptographic hash can be seen as an identifier for the Bitcoin addresses which requested the transfer), • and a coinbase transaction (the reward for the lucky miner). Each miner verifies the signatures of the Bitcoin addresses which requested the transfer of bitcoins. The miner then forwards it to peers in the network. A block is called valid when the included transactions are not in conflict with the current balances which are given by the preceding blocks. Together, all these blocks keep a record of all the transactions since the creation of Bitcoin. Therefore, we can see the chain as the virtual representation of the transparent ledger. More information about how miners exactly verify a block, is available in Appendix A. 1.3 Conflicting histories Since blocks are created quite randomly, it often occurs that two miners extend the same parent block. When different miners extend this block at approximately the same time a fork is created in the block chain. The result is different ledgers spread throughout the network. However, the Bitcoin Network has two main rules that solve the problem of conflicting histories. 1. The use of proof-of-work To mine a block miners need to solve a computationally hard problem. The solution of this problem is 1 THE BITCOIN NETWORK 3 called the proof-of-work and is easy verifiable by every miner. Still, finding this solution is far from easy. A miner will simply have to let his computer try out many guesses until he finds the right one. When a proof-of-work is found, the miner adds it to the block and sends it to the other miners (by adding it to the block chain), so they can verify his solution. The miner who mined this block is rewarded with bitcoins. Because there is no simpler way of finding the proof-of-work, it is hard to create a block. The difficulty of the computational problem is set such that every ten minutes a block will be created by the entire network. This means that the time interval to update the other miners is hopefully long enough to notify each miner, before one of them creates a second block for the same parent. The proof-of-work therefore prevents forks in the block chain. 2. The longest chain concept When miners notice that different versions of the ledger exist, it means the chain has split and according to Bitcoin policy every miner must adopt the longest chain. This chain has the longest transaction history. The other version of the chain will be abandoned. Transactions that were included within this branch become invalid and are taken out of the ledger, by which the fork dissappears. The concept of the longest chain therefore resolves fork-situations. 1.4 Attacks Unfortunately, like any other system, there are people who try to find it’s weaknesses and exploit them. The fork-problem has been used by some to their advantage. Let’s consider such a person (an attacker) who just bought something, but suddenly wants to reverse his transaction, which has already been approved. He creates a fork in the block chain by adding a block to some part in the chain before the block that contains his approved transaction. (Remember that the ledger is transparent, so an attacker can easily figure out where this block is.) If this branch becomes long enough, the longest chain concept ensures that the blocks of the other branch will be removed from the block chain, thereby erasing all the transactions in these blocks from the public ledger. This includes the transaction the attacker wanted to reverse and so he had his way. This is called a double spending attack. However, we already learned that creating a block is very difficult. Being a succesful miner requires a lot of computational power. This means that if an attacker wants to create a fork, he needs to mine at a higher rate than the rest of the network. In other words, he must be incredibly well technologically equiped. Since the peer-to-peer network is far from a small community an attacker must posses at least 50% of the computational power of the entire network. Otherwise, his chances are nil. [[7] p.108] When a miner does obtain at least 50% of the network’s computational power, he can launch a 50% attack. Because he creates blocks at a faster pace than the rest of the network, he can adjust the block chain anyway he likes by double spending attacks. The attacker can even stop all transactions by generating a chain full of empty blocks. The only thing he can’t do is move funds he doesn’t control, because transactions always have a cryptographical signature of the sender. Still, it is a worrying concept. These attacks stress the need for a well-connected peer-to-peer network. If enough honest miners join the network, it will get less likely that an attacker has enough computational power to force a fork in the chain. In other words: the more honest miners, the more resilient the network is to double spending attacks. Miners keep the network safe. 1.5 Pools Due to the vast growth of the network it was getting harder and harder for miners to mine bitcoins. In the beginning people could mine using the processors of their computers. Then more and more people discovered that graphics cards (which are used for gaming) were more efficient. The downside is that they use a lot of electricity and therefore generate a lot of heat. Eventually, special chips were developed for mining bitcoins: ASIC (Application-Specific Integrated Circuit chips). Figure 1 shows the best Bitcoin mining hardware options based on the current (02/05/17) price per hash and electrical efficiency. 1 THE BITCOIN NETWORK 4 Figure 1: The best Bitcoin mining devices. Source: www.bitcoinmining.com Still, it could take years for slower miners to mine a block. Those who wanted a steady income, needed a new approach. Therefore, the idea arose to form groups of miners who can combine their computational power and share the profit, hence mining pools were set up. When a member mines a block the profit is divided among the entire pool, such that all the miners have a lower but more steady income. The reward for mining a block is included in the block as the coinbase transaction and consists of a small fee that is paid for adding transactions to the block and new bitcoins which are added to the market. Remember that there will never be more than 21 million bitcoins, so the number of bitcoins rewarded to the miners decreases with every mined block. The first blocks added to the Genesis Block were rewarded with 50 bitcoins. Every 210,000 blocks this number is halved. This means that the currency is deflationary: bitcoins may be lost and never replaced because of the fixed number that is available. [[7] p.110] The structure of each pool is as follows. Each pool has a pool manager and miners. The miners only communicate via their pool manager (also called a pool operator). The pool manager is able to send block headers (a hash to indicate the previous block) to his miners. First, the pool manager will run a Bitcoin node on behalf of the other miners in his pool, collecting transactions and assembling them into a block. He then adds his own address to this block and sends it to the miners in his pool. In return the miners send back nonce fields which are suitable according to the information in the received block headers. These nonce fields are basically attempts to find the beforementioned proof-of-work and they are used to show that every miner is working on this block. Each nonce that is sent, is called a share. When the right nonce is found the pool manager will receive the rewards and divide them among the miners in his pools. [[5] p.125,126] Their are multiple ways to divide the profits in a pool. The two most basic models are the proportional and pay-per-share model (see table 1). In the first model the payoff is distributed according to one’s relative computational power in the pool. This proportional model is low risk for the pool managers, because they only have to pay out when a valid block is found and they have received bitcoins. In a pay-per-share model the pool manager has to pay the miners for the shares they send, even when they are still working on a block. Of course the pool manager will also keep a part of the profit, but in this thesis we will focus on the share of the miners. Pool managers can communicate with one another, but instead of a header, they have to send an entire block to each other. Miners within their pool only need the block headers. These forms of communication cause delays in the network, which will later on turn out to be extremely important for our main question. 1 THE BITCOIN NETWORK 5 Method Approach PPS: The Pay-per-Share (PPS) approach offers an instant, guaranteed payout for each share that is solved by a miner. Miners are paid out from the pools existing balance and can withdraw their payout immediately. This model allows for the least possible variance in payment for miners while also transferring much of the risk to the pool’s operator. PROP: The Proportional approach offers a proportional distribution of the reward when a block is found amongst all workers, based off of the number of shares they have each found. Table 1: Distribution methods As you can see in figure 2 many different pools of varying sizes exist. Each pool has his own model to divide the rewards. Returning to the problem of the attackers, it is recommended to join the smaller pools. When a pool approaches 50% of the network’s block creation rate, it is a threat to the system. Even when the members of the pool are good-natured, it is still possible that a hacker manages to compromise the pool’s servers, risking a 50% attack. Therefore, many miners chose to join the smaller pools. Nevertheless, large mining pools are not completely undesirable. In March of 2013 a bug occured in the code, which resulted in a long-lasting fork in the block chain. The large mining pools were askes to downgrade to an older version of the protocol and due to this the fork dissolved. [[7] p.112] (a) Pie chart of current recommended pools (b) Origin of mentioned pools Figure 2: Source: https://www.bitcoinmining.com/bitcoin-mining-pools/ 1.6 (Dis)advantages All in all, the Bitcoin Network is a system that keeps evolving. Improvements certainly are desirable. One huge disadvantage is that every miner keeps a copy of the ledger, which means a lot of useless data is being stored. Some have suggested that this wasteful replication can be reduced to some extent. For example, everyday users of the currency don’t need the entire history of transactions, because some are too old to be of use. When a part of the chain is removed, they have to store less data and thus have lower storage costs. The economic influences are also getting stronger: large miners are profiting from their increasing bank accounts (e.g. they can produce their own hardware) and thereby eliminating smaller miners from the market. Another disadvantage is the loss of privacy. All transactions are made public in the ledger, so anyone can verify them. This transparancy is useful for organizations who want to show their clients how they are using 1 THE BITCOIN NETWORK 6 their money. Still, the privacy of individuals is at risk. Bitcoin users can create new pseudonyms for each transaction, but full anonymity will never be reached. Nevertheless, there are many advantages: spreading money like information across the internet is relatively fast, anyone can join the network (as a miner and as a client) and every transaction is verifiable because of the ledger. More importantly, there is no third party or central government which can demand high fees. Decentralization is the essence of the Bitcoin Network. Its ongoing goals are to maintain this decentralization while protocol changes and other developments take place. We have seen how the miners make the network more resilient against double spending attacks and therefore keep it secure. When the network began to grow and profits were obtained less often and more randomly, the miners chose to evolve with the system by creating pools. Maybe this one of the reasons why the Wall Street critics were shown wrong about Bitcoin: it is not a perfect system, but every member (miners, developers, regulators and adopters) can reveal its shortcomings and is involved in its innovation. Step-by-step Bitcoin is proving its worth. 2 MINER COALITIONAL GAME 7 2 Miner Coalitional Game We will now analyse the structure of the bitcoin miner network as a cooperative game. The pools will be called coalitions. Our miners can join a pool or work solo. They can only be part of one pool, so there is no overlap between the coalitions. A few other assumptions are made: • the reward for a mined block is fixed, • the miners follow the protocol as described in Chapter 1, • the delay in communication between miners is fixed, • and every miner i mines blocks according to a Poisson proces with parameter λpi. 2.1 Notation We start off with a general introduction to the notations1 commonly used in Game Theory. For now, we leave out the coalitional structures. There always is a grand coalition, I = {1, 2, . . . , n}, containing all agents. Every subset C ⊆ I, |C| > 1 is a coalition. We define the characteristic function v : 2I → R. For every coalition this function determines the payment that can be achieved because of the collaboration. Furthermore, an imputation is a vector x ∈ R|I| that divides all the gains of the grand coalition among the miners. It has the following properties: 1. the payoff of a player i is xi ≥ 0; 2. the payoff of a coalition x(C) = � i∈C xi; 3. x(I) = � i∈I xi = v(I). Furthermore, we define a weight vector w ∈ R|I|, with ∀i ∈ I : wi ≥ 0 and � i∈I wi = 1. Again, the definition for the coalitions is similar: w(C) = � i∈C wi. Now, we will consider a game with coalitional structures. The grand coalition will be divided by some partition S = {C1, C2, . . . , Cm}, with m coalitions and ∪m i=1Ci = I. Since no overlap is assumed, we know that Ci ∩ Cj = ∅ for i ̸= j. The utility of a coalition under the partition S of other agents is given by the partition function v(S, Ci) = vs(Ci). The set of all possible partitions of I is denoted by CS(I). This set contains all the possible coalitional structures over I. The delay between two coalitions Ci, Cj (i ̸= j) is denoted by D and the delay within a coalition Ci is denoted by d. So in case a miner wants to announce that he or she has succesfully mined a block, it will take d seconds for the poolmanager to be notified and an extra D seconds before the other poolmanagers receive the information. After 2d + D seconds all the other miners will be aware of this progress. We define P = {p1, p2, . . . , pn} as the distribution of the relative computational power among the miners. This will be used to determine the share of a miner in the pool. The computational power of agent i is denoted by pi ∈ [0, 1] and � i∈I pi = 1. Finally, we will use λ to indicate the number of blocks which is expected to be mined by the network per second. We can now define a Miner Network as Γ = ⟨M, S, P, D, d, λ⟩, where M is the set of miners instead of I. 1All the notations are collected in appendix B. 2 MINER COALITIONAL GAME 8 2.2 The rate of block addition We define β as the desired rate of block addition to the longest chain per second. The actual rate of block addition is defined by β(Γ), where Γ is a Miner Network. When β(Γ) increases, the network becomes more efficient, because more transactions are verified per second. A Miner Coalitional Game with Coalition Structures is defined as C = ⟨M, P, D, d, β⟩. In the network a threshold (t) is often adjusted such that every 10 minutes a block is mined. This concept is called retargeting and makes sure that β(Γ) stays close to β. For example, a lower t means a miner needs more attempts to obtain the nonce that produces the right hash (pt decreases). Therefore, more computational power is needed and thus the rate of longest chain growth (β(Γ)) decreases and the network can process less transactions in the same time. The adjustment of the threshold t results in a β(Γ) ≈ β. Therefore, we have set β(Γ) = β in our Miner Coalitional Game. Now let’s explore the boundaries of β(Γ). Proposition 2.2.1. Let Γ = ⟨M, S, P, D, d, λ⟩ be a Miner Network with |M| > 1 miners and D, d > 0. For every solo miner i, it holds that λ ≥ β(Γ) ≥ piλ. Proof. We will split the proof in two cases: • λ ≥ β(Γ) We know that β(Γ) is the rate of block addition to the longest chain. In the best case scenario each block that is mined per second (λ) will have a hash below the threshold. So each mined block will be added to the longest chain. This means β(Γ) = λ in the best case. In reality, not every mined block will be added to the longest chain, so therefore λ ≥ β(Γ). • β(Γ) ≥ piλ Remember that every miner i mines blocks according to a Poisson process with parameter piλ. Hence, the rate of block addition cannot be smaller than the speed at which an arbitrarily miner i is mining. If every miner mines blocks just as fast as the others, then β(Γ) = piλ for every i ∈ M. 2.3 Pools share Joining a pool makes it easier to mine, but the payoff must be divided in a suitable way. In this model each miner strives to obtain as many bitcoins as possible. Therefore, we define γ(Γ)i as the chance that a miner i has succesfully mined a block in a Miner Network Γ. We will sometimes just write γi instead of γ(Γ)i. Every miner wants to increase his or her γi, because you only receive bitcoins for mining a block which be- comes part of the longest chain. Thus, γi is the total share of a miner i in the network. The shares are divided proportionally, so ∀i : γi ∈ [0, 1]. Furthermore, the total share of a coalition is defined by γC = � i∈C γi. An increase of one’s share in the longest chain means an increase in one’s payoff in bitcoins. We can therefore set γi as our payoff function: ∀C ∈ S : vs(C) = γC. Now, let’s explore two extreme examples of a Miner Network and observe what this will do to β(Γ). We start off with a network that consists of one large pool, containing all the miners in the network: Proposition 2.3.1. Let Γ = ⟨M, {M}, P, D, d, λ⟩ be a Miner Network, then β(Γ) = λ 1+2dλ. Proof. Since S = {M}, we have a Miner Network with one pool and no solo miners. With one pool there only exists a delay between the pool manager and the miners (d). Let’s assume that a block X was mined and added to the longest chain. We want to know how long it takes to mine a second block which will be added to the longest chain in order to calculate β(Γ). When the pool manager becomes aware of block X, he will need d seconds to update the miners with a new target. Since λ is the expected number of blocks mined by the network per second, a new block Y will be created after approximately 1 λ seconds. It takes another d second for the miner i to notify the manager. 2 MINER COALITIONAL GAME 9 In the meantime (2d + λ−1) seconds have passed since the creation of block X. Therefore, the rate of block addition to the longest chain (β(Γ)) is equal to (2d + λ−1)−1 = 1 2d+ 1 λ = λ 2dλ+1. The other extreme example is a network with only two solo miners. From Sompolinsky and Zohar [6] we obtain Theorem 2.3.2. Let Γ be a Miner Network with two solo miners. Then β = β(Γ) = (λp1)2e2Dp1λ − (λp2)2e2Dp2λ λp1e2Dp1λ − λp2e2Dp2λ (1) and when p1 = p2 = 1 2 then it holds that β(Γ) = λ 2+Dλ 2+2Dλ. Proof. For the extensive complete proof of equation (1) we refer to [6] Appendix E. The special case of p1 = p2 = 1 2 is easier to explain. Note that by substituting p1 = p2 = 1 2 in equation (1), we would divide by zero. We need another approach. First, we write p2 = 1 − p1. We substitute this into equation (1): β(p1) = (λp1)2e2Dp1λ − (λ(1 − p1))2e2D(1−p1)λ λp1e2Dp1λ − λ(1 − p1)e2D(1−p1)λ = λ2p2 1e2Dp1λ − λ2(1 − p1)2e2Dλ−2Dp1λ λp1e2Dp1λ − λ(1 − p1)e2Dλ−2Dp1λ = λp2 1e2Dp1λ − λ(1 − p1)2e2Dλ−2Dp1λ p1e2Dp1λ − (1 − p1)e2Dλe−2Dp1λ (λ > 0) = λp2 1 − λ(1 − p1)2e2Dλ(1−2p1) p1 − (1 − p1)e2Dλ(1−2p1) (Divide everything by e2Dp1λ ̸= 0) = λ � p2 1 − (1 − p1)2e2Dλ(1−2p1)� p1 − (1 − p1)e2Dλ(1−2p1) . Then we use l’Hˆopital’s rule by taking the derivatives of p1 and calculating the limit of p1 → 1 2. [Numerator] β′ 1(p1) = λ � 2p1 + 2(1 − p1)e2Dλ(1−2p1) + (1 − p1)24Dλe2Dλ(1−2p1)� [Denominator] β′ 2(p1) = 1 + e2Dλ(1−2p1) + (1 − p1)4Dλe2Dλ(1−2p1) β(p1) = lim p1→ 1 2 β′ 1(p1) β′ 1(p1) = λ �1 + 1 + 1 4 · 4Dλ 1 + 1 + 1 2 · 4Dλ � = λ � 2 + Dλ 2 + 2Dλ � . In this Two Miner Network we can also provide a formula for the share of each player. Theorem 2.3.3. Let Γ be a Miner Network with two solo miners. Then γ(Γ)1 = p2 1eµp1 − p1p2( 2eµ−2 eµp1+eµp2−2 − 1) p2 1eµp1 − p2 2eµp2 (2) where µ = 2Dλ and γ(Γ)2 = 1 − γ(Γ)1. Proof. Again we refer to [6] Appendix E for the involved proof. In the case of p1 = p2 = 1 2 we can again use L’Hˆopital’s rule to obtain γ1 = γ2 = 1 2. This means that when the computational power of both solo miners is equal, they payoff will also be split equally. When for example p1 > p2 we know that µp1 > µp2. Therefore, eµp1 > eµp2 and also p2 1eµp1 > p2 2eµp2. Considering this 2 MINER COALITIONAL GAME 10 we can see that γ1 of equation (2) will increase and therefore γ2 = 1 − γ1 will decrease. This is in agreement with our proportional payoff system. More importantly, we will see a remarkable result when the difference between p1 and p2 is relatively small. To obtain figure 3a we fixed λ = 1. Furthermore we set p1 = 0.55, p2 = 0.45 and then plotted γ1 as a function of Dλ. Despite the small difference in computational power the first solo miner has a significant higher payoff when the delay increases. Note that the threshold of the bitcoin network is set such that every ten minutes a block will be mined, so in this case the expected number of blocks mined by the network per second would be 1 600. In figure 3b we can see for the same values of p1, p2 the function of the share has stabilized to the computational power of miner 1. However, we couldn’t plot D = 0, because this would involve dividing by zero. To calculate γi for µ = 2Dλ = 0 we use l’Hˆopital again and obtain: lim µ→0 γ(Γ)1 = lim µ→0 p2 1eµp1 − p1p2( 2eµ−2 eµp1+eµp2−2 − 1) p2 1eµp1 − p2 2eµp2 = p2 1 − p1p2(limµ→0( 2eµ−2 eµp1+eµp2−2 − 1)) p2 1 − p2 2 = p2 1 − p1p2(limµ→0( 2eµ−2 eµp1+eµp2−2 − 1)) p2 1 − p2 2 , L’Hˆopital: lim µ→0( 2eµ − 2 eµp1 + eµp2 − 2 − 1) = lim µ→0( 2eµ p1eµp1 + p2eµp2 − 2 − 1) = 2 p1 + p2 − 1 (p1 + p2 = 1) = 1. Substituting this back into the first equation gives us: lim µ→0 γ(Γ)1 = p2 1 − 2p1p2 p2 1 − p2 2 = p1(p1 − p2) (p1 − p2)(p1 + p2) = p1(p1 − p2) (p1 − p2) = p1. Thus, when Dλ = 0, the share of each miner becomes the proportion of computational power held by him or her (γi = pi). Corollary 2.3.4. Let Γ be a Miner Network with two solo miners as defined in theorems 2.3.2 and 2.3.3. If pi > 1 2, then γi ≥ pi and if Dλ > 0 then γi > pi. (a) λ = 1 (b) λ = 1 600 Figure 3: The share γ1 as a function of D ∈ [1, 20] for p1 = 0.55, p2 = 0.45. 2 MINER COALITIONAL GAME 11 2.4 CS-core We will now focus on Miner Networks with Coalitional Structures and investigate if there are imputations that divide the gains in a satisfying way for all the miners. Otherwise, the CS-core will be empty. In this section we won’t consider γi as our payoff function yet. We first want to study the general case. An imputation x is blocked when there exists a coalition B ⊆ M such that v(B) > � i∈B xi = x(B). This means that the miners are better off working as a group B, than when they stick to the situation of the grand coalition with the given imputation x. From here it follows that an imputation x belongs to the core if it is not blocked by any coalition: ∀C ⊂ I we have x(C) ≥ v(C). We don’t just want to look at the core of one coalition. The CS-core is defined for the entire partition S ∈ CS(M), so we have to consider every possible deviation from this partition. Only then can we make general conclusions about the Miner Network. The CS-core is defined by: {x ∈ R|I| | xi ≥ 0, ∀C ⊂ I : x(C) ≥ vSC(C)}, (3) where SC = {C} ∪ {{D \ C} | D ∈ S, D \ C ̸= ∅}. Note that: x(C) = vS(C), but not neccessarily: x(C) = vSC(C). An imputation only defines the payoff for the current coalition structure. The partition SC consists of a new coalition C and the same coalitions as S, but without the miners collected in C. Example 2.4.1. Let S = {{a, b}, {c, d}, {e}}. Now let’s say that miners a and e decide that they are better off working together. By creating their new coalition we get SC = {{a, e}, {b}, {c, d}}. An imputation is in the CS-core of the partition S if the for every SC we create, the payoff will be lower for the coalition C. △ Now we will see that under certain conditions this core will always be empty. We use the conditions as defined by Lewenberg et al. [4]. Assume that the payoff function v satisfies: 1. Constant-sum For every S ∈ CS(I) we have � C∈S vs(C) = c. This means that the total payoff to be distributed among the grand coalition is always equal to a constant positive number c. 2. Nonlinearity with respect to a weight vector w ∈ R+ A partition function v is nonlinear (with respect to a weight vector w) if: for every partition S with maxC∈S w(C) > minC∈S w(C), we have vs(Ci) > w(Ci) · � C∈S vs(C) for the maximum coalition Ci ∈ arg(maxC∈S w(C)). In other words: for every partition with different weights for the coalitions, the coalition with the biggest share (highest weight) has a payoff bigger than all the payoffs of the coalitions times its weight. This means its profit is higher than its share in the network. Let’s consider a partition S = {C1, . . . , Cm} of the Miner Network Γ = ⟨M, S, P, D, d, λ⟩ and apply these conditions to it. The proportional distribution of the computational power will be our weight vector. We are now ready to prove the emptiness of the CS-core of S. Theorem 2.4.2 (Emptiness of CS-core). Let v be the partition function of a coalitional game with coalition structures (CS) of M. Let p be a weight vector satisfying ∀i ∈ I : pi < 1 2. If v is constant-sum (1) and nonlinear (2) for p, then the CS-core is empty for every coalition structure of M. Proof. Let v be a partition function as described in the theorem. Recall that the CS-core of S is: {x ∈ R|M| | xi ≥ 0, ∀C ⊂ I : x(C) ≥ vSC(C)}, with SC = {C} ∪ {{D \ C} | D ∈ S, {D \ C} ̸= {∅}}. The proof consists of taking a partition S of a coalition structure and then proving for every imputation x that there exists a C ⊂ I such that vSC(C) > x(C). Take S ∈ CS(M) and let x be an imputation associated with S. Without loss of generality we can assume that M = {1, . . . , n} and � A∈S vS(A) = 1, ∀S ∈ CS(M). The exact number of miners is not essential and for every partition the payoff function must be constant for c > 0, so we choose c = 1. 2 MINER COALITIONAL GAME 12 Now, let ϵi = xi − pi for every i and assume without loss of generality that ϵ1 ≤ ϵ2 ≤ · · · ≤ ϵn. Note that � i∈M ϵi = (x1 − p1) + · · · + (xn − pn) = x1 + x2 + · · · + xn − (p1 + p2 + · · · + pn) = � i∈M xi − � i∈M pi = 1 − 1 = 0. Let’s now set D = M \ {n}. This coalition will disrupt the core. Since ϵn is the greatest ϵ we know that ϵn ≥ 0. This means � i∈D ϵi = � i∈M ϵi − ϵn ≤ 0 and so x(D) ≤ p(D). Likewise, pn < 1 2 and therefore � i∈D pi > 1 2. Thus, our coalition D has the highest weight vector (D ∈ arg(maxC∈S w(C)) and because v is non-linear with respect to p: vSC(D) > p(D) · � C∈S vs(C) > p(D) · 1 = p(D) ≥ x(D). This means that for every imputation x we can always construct a coalition D such that vSC(D) > x(D). Therefore, the CS-core is empty. The condition of constant-sum is crucial, because this means we can assume � C∈S vSC(C) is constant. The condition of nonlinearity is necessary in order to prove vSC(C) > p(C), which will lead to the desired result: vSC(C) > x(C). What does the emptiness of this core mean? We considered a grand coalition of miners M, who were divided into multiple coalitions {C1, . . . , Cm}. The total amount of bitcoins which are to be distributed is constant (condition 1). Furthermore, the partition function v is nonlinear with respect to a weight vector (condition 2), namely the computational power of each miner (and no miner has an overbalance in computational power). The result is an empty CS-core of S, so there will always be a coalition which benefits from deviating from the current situation S. In short, there exist no distribution of the payoffs that will keep the miners in every coalition satisfied. 2.5 DMS-CS-core The emptiness of the CS-core is a strong notion. An imputation mustn’t be blocked by any possible coalition. Yet, there might be situations where certain subsets of agents can’t form a new coalition. We will constrain the number of possible partitions by only allowing the coalitions to split or merge. Therefore, we will introduce the concept of D-stability. We define D : CS(M) → 2M as the defection function. This function maps each partition to a set of possible coalitions. This means that a coalition C can only deviate from the current partition of S if C ∈ D(S). With this additional demand we might find an imputation that isn’t blocked by any coalition. There are two options for a coalition C: • a subset of C canmerge with a subset of another coalition {C′ ∪ D′ | C′ ⊂ C, D′ ⊂ D}; • C can split into two subsets C = C1 ∪ C2. An imputation x is DMS-stable if for every C ∈ D(S)MS we have x(C) ≥ vSC(C). The DMS-CS-core exists of all the DMS-stable imputations that are associated with S. Example 2.5.1. To illustrate that there are less constraints on an imputation x for the DMS-CS-core, consider a partition S = {{a}, {b}, {c}, {d, e}}. While checking if an imputation x is in a core of S, we must consider each possible alternative partition (SC) of S. The partition S2 = {{a}, {b}, {c, d}, {e}} is the result

See more

The list of books you might like

Upgrade Premium
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.
DMCA & Copyright: Dear all, most of the website is community built, users are uploading hundred of books everyday, which makes really hard for us to identify copyrighted material, please contact us if you want any material removed.
Copyright @ PDFdrive.to, 2022 | We love our users