Quote from: monsterer on August 25, 2015, 08:05:40 PM

Quote from: Fuserleer on August 25, 2015, 07:13:14 PM

All the honest nodes are in a state of correctness, and will not commit any actions presented by dishonest nodes that attempt to subvert that correctness, because they will all arrive at the same result when presented with that data. Should some data from a dishonest node be accepted, then all honest nodes will retain the state of correctness, because they will all have committed the change from the bad actor.

The network split I was referring to was a not a malicious one, but a topological one. If one group of nodes becomes disconnected from the rest, they will form their own completely valid consensus within their own group, creating a fork. When they re-join the network, the fork will need resolving somehow?

This kind of forking will happen all the time due to network latency, the topological split is the extreme case.

Network topology splits are handled in exactly the same way as malicious actors.

Byzantine agreement protocols can not determine if a node is faulty, or dishonest. Non-response may be for a number of reasons, a node may be faulty and cant not respond, it may be offline, or it may be choosing not to respond as its dishonest.

BA protocols regard all of these cases as a failure, and providing that less than (n/3)-1 failure occur at the same time, an agreement can still be met.

A fork/network partition/split-brain whatever you want to call it doesn't violate or hinder the operation of the majority providing the failure % is within bounds. In the case of a true BA protocol, the split partition may be able to continue operating for a short period of time after the fact, but will not be able to operate indefinitely.

For example:

Assume there is a network of 15 nodes and active traffic.

4 of these nodes suddenly loose communication from the other 11, but can communicate between themselves. These 4 nodes will likely get "stuck" immediately. They are not able to achieve a majority regarding any pending committals as they are not able to receive the votes from the other 11 voters.

Even in the case where there are no committals pending, or active traffic, the split of 4 will be aware that something is amiss upon one of them presenting a new transaction, as the set of nodes those 4 expects to acknowledge the next transaction, 11 will not respond.

While the original network regards the sudden non-response of these nodes as failures, it is below the maximum of (n/3)-1, and can continue operating. The network split containing 4 nodes regards the sudden non-response of 11 nodes as a critical issue as there has been > than (n/3)-1 failures which is easily detectable. That split network can then act accordingly, pausing operation and perhaps even informing users of the sudden critical issue until reconnection to the main network partition.

In this scenario there is no "data fork/split" because the failed group can not proceed unless they all decide to, which in most BA protocols, is not the case. This means that this group can rejoin the main network partition at any point, be given the information they need to achieve data correctness with the majority, and continue operation as before. No rollbacks, no re-organizing.

This IMO is a critical issue that proves block chains & POW are not truly Byzantine tolerant, because there isn't a majority agreement that can prevent changes to history. Bitcoin's use of POW results in an asynchronous network, as there is no mechanism to vote and thus prevent historical changes, and it has been proven that asyncronous networks can not tolerate even 1 Byzantine failure.

In Bitcoin's case the single Byzantine failure is when someone produces a Proof of Work that exceeds the one currently in place. In essence by presenting it, they are disagreeing with the rest of the network about what the state should be, and thus it can be classed as a Byzantine failure.