Bitcoin White Paper: 4. Proof-of-Work

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proof-of-work system similar to Adam Back's Hash cash [6], rather than newspaper or Usenet posts. The average work required is exponential in the number of zero bits required and can be verified by executing a single hash. The majority decision is represented by the longest chain, which has the greatest proof of work effort invested in it. To modify a past block, an attacker would have toredo the proof of the block and all blocks after it and then catch up with the honest nodes.