Public Keys and Proof of Work

There is a concept that has become popular lately in cryto (particularly
crypto currencies) which is called proof of work.

http://en.wikipedia.org/wiki/Proof-of-work_system

The principle behind it is that you can use cryptography to make your
public key 'special' in some predefined way, in order to prove that it was
a very hard key to create.

These special keys are considered valuable (indeed in cryto currencies you
can be rewarded financially for creating one)

However the original idea of proof of work was an anti spam measure.

I wonder if were start using proof of work public keys linked to identity
on the web, what possible formats could we use ... perhaps 6-10 leading 1's?