Reconstructing Hash Reversal based Proof of Work Schemes

Proof of work schemes use client puzzles to manage limited resources on a server and provide resilience to denial of service attacks. Attacks utilizing GPUs to inflate computational capacity, known as resource inflation, are a novel and powerful threat that dramatically increase the computational disparity between clients. This disparity renders proof of work schemes based on hash reversal ineffective and potentially destructive. This paper examines various such schemes in view of GPU-based attacks and identifies characteristics that allow defense mechanisms to withstand attacks. In particular, we demonstrate that, hash-reversal schemes which adapt solely on server load are ineffective under attack by GPU utilizing adversaries; whereas, hash-reversal schemes which adapt based on client behavior are effective even under GPU based attacks.