Its not possible to maintain a rainbow table because the server would specify the string to start with. Server sends "randomstringthatalsoreferencescurrenttime

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.