Safe(r) Deterministic Tie Breaking

[TierNolan]

When selecting a block to build on, miners are supposed to use these rules.

• Mine on the longest valid chain
• Break ties in favour of the earliest received full block

The problem is that the 2nd rule requires information on when each block was received.

If two blocks are found at around the same time and broadcast, half of the miners would end up seeing each of the blocks first.  The network wouldn't agree on which block is the longest.

Some nodes would see one confirm for transactions in one block and some would see one confirm for transactions in the other block.  

When the next block is found, the tie will likely be broken.

A deterministic way to find break ties means that the entire network will instantly agree on which block to build on.

The problem with this approach is that it can lead to miners withholding some blocks.

If the target was 10 million, then each valid block would have a hash ranging from 0 to 10 million.  If a miner hits a block and gets a low hash (say 1 million), then they can have high confidence that they will be able to win any tie break.

They could hold back their block and release it when someone else sends a new block.  The other person will probably have a hash above 1 million (90% chance), so they will probably win the tie.  

This means that their competitors end up wasting time searching for a block just to lose the tie immediately.

The problem is that miners can tell if the block that they just found is has a good chance of winning the tie break.

This can be avoided by using both hashes to determine the winner.

The strength of a block can be defined as

S_n = [2*H_n - sum(H_k)] mod T

T is the target and H_k is the hash of the kth block involved in the tie.

Each time a new block is added to the set, a random number is effectively added to sum(H_k).  This means that all strengths are effectively re-randomized and all of the blocks involved in the tie have an equal chance of winning.

For the two block case, the strengths are

S₁ = [H₁ - H₂] mod T
S₂ = [H₂ - H₁] mod T

The block with the highest strength wins.

This means that a miner has no way to know if the block that they just found is going to win the tie break.  No matter what the hash of the block, there is always a 50% chance of winning any resulting tie.

[1714676918]

1714676918

[gmaxwell]

50% is still much better than very low change you have on a late broadcast; I believe one of the revised selfish mining attack papers presented something similar to your suggestion (the original one was just busted).


I've thought before to use a similar rerandomization metric but include some sigmoid function of time so that the randomization is decreasingly likely to reorder the blocks the farther apart they are... but I was unable to find something that I felt I could analyize.

    Break ties in favour of the earliest header

No, the earliest received block. If the header's time were used there is trivial attack where you relay the header as fast as possible and withhold the block.

[DumbFruit]

A problem I see with this is that if a miner is missing one of the tie blocks then it's going to come to a different conclusion, whereas if it only picks the one with the hardest difficulty then the network is only depending on all of the miners getting that particular block. It's easier to get one difficult block than it is to make sure you have all of the potentially conflicting forks before running the algorithm.

It also looks like it could be retroactively attacked by adding blocks to the list of "ties" that "happened" in order to get the result it wanted. So instead of getting an advantage by holding a more difficult than usual block, the miner would instead look for more than one block, if he happened to get one faster than usual, and release the amount that would give a result that picks his fork. Though that would generally be really unlikely.

It seems like this would actually make it more difficult to come to a consensus since it can be gamed by picking and choosing, holding and releasing blocks.

Maybe none of that is a problem because blocks are found fairly slow.. I'm not sure.

[tl121]

Safer, maybe.  Safe, impossible.

Bitcoin is a distributed system that lacks central control. This means for bitcoin to operate reliably it must operate asynchronously.  It has been proven that it is impossible to achieve deterministic consensus in asynchronous  distributed systems. This explains why  bitcoin's consensus is non-deterministic. (Actually, it never achieves perfect consensus, with the probability of divergence from apparent consensus decreasing asymptotically to zero as confirmations are added.)

Of course, imperfect consensus is not a problem in the absence of actual double spend attempts.  It is sufficient for bitcoin's consensus to be "good enough" "soon enough" to effectively discourage double spent attempts.

Bitcoin also has the further complication that there is no trust that individual nodes will follow the protocol as designed and implemented.  This brings the discipline of game theory into play along with computer science.

While blocks are found comparatively slowly in relationship to the time it takes to verify them and propagate them, this slowness is contingent on the available computing and communications technology and the parameters of the system, e.g. the maximum block size. 

[Sergio_Demian_Lerner]

Once the network can decide which block is the "right" one, the best strategy for fast near short term global consensus is to allow the block reward to be split between competing blocks. To reward both blocks you need to be able to reference the orphan uncle header in a following block. To incentivize referencing uncles you need a monetary reward. To prevent back-mining you need a penalty (not all money should be split, some must be burned).
A way to do it incentive-compatible is described here:

https://bitslog.wordpress.com/2014/05/02/decor/ (Decor section)

and here:

https://bitslog.wordpress.com/2014/05/07/decor-2/

The Decor+ strategy slightly INCREASES the chance of a 1-confirmation reversal during a short window of time (e.g. 10 seconds) after block arrival, but DECREASES considerably the chances of a >1 confirmation reversal (e.g. from 0.16% down to 0.06%). Also it decreases the chance of 1-confirmation reversal after the 10 seconds window has passed from about 4% (assuming a 50%-50% split, and a 4% orphan rate) to 0.06%.

So even 1/confirmation transactions after 10 seconds are much more secure with Decor+ than without it (taking into account only random reversals, not attacks).

And remember....

GHOST:   Fast Money Grows on Trees, Not Chains
DECOR+: Fast Money Grows on Cooperation, not Competition

What happens if you combine both?

Best regards!
 Sergio.

[TierNolan]

50% is still much better than very low change you have on a late broadcast; I believe one of the revised selfish mining attack papers presented something similar to your suggestion (the original one was just busted).

I can look that up.

I've thought before to use a similar rerandomization metric but include some sigmoid function of time so that the randomization is decreasingly likely to reorder the blocks the farther apart they are... but I was unable to find something that I felt I could analyize.

In most cases, it doesn't matter, since it only changes when a new block enters the tie breaking set.

No, the earliest received block.

Ahh right.

A problem I see with this is that if a miner is missing one of the tie blocks then it's going to come to a different conclusion, whereas if it only picks the one with the hardest difficulty then the network is only depending on all of the miners getting that particular block. It's easier to get one difficult block than it is to make sure you have all of the potentially conflicting forks before running the algorithm.

Creating a block to change the tie break doesn't seem like it would be worth it.  Building a child wins you the tie automatically.

It also looks like it could be retroactively attacked by adding blocks to the list of "ties" that "happened" in order to get the result it wanted. So instead of getting an advantage by holding a more difficult than usual block, the miner would instead look for more than one block, if he happened to get one faster than usual, and release the amount that would give a result that picks his fork. Though that would generally be really unlikely.

Building siblings of blocks you own wouldn't be as efficient as extending your fork.  The sibling gives you the chance of winning the tie, but the child gives you a guarantee (if you find the block in both cases).

It seems like this would actually make it more difficult to come to a consensus since it can be gamed by picking and choosing, holding and releasing blocks.

It is based on the principle that if everyone has the same info, then the will agree on which is the longest chain.

Bitcoin is a distributed system that lacks central control. This means for bitcoin to operate reliably it must operate asynchronously.

I am not suggesting a single central server.

The point is that if everyone has the same info, they will all agree which is the longest chain.

A way to do it incentive-compatible is described here:

https://bitslog.wordpress.com/2014/05/02/decor/ (Decor section)

and here:

https://bitslog.wordpress.com/2014/05/07/decor-2/

Yeah, that is pretty cool, though it is a hard fork, I assume?