-

Bitcoin Redlist Attack
======================

Consider the following scenario:

Miners are split in two groups: A and B.
A has adopted redlist Ra, whereas B has adopted redlist Rb.
Let A be the strongest group, meaning that if A and B chase each-other for the longest chain, A will
win.

Now consider a bitcoin public key p, which is on Rb but not on Ra, owned by an attacker Q.
Q can now shut B out of the network: i.e. keep them busy on work that will never make it
into the block-chain.

Q can do so by creating transactions Tq using his private key.
Miners from A will create blocks containing Tq, whereas miners from B will reject Tq and mine blocks
where Tq is NOT included.
This introduces a fork in the chain and A and B will both attempt to uphold their chain for x
blocks.
Because A is the strongest group, B will loose and switch to A after those x blocks are mined.


*--*--*--*--Tq--*--*--*--*--* A's chain
          \
           \
            *---*--*--* B's chain

If another transaction from Q is then in the network, the attack will start from the beginning.
As such, Q can occupy B with useless work.

Discussion
----------

It seems in line with Bitcoin's idea of "consensus" that the redlist with the largest backing group
"wins", i.e. consensus about what transactions should be included in the blockchain is reached by
votes weighted according to CPU power.

But this attack exposes a vulnerability that goes beyond "we don't agree, but have more
computational power"; it exploits the fact that miners will attempt to uphold their chain to
effectively ban them from the pool of miners that contribute to the longest chain.

In effect, two solutions can be considered:

+   All miners accept the same redlist
+   Miners can pick their redlist, but do not reject blocks containing redlisted transactions

The first option is too restricting to be viable from a practical, real-world perspective.
The second option falls when we recognize that there will always be an incentive for miners to mine
redlisted transactions; and there only need be one in order for a transaction to end up in the
block-chain.