Primary Investigator:
Jeremiah Blocki

Project Members
Nathan Smearsoll

A Memory-Hard Proof of Work (MHPoW) allows a prover to convince an efficient verifier that the prover invested substantial time and memory on a particular computation. Proofs of Work (PoW) in general are an important construction for distributed consensus and spam-mitigation protocols, but existing constructions rely upon computation time rather than the more egalitarian metric of cumulative memory cost. Previous attempts to define MHPoW have lacked a formal security proof and been vulnerable to attacks. In this work, we formalize a construction of a MHPoW based on the Merkle Tree Proofs framework. We formally prove that our protocol is sound when instantiated with a depth-robust graph. We then give an instantiation of our construct such that, with high probability, any prover which outputs a valid certificate for our construction must have cumulative memory cost at least O(N^2 / log N).