BUIP015 - Decentralize mining with the FAIR PoW algorithm and an user-configurable PoW setting

bitcartel

Member
Nov 19, 2015
95
93
Status: DRAFT (call for input and discussion)
Proposer: Simon Liu
Revision: 2 (11 May 2016)
Submitted on: 19 Jan 2016

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 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/home/20151216005453/en/BitFury-Announces-Mass-Production-Fastest-Effective-16nm
[9] https://www.internetsociety.org/sites/default/files/blogs-media/equihash-asymmetric-proof-of-work-based-generalized-birthday-problem.pdf
[10] https://z.cash/blog/why-equihash.html
 
Last edited:

Zangelbert Bingledack

Well-Known Member
Aug 29, 2015
1,485
5,585
What of the argument that this just gives power to botnets, and that ASICs getting commodified solves the problem finally (changing algo forces us back through the danger period where the tech is being developed and ramping up very quickly)?

Someone on reddit today suggested a hybrid where say every tenth block would require SHA3 hashing, which if it works seems like it could be a way to adjust the mix between these two extremes as needed. That would create more urgency for a BUIP like this so that the community could adjust these settings independently of their choice of dev team.
 
  • Like
Reactions: VeritasSapere

solex

Moderator
Staff member
Aug 22, 2015
1,558
4,694
Personally speaking, I strongly oppose any change to the hashing algorithm as this is fixing something that is not broken. Mining may not be perfect, but it is working fine for Bitcoin right now. Mining decentralisation is steadily improving as ASIC tech plateaus.

This also plays into the Blockstream smokescreen puffed out by Luke-Jr where linkage of a change of PoW with a block limit hard-fork is simply intended to kill momentum for the block limit increase and leave Bitcoin with a BS-Core ethos future.

Edit: thoughtful BUIPs are always welcome, and it is up to the membership vote to determine the traction they get.
 
Last edited:

bitcartel

Member
Nov 19, 2015
95
93
@Zangelbert Bingledack Yep, Unlimited is about letting users make their own decisions (and thus the consensus they want to be part of) so at the very least a configuration option for the PoW scheme would be a good feature to have.

With the proposal above, you will see it is designed to increase the economic cost of ASIC development and reduce the efficiency of such designs. As difficulty increases, so do memory requirements which have a much larger impact on ASICs than normal home computers. Branch divergence and psuedo random code paths make it harder to efficiently schedule work for parallel processing, including GPUs.

Botnets vs ASICs? Good discussion to have. Two thoughts for you. Firstly, ASIC miners have a real human being who is able to publicly influence developers. Botnet operators in the meantime try to remain under the radar. Second, miners exist for one reason only, whereas Botnets are fluid in nature and the activity of mining competes with other perhaps more profitable Botnet activities.
[doublepost=1453256734][/doublepost]@solex @Peter Tschipper I think many people would argue that mining isn't working as a simple choice of hash function has resulted in mining centralization such that key developers have to lobby miners. It's certainly a discussion we should not be afraid to have, and importantly, in good faith unlike a recent pull request to Bitcoin Classic!
 

greatwolf

New Member
Jan 19, 2016
8
4
California
Another PoW I would suggest adding to the list is cryptonite used in monero and other cryptonote coins. It uses AES primitives as a building block for memory hardness so it can take advantage of the AES instructions present on modern intel chips. In some ways, this is like a commodified ASIC on widely available processors.

Also, are there any PoW algorithms out there that's memory-hard to find but memory-easy to verify? Vitalik blogged about this problem before where many memory-hard PoW's, like scrypt, ends up needing just as much memory to verify. For PoW, this is one area where you want to maximize this asymmetry as much as possible.
[doublepost=1453258786,1453257946][/doublepost]
I'm in agreement with @solex it's a thoughtful idea but I don't think this will be workable. Mining centralization has more to do with local electricity costs than anything else.
I disagree with this sentiment. Yeah electricity cost is certainly an important factor but so is accessibility to mining hardware itself.

The only way I can see Bitcoin's mining decentralization improving is to either 1. commodify ASIC hardware so anyone can get one easily or 2. change the PoW mining algorithm to something that's ASIC resistant.

And by ASIC resistant I mean that the performance gain from a pure hardware implementation isn't exponential when compared to general computing devices.
 

YarkoL

Active Member
Dec 18, 2015
176
258
Tuusula
yarkol.github.io
greatwolf said:
The only way I can see Bitcoin's mining decentralization improving is to either 1. commodify ASIC hardware so anyone can get one easily or 2. change the PoW mining algorithm to something that's ASIC resistant.

And by ASIC resistant I mean that the performance gain from a pure hardware implementation isn't exponential when compared to general computing devices.
Correct me if I'm wrong, but isn't it always possible to get an exponential performance gain using specialized circuitry, so that the real barriers are costs of R&D and manufacture?

I think that the points 1. and 2. above are mutually exclusive, and that point 1 (mass commodification) is the only hope of re-decentralizing the mining power. Point 2 (asic-"resistance") is detrimental to point 1,
since more harder you make the algorithm for ASICS, the more expensive it is to make such ASICS if it becomes profitable, and hence they cannot be mass-produced.

So if an algo change were really needed, it would be best to be as ASIC-friendly possible, so there is at least a prospect of wide-spread deployment of ASICs to consumers at some point.
 
I would support adding it as a configurable option with a consensus mechanism similar to BU's block size limit if some users want it and if somebody is willing to write the patch.

I don't personally support changing the PoW algorithm anytime soon, but the point of BU is to let the users reach their own consensus rather than to attempt to force our own interpretation of consensus onto the users. Some significant warning messages should be added for configurations with a risk of diverging from consensus, though. We don't want anyone to tinker with the consensus configurations without realizing that it could fork them off of the network.
 

Lee Adams

Member
Dec 23, 2015
89
74
I really think BU should be kept as simple as possible, until such time as BU has mass adoption. Otherwise it will never get mass adoption.

Trying to include too many features before BU is actually 'sold' will make any marketing much harder. BU was born out of the block size problem, let's concentrate on that problem before trying to solve the world.

I would also like to get some clarity on how the client's POW setting is advertised to the network. What is the incentive for miners/nodes to change these rules?
[doublepost=1453328479][/doublepost]Finally, just some food for thought, please do not mistake it from the normal r/bitcoin FUD...

...if the POW is made to be easily changed, what's to stop the coin release schedule from being easily changed... or is that the next BUIP being written? :eek:
 
  • Like
Reactions: YarkoL and solex
...if the POW is made to be easily changed, what's to stop the coin release schedule from being easily changed... or is that the next BUIP being written?
If consensus is reached that the supply schedule should be changed, who are you to say no?

The supply schedule is one of the most critical elements of Bitcoin, and I have no intention of ever following a chain that changes it. In the highly unlikely event that consensus on the issue does shift, the client would be prepared. Rather than requiring another software fork like we're at l seeing from Core, users could switch the configuration.

Making it easier to adapt to a consensus change shouldn't have any impact on what the consensus is.
 

bitcartel

Member
Nov 19, 2015
95
93
@Lee Adams The supply schedule would change the economics of the system, so no, i would not advocate changing that (although as @trevinhoffman says, you couldn't stop it if that's what people want ) whereas the underlying hash function as part of the proof-of-work is an implementation detail. It just happens that the original hash function chosen, SHA256, results in centralization which is at odds with Bitcoin's vision.

As for advertising the PoW config, it should use the same mechanism as other settings, which I currently believe is meant to be the user-agent string.
[doublepost=1453333808][/doublepost]@YarkoL Yes, there's a school of thought that ASIC commodization will be the great leveler, but what it would mean is that ordinary users have no chance of mining successfully unless they purchase a piece of equipment to do so. It's great a recurring revenue stream if you happen to be an ASIC manufacturer... picks and shovels :)

With mining tuned to general purpose computers, the entry barrier is lowered so that anybody can start organizing commodity hardware into clusters or server farms to mine. They don't have to spend money buying special hardware to get started. If hundreds of small scale miners end up controlling the majority of the hashing power, that's a win. The objective is to decentralize mining from what it is now, with 80% hashing power held by just 4 entities. Who knows, perhaps the combined power of tens of millions of solo miners will end up with the majority?
 

bitcartel

Member
Nov 19, 2015
95
93
A decentralized mining pool like P2Pool would be preferable over centralized mining pools which, as we can see today, can exert pressure on the system e.g. requiring 95% consensus.

Btw, @Peter Tschipper @solex If ever there was a canary in the coal-mine, so to speak ;-)

Bitcoin is not an electronic payments system like PayPal… Bitcoin is not and should not be free… Mass rule is not appropriate for Bitcoin… The pipe dream of some in the Bitcoin community is to govern the system by having ordinary users vote for changes by adopting the corresponding full node software. This approach is not only impractical, it is also not desirable.
-- BitFury https://medium.com/@BitFuryGroup/keep-calm-and-bitcoin-on-4f29d581276
 

solex

Moderator
Staff member
Aug 22, 2015
1,558
4,694
@bitcartel
Interesting article. There is a subtext to it. BitFury have invested millions of dollars into Bitcoin. For them this is big business, so they feel Mike Hearn's ragequit "Bitcoin has failed" like a punch to the solar plexus. Then they read Luke Jr's change of PoW proposal and this is like a karate kick to the gonads.

No wonder that article was so defensive.

I see Pieter Wuille's response to Luke as a rebuke:
  • <Luke-Jr> if the miners attempt to hardfork, against the consensus of the community/economy, the the community/economy may very well change PoW to overrule the miners' defection/betrayal*
  • <sipa> Luke-Jr: they may, but it's ridiculous to propose that at this point, sorry
  • <Luke-Jr> if there is a real consensus (not just miners) for a hardfork, then we don't have that situation and it can proceed safely
  • <sipa> i would strongly oppose merging it in bitcoin core, on the grounds that it would require an extremely high degree of consensus, and i do not see that hapoening
  • <sipa> Luke-Jr: yes, i understand, but it sends the completely wrong message imho
  • <sipa> the incentive is to maintain a single chain, and changing pow would be very damaging for that
  • <sipa> if mining would become completely centralized, the rest of the ecosystem should have a reason to *together switch PoW
  • <sipa> as mining is an expensive choice for the ecosystem, and its only purpose is avoiding central control and censorship;; in a highly centralized mining ecosystem, you get the coss without the benefits
  • <sipa> however, i think that it is clear right now that switching PoW would be way harder to get consensus on than other things thay are being debated
  • <sipa> so do not worry, i have no intention of merging such a thing*
So, basically, any change to PoW would first need a serious driver like SHA256 being compromised.
 
Last edited:
  • Like
Reactions: Peter Tschipper

YarkoL

Active Member
Dec 18, 2015
176
258
Tuusula
yarkol.github.io
With mining tuned to general purpose computers, the entry barrier is lowered so that anybody can start organizing commodity hardware into clusters or server farms to mine. They don't have to spend money buying special hardware to get started. If hundreds of small scale miners end up controlling the majority of the hashing power, that's a win. The objective is to decentralize mining from what it is now, with 80% hashing power held by just 4 entities. Who knows, perhaps the combined power of tens of millions of solo miners will end up with the majority?
I symphatize greatly with this vision... but I have great doubts of its long-term prospects.
When you have just began with a cpu/gpu-friendly algo, the network is very vulnerable to botnets.
Then either hashing becomes profitable enough to incentivize switching to ASICs or the coin stays at insecure low-price level like hundreds of alts do. Unless someone can prove that there exists an algorithm that is truly ASIC-resistant, I maintain that ASICs appearing are indication of coin's success.

I see no problem with picks and shovels being handed to ordinary people... it's economic growth, although I'm all for recycling old junk too (you ought to see some of the gear I work with :p)

In any case, WRT to proposal, IMHO we should tread lightly when touching consensus values, and
some things were set in stone when Satoshi mined his genesis block. I believe we can find a market-like discovery process to certain variables, like max block size, but it is not a trivial undertaking. I'd say that altering a consensus value is practical if it is numerical and is known to have been changed at least one time since the inception of the cryptocurrency. Block size fits the criteria, and checkpoints too. I don't think that things like emission/inflation curve or block interval belong to this set, to say nothing of proof-of-work algorithm.
 

bitcartel

Member
Nov 19, 2015
95
93
@YarkoL The picks and shovels will be proprietary. Surely that is a problem? Even if the manufacturer dumps a bunch of code onto Github, how do we really know what the ASIC is doing? Who has the time and skills to examine the silicon, let alone what might be in the software driver? Maybe there's no backdoor but who's to know if the device only reports 5/10 successes and the rest is sent back to the manufacturer?

https://www.schneier.com/blog/archives/2012/05/backdoor_found.html

"Claims were made by the intelligence agencies around the world, from MI5, NSA and IARPA, that silicon chips could be infected. We developed breakthrough silicon chip scanning technology to investigate these claims. We chose an American military chip that is highly secure with sophisticated encryption standard, manufactured in China. Our aim was to perform advanced code breaking and to see if there were any unexpected features on the chip. We scanned the silicon chip in an affordable time and found a previously unknown backdoor inserted by the manufacturer. This backdoor has a key, which we were able to extract. If you use this key you can disable the chip or reprogram it at will, even if locked by the user with their own key. "
 

YarkoL

Active Member
Dec 18, 2015
176
258
Tuusula
yarkol.github.io
I think that's a good point. In that case I guess we'd have to trust that the professional paranoiacs in the community are able to blow the whistle if something like that were to occur.
Even now there are a few small-scale ASIC makers, so if commodification of the tech took really off, the competitors would probably keep a close watch what the others were doing and let it known if there were any foul play.
 

bitcartel

Member
Nov 19, 2015
95
93
People say that commodification of ASICs will bring back decentralization of mining. Put another way, people are saying that in order for mining to be decentralized, it requires miners to use the same commodity technology.

However we already have commodity technology suitable for mining - the personal computer! All ASICs are doing is replacing one commodity with another, except you have to pay money to buy an ASIC when you already have a computer.
 

paulh69

New Member
Jan 24, 2016
1
0
It should be possible to create an additional proof of work method that brings mining back to individual PC's running wallets and nodes - ensuring decentralisation - eventually killing off insane power requirements of ASIC mining.
 

go1111111

Active Member
What of the argument that this just gives power to botnets, and that ASICs getting commodified solves the problem finally (changing algo forces us back through the danger period where the tech is being developed and ramping up very quickly)?
Did someone ever use a botnet to attack Bitcoin though? Anyone controlling a botnet has a choice between honest mining and attack. If they have enough hash power to launch an attack, they have enough hashpower to make huge sums of money through honest mining. Their opportunity cost is huge.