Basic idea of proof-of-work.

  1. I want to prove that I did some amount of computation for ID XYZ.
  2. I hash XYZ + a counter. I count the number of leading 0 bits in the hash.
  3. If the number of 0 bits is greater than the difficulty, I am done.
  4. Otherwise, I increment the counter and try again.

One of the earlier examples of proof-of-work is Hashcash.