I've read the whitepaper several times, but I still don't really understand it. It basically relies on cryptographic hashing algorithms to produce unique values which are very hard to find, but easy to validate. The example from their wiki:
We must find a variation on the base string "Hello, world!" + nonce which produces an SHA1 starting with "000".
Quote: ""Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7
...
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9"
Once this value is found, it is then 'verified' by several other computers as a proof of work. Note it is much harder to generate this value than it is to prove it (4251 hashes to generate, 1 hash to prove).
The guy who came up with the idea is an absolute genius, the algorithm is pretty much bullet-proof.
I dabbled around with it a bit when it was starting out and had some fun trying to push my hardware to the limit. It then got quite serious, with people dropping thousands on new rigs with an array of graphics cards and it was basically pointless trying to compete. Nowadays even graphics cards are not efficient enough (power costs are too high for the hashes generated) and FPGAs and custom ASICs are starting to dominate.
