Depending on synchrony assumptions and message creation times I am very much inclined to believe that Ripple will need more than three times (3f+1) as many honest and correct nodes to avoid byzantine attacks.
The only attack that would be possible is a denial of service attack though -- causing the network to not reach consensus. And since each node signs all of its proposals with the key by which it's known, it should be obvious which nodes to stop trusting. So to launch this attack, someone goes to all this trouble to build human trust, they maybe stop consensus for some period of time, but then they lose all that trust and have to start over. It seems unlikely anyone would bother.
Now what about network partitioning in the wake of failures? If you have a system with known participants all trying to agree on something you will need a total majority to ensure consensus, else you'll end up with two network partitions both possibly containing different versions of your lovely distributed ledger.
Correct, but everyone will know the network is partitioned because they won't see the validations and proposals they're expecting. A key Ripple concept is this -- if conditions make it such that reliable operation is impossible, don't pretend that everything is fine.
With Bitcoin the average block creation time is around 10 minutes which should give enough time even if a major outage occurs to somehow route information to the other partition. When you are doing transactions in seconds time even a short failure of an important connection (undersea cable is cut etc) may cause a network partition. Now what do you do? let the minority partition wait until it is re-joined?
Exactly. So you get quicker absolute confirmation unless conditions are such that this is not possible. In that case, you don't get quick confirmations, but at least you don't get confirmations that don't actually confirm anything. If Bitcoin has an extended split with mining power on both sides (as it did during the blockchain split), both sides will think they everything is perfectly fine and will see confirmations that appear perfectly normal in all respects.
I am very sceptical about ripple because a) It is complex and complex systems are more prone to contain errors and b) the technical problems are very very far from trivial
Agreed. Ripple is more complex than Bitcoin, has a larger attack surface, and has not had as long to prove itself.
Solving this on a medium scale system (several exchange nodes) may work (look at Group Communication or atomic broadcast algorithms, they solve consensus in such instances)
But thousands of nodes? I am VERY doubtful
Actually, the more nodes, the easier. It does take a bit longer, the consensus time goes up with the log of the number of participants you need to encompass most of the weighted trust, but it's much more robust.
Unfortunately, I'm not sure how useful our consensus algorithm would be for other classes of problems. It might be, but it might not be. We get a lot of simplifications from the fact that we were able to structure the problem we needed to solve specifically to make it easy to solve. For example, all a consensus is really established on is which transactions are going to go in a particular set. If two transactions conflict, to avoid a double spend, you just need to agree which comes first (most of which you can do with a deterministic rule). We've removed a lot of the double spend problem by the design of the ledger and transaction mechanics.
For each transaction any node has seen during a ledger window, the network need only come to consensus on whether or not to try to apply it, and can implicitly agree not to apply it simply by failing to agree to apply it. Everything else is handled by deterministic rules known to all nodes.
This is surprisingly simple because:
1) If there is absolutely no conceivable reason why the transaction should not be included, every honest node will agree to include it.
2) If there is some reason why the transaction should not be included, there is no harm in not including it. (If it's valid, every honest node will see no conceivable reason not to include it in the next round anyway.)
And it doesn't matter if invalid or conflicting transactions get agreed on. The deterministic rules will ensure valid results regardless of which transactions are included or when.