(re-announcing since paper has been substantially improved, and the implementation changed hash function)
Cuckoo Cycle is the first proof of work that does little computation but lots of random accesses to RAM,
making it both CPU and power friendly.
Proofs, of size 42*4=168 byes, are trivially verifiable, using only 1/3 KB.
It can be made to require any desired amount of RAM, e.g. 4GB, which is 32x more than what fits on an ASIC,
and which will send nearly all botnet computers into swap-hell, alerting their owners.
A whitepaper and implementation is available at
https://github.com/tromp/cuckoo
