4
$\begingroup$

I have some trouble understanding Lamport's paper about the Byzantine generals problem when it comes to signed messages. He showed that, with signed messages, the number of generals must be at least $m+2$ to tolerate $m$ malicious units\faults (for fewer generals, the problem is vacuous).If that's fulfilled it's guaranteed that the loyal generals make the same decision.

Now, I read a lot of papers where at least $2m+1$ generals are needed. The argument in these papers is that the loyal generals have to outnumber the malicious ones to make a majority vote (to get not only the same but the right result). But why isn't it sufficient to have $n \ge m+3$ with three loyal generals for majority vote?

Moreover, if $2m+1$ generals are needed for the majority vote, how can that work with three generals and one traitor? In both cases I need $m+2=3$ and $2m+1=3$ generals and (from what I understand) then I can only agree on the same but not on the correct value (majority vote with two loyal entities?).

I know that I have an error of reasoning here, but I really don't get it. Maybe someone can help me with that problem?

$\endgroup$
2
$\begingroup$

Maybe this is what confuses you -- mixing the byzantine agreement problem (broadcast: where there is one transmitter and multiple receivers) and the byzantine consensus (where every party starts with an input, and if all have the same input, this should also be their output). The bound of at most half traitors stems from the consensus requirement.

Say we have $n$ generals, out of which $t$ are traitors and $\ell=n-t$ are loyal. Assume general $i$ holds the input bit $b_i$

Now assume they all perform a distributed majority vote protocol. Is the protocol guaranteed to succeed? This questions is actually not a well defined. The success of the protocol can be interpreted in two different ways:

  1. All loyal generals output the same answer: $MAJ ( b_1, \ldots, b_n)$
  2. All loyal generals output the same answer: $MAJ (L)$ where $L=\{b_i \mid $ general $i$ is loyal$\}$.

Note that using Lamport's result you mentioned, if $n>t+2$ then all the loyal parties are guaranteed to output the same output even if the traitors misbehave and don't follow the protocol, but which output do they output? Assume $\ell=3$ as you suggest, and assume they all hold the input $0$. The "traitors" can still force the loyal generals to output "1": they just set their input to $1$ and behave honestly! Remember that the loyal parties don't know who is loyal and who isn't (or even if there are traitors at all -- maybe everyone is loyal). From their point of view, there are $t$ votes for "1" and only 3 votes for "0", and since everybody behaves as supposed by the protocol -- the output must be 1! This suits interpretation number (1) above.

Thus, interpretation number (2) above makes sense only for the case where setting the input of the traitors does not affect the majority. A special case is the consensus problem: if all the $\ell$ parties hold (say) "0", we want to guarantee that they all outputs a 0. Of course, if $t>\ell$ then the simple "attack" described above will work. So we need $t<\ell$, or equivalently, $$n=t+\ell \ge t+(t+1)=2t+1.$$

In the most general case of byzantine major-vote, the loyal parties may be split (e.g., $\lfloor \ell/2\rfloor$ votes vs. $\lceil \ell/2\rceil$ votes). In this case, even a single traitor (playing honestly) can determine the result by himself.

$\endgroup$
1
$\begingroup$

According to the paper 1 Generally speaking, Byzantine consensus considers the problem of reaching agreement among a group of n parties, among which up to f can have Byzantine faults and perform arbitrarily. There exist a few variant formulations for the Byzantine consensus problem. Two theoretical formulations are "Byzantine broadcast" and "Byzantine consensus". In Byzantine broadcast, there is a designated sender who tries to broadcast a value. In Byzantine agreement, every party holds an initial input value.

$\endgroup$

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.