13

Can somebody tell me why in dbft the threashold is 1/3 for malicious nodes? I mean that seems pretty abitrary. I have no problem if it is abitrary but is it?

Note: I'm not referring to Bitcoin. I chose this Forrm, because there is not game-theory or Antshares/Neo-forum.

3 Answers 3

22

We have a mathematical proof that to tolerate n malicious nodes, you need 2n + 1 good nodes. The full proof is found in G. Bracha and T. Rabin, Optimal Asynchronous Byzantine Agreement, TR#92-15, Computer Science Department, Hebrew University. It's also well known in the industry. It is not possible for an asynchronous system to provide both safety (the guarantee that all non-malicious nodes will eventually agree on what progress was made) and liveness (the ability to continue to make forward progress) with more than this number of malicious failures.

You can trivially ensure safety by simply making no forward progress at all. And you can trivially make forward progress unsafely by just letting each node do whatever they want. Neither of these modes of operation are useful.

Let's take a step back to make this answer more helpful:

Why do you need a distributed agreement algorithm at all? Well, you need one in cases where there is more than one way a system could validly make forward progress and you need all the participants in the system to agree on which one of them.

Consider a simple example: I have $10 in the bank, and I write two $10 checks, one to Alice and one to Bob. Either one alone is valid, but we can't let them both go through.

If we had a central authority, they could just clear whichever one they saw first. But what if we don't want a central authority or don't want a single point of failure? And what if we have potentially malicious participants?

Well, you could just sort the checks after representing them as binary data. But that's where the asynchronous component bites us. When do we sort them? Say I see both checks and sort them. How do I know that one second later I won't see a third check that sorts first? And maybe someone else already saw that one. Ouch!

So, we have the following requirements:

1) Our system is asynchronous.

2) Some participants may be malicious.

3) We want safety, that is, we do not want one honest participant honoring one check and one honest participant honoring the other.

4) We want liveness, that is, it's not fair just saying we never clear any checks. Sure, that's safe, but not useful. We want to be sure that we eventually agree on which checks to clear.

So, now the question arises -- how many dishonest partcipants can we tolerate in our asynchronous system and still guarantee both safety and liveness?

As a simple way to get the gist of the proof, though it is not rigorous:

Suppose we have n nodes of which h are honest and d are dishonest. Obviously, n = h + d. Now the system needs to come to consensus on which of two checks to clear.

Think about the case where all the honest nodes are evenly split about the two directions the system could make forward progress. The malicious nodes could tell all the honest nodes that they agree with them. That would give h/2 + d nodes agreeing on each of two conflicting ways the system could make forward progress.

In this case, the honest nodes must not make forward progress or they will go in different directions, losing safety. Thus, the number of nodes required to agree before we can make forward progress must be greater than half the number of honest nodes plus the number of malicious nodes, or we lose safety.

If we call t the threshold required to make forward progress, that gives us: t > (h/2) + d. This is the requirement for safety.

But the malicious nodes could also fail to agree at all. So the number of nodes required to agree before we can make forward progress must be no more than the number of honest nodes or we lose liveness.

This gives us t <= h. Or h >= t. This is the condition for liveness.

Combining the two results, we get:

h >= t > (h/2) + d
h > (h/2) + d
(h/2) > d
d < (h/2)

Thus the number of faulty nodes we can tolerate is less than half the number of honest nodes. Thus we cannot tolerate 1/3 or more of the nodes being dishonest or we lose either safety or liveness.

22
  • Can you provide a link? Your description could not clearify it for me. I also do not know what is meant by directions. In a peer to peer network there is no direction.
    – Ini
    Aug 30, 2017 at 13:08
  • What do you want to tell me with that?
    – Ini
    Aug 30, 2017 at 13:13
  • 1
    @Invader For formal proof purposes, forward progress is usually defined as ruling out at least one future state of the system that was previously possible. For purposes of a particular algorithm, it's usually defined in an algorithm specific way such as confirming one transaction or whatever. Aug 30, 2017 at 14:13
  • 1
    @Invader Everything doesn't still work fine. It may still work fine or it may fail. There's a statistical chance you're fine and a statistical chance the dishonest nodes will win. PoW sacrifices safety to tolerate more dishonest nodes, and that's a perfectly reasonable choice to make. Apr 27, 2018 at 17:34
  • 1
    @sas Bitcoin isn't secure even if all mining power is honest. Consider, for example, if a network failure splits the network in two. Both sides will produce blocks every 20 minutes on average and both sides will eventually have sufficient confirmations to rely on transactions that could conflict from one side to the other. The applicability of these theoretical results to practical systems is not always simple or direct. Nov 8, 2018 at 17:55
1

According to Wikipedia's article on Byzantine Fault Tolerance, that is only true when messages can be forged. Because showing a solution exists to the whole Byzantine Generals Problem can be reduced to showing a solution would exist to the problem of one General and two Lieutenants, and each Lieutenant wouldn't be able to tell whether the messages they were getting were really from the General or forged by the other Lieutenant.

However, for unforgeable messages (or where forgeries are infeasible) you could have an arbitrary number of traitors. Quote:

"A second solution requires unforgeable message signatures. For security-critical systems, digital signatures (in modern computer systems, this may be achieved in practice using public-key cryptography) can provide Byzantine fault tolerance in the presence of an arbitrary number of traitorous generals."

Source: https://en.m.wikipedia.org/wiki/Byzantine_fault_tolerance

To address the derivation given by @DavidSchwartz for example:

"Think about the case where all the honest nodes are evenly split about the two directions the system could make forward progress. The malicious nodes could tell all the honest nodes that they agree with them. That would give h/2 + d nodes agreeing on each of two conflicting ways the system could make forward progress."

If each honest node only accepted signed communications from others, then by gossiping, the honest nodes would learn of the malicious nodes' duplicity and stop listening to them. An algorithm could theoretically be designed that would automatically maintain both forward progress and liveness in each subset of honest participants, whose connections form a connected graph. (Obviously if their only links are through malicious participants, they cannot get any messages through to each other reliably.)

In the XRP consensus protocol, these signatures do constitute proof of malfeasance by the actual validators. The trick is figuring out how a group can achieve consensus as to who is a validator and who is not. Gossiping proof of malfeasance should be enough to stop an honest node from listening to that validator. As noted in their whitepaper, they value correctness before consensus.

35
  • @DavidSchwartz let me know if I made any mistake here, but I think that unforgeable signatures are a get-out-of-jail-free card allowing both liveness and progress in theory. There may, however, be an additional theoretical result on lower bounds that I (and the editors of the wikipedia article) are not aware of. Dec 6, 2017 at 16:27
  • I've yet to see any scheme proposed that had anything like that capability. Your gossip scheme doesn't work -- you just create a new Byzantine agreement problem of how to know when you're done gossiping. Do you use gossip to solve that agreement problem? Apr 27, 2018 at 22:48
  • No, we simply have the sender of the transaction make a final endorsement before it is posted to the ledger, but after it is signed by a supermajority of validators. If the supermajority is not reached before a timeout (e.g. because of a netsplit) the sender can just submit the transaction to a different group of validators (we implemented sharding by transaction) so maybe that group will come to a consensus first. The sender then simply endorses one approved transaction and ignores the other. This is only possible because the sender has ultimate say over if they want to send something. May 23, 2018 at 23:41
  • I don't see how this helps you. The sender can sign two conflicting transactions if they want to. Say there's a split of honest validators, the dishonest validators sign both ides of the split, and the sender signs both transactions too. The sender already has to be dishonest for a double spend anyway. May 24, 2018 at 8:16
  • If there is a split of honest validators in a consensus group, then at least one of the subgroups after the split won’t be able to achieve a supermajority, and the one that does sign a supermajority (assuming there is one) needs only ONE honest validator to detect that a dishonest validator has given (and signed) two different answers for the whole thing to be rejected by any self-interested recipient. May 25, 2018 at 16:13
1

The intuition here... could two nodes get to the point that the majority (e.g. both nodes) agree? If one of the nodes is malicious, then no, that node can always vote against the honest node.

Could three? Seems like they might - couldn't the two honest nodes figure out who the third dishonest node is? But in fact, they cannot - the dishonest node D can tell honest node A one thing, and honest node B another thing.

Let's say they are trying to agree on the color of the sky.

Honest Node A hears from honest node B: "I think the sky is blue, and node D says the sky is blue too". But A hears from dishonest node D: "I think the sky is red, and node B thinks the sky is red too". What is A gonna believe?

In the case of 4 nodes, if there's only 1 dishonest node, node A would hear two versions of "the sky is blue" and one version of "the sky is red" - so A would go with the sky being blue.

Essentially, if a malicious 1/3rd of the nodes can counteract the vote of an honest 1/3rd... then you need one more node as a tie break. Hence, 3f+1 nodes, where f is the number of dishonest nodes 2f+1 is the number of honest nodes.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.