BUIP015: Decentralize mining with the FAIR PoW algorithm and an user-configurable PoW setting Proposer: Simon Liu Submitted: 2016-01-19 Status: draft Revision: 2 (2016-05-11)
Summary
Add a configuration option so users can choose from a predefined selection of proof-of-work schemes. Introduce FAIR, a proof-of-work scheme featuring network sensitive memory hardness and pseudo-random code paths to reduce the effectiveness of parallel processing with dedicated mining hardware. Upon deployment of FAIR, it should once again become feasible to mine successfully on a personal computer, thereby providing an incentive for individuals to run a fully validating node and help maintain distributed consensus.
Background
Bitcoin's proof-of-work scheme is a puzzle derived from Hashcash and uses double SHA256 as its work function. Miners compete to package transactions into blocks and submit them to the network after solving a puzzle. A miner is compensated if their block is accepted into the blockchain. Mining successfully on a home computer was once feasible, but now impossible in the face of industrial mining farms packed with ASICs.[1][2][3]
As of January 2016, four mining entities - AntPool, F2Pool, BTCC Pool and BitFury - control almost 80% of the network's hashing power. That is, they mine four out of five blocks. The risks of centralized mining have long been discussed[4][5], as have potential solutions which include the replacement of double SHA256 hashing with a more egalitarian proof-of-work scheme.[6][7] If mining could be decentralized, it would help the network return to Bitcoin's original vision of distributed consensus.
Proposal
Part 1. User-Configuration
Add a configuration option so users can choose from a selection of proof-of-work schemes, including the current SHA256d hash function, and specify when a scheme starts and expires. Version bits could be used to signal intent for deployment of this configuration feature.
For example, the following configuration would tell a node to start mining with NewAlgo from block 500,000 and continue to accept but not mine SHA256d blocks for another 100,000 blocks:
Default, no, 0-600000
NewAlgo, yes, 500000
With the ability to switch proof-of-work schemes, users can influence the lifespan of dedicated mining hardware. Investment proposals for development of new ASICs and large-scale mining will face increased economic risk.[8]
Part 2. FAIR – a some-time memory-bound chained-hashing scheme
(i) FAIR High-Level Design
FAIR will use a chained-hash algorithm to increase design complexity for hardware miners. We have seen with both Bitcoin and Litecoin that a single a proof-of-work scheme involving just a single hash function leaves the network vulnerable to ASIC miners. While it is not feasible to design an ASIC-resistant algorithm, it is possible to increase the costs associated with ASIC chips.
The order of FAIR's chained-hashing will be psuedo-random. For each iteration of the scheme over a given block header, a different code path will be taken. Branch divergence should greatly reduce the effectiveness of SIMD parallel processing achievable with GPU miners.
FAIR will make use of memory-bound functions. Memory is a cheap commodity for home computers but expensive to integrate into an ASIC. By increasing memory requirements, GPU miners will have to reduce the number of blocks and threads that can executed in parallel, as well as run out of fast device memory and be forced to use slower host-mapped memory.
FAIR will use the difficulty of the network to determine the cost parameters for memory-bound functions. The rule-of-thumb will be that as network difficulty increases, so does the amount of memory required. Given that difficulty is essentially random, it will be hard for ASIC designers to calculate the optimal amount of memory to be included in their chips.
Bitcoin's existing PoW puzzle essentially boils down to this:
(SHA256(SHA256(header)) < target
With FAIR, the puzzle could look like any of the following:
(BLAKE2(BLAKE2(header)) < target
(ARGON2(BLAKE2(SKEIN(header)) < target
(SKEIN(SHA3(SHA3(ARGON(SCRYPT(SHA256(BLAKE2(BCRYPT(header)))))))) < target
(ii) FAIR Memory Formula
When FAIR calls a memory-bound algorithm, cost parameters are based on the difficulty of the network. The formula to calculate the memory requirements is as follows:
MEM = 1 KB * HEIGHT * DIFFICULTYRATIO
The HEIGHTRATIO will increase the memory requirements over time at a lower rate than Moore's law, while the DIFFICULTYRATIO will act as a multiplier such that as difficulty rises, so will memory requirements. The ratios are calculated as follows:
MEM = 1024 * (CURRENT HEIGHT/BASELINE HEIGHT) * (CURRENT DIFFICULTY/BASELINE DIFFICULTY)
The baseline values are:
MEM = INT(FLOOR( 1024 * (BLOCKHEIGHT/214563) * ((INT(FLOOR(DIFFICULTY))) / 2979636)))
The baseline is established so that were the formula running on 1 Jan 2013, the memory requirements on that date would have been just 1 KB. The rationale for this is that Bitcoin ASICs were introduced in 2013 and led to a jump in difficulty of almost 400x during the course of the year, compared to an increase of just 2.5x in 2012. From 2013 to 2016, the difficulty increased 34,863x.
To illustrate, let's see the memory cost function in action :
On 1 Jan 2013, block 214563 had a difficulty of 2979636.62, thus the memory requirement would be:
MEM = 1024 * ( 214563 / 214563 ) * (2979636/2979636) = 1 KB
Whereas on 1 Jan 2016, 391182 has a difficulty of 103,880,340,815.46, so required memory is:
MEM = 1024 * (391182 / 214563) * (103880340815 / 2979636) = 66649070382 =~ 63 MB
The implementation will use the difficulty from the previous block to resist a possible denial-of-service attack where an attacker sends a blockwith a fake difficulty setting in order to trick validating nodes into using excessive memory. As a precaution, an upper bound for memory cost could be set, say 128 MB, and linked to the HEIGHTRATIO so that it increases over time.
(iii) FAIR Chained Algorithms
FAIR will consist of R rounds where on each round one of the algorithms listed below is selected. R will be a psuedo-random value between 2 and 8. Each algorithm will consume as input the previous algorithm's output. All algorithms will output 32 bytes (256 bits). If a salt is required, the block headers' Merkle root hash will be used.
Algorithm ID and Name:
0. SHA256
1. ARGON2d
2. BLAKE2
3. Bcrypt
4. SHA3-256
5. Scrypt
6. Skein-1024-256
7. PBKDF2 (with HmacSHA256)
Another candidate is Equihash[9], which has recently been selected as the PoW scheme for Zcash.[10]
If ARGON2d is selected, the parameters will be:
TIME_COST=1
PARALLELISM=1
MEM_COST=max(10, int(floor(log 2 MEM)) – 20)
SALT=MERKLEROOTHASH[0:15]
Where memory usage is 2^MEM_COST KB.
If Bcrypt is selected, the parameters will be:
WORK_FACTOR = 10 + (int(ceil( HEIGHTRATIO )))
If PBKDF2 is selected, the parameters will be:
SALT=MERKLEROOTHASH
ITERATIONS=10000 * (int(ceil( HEIGHTRATIO )))
If Scrypt is selected, the parameters will be:
N = 1024
r = int(floor(log 2 MEM))
p = 1
where memory usage is 128 bytes × N × r x p
FAIR Psuedo Code
Let BLOCKHEADER be the block header being hashed
Let MERKLEROOTHASH be the 32 byte (256 bit) Merkle Root hash of transactions in the block
Let DIFFICULTY be the difficulty setting of the previous block
Let NONCE be an unsigned 4 byte (32 bit) number
Let OUTPUT be a 32 byte (256 bit) buffer to store the output of each round
Function FAIR( BLOCKHEADER ):
Clear OUTPUT
Set MAXROUNDS to 8
Set INDEX to 0
While INDEX is less than MAXROUNDS
Set B to MERKLEROOTHASH[INDEX] xor OUTPUT[INDEX] xor NONCE[INDEX]
Set ID of algorithm to B mod 8
Let ALGO be function representing algorithm of ID
Call ALGO with OUTPUT as input data and any other parameters if applicable
Store result of ALGO in OUTPUT
Increment INDEX by (1 + OUTPUT[0] MOD 3)
Return OUTPUT
Discussion
Algorithm parameters to be fine-tuned for desktop mining.
Other algorithms to consider are Cuckoo Cycle and Balloon hashing.
Seek out implementations optimized for Intel and ARM processors.
Mining pool and botnet resistance could come from adopting psuedo-random access to complete blockchain data but this will increase verification requirements.
References
[1] http://www.ofnumbers.com/2015/11/04/a-few-known-bitcoin-mining-farms/
[2] http://www.spokesman.com/stories/2014/apr/26/northwests-cheap-power-drawing-bitcoin-miners/
[3] http://motherboard.vice.com/read/chinas-biggest-secret-bitcoin-mine
[4] http://hackingdistributed.com/2014/06/13/time-for-a-hard-bitcoin-fork/
[5] https://blog.ethereum.org/2014/06/19/mining/
[6] https://bitcoinfoundation.org/mining-decentralisation-the-low-hanging-fruit/
[7] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-July/006184.html
[8] http://www.businesswire.com/news/ho...ounces-Mass-Production-Fastest-Effective-16nm
[9] https://www.internetsociety.org/sit...f-work-based-generalized-birthday-problem.pdf
[10] https://z.cash/blog/why-equihash.html