[koheripbal]

Summary:

1. The input need to be unpredictable. Block N is the seed for block N+1.

2. It needs to be difficult to calculate, yet trivially easy to verify.

3. Difficulty needs to be adjustable.

The only idea I've ever seen that met all three of these criteria was PrimeCoin's usage of calculating certain Cunningham twin primes (which is still of unclear/tiny value).

[imtringued]

4. You cannot make money off of the work being done because the saved money will then be spent on more mining until we hit a 100% non commercial computation equilibrium