Proof of storage scheme

I'm familiar with client puzzles, where the client performs some work and there is a way to prove to the server that the client has done so.

Is there a way to do this, but where the client's resource is memory (storage) rather than computation (CPU)? In other words, the client ties up some storage for some duration, and there is a way to prove to the server that it has done so. I would like it to be much cheaper for the server to verify than it is for the client to do this work.

The motivation is that this might serve some similar benefits as client puzzles, deterring Sybil attacks with mass denial-of-service, in cases where the clients have a relationship with the server over a period of time -- in a way that hopefully can't be sped up by GPUs, FPGAs, and similar tricks.

I know that we could have the client generate a certain amount of random data and then use schemes for proof-of-retrievability/proof-of-data-possession to let the client prove that it is storing this data for the duration. However, I'm wondering if we can do better in this setting, given that the exact data is not important, we just need a way to show that the client has tied up its memory (the equivalent of conspicuously burning a $1 bill, to prove that you are wealthy). - I did not read the paper, but proofs of space seems to be what you are looking for, see here. – DrLecter Mar 23 '14 at 8:50 What kinds of duration do you have in mind? Minutes? Hours? Days? Months? – John Tromp Oct 23 '15 at 15:58 @JohnTromp, I don't have a specific time period in mind, so a scheme that works for any of those would be interesting -- you pick. :-) – D.W. Oct 23 '15 at 16:15 My Cuckoo Cycle PoW only ties up memory during each attempt at finding a cycle. For that attempt you can set the required memory and get a corresponding runtime (roughly 10 min/GB single threaded), but the probability of finding a cycle of length 42 is only 2.5%, so it would take an expected 40 attempts (400 mins or roughly 7 hours) to find the proof. But in between attemps you can of course use the memory for other things. If you want to stretch the 7 hours to a week, then you could require a chain of 24 proofs, also reducing the variance in the total runtime. – John Tromp Oct 24 '15 at 20:35 1 Answer The paper "Proofs of Space: When Space is of the Essence" proposes a scheme that allows a client to prove that it has read/write access to at least$B$bytes of memory. Basically, the server gives the client a function$f$that requires at least$B$bytes to compute, and the client proves it can compute$f$. The method is complicated and I haven't absorbed all of the machinery. One of the lead developers of Bitcoin has proposed a different scheme, which allows the client to prove that it is "tieing up" a certain amount of space over time. The server can periodically send the client a challenge; if the client can always respond correctly, this proves that the client must have set aside that much space. The idea behind the latter scheme is not too complex. Basically, we form a GGM hash tree: for a complete binary tree of depth$d$, with a random 160-bit seed at the root, and then recursively label all of the nodes of the tree as follows: if a node has label$x$, then its left child has label$H(x||0)$and its right child has label$H(x||1)$, where$H$is a cryptographic hash function. There are$2^d$leaves. Each leaf can be thought of as a pair$(i,x)$, where$i \in \{0,1\}^d$is the index of the leaf (a binary string indicating the path taken from the root to that leaf) and$x$is the label on that leaf. Now sort these pairs on their$x$-values. At any point, the server can challenge the client by picking a random index$i$, computing the label$x$on that leaf (this takes just$d$evaluations of$H$, and can be done by the server, since$H$is publicly known), sending$x$to the client, and asking the client to send back the corresponding index. If the client has been tying up enough space to store all$2^d$records, it can quickly find the corresponding$(i,x)$pair and send back the correct value of$i\$; if it hasn't, it will find it difficult to respond correctly.

-
Nice idea. Merkle trees are poweful. A similar GGM-Merkle tree combination has also been used in redactable signatures to elegantly reduce the size of to be stored randomizers for hiding commitments from hash functions. I would never have thought of this application :) – DrLecter Mar 28 '14 at 23:30