Quote from: torba on August 15, 2013, 12:14:52 AM

...
The nodes then collectively agree that bitcoin#1251262613616 is now under the control of whatever address alice sent to.
...

That's the single hardest thing in distributed systems. It sounds simple, but it was actually believed to be impossible to do in any real fashion. The whole Proof-of-Work/Blockchain scheme is the first practical solution that's been deployed out there.

One way to look at the problem that I think helps a lot is imagine you're a node connecting to the network for the first time. You have 2 connections, 1 of which is honest, the other one is an attacker trying to trick you. How can you tell them apart?

- Connecting to more neighbors isn't going to help you, because making lots of fake nodes is really easy (Sybil attack).
- Just checking that there's a valid series of transactions isn't going to help, because double spends can create 2 alternate histories (Which is why all crypto currency used to have a central authority, which would manage the ordering of transactions).
- Just checking proof of work can expose you to attackers pretending to own coins they don't have, as long as they do enough PoW. (That's the danger of running an SPV node).
- Bitcoin full nodes validate EVERYTHING on their own, and then use the blockchain to determine the network's agreement of what order transactions have occured in.

Making this more efficient/better seems to be very hard. No one's figured out a way that doesn't require a blockchain.