For some reason I thought that the Byzantine Generals problem was all about coordinated action and TCP handshakes and stuff. I.e. two Byzantine generals are besieging a city from opposite sides. In order to successfully invade it, they have to attack at the same time. General A sends a messenger to General B saying "attack tomorrow at 1 PM". But the messenger might be captured, so General A wants to be sure that General B got the message, because if General A attacks alone he's doomed.
So General B sends a messenger back saying "i got the message!". But now General B is unsure that General A got the return messenger. If the return messenger was captured, General A will think that General B didn't get the original message and will not attack, so if General B attacks, he's doing it alone. General B thus needs to know that General A got the return message. So General A sends a return-return messenger. And General B sends a return-return-return messenger. And on and on and on.
Could you explain further, e.g., why this is a subset of the general Byzantine Generals problem and what the BG problem is exactly? Because both descriptions don't really match the same problem set, as far as I see.
> two generals have to come to a common agreement on whether to attack or retreat, but can communicate only by sending messengers who might never arrive. I stole the idea of the generals and posed the problem in terms of a group of generals, some of whom may be traitors, who have to reach a common decision.
All the "solutions" to the Byzantine Generals Problem required a centralized server of some sort.
Bitcoin was able to solve the problem without a centralized server by using a blockchain. It isn't perfect, but it's good enough to prove consensus.
What makes it possible is the financial incentive to mine or build upon the blockchain.
That's the reason why Lamport et al could not envision a decentralized way to solve the Byzantine Generals Problem--there wasn't a way to tie "money" to proof of work.
Bitcoin solved it with a distributed, massively replicated yet ultimately centralized database. There is only one blockchain, consensus driven, and if you're disconnected from the blockchain you can't participate.
Truly decentralized systems are like BitTorrent or git. There's no singular BitTorrent source, no single server for git. Anyone with a git repo can push/fork/share to their heart's content, even offline, even with other people on isolated networks.
I suppose you could argue that, but it's just semantics.
In the Byzantine Generals Problem the generals are trying to achieve consensus. Their messages to each other need to be stored in a cohesive form, like a log file.
The very definition of the Byzantine Generals Problem requires a single truth center. Call it a centralized database if you will, but the problem needs a single source of truth.
When independently acting miners or mining pools that do not require a centralized host or server to "bless" their contributions to the single source of truth is indeed a decentralized system.
Git and BitTorrent are decentralized too, but they don't have a single source of truth. I may have 100 git repo servers but which copy is the truth? Is Github's copy of master the ONE TRUE master or Bitbucket? Or is it my local repo?
In source control it all works out in the end. The developers come to a consensus of where they will push their work. The maintainer will deploy code to production from one of the many repositories.
But when you're dealing with financial transactions you definitely need to have a single source of truth. It doesn't mean it isn't decentralized to have a single source of truth.
The single truth center is the blockchain. Without that you have nothing.
Git and BitTorrent may not have a single truth center, but they are decentralized and can operate autonomously. Bitcoin cannot. I'd argue it doesn't really solve the generals problem, it just provides a mechanism that can solve it by narrowing the problem down and ignoring some of the ugly edge cases.
A true solution to that problem would work in "offline" mode, that is you don't need a persistent link to some authority to ensure you're working with correct information.
That's not really the threat model - Bitcoin isn't secured by math, but by economics: the cost of outhashing the rest. Bitcoin's natural recentralisation has resulted in a few large mining pools controlling most of the hashing power, with at least one having gone over 50% before already. The maths is still basically fine, but it's the least of the possible issues with Bitcoin.
Bit bitcoin uses SHA256, not SHA1. SHA256 is much more secure.
As an aside, even if SHA256 were vulnerable like SHA1 is (in extremely contrived circumstances) the amount of effort to present an alternative, false block would be harder to pull off than a 51% attack. It would cost billions of dollars and would allow the attacker to do a double spend.
Again, big whoop. Millions of dollars to do a double spend--it's not worth it.
So General B sends a messenger back saying "i got the message!". But now General B is unsure that General A got the return messenger. If the return messenger was captured, General A will think that General B didn't get the original message and will not attack, so if General B attacks, he's doing it alone. General B thus needs to know that General A got the return message. So General A sends a return-return messenger. And General B sends a return-return-return messenger. And on and on and on.