Feather-forks: enforcing a blacklist with sub-50% hash power

[socrates1024]

Here are a few variations of a new kind of attack I call a feather-fork, which involves using much less than 50% of the hashpower to influence the network (e.g., to refuse transactions from a blacklisted address). A feather-fork is when a miner refuses to mine on any chain that includes a transaction it doesn't like in the most recent several blocks. You can think of this as a very-soft-fork, or a weak form of blacklisting. As far as I know, this kind of attack has not been discussed previously.

Honest miners running the standard client will build on any valid block, regardless of its contents. A malicious miner that wants to enforce - at any cost - some additional condition (for example, to blacklist transactions from a particular address), might refuse to build on any chain containing a block it doesn't like. However, unless this malicious miner is able to convince half the network to join it, it will find itself on a short end of split, while the rest of the network carries on unaffected. However, I argue that the malicious miner, by refusing to build on this block just for a short time, can create a incentive for other miners to enforce the blacklist as well.

Caveat: The following analysis relies on an assumption that most mining participants are rationally motivated and try to optimize their income. I am imagining that most miners run a hypothetical "RationalMiner" client program, rather than the reference client. These attacks are not possible if more than half of the network are "honest" in the sense that they run the reference client.

1. Two-block feather-fork attack
Suppose a malicious mining entity, BlackPool, with a portion α<1 of the total hashpower (suppose for illustration that α=20%), wishes to blacklist transactions from a particular address. It publicly announces that it will use the following strategy: if a block containing a blacklisted transaction appears, then it will not mine directly on top of it. However, if a second block is found (i.e., the blacklisted transaction has two confirmations), then BlackPool will concede and go ahead on mining on the longest chain.

The key calculation to make is that a fraction α of the network has a chance α² of winning the next two consecutive blocks. In this example, BlackPool with 20% of the network will win the next two blocks 4% of the time. Now consider a miner deciding whether or not to include the blacklisted transaction. If it includes the transaction, it's effective mining rate will be diminished by 4%. On the other hand, the blacklisted transaction carries a large enough fee, then it may still be preferable to include it.

A miner controlling α of the hashpower can use a feather-fork to raise the fee necessary to commit a "blacklisted" transaction to α²U₀, where U₀ is the average reward from a block..

2. Three-block feather-fork attack
Now consider that BlackPool threatens not to mine on top of any chain where a blacklisted transaction shows up in the two most recent blocks.. Now there can be a sort of cascade effect. Even if BlackPool fails to win the next two consecutive blocks, it has some smaller chance of winning three out of the next four. So even if the rational miner finds a block and claims this fee, any subsequent miner would be mining at a lower effective rate to include it. In this circumstance, if every miner is rational, then no rational miner would include blacklisted transaction, regardless of the fee.

It's more realistic to assume that some miners are altruistic or just not alert to BlackPool's plans. If the fee is large enough, then it's worth claiming it and hoping an altruistic miner builds on it and wins the next block.

3. One-block feather-fork attack with payment
BlackPool has a chance α of winning the next block and causing a tie. If there were a way to offer a reward to the miner of the next block, as a way of winning a tie through bribery, then BlackPool could usurp the block with the blacklisted transaction with probably α rather than just α².

However, due to coinbase maturity (outputs from a coinbase transaction can't be spent for 100 blocks), and the lack of a way to make a transactions that are valid only if a particular block is present, it doesn't seem possible to offer such a bribe, at least not directly through the chain. This affects altcoins like Freimarkets, though, which has an OP_BLOCKHEIGHT instruction, because you could make a transaction with OP_HEIGHT in the scriptSig set to the current block height, and an anyone-can-spend transaction output that can be claimed in the next block.

4. A related natural occurrence
Consider the scenario where some user broadcasts a transaction with an anomalously large fee, U₁. Let's say that the chance of winning the next block is α, your proportion of the total power (in hashes/second), and that the typical reward for a block is U₀. Then the expected utility of cooperation (strategy C₀) is (something like):
       E[C₀] = αU₀
In order to earn the enormous reward U₁ (strategy C₁) you'd have to win TWO blocks before the rest of the network wins one:
       E[C₁] = α²U₁
So, in the case that U₁/U₀ ≥ α⁻¹, a rational miner with hashpower α will defect, even if all others cooperate. The larger your share of the hash power, the lower the breakpoint for a prize be to be worth contending over.

Example: Suppose the (fictional) RationalMiningPool accounts for about 33% of the hashpower. A software glitch at MyPHPWebWallet.com results in a submitted transaction with a fee exceeding 75 btc (the typical block reward is only 25 btc). RationalMiningPool does not find the first winning block to include this fee; however, it decides to keep fighting for the big prize, since the chance of finding the next two consecutive solutions is decent and the high value makes it worthwhile.

But defecting isn't an equilibrium either. Since mining is expensive and overall utility might diminish if there is contention rather than consensus, it can be preferable not to play at all. I assume that U₀ is already the competitive price below which a rational miner exits. Is there a cooperative equilibrium? Here's my solution:

A miner with hashpower α (such that U₁/U₀ ≥ α⁻¹)  could safely take a cut of the reward αU₁ for himself, and offer the remaining (1-α)U₁ as a fee for everyone else to fight over next. The reason is that for any miner with hashpower-portion β < 1-α, the value for cooperating in the next round E[C₀'] = β(1-α)U₁ exceeds the value of contending further E[C₁'] = β²U₁.

The "coinbase maturity" rule says that you can't spend mining rewards immediately, instead you have to wait for 100 blocks to elapse. With bounded budgets, a miner that wins the big prize would be unable to offer up the suggested (1-α)U₁ share and therefore this contention would be unavoidable.

Conclusion
Most miners currently run the standard client and do not discriminate between valid blocks. However it's plausible that in the future, mining pools may distinguish themselves by being "rational" and earning more profit by running greedy code. Rules like coinbase maturity (and the lack of opcodes letting you bind transactions to a particular height) affect the interactions between miners of consecutive blocks. In some cases they seem to help consensus, but in others they seem to cause contention. It's worth trying to analyze this more carefully, before an onset of "rational miners" catches us prize.

[1713925614]

1713925614

[1713925614]

1713925614

[gmaxwell]

You can think of this as a very-soft-fork, or a weak form of blacklisting. As far as I know, this kind of attack has not been discussed previously.

Honest miners running the standard client will build on any valid block, regardless of its contents. A malicious miner that wants to enforce - at any cost - some additional condition (for example, to blacklist transactions from a particular address), might refuse to build on any chain containing a block it doesn't like. However, unless this malicious miner is able to convince half the network to join it, it will find itself on a short end of split, while the rest of the network carries on unaffected. However, I argue that the malicious miner, by refusing to build on this block just for a short time, can create a incentive for other miners to enforce the blacklist as well.

We've generally called this block discouragement, and it's been proposed not as an attack but as a safer way to implement some kinds miner behavior shaping. E.g. "discouraging"  blocks that we know reorg the chain, or which do not include transactions (when we know our mempool had many). You can google around for it some.

Your name is better.

[oakpacific]

So even if the rational miner finds a block and claims this fee, any subsequent miner would be mining at a lower effective rate to include it. In this circumstance, if every miner is rational, then no rational miner would include blacklisted transaction, regardless of the fee.

It could be argued that it's also rational behaviour to dislike uncertainty("He is targeting XYZ's payment this time, who will he target next time, maybe me?"), other miners could very well insist on mining at losses of their own effective mining rates to deter rule-breakers, it might also be interesting to see what would happen if a game theory facet is added to the analysis of this attack.

[grau]

Assume a miner dislikes something in the highest block, and is willing to spend on suppressing it.  He mines a parallel block also embedding a transaction sending a bounty to a trivial to redeem script.  All rational miner including him will be incentivized to mine on top of his alternative and claim the bounty for themselves. Only an altruistic miner would remain on the original or include a mempool transaction claiming the bounty.

Added: An unsuccessful attempt to suppress the highest block does not even cost anything, since if not successful the bounty transaction will not be existent in UTXO. A trivial to redeem transaction included by the miner practically adds to the fee offered for the block building on it.

[grau]

It seems to me that mining on the trunk could be even brought to a temporary halt by creating a new orphan block deeper in the chain with a sufficient bounty trivially claimable.

Rational miner would mine on that orphan and leave enough bounty to incentivize the next until the orphan branch catches up with the trunk triggering a re-org that benefits those participated in the attack.

It is above my knowledge of game theory to attempt to formulate, but suspect that with only "rational" miner there is a sufficient bounty to trigger any depth of re-org (within the same difficulty cycle).

[d'aniel]

Assume a miner dislikes something in the highest block, and is willing to spend on suppressing it.  He mines a parallel block also embedding a transaction sending a bounty to a trivial to redeem script.  All rational miner including him will be incentivized to mine on top of his alternative and claim the bounty for themselves. Only an altruistic miner would remain on the original or include a mempool transaction claiming the bounty.

If he broadcasts this transaction, then what's stopping the rest of the miners from just including it in their chain, and claiming the bounty in the same block?

[grau]

Assume a miner dislikes something in the highest block, and is willing to spend on suppressing it.  He mines a parallel block also embedding a transaction sending a bounty to a trivial to redeem script.  All rational miner including him will be incentivized to mine on top of his alternative and claim the bounty for themselves. Only an altruistic miner would remain on the original or include a mempool transaction claiming the bounty.

If he broadcasts this transaction, then what's stopping the rest of the miners from just including it in their chain, and claiming the bounty in the same block?

It could stop them if the transaction is only valid in the orphan. For that the source of the bounty would have to be spent in the disliked trunk. The miner could prepare the attack by broadcasting a spends to his own address. If one of those is included in the block he dislikes, then he has a bounty to offer that is only valid in his branch by spending the source again to a trivial to redeem address in his block.

[d'aniel]

It could stop them if the transaction is only valid in the orphan. For that the source of the bounty would have to be spent in the disliked trunk. The miner could prepare the attack by broadcasting a spends to his own address. If one of those is included in the block he dislikes, then he has a bounty to offer that is only valid in his branch by spending the source again to a trivial to redeem address in his block.

I guess then he'd have to be including such a transaction in every block, just in case, but that's only a couple bucks a day.  OTOH, he'd also have to be able to mine a parallel block pretty much on demand.  He's unlikely to be able to do that.  And this is impossible to repeat indefinitely, so his blacklisted transaction will eventually make it in the chain, will it not?

[grau]

Actually one does not even have to be a miner to launch this attack:

The attacker rolls a Bitcoin holding again and again to new addresses of his own. Once he discovers a block he dislikes, he broadcasts a double spend of his previous roll to a trivially redeemable address.

If the transaction has the sufficient size rational miner will be attracted to create an branch rooted where the transaction was still valid and attempt to re-org to cash in the offered bounty.

Added: He would have to send the double spend to miner directly since ordinary nodes would drop, broadcasting would only work by chance.

[oakpacific]

Assume a miner dislikes something in the highest block, and is willing to spend on suppressing it.  He mines a parallel block also embedding a transaction sending a bounty to a trivial to redeem script.  All rational miner including him will be incentivized to mine on top of his alternative and claim the bounty for themselves. Only an altruistic miner would remain on the original or include a mempool transaction claiming the bounty.

Added: An unsuccessful attempt to suppress the highest block does not even cost anything, since if not successful the bounty transaction will not be existent in UTXO. A trivial to redeem transaction included by the miner practically adds to the fee offered for the block building on it.

If the malicious miner dislikes one transaction in the highest block, just one-up it will only delay, rather than foil his "enemy"'s attempt to send payments, because which transactions get to be included in the blocks afterwards in his alternative chain will still be decided by hashing power, if the malicious miner is willing to spend enough to incentivize all rational miners at every turn to make his enemy unable to send anything, then with such resource he probably should just buy enough hashing power to 51% attack the whole network.

[d'aniel]

Actually one does not even have to be a miner to launch this attack:

The attacker rolls a Bitcoin holding again and again to new addresses of his own. Once he discovers a block he dislikes, he broadcasts a double spend of his previous roll to a trivially redeemable address.

If the transaction has the sufficient size rational miner will be attracted to create an branch rooted where the transaction was still valid and attempt to re-org to cash in the offered bounty.

Then wouldn't the miners who didn't win the bounty just ignore the winner's chain, since they can just work on the honest chain which is just as long, and avoid fucking up Bitcoin?

Sorry if this is getting annoying

[grau]

Actually one does not even have to be a miner to launch this attack:

The attacker rolls a Bitcoin holding again and again to new addresses of his own. Once he discovers a block he dislikes, he broadcasts a double spend of his previous roll to a trivially redeemable address.

If the transaction has the sufficient size rational miner will be attracted to create an branch rooted where the transaction was still valid and attempt to re-org to cash in the offered bounty.

Then wouldn't the miners who didn't win the bounty just ignore the winner's chain, since they can just work on the honest chain which is just as long, and avoid fucking up Bitcoin?

Sorry if this is getting annoying

The winner might issue a new smaller bounty to keep others on his branch, and he also has the chance to mine the next himself as usual.

If the malicious miner dislikes one transaction in the highest block, just one-up it will only delay, rather than foil his "enemy"'s attempt to send payments, because which transactions get to be included in the blocks afterwards...

The attack could be repeated and is final to coin base transactions.

[d'aniel]

The winner might issue a new smaller bounty to keep others on his branch, and he also has the chance to mine the next himself as usual.

This would require the same kind of double spend preparation from the winner that the attacker made, before even knowing about the first bounty, but perhaps rational^TM miners would prepare such double spend bounties at all times just in case.  Seems more realistic that it's the attacker that just broadcasts another prepared bounty after seeing the winner's block (assuming rational^TM miners have decided to overcome the double spend broadcast censorship).

Regarding the long-term repeatability of the attack, I suppose if the attacker was high enough profile with deep enough pockets, they could create a chilling effect without actually having to continually pay bounties in repeating the attack; miners wouldn't dare disobey because they know they'd be made examples of and have their blocks orphaned.

[grau]

I suppose if the attacker was high enough profile with deep enough pockets, they could create a chilling effect without actually having to continually pay bounties in repeating the attack; miners wouldn't dare disobey because they know they'd be made examples of and have their blocks orphaned.

Exactly. The amount of bounties that need to be paid would pale in comparison of censoring power they could create.

[d'aniel]

Exactly. The amount of bounties that need to be paid would pale in comparison of censoring power they could create.

If there were some (hard forking) rule change to address this, I wonder if the network would collectively even agree to it if, for example, it's in response to "legitimate" government censorship.  I bet established businesses trying to stay in said governments' good books would put up some resistance.

Oh well, I ruled out Bitcoin ushering in crypto-anarchy a while ago anyway

[dillpicklechips]

Couldn't miners just turn around and find methods of determining who is doing "feather-forks" and refuse to build on their chain? Given enough miners adding this protection, other miners won't be tempted to do this?

[socrates1024]

Couldn't miners just turn around and find methods of determining who is doing "feather-forks" and refuse to build on their chain? Given enough miners adding this protection, other miners won't be tempted to do this?

You can't necessarily tell who actually wins a block. Many pools publicly take credit for the blocks they mine, but RationalPool might deliberately obscure it as a way of preventing its members from being discriminated against.

[d'aniel]

I suppose if the attacker was high enough profile with deep enough pockets, they could create a chilling effect without actually having to continually pay bounties in repeating the attack; miners wouldn't dare disobey because they know they'd be made examples of and have their blocks orphaned.

Exactly. The amount of bounties that need to be paid would pale in comparison of censoring power they could create.

On second thought, there's a pretty strong asymmetry here working against the attacker.  Suppose he has an organized opponent with an interest in breaking his censorship.  The opponent has accumulated a block of blacklisted transactions which he is willing to pay cU₀ to have included in a block (see OP for definitions).  A failed attempt to mine this block costs him roughly U₀.  But during this attempt, he'd be incrementing a bounty in response to the attacker's, up to cU₀.  If unsuccessful, he loses U₀, but the attacker spends more than cU₀ (the second tie-breaker block also costs money).  To recoup his previous cost, the opponent waits until the value to him of having this block mined has grown by another U₀.  Then he tries again.  The idea is that the opponent would just wait until c is large enough that he is confident his attacker will eventually be wiped out by this repeated attack, then mount it.  If he develops a reputation for success in thwarting the attacker, the chilling effect would then begin to work in the opposite direction, against the attacker.

[dacoinminster]

On second thought, there's a pretty strong asymmetry here working against the attacker.  Suppose he has an organized opponent with an interest in breaking his censorship.  The opponent has accumulated a block of blacklisted transactions which he is willing to pay cU₀ to have included in a block (see OP for definitions).  A failed attempt to mine this block costs him roughly U₀.  But during this attempt, he'd be incrementing a bounty in response to the attacker's, up to cU₀.  If unsuccessful, he loses U₀, but the attacker spends more than cU₀ (the second tie-breaker block also costs money).  To recoup his previous cost, the opponent waits until the value to him of having this block mined has grown by another U₀.  Then he tries again.  The idea is that the opponent would just wait until c is large enough that he is confident his attacker will eventually be wiped out by this repeated attack, then mount it.  If he develops a reputation for success in thwarting the attacker, the chilling effect would then begin to work in the opposite direction, against the attacker.

Awesome insight!

I think d'aniel deserves a title, like "king of thought experiments".

He also helped me a lot with the thought experiments for my own project, and then he altruistically turned over the 3BTC bounty I paid him to gmaxwell.

[groll]

That is interesting, but unlikely to be possible. the transaction will eventually enter the chain else he need to make and sustain a 51% attack

The biggest problem for the attacker is that the block making it longer (mined by rational pool ) is likely to have the orphan transaction and another bounty is needed to orphan this one so every one block need to be orphan, else it just delay the transaction for some blocks as the transaction is just delayed to enter the chain. By doing this it's not invalidate so the attacker need to repeat to keep it from going in and this will be costly.

so if you can't make the 2-3 first example you can't create a chilling effect or even get rational pool software install. even if he can get the rational pool software install: only pool that disclose the block they found would be possible target. miner and rational pool that don't disclose block can change address so only this mining block is in that address and then send to exchange to make it untraceable so chilling is not working on them.

In fact running the rational pool software would be usable to make a double spend with a parallel chain. if enough bounty is put to keep rational pool on the chain and if he has like 20% and the rational pool 33% so he can add his 20% to keep just behind until he reach the confirm required then make an effective 51%. he can then make a 6-10-20 blocks fork just behind the normal chain and then orphan it when it's needed. so running this kind of rational pool software would just make sure your coin is just going to loose value. So no gain to run this as at the end you will loose.