Fixing ripple and other byzantine agreement models in the face of sybil attacks

[monsterer]

Byzantine agreement models generally work under the conditions that the number of byzantine failures is less than N, such as (N-1)/3, where N is the number of byzantine nodes.

Unfortunately, although these models do hold under that many 'disagreements' between consensus nodes, the actual cost of disagreeing is zero, so you can easily have the case where N is mostly nodes under the control of a single individual, hence the sybil attack and why most of these models are not generally trust-less.

There are also long range attacks possible whereby a node which is syncing with the network (which is no different to any other node at any time) has no chain selection rule with which to autonomously pick the correct fork to sync with, should it be presented with counterfeit chains.

I propose the following solution to the problem, taking ripple's ledger close consensus as an example:

1) The RNL is discarded completely, nodes participate in a trust free manor
2) Nodes continue to vote for transactions in the closing ledger, but they do so by solving a POW for each transaction
3) Transactions have a cumulative difficulty target, and so does the ledger as a whole, transactions are added to the closing ledger when their target is reached, and the ledger closes when it's overall target is reached
4) Add a chain selection rule which takes the chain with the most amount of work
5) Difficulty adjusts based on network participation
6) Optionally add a voting reward to incentivise participation

This already sounds very like how POW chains work. The main difference is that you can get immediate feedback on transaction confidence, since votes will stream in continuously for transactions (depending on how long it takes to solve a POW vote, of course) while the ledger is being 'closed'. Of course, a 'closed' ledger can still be replaced by one in a chain of greater work, but arguably that is even easier to achieve using trust based byzantine models, when that trust is broken.

[1715028681]

1715028681

[1715028681]

1715028681

[Sukrim]

You only trade the manual selection of an "UNL" (unique node list) to a list that is potentially dominated by the attacker with the most hashing power.

Ripple style consensus has the nice property that there is no way other than a manual systemwide intervention to undo a closed ledger. The price is that it is hard to assess which node(s) might collude or not. This does not 100% require trust, I'd rather call it reputation I guess (but you need to trust that the reputation is earned rightfully).

[monsterer]

You only trade the manual selection of an "UNL" (unique node list) to a list that is potentially dominated by the attacker with the most hashing power.

Ripple style consensus has the nice property that there is no way other than a manual systemwide intervention to undo a closed ledger. The price is that it is hard to assess which node(s) might collude or not. This does not 100% require trust, I'd rather call it reputation I guess (but you need to trust that the reputation is earned rightfully).

You trade a trusted environment which a sybil attack would render compromised for a trustless environment which is sybil attack proof.

[Fuserleer]

...the actual cost of disagreeing is zero...

Agreed in nearly all cases, but this is mitigated somewhat in the eMunie BA model.

Its not free for a node to disagree, as that node has to be present in the current set of network agreed "voting" nodes.  To be in that set, you have to be online and perform work, either by way of real work requests, or challenges to prove you are doing work.

In most cases it "should" discourage all but the most well financed Sybil attackers, and any cost to disagree, is better than no cost at all like most.

Also after some revision of the trust based model we have, we may actually be able to improve the resilience further, but I'll post about that more once the investigations and testing is done.  

For those not in the know:

Ripples consensus can only guard against (n/5)-1 failures (20%), which is quite low considering the importance of the data its protecting.
Stellar's FBA can guard against (n/4)-1 (IIRC) (25%)
Modified RAFT to be BA tolerant can in some cases guard against (n/3)-1 (33%) but has a lot of limitations to achieve it
POW is claimed to have a tolerance of (n/2)-1 (50%).  But there is disagreement on whether this is true or not, with some believing that POW isn't BA tolerant in the true sense.

One concern I had with Ripples model is these UNLs.   Users are free to change them, but most don't, so nearly all client nodes in the network have the same list of UNLs.   This means that an attacker knows exactly who to hit to cause the most disruption.

Your proposal does sound very much like POW, but then that puts Ripple into the "not true BA" camp, because the ledger can be changed by an attacker some time in the future (just as with BTC).

True BA does not allow this, there is (or should be) no way to change history and the data being protected should be append only.

[monsterer]

...the actual cost of disagreeing is zero...

Agreed in nearly all cases, but this is mitigated somewhat in the eMunie BA model.

Its not free for a node to disagree, as that node has to be present in the current set of network agreed "voting" nodes.  To be in that set, you have to be online and perform work, either by way of real work requests, or challenges to prove you are doing work.

Yes, your model is like a POS version of byzantine agreement, where the stake is replaced by trust. So the cost of disagreeing is a constant, rather than zero.

One concern I had with Ripples model is these UNLs.   Users are free to change them, but most don't, so nearly all client nodes in the network have the same list of UNLs.   This means that an attacker knows exactly who to hit to cause the most disruption.

Your proposal does sound very much like POW, but then that puts Ripple into the "not true BA" camp, because the ledger can be changed by an attacker some time in the future (just as with BTC).

True BA does not allow this, there is (or should be) no way to change history and the data being protected should be append only.

As soon as the trust model is broken in byzantine agreement, the ledger is toast at zero cost. In POW you still need to outpace the entire network to replace the best block.

[Fuserleer]

...the actual cost of disagreeing is zero...

Agreed in nearly all cases, but this is mitigated somewhat in the eMunie BA model.

Its not free for a node to disagree, as that node has to be present in the current set of network agreed "voting" nodes.  To be in that set, you have to be online and perform work, either by way of real work requests, or challenges to prove you are doing work.

Yes, your model is like a POS version of byzantine agreement, where the stake is replaced by trust. So the cost of disagreeing is a constant, rather than zero.

One concern I had with Ripples model is these UNLs.   Users are free to change them, but most don't, so nearly all client nodes in the network have the same list of UNLs.   This means that an attacker knows exactly who to hit to cause the most disruption.

Your proposal does sound very much like POW, but then that puts Ripple into the "not true BA" camp, because the ledger can be changed by an attacker some time in the future (just as with BTC).

True BA does not allow this, there is (or should be) no way to change history and the data being protected should be append only.

As soon as the trust model is broken in byzantine agreement, the ledger is toast at zero cost. In POW you still need to outpace the entire network to replace the best block.

Constant cost is better than no cost though.

Its not toast, its still valid up to the point of the failure, at which point no further transactions can be added until honest nodes have the majority again, any transactions before that happens simply fail.

IMO this is MUCH better than always living in fear of a 3rd party producing blocks that undo, 1-2-4-8+ weeks of transactions.  That is the definition of toast.

[monsterer]

Constant cost is better than no cost though.

Its not toast, its still valid up to the point of the failure, at which point no further transactions can be added until honest nodes have the majority again, any transactions before that happens simply fail.

IMO this is MUCH better than always living in fear of a 3rd party producing blocks that undo, 1-2-4-8+ weeks of transactions.  That is the definition of toast.

Constant cost is indeed better than zero cost. For example, this is why Dash's implementation of instant-x is superior to vanillacoin's (constant cost vs zero cost attack). Of course, linear cost is again better than constant cost.

About the ledger being toast - as soon as the trust model is broken, the network can be put on permanent hold (no consensus) for existing nodes, and for new nodes joining the network can be entirely re-written by the byzantine nodes, unless there is some pre-agreed upon set of 'super trust' nodes with which to sync the chain (think the 5 ripple lab's owned nodes).

[Fuserleer]

Constant cost is better than no cost though.

Its not toast, its still valid up to the point of the failure, at which point no further transactions can be added until honest nodes have the majority again, any transactions before that happens simply fail.

IMO this is MUCH better than always living in fear of a 3rd party producing blocks that undo, 1-2-4-8+ weeks of transactions.  That is the definition of toast.

Constant cost is indeed better than zero cost. For example, this is why Dash's implementation of instant-x is superior to vanillacoin's (constant cost vs zero cost attack). Of course, linear cost is again better than constant cost.

About the ledger being toast - as soon as the trust model is broken, the network can be put on permanent hold (no consensus) for existing nodes, and for new nodes joining the network can be entirely re-written by the byzantine nodes, unless there is some pre-agreed upon set of 'super trust' nodes with which to sync the chain (think the 5 ripple lab's owned nodes).

There are some "super nodes" as you put it in the eMunie model that sign the first set of transactions after the genesis (there has to be, as there are no endorsements to create a set). 

They aren't used for resolving sync issues though, not only are they not needed, its pretty lax on the security side of things too.  You then have a set of known nodes to attack to disrupt sync after you've disrupted consensus (assuming you were successful).

I'm personally not much for the Ripple consensus, it strikes me as quite weak, and has a bunch of band-aids on it to patch it up.

[dragons_are_secure]

Picking up the thread on this one -- I'm curious if any of the code developments proposed by the OP for Ripple were done and/or whether other currencies picked up on the change --

[Sukrim]

I doubt it, since the ideas are bad. Tacking on PoW in random places does not make a protocol better.