How Bitcoin Works
Bitcoin is a system for sending value over the Internet between individuals and groups who don't depend on each other or others to not try to cheat the system. This is as opposed to traditional Internet payment systems, which require everyone in a transaction to depend on and trust a bank or payment service and be vulnerable to limitations by that service. In a decentralized system like Bitcoin, there are no specially trusted actors that have the ability to wholly invent, block, limit, or reverse payments. Bitcoin can be sent across borders without limits for example.
This post is meant to explain how Bitcoin works, and why it's designed the way it is. This post is a summary and explanation of the original Bitcoin white-paper and the prerequisite ideas behind it without getting too technical. This description should allow anyone to understand the mechanics of how and why Bitcoin works, without needing any previous knowledge on programming or cryptography.
Asymmetric cryptography allows people to sign messages with a digital signature. Anyone can look at a signed message and verify that the signature could only have been generated by the person who signed it. No one can fake a digital signature from someone else (unless they steal the key from the user's computer, beat the key out of the user, etc). A signature is only valid for the exact version of the message; if someone takes a copy of the signed message and changes the message, then the signature is obviously invalid for that message.
With digital signatures, you can imagine the basis of a decentralized value transfer / ownership tracking system. If everyone agrees that I have one credit, then I can sign a message saying "I give my one credit to Bob", and send that signed message to Bob. Bob can then show other people the signed message I sent him to show that I've signed away my one credit to him. If Bob wants to pay someone, he can sign a message "I give my one credit to Alice", and send both that message and the message I originally sent to Bob to show the valid movement of the credit from me to ultimately her. Everyone agreed I had that credit to start with, so anyone can verify that chain of messages describing the movement of the credit as valid.
However, you run into the double-spending problem now. I can sign a second message that says "I give my one credit to Charlie" and send that signed message to Charlie after I sent the earlier message to Bob. If Bob (or Alice later) compares notes with Charlie, they'll have an awkward situation. Anyone can easily duplicate credits.
The first step Bitcoin takes to combat this is that all transactions are broadcasted publicly. When I sign the message "I give my one credit to Bob", I don't just send that signed message to Bob, but instead I make it public and tell it to everyone I know, and they tell everyone they know, etc. Now if I try to double-spend my credits to Charlie later, everyone will know that I sent my one credit to Bob already, and no one will even pay attention to or relay my attempted double-spent payment message to Charlie. (There are privacy issues to this, though Bitcoin is pseudonymous which helps a lot. You use addresses instead of names in the publicly broadcast transactions, and everyone can have as many different addresses as they want.)
What if I publish the messages "I give my one credit to Bob" and "I give my one credit to Charlie" at the same time? Bob will want to insist that the message giving it to him is the valid one and that the transfer to Charlie is invalid, and Charlie will insist the other way.
(Aside: You might imagine you could try to get everyone to ignore both messages when conflicting messages are published at the same time like that, but there's issues with that. Anyone could reverse a payment to someone by waiting a short amount of time and then announcing a conflicting payment. How do you choose how much time it takes to solidify? And what if I tell half of everyone I know about my transfer attempt to Bob and half of everyone I know about my transfer attempt to Charlie a short while later, and no one can agree on exactly how much time passed in-between those messages?)
Ultimately, one of these conflicting messages has to be agreed on by everyone as the valid message, and everything that conflicts with it is thrown out.
If everyone trusted a single timestamping service that always enforced an order between events (never timestamping two things at the same moment), then everyone could submit their signed payment messages to the timestamping service, and then everyone would always agree that in case of conflicts, they would always check to see which message the timestamping service said came first.
But who could you trust to run the central timestamping service? If a friend of Charlie's ran it, then Charlie could convince them (or try to force them) to say that the transfer to Charlie was the one that came first. Or what happens if the timestamping service shuts down one day? The government might decide that the central service counts as an unlicensed money transmitter and easily force them to stop. Or what if Charlie really hates red-haired people and convinces the timestamping service to outright deny their transactions or only timestamp transactions from them if they pay him a fee? With this system, you're trusting the central timestamping service to run the system. Is there a decentralized and more democratic solution where you don't have to trust a single group like this?
(Aside: If you decide that trusting a central service is allowable, then relying on a timestamping service is not the only choice, and probably is a suboptimal one. Instead, everyone could rely on a central service who just tells you whether the transaction conflicts with anything in the past sent to the service or not, and you don't have to do the publicly-broadcast-all-transactions thing. This specific model can be extended so that payments can still be verified when the senders are anonymous even to the central entity by using a method called blind signatures, but the system still suffers from the issues above about relying on central entities. This system is referred to as a Chaumian digital currency system.)
This is equivalent to the Byzantine Generals' Problem, and Bitcoin's novel solution to this in the context of peer-to-peer applications is where Bitcoin truly innovates.
You could have everyone vote (say every ten minutes) on a message that contains all of the properly signed transactions that they're choosing to honor. Every round of voting always chooses to start out with the transactions decided on in the most recent vote. This forms a chain of voting rounds. People believe in the legitimacy of this chain of voting rounds based on the sum of all of the votes across all of the chain's previous rounds. Every person voting in this round knows the results of the most recent vote, has been personally watching all new transaction messages, ignoring all of the new transactions that conflict with a new transaction they saw come beforehand, and every round they vote for the message containing all of the new transactions they personally believe should be valid based on the order they saw them. (Aside: The vote isn't a majority-wins system, but is actually a lottery where each candidate message of new transactions to incorporate has a chance to win directly proportional to the number of votes it got. This means that it's fine if everyone is voting on slightly different payment sets to include (which is exactly what happens for reasons that are mentioned later). This eliminates the chance of a vote split between many similar choices allowing a small colluding group to easily vote in a fringe candidate. And if a suboptimal candidate wins a round, it's no big issue at all because double-spend attempts are rare (because everyone knows they don't work long-term), no one really trusts payments until they've been voted in for a few rounds anyway, and any missed non-conflicting payments are very likely to be part of the winning candidate message next round. The true value in voting is less about resolving rare double-spend conflicts, but more about adding to the legitimacy of the chain of voting rounds, which cements the history of the system and prevents transactions from being switched for double-spends much later.) After a round of voting ends, everyone forgets the order they personally saw the last round of new transactions come in as, and defers to the results of the vote as to what transactions they trust.
Now whenever someone receives a payment, they wait for a few rounds of voting (aka. confirmations) to pass before they trust that the payment is unlikely to ever be disagreed with in the future. Essentially, this system of voting rounds is a distributed timestamping service that quickly increases its confidence over successive rounds that everyone can agree on.
But how do you do this over the Internet? Anyone could pretend to be a bunch of people (either by using lots of network connections, or by claiming to be relaying many people's votes) and vote any number of times. Bitcoin uses a proof-of-work system as votes. Your number of votes are based on how much computing power you decide to use for voting. Anyone can verify how much computing power your votes had put into them. It's not possible to fake.
There's two problems left: the initial distribution of credits, and the point of voting. If there are no central entities, then where are credits minted to begin with? How does everyone agree who should start out with credits? And why would people bother to spend processor time voting, besides when they're receiving a transaction? If almost no one is voting, then anyone with a lot of processor power can come in at any time and overwhelm the votes to fully control what transactions are counted as valid each round. (If their number of votes is greater than the number of votes of the previous round, then they could even decide to ignore a number of previous rounds, host their own replacement voting rounds that throw out previously agreed-upon transactions, and claim that their chain of voting rounds are more legitimate because it has more votes across it. Everyone participates in the chain with the most votes across all of its past voting rounds, and knows everyone else follows this same rule, so everyone who wants their votes to matter will have no choice but to switch to the attacker's chain of voting rounds and history if the attacker invents their own chain with enough votes faster than any other chain. This is the so-called 51% attack.) It is essential for maintaining the consistency of the history of the system for there to be many voters voting regularly with processor power.
Bitcoin solves both of these problems with one move: voting mints credits and claims the included transaction fees. People who send transactions can choose to include a little extra as a fee which goes where the winning voter decides for it along with a predetermined amount of new credits. (The rate of credit minting is predetermined and decreases over time eventually to zero in order to enforce scarcity. Transactions without fees might get ignored by a lot of voters and therefore take longer to show up in a winning entry.) You're rewarded for showing up with your processor time to vote. The creation of new credits and the distribution of transaction fees is spread between the voters who work the hardest to maintain the system.
(Aside about terminology: In Bitcoin, a completed voting round is called a "block". Every voting round besides the first is dependent on a previous voting round, and this chain is called the "blockchain". Voting using your processor power is called "mining". Voters are "miners". Credits are divisible and called "bitcoins". People who listen for new transactions and relay them to more people (and might not be voting/mining themselves) are often just called "nodes"; this includes everyone who runs the standard Bitcoin-Qt wallet software.)
That is Bitcoin. There's no single central entity you have to depend on or trust to run it. It's an open source decentralized value holding and transfer system.