What is Byzantine Agreement?

This was mentioned in a different question. However Wikipedia states it is proven to be unsolvable.

So I would like to know what it is in this context and - since it is unsolvable - what the protocols trying to achieve it are actually doing.

1 Answer

The problem is proven unsolvable if the number $t$ of faulty machines of total $n$ machines have a ratio $t \geq \frac{n}{3}$. So for $t < \frac{n}{3}$ it can be solved. Or it can be solved if the result does not have to be certain agreement but allows some uncertainty (which should be small), which might allow a higher threshold.

• Could you add a small description of how the problem fits in the realm of cryptography? – Elias Apr 12 '17 at 11:48
• The problem itself actually doesn't. But it is relevant in the area of network security and distributed systems. E.g. it's quite important for upper limits on corrupted parties in secure broadcasting schemes and similar constructions. – tylo Apr 12 '17 at 11:58
• But solutions rely on cryptographic techniques then? – Elias Apr 12 '17 at 12:12
• It depends on the underlying network and adversarial model. See this and its references. – fkraiem Apr 12 '17 at 12:16
• @Elias In principle, no. But in practice, you usually need some way for X to convince Y that Z said something and the easiest way to do that is to have everyone know Z's public key and have Z sign what it says. This guarantees that X and Y, if honest, will always agree on what Z said. – David Schwartz Apr 13 '17 at 2:27