Another attempt to solve the offline chain swap problem (aka the 51% problem)

[kjj]

What if we just made it harder to swap in a new branch of the chain the deeper the branch goes?

The criteria for deciding which of two chains is correct is that the one with the highest difficulty is the real chain.

Say we kept that criteria, only when the number of blocks we would have to replace (call it Y) is a small number, like 4 or 5 (call it X).  Also call the current difficulty D.  But, if Y is greater than X, we require the difference in difficulty between the two branches to be (2 ^ (Y-X) )*D.

Honest block races would still be resolved normally, as long as X was chosen appropriately.
The difficulty of retroactively forking the chain would grow exponentially the further back the fork needed to be to meet the attacker's objectives.

The only downside is that this would introduce a very tiny chance of a network split causing a fork that could not be repaired using ordinary means.  Note that the network split capable of causing this fork would be very, very unlikely, since it would need to be complete, nearly evenly split in terms of hashing power connected to each side of the split, and somewhat long lasting.

[BitterTea]

Does that solve the problem of an attacker controlling more than half the network? They still have a higher probability of finding the next block each time, though I am unsure what % of the entire network's capacity is required to sustain this.

[kjj]

If you have X% of the global hashing power, your probability of keeping ahead of the rest of the network for Y blocks is X^Y.  It vanishes quickly unless you have a huge amount of hashing power, like 95% or more.  That means 20 times more than the rest of the world.  Also, a realtime attack would be very obvious, and could be handled by flap damping.

This is for the attack where they start working, but don't publish their alternate chain until they are far in advance of the rest of the world, effectively reversing all of the transactions in many blocks at once.

[WilliamJohnson]

I'm not sure how it would work:
Say an attacker has 10% more than the current processing power of the legit blockchain, and creates his own blockchain (offline).
When he publishes it, it wouldn't become the accepted blockchain, because the difficulty would be only slightly higher,
but then, the (former) legit blockchain wouldn't be accepted anymore, either (because its difficulty is even lower).

EDIT: I've just learned from this thread that there are "checkpoints" hardcoded in the official client.
Determining which chain got widely accepted first seems like a good solution to determine which one is the legit one.

[kjj]

Yes, but the transactions from the legit chain will now show up, and people will learn of the attack.  And the exponential difficulty rise means that the attacker has a short window to launch his attack, even with unimaginable amounts of hashing power.

A person waiting for a really big transaction can wait something like 30 blocks, and know that unless the attacker has 33 million times as much hashing power as the rest of the planet combined, that transaction will never be reversed.  A day or two would put the attack outside the power of an entity cable of using every particle in the entire universe for his hashing machine.

[MoonShadow]

Determining which chain got widely accepted first seems like a good solution to determine which one is the legit one.

Keep up the research.  There is a mechanism that the protocol uses to determine for itself which chain was first.

also, those checkpoints are hard coded so far.  It's not unreasonable for one or more clients to have an automatic checkpointing method, wherein they will refuse to accept a new chain beyond a certain point; thus forcing a chain split until human users resolve the issue.