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.
