I am unable to understand why there is a requirement of 3m+1 generals overall given m traitors. As per my understanding, the steps are as follows:
- Each general decides a strategy and forwards their strategy to all the other ($3m$) generals.
- Each general forwards a vector containing the strategies (of all the other generals they received) to all the generals ($m$)
- Now, each general has a list of vectors corresponding to the vote made by each general and using a majority criteria (majority vote) decides each general's strategy and thus, the strategy that it itself chooses.
If there are $3m+1$ generals then, with $m$ (loyal) generals choosing to 'attack' and $m+1$ (loyal) generals choosing to 'defend' and $m$ traitors, then since every loyal general forwards the message correctly, each of the $m$ 'attacking' generals will receive $m-1 + m$ (from the other 'attacking' generals and the $m$ 'defending' generals) confirmations of attack for all the other $m-1$ 'attacking' generals, similarly $m-1 + m$ confirmations of 'defend' for the strategy adopted by each one of the defending generals. The traitors however can alter either by sending whatever they'd like (different bits) to the attackers and the defenders [send
d for all the defenders and
a for all the attackers, but send conflicting values —
d to the defenders and
a to the attackers — for all the traitors' values], thus making them follow a different plan (defenders will defend, while attackers will attack).
This can't be right, because all the papers and presentations I've gone through state that $3m+1$ with only $m$ traitors will definitely give you the correct solution (all loyal generals follow the same plan). Can anybody go through my understanding, find the flaw and re-explain it to me?
Also, I have understood the $m = 1$ example, it would be nice if someone could explain to me how it fails when $m = 2$ and there are 6 generals and how it succeeds if $m = 2$ and there are 7 generals... I've tried a lot and am stuck.