AdaptivePoW: the solution to diff stranding of smaller blockchains
First let me describe the problem that is often encountered by small PoW blockchains, which in this context is any blockchain that uses a hashing algorithm and isnt the highest hashrate coin that uses the same hashing.
It is not uncommon for a coin to have less than 1% the hashrate of a specific algo. That means if some miner decides to mine at 100x normal hashrate for a few minutes (this will find many blocks very quickly) he can get a lot of blocks in a very short amount of time. Then jump to the next coin that is in the same situation. This coin switching miner with a lot of hashrate can thus get a lot more than the expected number of blocks per hour and depending on the value of the coins he mines, maybe makes significantly more than just mining on the largest coin that uses the same algo.
What happens to the poor coins that are mined like this? Regardless of the specific DAA (diff adjustment algorithm), after being mined with 100x the normal hashrate for any prolonged period of time, the diff will be a lot higher. On the order of 100x higher.
The consequence of this is that after this big miner leaves, the chain is “diff stranded” and the ordinary miners for the chain would need to mine 100x longer to get the next block. It gets worse. If you have to spend 100x more for the same thing, would you? Only the most dedicated miners would do this and it could be that the vast majority of normal miners and what was “only” a 100x hurdle becomes a 1000x hurdle. What should take about a minute could end up taking a day, or in the worst case lead to even worse outcomes. You can imagine what happens to a coin that has no new blocks for a day, if there arent any miners willing to mine at a loss to get the chain back to normal, it might just stop without a hardfork.
Even if there are miners that are willing to rescue a stranded chain once, what if it happens again, and again, … At some point the entire mining equilibrium is broken for the coin and without that it becomes nonviable, so this is a big problem.
OK, so now the problem is clear. Any coin that uses an already existing hashing algorithm is at the mercy of the existing large miners of that algo to not abuse their chain. Which maybe you can get lucky, but maybe not, so it is best to have a decentralized solution to this. The context of all this was that one of our test chains MORTY was diff stranded and it messed with our atomicDEX testing. I was asked to fix it with some new consensus magic, but my first response was that DAA are very tricky and best not to mess with and after all what can you do about such hashrate issues. However, a bit later i had the idea on how to solve it as i already solved a very similar issue on the PoS side.
First let me describe DAA at the highest level, without getting into all the precise details. Each blockchain has the desired time between blocks and if the blocks are too fast, the difficulty is increased. If the blocks are too slow, the difficulty is decreased. Really it is just a feedback loop that tries to keep the blocktimes constant and works most of the time, but it breaks down when there is a big drop in hashrate. Usually the feedback for adjusting to new hashrate adjusts over hundreds or even thousands of blocks. Some coins have DAA that adjust every block, but even in this extreme situation, 100x strandings are a problem. For DAA that take 100 blocks to adjust that is basically a full days hashrate needed to just get 100 blocks and a costly event to whoever has to bail out the chain.
Finally, I can describe my solution, adaptivepow, which adjusts the difficulty target within a single block. This fully solves the problem as we can imagine a 50000x diff stranding (that is what happened), which would make the mining take months at normal rates. With adaptivepow, after it activates it rapidly adjusts the required difficulty, all during the same block.
Let me describe the adaptivepow. It waits for a long enough time to make backdating a block and future dating a block a nonviable attack. You need to make sure that is the case to avoid miners simply backdating a block and then postdating the next one with a much reduced difficulty. That would double their mining ROI and totally make the timestamps for each block going backwards and forwards. Also using the median time of the recent blocks instead of just the previous blocktime helps reduce the effectiveness of such messing around with block timestamps.
It is mostly assumed that block timestamps should always be increasing, but in reality it can go backwards. Still it is best to not have such chaos and a way for miners to boost revenues with timestamp gains. So adaptivepow doesnt activate until after enough time has passed, the max backdated time plus the maximum future dated timestamp, with a little bit of margin added.
Next step is to make things stairstep once per blocktime, this is done by calculating the difference between the proposed blocktime and the median blocktime and rounding it to the nearest multiple. This will setup a stable diff for a one blocktime period. If a block isnt found, then the diff is made easier and easier with the passing of each block period.
The final trick to make it recover from even a million times diff stranded is to use N*N as the diff adjustment, where N is the elapsed time minus the activation time. What this does is that with each new block, the difficulty becomes much easier.
For example, with a one minute blocktime, the first minute will be 3600x easier, the next minute 14400x easier, the third minute 32400x easier, etc. 17 minutes after activation the diff becomes over a million times easier. So about half an hour for the practical worst case stranding of what otherwise would be a million minutes (almost 2 years!)
From concept to implementation and debugging for -ac_adaptivepow was one day, thanks to shossain on the testing side.
update: after some more bugfixing, blocks seem to be coming in at about half the normal rate, though sporadically. it seems quite a reasonable recovery from a crazy big diff stranding