The magic part of bitcoin is Proof-of-Work. That's the solution to the core of the problem. That's the essence of decentralization and immutability. We no longer need trusted third parties to process transactions, and more crucially: we don't need authorities to be responsible for monetary policy. Proof-of-work is self-authenticating; there's no faith required. People now have the choice to either go with central planning, or follow a neutral, new, liberty standard.

The second part is digital signatures. The fact that you use private and public keys to prove ownership of fortunes still seems mind blowing to me.