Deterministic tie breaking of >2 length forks

[TierNolan]

When 2 blocks arrive at around the same time, the rule is to break the tie in favor of the earliest block.

If 2 blocks arrive at the same time, then the tie is broken by the next block.

This means that for around 10 minutes, network hashing power is split over two blocks.

A deterministic tie breaking rule would break the tie in favor of the block with the lowest hash.

This would reduce the number of long duration forks.

If two blocks arrived, then the network would "know" which of the two blocks wins the tie.

The disadvantage of this system is that it allows miners to game the system.

For example, if the target was 1 million and the most recent block hashed to 900,000, then the block would be a valid block.

However, a miner who wanted to double spend a transaction in that block could mine on the blocks parent.  If the miner hit the block, then he would have a random number between 0 and 999,999.  There is a good chance his new block would be able to orphan the current leaf block.

Before:

A <- B(900,000)

After

A <- B(900,000)
    <- B'(600,000)

The remaining miners would recognize B' as the longest chain.

A compromise would be to only engage the rule where the fork is more than 1 block back.

If the 2 candidate blocks have the same parent, then mine on the one that arrived first.  However, if fork point is at the grandparent or before, then mining on the block with the lowest hash.

Code:

Let S be the set of all blocks which tie for highest POW

Let E be the earliest block in S to arrive

Remove from S all blocks that have the same parent as E

Mine on the block in S with lowest hash

If all miners agree on E, then they will pick the same block to build on.

No matter which block a miner picks as E, all miners will agree if there is a grandparent fork.

[Altoidnerd]

If 2 blocks arrive at the same time

The notion of simultaneity is disturbing to me in this context.

If communications were ideal and instantaneous (they aren't), a node would never have a question as to which block it sees first.

Could you explain to me the fundamental limitation for a node to decide the order of block arrivals? That is, the internet-reason that this is even possible for a node to "think" two blocks arrived at the same time?  What limitation does a node have to decide the order of events - where is the bottleneck...the ISP, the software, the big routers ...

I hope my question is clear.

[TierNolan]

Could you explain to me the internet-reason that this is even possible for a node to "think" two blocks arrived at the same time?

I just meant a tie, I concede it was bad phrasing.

If a miner finds a block and no other miner finds another for around 15-30 seconds, then that block will be the only block seen by the network.

Every will simply mine on that block.

A tie is where a miner finds a block before he has a chance to update to the new block.  That gives 2 blocks with the same parent.

Each node will build on the block which that node received first.

Assuming that the leaf block starts as A

A

Two blocks B and B' are found at around the same time, so both miners broadcast their blocks.

There are 2 possible chains

A <- B
A <- B'

If 75% of the nodes saw B first, then 75% build on B and 25% build on B'.

Since they both have the same parent, the block that arrived at the node first will be built on.

There is a chance that 2 more blocks will be found at around the same time.  Assuming they are each built on B and B', then the chains are

A <- B <- C
A <- B' <- C'

At this point, the tie is broken deterministically.

S will be the set of all the tied blocks, so [C, C']

It doesn't matter if a node sets E to be C or C', as neither block has the same parent.

The tie will be broken between C and C' based on which block has the lowest hash.

[Altoidnerd]

Could you explain to me the internet-reason that this is even possible for a node to "think" two blocks arrived at the same time?

There is a chance that 2 more blocks will be found at around the same time.  Assuming they are each built on B and B', then the chains are

A <- B <- C
A <- B' <- C'

All clear.

I think there would be 4 cases at this point,

A <- B <- {C, C'}

A <- B' <- {C',C}

longhand:
A <- B <- C
A <- B <- C'

A <- B' <- C
A <- B' <- C'

[TierNolan]

I think there would be 4 cases at this point,

<snip>

longhand:
A <- B <- C
A <- B <- C'

A <- B' <- C
A <- B' <- C'

However, in all cases, the tie will be broken the same way (lowest hash of C and C').

The rules are so that it smoothly switches from the "earliest block" rule to the "lowest hash" rule.

The only ambiguity would be if there was 2 sets of ties

A <- B <- C
A <- B <- C'

A <- B' <- C''

If C is received earliest, then the choice is between [C and C''].  Likewise, if C' is received earliest, the choice is between [C' and C''].  If C'' is received earliest, the choice is between [C, C' and C'']

[Altoidnerd]

This is pretty interesting.  I'm going to spend some time thinking about this combinatorics problem for the fun of it - I cannot comment on whether this is terribly useful or not.

[TierNolan]

I cannot comment on whether this is terribly useful or not.

Heh, yeah.  If the odds of 2 blocks happening at the same time is 1%, then the odds of it happening twice in a row is only 0.01%, so it wouldn't happen very often either way.

[Altoidnerd]

If you're not lurking the development mailing list, you should be.

[spartacusrex]

I was wondering if this idea could be generalised..

What I mean is, if you had blocks coming in.. continuously..with uneven gaps between them, and all you know is when you received the block & the block hash, and other details pertaining to the contents of the block, could you work out a deterministic way of ordering them.. ? Which would be the same for users across the network who may have received the blocks in a slightly different order to each other ? 

Maybe a block could tell you where it 'thinks' it should be in the order, by using it's timestamp, but that would only be valid if you received it within a certain time range from that point.. A window of validity.

Is there a way to do this.. ?

Assume non-malicious users to start with, then we can try and break the system later..   

[gmaxwell]

A deterministic tie breaking rule would break the tie in favor of the block with the lowest hash.

And would also create a concrete incentive to delay your block announcement when the block you have is a likely winner.

I'm fairly sure this has been proposed before and debunked.

[TierNolan]

And would also create a concrete incentive to delay your block announcement when the block you have is a likely winner.

I'm fairly sure this has been proposed before and debunked.

It is 2 stage.  If all blocks in the tie have the same parent, then the tie is broken in favor of the earliest block.

However, for forks which are more than 1 block deep (so the blocks have different parents), then it breaks to the lowest hash.

The effect is that random forks are very unlikely to grow beyond 2 blocks.