How to Prove Work: With Time or Memory

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 types of participants, $\textit {i.e.}$ , provers and verifiers. Provers are asked to solve a computational puzzle, and verifiers need to check the solution’s correctness. A 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, $\textit {e.g.}$ , “ASIC”, which is not generally accessible, let alone the high energy consumption rates. In this work, we turn our eyes back to the original meaning of “proof of work”. Under a trusted setting, we propose a framework and its constructions 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 hardware.

Keywords

• Blockchain
• moderate hard primitives
• proof-of-work