Selfish mining mitigations (Publish or Perish)

[tevador]

Monero is currently being attacked by a malicious pool that has around 33% of the network hashrate (α = 0.33). There is no evidence that the malicious pool has reached the majority of the network hashrate. Nevertheless, any pool with α > 0.25 can cause disruption with selfish mining, which is a malicious mining strategy which allows the pool to gain more that its fair share of the block rewards [1].

This is a proposal to mitigate selfish mining. It assumes that Monero keeps RandomX as its consensus mechanism and that α < 0.5. It does not (and cannot) address 51% attacks.

It's actually 2 proposals. The first proposal is a soft fork, which does not alter any consensus rules and only needs to be adopted by the honest majority of miners. The second, more comprehensive proposal, requires a hard fork.

After reviewing the available literature about selfish mining, I first want to disqualify all mitigation strategies that rely on more frequent hashrate sampling. This is the Fruitchain and related proposals [2,3]. The main idea is to submit proof of work "fruits" or "shares" with a much lower difficulty than what is required to mine a block and then aggregate those shares within a block. These ideas are unsuitable for Monero because RandomX is too slow to verify. A block consisting of 100 work shares would require 1.5 seconds just to verify the PoW.

Secondly, a large number of mitigations focus on tie-breaking rules [1,4], which apply when the attacker's private chain has the same length as the honest chain. These proposals are not sufficient against a resourceful attacker with α > 0.25, who can often outmine the honest majority and win due to the longest chain rule. We need a mitigation strategy that can work even if the attacker's chain is longer.

1. Soft-forking proposal

The most efficient selfish mining mitigation that can be rolled out as a soft fork is Publish or Perish (PoP) [5]. It works when the attacker's chain is less than k blocks longer than the honest chain (otherwise it falls back to the longest chain rule to allow network partitions to be eventually resolved). A chain weight rule is applied that takes into account the block's relative time of arrival and its embedded uncle block.

PoP introduces the concept of late blocks. A block is late if it arrives more than D seconds after any other block of the same height. This only requires relative time measurement and does not need the clocks of the network nodes to be synchronized. Late blocks do not contribute to the weight of its chain.

In case of two competing chains of equal weight, the PoP paper calls for a random selection to be made, but I would suggest to use a deterministic tie breaking rule (e.g. with hashing).

For a practical implementation in Monero, we would create a new tx_extra tag for uncle blocks and each miner could include an uncle block of height exactly N-1 (where N is the height of the current block) in the coinbase transaction. The uncle block is represented by its PoW header, which allows the PoW to be checked. Since the PoW header does not include the height, we would validate the height by checking that the prev_id field is the same as the one in block N-1 of the canonical chain. The approximate size of an uncle block is 80 bytes, which is quite negligible. Uncle blocks do not affect block rewards or the cumulative difficulty.

We would use k = 3, which means the attacker would need to mine 3 blocks more than the honest majority to cause a reorg. We would use a propagation delay of D = 5 seconds.

While not perfect, this strategy significantly reduces the excess profits from selfish mining. With α = 0.48, the attacker gets ~64% of the block rewards compared to ~88% with no mitigations (numbers from [5]).

2. Hard-forking proposal

The hard-forking proposal extends PoP with Reward Splitting (RS) [6]. It bears some similarities with the proposal by @venture-life [7].

This proposal fully removes the economic incentives for selfish mining unless the attacker can mine at least 20 blocks faster than the honest majority.

I will first list the consensus changes:

1. Include the block height in the PoW blob.
2. Reduce the target block time to 60 seconds and raise the output lock time to 20 blocks. The block reward and the penalty free block size will be halved.
3. Increase coinbase maturity to 1440 blocks (1 day).
4. The coinbase transaction of the block at height N pays out the block reward of the block at height N-20.
5. A new coinbase transaction field miner_address that includes the miner's Monero address (or more addresses and the percentages how to split the reward). This will be used in block N+20 to pay the miner(s).
6. A new coinbase transaction field uncle_blocks that includes uncle blocks. Uncle blocks include the PoW header, the coinbase transaction and its inclusion proof. Only uncle blocks with a height of at least N-20 can be included in block N.
7. Apply the PoP fork selection rule with k = 3 and D = 5. Only uncle blocks with a height of N-1 are counted towards the chain weight.
8. The difficulty adjustment algorithm uses the past 1440 blocks, starting from block N-30. Uncle blocks are included in the difficulty calculation. The lowest and the highest 120 block times are trimmed out before calculating the average block time.
9. The block reward for block at height N is split equally between the miner who mined the block N and all miners who mined an uncle block of height N that was included in blocks N+1 to N+20.

Rationale:

1. Including the block height in the PoW header makes uncle blocks easier to verify and can also help to detect malicious activity of public pools (e.g. mining a parallel chain).
2. Monero used to have a 60 second block time, but it was increased to 120 seconds in 2016 to reduce the natual orphan rate. Due to reward splitting, orphan blocks are not an issue in this proposal. The faster blocks make it harder for a minority hashrate attacker to reorg longer time periods of the honest chain at the cost of doubling the PoW to verify the chain, which is acceptable. Adjusting the output lock time to 20 blocks matches the current 10-block lock time (the same 20 minutes on average, but reduced variance).
3. Longer coinbase maturity prevents malicious miners from quickly selling mined coins after an attack and promotes long-term mining.
4. Delaying the payment of block rewards is required for reward splitting in order to collect uncle blocks. 20 blocks seems like a good compromise as it matches the output lock time.
5. Miner addresses are needed because miners no longer construct their own outputs. Note that the full (main) address and a transparent tx private key are needed in order to verify that the coinbase payout is constructed correctly (similar to p2pool).
6. Uncle blocks are needed for consensus as they affect both the block reward and the difficulty calculation.
7. Keeping the PoP chain selection rules makes the hard forking proposal strictly stronger than the soft forking one.
8. It's essentially the same algorithm, only adjusted for 2x faster blocks and include uncles for proper network hashrate estimation.
9. Reward splitting means that orphaning blocks no longer increases malicious miner's rewards (up to the limit of 20 blocks). There is no reward for including uncle blocks because malicious miners will never include them and honest miners have enough incentive through the cumulative difficulty increase that they bring due to being counted in the difficulty adjustment algorithm (a heavier chain is more difficult to reorg, which secures past block rewards waiting to be unlocked).

The exact effect of this proposal (in terms of rewards for a specific attacker strategy) is unclear (pending Monte Carlo simulations), but it should be much closer to a fair distribution.

References

[1] Majority is not Enough: Bitcoin Mining is Vulnerable https://arxiv.org/abs/1311.0243

[2] FruitChains: A Fair Blockchain https://eprint.iacr.org/2016/916

[3] Optimal Reward Allocation via Proportional Splitting https://arxiv.org/abs/2503.10185

[4] One Weird Trick to Stop Selfish Miners: Fresh Bitcoins, A Solution for the Honest Miner. https://eprint.iacr.org/2014/007

[5] Publish or Perish https://www.researchgate.net/publication/312184074_Publish_or_Perish_A_Backward-Compatible_Defense_Against_Selfish_Mining_in_Bitcoin

[6] Lay Down the Common Metrics: Evaluating Proof-of-Work Consensus Protocols' Security https://ieeexplore.ieee.org/document/8835227

[7] #141

[dimagid]

@tevador, thanks for the proposal. How does it mitigate a selfish mining attack that prioritizes discrediting RandomX and destabilizing the network over profit? Specifically, how do the consensus rules (like k=3 and the 1-day coinbase maturity) make such an ideological attack prohibitively expensive and less effective at causing visible disruption, even with external funding?

[tevador]

how do [the proposed changes] make such an ideological attack prohibitively expensive [...]?

I never claimed that this proposal makes attacks prohibitively expensive.

How does it mitigate a selfish mining attack that prioritizes discrediting RandomX and destabilizing the network over profit?

Selfish mining is typically employed for profit. I'd argue that any pool who mines Monero at least partially cares about profits, including the current malicious pool.

But the mitigation stategies described here also help against an irrational attacker who does not care about mining profits. Overall, they would cause less disruption to the network:

1. Malicious reorgs would be much less frequent due to the new fork choice policy. The attacker has to mine 3 more blocks than the honest chain in order to reorg. (This applies to both proposals.)
2. Even if the attacker does reorg, honest pools would typically not lose revenue due to reward splitting. (This only applies to the second proposal.)
3. The attacker would be much less likely to cause a reorg that invalidates transactions, which would have to be 20 blocks deep instead of the current 10 blocks. (This only applies to the second proposal.)

[shortwavesurfer2009]

This would require adjusting the fee back to 0.3 Monero per block, correct?

I think it would also require adjusting the ring signature decoy selection algorithm because currently I believe that's set to deal with 10 blocks as the lock time.

[tevador]

This would require adjusting the fee back to 0.3 Monero per block, correct?

Yes, the block reward would be halved to 0.3 and the penalty free block size would also be halved. I forgot to mention this explicitly.

[tevador]

I think it would also require adjusting the ring signature decoy selection algorithm because currently I believe that's set to deal with 10 blocks as the lock time.

Yes, the wallet side code would need to be adjusted to match the new lock time consensus rule. Note that the decoy selection algorithm itself is not a consensus rule. In any case, decoy selection will go away with FCMP.

[monerobull]

Couldn't an adversary with enough hash add thousands or as many miner addresses in field as they want and distribute the hash-power so each miner_address can still get paid 0.000000000001 XMR and all those ID get added into the chain?

I guess this depends on if this data can be pruned after some time?

[tevador]

Is that on-chain then?

Yes, everything needed for consensus must be on-chain.

If so couldn't this be spammed? Or bloat the chain significantly?

It could be spammed the same way miners can now spam outputs in their coinbase transaction. The only difference is that a spammy block N would force the miner of block N+20 to create a lot of outputs. That could be mitigated by counting the size of the coinbase outputs in the size of block N and not N+20. Additionally, there could be some limit on the number of coinbase outputs per block. A typical block should only have one address in the miner_address field, which is 65 bytes (unless it's mined by p2pool).

(The text above is a reply to a comment that was later deleted.)

I guess this depends on if this data can be pruned after some time?

Yes, both miner_address and uncle_blocks are prunable (i.e. nodes can prune them after verification).

[venture-life]

Thanks @tevador for this proposal. It's very intriguing.
One change not listed yet is probably the relaying of competing in-time blocks (so that uncles are reliably included).

I haven't fully grasped all the parts yet, but once I have them lined up, I will try to simulate the changes and hopefully will lead to the same benchmark numbers from the PoP paper. I'm currently dissecting the implications of 2 branches longer than 2 blocks each. The tips of both won't have any uncles referenced if I understand correctly? Ie, Reward splitting only applies to the first block of each branch from the mutual parent.

Another thing I'm unsure about, is whether the "Perish" part can be recouped if the attacker has a lead of 1 and embeds the the public block once it arrives in his next block template.

[W]eighted FRP addresses the selfish mining problem at the price of sacrificing partition recovery time. In our scheme, previously separated groups of miners would consider blocks mined by the other groups during the partitioned period late and only recognize the weight of their own blocks. Consequently, every group works on its own chain until the first rule in weighted FRP applies.

This quote is from the PoP paper, end of page 13. This seems very similar to the current first-seen rule. It depends on the connectivity of an attacker (gamma). I don't think this paragraph is actually correct in the paper, it should fall back to rule 3 in this case. In our case, deterministic selection. Which seems promising when competing blocks are relayed.

[venture-life]

I think I understand now what they mean by

[...] Consequently, every group works on its own chain until the first rule in weighted FRP applies.

In their simulation, they have segregated the honest miners (1 − α)/2 since there will likely be edge nodes who deems blocks late or in-time differently from the rest. I'm not sure if even in the absence of an malicious entity this might happen considering the higher block frequency (1min). Personally, I like the deterministic selection of a branch in this case.

Edit: Also, is it possible to have two different kind of uncles, eg, in-time uncles affecting the weight and reward-splitting, and late uncles affecting reward splitting only?

[tevador]

One change not listed yet is probably the relaying of competing in-time blocks (so that uncles are reliably included).

I only listed consensus changes. But yes, all valid uncles would be relayed.

I'm currently dissecting the implications of 2 branches longer than 2 blocks each. The tips of both won't have any uncles referenced if I understand correctly?

Depends on if the selfish miner selected "publish" or "perish". If the selfish miner's chain is entirely private, it will have a weight of zero (all blocks are late). If the selfish miner is publishing each block in time, the public chain will have uncles included that will again make it have a higher weight.

Reward splitting only applies to the first block of each branch from the mutual parent.

Reward splitting is orthogonal to PoP. Uncles relevant for RS can be included late (up to 20 blocks later). Uncles relevant for PoP are more narrowly defined.

Another thing I'm unsure about, is whether the "Perish" part can be recouped if the attacker has a lead of 1 and embeds the the public block once it arrives in his next block template.

If the attacker has a private block N+1, once the public N+1 arrives, he can either immediately publish his N+1, in which case it can be included as an uncle by the public chain block N+2, or he can withhold N+1, in which case it won't be counted in the weight of his chain. Both options have the same net effect.

See the PoP Fig. 3 (left side). The only case when the selfish miner wins unconditionally under PoP is when he mines 2 blocks while the honest chain mines 1 block (the SSH case). All other cases depend on tie breaking and will only have a 50% chance of success.

This means that under PoP, there would mostly be 1-block reorgs and 2-block reorgs would only have 50% chance of success. 3-block reorgs or longer would be much less likely because they would require the selfish chain to be 3 blocks longer to skip the PoP weight rule entirely (e.g. the public chain has 3 blocks, the attacker has 6 blocks etc.).

there will likely be edge nodes who deems blocks late or in-time differently from the rest. I'm not sure if even in the absence of an malicious entity this might happen

I think this shouldn't happen if D is set to 2x the maximum block propagation time. Then all honest blocks will always be in time.

E.g.:

At time t, honest node A mines block BA1.
At time t+D/2, honest node B mines block BB1 (just as BA1 arrives). Note that BB1 cannot be mined any later than this because node B will start mining block BB2 immediately after receiving BA1.
At time t+D, node A receives block BB1.

With deterministic selection, at time t+D, all honest nodes will be mining on top of the same block while including the other block as an uncle.

If B is a malicious node, it can release block BB1 later than at t+D/2, which will cause some nodes to deem the block to be late, but I don't think this can benefit the attacker.

Also, is it possible to have two different kind of uncles, eg, in-time uncles affecting the weight and reward-splitting, and late uncles affecting reward splitting only?

This is already included in the proposal. Under the PoP fork choice rule, late blocks have a weight of 0 regardless of any included uncles. Reward splitting doesn't care about late blocks. It comes into effect 20 blocks later when one of the forks had alread won (assuming 20+ block reorgs don't happen).

[venture-life]

Thanks for the input.
IIUC, It's actually quite nice, any block withheld (and matched upon the public finds one), cannot be mined upon efficiently before match since the public chain would incorporate the matched block as an uncle.

If the attacker has a private block N+1, once the public N+1 arrives, he can either immediately publish his N+1, in which case it can be included as an uncle by the public chain block N+2

I hope my follow-ups are constructive. Just to confirm, currently a malicious miner has a better connectivity to some honest miners than they have to the rest. So, for example, if I receive 2 blocks at the same height and both within D, would I know include the second as uncle and mine on the first, or would I rather treat them equally and resort to rule 3, deterministic selection?

[tevador]

So, for example, if I receive 2 blocks at the same height and both within D, would I know include the second as uncle and mine on the first, or would I rather treat them equally and resort to rule 3, deterministic selection?

If both blocks BA1 and BB1 are in time, you will apply the deterministic selection rule, which will tell you e.g. to mine on top of BB1. In that case, you will include BA1 as an uncle block.

[venture-life]

That's really cool. I know you mentioned this earlier already but it's nice to have gone through all the parts working in conjunction. Like, assuming the selfish miner would have won the coin flip, he still couldn't have been mining efficiently before broadcasting, since others would mine (granted on the same tip) with the weight of an uncle :)