Comment by omribahumi

That's cool. Didn't know that bitcoin does this. It sounds like a much better approach.

I guess you can fine tune how complex you want this to be by changing the number of zeros you require.

A friend suggested something else - make the client bruteforce a short RSA key (of say, 100 bits)