1
$\begingroup$

This question follows from my previous one on proofs of space. Proof of space mechanisms rely on the computation of some proof that is easy to verify and requires from the prover an arbitrary amount of space, so that the elaboration of the proof is a way to show that some space was indeed available at the moment of the computation.

For my present purposes, however, a more relaxed and simple solution would be agreeable. Consider a situation where both Alice and Bob have a $K$-bytes storage available, with $K$ in the order of $10^{12}$ and the following happens:

  • Alice sends Bob a random seed.
  • Bob expands the seed to fill the whole $K$ space with a long string (let's call it $X$)
  • Bob then computes $Y = f(X)$, where:
    • The size of $Y$ is also $K$.
    • $f$ takes a very long time to compute (in the order of days).
    • $f$ is sequential, i.e., it cannot be made parallel.
    • The computation of any byte in $Y$ cannot be done significantly more efficiently than computing the whole $Y$.
  • In the meantime, Alice computes the same value on her side.
  • When the computation is completed on Bob's side, Alice sends Bob a list $N \ll K$ of bytes positions $i_0, \ldots, i_{N - 1}$.
  • At this point, Bob has only a few seconds to send back $Y_{i_0}, \ldots, Y_{i_{N - 1}}$.

Once Bob gets to know what bytes is Alice requesting, the time to compute on the go the single values for $Y_{i_0}, \ldots, Y_{i_{N - 1}}$ is too large, and it cannot significantly be reduced since $f$ is natively single-threaded. Therefore if Bob is actually capable of sending back the values, then he had all of them saved (which means, with increasing probability in $N$, that he has filled up at least $p < 1$ space for any $p$.

Now, the issue at hand is obviously the nature of $f$. I thought that $f$ should be some form of hash function whose output is actually $K$ bytes long. It is likely, however, that some more relaxed shuffling and XOR-ing on the bytes of $X$ would be sufficient anyway.

The solution I am thinking about

$K$ is very large, and memory is provided by an actual hard disk, that wears out with random writes and is very slow in accessing random parts of the memory.

Here is what I am currently doing, be $H$ the SHA256 hash of a string, be $M \sim 2^29$ some amount of bytes that could fit in a RAM.

Block splicing

  • Compute $H(X)$, use the first half to get two 64-bit numbers ($a$ and $b$).
  • Be $A = X_{a} X_{a+1} \ldots X_{a + M/2}$, be $B = X_{b + 1} \ldots X_{b + M/2}$, be $C = AB$.
  • Compute the shuffling (see later) $C' = S(C)$.
  • Be $A' = C_0 \ldots C_{M/2}$, be $B' = C_{M/2 + 1} \ldots C_{M - 1}$.
  • Write back $A'$ and $B'$ on $X$: $X_{a + i} = A'_i$, $X_{b + i} = B'_i$.
  • Compute the hash of $C$, genererate $a, b$ from its firt half, go back to step 2 and start over for a sufficiently large number of iterations.

Block shuffling

  • Compute $H(C)$, compute $a, b$ from its first half.
  • Be $A = C_a \ldots C_{a + 15}$, be $B = C_b \ldots C + 15$ be $D = AB$.
  • Compute $D' = H(D)$.
  • Be $A'$ and $B'$ the first half of $D'$ respectively.
  • Write back $A'$ and $B'$ to $C$: $C_{a + i} = A'_i$, $C_{b + i} = B'_i$.
  • Compute $D'' = H(D')$, use its first half to determine new values for $a$ and $b$, go to step 2 and repeat for a sufficiently large number of iterations.

The above algorithm has the advantage of being very gentle on the hard disk, as it reads and writes down blocks in the order of hundreds of MB, but every block is taken randomly and shuffled several times with other blocks. Moreover nothing is aligned, so that for any $i$ in general the final value for $Y_i$ is determined by a very large amount of initial values for $X_i$, so that computing it should require much more time than the few seconds timeout that Alice will allow when checking the results.

What I wonder if there could be some vulnerability to this idea that allows to immediately take a shortcut and compute $Y_i$ for any $i$ in a short time. Is there any known technique of this kind in literature? Any other solution I could look at that takes this same approach, of having one part of heavy computation and another of checking with a very short timeout with respect to the time needed to generate the values?

$\endgroup$
  • $\begingroup$ why do you want to use this trick where Bob "has a few seconds to answer"? Why not simply letting Bob commit to the entire Y with a Merkle tree, and then open the bits asked by Alice? This removes the need to ensure that Bob cannot compute the bit after he received the challenge, as he commits to those bits before receiving the challenges. $\endgroup$ – Geoffroy Couteau Oct 25 '16 at 16:22
  • $\begingroup$ If there was a procedure that allows Bob to compute Y_i in a relatively small space and not crazy time, then Bob could compute the merkle tree by recursion, then save the first L layers of the merkle tree, and when the query incomes, he will only have to compute some K/L values for the leafs of the merkle tree! I thought about using merkle trees as well but I don't seem to be able to figure out a way to prevent this from happening. $\endgroup$ – Matteo Monti Oct 25 '16 at 16:24
  • $\begingroup$ My first solution was just to have Y_i as the solution of a classical proof of work on i, then I used the merkle tree. But Bob could have a first recursion round where he computes the leaves, and so on up to the root of the Merkle tree, then he would save the first levels of the tree and compute on the go the rest requested. $\endgroup$ – Matteo Monti Oct 25 '16 at 16:26
  • $\begingroup$ The problem is that if Y_i can be computed relatively easily, than there is a tradeoff more or less in the form ST = const, which as pointed out in the paper you sent me is quite bad as you can store 1 GB, compute on the go 1000 proofs of work and trick Alice into thinking we have 1 TB. $\endgroup$ – Matteo Monti Oct 25 '16 at 16:27
  • $\begingroup$ What I need is that the time to compute the single Y_i is very very large, but if we partition the whole computation of Y into separate problems we will never make it. For example, if it took one hour to compute independently the single Y_i, Bob will never make it to compute f, since K is very very large. We need a way to make the Y_i very interdependent. $\endgroup$ – Matteo Monti Oct 25 '16 at 16:28

Your Answer

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

Browse other questions tagged or ask your own question.