Author

Topic: Detecting and handling forking events (Read 755 times)

legendary
Activity: 1232
Merit: 1094
July 25, 2013, 09:00:48 AM
#4
You probably don't even need to send invalid block headers to anybody.

You just connect to as many nodes as you can and store all block headers. If there is a fork, you will personally detect it and act on it. E.g. if your reimplementation of Bitcoin is buggy, you'll notice it by seeing a lot of fresh blocks that you cannot accept for whatever reason.

Right exactly.  That is why all headers should be forwarded (even if the client .

The "chain" isn't really a chain, it is a tree.  However, normally, the main branch is the only one that is extended.  The tree becomes a single branch with a few small orphan branches.

When a fork happens, there are 2 branches that are being extended.  Headers should be forwarded if they extend the tree, even if they aren't part of the main branch (and even if the blocks they represent are invalid).

I think it is better to give all nodes as much info as possible, rather than hoping that dishonest nodes won't forward the info.
legendary
Activity: 2128
Merit: 1073
July 25, 2013, 08:07:04 AM
#3
Very cool proposal.

If I may suggest one thing: instead of improvising your own confidence measures and decision policies use the existing mathematical apparatus of http://en.wikipedia.org/wiki/T-norm_fuzzy_logics where bool isn't discrete-valued [false,true] but a real value on the unit interval [0,1].

Pretty pictures are here: http://en.wikipedia.org/wiki/T-norm and here: http://en.wikipedia.org/wiki/Construction_of_t-norms , but the point of looking at them is to avoid choosing something that is already known to fail to produce self-consistent results.
full member
Activity: 200
Merit: 104
Software design and user experience.
July 25, 2013, 07:15:45 AM
#2
You probably don't even need to send invalid block headers to anybody. You just connect to as many nodes as you can and store all block headers. If there is a fork, you will personally detect it and act on it. E.g. if your reimplementation of Bitcoin is buggy, you'll notice it by seeing a lot of fresh blocks that you cannot accept for whatever reason.
legendary
Activity: 1232
Merit: 1094
July 25, 2013, 05:51:53 AM
#1
One of the points that is often raised is that bitcoin solves the "distributed consensus problem".

This means that all nodes agree on the rules of the network.

The big failure mode is where a majority of the hashing power mines a fork which a minority of the nodes consider invalid.

This happened during the upgrade to 8.x.

I think that rather than betting everything on preventing it, it would be better to have it fail more gracefully.  This would reduce the emergency nature of the event, give more time for it to be handled, and reduce the risk for users of the network during that time.

An example is where there are 2 forks

Fork A:
75% of miners think it is valid
75% of miners think it is the longest fork

Fork B
100% of miners think it is valid
25% of miners think it is the longest fork

This is considered a critical failure, as some of the network will follow one fork and some will follow the other.

The ideal solution is that all miners switch to fork B, since 100% of miners consider it valid.

Detection

At the moment, nodes can't even detect that the problem is occurring.  Nodes that are on fork A won't forward fork B blocks, since they don't extend the main chain (and vice versa).

As long as there is enough mixing of nodes, the blocks may still be distributed anyway.  If type A nodes and type B nodes separately form 2 connected networks and every node is connected to at least 1 of each type, then the blocks for both forks would still be distributed (but less efficiently).

I think that headers for all forks should be distributed (unless the fork point was ages ago).

So, if a block (or header) is received which extends a branch of the tree that forked off less than 1008 blocks ago, then the header should be forwarded.  If it extends the main chain, then the entire block should be forwarded (as happens now).

Peers might pull the block, once they get the header, if they are newer nodes.

I have suggested elsewhere to allow low POW headers to be broadcast.  This means slightly more network traffic, but gives nodes a more accurate estimate of the amount of hashing power on each fork.

Precautions

The best solution is to prevent the problem happening in the first place.

Pools should be recommended to run all popular versions of the client.  If any of the clients reject a block, then the pool should reject the block (or at least stop building on it).  I think some pools already do this?

If a majority of the hashing power is from pools which implement this policy, then the failure is much less likely to occur.  At least one of the clients will reject fork A, but all will accept fork B, so the pools will add its hashing power to fork B.

The orphan rate will increase, but the type B fork will "win", so all the network will follow the same fork.

The pools could publish the blocks that were rejected and which client had a problem.  The client maintainers would be expected to update their software quickly.

The problem with this is that it doesn't help in a situation where some miners use non-standard software.

Reacting

If a fork is getting a significant portion of the mining power, then the 2 forks could be marked as "live".  The threshold could be 2 blocks long and at least 1 block has been added to the fork within the last 2 hours.  This means a 2 block orphan can stall transactions for 2 hours, so that it likely too strict.

A client could parse the alternative fork, without doing any script checks and scan for transactions.  Unless the other clients messed up SHA256 and/or the transaction format, all clients could check what was spent on the alternative fork.

This means the client can give multiple confirm counts for each transaction.

"Confirmed 6/25" means that it has 6 confirms on the main chain and 25 confirms on the alternative chain.  This indicates that the client is tracking the minority chain, since the "alt" chain has more hashing power than the main chain.

Similarly, 6/D would mean that it has 6 confirms on the main chain but has been double spent on an alternative chain.

The "confirms" total would be the lowest of all live forks.

Miners should scan both forks for transactions and reject any that are double spends. 

This could include rejecting blocks.  However, that opens up double spending problems of its own.

The safest might be to implement a guideline that transactions should not be incorporated into blocks unless they were received at least 5 minutes previously and no double spend for the transaction has been received (double spends would have to be forwarded for that to work).  This rule should activate when a forking event is detected.

Active Reacting

If a miner notices that there are 2 forks, and both are valid, they could switch to the one that is accepted by most of the miners.

It is unclear how best to do this in a distributed manner.

An extra header field could be added so that a miner could indicate which chains are valid.  However, there is an incentive to lie about it, since losing the current chain means loss of coinbase rewards.
Jump to: