Comprehensive Bitcoin Mining - Aarti Dabholkar

    AUTHOR :   Aarti Dabholkar  

Abstract

Bitcoin has emerged as the first widely-deployed decentralized global currency.The crux behind Bitcoin exchange is mining ,a computation intensive process that is used to verify Bitcoin transactions.This process is organized as a speed game between individuals or firms-the  miners with different computational powers to solve a mathematical problem,bring a proof of work, spread their solution and reach consensus among the Bitcoin  network nodes with it.This paper describes the fundamentals of Bitcoin system and  mining process.It also assess the method of mining the concerned opportunities and implications for the benefit of potential miners.It also presents Bitcoin-NG (Next Generation), a blockchain protocol.

Keywords

SHA-256,Bitcoin mining,Blockchain framework,POW mechanism

 Introduction

Bitcoin is an interesting form of currency that arose to address economic problems related to centralized currency. Bitcoin is a form of digital currency that was founded during the financial crisis in 2009. In September of 2008, Lehman Brothers filed for the largest bankruptcy in history. The collapse of this giant kicked off a global financial crisis. A few months later, Bitcoin was born.Bitcoin is a bank free Internet money.Unlike the Dollar, the Euro, the Yen, and other forms of Centralized Currency, Bitcoin is classified as a Decentralized currency that are controlled by a network of users who control and verify the monetary transactions.Nakamoto described Bitcoin as providing “a system for electronic transactions without relying on trust” between participants through the use of cryptographic proof.When an individual sends some bitocins to another individual,this information is broadcast to the peer-to-peer Bitcoin network. These transactions are recorded into an online public ledger called as Blockchain.Blockchain is a physical DNAof the cryptocurrency.Blockchain keeps a track of every single transaction recorded and all Bitcoin users can trust this decentralized, distributed ledger. Mining for bitcoins is actually the process of verifying other bitcoin transactions which users are rewarded for. This is the central mechanic behind the bitcoin economy, and mining is used to keep transactions secure and reliable.In this paper we observe that  for mining,custom hardware is required. When Bitcoin first started, it was possible to mine using only your desktop's CPU and GPU. While this is still possible, the returns make running this method impractical since more cost will be incurred on electricity than to earn mining coins.Instead, custom hardware allows for much better processing for about the same power draw. Section 1 describes how mining is performed. In Section 2,it is shown that Bitcoin mining is a race between computer users –the miners with different computational power to solve a mathematical problem and  analyze the parameters for which miners would face proper incentives to fulfill their function of transaction processors in current situation.It is the role of the miner to do this work of confirming and securing transactions through the insertion of blockchain. The probability of each miner to solve a mining problem depends upon his computational power.The complexity of mining is made proportional to the total computational power of all miners.More precisely the complexity is dynamically adjusted so that block solving and hence a creation of  bitcoins will occur every ten minutes.Once a block is inserted in the blockchain,the mathematical problem faced by all the miners are modified and we can consider that a fresh new speed game starts between miners.Hence the whole building of the blockchain can be considered as independent block insertions from the miners point of view.The Bitcoin network automatically changes the difficulty of math problem depending on how faster the miners solve them.   Section 3 of this research paper explains the Bitcoin-Next Generation(NG) crux area i.e Blockchain protocol.   Section 4 highlights Proof of Work(POW) mechanism.POW is basically the calculations that must be performed by the nodes present in the cryptocurrency network. Proof of Work is the requirement for a service user to prove that they have performed a costly action (usually a computational cost of performing mathematical operations) in order to deter network attacks such as spam and dedicated denial of service (DDoS).The POW mechanism is essential to Bitcoin network security.    

Study

 

1.Bitcoin Mining

  Overview  As aforementioned Bitcoin is decentralized ,and since there is no central government regulating it,then how to ensure that the transactions are accurate?How do we know that a person A has sent 1 bitcoin to person B?How do we stop person A from also sending that bitcoin to person C? .The answer is mining[1].To maintain the validity of transactions in the Bitcoin network,mining is performed. Mining Bitcoins requires significant computational resources.The Bitcoin network overall finds a block every 10 minutes.Clearly miners must invest in suitable computer hardware.First generation machines were CPUs in PCs but it was impossible for CPUs to mine Bitcoins speedily as the difficulty of Bitcoin intensified.The second generation machines were GPUs on display cards,but miners discovered  that these graphic cards though are faster,they consume more electricity and generate heat.The first commercial bitcoin mining product included chips that were re-programmed for mining bitcoins.These chips were faster but were still power hunger. ASIC (Application specific integrated circuit)  are designed specifically for bitcoin mining.ASIC technology has made bitcoin mining even faster and using less power and earn more profits[2] .Successful miners update equipment quickly,and those who do not invest continuously and extensively in current-generation hardware must exit the industry or face the likelihood of never mining a single block  out within their lifetimes.Without miners, new transactions cannot be added to the public ledger, and Bitcoin will not function. The mining process is summarized in Figure 1. Mining consists of searching for a cryptographic nonce value within a block such that the hash of the block falls within a certain range.The nonce is a 32 bit arbitrary random number that is typically used once.The network scales the range to maintain an average rate of one new block every ten minutes.       Figure 1.Mining process block diagram     As a result, miners naturally compete against each other to gain a higher fraction of the network's  hash rate in order to maximize reward. In a race to capture the network's rewards, miners have developed increasingly sophisticated solutions, culminating in the development of Bitcoin ASIC accelerators [3]. A miner's revenue is determined by the accelerator's hash rate (GHash=s); operating costs are determined by its energy efficiency (GHash=J).The mining algorithm is shown in Algorithm 1. In short,mining is searching of the nonce value that results in a double SHA-256 hash digest (Algorithm 2) value less than a given threshold. The nonce is a 32-bit field within a 1024-bit block header. In order to verify transactions at a steady rate, this threshold varies over time as a function of difficulty D(t). Difficulty is adjusted by the network regularly such that a solution is expected to be found approximately every 10 minutes, regardless of the network's collective hash rate. By their very nature, hash functions are designed to be non-invertible, so mining is performed by brute force, guessing nonce values and comparing the hash output. This task is perfectly parallel as multiple hashes may be computed at once. It follows that one's probability of finding a solution is proportional to one's hash rate. The first miner to find a valid nonce broadcasts the value on the network for verification and is rewarded with newly minted digital bitcoins.   Algorithm 1-Mining Process

1: nonceß0 2: while nonce < 23  do 3: threshold ß((216 - 1) << 208)/D(t) 4: digest ßSHA-256(SHA-256(header)) 5: if digest < threshold then 6: return nonce 7: else 8: nonce ß nonce + 1 9: end if 10: end while

          Algorithm 2 presents a basic description of SHA-256

• The message M is divided into N 512-bit blocks M⁽⁰⁾,M⁽¹⁾,…..,M^(N-1).Each of these blocks is further subdivided into 16 32-bit words M₀⁽ⁱ⁾,…..,M₁₅⁽ⁱ⁾.
• The intermediate hash value H⁽ⁱ⁾ is composed of 8 32-bit words H₀⁽ⁱ⁾,H₁⁽ⁱ⁾,….,H₇⁽ⁱ⁾
• Ch(x, y, z) = (x ^ y) ⊕ (­x ^ z)
• Maj(x,y, z) =(x ^ y) ⊕ (x ^ z) ⊕ (y ^ z).
• Σ₀(x)=x >> 2⊕x >> 13⊕x >> 22
• Σ₁(x)=x >> 6⊕x >> 11⊕x >>25

                                                           Algorithm 2:SHA-256    

• Baseline Hardware

 

• Implementation

For our studies, we selected as baseline the SHA-256 ASIC design outlined by Dadda et al. [3]. A summary of SHA-256 is provided in Algorithm 2. The hashing core in this design is implemented as two parallel pipelines, the Compressor (Line9 of Algorithm 2) and the Expander (Line 3 of Algorithm 2) shown in Figure 2. The logic functions Ch, Maj, Σ_0,Σ₁,σ₀ ,σ₁ in  the figure are defined with Algorithm 2.  

         Figure 2:  SHA-256 Pipeline Datapath

  A single iteration of the algorithm's compression and expansion loops are performed each clock cycle. The expandercircuit receives a new 32-bit message chunk Mj⁽ⁱ⁾ every j^th cycle and feeds the compressor the expanded message through register W_j. Conversely, the compressor receives a 32-bit chunk of the expanded message and 32-bit constant K_j  every j^th  cycle and compresses these sequences. After 64 cycles, the final 256-bit hash is given by A₀+A₁,  B, C, D, E, F, G, H. In order to reduce delay, most additions are performed by carry-save adder (CSA) trees to avoid unnecessary carry propagation. The ultimate carry propagation is performed only once by some form of carry-propagate adder (CPA) (e.g. ripple-carry adder (RCA) or carry-lookahead adder (CLA)).[4]    

2. The Bitcoin Mining Game

  Bitcoin is a network protocol that enables individuals to transfer property rights on account units called "bitcoins", created in limited quantity. When an individual sends some bitcoins to another individual, this information is broadcast to the peer-to-peer Bitcoin network. However, for technical purposes we won’t address here, this transaction needs to be included – together with other transactions forming a block – in the blockchain in order to be confirmed and secured. As a consequence, the blockchain is a public ledger that contains the whole history of all the transactions of bitcoins ever processed and all Bitcoin users can trust this decentralized, distributed ledger. This section tackles the question of the incentives faced by the miners as a function of the reward scheme and values. First, let us see the possible gains for a miner. As it is today, the fixed reward is 25 bitcoins (BTC) per block. The variable reward is typically 10^-4 BTC per transaction today but it can also be considered as the price on the market for space in blocks[5] Second, let us see the cost structure. When mining a block, a miner is free to choose which of the transactions in the network he wishes to include in the block he is trying to solve. In a very good first approximation, computing the mining mathematical problem with more transactions included in it is not more expensive in terms of CPU, disk or bandwidth use. However, it should be considered that the larger a block, the longer it takes for it to be spread in the Bitcoin network and reach consensus. Thus, including maximum transactions in a block can have the adverse effect of lowering the probability of a miner to earn any reward. When a block is mined but is outraced by another one, it becomes orphaned and all associated rewards are lost for its finder. Then, there exists a tradeoff problem that sets the number of transactions miners should include in their blocks. However, as the solution to this tradeoff depends on how many transactions other miners include in the block they are trying to mine. Then, the number of transactions included in blocks is the outcome of a game: the Bitcoin mining game that we propose to study in this section   2.1 Model   Let us consider a set N = {1,….,N} of miners in the Bitcoin network with N >=2[6]. Each miner i belongs to N has a relative computational power hi > 0. Miners play against each other in a race to find the solution of a mathematical problem. This mathematical problem is solved by a try and guess strategy and the occurrence of solving the problem can be modeled as a random variable following a Poisson process. As explained in the introduction, the complexity of finding a block is dynamically adjusted so that this operation takes T = 600(i.e 10 minutes) seconds in expectation. Then, the mining Poisson process has a fixed parameter T^-1 for the whole network of miners. The set of transactions included in a block to be solved is chosen by each miner. This set has no effect on the cost to solve it in a first approximation. However, once a miner has found a block with a given set of transactions in it, he needs to broadcast his solution to the Bitcoin network and his solution must reach consensus. The time needed for a block to reach consensus is dependent on its size and hence on the set of transactions in it. Let π(Q) be the time needed for a block with size Q to reach consensus. We will make the assumption that this time function is linear, π(Q) = z.Q with z > 0[7]. The first miner to find a block that reaches consensus earns (in bitcoins) a fixed reward, R ≥0, and a variable one, p.Q, with p≥0 the fee density.   2.1.1. Mining payoffs-   Let us first compute the mining benefit earned by miners. We assume that all miners start trying to find a new block at the same time, t = 0. Each miner i belongs to N tries to mine a block with size Qi ≥0.Obviously, using standard Poisson process results, the probability for i to find a block between t and t+dt and that this block will be the first to reach consensus is:   2.2 The current case   In this Section, we study the current behavior of the miners in the Bitcoin network. In fact, miners can be mining pools but, for the sake of simplicity[8] we will make no difference as we will consider that the best strategy for a miner is the same whether it is a pool or a single miner, benefits being redistributed among the participants of a mining pool, proportionally to the computational power they bring along to their pool. All the data we need for this study is public in the Bitcoin blockchain and protocol or relies on the simplifying assumption that, today, all miners include all the transactions present in the network when trying to find a block[9]. We will also work with a typical fee of 10^-4 BTC per 0.6kB transaction. Unless otherwise stated, the values for our computations are displayed in Table 1     Table 1: Data Values     Let us start our analysis of the current situation as displayed in Table 2. In reality, transactions can have different sizes and require different levels of fees to be computed. The size of a transaction depends on many parameters (number of inputs and outputs mainly) but not directly on the amount paid in the transaction. Throughout this section, we will make the simplifying assumption that all transactions have the same size. 884 is the average number of transactions in the blocks inserted in the blockchain between blocks 377,261 and 378,260. The average size of a transaction over the same period is 600 bytes. We will also consider that the Bitcoin network computational power is distributed as shown in Table 2 (column B).We inferred these relative computational powers of miners from an analysis of the blocks found. Indeed, we make, as already noted, the assumption that all miners include all the transactions in the network in their blocks Further, we make the assumption that the frequency of blocks found by a miner, that we can observe, is the best estimation of the probability that he solves a block and, hence, the best estimation of his relative computational power. We can now consider each miner and compute his best response to the other miners’ current strategy. This optimal number of 0.6kB transactions to include in the current computed block is 0 for all miners (column D). This shows that the current situation is not a Nash Equilibrium and all miners have a profitable deviation.Nash Equilibrium used in  game theory, is a solution concept of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy[10]. If unilaterally mining blocks with no transaction, a miner would increase his probability to earn the fixed 25 BTC reward (as displayed in column E) at the cost of the 884*10^-4 = 0:0884 BTC variable reward in case of successful mining. In the current case, this deviation would lead to a higher expected benefit (columns F,G).     Table 2   Equivalently, the lowest value of c for which the situation where all miners include no transaction in their blocks is not a Nash equilibrium is c =3.4*10^-4  BTC. This corresponds to an increase from the current value of the transaction fee of a factor approx. 3.5. At the time this article is written, 3.4*10^-4  BTC can be bought for about $0:15. With R = 25 BTC and c =10^-4   BTC, we can estimate the maximal value of z for which all miners mining empty blocks is not a Nash equilibrium of the Bitcoin mining game with the current computational powers. After simple calculation, this value is z =0.0049 s.kB^-1.   2.3  The Block Space Offer   In this section, we study the relationship between Rizun [11] and our study.Peter R.Rizun,Chief Scientist in his recent conference has stated that the upgrade to larger blocks must be decesive and absolute.The community does not want the blockchain to split. A split would threaten Bitcoin’s network effect, cause confusion in the media, and create unnecessary work for many Bitcoin businesses.   In particular, we look at the implications in terms of block space offer. Rizun finds the following expression for the block space offer on the market as a function of p,   (1)   In order to obtain this result, Rizun[8]  makes two implicit assumptions: a) there is an infinite number of symmetric atomistic miners, and b)miners consider that others mine empty blocks, which implies the orphaning probability (Rizun’s Equation 4[8]) as suggested by Andresen[9]. In order to be in the same framework, we will also make the assumption of an infinite number of symmetric atomistic miners.In this case we find:   (2)   In Figure 3, we display Q as a function of p as obtained in Equation 1 and 2 for parameter as given in Table 1.                     Figure 3:Q as a function of p as obtained in Equation 1(light grey) and 2(black) Since we consider the case with atomistic miners, the only reason why Equations 1 and 2 differ is the following. Rizun[10] considers that decisions are made by miners considering other miners try to mine empty blocks. On the contrary, we consider that, at the Nash equilibrium, miners consider the optimal decision made by other miners. Obviously, close to the point where miners actually mine empty blocks, both assumptions coincide. This is why we can see that Q as obtained in Equations 1 and 2 are strictly positive for the same values of p , i.e. when p> zR/T and are equal for small deviations of p above zR/T. Another important difference between Equations 1 and 2 is that when p tends to infinity, Equation 1 has no upper bound whereas Q tends to T/z  from below in Equation 2[12] .The reason  why Q has an upper bound in our model is as follows: as p increases, all miners are willing to include more transactions in their blocks in order to enjoy larger variable rewards. However, as other miners  include more transactions in their blocks, this makes the incentive to outrace them by decreasing the size of the block to be found more important. And hence, this limits the trend to always include more transactions. This negative feedback does not exist in Rizun[11] because the changes of behavior by other miners is not considered.

3. Bitcoin NG: A Scalable Blockchain Protocol

 This section describes Bitcoin-NG (Next Generation), a new blockchain protocol designed to scale. Bitcoin-NG is a Byzantine fault tolerant blockchain protocol that is robust to extreme churn and shares the same trust model as Bitcoin. The blockchain technology provides a decentralized, open, Byzantine fault-tolerant transaction mechanism, and promises to become the infrastructure for a new generation of Internet interaction, including anonymous online payments [13], remittance, and transaction of digital assets [14]. Ongoing work explores smart digital contracts, enabling anonymous parties to programmatically enforce complex agreements [15,16]. Despite its potential, blockchain protocols face a significant scalability barrier [17, 18, 19, 20]. The maximum rate at which these systems can process transactions is capped by the choice of two parameters: block size and block interval. Increasing block size improves throughput, but the resulting bigger blocks take longer to propagate in the network. Reducing the block interval reduces latency, but leads to instability where the system is in disagreement and the blockchain is subject to reorganization. Bitcoin currently targets a  conservative 10 minutes between blocks, yielding 10-minute expected latencies for transactions to be encoded in the blockchain. The block size is currently set at 1MB, yielding only 1 to 3.5 transactions per second for Bitcoin for typical transaction sizes. Proposals for increasing the block size are the topic of heated debate within the Bitcoin community[21]. In this section of the reserach paper ,present Bitcoin-NG, a scalable blockchain protocol, based on the same trust model as Bitcoin. Bitcoin-NG’s latency is limited only by the propagation delay of the network, and its bandwidth is limited only by the processing capacity of the individual nodes. Bitcoin-NG achieves this performance improvement by decoupling Bitcoin’s blockchain operation into two planes: leader election and transaction serialization. It divides time into epochs, where each epoch has a single leader. As in Bitcoin, leader election is performed randomly and infrequently. Once a leader is chosen, it is entitled to serialize transactions unilaterally until a new leader is chosen, marking the end of the former’s epoch. While this approach is a significant departure from Bitcoin’s operation, Bitcoin-NG maintains Bitcoin’s security properties. Implicitly, leader election is already taking place in Bitcoin. But in Bitcoin, the leader is in charge of serializing history, making the entire duration of time between leader elections a long system freeze.  In contrast, leader election in Bitcoin-NG is forward looking, and ensures that the system is able to continually process transactions. Evaluating the performance and functionality of new consensus protocols is a challenging task. To help perform this quantitatively and provide a foundation for the comparison of alternative consensus  protocols, we introduce several metrics to evaluate implementations of Nakamoto consensus. These metrics capture performance metrics such as protocol goodput and latency, as well as various aspects of its security, including its ability to maintain consensus and resist centralization. We evaluate the performance of Bitcoin-NG on a large emulation testbed consisting of 1000 nodes, amounting to over 15% of the current operational Bitcoin network [22]. This testbed enables us to run unchanged clients, using realistic Internet latencies. We compare Bitcoin-NG with the original Bitcoin client, and demonstrate the critical trade-offs inherent in the original Bitcoin protocol. Controlling for network bandwidth, reducing Bitcoin’s latency by decreasing the block interval and improving its throughput by increasing the block size both yield adverse effects. In particular, fairness suffers, giving large miners an advantage over small miners. This anomaly leads to centralization, where the mining power tends to be concentrated under a single controller, breaking the basic premise of the decentralized cryptocurrency vision. Additionally, mining power is lost, making the system more vulnerable to attacks. In contrast, Bitcoin- NG improves latency and throughput to the maximum allowed by network conditions and node processing limits, while avoiding the fairness and mining power utilization problems. 3.1 Bitcoin and its Blockchain Protocol  Bitcoin is a distributed, decentralized crypto-currency [23,24,25,26], which implicitly defined and implemented Nakamoto consensus. Bitcoin uses the blockchain protocol to serialize transactions of the Bitcoin currency among its users. The replicated state machine maintains the balances of the different users, and its transitions are transactions that move funds among them. This state machine is managed by the system nodes, called miners. Each user commands addresses, and sends Bitcoins by forming a transaction from her address to another’s address and sending it to the nodes. More explicitly, a transaction is from the output of a previous transaction to a specific address. An output is spent if it is the input of another transaction. A client owns x Bitcoins at time t if the aggregate of unspent outputs to its address is x. Transactions are protected with cryptographic techniques that ensure only the rightful owner of a Bitcoin address can transfer funds from it. Miners accept transactions only if their sources have not been spent, thereby preventing users from double-spending their funds. The miners commit the transactions into a global append only log called the blockchain. The blockchain records transactions in units of blocks. Each block includes a unique ID, and the ID of the preceding block. The first block, dubbed the genesis block, is defined as part of the protocol. A valid block contains (1) a solution to a cryptopuzzle involving the hash of the previous block, (2) the hash (specifically, the Merkle root) of the transactions in the current block, which have to be valid, and (3) a special transaction, called the coinbase, crediting the miner with the reward for solving the cryptopuzzle. This process is called Bitcoin mining, and, by slight abuse of terminology, we refer to the creation of blocks as block mining. The specific cryptopuzzle is a double-hash of the block header whose result has to be smaller than a set value. The problem difficulty, set by this value, is dynamically adjusted such that blocks are generated at an average rate of one every ten minutes.  Mining : When a miner creates a block, she is compensated for her efforts with Bitcoins. This compensation includes a per-transaction fee paid by the users whose transactions are included, as well as an amount of new Bitcoins that did not exist before.  Forks : Any miner may add a valid block to the chain by simply publishing it over an overlay network to all other miners. If multiple miners create blocks with the same preceding block, the chain is forked into branches, forming a tree. Other miners may subsequently add new valid blocks to any of these branches. When a miner tries to add a new block after an existing block, we say it mines on the existing block. If this block is a leaf of a branch, we say he mines on the branch. To resolve forks, the protocol prescribes on which chain the miners should mine. The criterion is that the winning chain is the heaviest one, that is, the one that required (in expectancy) the most mining power to generate. All miners add blocks to the heaviest chain of which they know, with random tie-breaking. We note that choosing a longest branch at random is suggested by Eyal and Sirer [27]. The operational client currently chooses the first branch it has heard of, making it more vulnerable in the general case. The heaviest chain a node knows is the serialization of RSM inputs it knows, and hence describes the RSM’s state. The formation of forks is undesirable, as they indicate that there is no globally agreed  RSM state. Branches and blocks outside the main chain are called pruned (and not orphans, as is common in informal discussions, since they have a parent in the block tree). Transactions in pruned blocks are ignored. They can be placed in the main chain at any later time, unless a contradicting transaction (that spends the same outputs) was placed there in the meantime. Block dissemination over the Bitcoin overlay network takes seconds, whereas the average mining interval is ten minutes. Therefore, accidental bifurcation occurs on average about once every 60 blocks [28]. 3.2 Bitcoin –NG  Bitcoin-NG is a blockchain protocol that serializes transactions, much like Bitcoin, but allows for better latency and bandwidth without sacrificing other properties. The protocol divides time into epochs. In each epoch, a single leader is in charge of serializing state machine transitions. To facilitate state propagation, leaders generate blocks. The protocol introduces two types of blocks: key blocks for leader election and microblocks that contain the ledger entries. Each block has a header that contains, among other fields, the unique reference of its predecessor; namely, a cryptographic hash of the predecessor header. 3.3 Key Blocks and Leader Election Key blocks are used to choose a leader. Like a Bitcoin block, a key block contains the reference to the previous block (either a key block or a microblock, usually the latter), the current Unix time, a coinbase transaction to pay out the reward, a target value, and a nonce field containing arbitrary bits. As in Bitcoin, for a key block  to be valid, the cryptographic hash of its header must be smaller than the target value. Unlike Bitcoin, a key block contains a public key that will be used in subsequent microblocks. As in Bitcoin, for a miner to generate a key block, it must iterate through nonce values until the crypto-puzzle condition is met. Consequently, the interval between consecutive key blocks is exponentially distributed. To maintain a set average rate, the difficulty is adjusted by deterministically changing the target value based on the Unix time in the key block headers. In case of a fork, just as in Bitcoin, the nodes pick the branch with the most work, aggregated over all key blocks, with random tie breaking.

       Figure 4:Structure of the Bitcoin-NG chain.

In the above figure Microblocks (circles) are signed with the private key matching the public key in the last key block (squares). Fee is distributed 40% to the leader and 60% to the next one. 3.4 Microblocks  Once a node generates a key block it becomes the leader. As a leader, the node is allowed to generate microblocks at a set rate smaller than a predefined maximum. The maximum rate is deterministic, and can be much higher than the average interval between key blocks. The size of microblocks is bounded by a predefined maximum. Specifically, if the timestamp of a microblock is in the future, or if its difference with its predecessor’s timestamp is smaller than the minimum, then the microblock is invalid. This bound prohibits a leader (malicious, greedy, or broken) from swamping the system with microblocks. A microblock contains ledger entries and a header. The header contains the reference to the previous block, the current Unix time, a cryptographic hash of its ledger entries, and a cryptographic signature of the header. The signature uses the private key that matches the public key in the latest key block in the chain. For a microblock to be valid, all its entries must be valid according to the specification of the state machine, and the signature has to be valid. Figure 4 illustrates the structure. Note that microblocks do not affect the weight of the chain, as they do not contain proofs of work. This is critical for keeping the incentives aligned, as explained in Section 5.   When a miner generates a key block, he may not have heard of all microblocks generated by the previous leader. If microblock generation is frequent, this can be the common case on leader switching. The result is a short microblock fork, as illustrated in Figure 5. Such a fork is observed by any node that receives the to-be-pruned microblock (blocks A3 and A4 in the figure) before the new key block (block B in the figure). It is resolved once the key block propagates to that node. Therefore, a user that sees a microblock should wait for the propagation time of the network before considering it in the chain, to make sure it is not pruned by a new key block.           Figure 5: When microblocks are frequent, short forks occur on almost every leader switch.  3.5  Renumeration  To motivate mining, a leader is compensated for her efforts by the protocol. Remuneration is comprised of two parts. First, each key block entitles its generator a set amount. Second, each ledger entry carries a fee. This fee is split by the leader that places this entry in a microblock, and the subsequent leader that generates the next key block. Specifically, the current leader earns 40%  of the fee, and the subsequent leader earns 60% of the fee, as illustrated in Figure 1. The choice of this distribution is explained in Section 3.7. In practice, the remuneration is implemented by having each key block contain a single coinbase transaction that mints new coins and deposits the funds to the current and previous leaders. As in Bitcoin, this transaction can only be spent after a maturity period of 100 key blocks, to avoid non-mergeable transactions following a fork.  3.6  Micoblock Fork Prevention  Since microblocks do not require mining, they can be generated cheaply and quickly by the leader, allowing it to split the brain of the system, publishing different replicated-state-machine states to different machines. This allows for double spending attacks, where different nodes believe the same coins were spent with different transactions. To demotivate such behavior, we use a dedicated ledger entry that invalidates the revenue of fraudulent leaders. Past work has used such entries in different contexts [29,30,31]. In Bitcoin-NG, the entry is called a poison transaction, and it contains the header of the first block in the pruned branch as a proof of fraud. The poison transaction has to be placed on the blockchain within the maturity window of the misbehaving leader’s key block, and before the revenue is spent by the malicious leader. Besides invalidating the compensation sent to the leader that generated the fork, a poison transaction grants the current leader a fraction of that compensation, e.g., 5%. The choice of this value is explained in Section 3.7. Only one poison transaction can be placed per cheater, even if the cheater creates many forks. The cheater’s revenue that is not relayed to the poisoner is lost.  

 Security Analysis

4.1. Proof of Work Mechanism for Bitcoin   ss what they see as the wasteful nature of PoW.   4.2  How does the proof-of-work system help secure Bitcoin? Bitcoin uses the Hashcash proof of work with a minor adaption. To give a general idea of the mining process, imagine this setup:

The work performed by a miner consists of repeatedly increasing "nonce" until the hash function yields a value, that has the rare property of being below a certain target threshold. (In other words: The hash "starts with a certain number of zeroes", if you display it in the fixed-length representation, that is typically used.) FOR EXAMPLE: Let's say the base string that we are going to do work on is "Hello, world!". Our target is to find a variation of it that SHA-256 hashes to a value beginning with '000'. We vary the string by adding an integer value to the end called a nonce and incrementing it each time. Finding a match for "Hello, world!" takes us 4251 tries (but happens to have zeroes in the first four digits): 4251 hashes on a modern computer is not very much work (most computers can achieve at least 4 million hashes per second). Bitcoin automatically varies the difficulty (and thus the amount of work required to generate a block) to keep a roughly constant rate of block generation. As can be seen, the mining process doesn't compute anything special. It merely tries to find a number (also referred to as nonce) which - in combination with the payload - results in a hash with special properties. The advantage of using such a mechanism consists of the fact, that it is very easy to check a result: Given the payload and a specific nonce, only a single call of the hashing function is needed to verify that the hash has the required properties. Since there is no known way to find these hashes other than brute force, this can be used as a "proof of work" that someone invested a lot of computing power to find the correct nonce for this payload. This feature is then used in the Bitcoin network to allow the network to come to a consensus on the history of transactions. An attacker that wants to rewrite history will need to do the required proof of work before it will be accepted. And as long as honest miners have more computing power, they can always outpace an attacker[44].

Analysis

 From this research paper we analyse that why SHA-256 is being used for bitcoin mining. SHA-2, like all Merkle-Damgard hashes suffers from a property called "length-extension". This allows an attacker who knows H(x) to calculate H(x||y) without knowing x. This is usually not a problem, but there are some uses where it totally breaks the security. The most relevant example is using H(k||m) as MAC, where an attacker can easily calculate a MAC for m||m'. Though Bitcoin ever uses hashes in a way that would suffer from length extensions, but  Satoshi went with the safe choice of preventing it everywhere.To avoid this property, Ferguson and Schneier suggested using SHA256d = SHA256(SHA256(x)) which avoids length-extension attacks. This construction has some minor weaknesses (not relevant to bitcoin)[45]. Secondly we study that how Poisson Process is relevant in Blockchain technology.Poisson distribution deals with continous random experiments. The time between blocks in the Bitcoin blockchain is Poisson distributed with an expected value of 10 minutes between blocks. The crux of how blockchain works is the hash puzzle, a massive race that bitcoin miners all over the world are striving to solve every second. The mechanics of the puzzle are fairly simple. Every miner has a block containing a list of transactions that should be published. The miner’s goal is to find a value called a nonce, such that the hash of {nonce + block} is less than a target value. The current target is 440 billion, which may seem like a lot, but keep in mind that miners are using the SHA-256 hash, which outputs 256 bits. And because SHA-256 is a specially constructed cryptographic hash function, miners can’t do better than guesswork when it comes to finding a nonce that wins the hash puzzle. So every nonce has a 440 billion / 2^256 chance of winning the hash puzzle—meaning a Bernoulli trial. Since millions of these Bernoulli trials are happening every second, across the global compute power of miners, we end up with a Poisson distribution where a miner wins the hash puzzle (and can then publish a block) every 10 minutes, on average. Since the global compute power of miners changes, so does the target value in the hash puzzle. Thus, the expected time between blocks remains 10 minutes, even as global mining power changes over time[46].  

Conclusion

  In this research paper I have introduced and studied the Bitcoin Mining process.Miners when deciding on including a transaction into blocks,they must consider the  tradeoff between, on the one side, including more transactions and earning  more transaction fees if they find the current block first and, on the other side, including less transactions in order to decrease the time that is taken to spread their block solution  across the network and reach consensus with it, thus  increasing  their probability to include their block in the blockchain first and earn more rewards.  

Future Enhancements

  We can see three limitations to our study. The first one is about the sensitivity of our results to the parameters’ values. Our result stating that, at the Nash equilibrium, miners should not include transactions in their blocks is strongly dependent on, for instance, the marginal time needed to reach consensus. We took the best estimate for this parameter, 0:017s:kB?1 but it may be the case that it is smaller in reality and hence, the current case be a Nash Equilibrium. Another assumption of ours is that transactions are all the same in size. In reality, it is not the case and considering this could change some results in a more detailed version of our model. The second limitation of our study is about the security of the Bitcoin protocol. For Bitcoin to be used as an efficient payment system, it is a minimal necessary requirement that transactions be processed. However, this is not sufficient. Indeed, Bitcoin is vulnerable to what are called 51% attacks.22, 24, 26 Such attacks can occur when a miner can solve too many blocks in a row in expectation. It is usually said that this is the case when a miner owns strictly more than 50% of the computational power.18 In order to make such an attack costly, the total computational power of the Bitcoin network should be as large as possible. Since we did not consider the computational power as an endogenous variable, what matters in our study when an agent makes his decision regarding the number of transactions to be included in his block is the ratio between the fixed and the variable rewards (R=r). However, the miners’ benefits that will drive the computational power purchase and hence eventually decide on the security of Bitcoin will depend on R and r in absolute values. This aspect has already been studied, though in a different context.25 The second limitation is about the value of the Bitcoin network. Miners are rewarded in bitcoins. Hence, they have a vested interest in it to function well. Miners know that not processing transactions in their blocks means that Bitcoin loses some if not all of its value. Hence, any reward they may earn from their mining activity has no value either in this case. This suggests that the Bitcoin mining game should include a supplementary public good game on top of it. Other reasons could explain why, even though it may theoretically not be an equilibrium to include transactions in blocks today, miners still do so. The power of default, ideology, fear to appear as a free-rider in the eyes of the Bitcoin community or non-awareness of the theoretical predictions could be such reasons[47].  

References

 

1. .Bitcoin Mining(http://www.huffingtonpost.com/)
2. What is Bitcoin mining (www.youtube .com)
3. Dadda, M. Macchetti, and J. Owen. The design of a high speed ASIC unit for the hash function SHA-256 (384, 512). In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition Designers' Forum (DATE), February 2004.
4. Approximate Bitcoin Miming research paper from IEEE explore digital library.
5. The transaction fee is usually proposed by the user’s wallet. It is in fact a function of many parameters we will not consider here for the sake of simplicity. It also is related to the minimum relay fee needed for a transaction to be relayed in the network. We only consider the typical case of a low-priority transaction with size smaller than 1 kilobyte. This proposition is not mandatory, it is depending on the software used to send bitcoins and is not coded as a part of the Bitcoin protocol. See https://bitcoin.org/en/developer-guide# transaction-fees-and-change for more information.
6. https://medium.com/@peter_r/on-the-emerging-consensus-regarding-bitcoins-block-size-limit-insights-from-my-visit-with-2348878a16d8
7. This linear approximation is acceptable for the numerical simulations we run in Section 4.31, 32 Also, it would certainly be more appropriate to add a constant term in the t function definition, see Decker and Wattenhofer.We will only use the t function in differences so that this constant term would have no effect on our results.
8. See prior studies about mining pools and the qualitative differences between them and solo miners from The Bitcoin Mining Game Research paper taken from Papers 3 application.
9. The data we use from the blockchain come from the 1,000 blocks between blocks 377,261 (mined on Oct. 3, 2015 1:49 PM) and block 378,260 (mined on Oct. 10, 2015 1:27 PM). Data about the protocol can be found in the Bitcoin open-source code; see Nakamoto(Nakamoto, S. “Bitcoin: a peer-to-peer electronic cash system,” (2009).).
10. What is Nash Equilibrium(https://en.wikipedia.org/wiki/Nash_equilibrium)
11. Rizun, P.R. “A transaction fee market exists without a block size limit,” (2015).(https://dl.dropboxusercontent.com/u/43331625/feemarket.pdf).
12. This 30 MB block size bound has been emphasized by Stone and corresponds to the size of the block that would require T = 600 seconds to reach consensus.

Stone, A. “An examination of single transaction blocks and their effect on network throughput and block size,” (2015) http://www.bitcoinunlimited.info/1txn/.  

13. CNNMONEY STAFF. The Ashley Madison hack...in 2 minutes.

http://money.cnn.com/2015/08/24/technology/ashley-madison-hack-in-2-minutes/, retrieved Sep. 2015.

14. COLORED COINS PROJECT. Colored Coins. http://coloredcoins.org/, retrieved Sep. 2015.
15. KOSBA, A., MILLER, A., SHI, E., WEN, Z., AND PAPAMANTHOU, C. Hawk: The blockchain model of cryptography and privacy-preserving smart contracts. Cryptology ePrint Archive, Report 2015/675, 2015. http://eprint.iacr.org/.
16. THE ETHEREUM COMMUNITY. Ethereum white paper. https: //github.com/ethereum/wiki/wiki/White-Paper, retrieved July. 2015.

 

17. SOMPOLINSKY, Y., AND ZOHAR, A. Accelerating Bitcoin’s transaction processing. fast money grows on trees, not chains  In  Financial Cryptography (Puerto Rico, 2015).
18. LEWENBERG, Y., SOMPOLINSKY, Y., AND ZOHAR, A. Inclusive block chain protocols. In Financial Cryptography (Puerto Rico, 2015).
19. DECKER, C., AND WATTENHOFER, R. A fast and scalable payment network with Bitcoin Duplex Micropayment Channels. In Stabilization, Safety, and Security of Distributed Systems - 17^th International Symposium, SSS 2015, Edmonton, AB, Canada, August 18-21, 2015, Proceeding (2015), Springer, pp. 3–18.
20. BAMERT, T., DECKER, C., ELSEN, L., WATTENHOFER, R.,AND WELTEN, S. Have a snack, pay with Bitcoins. In Peerto- Peer Computing (P2P), 2013 IEEE Thirteenth International Conference on (2013), IEEE, pp. 1–5.
21. PECK, M. E. Adam Back says the Bitcoin fork is a coup.http://spectrum.ieee.org/tech-talk/computing/ networks/the-bitcoin-for-is-a-coup, Aug 2015.
22. MILLER, A., LITTON, J., PACHULSKI, A., GUPTA, N., LEVIN, D., SPRING, N., AND BHATTACHARJEE, B. Preprint: Discovering Bitcoins public topology and influential nodes. http://cs.umd.edu/projects/coinscope/coinscope.pdf, 2015.
23. BITCOIN COMMUNITY. Bitcoin source. https://github.com/bitcoin/bitcoin, retrieved Mar. 2015.
24. BITCOIN COMMUNITY. Protocol rules. https://en.bitcoin.it/wiki/Protocol_rules, retrieved Sep. 2013.
25. BITCOIN COMMUNITY. Protocol specification. https://en.bitcoin.it/wiki/Protocol_specification, retrieved Sep. 2013.
26. NAKAMOTO, S. Bitcoin: A peer-to-peer electronic cash system. http://www.bitcoin.org/bitcoin.pdf, 2008.
27. EYAL, I., AND SIRER, E. G. Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security (2014).
28. DECKER, C., AND WATTENHOFER, R. Information propagation in the Bitcoin network. In IEEE P2P (Trento, Italy, 2013).
29. EYAL, I., BIRMAN, K., AND VAN RENESSE, R. Cache serializability: Reducing inconsistency in edge transactions. In 35^th IEEE International Conference on Distributed Computing Systems (2015), pp. 686–695.
30. BACK, A., CORALLO, M., DASHJR, L., FRIEDENBACH, M., MAXWELL, G., MILLER, A., POELSTRA, A., TIMN, J., AND WUILLE, P. Enabling blockchain innovations with pegged sidechains. http://cs.umd.edu/projects/coinscope/pdf, 2014.
31. BUTERIN, V. Slasher: A punitive proof-of-stake algorithm. https://blog.ethereum.org/2014/01/15/ slasher-a-punitive-proof-of-stake-algorithm/, January 2015.
32. http://cryptorials.io/glossary/proof-of-work/
33. https://en.bitcoin.it/wiki/Help:FAQ#How_does_the_proof-of-work_system_help_secure_Bitcoin.3F.
34. https://bitcoin.stackexchange.com/questions/9202/why-does-bitcoin-use-two-hash-functions-sha-256-and-ripemd-160-to-create-an-ad.
35. https://www.quora.com/Why-is-the-Poisson-distribution-relevant-to-Bitcoin-blockchain.
36. The Bitcoin Mining Game research paper by Nicolas Houy downloaded from the Papers 3 application.