Proof of work
If you're unfamiliar with the term "hashing", please read the hash article first.
Hashing can be used to prove that a certain amount of computation has been done that corresponds to some piece of data which is called "proof of work". This is simply done by appending the data with an arbitrary number (called a "nonce") that satisfies a particular constraint on the resulting hash. For example the "Hashcash" system (described below) requires that an email message header appended with its nonce has twenty zeros at the start of its binary hash result. Since a hash with many zeros at the beginning is very rare, hundreds of millions of different nonce values will need to be tried before finding such a hash result.
As a concrete example, lets take the sentence, "the quick brown fox jumps over the lazy dog", and find the first number on the end of the sentence that yields a hash starting with four zero. First we start with "the quick brown fox jumps over the lazy dog1" which has an MD5 hash value of e48c7b8bfcdc4efe97e08c43ae387524 which doesn't start with any zeros, so we try "the quick brown fox jumps over the lazy dog2", then 3,4,5 and so on... None of the results start with four zeros until we get all the way up to the number 49609 on the end of the sentence which has a hash value of 0000fc25d6614bf1636577c532e86788. The only way we could possibly find this number (our "nonce") that gave that gives a hash with four leading zeros like this was to keep trying hashes, either randomly or counting in some way, there's no short cut, we had to do the work.
But for someone else to prove that our number 49609 does give these zeros (our nonce is a valid one), they just need to get the hash of "the quick brown fox jumps over the lazy dog49609", which in Linux you can do as follows:
echo "the quick brown fox jumps over the lazy dog49609" | md5sum
Which gives you the following output:
In this same way a piece of data can be accompanied by a proof of work in the form of a nonce, so that a client that wishes to verify that this work has really been done can simply hash the data appended with the nonce value and check if the resulting hash value satisfies the criteria, such as having twenty leading zeros in the case of Hashcash or mining Bitcoin.