12
$\begingroup$

Alice has bought a brand new hard disk, $K$ (with $K \sim 10^{12}$) bytes in size. She is very happy about her purchase, and tells Bob about it. Bob claims he also bought a $K$ bytes hard disk. Alice doesn't really trust Bob on this, so she asks him to prove his claim:

  • Alice sends Bob an $O(\ln(K))$ sized problem she has generated.
  • The problem can only be solved if one has $K$ bytes of memory.
  • Bob sends back an $O(\ln(K))$ sized solution.
  • Alice verifies the solution.

In particular, there can be two distinct cases:

  • Alice verifies the solution without having to carry out the same operations as Bob (in this case, she doesn't even need to have a $K$-bytes hard disk herself)
  • Alice computes the same solution as Bob on her side, using her own hard disk.

What problem could we use? It is perfectly okay if the nature of the communication between Alice and Bob changes a bit (for example requiring more than a two-way communication is okay), but the communication should never grow in size to something like $\Theta(K)$.

Solutions I tried

(Feel free to skip this section if you don't need inspiration!)

  • Using $\Theta(K)$ communication, Alice could obviously generate $K$ random bytes, send them to Bob and ask him to compute the hash of some subset of them that she will send only after sending the whole payload. (We need the hash of a subset of the data otherwise Bob can compute the hash on the go as he receives the bytes). But this solution is obviously discarded because it requires too much communication.
  • Alice sends a seed, Bob generates random numbers with the seed to fill the $K$ bytes, then he sorts the bytes and computes the hash. However, an $O(K^2)$ (in time) solution exists that will allow Bob to compute the hash by extracting the first, second, third... item by repeatedly re-generating the random numbers. So this doesn't actually prove that Bob has a $K$-bytes hard disk.
  • Alice sends a seed, Bob generates random numbers with the seed to fill the $K$ bytes, then a shuffling procedure is put in place to randomly take small blocks and hash them together, or XOR them, or anything in that fashion, so that after a few iterations each byte depends on every other and it is impossible to compute a partial solution on the go. Alice then asks the hash of a subset of the total result (or even the total hash). This could work, but it has the issue of producing an huge amount of random I/O on the disk, which could actually damage a real-life, non-SSD hard disk.
  • Bob generates a sequence of proofs of work (as in bitcoin mining). Bob then generates a Merkle tree on the sequence and sends the root to Alice. Alice asks for $N$ random proofs of work, and Bob sends back the whole navigation on the Merkle tree from the root to the leaf, Alice verifies everything. However, Bob could just save the first $L$ layers of the Merkle tree, and re-compute on the go all the leafs under the last node memorized. If he stores $10^9$ values, for example, he will just have to recompute $10^3$ leafs, which is feasible on the go.
Improve this question
$\endgroup$
4
  • $\begingroup$ If Alice gives Bob a physical trusted object, like a HSM or fast Smart Card, then the solution in the first bullet can be performed with little communication. Alice puts a secret AES key in the object, and allows it to encipher any block at will, except that for the all-ones block the device permanently disables before the answer is output. Bob is supposed to use the device $K/16$ times to fill the hard disk, with the device used in counter mode, starting from zero; then use it a last time with the all-ones block and send the result to Alice. Alice then proceeds as in the first bullet. $\endgroup$ – fgrieu♦ Oct 25 '16 at 12:53
  • $\begingroup$ What if Bob didn't buy such a disk, but borrowed/rented the equivalent amount of storage from Charlie for a day? $\endgroup$ – ilkkachu Oct 25 '16 at 13:03
  • $\begingroup$ @ilkkachu well of course we have no way to determine the moral relationship Bob has with the hard disk, let's say we just want to check whether or not Bob is in position to use one right now. $\endgroup$ – Matteo Monti Oct 25 '16 at 14:04
  • $\begingroup$ @fgrieu smart but I cannot do it! $\endgroup$ – Matteo Monti Oct 25 '16 at 14:05
6
$\begingroup$

There has been a huge amount of work on related questions in the past years. As Thomas Prest mention, this problem was considered for memory-hard function, which provably (in some idealized models) require some amount of space to be evaluated.

However, MHF alone are only the weakest primitive of this kind; many primitives have been designed that enhance MHFs with other desirable properties, such as efficient verification. What you are looking for is probably best captured by proofs of transient space, where you provably use a given amount of space during a computation, so that the proof can be verified in a time and space considerably smaller (polylogarithmic) than the space used by the prover.

I recommend going through the introduction of this article, which does address your problem and furthermore points to many interesting references if you want to dig the subject a bit. Most constructions use graphs with specific combinatorials properties (such as expander graphs and depth-robust graphs), which imply lower bounds on the hardness of playing a certain game (the pebbling game) on the graph. These lower bounds then translate into bounds on the memory usage in the random oracle model.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Hey Geoffroy, how you doing? I am very surprised, I thought that one couldn't verify a proof of computation using less than a square root of the space, because of this theorem (en.wikipedia.org/wiki/Savitch%27s_theorem). How come it is possible for proofs of transient space? Are they interactive? $\endgroup$ – Thomas Prest Oct 25 '16 at 13:12
  • $\begingroup$ Hey Thomas, I'm doing fine :) What about you? I was not aware of this theorem. The proofs are interactive, but from what I recall, they can be made non-interactive in the ROM. Moreover, all those proofs are in fact arguments: they assume that the prover is computationally bounded (more specifically, that he cannot break the collision resistance of a given hash function). I cannot answer for sure in this case, but in general, using arguments instead of proofs allows to overcome bounds and to get very short communication & computation for the prover. $\endgroup$ – Geoffroy Couteau Oct 25 '16 at 13:20
  • $\begingroup$ I'm doing good too :) Interesting, I guess that interactivity and/or ROM is the key... $\endgroup$ – Thomas Prest Oct 25 '16 at 13:44
  • $\begingroup$ I did guess that it is'nt (actually, my current work focus in part on removing the ROM from standard primitives :)). For me, the core difference is that in a proof, the prover is not assumed to be computationally bounded, whereas in an argument, a computationally unbounded prover could always cheat. $\endgroup$ – Geoffroy Couteau Oct 25 '16 at 14:21
  • $\begingroup$ Wait, so in which case if the prover unbounded? Proof or argument? Anyway, in the protocols we consider the prover is always supposed to be computationally bounded, right? In which case I can only think of interactivity and/or ROM ; in particular, a ROM is spatially unbounded so it might (i'm just guessing here) make Savitch's theorem irrelevant $\endgroup$ – Thomas Prest Oct 25 '16 at 15:03
3
$\begingroup$

I see at least one way of doing what you want to do: memory-hard functions.

Alice just needs to store a value $m$ and its hash $H(m)$, where $H$ is a memory-hard function and where the parameters are scaled so that you cannot compute $H(m)$ unless you are above a certain memory threshold. See e.g. this article which provides a provably memory-hard hash function. Alice would only need to store the short values $m$ and $H(m)$, but someone (possibly Alice) will need to compute $H(m)$ beforehand and send it to Alice.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I read through the scrypt algorithm (en.wikipedia.org/wiki/Scrypt#Algorithm): that's interesting, the problem being that the SMix part will issue an huge amount of random accesses on the hard disk, right? Is this solution somewhat similar to the third point of the solutions I have tried? $\endgroup$ – Matteo Monti Oct 25 '16 at 12:39
  • $\begingroup$ Indeed, when computing H(m), Alice will need a lot of memory at some point. But your proposal seems to be interactive, which scrypt is not. And I am no expert in hard drives but I don't think it would damage your hard drive :) $\endgroup$ – Thomas Prest Oct 25 '16 at 12:51
  • $\begingroup$ Of course SSD won't be damaged, but mechanical hard drives will likely be.. moreover random access is extremely slow, thus computing the whole thing on a hard disk could be heavy.. $\endgroup$ – Matteo Monti Oct 25 '16 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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