Minim bitcoin with paper and pen
At one point, I wanted to estimate how quickly you can mine the bitcoins manually. It turned out that SHA-256 hashing is used for mining, and it is quite simple and can be calculated even without a computer. Of course, the process is very slow and completely impractical. But, having passed all the steps on a piece of paper, you can well understand the details of the algorithm.
One cryptographic round
A key part of the entire Bitcoin security system is mining. The basic idea is that miners group bitcoin transactions into one block, which is already hashed an innumerable number to find a very rare hash value that is subject to special conditions. When such a value is found, a block is considered to be smiled and falls into a chain of blocks. Hashing itself does not carry any useful purpose other than increasing the difficulty of finding the right block. Thus, this is one of the guarantees that no one alone with any existing set of resources can take control of the entire system. You can read more about mining in my last article .
The cryptographic hash function on an input receives the block with data, and produces a small, but unpredictable, output. It is designed so that there is no quick way to get the desired output, and you must continue to search until you find a suitable value. Bitcoin uses SHA-256 as such a function. Moreover, to enhance the durability of SHA-256 is applied to the unit twice and is already called double SHA-256.
In bitcoin, the criterion of validity of a hash is a sufficient number of zeros at its beginning. [1] Finding such a hash is as difficult as, for example, finding a car or phone number ending in several zeros. But, of course, for hash it is exponentially more difficult. Currently, the correct hash should contain approximately 17 starting zeros, which only 1 of 1.4x10 20 satisfies. If we draw an analogy, then finding such a value is more difficult than finding a specific part among all the sand on Earth .
')
The diagram below shows a typical block in a chain and its hash. Yellow highlighted bytes, which are involved in the hashing process. In this example, the hash is valid and has a sufficient number of zeros at its beginning. However, this is an infrequent case, and usually the miner has to iterate over the value of the nonce field or other data available to change.
Bitcoin block structure
The algorithm works with data divided into pieces of 512 bits (64 bytes), mixes them cryptographically and produces a 256-bit (32 bytes) hash. SHA-256 consists of a relatively simple round, repeated 64 times. From below, just such a round is shown, accepting 8 4-byte words as input - from A to H.
One round SHA-256 for eight input words AH. The scheme is drawn kockmeyer, CC BY-SA 3.0 .
Blue blocks mix bits nonlinearly to complicate cryptographic analysis. Moreover, for even greater reliability, different mixing functions are used (if you can find a mathematical loophole for quickly generating valid hashes, then take control of the entire bitcoin mining process).
The majority function (Ma block) works bit-wise with the words A, B, and C. For each bit position, it returns 0 if most of the input bits in this position are zero, otherwise it returns 1.
The Σ0 block cyclically shifts A by 2 bits, then the source word A is cyclically shifted by 13 bits, and, similarly, by 22 bits. The resulting three shifted versions of A are added up bitwise modulo 2 ( normal xor, (A ror 2) xor (A ror 13) xor (A ror 22) ).
Ch implements the select function. At each bit position, a bit from E is checked, if it is equal to one, then a bit from F from this position is output, otherwise a bit from G. Thus, the bits from F and G are mixed based on the value of E.
Σ1 is similar in structure to Σ0, but works with the word E, and the corresponding shift constants are 6, 11, and 25.
Red blocks perform 32-bit addition, forming new values for the output words A and E. The value of W t is generated based on the input data (this occurs in the segment of the algorithm that receives and processes the hashed data. It is beyond our consideration). K t - its own constant for each round. [2]
On the diagram above, it is noticeable that only A and E change in one cryptographic round. The remaining words do not change, but shift at the output — the old A turns into the output B, the old B turns into the new C, and so on. Although a separate round of the algorithm does not greatly change the data, but after 64 rounds, the input information will be completely encrypted. [3]
In the video, I show how you can go through all the steps described with a pen and paper. I completed the first round of hashing to mine the block. It took me 16 minutes, 45 seconds.
I’ll explain a little bit what's going on: I wrote down the words from A to H in hexadecimal form, and under each one I made the translation into binary form. The result of executing the Ma block is under the word C, and the values of A after the shifts and the output Σ0 itself are located above the line with A. The selection function appears under G, and finally the corresponding shifted versions of E and the value after the Σ1 block go above the line with E. made a addition in the lower right corner, the result of which participates in the calculation of both the new A and the new E (the first three red summation blocks). On the right, I calculated the new value of A, and in the middle is the calculation of the new value of E. All these steps were discussed above and can easily be traced in the diagram.
In addition, the round that is shown in the video, I spent another - the last 64th hashing round for a particular bitcoin block. In the photo, the hash value is highlighted in yellow. The number of zeros confirms that this is a valid bitcoin hash. Note that zeros are located at the end of the hash, and not at the beginning, as I wrote earlier. The reason is that Bitcoin simply turns the bytes received by SHA-256. [four]
The last round of SHA-256, as a result of which a successfully smiled bitcoin block is visible
Each step in SHA-256 looks very simple in digital logic - simple bit operations and 32-bit summations (if you've ever studied circuit technology, then you probably already imagined how it might look in hardware). Therefore, ASIC chips implement SHA-256 very efficiently, placing in parallel hundreds of blocks of execution of SHA-256 rounds. The photo below shows a mining chip that can calculate 2-3 billion hashes per second. On Zeptobars you can look more photos.
A snapshot of a Bitfury ASIC silicon chip that can mine bitcoins at a speed of 2-3 gigabytes per second. Picture with Zeptobars . ( CC BY 3.0 )
In contrast to bitcoin, Litecoin, Dogecoin, and other similar alternative -coin systems use the scrypt hashing algorithm, which initially embodies the complexity of implementation in hardware. This algorithm at runtime stores in memory 1024 different hash values, and already at the output combines them to obtain the final result. Therefore, much more memory and schematics are required to calculate scrypt hashes compared to SHA-256 hashes. The effect of changes in the hashing algorithm is clearly seen when comparing the corresponding hardware for mining - the versions for scrypt (Litecoin and others) are thousands of times slower than the versions for SHA-256 (Bitcoin).
SHA-256 unexpectedly turned out to be so simple that it could even be computed manually (an algorithm on elliptic curves, which is used to sign a bitcoin transaction, would be much more painful, since it contains a bunch of 32-byte multiplications). Calculation of one round of SHA-256 took me 16 minutes, 45 seconds. With such a performance, the hashing of the entire bitcoin block (128 rounds [3] ) will take 1.49 days, that is, we obtain a hashing rate of 0.67 hashes per day (in fact, of course, the process would be accelerated with practice). For comparison, the current generation of bitcoin miners produces several terahshes per second, which is about a quintillnn times faster than me. I think it’s obvious that manual mining of bitcoins is not very practical. [five]
A reader from reddit asked about my energy costs. Since I do not make any serious physical effort, it can be assumed that the metabolic rate will be 1500 calories per day, then we find that manual hashing requires almost 10 megajoules per hash. The typical energy consumption for an iron miner is 1000 Magehashes per Joule. Thus, I am less energy efficient than a specialized piece of iron 10 ^ 16 times (10 quadrillion). Another issue is the cost of energy. A cheap food source is donuts at 23 cents for 200 kilocalories. My electricity costs 15 cents per kilowatt-hour, which is 6.7 times cheaper than donuts. As a result, the cost of energy in terms of hash for me as a miner is 67 quadrillion times higher. Yes-ah, it is clear that I will not grab the luck by the tail of hand mining bitcoins, and this is not taking into account the cost of paper and pens!
1. In fact, it is important not the number of leading zeros in the hash, but the fact that it should be less than a specific value, which depends on the current level of complexity of the system . ↑
2. Quite amusing, where did these constants come from for SHA-256. Since the NSA developed this algorithm and chose constants, how do we know that they did not pick up special values in order to break hashes faster? In order to prevent such speculations, the initial initialization values of the hash are taken as the square roots of the eight first primes (the first 32 bits of the fractional part). And K t is obtained from the cubic roots of the first 64 primes. As you can see, the constants are generated using simple formulas, so you can trust that the NSA did not invent anything tricky (at least with respect to constants). ↑
3. To my regret, SHA-256 works with blocks of 512 bits, and the bitcoin block header is larger. Therefore, a second pass of 64 rounds of hashing is needed. In addition, double bit SHA-256 is used in bitcoin. Thus, hashing one block requires 192 rounds. However, we can reduce this number, because the mining process consists of re-hashing the same block, with slight changes to the nonce field in the second half of the block. And here there is an optimization due to the fact that we can use the result of calculating the first 512 bits of the block again. As a result, we only need 128 rounds of hashing. ↑
4. Of course, I'm not so incredibly lucky that I immediately found a valid hash. I started hashing a block that was previously smiled. Specifically, the one that was already mentioned in the article - # 286819 . ↑
5. Another problem with manual mining is that new blocks are mined approximately every 10 minutes, so even if I successfully mine a block, it will be hopelessly outdated (orphaned, in terms of Bitcoin). ↑
One cryptographic round
Mining
A key part of the entire Bitcoin security system is mining. The basic idea is that miners group bitcoin transactions into one block, which is already hashed an innumerable number to find a very rare hash value that is subject to special conditions. When such a value is found, a block is considered to be smiled and falls into a chain of blocks. Hashing itself does not carry any useful purpose other than increasing the difficulty of finding the right block. Thus, this is one of the guarantees that no one alone with any existing set of resources can take control of the entire system. You can read more about mining in my last article .
The cryptographic hash function on an input receives the block with data, and produces a small, but unpredictable, output. It is designed so that there is no quick way to get the desired output, and you must continue to search until you find a suitable value. Bitcoin uses SHA-256 as such a function. Moreover, to enhance the durability of SHA-256 is applied to the unit twice and is already called double SHA-256.
In bitcoin, the criterion of validity of a hash is a sufficient number of zeros at its beginning. [1] Finding such a hash is as difficult as, for example, finding a car or phone number ending in several zeros. But, of course, for hash it is exponentially more difficult. Currently, the correct hash should contain approximately 17 starting zeros, which only 1 of 1.4x10 20 satisfies. If we draw an analogy, then finding such a value is more difficult than finding a specific part among all the sand on Earth .
')
The diagram below shows a typical block in a chain and its hash. Yellow highlighted bytes, which are involved in the hashing process. In this example, the hash is valid and has a sufficient number of zeros at its beginning. However, this is an infrequent case, and usually the miner has to iterate over the value of the nonce field or other data available to change.
Bitcoin block structure
SHA-256
The algorithm works with data divided into pieces of 512 bits (64 bytes), mixes them cryptographically and produces a 256-bit (32 bytes) hash. SHA-256 consists of a relatively simple round, repeated 64 times. From below, just such a round is shown, accepting 8 4-byte words as input - from A to H.
One round SHA-256 for eight input words AH. The scheme is drawn kockmeyer, CC BY-SA 3.0 .
Blue blocks mix bits nonlinearly to complicate cryptographic analysis. Moreover, for even greater reliability, different mixing functions are used (if you can find a mathematical loophole for quickly generating valid hashes, then take control of the entire bitcoin mining process).
The majority function (Ma block) works bit-wise with the words A, B, and C. For each bit position, it returns 0 if most of the input bits in this position are zero, otherwise it returns 1.
The Σ0 block cyclically shifts A by 2 bits, then the source word A is cyclically shifted by 13 bits, and, similarly, by 22 bits. The resulting three shifted versions of A are added up bitwise modulo 2 ( normal xor, (A ror 2) xor (A ror 13) xor (A ror 22) ).
Ch implements the select function. At each bit position, a bit from E is checked, if it is equal to one, then a bit from F from this position is output, otherwise a bit from G. Thus, the bits from F and G are mixed based on the value of E.
Σ1 is similar in structure to Σ0, but works with the word E, and the corresponding shift constants are 6, 11, and 25.
Red blocks perform 32-bit addition, forming new values for the output words A and E. The value of W t is generated based on the input data (this occurs in the segment of the algorithm that receives and processes the hashed data. It is beyond our consideration). K t - its own constant for each round. [2]
On the diagram above, it is noticeable that only A and E change in one cryptographic round. The remaining words do not change, but shift at the output — the old A turns into the output B, the old B turns into the new C, and so on. Although a separate round of the algorithm does not greatly change the data, but after 64 rounds, the input information will be completely encrypted. [3]
Minim by hand
In the video, I show how you can go through all the steps described with a pen and paper. I completed the first round of hashing to mine the block. It took me 16 minutes, 45 seconds.
I’ll explain a little bit what's going on: I wrote down the words from A to H in hexadecimal form, and under each one I made the translation into binary form. The result of executing the Ma block is under the word C, and the values of A after the shifts and the output Σ0 itself are located above the line with A. The selection function appears under G, and finally the corresponding shifted versions of E and the value after the Σ1 block go above the line with E. made a addition in the lower right corner, the result of which participates in the calculation of both the new A and the new E (the first three red summation blocks). On the right, I calculated the new value of A, and in the middle is the calculation of the new value of E. All these steps were discussed above and can easily be traced in the diagram.
In addition, the round that is shown in the video, I spent another - the last 64th hashing round for a particular bitcoin block. In the photo, the hash value is highlighted in yellow. The number of zeros confirms that this is a valid bitcoin hash. Note that zeros are located at the end of the hash, and not at the beginning, as I wrote earlier. The reason is that Bitcoin simply turns the bytes received by SHA-256. [four]
The last round of SHA-256, as a result of which a successfully smiled bitcoin block is visible
What does all this mean for the design of "iron" miners?
Each step in SHA-256 looks very simple in digital logic - simple bit operations and 32-bit summations (if you've ever studied circuit technology, then you probably already imagined how it might look in hardware). Therefore, ASIC chips implement SHA-256 very efficiently, placing in parallel hundreds of blocks of execution of SHA-256 rounds. The photo below shows a mining chip that can calculate 2-3 billion hashes per second. On Zeptobars you can look more photos.
A snapshot of a Bitfury ASIC silicon chip that can mine bitcoins at a speed of 2-3 gigabytes per second. Picture with Zeptobars . ( CC BY 3.0 )
In contrast to bitcoin, Litecoin, Dogecoin, and other similar alternative -coin systems use the scrypt hashing algorithm, which initially embodies the complexity of implementation in hardware. This algorithm at runtime stores in memory 1024 different hash values, and already at the output combines them to obtain the final result. Therefore, much more memory and schematics are required to calculate scrypt hashes compared to SHA-256 hashes. The effect of changes in the hashing algorithm is clearly seen when comparing the corresponding hardware for mining - the versions for scrypt (Litecoin and others) are thousands of times slower than the versions for SHA-256 (Bitcoin).
Conclusion
SHA-256 unexpectedly turned out to be so simple that it could even be computed manually (an algorithm on elliptic curves, which is used to sign a bitcoin transaction, would be much more painful, since it contains a bunch of 32-byte multiplications). Calculation of one round of SHA-256 took me 16 minutes, 45 seconds. With such a performance, the hashing of the entire bitcoin block (128 rounds [3] ) will take 1.49 days, that is, we obtain a hashing rate of 0.67 hashes per day (in fact, of course, the process would be accelerated with practice). For comparison, the current generation of bitcoin miners produces several terahshes per second, which is about a quintillnn times faster than me. I think it’s obvious that manual mining of bitcoins is not very practical. [five]
A reader from reddit asked about my energy costs. Since I do not make any serious physical effort, it can be assumed that the metabolic rate will be 1500 calories per day, then we find that manual hashing requires almost 10 megajoules per hash. The typical energy consumption for an iron miner is 1000 Magehashes per Joule. Thus, I am less energy efficient than a specialized piece of iron 10 ^ 16 times (10 quadrillion). Another issue is the cost of energy. A cheap food source is donuts at 23 cents for 200 kilocalories. My electricity costs 15 cents per kilowatt-hour, which is 6.7 times cheaper than donuts. As a result, the cost of energy in terms of hash for me as a miner is 67 quadrillion times higher. Yes-ah, it is clear that I will not grab the luck by the tail of hand mining bitcoins, and this is not taking into account the cost of paper and pens!
Notes and links
1. In fact, it is important not the number of leading zeros in the hash, but the fact that it should be less than a specific value, which depends on the current level of complexity of the system . ↑
2. Quite amusing, where did these constants come from for SHA-256. Since the NSA developed this algorithm and chose constants, how do we know that they did not pick up special values in order to break hashes faster? In order to prevent such speculations, the initial initialization values of the hash are taken as the square roots of the eight first primes (the first 32 bits of the fractional part). And K t is obtained from the cubic roots of the first 64 primes. As you can see, the constants are generated using simple formulas, so you can trust that the NSA did not invent anything tricky (at least with respect to constants). ↑
3. To my regret, SHA-256 works with blocks of 512 bits, and the bitcoin block header is larger. Therefore, a second pass of 64 rounds of hashing is needed. In addition, double bit SHA-256 is used in bitcoin. Thus, hashing one block requires 192 rounds. However, we can reduce this number, because the mining process consists of re-hashing the same block, with slight changes to the nonce field in the second half of the block. And here there is an optimization due to the fact that we can use the result of calculating the first 512 bits of the block again. As a result, we only need 128 rounds of hashing. ↑
4. Of course, I'm not so incredibly lucky that I immediately found a valid hash. I started hashing a block that was previously smiled. Specifically, the one that was already mentioned in the article - # 286819 . ↑
5. Another problem with manual mining is that new blocks are mined approximately every 10 minutes, so even if I successfully mine a block, it will be hopelessly outdated (orphaned, in terms of Bitcoin). ↑
Source: https://habr.com/ru/post/258181/
All Articles