The problem is how to achieve agreement (“consensus”) on the truth when at least one person is actively lying and trying to disrupt the truth. In the context of digital money, it’s how you prevent the same coin being spent twice when manipulating digital information is easy.
A related problem is a Sybil attack, where a decentralized peer-to-peer system that is truly open makes it easy to generate new identities and overwhelm the system, so simply relying on the majority of accounts to agree on truth can still be subverted by a motivated attacker.
Bitcoin was a novel solution to this problem by using “mining”, or raw computation power, as a mechanism for enforcing consensus. This made Sybil attacks worthless as the only thing that truly matters in Bitcoin is computation power, which is expensive, and an attacker would need 51% of the power to attack the network.
At the moment, accumulating 51% of the Bitcoin network's hash rate is prohibitely expensive. An attacker would be better off just using that massive hash power to legitimately mine bitcoins. This is the game theory behind bitcoin mining.
Having said that, smaller PoW coins have been recently hit by 51% attacks, as renting the needed hash power for them is cheaper than the profits from selling the double spent coins.
Not too expensive if you're Beijing. 75% of hashpower is centralized within the PRC. All Beijing has to do is inform the miners they now do their bidding. This kind of thing happens all the time in the PRC. The 'community' lost this fight ages ago, at this point Bitcoin effectively operates at the pleasure of Beijing, and one day that may very well change.
Byzantine generals: N generals wish to coordinate their attack on a defending army. The attack will succeed if a majority attack at the same time, so you send messages to the other N-1 generals saying "attack tomorrow at dawn".
But wait: Some of those messages may have been captured by the enemy, and some generals may simply not agree with your strategy. If enough generals don't attack, but you still attack, you will fail. So the new plan is to send a message to the other N-1 generals saying "attack tomorrow at dawn, please reply with confirmation that you will be participate", and then if you get confirmation from at least (N/2 - 1) generals, you can attack with confidence.
But wait: Your fellow generals know that the enemy is potentially capturing messengers, and they won't want to attack if nobody else is attacking, and they know nobody will attack if they don't get the confirmation, so they need confirmation that everyone got their confirmation.
But wait: You'll need confirmation of their confirmation, and so down the rabbit hole we go.
What we end up with is a network of messengers, where every general keeps broadcasting a planned attack date to all the others, but it never able to be certain that the others heard and agreed to it. What's needed to solve this problem is a way of sending a message who's mere existence proves that a majority of generals are committed to the attack, and thus you don't have to reply to the message asking for confirmation that everyone still agrees.
Enter proof of work. What if each general would, upon receipt of the proposed attack date, perform some complex and time consuming calculation; maybe have some poets write a poem in iambic pentameter about the proposed date, and then the first one to finish attachs the poem to the message, and rebroadcasts it? Each time a general receives a new message, they'll take the one with the most poems attached, and start writing a new poem that references the attack date and all previous poems. Fairly soon you'll have a massive chain of dozens of epic poems about the proposed attack date. This tells you a couple of things:
1. All those poems are too much work for one rogue general (or the defending army) to have done. This took the finest minds of the most of the Byzantine general staff to create.
2. And that means that most of the generals must be okay with this plan, because they've spent all week writing poems about it.
3. And most of them must be aware that everyone else is okay with it too, since they've all seen all the poems everyone else saw.
The mere existence of this attack plan, with all of it's self-referentials poems attached, is proof that a consensus attack date exists, and means you're safe to attack, without needing to communicate further.
It's a classic topic of study in the field of distributed systems.
The overarching goal is consensus between agents (e.g servers) over the state of the system.
For example, suppose that you want to achieve atomic consistency (i.e at any point in time the committed/persistent state of the system is homogeneous across all live nodes) in a private cluster replicating a database. The incoming requests are routed randomly to any node in your cluster. You have a synchronization mechanism (a consensus algorithm - like any-Paxos, Raft, Viewstamped Replication etc.) that lets you get this cluster of machines to agree on the state of the database. This is useful if you want fault-tolerance. The synchronization part is the consensus. The agents have to agree on the state-transition.
Now, observe two things:
1. This is a private cluster you own. In other words, you can make all the machines run the same software, trust each other, and assume they act on a best effort basis.
2. The failure model is "fail-stop". If a machine encounters some kind of failure, it won't exhibit arbitrary behavior but rather crash immediately. And you do not consider the case where a machine is taken over and tries to mess with the rest of the cluster in order to violate the desired safety guarantee (atomic consistency).
Obviously, these works if you are a privately own company and can spend resources hardening the parts of your network that are susceptible to be taken over. In a private setting, these assumptions are sufficient even though they are weak and optimistic. In practice, this is not so much an issue.
This falls apart however when you are in an adversarial setting and when your cluster is an open and public network that anyone can join or leave at any point in time. In that model, malicious actors can also show-up and exhibit/fake any kind of failure they want (e.g re-order messages, lie on their internal state, attempt to spoof other agents etc.). In that case, we say the fault-tolerance model is Byzantine. We go one level above in difficulty from the comfortable fail-stop assumption.
That's the gist of what Byzantine fault-tolerance is about. It defines the ability of a distributed system to resist a subset of its network trying to break consensus by any means possible as long as a sufficient majority remains honest.
For years, the major result on Byzantine Fault-Tolerance (BFT) had been a system called PBFT which although innovative and first of its kind, suffered several limitations. One of them was that any node in the network needed to have a complete list of the other nodes in the network, another was high-overhead, and communication complexity.
The innovation of Bitcoin cannot be explained without providing full-context of many different topics (defining asynchronicity, FLP result etc.) but the crux of it is that it offered a way to circumvent these limitations by massaging some of the requirements and cleverly aligning incentives such that you get a system where: 1/ safety is preserved even in an adversarial setting 2/ anyone can join/leave 3/ you get some degree of asynchronicity, 4/ many other things.
I realize this cannot be a satisfactory or exhaustive exposition of all the innovation that Bitcoin introduces but that would turn this comment into x10 its current length.
