How to Prove Work: With Time or Memory (Extended Abstract)

Proposed by Dwork and Naor (Crypto’ 92) as an anti-spam technique, proof-of-work is attracting more attention with the boom of cryptocurrencies. A proof-of-work scheme involves two kinds of participants, provers and verifiers. Provers intend to solve a puzzle with a solution, while verifiers are in charge of checking the puzzle’s correctness and solution pair. The widely adopted hash-based construction achieves an optimal gap in computational complexity between provers and verifiers. However, in industry, proof-of-work is done by highly dedicated hardware, e.g., “ASIC”, which is not generally accessible, let alone the high energy consumption rates. In this work, we turn our eyes back on the original meaning of “proof of work”. Under a trusted setting, our proposed framework and its constructions are based on computationally hard problems and the unified definition of hard cryptographic primitives by Biryukov and Perrin (Asiacrypt’ 17). The new framework enables us to have a proof-of-work scheme with time-hardness or memory-hardness while cutting down power consumption and reducing the impact of dedicated hardwares.