Adaptive Proof of Work (APoW): Komodo’s New Solution To Difficulty Stranding

Blockchains do not have inherent security. While major blockchains like Bitcoin and Ethereum are incredibly secure, it’s common knowledge that smaller blockchains don’t have anywhere close to the same level of protection. If a blockchain’s network is small and weak, so are that blockchain’s defenses against malicious attacks.

Proof of Stake blockchains face threats like the Nothing at Stake problem and Weak Subjectivity. On the other hand, Proof of Work blockchains have to worry about the infamous 51% attack, as well as more obscure attacks like the Diff Strand Attack.

A Diff Strand Attack is when malicious miners raise a small network’s hash rate and cryptocurrency mining difficulty to extremely high levels, all very suddenly. Then, the malicious miners quickly abandon the network, leaving it stranded with such a high difficulty that the remaining miners are totally incapable of processing transactions or finding new blocks. The network gets stuck and the chain is effectively brought to a screeching halt.

To defend against 51% attacks, Komodo uses the delayed Proof of Work (dPoW) security mechanism, which recycles the Bitcoin network’s hash rate to give every dPoW-integrated coin the same level of security as Bitcoin itself.

As for the threat of difficulty stranding attacks, Komodo now has a solution for this, too. Komodo’s Lead Developer James ‘jl777’ Lee recently implemented adjustments to traditional Proof of Work rules, originally developed by zawy, to allow a network to quickly and naturally recover from a Diff Strand Attack. This new consensus method is called Adaptive Proof of Work (APoW).

Understanding Proof of Work and Mining

The first step in learning about Adaptive Proof of Work (APoW) is to gain an understanding of how ordinary Proof of Work networks function.

Stated very simply, Proof of Work forces all of the machines on the blockchain’s network— that is, the miners— to compete against one another. Each miner is trying to solve a complex math problem before anyone else.

The miner who is first to find the solution (the nonce) mines a block and receives the corresponding block reward. Then a new math problem is created and the contest starts over again. These repeated competitions incentivize miners to use their hardware, time, and skills on cryptocurrency mining, as they all want to earn the block rewards that come with mining blocks.

Block rewards vary from blockchain to blockchain. KMD block rewards, for instance, are 3 KMD per block. Bitcoin block rewards are currently 12.5 BTC per block, although they began at 50 BTC per block and decrease by 50 percent every 210,000 blocks. The next block halving will take place in May 2020, when BTC block rewards will drop to 6.25 BTC per block.

Hash Rate and Difficulty Adjustments

Proof of Work blockchains have a built-in mechanism that detects the network’s hash rate— the amount of computational power that all the miners are cumulatively using to search for blocks on that chain. Hash rate is typically measured in tera hashes per second. One tera hash is equal to 1 Trillion hashes per second.

The built-in hash rate detector periodically calibrates the difficulty of the math problem that miners must solve to mine a block. This is what’s known as a Difficulty Adjustment Algorithm (DAA).

The general principle of a DAA is simple: the higher a chain’s hash rate, the more difficult the math problems that miners must solve to find blocks. This ensures that miners aren’t finding blocks too quickly, which would be the case if the problems were too easy. It also avoids long periods of time with no blocks at all, which is what would happen if the problems were too hard.

To take the Bitcoin blockchain as an example, the difficulty is adjusted every 2,016 blocks, which is roughly every two weeks. The new difficulty is based upon the network’s average hash rate from the previous two weeks. Based on that average, the new difficulty is set such that, if that same average hash rate is maintained, the network will find a new block every 10 minutes.

Of course, different blockchains have different block times (the Komodo blockchain produces a new block roughly every 60 seconds) so the way that difficulty is adjusted varies. Most blockchains have a faster block time than Bitcoin’s painfully slow ten minute block times, so most blockchains need to adjust the difficulty level more frequently than every two weeks.

While the frequency and method used to calibrate a Proof of Work blockchain’s settings may vary, the important point here is that all Proof of Work blockchains must adjust their difficulty. Otherwise, a huge influx of new miners (and thus hash rate) would speed block creation up unacceptably fast.

Conversely, if a large number of miners suddenly left a network, the hash rate would drop suddenly and the remaining miners may need days or even weeks to find a single block. In short, this is what’s known as a Diff Stranding attack.

Diff Stranding Attacks Explained

A Diff Strand Attack is one in which a malicious miner or group of miners who control a large amount of hash power join a small blockchain network, causing that network’s hash rate and mining difficulty to skyrocket. After the difficulty of finding a block becomes extraordinarily high, all of the malicious miners who recently joined the network— causing the increase in hash rate and difficulty in the first place— leave the network just as quickly as they ascended upon it.

The consequence of this sort of attack is that the difficulty of finding a block gets stuck at an extremely high level. When the malicious miners leave the network, they take a vast majority of the network’s hash rate with them. This means that the miners who remain on the network need a very long period of time to find a new block, possibly a few weeks or even a month for one new block. And, since the DAA only readjusts the difficulty level every X blocks, the network still needs to find a number of new blocks before the difficulty is reduced again.

If a blockchain ordinarily produces blocks every 60 seconds, not producing a single block for one full month is akin to the death of that network. Nobody would be able to send or receive transactions. In effect, the blockchain comes to a grinding halt and the coin becomes useless.

An Example Of A Diff Strand Attack

All of this might not be completely clear so let’s use an example to really grasp a Diff Strand Attack.

Let’s use Commercium as our example. It’s a perfect example because it uses Equihash, a popular hash function with plenty of available hash power, and because its network is particularly tiny. According to crypto51.app, a whopping 35,000 percent of the entire Commercium network’s hash rate is available for rent on the popular hash rate rental site NiceHash (at the time of writing). You could rent more than twice the hash rate of the entire Commercium network for round $10 USD per hour.

One important thing to understand about Proof of Work blockchains is that they do not all use the same cryptographic hash function. For instance, Bitcoin famously uses SHA-256, Litecoin uses Scrypt, and Ethereum uses a unique hash function called Dagger Hashimoto.

Zcash, Zclassic, Horizen, Komodo, Pirate Chain, HUSH, Bitcoin Private, and Commercium all use the Equihash algorithm. Here’s a chart showing the hash rate of these Equihash chains:

As this chart shows, hash rate distribution is heavily skewed. In this case— that is, the case of the Equihash algorithm— the Zcash network is host to almost all of the Equihash hash rate. Approximately 90 percent of all existing hash rate for the Equihash algorithm is on the Zcash network.

It’s important to note that Komodo, Pirate Chain, and HUSH are all protected with the power of the Bitcoin network with the delayed Proof of Work (dPoW) security mechanism. This prevents 51 percent attacks and keeps the networks secure, despite having comparatively small hash rates.

Even if we remove Zcash from the table above, it’s still clear that the hash rate is not distributed evenly.

Let’s imagine that miners controlling a mere 10 percent of the total hash rate of the Horizen network decide to start mining Commercium. That means 35 MH/s would move from Horizen to Commercium, leaving Horizen with a total of 315 MH/s and boosting Commercium from just 0.7 MH/s all the way up to 35.7 MH/s. This is an increase of more than 50 times the original hash rate.

As a result, the difficulty of finding a block will also increase by roughly 50 times when the DAA next adjusts the network's difficulty level.

Now, imagine that all of those miners who recently joined the Commercium network decide to switch to a different Equihash blockchain. The Commercium hash rate would drop back down to around 0.7 MH/s.

However, because the difficulty level is only adjusted periodically, the network would be stuck with a very high difficulty until the next calibration.

The remaining miners on the network— meaning the miners who collectively contribute 0.7 MH/s to the Commercium network— do not have enough hash rate to find blocks at the new difficulty that’s 50 times higher than the original difficulty level. It might take the network several weeks or even a month to find a single block at a difficulty level intended for a network with a hash rate of 35.7 MH/s.

This is a Diff Strand Attack. After an influx of miners causes a blockchain’s difficulty to increase by dozens or even hundreds of times over, the miners all abandon the network, leaving it stranded and unable to find blocks. The network becomes completely incapable of processing transactions, as no miner can produce a new block. No one can send or receive the coin.

It’s a devastating attack that smaller blockchain networks have previously not had a way to defend against. That is, until Komodo developed a solution.

Adaptive Proof of Work (APoW)

A developer by the name of zawy12, , an electrical engineer who is widely considered the industry’s foremost authority on Difficulty Adjustment Algorithms, recently developed a solution to Diff Strand Attacks. In close cooperation with zawy12, Komodo’s Lead Developer James ‘jl777’ Lee implemented this solution to the Komodo code base in what is now called Adaptive Proof of Work (APoW). As the name suggests, this variation of Proof of Work allows a blockchain’s network to adapt to sudden and substantial changes in hash rate. In fact, with APoW, a blockchain network can adjust the difficulty target within a single block!

There are three main components to this new variation on Proof of Work: timestamp protection, block-to-block stair-stepping, and N*N difficulty adjustments.

Timestamp Protection

Since APoW allows a blockchain’s difficulty to be adjusted from one block to the next, it’s necessary to implement some form of timestamp protection. Otherwise, miners would be able to backdate a block and then post-date the next one with a much reduced difficulty, thus doubling their block rewards as they manipulate the difficulty and selfishly mine two (or more) blocks in quick succession.

To avoid this form of selfish mining, APoW does not activate until after a set length of time has passed: the maximum backdated time allowance plus the maximum leniency for a future-dated timestamp, with a little bit of margin added. This ensures that selfish miners will not be able to manipulate timestamps to abuse the APoW difficulty adjustments to increase their earnings.

Block-To-Block Stair-Stepping

Adaptive Proof of Work uses the median block time of a batch of recently-mined blocks, rather than just the previous block’s block time, to calibrate difficulty.

For instance, a single block might be mined in, say, 45 seconds, despite the fact that the blockchain has a target of 60 second block times. Outliers such as this occasionally occur. It’s simply a matter of statistics. Think of a standard normal distribution— even with an established average, roughly 4 percent of all blocks will be 2 or 3 standard deviations above or below the mean block time.

If APoW relied on just one block, which happened to be an outlier, it may make inaccurate readjustments. In our current example, the block was found in just 45 seconds, which is a full 25 percent faster than the target block time. Thus, if APoW was calibrating the difficulty on this one block alone, it would increase by difficulty by 25 percent. This would be a huge increase in difficulty in response to what was just a simple statistical outlier.

Instead, APoW relies on the median block time of the last several blocks. This is a much more reliable indicator of whether or not the difficulty needs to be adjusted and, if so, by how much.

Exponential Decay Difficulty Adjustments

The third and final component to APoW is an exponential decay algorithm for difficulty adjustment, one that helps a Diff Stranded chain get back on track quickly but cannot be abused by malicious miners.

With the help of Zawy, Komodo Lead Dev James ‘jl777’ Lee was able to improve the Komodo code base to almost completely negate the effects of a diff strand attack while also preventing manipulation and selfish mining. The algorithm adjusts the difficulty according to 3^delay/blocktime.

The result of this is that, after a significant spike in hash rate and difficulty followed by a huge drop in hash rate and difficulty, each new block becomes much easier until the difficulty stabilizes according to the true size of the network.

For example, let’s imagine that a small blockchain network with a target block time of 60 seconds experiences a 1 Million percent increase in hash rate and difficulty. Suppose further than the miners who caused the 1 Million percent spike then leave the network, stranding the remaining miners with a difficulty one million times higher than it was originally.

In all ordinary circumstances, this Diff Strand Attack would cripple the blockchain. It may take several days or perhaps even weeks for the network to find a single block, depending on the exact details of the attack and network.

However, with APoW, the network can quickly recover.

Zawy and jl777 estimate that:

a 1 million fold hashrate attack will readjust to a difficulty of 500,000 in just 7 blocks. Usually, a 1 million fold hashrate attack will take hundreds of blocks to stabilize, so this is just an amazing result. Since the recovery takes 10 minutes or so, that is about 9 lost blocks to cancel out the 7 blocks that came faster, i.e. a net neutral or close to net neutral number of blocks. We will continue working together to fully solve the DAA problem.

Trying Adaptive Proof of Work On A Test Blockchain

After writing the code and implementing Adaptive Proof of Work on a test blockchain, the Komodo community worked together to test APoW’s recovery capabilities in a real Diff Strand Attack.

With Komodo’s multi-chain architecture, launching a Smart Chain takes just a few minutes. This can be done with the Komodo Chain Composer or it can be done for free from the command line. To learn more about customizing and launching your own Smart Chain with Komodo, please see Komodo’s Developer Documentation.

The test chain created to test APoW was aptly titled ADAPT and it was spawned on July 31, 2019. Kolo, Decker, MrLynch, and SHossain all participated in testing the new APoW implementation.

The test team started ASIC mining the ADAPT chain at 20:00 UTC on July 30 and pushed as much hash power onto the ADAPT network as they could, as quickly as they could. They mined with all the power they could for 30 minutes, stopping ASIC mining completely at block 2374, which was mined with a time stamp of 20:31:48 UTC.

At its highest point, the hash rate reached 1.1 MH/s. This gave the ADAPT test chain a difficulty of 1.2 Million. Here is a chart of the hash rare that the test team’s cryptocurrency mining pool was contributing to ADAPT.

After the team stopped ASIC mining at block 2374, just one mining node remained on the network— a CPU miner with a single thread. The CPU took about half an hour to produce any blocks but, once the blocks were mined, they come in batches of six blocks at a time.

After 456 blocks, the ADAPT test chain’s difficulty dropped all the way down to only 9, from a high of 1.2 million. It took the sole CPU miner 16.5 hours to mine those 456 blocks, averaging out to roughly 2.17 minutes (2 minutes and 10 seconds) per block.

About the testing on APoW, Komodo’s Lead Dev jl777 wrote:

We just did a mining attack test to validate the Adaptive Proof of Work (APoW). We boosted the difficulty to 1.2 million and now have a single CPU trying to mine it back to normal. Of course, that would be impossible without APoW, but with it, even a 1 million diff stranding can be recovered from. Blocks come in clumps of six after a gap of 13+ minutes. At a difficulty of one million, the first gap was almost 30 minutes, but as the diff drops over the hours, the network will produce a batch of six blocks every 15 minutes or so. I predict within a day (instead of 10 years!) APoW will get a diff stranded chain back to normal.

The testing of APoW was so successful that the Komodo team made this feature available to any third-party project in October 2019. Today anyone who launches a Smart Chain with Komodo’s technology will have Diff Strand Attack prevention via APoW.

Combined with Komodo’s delayed Proof of Work (dPoW) security mechanism, which leverages the enormous hash rate of the Bitcoin network to prevent 51 percent attacks, Smart Chains are supremely secure and free to host value and apps without threat of attack or manipulation.

📧Komodo Newsletter

If you'd like to learn more about blockchain technology and keep up with Komodo's progress, subscribe to our newsletter. Begin your blockchain journey with Komodo today.