On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model

摘要: We study the time- and memory-complexities of problem computing labels multiple randomly selected challenge-nodes in a directed acyclic graph. The w-bit label node is hash its parents, function modeled as random oracle. Specific instances this underlie both proofs space [Dziembowski et al. CRYPTO'15] well popular memory-hard functions like scrypt. As our maini¾?tool, we introduce new notion probabilistic parallel entangled pebbling game, type combinatorial game on graph, which closely related to labeling same graph. As first application framework, prove that for $$\texttt {scrypt} $$scrypt, when underlying invoked n times, cumulative memory complexity CMC recently introduced by Alwen Serbinenko STOC'15 capture amortized memory-hardness adversaries at least $$\varOmega w \cdot n/\log n^2$$Ωwi¾?n/logn2. This bound holds can store many natural e.g., linear combinations, but still not arbitrary thereof. We then quantity, show how sufficiently small upper it conjecture extends $$scrypt hold against adversaries. We also such an solves main open proofs-of-space protocols: namely, establishing time graph nodes given initial kw-bit state reduces tightly black k-node pebbling.