Fig. 2. The Block Hashing Algorithm of bitcoin revisited and seen as a Constrained Input Small Output (CISO) problem. We see two applications of SHA-256 together with internal details of the Davies-Meyer construction. We can view it as a triple application of a specific block cipher. An interesting question is whether there is a more efficient cryptographic shortcut or inversion attack or some non-trivial optimizations which allow to save a constant factor. Such optimizations, if they exist, could be worth some serious money as they would allow to produce bitcoins cheaper.

Here target is a large integer which is a global variable for the whole bitcoin system worldwide, and on which all the participants worldwide are expected to agree. The value of target slowly changes with time and is adjusted approximately every 2 weeks. More details are given below in Section 7.1. The job of bitcoin miners is to find these solutions and publish them. They are rewarded with some bitcoins for their work. In 2013 the reward is 25 BTC (25 bitcoins) per valid solution. How exactly this reward works and how it changes over time will be explained later. It is generally believed that there is no other method to achieve success than trial and error; hashing at random as depicted on Fig. 2 until a result with a sufficient number of leading zeros is found. However this is unlikely to be true, there is always a better way, at least slightly, see Section 12. A number of data fields are present as inputs to the CISO problem, cf. Fig. 2. Some data are fixed or change very slowly and these are indicated in green on Fig. 2. Other data need to be adjusted by the miner in order to obtain a solution however they still change very slowly. Such data are indicated in yellow on the main picture. Data which change the most frequently are indicated in red: these are “hot” data which need to be re-computed each time the nonce changes. Bitcoin is a live distributed system and the exact conditions required for the data to be consider valid are essentially fixed and known, however they are likely to evolve with time in subtle ways. Rules have already been and are likely to be altered during the operation of the system. They also depend on the consensus of participants in the system. It is generally admitted in the bitcoin community that there could be and should be many different versions of the software which co-exist. This is because if all the software came from one single source, bitcoin would cease to be a system independent from any central authority and would develop a serious syndrome of a single point of failure. Therefore bitcoin software should be diverse. We could even postulate that nobody should be excluded from making their own software even though we might be worried about Denial of Service attacks. In practice the reality is different: the original Satoshi software [6] conserves a prominent position. In what follows we are going to describe what different inputs are. We need to pay attention to the degree of freedom which is allowed: to what extend the miner is able to select different values in order to achieve the desired result. We have: 1. Version number on 32 bits. This is an integer which represents the version number of the bitcoin software. It defines the rules which govern the blocks, which blocks could be accepted as valid. It is essentially a constant, since the creation of the system in 2009 it has always been equal to 1 then it became 2. At the time of writing new blocks are typically version 2 and it has been announced that very soon the community will stop accepting blocks generated compliant with older version 1 rules. 2. The previous block on 256 bits. Or more precisely a hash on 256 bits of all the data of the previous CISO block encoded in a specific way. Each new block is added at the end of the chain of blocks. Ideally there is only one official chain of blocks. The miner has essentially no choice, a new CISO block is created approximately every 10 minutes and it is broadcast in the peer to peer network (and published on the Internet) as soon as possible. The current block very quickly becomes obsolete. Either miners will now use it as a previous block, or they will use another freshly generated solution. The solution is NOT unique however there is only one winner (in the long run). Each miner who produces a solution wants this solution to be known by the highest possible number of other miners and ahead of any competing solution. It is a race where every microsecond counts. The process of generating new blocks is a sort of lottery and the probability that there will be two winners in a very short interval of time is low. It is the miner’s responsibility to check very frequently if a solution have not already been found. If this is the case, it is not in his interest to find another one later on, his chances to succeed decrease quickly with time. On the human and technical/software side however, network propagation makes that not all participants have the same view of which solution was the first, and there is a real possibility to have disputes. Potentially bitcoin could split into two systems which do not recognize each other and which operate two independent ever growing blockchains. In theory there is a so called Longest Chain rule which allows to solve this problem [41]. In practice it is a bit different. The Longest Chain rule might be hard to enforce. People may rather trust a well-established website than siome votes which come from the (more obscure) peer-to-peer network. They could suspect or resist an attack by a powerful entity. They can simply agree to disagree because they have spent some substantial money on electricity on one version of the chain. 3. The Merkle root on 256 bits . This is a sort of an aggregated hash of many recent events in the bitcoin network which certifies that the system recognizes all of them simultaneously as being valid. Moreover it also has a self-certifying property . It also hashes and certifies the public key of the future owner of this freshly created portion of bitcoin currency which this block is intended to embody, as soon as it is in turn confirmed by few other CISO blocks. The current CISO block which the miner is trying to create by solving the current CISO problem and all subsequent CISO blocks will provide an accu- mulation of evidence about all these events which will be increasingly secure and increasingly hard to falsify with time. This security guarantee increases with time. It is achieved because miners expend a lot of computing power, the number of miners is increasing, and more recently they use specialized devices with increasing fixed (equipment) costs. All these things are increasingly hard to imitate. Interestingly the value of the Merkle root can (and needs to be) influenced by the miner as explained below. First of all it is clear that miners do have some discretionary powers and should be able to collude and/or select which transactions are going to be recognized by the system. However the transaction fees which are decided at the moment of making a transfer from one bitcoin address to another are an incentive to include every single transac- tion. Thus the miner is able to collect hundreds of transaction fees for each block generated. The Merkle root value is always produced by a hash function which is expected to behave as a random oracle. This means that the miner can influence this Merkle root value but only very slightly, basically by trial and error. 4. Timestamp on 32 bits . This is the current time in seconds. The miner can hardly change it. This would be extremely risky as another solution could be submitted at any moment. There are only 600 seconds in 10 minutes. 5. Target on 32 bits . More precisely the global variable target is on 256 bits and what is stored here is a compressed version of target which is frequently called difficulty . We have difficulty ≈ 267 , 731 , 249 ≈ 2 28 . 0 as of 22 October 2013. This difficulty is a real (floating) number which is at least 1 and which is stored in a 32-bit format. We have difficulty ·  2 32 = 1 / probability = 2 256 / target . 6. Nonce on 32 bits . This nonce is freely chosen by the miner. Interestingly the nonce has only 32 bits while the current value of target makes that the probability of obtaining a suitable H 2 by accident is as low as 2 − 60 . 00 . This means that the miner needs to be able to generate different versions of the puzzle with a different Merkle root (or with other differences) 7. Padding+ Len has 384 bits for H1 and 256 bits for H2 . These are two constants due to the specification of SHA-256 hash function which is used here twice with data of different sizes: the input hashed has 640 and 256 bits respectively in each application of SHA-256. These two values never change. With respect to the input data requirements and constraints above and the output constraint H 2 < target we have: Definition 6.1 (CISO Problem). We call the CISO Problem the problem of finding a valid Merkle root and other data as illustrated on Fig. 2 which is correctly formed and will be accepted by the majority of current bitcoin software. The integer target is system-wide variable which should be the same for all bitcoin miners at any given moment. From the point of view of the miner it should be considered as a constant. It changes with time according to pre-determined rules. It determines how hard it is to solve the CISO problem. It is implements self-regulation. The target value is adjusted simply in such a way that the total number of CISO blocks found by all miners on our planet taken together is constant in a given period of time. More precisely and according to the rules embedded in current bitcoin software, on average one block should be generated every 10 minutes. This regulation is achieved by observation of the speed at which shares have been generated in a fixed period of time and adjusting the global variable target accordingly. The exact value target changes roughly every two weeks, or when exactly 2016 new blocks have been produced. It goes without saying that the actual speed at which the blocks are generated is not uniform, however it remain close to uniform. As of 22 October 2013 we have

This current probability of 2 corresponds to the requirement of having 60 leading zeros, and in fact slightly more or less slightly less than 60, the exact rule is simply that the equation H 2 < target needs to hold. The value of target changes quite frequently. This current probability of 2 − 60 . 00 is really the success probability for mining by hashing the appropriate data at random with a double application of the hash function (as required cf. Fig 2). This is already an extremely small figure. It makes bitcoin mining very difficult. It reflects the fact that many people have already solved many CISO puzzles and obtained bitcoins as a reward. Tens of thousands of people worldwide mine bitcoins with increasingly powerful computing devices. Accordingly the difficulty increases which is necessary in order to keep limited monetary supply in the system. At the moment of writing the global hash rate in the network was already 3000 TH/s and has increased about 50 times in the previous 6 months. Remark 1. Typically target decreases with time. However it can also go slightly up in order to insure that CISO blocks are produced at a uniform speed. It should and could substantially increase if for some reason the global production of CISO blocks goes down, for example due to increased electricity prices or important “real money” capital outflows in the bitcoin market. Such events are more than likely to happen, see Section 13.1. Remark 2. Initially in early 2009 the probability was only 2 − 32 . 0 . Back then it was 256 million times easier than today to solve CISO puzzles. Many early adopters of bitcoin have made a lot of money. One of the well-known problems of bitcoin is the problem of hoarding: a substantial proportion of bitcoins in circulation is not used. Remark 3. It is also widely believed that many bitcoins have been lost because their owners did not think it would ever be worth some serious money. Even though all bitcoin data are public there is no way to tell the difference between bitcoins which are saved (and could be sold or exchanged later), from those which have been lost. Therefore is it not correct to believe that the monetary supply of bitcoins is fixed. We can only say that it is upper bounded and limited by the existing production and a cap of 21 million bitcoins to be ever produced. However there is no way to know how many bitcoins are in active existence.

In this part we look at a pure specialist question which pertains to symmetric cryptography, of whether there is a cryptographic “shortcut” attack: simply a method of mining bitcoins faster than brute force, or faster than the trivial method in which the SHA-256 hash function is a black box. The answer is trivially yes, such a method trivially exists and most developers of modern bitcoin miner hardware have already applied various tricks which enhance the speed or/and decrease the cost. However until now there was no public discussion of these questions and it was not possible to see how far one can go in this direction. In this paper we describe a series of more or less non-trivial optimizations of the bitcoin mining process. These optimizations are quite important as considerable computing power is already expended on our planet on bitcoin mining [34]. The question is what is the fastest possible method for bitcoin mining, given the specific structure of Fig. 2 and can we save some of the gates needed for this task. The answer is yes we can. In this paper we are the first to develop such techniques openly and publish them. We have invented these techniques independently from scratch and to the best of our knowledge they are free of any intellectual property rights. However we expect that ASIC designers have already done similar optimizations and some of these techniques could have been patented. Since 2009 bitcoin mining have gone through four major stages. Speed of bitcoin operations is measured in GH/s or mega hashes per second, as these operations are essentially about computing the standard hash function SHA-256 many times. No source gives a clear definition of H/s as the speed of SHA-256 is variable and depends on data length. We will go back to this question later. 1. First generation - software mining using CPUs . Initially amateurs used to do these computations at home with open-source software. Various modern CPUs allow to achieve roughly between 1 and 5 MH/s per CPU core. With this technology miner have been expanding quantities of energy to produce one Giga Hash per second. For example we have computed that with Intel i5 processors we would need some 50 4-core CPUs consuming 4000 Watts. The power consumption is therefore 4000 W per GH/s. 2. Second generation - software mining using GPUs . Graphic card CPUs have revolutionized bitcoin mininng however they have NOT always achieved very important savings compared to CPUs. In some cases their electricity consumption is not much lower than with CPUs. Other solutions are more efficient and allow one to mine with a power consumption at least 10 times lower than with CPU mining see [29]. For example with Radeon 7790 we obtain about 0.33 GH/s with a power consumption of 70 watts. This is about 210 W per GH/s. 3. Third generation - hardware mining with FPGAs . Then miners have used FPGAs, not always achieving much higher speeds on devices with com- parable cost and size, but decreasing the power consumption quite substantially, up to 100 times in comparison to CPU mining. For example ModMiner Quad based on a 45 nm FPGA requires about 50 W per Gh/s. 4. Fourth generation - hardware mining with ASICs . Finally since mid- 2013 miners are moving towards using ASICs, dedicated hashing chips. This further decreases the cost of mining and in particular power consumption many times. These devices can achieve as little as 0.35 W per Gh/s (pre-order announcement from Bitmine.ch expected to ship in November 2013). As we can see, the energy efficiency of bitcoin miners have improved by a factor of nearly 10,000 since 2009. Recent developments have driven amateurs out of business and require them to invest thousands of dollars and purchase specialized hardware. At the same tile new innovative business ventures make money by selling increasingly sophisticated bitcoin mining devices. At the moment of writing the key players in this business are the US company Butterfly Labs, Swedish KNC miner, the Swiss company Bitmine.ch, their Russian competitor BitFury and few other. There is abundant publicly available data about bitcoin mining. In April 2013 it was estimated that bitcoin miners already used about 982 Megawatt hours every day, enough to power about 30,000 U.S. homes or an equivalent of 150,000 USD per day in electricity bills. Still they would be able to make some 0.7 Millions of dollars in daily profits [34]. At that time the hash rate was about 60 Tera Hashes/s. At the moment of writing (22 October 2013) the hash rate has attained 3000 Tera Hashes/s due to a massive switch from GPU and FPGA mining to ASIC mining. However the power consumption have probably decreased due to the fact that recent mining devices are more efficient, see Section 12. Bitcoin mining is known to be a highly profitable business. Some online tools for bitcoin profitability calculations based on the price of electricity are available, cf. [1]. We contend that there will be further improvements in the basic technology. In science, not everything can be improved. Interestingly in business, we are accus- tomed to see that more or less every technology which has some economic impact can be systematically improved every year. This is for example is reflected in the famous Moore’s law. We see no reason why it should be otherwise with basic algorithmic technology behind bitcoin mining, this independently from the question of efficient hardware implementation of this technology. Such improvements are inevitable. In the long run, we believe that sooner or later there will be substantially better technology for bitcoin mining, would this be with quantum computers or a fundamentally different methodology than currently known. In order to fix the ideas we call this claim a super optimistic assumption . The interesting aspect is that researchers who are able to generate such improvements will be able to make a lot of money by mining bitcoins and selling them at their market price, or by licencing their algorithmic improvements to miners. Moreover even a tiny energy efficiency improvement of 1 % could be profitable as it will generate already thousands of dollars of tangible savings on electricity bills. In this paper we show that such improvements are possible, see Section 12. However we have do not claim that we are getting anywhere near the fifth generation of bitcoin miners. We have been only moderately successful in this task and therefore our result are like generation 4.1. of bitcoin miners, a small improvement. We offer our improvements free of charge and do not plan to patent them. In this section we re-visit and expand our technical explanation of the internals behind bitcoin mining fom Section 6.3. We recall that we can see the problem of bitcoin mining as a specific problem in symmetric cryptography which we called “CISO hash puzzle”. It involves three applications of a block cipher. We have already outlined this approach on Fig. 2 and now we explain it in all due details. Our analysis follows the NIST specification of SHA-256 [30] and the inspection of the Bitcoin source code [6]. We use vere similar notations and graphical conventions as the leading experts of SHA-256 in the cryptographic literature, see for example [35, 40]. We start by recalling how the SHA-256 has function is constructed and then we show how exactly it is used in bitcoin mining. SHA-256 is a hash function built from a block cipher following the well-known Davies-Meyer construction in which the input is at the end added to the output. This construction is one of the known methods to transform a block cipher into a compression function. A compression function is a building block of a hash function with a fixed input size. It is typically equal to twice the output size. In our case we have a compression function from 512 to 256 bits, cf. Fig. 3. The block size in this block cipher is 256 bits, the key size is 512 bits which is expanded to 64 subkeys on 32 bits each for each of 64 rounds of the cipher. The first 16 subkeys for the first 16 rounds are identical to the message and are copied in the same order cf. [30] and later Fig. 10. In addition in order to hash a full message, SHA-256 applies a Merkle- Damgard padding and length extension which makes it a secure hash function for messages of variable length. In the pre-processing stage, we must append one binary 1 and many zeros to the message in such a way that the resulting length is equal to 448 modulo 512, cf. [30]. Then we append the length of the message in bits as a 64-bit big-endian integer. An interesting peculiarity in Bitcoin specification and source code is that hashing with full SHA-256 is applied twice. This may seem as excessive: one “secure” hash function should be sufficient. It also makes our job of optimizing bitcoin mining substantially more difficult. In the first application of SHA-256 in Bitcoin mining the message has a fixed length of 640 bits which requires two applications of the compression function as shown on Fig. 4. In the second application SHA-256 is applied to 256 bits. Overall “in theory” we need three applications of the compression function as already shown on Fig. 2 which we also show on a smaller-scale Fig. 5 below for convenience. It may therefore seem that a bitcoin miner needs to compute the compression function 3.0 times for each nonce and for each Merkle hash. In the following sections we are going to work on reducing this figure down to about 1.86 on average. Further details about inner mechanisms of SHA-256 will be provided later when we need them cf. for example Section 11.4. We recall from Section 6.2 that new bitcoins can be created when the miner succeeds to hash some data from the bitcoin network together with a 32-bit random nonce and is able to obtain a number on 256 bits which starts with a certain number of 60 or more zeros. We call it C onstrained I nput S mall O utput problem or shortly the CISO problem. On Fig. 5 we recall the key steps in this process. The process needs to be iterated with different values of MerkleRoot and different 32-bit nonces until a suitable “CISO configuration” is found in which the output satisfies H 2 < target as explained in Section 6.4. We can reduce the cost factor from 3.0 to 2.0 almost instantly by making the following observation. In the process of bitcoin mining the first compression function does not depend on the random nonce on 32 bits. Therefore we can compute it once every 2 32 nonces. On average we need 1 2 . 0 + 2 32 compression functions. The added factor is the amortized cost of the first hash and can be neglected. Important Remark. In more advanced bitcoin mining algorithms the miner does not have to compute the output for every nonce. He can do it only for some well chosen nonces. They may be chosen in such a way as in order to obtain specific values which make the computation easier. Moreover, some well chosen nonces could be generated in some specific order in order to enable incremental computations. In an incremental computation some computations could made easier by reusing all the (known) internal values in one or several previous computations. There is a lot of highly non-trivial optimizations which can be developed. One simple example of incremental computation will be given in Section 11.4, another in Section 11.9. We look at the computation of H2 on Fig. 5, (the second computation of the hash function and the third compression function). A close examination reveals that in last rounds of the underlying block cipher the two words on 32 bits in which we we want to have at least 60 zeros, after addition of a suitable constant, are created at rounds 60 and 61 if we number from 0. We basically want to force values created at rounds t = 60 and 61 to two fixed constants which come from the SHA-256 IV constants, and which would produce zeros at the output. For this most of the time we just need to compute the first 61 rounds out of 64 and we can early reject most cases. Only in 1 / 2 32 of cases we need to compute 62 rounds in the third compression function. Then only in some 1 / 2 60 of cases where we have actually obtained at least 60 zeros, we would need compute the full 64 rounds. Thus overall one only needs to compute the whole compression function an equivalent of very roughly 1 + 61 / 64 ≈ 1 . 95 times on average. Most of the time one only needs to compute H 1 and 61 rounds of H 2 to early reject the 32-bit value obtained which must be equal to the IV constant. Remark 1. This figure is not exact and in fact it is slightly less. This is because we can in fact save a higher fraction of about 3/48 of the message expansion process when we stop our computation at 61 rounds. This is due to the fact that message expansion is only computed in the last 48 rounds, in the first 16 rounds the message is copied cf. [30] and later Fig. 10. For the sake of simplicity we ignore the message expansion in our calculations. Remark 2. We have carefully checked the ordering of words by inspection of bitcoin source code [6] and by computer experiments. An interesting question is what would happen if the bitcoin designers have formatted the output of the hash function in the reversed order. If they required that 60 bits are at 0 at the opposite end compared to the current formatting, then it is possible to see that the miner would need to do more work: 63 out of 64 rounds in the last application of the compression function. This would make mining more expensive and would cancel most of our savings. Now we look at the second computation of the hash function in the second compression function, the computation of H1 on Fig. 5. Here we use the observation that in SHA-256 the key for the first 16 rounds are exactly the 16 message blocks in the same order, cf. [30] and Fig. 10. It is possible that in the second compression function on Fig. 5 the nonce enters at round 3 (numbered from 0) and therefore in most cases we just need to compute the last 61 out of 64 rounds of the block cipher. The first three rounds are the same for every nonce and their (amortized) cost is nearly zero. Putting together Improvement 2 and Improvement 3, overall one only needs to compute the whole compression function slightly less than an equivalent of 2 ×  61 / 64 = 1 . 90 times. This improvement requires us to delve more deeply into the structure of the block cipher inside SHA-256. We recall that the state of the cipher after round 2 is constant and does not yet depend on the value od the nonce. The 32-bit nonce will be precisely copied to become the session key for the round 3 of encryption. On Fig. 7 we show the circuit for one round of encryption where at round 3 the nonce enters as W 3 = nonce as shown on later Fig. 9. Here denotes one addition on 32 bits. Here W t is the key derived from the message and K t is a certain constant [30]. For t = 3 we have W 3 = nonce . Now it is obvious that the whole round 3 can be computed essentially for free in the incremental way. We just need two 32-bit increments instead of one whole round which is about 7 additions and 4 other 32-bit operations. Each time we increment the nonce we simply need to increment two values at the output of round 3 which is shown on Fig. 8 below.

Each time a certain type of good, medium or technology is widely adopted as a mean of exchange and payment, and regardless if we would really agree call it “a currency”, it has certain pre-existing characteristics. These are its (rela- tive) rarity, security understood as important difficulty to forge this “currency” and/or to commit fraud. The rules which govern the adoption of cryptographic technology are not dissimilar. In cryptography, when a certain cryptographic scheme is massively adopted, it is so because it is hard to break. Money has somewhat to resist fraud theft and forgery, cryptography has to withstand the presence of hackers and code breakers. Both emerge through the process of nat- ural selection in which different types of payment technology or/and different sorts of cryptography co-exist. With time some solutions emerge as a preferred choice however a certain bio-diversity always remains. In this paper we study bitcoin with particular attention paid to the process of bicoin mining, which is the specialist term given to the process by which new bitcoins are created. We are going study this question from many different angles. It is a cryptographic puzzle, but also a disruptive technology in monetary history. It also is method to make money for miners, a method to own and control the bitcoin currency, a method to police the bitcoin network and enforce the compliance with a certain version of the bitcoin specification, etc. Later in Part II we are going to to study in a lot of detail one particular technical question in symmetric cryptography to see if there exists an improved method which allows one to mine bitcoins faster. Bitcoins are a type of digital currency which can be stored on a computer, though it is advisable to store them rather in a more secure way. For example on paper and in a safe, or on a smart card or another highly secure platform. Bitcoins use the concept of so called “Proofs or Work” which are solutions to certain very hard cryptographic puzzles based on hash functions. However these solutions are NOT bitcoins. The puzzles are rather part of the bitcoin trust infrastructure. In fact the puzzles are connected together to form a chain and as the length of this chain grows, so does the security level. Bitcoins are simply awarded to people who produce these “Proofs or Work” which is a very difficult task. Ownership of bitcoins is achieved through digital signatures: the owner of a certain private key is the owner of a certain quantity of bitcoins. This private key is the unique way to transfer the bitcoin to another computer or person. The operation of so called bitcoin mining or creating bitcoins out of the thin air is not only possible. It is essential, it is encouraged, and it is a crucial and necessary part of the Bitcoin ecosystem. Cryptographic computations executed by a peer-to-peer network of a growing network of currently some twenty thou- sand independent nodes [20] are the heart of the security assurance provided by this virtual currency system. It would be very difficult and extremely costly for one entity to corrupt all these independent people. The sum of all this col- lective computational work provides some sort of solid cryptographic proof and prevents attacks on this system. This also how the network polices itself: miners are expected to approve only correctly formed transactions. Bitcoin implements a specific sort of distributed and decentralized electronic notary system without a central authority. Well almost. Certain decisions about how the system works, what exactly the bitcoin software does and how [6], are still pretty centralized. They are subject to adoption or rejection by the wider community. In a nutshell, bitcoin miners make money when they find a 32-bit value which, when hashed together with the data from other transactions with a standard hash function gives a hash with a certain number of 60 or more zeros. This is an extremely rare event. It is in general believed that there is no way to produce these data otherwise than by engaging in very long and costly computations. This question of feasibility of bitcoin mining and possible improvements is a central question in this paper and we study it later in more details. Is Bitcoin a secure distributed system and in what sense it is secure remains unclear. As far as we can see nobody yet claimed that bitcoin is provably secure as we understand it in cryptography with a formal definition and a security proof. On the contrary, bitcoin clearly isn’t a state of the art cryptographic system , see [4]. It is a practical system with many potential shortcomings. In this respect it has been a tremendous success and it has no serious competitor at the present moment. For the time being we need to assume that the security of bitcoin payments is based on the shared belief that there is no way to hack the bitcoin system in any substantial way. Officially bitcoin is experimental, it does not claim to be secure. In fact the security of the bitcoin protocol and software has already been broken once . On 15 August 2010 somebody has created an unbelievably high quantity of 184 billion of bitcoins worth literally trillions of dollars out of nothing and made the distributed system accept it, see [10]. The protocol system and software have been patched immediately and bitcoin protocol is now at version 2. All bitcoin adopters worldwide had to agree to discard this strange attribution of money. The only way to recover from this sort of error is by consensus. There were also major cyber attacks with concrete exploits against bitcoin software and systems, see [10]. In just once such incident 17000 BTC were lost (or maybe stolen) which is worth millions of dollars. These embarrassing incidents are not very widely publicized. Moreover there are some non-technical reasons to be very cautious with bitcoin. Quite interestingly the creator of the system [41] was apparently a pseudonym and seems to have disappeared. As far as we can see no serious academic cryptologist has publicly expressed their faith in bitcoins and their security. On the contrary, the cryptographic community, as well as the software engineering community, are full of highly capable code breakers able to find new attacks and exploits on secure systems such as bitcoin every day. A major reference in this area is a paper published at Financial Cryptography 2012 [4]. This paper clearly explains that hundreds of academic papers have been published to improve the efficiency and security of e-cash constructions . At the same time the authors explain that bitcoin is a rather simple system which uses no fancy cryptography, and is by no means perfect . Then they analyse the security of the bitcoin system from numerous angles and consider many interesting attacks, see [4]. In this paper we look mostly at the questions of how bitcoin works and how exactly bitcoin mining works. We try to see if it is possible to improve this process to be more efficient. Later we will look at what are the consequences of what we have learned. The goal of the miner is to solve a certain cryptographic puzzle which we will later call a CISO Hash Problem . The solution will be called a CISO block . Great majority of miners ignore what exactly they are doing, they are running either open source software or have purchased some hardware to do mining very efficiently. However miners must know that the operation is very timely and that they need to be permanently connected to the network. The solutions to these puzzles are linked to each other and form a unique chain of solutions. This is usually called the block chain . The whole block chain is published on the Internet. The whole of it can for example be consulted at . All new blocks which are found need to be broadcast to all network participants as soon as possible. The miners need to be very reactive and they do it because it is in their interest (note: a very recent paper proposes another strategy [28]). They need to listen to broadcasts in order to receive the data about recent transactions which they are expected to approve. Then they need need to broadcast any solution (a CISO block) which they have found as soon as they found it, because their solution is likely to be part of the ”main chain of blocks” only if it is widely known. Once the solution is known it ”discourages” other miners from searching for the same block. Instead they can concentrate on searching for the next block which will confirm the present block and will make the miner be able to claim hist a reward for producing this CISO block. Our goal is to clarify how this system works. In the present section we consider a static computational problem which needs to be solved. In Section 7 we will further explain the dynamics of bitcoin production in the long run: how this problem changes with time in a predetermined way. The problem of bitcoin mining is very closely related to well known problems in cryptography. One crucial question is as follows: how does the bitcoin mining differ from traditional questions in cryptanalysis of block ciphers and hash functions and is there a more efficient way to mine bitcoins. First we are going to briefly describe the problem as a static computation problem about a certain block cipher. Then we are going to look at how the problem evolves in time and how solutions to the CISO problem are converted to shares in the bitcoin currency. Finally we are going to study what the possible solutions and optimizations are. New bitcoins can be created if the miner can hash some data from the bitcoin network together with a 32-bit random nonce, and obtain a number on 256 bits which starts with a certain number of zeros. We call this problem CISO: C onstrained I nput S mall O utput. This can be seen as a special case of a problem which is sometimes called CICO which means C onstrained I nputs C onstrained O utputs problem. This ter- minology have been introduced recently in the study of the most recently stan- dardized U.S. government standard hash function SHA-3 a.k.a. Keccak. SHA-3 is the latest has function in the SHA family and a successor to SHA-256 used in bitcoin [2]. It is possible to claim that this means that SHA-256 of Bitcoin is considered by the United States NIST and a broader cryptographic engineering community as NOT sufficiently secure for long term security. This sort of CISO/CICO problems are not new, they are very frequently studied in cryptanalysis of hash functions since ever, and endless variants of these problems exist for specific hash functions, some examples can be found in [2, 24, 40]. The exact details of the specific Constrained Input Small Output (CISO) problem which we have in bitcoin are described below. It can be obtained by the inspection of the bitcoin source code, see [6, 7]. Both code for bitcode mining and for the whole bitcoin network is open and therefore the process is relatively transparent. On Fig. 2 we show the cryptographic computation which is executed many many times by bitcoin miners. This picture emphasizes the internal structure inside SHA-256 hash function. The inputs and contraints on these inputs are explained in details in Section 6.5 below. SHA-256 is a hash function built from a block cipher following the so called Davies-Meyer construction. The principle of the Davies-Meyer construction is that the input value is at the end added to the output and that it transforms an encryption algorithm into a “hashing” algorithm, a building piece of a standard hash function. The underlying block cipher has 64 rounds and thus a 2048-bit expanded internal key (64x32 bits). This key is obtained from the message block to be compressed, which has 512 bits at the input and is expanded four times to form this 2048-bit internal key for our block cipher. In one sense on Fig. 2 we convert the problem of bitcoin mining or of solving CISO hash puzzles, to a specific problem with three distinct applications of the block cipher which underlies SHA-256 connected together to form certain circuit. More details about these inner workings of SHA-256 as it is used in Bitcoin mining will be given in Section 10. The goal of CISO hashing is to produce solutions which are correctly formed in the sense that they satisfy all the required conditions and constraints, which we are going to explain in details in Section 6.5. The miner is trying to find a solution to the CISO problem such that

...The promise of multiple benefits such as quick and cheap transactions provided through the Bitcoin cryptocurrency attracts financial institutions and individual merchants worldwide (Mullan, 2014;Brito, 2013). Their attraction can further be motivated through higher robustness against interference compared to conventional payment providers who may prevent a transaction due to political, security or other reasons (Hill, 2013), ongoing optimizations (Courtois et al., 2013), investment opportunities (Donnelly, 2015), etc. Ari Juels, the co-director of the Initiative for CryptoCurrencies and Contracts (IC3), claims that Bitcoin will lose its independent structure and become centralized in the future (Extance, 2015).Morphy (2014)argues that in order to use Bitcoin on a daily basis and to stay in compliance with tax regulations, users would have to increase paper work, which could be a strong barrier for system implementation.Glaser et al. (2014)claim that currently users adopt Bitcoin as a speculative investment vehicle rather than an alternative transaction system. On the other hand, these investments could have been done based on the belief that Bitcoin will be widely adopted in the future and increase in its value. ...

...Although the author considered the most energy and cost efficient machines in the market, he highlighted a difference of four orders of magnitude between the Bitcoin and Nxt system, highlighting hence a much higher efficiency of the system using PoS than that using PoW. Results similar to those by Czarnek for the Bitcoin system emerge also from other works, such as that by[25], who simulate an artificial Bitcoin market, and that by[37], who wrote: " In April 2013 it was estimated that Bitcoin miners already used about 982 Megawatt hours every day. At that time the hash rate was about 60 Tera Hash/s. ...

...Bitcoin counters the sybil attacks by making use of PoW in which to verify a transaction, the miners has to perform some sort of computational task to prove that they are not virtual entities. The PoW consists of a complex cryptographic math puzzle[18], and it imposes a high level of computational cost on the transaction verification process, thus the verification will be dependent on the computing power of a miner, instead on the number of (possibly virtual) identities. The main idea is that it is much harder to fake the computing resources in the Bitcoin network than it is to perform a sybil attack.In practical, the miners do not verify individual transactions, instead they collect pending transactions to form a block. ...

...As soon as new transactions are notified to the network, miners check their validity and authenticity and collect them in a block. Then, they take the information contained in the block of the transactions, which include a variable number called " nonce " and run the SHA- 256 hashing algorithm on this block, turning the initial information into a sequence of 256 bits, known as Hash [18]. There is no way of knowing how this sequence will look before calculating it, and the introduction of a minor change in the initial data causes a drastic change in the resulting Hash. ...

...Bitcoin's price has stabilised somewhat in the last year, but it still can suffer swings of up to US$20 in price. This makes it too unstable and seems to be keeping away investors, making it an unreliable means of payment [82]. Price instability could be part of the decentralised nature of the technology. ...

...Later we are going to see that this attack also gets worse with time due to the build-in monetary policy in bitcoin and that there will be sudden transitions because the monetary policy mandates sudden jumps in the miner reward (cf. also Part 3 in [5]). ...