| Summary: | 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, <inline-formula> <tex-math notation="LaTeX">$\textit {i.e.}$ </tex-math></inline-formula>, 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, <inline-formula> <tex-math notation="LaTeX">$\textit {e.g.}$ </tex-math></inline-formula>, “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.
|
|---|