Pebbling and Proofs of Work

      Cynthia Dwork             Moni Naor                 Hoteck Wee 


We investigate methods for providing easy-to-check proofs of computational effort. Originally intended for discouraging spam, the concept has wide applicability as a method for controlling denial of service attacks.  Dwork, Goldberg, and Naor proposed a specific memory-bound function for this purpose and proved an asymptotically tight amortized lower bound on the number of memory accesses any polynomial time bounded adversary must make.  Their function requires a large random table which, crucially, cannot be compressed.

We answer an open question of Dwork et al. by designing a compact representation for the table. The paradox, compressing an incompressible table, is resolved by embedding a time/space tradeoff into the process for constructing the table from its representation.  In particular  we apply the well known connections between pebbling graphs and space complexity.

Postscript , gzipped Postscript , PDF

Recent talk on the subject: ppt

Related On-Line Papers:

Back to On-Line Publications

Back Home