Toward quantum mining (1/2)
Many analysis have been made regarding the possible attack vectors that quantum computing can lead to Bitcoin, in particular, the most “promising”, the use of the Shor algorithm to attack the public-key ECDSA cryptography that underlies it.
By “attack” here I mean a deliberate act intended to take possession of Bitcoin that the attacker does not possess, managing to go back to private keys or to rewrite blocks already validated in the Blockchain.
For all these attacks, however, have been imagined solutions to be implemented over time, new functions of public-key cryptography to be adopted or hashing to add to the top of current schemes.
With these two informative article, I will try instead to highlight how this technological evolution has implications regarding “normal” operations, resulting in its adoption as a system singularity point for Bitcoin.
In this first article, I will try to give a full picture of the state of the art so that the reader has all the elements to face the reading of the second one that will adequately deal with Quantum mining.
Theory of Bitcoin mining
Mining is the process of adding new transaction records to Bitcoin’s public ledger of past transactions. In practice, it is a matter of solving a computational problem. The first miner that find the solution will get the reward. To create a race between miners, with the correct economic incentives, the computational problem to be solved must be probabilistic, not deterministic.
Mining creates the equivalent of a competitive lottery that makes it very difficult for anyone to add new blocks to the Blockchain consecutively. The “lottery” protects the neutrality of the network by preventing any individual from gaining the power to block certain transactions. Also prevents any individual from replacing parts of the Blockchain to roll back their spends, which could be used to defraud other users. Mining makes it exponentially more difficult to reverse a past transaction by requiring the rewriting of all blocks that occurred after the target transaction.
The iterative procedure to look for the solution is called “Hashcash proof of work algorithm”. Let’s explain the idea on how it works.
- The miner creates a data structure. It contains two kinds of data, one that remains fixed until the network accepted a new mined block and one that changes at each try to find a solution.
- It then applies to this data structure a one-way function, that is a hash function which is infeasible to invert.
- The result obtained must be less than or equal to a target, in which case the network will accept it so the Blockchain will incorporate transactions and the reward is assigned. Otherwise, the miner will restart the process modifying the changing part of the data structure.
Now we can better analyze each step.
The data structure
The data structure is the header of the candidate block that should be inserted in the Blockchain. It contains many fields, some that we can consider fixed because calculated at the beginning of the iteration, while others change one or all the times during the iteration:
- Version, 4 bytes, Block version number, fixed
- HashPrevBlock, 32 bytes, 256-bit hash of the previous block header, that change every time a new block is confirmed by the network, fixed
- HashMerkleRoot, 32 bytes, 256-bit hash based on all of the transactions in the block that is defined when the miners build the block putting together from mempool transactions to be confirmed by the network, change during the computation every 2³²+1 iterations.
- Time, 4 bytes, the current timestamp as seconds since 1970–01–01T00:00 UTC. A timestamp is accepted as valid if it is higher than the average timestamp of previous 11 blocks and less than the network-adjusted time + 2 hours. “Network-adjusted time” is the average of the timestamps returned by all nodes connected to you. We can consider it fixed in this context as the two hours tolerance is more than the 10-minute average time between blocks.
- Difficulty, 4 bytes, current target in compact format, change when the difficulty is adjusted, fixed.
- Nonce, 4 bytes, a 32-bit number, starts at 0 and increment at every tentative to find the solution, so change at every iteration.
So, 44 bytes are defined at the start of the process, 32 can change one or more time during the computation and the last 4 change accordingly to the increment of the value represented.
The nonce is necessary to obtain different result each time the hashing operation is performed but, as it is small at 32-bits, each time it wraps an ExtraNonce field must be incremented (or otherwise changed) to avoid repeating work.
Bitcoin stores the ExtraNonce field as part of the coinbase transaction, which is stored as the leftmost leaf node in the Merkle tree (the coinbase is the special first transaction in the block). So after 2³² computation, the HashMerkleRoot field have to be recalculated. But, if we assume that after 2³² rounds the data structure is recreated, then 76 of the 80 bytes are fixed and the process is streamlined.
The hash function
A cryptographic hash function is a mathematical algorithm that maps data of arbitrary size (in Bitcoin is the data structure we have presented, also called the block header) to a bit string of a fixed size (the hash).
Bitcoin’s mining function processes block headers with a double round of SHA-256, which is one of the functions of the SHA-2 family, a set of cryptographic hash functions designed by the United States National Security Agency.
The whole family of SHA-2 functions, and therefore also SHA-256, is based on Merkle-Damgård construction, a method of building collision-resistant cryptographic hash functions.
A Bitcoin block header is 80 bytes long and is divided into two chunks of 512 bit (64 bytes) as follows; the second is padded to a length of 64 bytes:
For each chunk an array w[0..63] of 32-bit word is populated, putting the chunk into first 16 words w[0..15] of the array and deriving the next [16–63] elements from the previous ones doing some calculation (using bitwise operation like xor, rightrotate, rightshift and modulo addition). The phase described in this paragraph is called message expander function.
Then the main loop or compressor function is performed, for each element of the w array another set of computation is done (using the aforementioned bitwise operations again on a set of 8 registers A-H), and 8 x 32-bit word is obtained.
The result of the main loop is added iteratively for each chunk computed then finally appended together obtaining a 256-bit value that is the hash of the message submitted to the function. The theoretical analysis of process is available here to be examined by those wishing to go into details.
The hash function is unidirectional because in the process, at each iteration, there is an addition of information but at the same time being the destination space limited to 256-bits there is also the loss of a part of the one inserted previously.
The entire process flows as follows:
The part of the flow that is repeated in the loop and depends on the Nonce is depicted in red in the above diagram. The green part is not repeated in the loop as it depends only on the block header candidate, not on the Nonce. The input of the loop so are:
- Mid-state
- Message
The Mid-state is the output of the green compressor function. The Message is the part of Chunk 2 that depends on the block header candidate. The Message excludes the Nonce (which is selected inside the loop) and the padding (which is constant). In light of this, the following diagram shows the core part of the computation involved in Bitcoin mining, or the Bitcoin mining loop:
The mining loop is the fundamental part that makes up most of the SHA-256 calculation, so it’s the part where an improvement in efficiency will result in an overall gain for the miner.
The target
Mining a block is difficult because the SHA-256 hash of a block’s header must be lower than or equal to the target for the block to be accepted by the network. Let’s simplify it for explanation purposes: the hash of a block must start with a certain number of zeros, so the probability of calculating a hash that starts with many zeros is very low. Therefore many attempts must be made.
The target to be achieved is called Difficulty. The Bitcoin network has an adaptation mechanism to change this value every 2016 mined blocks to keep the average time between each block at ten minutes from each other. The first miner to find a hash lower then the difficulty is rewarded today with 12.5 bitcoins, 212.500 USD at the current (volatile) exchange rate.
The solution of the problem, on which the bitcoin mining is based, is the nonce that will produce a hash less than the difficulty.
Should be noted however that there may not be a solution for a given data structure, so you may be trying to find a nonce for a candidate block which doesn’t have one. I.e., can be that a hash that is less than the difficulty does not exists as well by varying all the 2³² values of the 4-bit part of the Nonce.
To have more probability to be the first to find the solution — assumed that the speed of a single computation is similar — a miner must have greater hashing power than the others.
Technology of Bitcoin mining
The previous assumption about the same speed is valid for most of the time, as all miners use the same technology to mine Bitcoin. In the history of Bitcoin, however, there was already technology discontinuity moment. At the dawn of mining (2009), CPU of computers calculate the hash, but soon this calculation was shifted towards graphics processing units (GPU). In fact, due to their architecture, graphics adapters run cryptographic calculations much faster than CPU. A competing technology of FPGA (Field-programmable gate array) then emerged providing a nearly five fold advantage regarding power consumption as compared to GPU miners.
All these underlining technology changes have anyway not given to a single actor in the mining space any advantage on the others. But back in 2014, when the ASIC (application-specific integrated circuit miners) mining chip hit the market, the Ghash.io pool, who gets on his behind many ASIC miners briefly reached the 51%, potentially enabling Ghash.io to conduct a 51% attack.
From the technology point of view, an ASIC is a silicon wafer designed for the sole purpose to run cryptographic calculations for mining. Their power efficiency is tenfold higher. The impact of having a means for mining which was significantly faster than previously available mining hardware is that it would render current hardware obsolete since the difficulty factor is adjusted by the system to keep solution times on the order of ten minutes.
The problem is that mining has a natural tendency towards vertical integration, which is, those who produce a more efficient device undoubtedly try to use it at the beginning, on their own, exploiting for themselves the competitive advantage that derives from efficiency.
To better make a comparison when we later present the quantum mining, we try to depict the hardware implementation of the mining process inside an ASIC.
There is a general purpose open source implementation of the SHA-256 cryptographic hash function written in VHDL, a hardware description language with which designers can quickly write descriptions of large circuits in a relatively compact and concise form. It separates the expander and the compressor functions. Let’s take a look:
The expander function is implemented as a compact 16-word circular buffer, that is cycled for the 64 clock cycles.
On the left, there is a simplified diagram of the implementation of the expander datapath, with the circular buffer (r0 .. r15) and the combinational functions (σ0, σ1).
The compressor function, the core logic is implemented as a word-shift register with a combinational logic that computes the next state for the word shifter registers.
Here is a simplified depiction of the compressor datapath, with the core registers (a .. h) and the combinational functions (Maj, Ch, ∑0, ∑1).
The whole block is processed in a single clock cycle for each of the 64 cycles of the algorithm.
A well VHDL written circuit can be “synthesized” in a silicon wafer by a compiler that takes your high-level design and generates a “gate-level netlist”. Every element of the two previous schema are called cell, and each cell is composed by a certain number of logical gates. With this, an ASIC designer can do the “ Place and Route” obtaining the final netlist, from which, using an automated layout tool, he can obtain the layout of the chip ready for a “hand-tweak”, manually optimizing any performance-limiting aspect of the design and extracting parasitic layout.
The previous paragraph makes it look easy, but it is not at all, to just go in the surface of this complex industrial process you can find more info here.
To figure out a metric on how many gates are needed for a Bitcoin mining ASIC chip, we can use the fact that all Boolean logical gates can be implemented by using a combination of NAND gates (The only exception is the rightshift and rightrotate that is simply a wiring matter). This property is called functional completeness.
For example, a 32 bit MUX (multiplexer gate) like ones in the left of figure 6 can be decomposed each in 4 NAND gates for a total of 4x32=128 NAND gate. The A-line not pictured in figure 7 is the clock of the chip.
Currently an ASIC chip implements the full figure 4, including the target comparison part of the algorithm.
A design of a bitcoin mining ASIC doing a double SHA-256 can have the complexity of approximately 20000 NAND gates. Not many compared to the millions contained in a modern CPU. In fact, in an ASIC chip to mine Bitcoin the number of cores is much higher, the most recent have 8192 cores. Each NAND gate is synthesized in the silicon wafer using CMOS technology.
The goal of an ASIC manufacturer is to increase the calculated hash in the unit of time (GH/s), while simultaneously minimizing the ratio of energy used and Hash computed (J/GH). In other words, increase revenues, minimizing costs. CMOS technology follows these laws:
- Output Calculated = Frequency * Computation per cycle * Numbers of cores
- Power Consumed = Frequency * Transistor Gate Capacitance * Voltage² + Leakage Current * Voltage
As happens for CPU, a higher frequency achieve faster calculations but creates more consumption. Then ASIC producer tries to reduce the Voltage and the Transistor Gate Capacitance. Means lowering distances, so fewer electrons are needed. Incidentally, this implies also the opportunity to have more cores as the silicon wafer cannot be too big because it must be possible to dissipate all the heat it produces. So after doing all possible optimizations like building optimized logical gates cells, using high-k dielectrics and lowering the resistivity of the metal layers, it’s a matter of miniaturization.
Silicon designers think regarding the “feature size” or “geometry” of design, and this is measured in nanometers (nm). This number describes the smallest sized part used in constructing the transistors or wires within the silicon wafer. As we are reasoning in two dimensions, halving the feature size means getting four times as many things in the same space.
At the start of 2018, we will be at 16 nm, and there is still room for some advancement as look like that for 2020 there will be a 5 nm technology available for CPU. But miniaturization means nonlinear increasing costs in the engineering the chip. If this is the sole problem, we can think that raising Bitcoin prices will suggest that this kind of investment will become affordable. Later promising materials like Graphene, can reduce the power consumption by 75% as in this type of material, in fact, the electrons move at very high speeds.
But at some point, starting at the ~10 nm scale, quantum tunneling becomes a significant phenomenon due to Heisenberg uncertainty principle. Miniaturization becomes more difficult as the simulation and the synthesis of the chip have to keep in account quantum phenomena.
First article conclusion
ASICs to mine Bitcoin still have several years of possible improvements both regarding miniaturization and optimization. Given the high prices and the consequent increase in the reward, some big players in the production of chips like Intel or AMD will likely enter the market. But the growth of hashing power under the same technological paradigm is bound to slow down and become mainly a matter of more hashing devices.
In the long run, however, primarily because of the enormous economic incentive we have talked about, and because of the relative simplicity of ASICs compared for example to the CPUs, it is likely that substantial investments will be made towards new technological paradigms.
In the next article we will examine the hypothesis of quantum mining, the opportunities and dangers that this type of technology would bring to the Bitcoin ecosystem.
