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:
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
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:
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
mod 3]
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