How is the client expected to proceed ? Should it try a,b, ... aa, ab, ... ? Couldn't a rainbow table allow to cheat with such algorithm ?
It seam that the computation of a MAC or an encryption where the key serves as salt could prevent such cheating. But this computations are now hardcoded in the cpu which won't be the same proof of work for everybody.
Its not possible to maintain a rainbow table because the server would specify the string to start with.
Server sends "randomstringthatalsoreferencescurrenttime"
Client needs to add strings to this such that the MD5 hash of the result has the first N bits as 0 where N specifies the difficulty. The client is expected to send what it added to the server's string and the server verifies the proof of work.
Oh, I left that out of my description. Having the server specify the salt or the text required to be at the front of the value to be hashed does make things better.
It seam that the computation of a MAC or an encryption where the key serves as salt could prevent such cheating. But this computations are now hardcoded in the cpu which won't be the same proof of work for everybody.