Why doesn't Bitcoin use a tiebreaking rulewhen comparing chains of equal length?

[cunicula]

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?

[1714866360]

1714866360

[1714866360]

1714866360

[1714866360]

1714866360

[1714866360]

1714866360

[Sukrim]

I thought it already looks at the total work being actually done (sum of difficulties of blocks, not just the sum of min_difficulty) instead of just the length of a chain?

[cunicula]

I thought it already looks at the total work being actually done (sum of difficulties of blocks, not just the sum of min_difficulty) instead of just the length of a chain?

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.

[readerbtc]

Hi!

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.

But what happens when a third block arrives with a greater difficulty?

Like that:

chain 1: ... + A1 + B1, work(A1) + work(B1) =X
chain 2: ... + A2 + B2, work(A2) + work(B2) =X

cunicula decides for the chain 2, because work(B2) > work(B1)

Then blocks C1 e C2 arrive, and work(A1) + work(B1) + work(C1) > work(A2) + work(B2) + work(C2) . What if then?

[cunicula]

Hi!

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.

But what happens when a third block arrives with a greater difficulty?

Like that:

chain 1: ... + A1 + B1, work(A1) + work(B1) =X
chain 2: ... + A2 + B2, work(A2) + work(B2) =X

cunicula decides for the chain 2, because work(B2) > work(B1)

Then blocks C1 e C2 arrive, and  work(C1) > work(C2) . What if then?

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.

[readerbtc]

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.

I think I got it now.
As I see, in the current system, the de facto tiebreak rule is "mine on top of the block from the miner that puts more effort on getting his/her blocks across the network, by whatever means he/she has, like increased bandwidth, good network settings for decreasing latency, smaller blocks, etc".

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.

Maybe the de facto rule I wrote in the previous paragraph is intentional, let's see what the others say.

BTW, adding a tiebreaker is a backward compatible change.

So is removing it.

I mean, a miner could decide "I think is best for me to mine on top of B1, even if everybody else is mining on top of B2" edit the source and recompile. And then find a C1 longer than C2, or even before people come up with any C2.

If a lot of people do that, we can go back to the situation of today: the de facto rule I described becomes the new Nash equilibrium.

[QuinnHarris]

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.

[readerbtc]

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.

#agree

[cunicula]

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

[readerbtc]

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

Sad to read that. I am genuinely trying to help. I spent some time thinking about alternative solutions to the problem. To be honest, until now I only thought about an even stronger argument against tiebreaking, but...  

I saw on the other thread you intention was to solve the problem also for proof-of-stake coins. I'll try to think about that too.

[cunicula]

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

Sad to read that. I am genuinely trying to help. I spent some time thinking about alternative solutions to the problem. To be honest, until now I only thought about an even stronger argument against tiebreaking, but...  

I saw on the other thread you intention was to solve the problem also for proof-of-stake coins. I'll try to think about that too.

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.

[readerbtc]

I'll wait. 

[QuinnHarris]

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

Code:

uint256 choose_block(uint256 a, uint256 b, uint256 difficulty)
{
  bool choice = false; // false for lower hash, true for greater hash
  uint256 am = (a + d/4) % difficulty;
  uint256 bm = (b + d/4) % difficulty
  if (a + d/4 >= d)
    choice = b > a || b < am || bm > a || bm < am;
  else
    choice = (b > a && b < am) || (bm > a && bm < am);
  return choice ? (a > b ? a : b) : (a > b ? b : a);
}

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.

[jl777]

I had the same question.

I think the issue is that if there is a metric that gives permanent precedence to one block or another, then it would allow an attacker to create a replacement block for any point in the past beyond whatever checkpoint.

So, clearly any tiebreaker would need to only apply when there are two chains of equal length. Given the same length, both have the same cumulative weight as the nBits is the same for both chains for all blocks, so the PoW sum will be the same. Due to this, a longer chain will have more chain weight than a shorter chain.

It seems that without changing anything in the protocol, if all the miners just adopted any deterministic metric to resolve chains of equal length, then this will have the effect of extending the chain with the highest metric, even though the block is contributing the same amount to the chainweight.

This isnt much of an issue with bitcoin, due to its high difficulty, but for weaker networks having a way to minimize forks would be a good thing, unless there is some horrible attack vector this opens. However, since all miners using the same tiebreaker is within the current protocol, if standardizing a tiebreaker creates an attack vectors, that already exists

[deepceleron]

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.

[TierNolan]

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.

I made that suggestion a few times.  If miners could broadcast near misses, then the network should quickly converge on one of the 2 blocks, when there is a tie.  Even if some miners don't broadcast, the ones that do would give faster convergence.

For deterministic mining, you could use something like

weight_block_n = [sum(all blocks in the tie) + hash_block_n] mod Target

Pick the block with the most weight.  

This makes it so that a miner can't determine if they will win a tie, in advance of the 2nd block being found.  This keeps the incentive to broadcast as quickly as possible.

I am not sure this counts as the selfish mining attack.  I thought that assumed that the attacker had better network connectivity to the victim?  Even a slower miner would win the tie break in this case.

[Tracy_Hu]

If miners could broadcast near misses, then the network should quickly converge on one of the 2 blocks, when there is a tie.  Even if some miners don't broadcast, the ones that do would give faster convergence.

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

For deterministic mining, you could use something like

weight_block_n = [sum(all blocks in the tie) + hash_block_n] mod Target

Pick the block with the most weight.  

This makes it so that a miner can't determine if they will win a tie, in advance of the 2nd block being found.  This keeps the incentive to broadcast as quickly as possible.

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.  

[TierNolan]

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

If there are two or more blocks that are tied, miners could broadcast the headers for child blocks that almost meet the difficulty (say 1/64 of the work required for an actual block).

Whichever block has the most mining support will get more of those mini-blocks built on it.  Miners should break ties in favor of the block with the most mini-blocks.

Mini-blocks don't need to be stored and can be discarded once the next block is found.

It means that by the time the next block is found 100% of the miners will be building on the same block.   Whichever block in the tie gets the first mini-block has a good chance of ending up winning the tie break rule.  By the time 6 mini-blocks are broadcast, there is a very high chance all miners will agree on which block to mine on.

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.

The mod function means that it wraps around, the sum(all blocks in a tie) effectively re-randomizes the ordering when a new block is found.

You have just as much chance of winning with a high hash value as a low hash value.