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?
