Bitcoin Generated Algorithm
This paper is a study on Bitcoin Generated Algorithm. There are many many bitcoin generated algorithm are available.In this paper we have study on bitcoin with proof of work and SHA-256 algorithm.How bitcoin will be work with its advantages and disadvantages.An overview of Proof–Of-Work and SHA-256 algorithm.
Bitcoin was created by Satoshi Nakamoto, who published the invention and later it was implemented as open source code. A merely endto-end version of electronic cash would allow online payments to be sent straight from one person to another without going through an economic body. Bitcoin is a network practice that enables folks to transfer assets rights on account units called “bitcoins”, created in limited quantity. When a person sends a few bitcoins to another individual, this information is broadcast to the peer-to-peer Bitcoin network.
A proof of work is a piece of data which is difficult (costly, time-consuming) to produce but easy for others to verify and which satisfies certain requirements. Producing a proof of work can be a random process with low probability so that a lot of trial and error is required on average before a valid proof of work is generated. Bitcoin uses the Hashcash proof of work system.
3.What Is Bitcoin?
Bitcoin is a crypto-currency, a form of electronic money. It is a decentralized digital currency without a single central bank or an administrator that can be sent from user to user in the peer to peer bitcoin network without the need for intermediaries.
One of the most interesting aspects of Bitcoin is that it does not require a central authority to verify transactions. All transactions are recorded in a public accounting called a blockchain. New transactions are transmitted to all nodes in the network and each node collects new transactions in a block. Once a block reaches a certain size (which is equal to the number of transactions made in about 10 minutes), all nodes in the network must agree on the same block. Once agreed, the block is terminated and new transactions are saved in a new block.
4.HOW DOES BITCOIN WORK?
The first thing you need to think about with a virtual currency is the transaction - the actual exchange of value from one person to another. While this may sound simple, in many ways it can be easy to forge a transaction to try to cheat the system. With physical currency, transactions are controlled by banking institutions which verify that they’re not forged and are unique.
Figure:Bitcoin Transaction Life Cycle
4.2. A Serial Number
To avoid people trying to forge transactions or reuse them with virtual currency, you need a way to tie a unique serial number to each person and each transaction as well. Bitcoin does this by using a private and public encrypted key. These hashes are used to make sure transactions aren’t duplicated in the network and there’s no way to cheat the system.
4.3. Goodbye Banks
Currently, banks are in place to facilitate a financial transaction between two people. When Bitcoin was being set-up, it was realized that banks could be taken out of the picture entirely if a peer-to-peer network was created to verify the transactions between two entities. This decentralization of financial transactions is one of the biggest reasons so many smart people are getting excited about Bitcoin.
4.4. Bitcoin Mining
-; Another piece is needed to make Bitcoin work. If it’s too easy for transactions to be validated, people could program bots to flood the network with verifications, making it difficult to actually verify the transaction. To combat
this, the idea is to make it computationally difficult to verify the transaction. This helps fight against the bad guys while at the same time offering a way to reward people who give up computing power to verify the transaction. The computational puzzle has to be difficult enough to make it impossible to hack while easy enough to still allow people to solve in a reasonable amount of time.
5.Bitcoin vs. Convenstional currencies
5.1.Bitcoin is Decentralized
Unlike traditional currency, which is controlled by a central authority - usually an arm of the government - Bitcoin is decentralized. Because it operates as a peer-to-peer network, all transactions and verification of transactions are done by various people in the network.
Figure: Bitcoin is Decentralized
5.2. Bitcoin is Virtual Currency
The other thing that sets Bitcoin apart from traditional currency is the fact that it’s virtual. That is to say coins and paper money aren’t produced to represent the value. Instead, all bitcoins exist in virtual space. This means you can’t go to an ATMand withdraw physical money. Some people have created unofficial physical representations of bitcoins, but first and foremost, Bitcoin is virtual.
5.3. Bitcoin has Scarcity
Because only 21 million bitcoins will be created, BTC has scarcity, unlike traditional currenc that can be printed when governments decide to print more. To spread out the creation of bitcoins being released into the world, the number that are created by “mining” will half every four years. This means that people will still be able to create them until the year 2140. At that time, no new bitcoins will be created and the existing stockpile will enjoy the benefits of scarcity - i.e. becoming more valuable.
5.5. Bitcoin transactions cannot be reversed
In order to preserve the block chain of all transactions in sequential order, Bitcoin transactions are not reversible. Additionally, a Bitcoin transaction can take ten minutes or more to confirm. This is different than other currencies that typically process transactions in seconds and also allow for reversing a charge to a credit or debit card.
5.6. Bitcoin is not Ubiquitous
Wherever you go in the world, you’re going to run into local currencies. In most places, you’ll be able to trade your country’s money for bills of the country you’re visiting. And no matter where you go in the world, you’re going to be able to trade your money for goods and services. Bitcoin hasn’t yet been embraced by the world at large. This may change in years to come as more businesses begin to accept Bitcoin for payment, but for now it’s a difference that matters to a lot of people.
6.Bitcoin Strengths and Weaknesses
While Bitcoin has a lot of strengths, there are some weaknesses for the cryptocurrency as well. We’re going to take a look at both the pros and cons of Bitcoin so that you can get a better understanding of where this virtual currency is going to head in the years ahead.
The fact that it’s already growing in popularity so rapidly is a good sign, but
there are hurdles that Bitcoin is going to have to get over if it’s to survive and thrive in the future.
First, let’s go over some of the main strengths of cryptocurrency in general and Bitcoin specifically.
6.1.1.Anonymity and Privacy
One of the big strengths of Bitcoin currently is that it offers virtual anonymity and a lot more privacy than is found in current financial systems. Bitcoin uses hash addresses to send and receive money, and these hashes or addresses can changed from transaction to transaction. Because of that, it’s entirely possible for two parties to be completely anonymous when conducting their transactions.
Because addresses (hashes) can be created for each transaction, it makes it really difficult to track and trace financial activity of any single person in the network. And, unlike cash which is also private to an extent, you can use Bitcoin online to do virtual transactions. Add to that the fact that there’s no central authority keeping tabs on all transactions, people can feel safer about their privacy.
6.1.2.No transaction fees
When you use a credit or debit card, the processor charges a transaction fee. The charge is given to the merchant which can cut down on their profit margin considerably. However,Bitcoin doesn’t have transaction fees - at this time. When 21 million bitcoins are produced and released into the world this may change, but for now Bitcoin doesn’t charge a transaction fee.
When Bitcoin mining goes away, there’s going to be no financial incentive for people to verify transactions by solving a block and adding it to the block chain. At that time, there’s a good chance that a low BTC transaction fee may be instituted in order to make sure others still verify transactions. Giving them a cut of the transaction fee will enable the system to continue.
6.1.3.No central governing authority
When you purchase something around the world, you’re typically taxed by the government for the transaction. Currently, Bitcoin is not recognized as money by any government so it is not taxed. Most Bitcoin transactions could be thought of as trades - which are generally exempt from taxation by governments.
This is likely to change if and when Bitcoin begins to be recognized as legitimate currency around the world. This is actually an incentive for governments to legally recognize Bitcoin as proper money. No one is sure when or if this will happen, but it’s something to think about as Bitcoin continues to experience a lot of growth around the world.
Next, let’s take a look at some of the weaknesses of Bitcoin. There’s a good chance a lot of these problems are going to be solved going forward, but for now they’re weaknesses.
While this hasn’t happened a lot - yet - there are many signs pointing to governments around the world interfering with the growth of Bitcoin. Whether it’s stopping bitcoins from being transferred to bank accounts or something else, one of the biggest weaknesses of Bitcoin currently is the chance of even more government interference as the virtual currency becomes more popular around the world. This is also a good thing on some levels, however.For example, no one wants money laundering or other illegal activities to be condoned or made possible due to Bitcoin. So, in some ways, the fact that governments are starting to getinvolved is a good thing that will help Bitcoin grow even more in the years ahead.
6.2.2.No Monetary Sovereignty
Another weakness of Bitcoin is that it has no monetary sovereignty. Basically, this means that Bitcoin is not yet accepted as “real money” around the world. Bitcoin is not backed by any government currently. Some may consider this a strength, but it also poses some problems for people (especially corporations) that want to make money with Bitcoin.
Bitcoin is, at its core, another fiat currency that isn’t backed by precious metals or other items of value. The exact value of a single BTC is that which is given to it by people. This makes Bitcoin extremely vulnerable to destabilization. For example, if a large number of people who have bitcoins suddenly decide to sell, this may cause a panic that devalues bitcoins considerably.
6.2.3.Deflationary by design
If Bitcoin deflation happens too quickly, investors are not going to want to invest large amounts of BTC because their efforts won’t be rewarded as BTC becomes more valuable during the time it takes them to create a product and take it to market.
There’s also the real possibility of a recession if a large number of people who purchase BT for investment reasons hold onto their bitcoins. If they can control large amounts of the 21 million bitcoins that will be in circulation, there’s a good chance that others won’t be able to conduct transactions because they don’t have enough bitcoins in their possession. At this point, a recession or even a depression become a real possibility. 6.2.4.Accidental Loss and Theft
Another problem is the loss or theft of bitcoins. Because Bitcoin has no protection mechanism built into the currency, it’s possible for someone to lose their wallet file. If this happens, the bitcoins they had in the wallet will be taken out of the system - theoretically forever. This could help spur the problems with deflation mentioned above.
Additionally, if someone manages to steal bitcoins from another person, there’s no way to rollback the transaction, even if there’s proof that a theft occurred. The Bitcoin system is built so that once a transaction happens it’s there permanently. If not, it would destroy the integrity of the block chain. With most current financial transactions - like with a credit card - you can contest a transaction and get your money back. This isn’t possible - currently - with Bitcoin.It’s definitely something that needs to be considered moving forward.
6.2.5.Black market appeal
Because of the decentralization of Bitcoin as well as the anonymity that it can provide, there’s a good chance that many are going to try to abuse the system for financial gain. Because of the way it’s set up, there’s no way to deny any person or corporation from participating in the Bitcoin network. And this may make it favorable for black markets - like Silk Road - to use Bitcoin as a means to commit crimes online without being caught
6.2.6.It is complicated to use
While the Bitcoin software is relatively easy to use, it’s not as easy as whipping out your credit card and making a transaction. Because it’s somewhat complicated to use, there’s a chance that a lot of the world’s population may not use it, which will affect whether Bitcoin continues to grow or not.
This is changing gradually as Bitcoin software becomes easier to use, but a lot more work needs to be done before Bitcoin really takes off. Luckily, there’s a lot of financial gain to be had by those who can come up with easier ways to use Bitcoin. This means there’s going to be a lot of people working on the problem of Bitcoin being difficult for some people to understand and use.
6.2.7.It is a poor use of computing power
Last but not least, you have to consider that Bitcoin mining takes quite a bit of processing power.This computational power could be used for other more productive reasons. Some say that the Bitcoin network is already the world’s largest peer-to-peer network - at least when it comes to processing and number crunching. This may not seem like a big thing, but you have to consider all the electricity that’s needed to keep all the computers on the network going.
A proof of work is a piece of data which is difficult (costly, time-consuming) to produce but easy for others to verify and which satisfies certain requirements. Producing a proof of work can be a random process with low probability so that a lot of trial and error is required on average before a valid proof of work is generated. Bitcoin uses the Hashcash proof of work system.
A Proof-of-Work (PoW) system (or protocol, or function) is an economic measure to deter denial of services attacks and other service abuses such as spam on a network by requiring some work from the service requester, usually meaning processing time by a computer. The concept was invented by Cynthia Dwork and Moni Naor as presented in a 1993 journal article.The term “Proof of Work” or PoW was first coined and formalized in a 1999 paper by Markus Jakobsson and Ari Juels. An early example of the proof-of-work system used to give value to a currency is the shell money of the Solomon Islands.
A key feature of these schemes is their asymmetry: the work must be moderately hard (but feasible) on the requester side but easy to check for the service provider. This idea is also known as a CPU cost function, client puzzle, computational puzzle or CPU pricing function. It is distinct from a CAPTCHA, which is intended for a human to solve quickly, rather than a computer. Proof of space(PoSpace) proposals apply the same principle by proving a dedicated amount of memory or disk space instead of CPU time. Proof-of-Stake, Proof of bandwidth, and other approaches have been discussed in the context of cryptocurrency. Proof of ownership aims at proving that specific data are held by the prover.
One application of this idea is using Hashcash as a method to preventing email spam, requiring a proof of work on the email’s contents (including the To address), on every email. Legitimate emails will be able to do the work to generate the proof easily (not much work is required for a single email), but mass spam emailers will have difficulty generating the required proofs (which would require huge computational resources).
Hashcash proofs of work are used in Bitcoin for block generation. In order for a block to be accepted by network participants, miner must complete a proof of work which covers all of the data in the block. The difficulty of this work is adjusted so as to limit the rate at which new blocks can be generated by the network to one every 10 minutes. Due to the very low probability of successful generation, this makes it unpredictable which worker computer in the network will be able to generate the next block.
For a block to be valid it must hash to a value less than the current target this means that each block indicates that work has been done generating it. Each block contains the hash of the preceding block, thus each block has a chain of blocks that together contain a large amount of work. Changing a block (which can only be done by making a new block containing the same predecessor) requires regenerating all successors and redoing the work they contain. This protects the block chain from tampering.
A proof of work is a cryptographic puzzle used to ensure that a party has performed a certain amount of work. In particular, the Bitcoin mining process incorporates a proof of work system based on Adam Back’s Hashcash 3. It has two basic properties – ?rstly, it ensures that the party providing the proof of work has invested a prede?ned amount of e?ort in order to create the proof and secondly, that the proof is e?ciently veri?able. Typically, ?nding a solution to a proof of work puzzle is a probabilistic process with a success probability depending on the prede?ned di?culty.
Figure:Proof Of Work
The proof of work system, the basis of the most popular and dominant cryptocurrencies like bitcoin, is a mining and computer power-based system in which participating users are required to solve difficult mathematical problems to validate and authenticate transactions.
Large cryptographic networks like bitcoin integrated the Proof-of-work algorithm as its foundation because it provides complete decentralisation of power and control over the distribution and implementation of major technical and economic changes in the network.
To attack bitcoin, the proof of system requires the hacker to own at least 51% of the network’s hashrate or computing power, which is virtually impossible considering the size of the bitcoin network and its considerably high hashrate.
However, small proof of work-based networks are easier to hack because attackers can gain 51% of their computing power at a much lower cost.
For instance, the Ethereum network is based on a Proof-of-work system. When it split into two independent networks – Ethereum Classic (the original chain) and the hard-forked Ethereum –former Ethereum supporters including Chandler Guo threatened to use the 51% attack against Ethereum Classic since it was affordable to gain more than half of the network’s total computing power given the small size of the Ethereum Classic network at the given time.
One popular system, used in Hashcase, uses partial hash inversions to prove that work was done, as a good-will token to send an e-mail. For instance the following header represents about 252 hash computations to send a message to [email protected] on January 19,2038:
X-Hashcash: 1:52:380119:[email protected]:::9B760005E92F0DAE
It is verified with a single computation by checking that the SHA-1 hash of the stamp (omit the header name X-Hashcash: including the colon and any amount of whitespace following it up to the digit ‘1’) begins with 52 binary zeros, that is 13 hexadecimal zeros.
Whether PoW systems can actually solve a particular denial-of-service issue such as the spam problem is subject to debate the system must make sending spam emails obtrusively unproductive for the spammer, but should also not prevent legitimate users from sending their messages. In other words, a genuine user should not encounter any difficulties when sending an email, but an email spammer would have to expend a considerable amount of computing power to send out many emails at once. Proof-of-work systems are being used as a primitive by other more complex cryptographic systems such as bitcoin which uses a system similar to Hashcash
There are two classes of proof-of-work protocols.
Challenge-response protocols assume a direct interactive link between the requester (client) and the provider (server). The provider chooses a challenge, say an item in a set with a property, the requester finds the relevant response in the set, which is sent back and checked by the provider. As the challenge is chosen on the spot by the provider, its difficulty can be adapted to its current load. The work on the requester side may be bounded if the challenge-response protocol has a known solution (chosen by the provider), or is known to exist within a bounded search space.
Solution-verification protocols do not assume such a link: as a result the problem must be self-imposed before a solution is sought by the requester, and the provider must check both the problem choice and the found solution. Most such schemes are unbounded probabilistic iterative procedures such as Hashcash.
Known-solution protocols tend to have slightly lower variance than unbounded probabilistic protocols, because the variance of a rectangular distribution is lower than the variance of a Poisson distribution.A generic technique for reducing variance is to use multiple independent sub-challenges, as the average of multiple samples will have lower variance.
There are also fixed-cost functions such as the time-lock puzzle.
Moreover, the underlying functions used by these schemes may be:
CPU-bound where the computation runs at the speed of the processor ,which greatly varies in times, as well as from high-end server to low-end portable devices.
Memory-bound where the computation speed is bound by main memory accesses (either latency or bandwidth), the performance of which is expected to be less sensitive to hardware evolution.
Network-bound if the client must perform few computations, but must collect some tokens from remote servers before querying the final service provider. In this sense the work is not actually performed by the requester, but it incurs delays anyway because of the latency to get the required tokens.
Finally, some PoW systems offer shortcut computations that allow participants who know a secret, typically a private key, to generate cheap POWs. The rationale is that mailing-list holders may generate stamps for every recipient without incurring a high cost. Whether such a feature is desirable depends on the usage scenario.
Reusable proof-of-work as e-money
Computer scientist Hal Finney built on the proof-of-work idea, yielding a system that exploited reusable proof of work (“RPOW”). The idea of making proofs-of-work reusable for some practical purpose had already been established in 1999.Finney’s purpose for RPoW was as token money. Just as a gold coin’s value is thought to be underpinned by the value of the raw gold needed to make it, the value of an RPoW token is guaranteed by the value of the real-world resources required to ‘mint’ a PoW token. In Finney’s version of RPoW, the PoW token is a piece of Hashcash.
A website can demand a PoW token in exchange for service. Requiring a PoW token from users would inhibit frivolous or excessive use of the service, sparing the service’s underlying resources, such as bandwidth to the Internet , computation, disk space, electricity and administrative overhead.
Finney’s RPoW system differed from a PoW system in permitting the random exchange of tokens without repeating the work required to generate them. After someone had “spent” a PoW token at a website, the website’s operator could exchange that “spent” PoW token for a new, unspent RPoW token, which could then be spent at some third-party website similarly equipped to accept RPoW tokens. This would save the resources otherwise needed to ‘mint’ a PoW token. The anti-counterfeit property of the RPoW token was guaranteed by remote attestation. The RPoW server that exchanges a used PoW or RPoW token for a new one of equal value uses remote attestation to allow any interested party to verify what software is running on the RPoW server. Since the source code for Finney’s RPoW software was published,any sufficiently knowledgeable programmer could, by inspecting the code, verify that the software (and, by extension, the RPoW server) never issued a new token except in exchange for a spent token of equal value.
Until 2009, Finney’s system was the only RPoW system to have been implemented; it never saw economically significant use.
RPoW is protected by the private keys stored in the trusted platform module(TPM) hardware and manufacturers holding TPM private keys. Stealing a TPM manufacturer’s key or obtaining the key by examining the TPM chip itself would subvert that assurance.
In 2009, the Bitcoin network went online. Bitcoin is a proof-of-work crypto-currency that, like Finney’s RPoW, is also based on the Hashcash PoW. But in Bitcoin double-spend protection is provided by a decentralized P2P protocol for tracking transfers of coins, rather than the hardware trusted computing function used by RPoW. Bitcoin has better trustworthiness because it is protected by computation. Bitcoins are “mined” using the Hashcash proof-of-work function by individual miners and verified by the decentralized nodes in the P2P bitcoin network.
The difficulty is periodically adjusted to keep the block time around a target time.
Many PoW systems require the clients to do useless work, such as inverting a hash function. This means that a lot of resources (mainly the electricity that powers the clients’ computers) is used only for providing trust in the currency. To be more efficient with that resource expenditure, some alternative coins use a PoW system where the performed work is actually useful.
Here are 3 of the main problems I see with the current proof of work setup:
1. The Competitive disadvantage and inevitability of monopoly
Where financial incentives and personal interests collide, you get divisions. These are inevitable in any functioning ecosystem and Bitcoin should certainly not be de-incentivised. However, what we are increasingly witnessing the emergence of a new political class within the Bitcoin network. It seems that miners, for purely economic reasons are increasingly brining their own agendas to the forefront. This has contributed massively to the new trend of hard-forking for political differences. The forking of Bitcoin is almost exclusively a result of the disagreements about mining difficulties and compensations using the proof of work algorithm.
Miners have invested small fortunes in ASIC processor powered ‘mining farms’ that are specialised for mining Bitcoin, and not only has this made it almost impossible for new entrants to enter the Bitcoin mining pool, it has also resulted in Bitcoin being forked to form alternative revenue streams for these groups.
Segwit was opposed by miners because of the reduced mining reward, (the Lightning Network will likely cause further tumult if adopted en masse in the Bitcoin network, as it takes transacting off chain and will reduce greatly the demand for transaction confirmations and new blocks). Other currencies since have attracted miners by increasing the block sizes but as a consequence, may have inadvertently decreased competition by making it increasingly harder for independent miners to compete with the larger mining farms. This centralisation of what underpins the security of Bitcoin is increasingly being considered as a concern for those attracted to Bitcoin’s decentralisation.
2. Barrier to entry and Economic Disadvantage for poorer communities
Whether or not we like to admit it, the entire mining industry is economically unfair. First of all there is the basic fact that Bitcoin’s price is not linked to the petrodollar (Thank god!), but this ultimately means that if you live in a region where electricity is not subsidised, you are at a considerable economic disadvantage in comparison to mining rigs set up in subsidised nations. In addition to this, the start up cost of attaining ASIC processors and cooling equipment has left most developing nations high and dry. In fact, no more than 15 mining pools pretty much have oligopoly over the entire bitcoin mining infrastructure. That is shockingly close to being centralised and is hardly the egalitarian utopia that was envisioned in Satoshi’s whitepaper.
For example, in Bitcoin the hashing algorithm is double-SHA256 (SHA2562) and the prede?ned structure is a hash less or equal to a target value T. The success probability of ?nding a nonce n for a given message msg, such that H = SHA2562(msg||n) is less or equal to the target T is
PrH ? T =T
This will require a party attempting to ?nd a proof of work to perform, on average, the following amount of computations
1 = 2256
PrH ? T T (2)
Finally, it is easy to see that it can be e?ciently veri?ed whether the nonce accompanied with the message is indeed a valid proof of work by simply evaluating
SHA2562(msg||n) ? T (3)
8.An Overview of SHA256
A detailed description of the SHA256 hashing algorithm can be found in the official NIST standard. This section provides an overview of the SHA256 algorithm that forms the backbone of the Bitcoin ecosystem. The integrity of Bitcoin transactions depends upon the
collision resistance and pre-image
resistance of the SHA256 hashing algorithm. It is important to remember the fact that in the Bitcoin protocol, the SHA256 hash is computed twice.
Figure : An Overview of the SHA256 Hashing Algorithm
The SHA256 algorithm takes an input that has a length of less than 264 bits. It has a block size of 512 bits which are represented as a sequence of sixteen 32-bit words. This 512 bit block enters a function called the message compression function in words of 32 bits (Wt) through a message scheduler. Both of these are explained in detail later on. The message
scheduler expands the 512 bit message block into sixty-four 32-bit words. The operations inside the SHA256 hashing algorithm are performed on words that are 32-bit in length using eight working variables names as A, B, C, D, E, F, G and H that are also 32-bits in length. Hence, the word length of the SHA256 algorithm is of 32 bits. The values for these working
variables are computed at every round and this process continues till 64 rounds have been completed. Very importantly, it should be noted that all additions in the SHA256 hashing algorithm are performed modulo 232. Hence, the reader should interpret all additions mentioned henceforth in this text as additions performed modulo 232.
SHA256 also takes a 256 bit initialisation vector (IV) which is fixed for the first message block. An intermediate message digest obtained at the end of the first 64 rounds which serves as the IV for the next message block. The SHA256 hash function is built using the Davies-Meyer construction where the IV is added to the output at the end of 64 rounds. Thus, after 64 rounds of the message compression function and addition of the IV, the
algorithm produces an intermediate message digest of 256 bits. After the entire message blocks have been hashed, a value on 256 bits is obtained that is the final message digest of the input message. The SHA256 hashing algorithm is thus comparable to a block cipher with a 256 bit message block size (IV) and a 512 bit key (message block) that is expanded into sixty-four 32 bit round keys using the message scheduler for each of the 64 rounds of this cipher. The Bitcoin protocol takes advantage of the avalanche property of the SHA256 algorithm that makes it very hard for attackers to find shortcuts in finding a new block that starts with the stipulated number of 0s. The next section will take a deep-dive into the insides of the SHA256 algorithm.
An Overview of the Bitcoin Block Header Hashing Algorithm
Mining devices use the Bitcoin Block Header Hashing Algorithm to find new blocks and thereby mine new Bitcoins. Looking from a purely technical perspective, the process of Bitcoin mining basically involves mining devices continuously calculating the double SHA256 hash of the Bitcoin block header and waiting for an output that would be accepted by the Bitcoin network. This section will emphasise on what constitutes this Bitcoin block header and how it is constructed. The construction of the Bitcoin block header will throw a light on
how the data to be hashed actually enters the SHA256 hashing algorithm. It will also explain what part of this data typically remains constant throughout the mining process, what data changes but rather infrequently and what part of the data changes quite frequently.
The Bitcoin block header hashing algorithm is explained using a colour coded approach. Three colours viz. Green, Yellow and Red are used in order to explain the rate at which these values fluctuate relative to the process of Bitcoin mining. The green colour specifies that the value will either remain constant forever or for significantly long period of time. The yellow colour indicates that the value will change but rather quite infrequently i.e. relatively after some amount of time. The red colour indicates that this data value will change the fastest i.e. typically for every hash calculation. It needs to be pointed out that the colour coding and the data change frequencies mentioned are relative to the hashing speed of current hashing devices that are huge. The next figure shows the structure of the Bitcoin block header and how it is fed to the double SHA256 hashing algorithm in order to obtain a hash value that gets accepted by the Bitcoin network.
Figure : The Bitcoin Block Header Hashing Algorithm
From the figure, it is evident that the process of Bitcoin mining i.e. hashing this Bitcoin block header employs three applications of the SHA256 hashing algorithm. We shall name them SHA2560, SHA2561 and SHA2562. These notations will henceforth be used throughout this
text for addressing that particular application of the SHA256 hashing algorithm. The block header being greater than 512 bits in length, it is processed by two applications (SHA2560, SHA2561) of SHA256 (one 512 bit block at a time). SHA2560 takes the first 512 bit block as
input and after 64 rounds, produces the intermediate message digest H0. SHA2560 takes the default IV on 256 bits. The default IV that SHA2560 uses will be constant forever and hence it has been marked with the green colour. As the calculated intermediate message digest H0 depends on inputs marked with the
yellow colour, H0 is also marked as yellow.
SHA2561 uses H0 as its initialisation vector and takes the next 512 bits as its input block. The red coloured nonce is present in the input and hence, the final message digest, H1 produced by SHA2561 is also marked as red. The process of hashing the block header does not stop here. The final message digest H1 produced by SHA2561 is applied through another SHA256 hashing which we name as SHA2562. SHA2562 takes the 256 bit block of H1 as its input message block and applies suitable padding to make it a block of 512 bits. SHA2562 being an additional application of SHA256 applied again, uses the same default IV as used by SHA2560 which is marked as green. After 64 rounds of the compression function of SHA2562, the final hash H2 is generated which for obvious reasons is marked as red in the earlier figure. H2 is then checked to see if it satisfies the current constraints of the Bitcoin protocol. If H2 does satisfy these constraints, the successful block with the correct nonce is broadcast immediately in the Bitcoin network for acceptance and
to claim the mining reward. The Bitcoin mining process thus basically involves the below calculation repeated potentially billions of times with variable nonces
H2 = SHA256(SHA256(Block_Header))
Equation : Bitcoin Mining – Hashing the Block Header
The reader may question as to why an additional application of SHA256 is made at the end.Why Satoshi Nakamoto chose to have double SHA256 hashing is to prevent length extension attacks. The SHA256 hashing algorithm, like all hashes constructed using the Merkle-Damgård paradigm, is vulnerable to this attack. The length extension attack allows an attacker who knows SHA256(x) to calculate SHA256(x||y) without the knowledge of x. Although it is unclear how length extension attacks may make the Bitcoin protocol susceptible to harm, it is believed that Satoshi Nakamoto decided to play it safe and include the double hashing in his design. For this double hashing is that 128 rounds of SHA256 may remain safe longer if in the far future, a practical pre-image or a partial pre-image attack was found against SHA256.
Regardless of the reason behind it, what is important to know and to understand is that whenever a SHA256 hash is calculated in Bitcoin, it is a double SHA256 hash. Thus, a double hash of the block header is calculated and is then checked if the value of the hash conforms
to the Bitcoin protocol proof-of-work constraints. The next section covers the details of the Bitcoin block header by explaining what each data block contains and the frequency by which these data change.
Details of the Bitcoin Block Header
The block header may also occasionally need to be updated while working on it during mining. It is important to know that it is the body of the block that contains the actual transactions and NOT the block header. All the transactions contained in the block are only hashed indirectly into the block header via the Merkle root . This ingenious
method not only ensures the transaction integrity but another offshoot of this arrangement is that the time taken to hash the block header becomes independent of the number of transactions that it contains.
Table: Bitcoin Block Header Fields Along With Their Brief Description
This 32-bit value is an integer that represents the version of the rules that the Bitcoin software follows to create a new block. The current value is 2 and has changed ever since BIP00349 was accepted in July 2012. Before that, the value was 1. The point to take here is that this value can be considered as constant and is hence marked as green in the table above as well as in figure Bitcoin Block Header Hashing Algorithm. The announcement that Version 1 blocks will soon be orphaned was made by Gavin Andresen, the lead core Bitcoin developer in his post on Bitcointalk. The BIP that has been accepted has implemented the rule that if 950 of the last 1,000 blocks are version 2 or greater, then reject all version 1 blocks in the community, mentions that currently more than 90% of new blocks created are of version 2 and that the Bitcoin community will soon stop accepting blocks with version as 1.
This is the 256 bit H2 of the previous block that was accepted by the Bitcoin network. It is important to know that the miner has to find a new block after the latest accepted block and he tries to be the first to solve the proof of work problem. The solution to the proof-of-work problem however, is NOT unique and is actually a race between different miners to be the first to solve and broadcast the new H2 that will be accepted by the network. If accepted, the miner will hence be awarded with the current mining reward of 25 BTC along with the transaction fees that were included in the individual transactions held by the block. As the Bitcoin protocol is designed such that a new block is generated by the network in approximately every 10 minutes, it is safe to assume that on average, hashPrevBlock needs to be updated after around every 10 minutes. For this reason, we have marked it with the yellow colour.
hashMerkleRoot is the 256 bit value of the Merkle Root. Similar to hashPrevBlock, hashMerkleRoot will typically on average change in around 10 minutes time and hence even this is marked in yellow. There is another scenario where hashMerkleRoot changes and this will be explained ahead in section nonce
This 32 bit value is the current time in seconds since 1970-01-01 T00:00 UTC. The miner may have some flexibility of varying it to his advantage but this is very risky as there are only 600 seconds in that 10 minute window and every microsecond counts. Considering the hashing rate of current miners, 1 second is relatively a large timeslot and we have thus marked the timestamp field as yellow; indicating that it changes but relatively rarely.
This value is a compact version for it and is expressed in 32 bits rather than 256 bits. This is a particular sort of floating-point encoding that uses 3 bytes mantissa, the leading byte as exponent (where only the 5 lowest bits are used) and the base is 256. The target changes after every 2016 new blocks which takes about 2 weeks time. As the target changes in about two weeks’ time, we have marked it as green.
This 32 bit value is the only value in the block header that is the most volatile as it changes on every attempt of the double hash on the block header. We have thus marked the nonce field in red. The nonce starts at 0 and it is incremented strictly in a linear manner for each H2 attempted. One interesting question that needs to be brought up is that if one knows the current target, what would be the probability of finding H2 that will be accepted by the Bitcoin network? This probability is given by:
Probability = Target/2256 = 1/(Difficulty*232)
With the current Difficulty10 at the time of writing being 65750060,
Probability = 1/(65750060*232) = 2-57.97
Hence, the average number of hashes that need to be tried to solve a block = 1/Probability = 257.97
That been said, we know that there are only 232 possible values for the nonce! This means that the nonce is probably going to overflow more often than not. If this happens, there is a provision in the Bitcoin protocol such that whenever the nonce overflows, the “extraNonce” portion of the generation transaction in the block is incremented which ultimately changes
the Merkle Root. Once this updated Merkle Root is added to the block header, calculation commences again with nonce at 0 until an acceptable H2 is found. Else, this process is repeated. This is the second scenario in which hashMerkleRoot might change while a miner is solving for a new block. This value of 57.97 also means that H2 will need to start with 58 or more 0s and also be less than the target so as to be accepted in the block chain by the
5.2.7 Padding + Length
For SHA2561, padding + length are 384 bits long while for SHA2562, it is 256 bits long. As the specification of SHA256 is known and the length of the input message to SHA2561 and SHA2562 is fixed i.e. 640 bits and 256 bits respectively; the padding + length field will always remain constant. We have hence marked these in green.
After comprehending all of this, the reader may argue that given all these fields, the same sequence of hashes will be generated by all miners and the miner with the most mining capability will always be able to solve the block first. This is in fact not true as it is almost impossible for two miners to end up with the same hashMerkleRoot. This is because each block has a unique transaction called the “Generation Transaction” or the “Coinbase
Transaction”. This transaction grants the mining reward and the transaction fees to the miner once the block is accepted by the network. As this generation transaction is unique, hashMerkleRoot is generally unique for all miners and every hash calculated by a miner has the same chance of solving the block as every other hash calculated in the entire Bitcoin network. Therefore, it can be said that the process of Bitcoin mining is analogous to a lottery
draw where each participant has an equal chance of winning. But as people tend to buy more and more lottery tickets in order to have a better chance at winning the lottery, same is evident in the Bitcoin world where there is an arms race between miners to obtain mining devices with the fastest hashing rate. This is because a mining device with a faster hashing rate can make more attempts at solving the block in a given time. Winning the Bitcoin
lottery is getting harder every two weeks as the network hash rate is constantly on the rise which is driving the Difficulty up as well. Bitcoin miners are now clever enough to participate in mining clusters or mining pools that helps to smooth their gains in mining and remove the lottery aspect from their earnings. Each miner is then paid out on the basis of the hashing rate contributed to the cluster/pool.