Feather-fork: A new type of attack

[Kevlar]

Originally posted here: https://bitcointalk.org/index.php?topic=312668.0

Copied here for further discussion as it relates to Feathercoin.

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 α
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.

[groll]

my reply
[quote]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.[/quote]

in addition : nothing prevent the attacker from adding to claimed bounty to remove the bounty from everyone if they win as he had done with the first transaction bounty. this until he get the block himself. possible if he have some hash also and many rational are competing.

from his conclusion: the OP seems to have just trigger thinking around adding spend at x height. as this can add some weird attack derive from this kind of idea, but not this one.

[wrapper]

Quite mind bending, well done for finding that. Even Litecoin devs are now realising that network security is everything.

My first thought is that we need to enforce miner version(s), but obviously that is difficult (impossible?) to implement and would have to be centralised and is against the general open ethic of the (Satoshi coin) protocol.

The second option is to be open and monitor for “unfair” allocation of funds to particular miners. Again, not perfect, but is my preferred option, as it does not effect the protocol.

On the other hand, Feathercoin does seem to be maintaining a sufficient mining base to make such an attack technically difficult, it might even have to be run by a pool. This could mean community pressure might work to restrict this being implemented.

Maybe, we need a a traffic light system to mark when we are more liable to attack (awaiting bug fix, low Hash rate, known attacker identified). Pools could be “Feathercoin Audited” for using standard / up to date code version, and listed on the forum.

Yellow alert!