Lucky Errors Found in Bitcoin
Source: Rakesh Kumar
Bitcoin mining is a search for the nonce value that results in a double SHA-256 hash value less than a given threshold.
We found bitcoin mining is inherently tolerant to faults in the mining ASIC that can be exploited to maximize profits by up to 30% -- techniques that could be useful to any application of approximate computing.
First some background for the novice: Bitcoin is the most popular crypto-currency today with a market capitalization of over $6.3 billion. Bitcoin transactions are recorded in a public ledger called a blockchain. All new transactions are checked against existing history to ensure validity of new transactions. Transaction verification and blockchain updates are performed by so-called miners. Miners are rewarded with some new bitcoins for every block of transactions that they add to the blockchain.
Bitcoin mining involves searching for a cryptographic nonce value (a sequence of bits) within a block of transactions such that the hash of the block is less than a threshold. Each miner attempts to find a valid nonce earlier than other miners so that the bitcoin reward for the block can be claimed.
As can be imagined, the higher the hash rate the higher is the probability of winning the reward for a block. However, the higher the hash rate the more the power consumption of mining. A miner has to be energy efficient in order to make profits.
The only profitable way to mine today is by implementing the mining process as an ASIC. Programmable platforms, including microprocessors and GPUs are too energy inefficient to yield mining profits today. As the difficulty of mining increases with time, mining ASIC energy efficiency needs to improve in order to keep mining profitable.
We observe that bitcoin mining is inherently tolerant to faults in the mining ASIC.
Inherent tolerance of mining can be attributed to two reasons. First, mining is an embarrassingly parallel application since hashes can be generated for multiple nonces completely in parallel. A hardware fault affecting one hash does not propagate to other hashes.
Second, a hardware fault leads to two kinds of errors. The miner may declare a nonce to be valid even when it was not (false positive) or it may declare a nonce to be invalid even when it was valid (false negative). The probability of a false positive is minuscule since a valid nonce can be found in a bitcoin network only once every ten minutes. Besides, all blocks are verified locally and by multiple nodes before being appended to the blockchain . So, a false positive is immediately detected and the corresponding block is discarded. False negatives lead to a miner not earning a reward. So, only profits are affected.
The inherent error tolerance of bitcoin mining can be exploited to maximize profits.
First, mining circuits can be replaced by their approximate versions that have lower delay, power, or area (functional approximation). This allows a higher hash rate for the same energy budget.
For example, bitcoin mining ASICs implement SHA-256-based hashing whose delay is dictated by adders in the circuit. We estimate that mining profits can increase over 15% by replacing conventional adders in SHA-256 circuits with approximate adders that have lower delay and area, but produce incorrect results for certain inputs.
Second, profits can be increased by reducing the PVT guardbands on the design. This allows operation at a reduced voltage or higher frequency resulting in more hashes in the same energy budget. In fact, we found that mining circuits can be run at some negative slack and still improve profits in spite of increased number of errors. This operational approximation increases profits by an additional 15%, for a total increase in profit exceeding 30%.
There are other significant opportunities to improve the energy efficiency of mining chips. Near threshold computing may allow an increase in profits by reducing mining costs without proportionally affecting hash rates. Adaptive power management schemes may allow adaptation to bitcoin exchange rate, mining difficulty, and electricity costs. Non-CMOS technologies, including ones with probabilistic behavior, may allow reduced power and increased compute density while exploiting error tolerance.
Mining profits are critical to survival of bitcoins since no blocks will be added to the blockchain without mining. Chip and circuit designers interested in the success of crypto-currencies such as bitcoin should try these techniques to maximize profits. But ultimately these techniques that could be useful to other application of approximate computing such as video processing.
--Rakesh Kumar is an Associate Professor in the Electrical and Computer Engineering department at the University of Illinois at Urbana-Champaign. His paper, co-authored by Matthew Vilim and Henry Duwe will be presented at DAC in June.
| }
|