Microsoft paper demonstrating Bitcoin is impossible
-
Prior to 2008 it was widely believed that the problem of generating a consensus in a distributed environment was impossible when more than 1/3rd of the participants were conspiring against the rest. This is called the Byzantine General’s problem because it’s frequently phrased as a problem in which generals must coordinate an attack with their deputies using communication channels that can be subverted by spies.
In this paper from Microsoft Research from 1981, they provide a mathematical proof demonstrating why this problem has no solution, and furthermore, CANNOT have a solution.
[url=http://research.microsoft.com/en-us/um/people/lamport/pubs/weak-byz.pdf]http://research.microsoft.com/en-us/um/people/lamport/pubs/weak-byz.pdf[/url]
It’s interesting to note that their hypothetical approach for solving the case of less than 1/3rd has the generals recursively signing each other’s messages as they get passed along in the same way that each new block signs the one prior to it. The fact that Satoshi produced a solution to this problem which raises the attack cost from 33.3% to 51% is nothing short of a feat of logic and mathematics, and it isn’t until you see how other people were thinking about the problem that you can truly appreciate why Satoshi’s solution is so unique and potent.
As a humorous aside, another solution is also presented, but it requires the generals to send an infinite number of messages before arriving at a consensus… Ain’t nobody got time for that!