Verifiably Hard Functions

Computer science tools, particularly cryptographic tools, depend on some underlying function which is difficult to compute. This is of particular relevance recently since cryptocurrency and blockchain protocols utilizing Proofs of Work (PoW) have exploded in popularity. These tools depend on tasking certain users with solving a particular “hard” function, and then rewarding them for it. This little computational puzzle prevents adversaries from generating millions of false accounts and taking an unfairly large portion of the new rewards in the system. This notion of a “hard” function, however, is vague in many parameters. A recent paper dives into the idea of “verifiable” delay functions, in which one player can prove to another that they spent a certain amount of sequential time computing a function without requiring the verifying player to recompute the function. We plan to apply this framework to “memory-hard” functions. Instead of simply requiring some amount of sequential time (which may be vulnerable to time-space tradeoff attacks), memory-hard functions require some intrinsic minimum space x time to compute. These functions are more resistant to specialized hardware in that the speedup in computation time on a specialized circuit is much lower compared to standard functions. A verifiably memory-hard function will provide the basis for a more democratic Proof of Work system, in which specialized mining rigs do not gain significant advantages over general players in the system.