You see, the Matrix itself is the proof-of-work puzzle, formatted for compatibility with the neocortex. The simulation of a circa-1999 metropolis is not just something to keep the humans' brains occupied while they power the machines; its very substance is a cryptographic hashing process in the form of a simulated world, which also explains why everyone has to be in the same Matrix rather than instanced versions. Agent Smith's real job was just to prevent 51% attacks!