The most widely known and used proof-of-work is the hashcash cost-function which is used by Bitcoin, and also some anti-spam systems and as an anti-DoS mechanism in a number of other protocols. In the context of anti-spam, a proof of work on the recipients address can be attached to the email in an email header. Legitimate senders will be able to do the work to generate the proof easily (not much work is required for a single email), but mass spam emailers will have difficulty generating the required proofs (which would require huge computational resources).