Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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).

share|improve this question
2  
I did not read the paper, but proofs of space seems to be what you are looking for, see here. –  DrLecter Mar 23 at 8:50

1 Answer 1

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.

share|improve this answer
1  
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 at 23:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.