Responding to the introduction of selfish mining and block withholding

[Steve Sokolowski]

Part of the reason that many cryptocurrency community members are confused about technical details is that a large part of the discussion revolves around theory. Theories are a necessary part of science, but testing theories often leads to unexpected results. For example, although there is much gnashing of teeth over the theoretical effects of 8MB blocks on the bitcoin network, in practice we have not determined a correlation of statistical significance between orphan rates and blocksize in any coin (the orphan rate is, however, directly proportional to block time). One of the reasons why the scientific method is important is because it allows humans to double-check their mathematical assumptions and to refine them based on unexpected discoveries.

One popular branch of bitcoin theories focuses on ways that miners can gain an advantage over other miners or mining pools. Other than the obvious 51% attack, "selfish mining" is one of the most commonly discussed principles here. Last year, we posted that we had experimented to see if selfish mining could be implemented as easily as was claimed in the literature. We were unable to make any progress in a timely fashion, and computed that we could earn more profit in a kinder way by dedicating the time to other features. Our suspicion that theory is rarely backed up by practice was confirmed when well-connected Core developer Gregory Maxwell (nullc) replied with his surprise that anyone had actually tried selfish mining.

The "officially" proposed version of selfish mining involves mining normally on a coin until a block is found, and then creating a private blockchain that is not published to the main network. The private chain remains ahead of the chain visible to the remainder of the network. In the ideal case, you keep your private chain two blocks longer than the public chain, and publish the second block behind, so that the other miners will always orphan their blocks until they finally gain enough hashpower to catch up. The exact procedure is more complicated, and full detail can be found in the original paper at https://www.cs.cornell.edu/~ie53/public ... ProcFC.pdf.

Earlier this year, the previous operator of a mining pool E-Mailed Chris to threaten him to buy a license to his pool software. We declined because of the tone of his message. He stated that he had licensed his pool to a new owner, that it had relaunched, that he had put older pools like the Wafflepool out of business, and that the pool would now have increased profits (and we would die) because it would overload networks by having a large hashrate suddenly mine long chains of blocks, thus orphaning the blocks of pools that mine one block at a time. He is licensing the software to other pools, which means that the cryptocurrency industry has now entered an era of block withholding. His message caused us to plan countermeasures, and after we were able to return from the weeks spent preparing taxes, we successfully implemented a solution. This solution was deployed to production on Saturday and Chris is now enabling it one coin at a time.

Our first thought was that the best response to his software would be to engage in selfish mining ourselves. However, we quickly discovered that the original selfish mining paper fails to consider that for all coins, even bitcoin, there are other networks available that use the same algorithm. While selfish mining may make that pool more money on specific coin networks, a significant amount of hashpower needs to be continually devoted to those networks to make the process feasible. Otherwise, the competing pools will catch up quickly, and the entire private chain will be a huge loss. Thus, we discovered that the pool operator was indeed telling the truth; he would have to have a huge amount of hashpower to accomplish this task. However, we found that the devotion to keeping the withheld private chain ahead on one coin is almost always outweighed by the opportunity cost of being unable to mine easier coins that occasionally present themselves as more profitable.

While we don't have the exact code that the pool operator is using, our conclusion through our data is that if he implemented selfish mining exactly as it is described in the paper, or even if he simply withholds blocks in some other fashion, he made his software less efficient because they can't switch coins frequently. If they decide in the future to offer litecoin-only or bitcoin-only mining, selfish mining will benefit users of their pool, but mining only litecoins or bitcoins is a losing strategy, because both scrypt and SHA-256 have more profitable coins available. (There are specific factors that favor single-coin mining in rare environments that are out of the scope of this article.)

While we were confident that selfish mining or overloading networks with long strings of blocks could not improve profitability in a multi-coin environment, we continued our research in an attempt to determine if a variant of the technique could be made to work in the real-world multi-coin environment and if it could be made more network-friendly. We arrived at what we have named "orphan bonuses." To see how this works, it is necessary to understand that there are multiple steps in finding blocks:

• A miner discovers a hash that solves a block
• Network latency of up to 100ms in sending the hash to the mining server
• Delay of a few ms while the CPU sends the work to a multiprocessing system to be hashed and receives the result
• If block found, incur delays in processing block and sending block to network
• The block is sent to all connected nodes, which incurs network latency again

As you can see, there are multiple steps that result in significant latency between a miner solving a block and that block getting out to the network. For example, the following scenario happened frequently:

• A new block is discovered by another pool
• 100ms required for daemon to notify mining server, for mining server to create work, for mining server to determine which coins are now most profitable, for mining server to send new work, and for network latency in the miner receiving the new work
• After 99ms, the miner, who has not yet received the new work, finds what it doesn't know is an orphaned block
• Miner transmits orphaned block to mining server
• The block is orphaned, so the mining server discards it

In the second scenario, the mining server receives an orphaned block 200ms after having known that there was already a new block on the network. Previously, this block would be considered stale and deleted, but the orphan bonus scheme allows this situation to become very profitable.

In the orphan bonus scheme, we mine the most profitable networks most of the time. When the case above is detected, this coin actually becomes more valuable to mine because the discovery of the next block results in the status of the previous block being switched from orphaned to immature. Instead of mining the next block on top of the block that the network received earliest, we send a work restart to mine on top of our orphaned block if we are going to continue mining this coin. The expected payout of our orphaned block is now equal to the expected payout of the previous block plus the expected payout of the current block, because finding the next block causes the network to reorganize its chain. If this situation occurs again when we find a second block, then the third block is now as valuable as the last three blocks combined.

The coin selection algorithm will now assign proportionally more miners to the coin, even if a difficulty increase or a price decrease in the next block caused the coin to fall down to the bottom of the list. Additionally, the counterintuitive field of statistics allows miners to be paid more because they stand to earn more if this "higher-value" block is found. Of course, the pool assigns the same number of miners to the coin if we would have a high probability of orphaning our own blocks by assigning more (which is currently assumed to be a target of no shorter than 2.7s block time). We abandon this chain of blocks when another pool finds a block of higher height than ours. Then, the profitability of the coin falls to the profitability of the current block.

One would think that mining on top of an orphaned block is as simple as changing the previous block's hash in the next block. In practice, this scheme is not easy to implement because of shortcomings in the daemon code. After much gnashing of teeth, we discovered that the difficulty of a block is actually encoded in the block itself. Since most coins change their difficulty every block, a method was needed to determine what the difficulty of the next block would be. The difficulty of the next block is often dependent upon the time the last block was received, so our block (which has a timestamp different from the other pool's block) results in a different difficulty for the next block.

The coin daemons do not include code to determine the difficulty of the next block. The best alternative RPC call is "getblocktemplate," which returns a "bits" field that indicates the target difficulty of the next block after the other pool's block - but getblocktemplate does not provide a way for the caller to specify which chain to extend. Thus, we wrote code to add a new "getnbits" RPC call, which receives a String (the block hash), and calls the existing functions in the daemon to determine the next difficulty as if the orphaned block were the latest. This call allows us to provide orphan bonuses without having any knowledge of a coin's difficulty adjustment algorithm, as understanding the difficulty algorithm for all 200 coins would be impossible. Chris further expanded upon this feature by writing code to modify the source after cloning to add this function and its dependencies in other files when coins are being added or updated.

Our first block to be reversed from orphaned state was HeisenbergHex block 1865740, visible at https://prohashing.com/explorer/Heisenb ... 13f813772/. The network saw this block as orphaned, but we mined on top of it and this block is now part of the longest chain.

It takes Chris about 30 minutes to modify a daemon, which means that it will take a little over a week (80 hours) of work to get most daemons recompiled. Some of the newer daemons have additional parameters for a "Consensus" object, which breaks compatibility with this solution, but since the number of daemons with that change is small, those will be ignored for now.

In conclusion, selfish mining isn't an effective way to improve profitability unless a pool is willing to devote a significant amount of resources to a single coin. Since all algorithms have other coins available, the "orphan bonus" solution is a better way to increase profitability. Whereas suddenly publishing huge strings of blocks has implications for double-spending, orphan bonus mining is also friendly to networks, because the orphaned blocks are visible to all and transactions that have more than one confirmation are never reversed.

The previous operator of the other mining pool is offering to license his software to multiple owners, which means that selfish mining, or a variant of it, is here to stay. Even owners choosing not to license the software are now required to respond in some way to remain competitive. It will be interesting to see how the widespread introduction of block withholding impacts the industry, and how multiple-coin pools respond with more efficient solutions.

[coinaday]

When the case above is detected, this coin actually becomes more valuable to mine because the discovery of the next block results in the status of the previous block being switched from orphaned to immature. Instead of mining the next block on top of the block that the network received earliest, we send a work restart to mine on top of our orphaned block if we are going to continue mining this coin. The expected payout of our orphaned block is now equal to the expected payout of the previous block plus the expected payout of the current block, because finding the next block causes the network to reorganize its chain. If this situation occurs again when we find a second block, then the third block is now as valuable as the last three blocks combined.

I didn't understand this at first, but I think I understand it now. At first, I thought you had solved the latest block, and gotten an orphan at the same time. Instead, if I'm understanding right now, the case is that someone else solved the latest block, and someone using your pool got an orphan. And so the "double value" for mining on top of the orphan is because, instead of getting no reward at that time, because someone else got the block, you're getting a second chance to make the orphan count, along with the new block.

So if we say the height is X, there's a published block (not ours) at height X, and there's an orphan that we have at height X. By mining on top of the orphan instead of the published block, we double our reward on success, because we get the reward for the orphan, which otherwise would have gone unclaimed, along with the standard reward.

Then for the final line, let's see if I'm still tracking. So in this case, is it that there's a published X+1 block right as you find an orphan on top of your orphan? So we have two "parallel chains", the X and X+1 that's published and the X' and (X+1)' orphaned unpublished. So by working on the orphaned chain, we can get "three times the normal reward" by "reclaiming" the rewards for the orphans which otherwise would get nothing, instead of getting a standard reward for working on the published chain.

The only problem I see with this is that you also said that there would never be a case where a reorganization would cause a transaction with more than 1 confirmation to be reversed. But in this last example, the potential reorganization would change two published and accepted blocks, so I don't see how that could be guaranteed to be the case (consider if X and X' had conflicting transactions). I can understand that because you're not acting maliciously, it should be uncommon (you'd tend to be including the same transactions as everyone else), but it seems like there could potentially be a double spend vector in here, if someone could figure out how to (or, more likely, try until they are able to get by chance; or some combination of the two) get the published block to contain the transaction they want to reverse, and the orphaned block to contain their attempt to double spend it.

Additionally, it seems like this sort of technique would result in a sort of 51% attack, in that the majority hash would keep building on its orphans and catching up, and the minority hash would find that even when it found a block first, it would ultimately be reorganized away and orphaned. I'm not sure what to do about that, as the approach described here seems like a logical and not obviously malicious route, but it does seem like it could have an unfortunate centralizing tendency.

[Steve Sokolowski]

When the case above is detected, this coin actually becomes more valuable to mine because the discovery of the next block results in the status of the previous block being switched from orphaned to immature. Instead of mining the next block on top of the block that the network received earliest, we send a work restart to mine on top of our orphaned block if we are going to continue mining this coin. The expected payout of our orphaned block is now equal to the expected payout of the previous block plus the expected payout of the current block, because finding the next block causes the network to reorganize its chain. If this situation occurs again when we find a second block, then the third block is now as valuable as the last three blocks combined.

I didn't understand this at first, but I think I understand it now. At first, I thought you had solved the latest block, and gotten an orphan at the same time. Instead, if I'm understanding right now, the case is that someone else solved the latest block, and someone using your pool got an orphan. And so the "double value" for mining on top of the orphan is because, instead of getting no reward at that time, because someone else got the block, you're getting a second chance to make the orphan count, along with the new block.

So if we say the height is X, there's a published block (not ours) at height X, and there's an orphan that we have at height X. By mining on top of the orphan instead of the published block, we double our reward on success, because we get the reward for the orphan, which otherwise would have gone unclaimed, along with the standard reward.

Then for the final line, let's see if I'm still tracking. So in this case, is it that there's a published X+1 block right as you find an orphan on top of your orphan? So we have two "parallel chains", the X and X+1 that's published and the X' and (X+1)' orphaned unpublished. So by working on the orphaned chain, we can get "three times the normal reward" by "reclaiming" the rewards for the orphans which otherwise would get nothing, instead of getting a standard reward for working on the published chain.

The only problem I see with this is that you also said that there would never be a case where a reorganization would cause a transaction with more than 1 confirmation to be reversed. But in this last example, the potential reorganization would change two published and accepted blocks, so I don't see how that could be guaranteed to be the case (consider if X and X' had conflicting transactions). I can understand that because you're not acting maliciously, it should be uncommon (you'd tend to be including the same transactions as everyone else), but it seems like there could potentially be a double spend vector in here, if someone could figure out how to (or, more likely, try until they are able to get by chance; or some combination of the two) get the published block to contain the transaction they want to reverse, and the orphaned block to contain their attempt to double spend it.

Additionally, it seems like this sort of technique would result in a sort of 51% attack, in that the majority hash would keep building on its orphans and catching up, and the minority hash would find that even when it found a block first, it would ultimately be reorganized away and orphaned. I'm not sure what to do about that, as the approach described here seems like a logical and not obviously malicious route, but it does seem like it could have an unfortunate centralizing tendency.

There could be a double-spend issue with this algorithm, but we include the transactions from the block that the rest of the network submitted in the block that we are building. If transaction A is included in the block the rest of the network submitted and our orphaned block had no transactions, then transaction A is included in the next block we are mining. This makes economic sense, because we want to get the fees for A, and also ensures that the state of the network doesn't change regardless of whether we are successful or not.

I think I have to amend the original post this evening to include what you pointed out - that it is possible that in some cases there could be more than one block reversed. However, because the same regular transactions are being included, only coinbase transactions in those blocks would be reversed. If the case of three blocks arises and we are successful in reorganizing the chain, then the same transactions appear, just one block later than they would have otherwise. However, despite this being active on the HeisenbergHex and CryptoEscudo networks for two days, the case of more than one block being reversed at a time has never actually happened, as the circumstances for that happening when we aren't purposely trying to create the situation are very rare.

Unfortunately, there's not much that we can do now that the other pool has started this "arms race." The only thing we (and others) can do is to try to find the least disruptive way of responding. I think that including the previous transactions in the new blocks is the best way of responding - the only loser in that case is another pool, while the disruption to users (having their transactions show up one block later) is minimal.

[coinaday]

Absolutely agreed that there's not really a choice. This seems like the least-bad response to the block withholding attack for sure, and it's a brilliant defense which I'm surprised I haven't heard of anyone doing before. It's one of those "seems obvious in hindsight" advances.

With the double spend possibility, yep, makes sense. It should be very obscure, but a potential exploit if a person can somehow manage to make your orphan block include a transaction which conflicts with the published block.

I do think the idea that it might cause minority hash pools to end up constantly orphaned is concerning, but I have no idea what to do about that, and you have to defend yourself against orphaning as best you can, so it seems like perhaps it's simply inevitable. I have a rather different view on that sort of thing than many in cryptocurrency, since I consider having centralized hashing to be one of those things that is terrible in theory and can be in practice, but need not be terrible. With Nyancoins, you guys have generally been the majority hash and it's had no negative effect that I know of, since you're honest and interested in long-term growth and development of cryptocurrency.

I will be interested in trying to see if this results in greater orphaning with the other pools once you activate it though, since by my understanding it should. Although, since this only kicks in if you happen to get an orphan, and you take the blocks when someone else publishes, I think it actually should be a smaller effect than I was initially thinking (won't orphan all minority hash blocks; only when simultaneous find happens).

And on the longer reorganizations, aye, that makes sense that it would be rare. This is definitely edge case stuff, but that sort of thing is always good to think through to understand the fundamentals better.

Thanks for the write-up! Providing this sort of analysis is great for the cryptocurrency community!

[excelerator]

This paper from Cornell also provides additional insight into the risks of Selfish mining.
https://www.cs.cornell.edu/~ie53/public ... ProcFC.pdf

[Steve Sokolowski]

Absolutely agreed that there's not really a choice. This seems like the least-bad response to the block withholding attack for sure, and it's a brilliant defense which I'm surprised I haven't heard of anyone doing before. It's one of those "seems obvious in hindsight" advances.

With the double spend possibility, yep, makes sense. It should be very obscure, but a potential exploit if a person can somehow manage to make your orphan block include a transaction which conflicts with the published block.

I do think the idea that it might cause minority hash pools to end up constantly orphaned is concerning, but I have no idea what to do about that, and you have to defend yourself against orphaning as best you can, so it seems like perhaps it's simply inevitable. I have a rather different view on that sort of thing than many in cryptocurrency, since I consider having centralized hashing to be one of those things that is terrible in theory and can be in practice, but need not be terrible. With Nyancoins, you guys have generally been the majority hash and it's had no negative effect that I know of, since you're honest and interested in long-term growth and development of cryptocurrency.

I will be interested in trying to see if this results in greater orphaning with the other pools once you activate it though, since by my understanding it should. Although, since this only kicks in if you happen to get an orphan, and you take the blocks when someone else publishes, I think it actually should be a smaller effect than I was initially thinking (won't orphan all minority hash blocks; only when simultaneous find happens).

And on the longer reorganizations, aye, that makes sense that it would be rare. This is definitely edge case stuff, but that sort of thing is always good to think through to understand the fundamentals better.

Thanks for the write-up! Providing this sort of analysis is great for the cryptocurrency community!

I thought about this a little more and I realized that what I said before is incorrect. The state of transactions never changes at all because of the magic of statistics.

I was mistakenly comparing the idea that when we reverse the transaction in block X and replace it with the same transaction in X+1, that we somehow reduced the odds of a third alternative: that someone else found a second block and gave the transaction two confirmations. But that isn't true. The probability of that person finding the next block is no higher when we are mining X+1 and after we have mined X+1.

When X+1 is found, the state of the network is exactly the same as before. The transaction is still in the latest block. The other miners still have the same probability of adding a second confirmation to X+1 as they used to have adding a second confirmation to X.

Therefore, this method doesn't actually change any security at all. It would only reduce the security of the network if we were "wasting" work towards the next block by someone else. But every bad hash is "wasted" work the minute it is finished.

[claydigger]

Glad to hear that the Prohashing brothers are constantly refining the "Secret Sauce" to keep the pool in top shape. I have tried other pools that claim high payouts, but my Titan miners run better at Prohashing that anywhere else so I am keeping my hash right here.

[Steve Sokolowski]

For those interested, we reversed at least 114 blocks worth $5.33 in the past 24 hours, for an increase in profitability of at least 0.75%.

However, we've only implemented about 1/8 of the coins, and even after we have recompiled all the coins, it will take one month before we gain full effect from this change. Right now, we're only gaining an advantage on networks where the orphan rate is already low, because the old code orphaned blocks and made them unprofitable on the other networks. As the average orphan rate falls on those coins, they will be selected more often, and since their orphan rate was high, the probability of our reversing blocks from selfish pools on those networks will be higher than the probability of reversing blocks on the low-orphan coins we are mining now.

Furthermore, the $5.33 is underestimated because the latest batch of coins has only been active for 24h, which means that there are many networks where coins take a very long time to confirm that have not been counted as having "reversed" blocks yet, but will when we look at this number tomorrow.

Given that we can already earn 0.75% more on the 1/8 of low-orphan coins that we already are selecting, and we haven't had enough time for all the blocks to be confirmed yet, this change has the potential to significantly combat the pool that is publishing those long chains of blocks.

[kires]

Wow, that's pretty amazing. Kudos and mad props unto thee!

[Steve Sokolowski]

Wow, that's pretty amazing. Kudos and mad props unto thee!

Chris added more coins, and the last 24 hours (8 am Wednesday to 8am Thursday) improved profit by $6.97, up from $5.33 from 6pm Tuesday to 6pm Wednesday.

kires, Chris made an update and you can now see these blocks in the "found blocks" tables. They are listed as "reversal," which indicates that they were originally orphaned but the next block reorganized the chain. You'll have to go back in time a little bit because reversals can't be determined until the coins mature, which takes 5 minutes to several hours.