3 ms·
This has in fact been known for a long time; Leslie Lamport’s famous 1982 paper “The Byzantine Generals Problem” (link here) contains a description of the algor
by apo 8y ago
This has in fact been known for a long time; Leslie Lamport’s famous 1982 paper “The Byzantine Generals Problem” (link here) contains a description of the algorithm. The following will be my attempt to describe and reformulate the algorithm in a simplified form.
https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html
The link points to Lamport's original formulation of the Byzantine Generals Problem:
https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf https://people.eecs.berkeley.edu/~luca/cs174/byzantine.pdf
Vitalik's explainer doesn't address Sybil attacks at all. Deploying a constellation of nodes all controlled by the same attacker seems like a way to defeat even this protocol.
This was the line of thinking that lead to proof-of-work as described in the Bitcoin white paper.
- api 8y agoI wondered about this too. Vitalik is real, so I'd be curious to read a deeper analysis. With sybil attacks its important to realize there is no upper bound on effort or sophistication. A sybil can use botnets, social engineering, machine learning, etc.
- vitalikbuterin 8y agoThere's an assumption that there's some proof of work or proof of stake (or heck, proof of authority)-based sybil resistance mechanism that prevents anyone from launching a huge pile of nodes. I tend to (and think all Byzantine fault tolerance theorists should) view consensus set selection (where sybil resistance is a key goal) and consensus algorithms as largely separate problems.
- wmf 8y agoThere's an assumption You and I know that, but the press and the public don't and they will run away with crazy headlines. This caveat should really be the first line of the blog post (same for Avalanche).