It seems like even massive forks could be resolved quickly if there was some rule for picking between chains of equal length.
Why does bitcoin treat all of these chains as equivalent instead of imposing a tie-breaking rule? Is there a rationale for this?

Some background:

I was considering the problem of fork resolution when one block is clearly better than another.
More concretely, I consider a fork with n different chains ranked from 1 to n (1,...,k,...,n). A chain k will dominate chain j if k<j.
Nodes connect to each other at random. If a node with chain j connects to a node with chain k where k<j, then this node will drop chain j and adopt chain k.

In this setup, the time necessary to resolve a fork increases in the log of the number of competing chains. See below for a picture. It comes from solving a set of iterative differential equations. Fun.

Next step would be adding block arrivals that cause chains 2,..., k,..., n to leapfrog into the #1 position.
Faster block arrivals = slower consensus as always, but I think that a tiebreaker for chains of equal length speeds things up.



Is there somewhere I can look for deeper analysis on this issue?

Yes, but if two chains have an equal summed difficulty, they are treated as equal. This doesn't make sense to me.
Why not pick one of the two chains based on some arbitrary metric?
For example, you could use the work submitted on the most recent block as a tiebreaker. Then you wouldn't have to wait until the next block arrives to find out which chain is most likely to win.

Edited your post to reflect my suggestion more accurately.
Then you pick C1.

This misses the point though. If you move towards consensus while waiting for a new block, the likelihood of finding both C1 and C2 and continuing the race would decrease. Instead, miners would focus on creating C2. Ignoring the guy who minted B1, miner compliance with this rule should be a nash equilibrium. Mining C1 would mean updating 2 blocks instead of 1. This would increase latency and the risk of creating an orphan.

The current rule is:
1) pick chain with highest summed difficulty
2) if two chains have equal summed difficulty, pick whichever you saw first.

Basically (2) means give up on consensus until a new block is found.

The modification I suggest only applies to 2. It is a tiebreaker

Cunicula version of 2) if two chains have equal summed difficulty, pick whichever one has more work in the most recently discovered block.

This means that there will always be a unique consensus chain, even when comparing two chains with equal summed difficulty.
I realize that this isn't a big issue for bitcoin. I just want to know if there is a rationale for the current system.
BTW, adding a tiebreaker is a backward compatible change.

There really isn't a reasonable notion of more work done on one block.  A lower proof of work hash value doesn't mean the miner worked harder, it just happened to land on that value.  All output values have an equal probability, but the greater the network difficulty the fewer hash outputs will be accepted.  Under a vast majority of cases each block in equal length chains will be expected to have the same difficulty.

Some have suggested broadcasting lower POW block headers when found, something like 1/64th the current difficulty.  If miners switched to the chain with the most POW headers it should quickly move the network to one chain.

Any scheme that allows a malicious miner who withholds blocks to determine if their chain will be chosen over another can game the network in a way similar to what is described by this recent paper http://arxiv.org/pdf/1311.0243v1.pdf

I think deterministic block choices makes this type of attack even more problematic as it removes the need for the malicious miner to propagate their block faster than the competing block.

But I am not absolutely certain about this.  Need to think this through more.  This is can be tricky to figure out, any scheme you think of to fix one problem seems to cause another.

Sad to see the discussion degenerate into more selfish mining nonsense. Consider the thread closed.

Don't worry about it. Nothing personal. I just spent a long time arguing against selfish mining as a practical concern and don't want to revisit the argument here.
I'll post a new thread when I've added in the mining of new blocks to the model. I've made some progress on this, but there is still work to be done.

The assumption that the selfish miner could propagate their block faster than the rest of the network is a bit contrived.

But, if a deterministic block choice is used that allows the selfish miner to determine if their block is more likely to be chosen over the yet unknown competing block the situation becomes less contrived.

That said, I think this problem can be fixed or at least mitigated by choosing a block choice algorithm that doesn't allow the selfish miner to predict if their block will win.

I had suggested the following approach taking into account the current difficulty on the dev mailing list.

Assuming
a = hash of block A
b = hash of block B
difficulty = current difficulty such that A < difficulty and b < difficulty


Given any hash a you can't know if any other hash value b is more or less likely to be chosen.  There are many other methods like an exclusive or between 1 bit on the hash of the hash value.


I strongly expect if a deterministic block choice is used, this approach is better than just choosing the block with the lowest POW hash value or the chain with the lower POW sum.

That said, I don't think the selfish miner problem is big enough to warrant significant concern and I am not certain any change won't have other problems like the ability for a powerful adversary to cause the network to imprudently reject good blocks.

The network and nodes are relatively stable, we aren't tiebreaking between orphan or attack chains dozens of blocks long. The current rule where the majority decides "the chain I heard about first is the one I trust" is a good way of deciding blocks. It is not uncommon for miners to publish block solutions within seconds of each other due to network latency; orphans happen all the time. "First to get the block published, wins" is thus logically fair and creates the least reorgs.

I don't quiet understand it. Do you mean the network can handle a tie?


When two chains are the same length, with a high probability that they have the same "sum(all blocks in the tie)".

So, according to your formula "weight_block_n = [sum(all blocks in the tie) + hash_block_n] mod Target", the critical part seems to come from the hash value of the head of a chain (i.e. block_n in your formula).

Although an adversary can not know the competing block's hash value, but he can know the one he owns. If the hash value of his block is very large, the probability that other blocks' hash can exceed it is low. According to your formula, the adversary has an advantage if two chains are competing.

On the contrary, if the adversary's hash_block_n is small, it seems the adversary has little incentive to broadcast. I don't understand how the speed to broadcast a block can affect the result.