Scaling Proof-of-Replication for Filecoin Mining

Ben Fisch¹, Joseph Bonneau², Nicola Greco³, and Juan Benet³

¹ Stanford University ² New York University ³ Protocol Labs

Abstract

A proof-of-replication (PoRep) is a proof system that a server can use to demonstrate to a network in a publicly veriable way that it is dedicating unique resources to storing one or more replicas of a data le. While it is not possible for PoReps to guarantee cryptographically that the prover’s storage format is redundant, PoReps do guarantee that:

(a)The prover must be using as much space to produce the proof as replicas it claims to store (it is a proof of space)

(b)The prover can retrieve a committed data le (it is a proof of retrievability)

(c)The prover can use the space to store this le without any overhead

In this sense a PoRep is a useful proof of space. It is uniquely suited to replace proof-ofwork in Nakamoto consensus as a Sybil resistance mechanism, while simultaneously incentivizing and subsidizing the cost of le storage.

Technical report This is a short technical report on our constructions. A more detailed paper is forthcoming with information about our prototype implementation of PoReps.

1 Proofs of Replication

A PoRep operates on arbitrary data D 2f0*;* 1g of up to O(poly()) size for a given security parameter. All algorithms are assumed to operate in the RAM model of computation. Parallel algorithms operate in the PRAM model.

$$ D\in{0,1}^{*} $$

$$ \lambda, $$

$$ O(\mathrm{p o l y}(\lambda)) $$

1. PoRep.Setup(;T)! pp is a one-time setup that takes in a security parameter, time parameter T, and outputs public parameters pp. T determines the challenge-response period.

$$ \lambda, $$

2. PoRep.Preproc(sk;D)! D; ~ is a preprocessing algorithm that may take a secret key sk D along with the data input D and outputs preprocessed data D~ along with its data tag, _D which at least includes the size N = jDj of the data. The preprocessor operates in keyless mode when sk =?.

$$ (s k,D)\to\tilde{D},\tau_{D} $$

$$ \tilde{D} $$

$$ \tau_{D} $$

$$ N=|D| $$

3. PoRep.Replicate(id;; D)! R; aux takes a replica identier id and the preprocessed data D D along with its tag. It outputs a replica R and (compact) auxilliary information D aux which will be an input for the Prove and Verify procedures. (For example, aux could contain a proof about the replication output or a commitment).

$$ (i d,\tau_{D},\tilde{D})\to R $$

$$ \tilde{D} $$

$$ \tau_{D} $$

4. PoRep.Extract(pp;id;R)! D~ on input replica R and identier id outputs the data D~.

$$ \therefore P O R e p.E x t r a c t(p p,i d,R)\rightarrow\dot{D} $$

$$ \tilde{D} $$

5. PoRep.Prove(R; aux*;id;r*)! on input replica R, auxilliary information aux, replica identier id, and challenge r, outputs a proof_id.

$$ (R,\mathsf{a u x},i d,r)\to\pi $$

$$ \pi_{i d} $$

6. PoRep.Poll(aux)! r: This takes as input the auxiliary replica information aux and outputs a public challenge r.

$$ \mathsf{R e e p.P o l l(a u x)}\to r! $$

7. PoRep.Verify(id;_D;r; aux*;)!f0;* 1g on input replica identier id, data tag_D, public challenge r, auxilliary replication information aux, and proof it outputs a decision to accept (1) or reject (0) the proof.

$$ \mathrm {y} \left(i d, \tau_ {D}, r, \mathrm {a u x}, \pi\right)\rightarrow {0, 1 } $$

$$ i d, $$

$$ \tau_{D} $$

$$ \pi $$

$$ r, $$

PoRep interactive protocol These algorithms are used in an interactive protocol as illustrated in Figure 1. The setup (whether a deterministic, trusted, or transparent public setup) is run externally and pp is given as an input to all parties. For each le D, a preprocessor (a special party or the prover when operating in keyless mode, but not the verier) runs (D; ~) PoRep.Preproc(sk;D). The outputs D; ~ are inputs to the prover and to the _D D D verier.

$$ D. $$

$$ \ddot{D},\tau_{D} $$

$$ \tau{boldsymbol}D\ \boldsymbol{} $$

Transparency, public coin, and public veriability A PoRep scheme may involve a trusted one-time setup, in which case PoRep.Setup is run by a trusted party¹ and the output pp is published for all parties to see. A transparent PoRep scheme is one in which the setup does not involve any private information. This trusted setup is an independent, one-time procedure, and the trusted party that runs the setup should have no further involvement in the interactive protocol. The data preprocessor may use a secret-key, but it is not trusted (in particular it may collude with the prover). A secret-key preprocessor only has implications for data retrievability, but not for the security of the publicly veriable data replication (or proof of space). This is an important distinction from previous notions of proof of data replication [6, 27].

-Rational Replication An ideal security goal for PoRep protocols would be to guarantee the following properties, described informally:

Any prover who simultaneously passes verication in k distinct PoRep protocols (under k distinct identities) where the input to PoRep.Replicate is a le D_iin the ith protocol must be storing k independent replicas, one for each D_i, even if several of the les are identical.

$$ D_{i} $$

$$ D_{i} $$

By \storing k independent replicas" we mean that is a k-replication of a le D if the string can be partitioned into k substrings₁;:::;_ksuch that each allow full recovery of the le D. More generally, we say that is a k-replication of a vector of (possibly repeating data blocks)

$$ \tau_{1},...,\tau_{k} $$

$$ \tau $$

¹ As usual, the trusted party can also be replaced with a committee that runs a multi-party computation (MPC) protocol to generate the public parameters

$$ \xleftarrow{\mathrm{R}} $$

$$ r\xleftarrow{\mathtt{R}}\mathsf{P o R e p.P o l l(a u x)} $$

$$ \pi\xleftarrow{\scriptstyle{cal P}}\mathsf{R}e e\mathsf{R}\mathsf{P r}\mathsf{O r v}(R,\mathsf{a u x},i d,r) $$

$$ b\nleftarrow{O}\ {R R e p.e r i n y y}d({i},tau{\tau}_{D},r,\mathsf{a U x},\pi) $$

Figure 1.1: The diagram illustrates the interaction between a prover and verier in a PoRep protocol. The setup and data preprocessing is run externally generating pp PoRep.Setup(;T) and D; ~ _D PoRep.Preproc(sk;D). The challenge-response protocol is timed, and the verier rejects any response that is received more than T time steps after sending the challenge. This is formally captured by requiring PoRep.Prove to run in parallel time at most T. The propogation delay on the communication channel between Prover and Verier is assumed to be nominal in comparison to T.

$$ p p\gets\mathsf{P o R e p.S e t u p}(\lambda,T) $$

$$ \ {\ddot{D}},\tau_{D}\leftarrow $$

$$ T $$

D₁;:::;D_kif can be partitioned into k substrings as above such that for each D_ithere is a unique_ifrom which D_ican be fully recovered. (Note how this is the similar to the denition of an optimal erasure code with rate 1*=k*, yet a weaker requirement as the data in an erasure code can be recovered from any 1*=k* fraction of the bits).

$$ k $$

$$ \tau $$

$$ D_{1},...,D_{k} $$

$$ D_{i} $$

$$ \tau_{i} $$

$$ D_{i} $$

$$ 1/k. $$

$$ 1/k $$

This would imply that if several provers each provide distinct PoReps of the same le then they are each dedicating unique resources² to storing the le. It would also imply that a prover who claims in a single proof to be storing multiple replicas of a le cannot physically deduplicate its storage. Unfortunately, this security property is impossible to achieve in a classical model of interactive computation (that does not include timing bounds on communication³), as we explain next.

Suppose that the PoRep adversary stores the replicas in a string. The adversary can then \sabotage" the replication by using say the rst bits of as a key to encrypt the rest, and store 0 the transformed string that includes the bit key and ciphertext. Since the adversary can 0 eciently decode from it will still pass the protocol with the same success probability (i.e.

$$ {sigma}{,}} $$

$$ \sigma^{\prime} $$

$$ \sigma^{\prime} $$

$$ \sigma $$

² The provers may be storing all the replicas on the same hard-drive, hence PoReps alone do not give a meaningful guarantee of fault-tolerant data storage.

Figure 1.2: Space-time diagram of the PoRep protocol. Following a phase of length t_initduring which the prover generates a new replica, the verier repeatedly challenges the prover to produce a PoRep within a challenge time period length T in order to verify that the prover is still storing the unique replica of the original data. For this proof system to be sound it is necessary that t_init>> T.

$$ t_{\mathrm{i n i t}} $$

$$ t_{\mathsf{i n i t}}>>T $$

0 it eciently decodes and retrieves, and then follows whatever protocol behavior it would have initially on). Indeed, such \scrambling" attacks are impossible to prevent as there is always a trivially fast way to encode/decode one’s state in a way that destroys the k-replication format.

$$ \sigma^{\prime} $$

$$ \sigma, $$

Instead, we will need to relax the security model to consider adversaries who are \honest-butopportunistic", meaning they will only employ a malicious strategy if they stand to save more than some cost doing so (measured in storage resources). This security model, called-rational replication, has been formally specied and applied rigorously to analyze the constructions included in this report [13]. In the context of the Filecoin storage network and blockchain ecosystem,-rational replication captures the cost that clients must pay to convince miners to encode their real data inside PoReps rather than \useless" generated data, and therefore the degree to which Filecoin subsidizes storage costs.

Proof of space A PoRep is a publicly veriable proof-of-space (PoS) [12]. A prover that passes verication in the interactive challenge-reponse protocol for a le D~ of claimed size jD~ j = N must be using (N) persistent storage. Moreover, a prover that passes verication in k instances of this protocol with distinct ids id₁*;:::;id*kand claimed le sizes N₁;:::;Nkmust be using (M) P k space where M = N_i. This is implied by-rational replication and is in general a weaker i=1 property.

$$ |\ddot{D}|=N $$

$$ i d_{1},...,i d_{k} $$

$$ N_{1},...,N_{k} $$

$$ M=\sum_{i=1}^{k}N_{i} $$

Data preprocessing and data retrievability Finally, a PoRep is a proof-of-retrievability (PoR) [16] of the underlying data represented by the data tag_D. The type of security guarantee here depends on the mode of the data preprocessing step. When the data input is preprocessed using a secret-key the resulting PoRep is a public-coin PoR. In this scenario we can imagine

$$ \tau_{D} $$

³ Consider a model with network communication round trip bounds and distance between parties. Two servers claim to be in two dierent locations and are each storing a replica of the same le. We could use distance bounding protocols combined with proofs of retrievability to verify the claim [30]

the preprocessor is a single client who wants to store (and replicate) data on a server, and generates the data tag_Dto outsource this verication work (i.e. anyone with the tag_Dcan verify on behalf of the client). When the preprocessor runs in keyless mode the resulting PoRep 4 is a publicly-veriable proof of retrievable commitment (PoRC). In this case_Dis simply a binding commitment to the data le D, and the PoRep is a proof that the prover can retrieve the data D. Any (stateful) verier that is at one point given the opening of the commitment can thereafter use the tag to verify PoReps as standard PoRs. This is particularly useful for a setting in which multiple clients pool their les together and want to receive a single PoRep for the entire dataset, but they do not mutually trust one another to share a private-key. It is also appropriate for a dynamic setting where new clients are made aware of the data stored on the server and wish to verify retrievability without trusting the original client’s private-key preprocessing.

$$ \tau_{D} $$

$$ \tau_{D} $$

$$ \mathrm{{(P o R C)^{4}} $$

$$ D, $$

$$ D $$

$$ \tau\ {\cal D} $$

2 Basic PoRep from Sequential Encodings

The rst basic PoRep we describe applies a slow encoding to a le F to transform it into a format F, which can be quickly decoded back to F. This general approach has been described before in [1,9,19]. The slow transformation is done in an initialization period \oine". A verier then periodically checks that the server is still storing the encoding F. If the server has deleted the encoding F~ then it will not be able to re-derive it quickly enough to respond to challenges from the verier during the \online" phase. Furthermore, the encoding can be made unique to a particular identier id, so that two the encodings F~ and F~ (called replicas) are independent id1 id2 and cannot be quickly derived from one another. This way, a server that is only storing one of the two encodings of the same original le F will fail the online challenges from the verier for the missing replica.

$$ {tilde{F}}] $$

$$ F $$

$$ \tilde{F} $$

$$ \tilde{F} $$

$$ i d, $$

$$ \tilde{F}_{i d1} $$

$$ \tilde{F}_{i d2} $$

Veriable Delay Encodings The primitive we use to implement slow encodings in our most basic PoRep is called a veriable delay encoding (VDE). These will also play a role in our more advanced constructions. Informally, as described, this is an encoding that is slow to compute yet fast to decode. More specically, the encoding requires non-parallelizable sequential work to evaluate and therefore in theory cannot be computed in shorter than some minimum wall-clock time. A VDE is a special case of a VDF [9]. Practical examples of VDEs include Sloth [17], MiMC [3], and a special class of permutation polynomials [9].

The syntax we will use for a VDE is a tuple of three algorithms VDE = fSetup*;Enc;Decg* dened as follows. (Some constructions of VDESetup may require this to be run by a trusted party, or computed using MPC. The instantiations described above do not).

1. VDE.Setup(t;)! pp is given security parameter and delay parameter t produce public parameters pp. By convention, the public parameters also specify an input space X and a code space Y. We assume that X is eciently samplable.

$$ .\mathsf{S e t u p}(t,\lambda)\to p p $$

$$ \lambda $$

$$ x\in\mathcal{X} $$

2. VDE.Enc(pp;x)! y takes an input x 2X and produces an output y 2Y.

$$ \mathsf{V D E.E n c}(p p,x)\to y $$

$$ y\in\mathcal{Y} $$

3. VDE.Dec(pp;y)! x takes an input y 2Y and produces an output x 2X.

$$ \ {mathsf V D D}.{\mathsf{D e c}}(p p,y)\to x $$

$$ y\in\mathcal{Y} $$

$$ x\in\mathcal{X}. $$

⁴ This primitive is formally dened in [13]. It is similar to a proof of knowledge of a commitment, only with a public extraction property more similar to PoR. The publicly veriable Merkle commitment described in [16] is a simple example of a PoRC

2.1 Basic PoRep Construction

In all of the constructions we describe in this report we will skip the description of PoRep.Preproc. The data is preprocessed in one of the modes described, and we start with the preprocessed data D~ and data tag. We assume there is an external verication procedure that the ver- D ier may query on any block d of the le D~, its position i, and, which returns a result i D that we denote by O_check(d_i;i;_D)! b 2 f0*;* 1g. The construction will use a VDE scheme m fVDE.Setup*;VDE.Enc;VDE.Decg* with identical input space and code space over f0*;* 1g, as well m as a hash function H : f0*;* 1g! f0*;* 1g ^modeled as a random oracle (i.e. maps strings of arbitrary length to strings of length m). For two strings s₁;s₂ 2 f0*;* 1g the notation s₁jjs₂ denotes their concatenation.

$$ \tilde{D} $$

$$ \tau_{D} $$

$$ i, $$

$$ \tilde{D} $$

$$ \ {{\ \ T}}D, $$

$$ d_{i} $$

$$ \mathcal{O}{\mathsf{c h e c k}}(d{i},i,\tau_{D}),\rightarrow,b,\in,{0,1} $$

$$ {0,1}^{m} $$

$$ H:{0,1}^{*}\to{0,1}^{m} $$

$$ s_{1},s_{2},\in,{0,1}^{*} $$

$$ s_{1}||s_{2} $$

PoRep.Setup(;T)! pp Run VDE.Setup(T;)! pp. This species the block length m, and provides implicit input parameters to VDE.Enc and VDE.Dec.

$$ \ (\lambda,T)\to p p $$

$$ \mathsf{V D E.S e t u p}(T,\lambda)\to p p. $$

$$ m. $$

PoRep.Replicate(id;; D)! R;aux Parse D as a le of N blocks d₁;:::;d each a string D N m in f0*;* 1g. For each i compute R_i= VDE.Enc(d_iH(idjji)). Output R = (R₁;:::;R_N) and aux = N.

$$ :(i d,\tau_{D},\tilde{D}),\to,R. $$

$$ \tilde{D} $$

$$ d_{1},...,d_{N} $$

$$ {0,1}^{m} $$

$$ R_{i}=\mathsf{V D E.E n c}(d_{i}\oplus H(i d||i)) $$

$$ R=(R_{1},...,R_{N}) $$

$$ \ u={N} $$

PoRep.Extract(id;R)! D~ Parse R = (R₁;:::;R) and for each i compute d = VDE.Dec(R) N _i i H(idjji). Output D~ = (d₁;:::;d). _N

$$ \mathfrak{L}(i d,R)\to\tilde{D} $$

$$ R=(R_{1},...,R_{N}) $$

$$ d_{i}=\mathsf{V D E.D e c}(R_{i})\oplus $$

$$ H(i d||i) $$

$$ \tilde{D}=(d_{1},...,d_{N}) $$

R PoRep.Poll(N)! r For i = 1 to randomly sample r_i[N]. Output r = (r₁;:::;r).

$$ \ {tt0R e p.}{\sf P o l l}(N)\to r $$

$$ r=(r_{1},...,r_{\lambda}) $$

$$ r_{i}\xleftarrow{\mathtt{R}}[N] $$

PoRep.Prove(R;N;id;r)! Parse R = (R₁;:::;R_N) and r = (r₁;:::;r). Output the proof = (R_r1;:::;R_r).

$$ \mathrm {e} (R, N, i d, r) \rightarrow \pi $$

$$ R=(R_{1},...,R_{N}) $$

$$ r=(r_{1},...,r_{\lambda}) $$

$$ \pi=(R_{r_{1}},...,R_{r_{\lambda}}) $$

m PoRep.Verify(id;_D;r;N;)! 0*=1 Parse the proof = (₁;:::;) as strings in f0;* 1g. For each i = 1 to do:

$$ \mathsf{f y}(i d,\tau_{D},r,N,\pi)\to0/1 $$

$$ \pi=(\pi_{1},...,\pi_{\lambda}) $$

$$ {0,1}^{m} $$

1.Compute d^ = VDE.Dec() H(idjjr) _i i i

$$ \hat{d}{i}=\mathsf{V D E.D e c}(\pi{i})\oplus H(i d||r_{i}) $$

2.Query b O (d^;r;) _i check i i D

$$ b_{i}\leftarrow\mathcal{O}{\mathsf{c h e c k}}(\hat{d}{i},r_{i},\tau_{D}) $$

If b_i= 1 for all i then output 1 (accept), otherwise output 0 (reject).

$$ b_{i}=1 $$

Instantiation We can instantiate the basic PoRep construction with the Sloth [18] VDE. For a target polling period of 5 minutes, choosing the block size gives a tradeo between proof size and initialization time. With a block size of m = 4096 and time delay T of 10 minutes, replication of les up to 50KB (N = 100) take under 1 hour and extraction takes under 1 second on 16 parallel cores. With block size m = 256 we can only support les to 320 bytes for replication to take under 1 hour. If instead we x the le size (e.g. up to 50KB) but decrease block size by a factor, then we both increase initialization time by a factor and decrease proof size by a factor.

$$ m=4096 $$

$$ m=256 $$

$$ {\tilde{D}}_{1} $$

$$ \mathsf{V D E.E n c}(\tilde{D}_{1}\oplus H(\mathrm{}{i d}||i)) $$

$$ R_{1} $$

$$ {\tilde{D}}_{2} $$

$$ \mathsf{V D E.E n c}(\tilde{D}_{2}\oplus H(\mathrm{}{i d}||i)) $$

$$ R_{1} $$

$$ \tilde{D}_{N} $$

$$ \underline{{\mathsf{V D E.E n c}(\tilde{D}{N}\oplus H(i d||N))}}\ \ \ \ R{N} $$

Figure 2.1: Illustration of PoRep.Replicate in the basic PoRep construction using a VDE.

Proof size The proof size is m bits. To detect deletion of 1% of the data block with soundness error 1*=3 we would require = 100, in which case the proof might as well include the entire replica (if we support only up to N = 100). To detect deletion of 5% with soundness 1=*3 only requires = 20, or 1/5 of the entire le. For 80% we can set = 5, or 5% of the le size. In combination with erasure code during preprocessing, the le may still be perfectly recoverable. Therefore we still achieve-replication. For example, if D is preprocessed with an erasure code that tolerates arbitrary 20% deletion, then we tradeo an increase in the replica size by 20% for a proof size of only 6% of the original le size.

$$ 1/3 $$

$$ \lambda=100 $$

$$ 1/3 $$

$$ N=100) $$

$$ \lambda=20 $$

$$ 1/5 $$

$$ \lambda=5 $$

$$ 5% $$

3 Block Chaining Sequential Encodings

The Basic-VDE-PoRep does not scale well for large le sizes. A 1 GB size le with block size of 512 bytes would take over 13 days to replica on a machine with limited parallelism. Increasing the block size to reduce replication time impacts proof size and is also limited by the message space of the VDE scheme. VDE schemes like Sloth operate on relatively small input spaces as larger input spaces are more susceptible to parallelization attacks. The fundamental issue in the Basic-VDE-PoRep construction is that the VDE (tuned for the polling period delay T) is applied individually to each block of the le thus allowing a fully parallel attacker to derive the entire replica within time T whereas it takes a non-parallel prover time TN.

This is not just due to paranoia about massively parallel attacks! Any attacker who uses only a factor k more parallelism will be able to reduce replication time by a factor k. If the best adversary can generate replicas a factor k faster then the time to replicate for the honest provers must be at least a factor k times longer than the polling period. In fact, since the verication strategy randomly samples only ‘ blocks to challenge, the adversary only needs ‘ parallelism to re-derive the challenged blocks in wall-clock time T.

Block chaining A natural way to reduce the overall replication time while maintaining the sequential hardness is to chain the encodings of each block, similar to encryption in block chaining cipher modes. A simple chaining would modify PoRep.Replicate in the Basic-VDE-

Figure 3.1: Basic-VDE-PoRep in CBC-mode.

PoRep by deriving from each R_i(encoding of block d_i) a key k_i= H(idjjR_i) to be used in the encoding R_i+1= VDE.Enc(d_i+1k_i) (of block d_i+1) as shown in Figure 3.1.

$$ R_{i} $$

$$ d_{i}) $$

$$ k_{i}=H(i d||R_{i}) $$

$$ R_{i+1}!=!\mathsf{V D E.E n c}(d_{i+1}\oplus k_{i}) $$

$$ d_{i+1}) $$

Each R_ican still be decoded locally given only R_{i 1}as D_i= VDE.Dec(R_ik_i) where k_i= H(idjjR_{i 1}). We would then reduce the time delay T for each call to VDE.Enc such that T N is equal to the desired replication time. However, the problem with this basic chaining method is that it has a smooth time/space tradeo. An adversarial prover can store only each kth block (reducing overall storage by a factor k) and yet it can recompute any individual block with only k calls to VDE.Enc. With sucient parallelism it can re-derive the entire replica in time kT instead of NT, and worse yet it can respond to the verier’s ‘ random challenges in time kT with only ‘ parallelism. As a result to ensure the server is storing at least 1*=k* fraction of blocks the replication time must be at least a factor N=k longer than the polling period.

$$ R_{i} $$

$$ R_{i-1} $$

$$ D_{i}=\mathsf{V D E.D e c}(R_{i}\oplus k_{i}) $$

$$ k_{i}=H(i d||R_{i-1}) $$

$$ 1/k $$

Dependency graphs One way to characterize the issue with the simple cipher block chaining method is that the dependency graph of the block encodings is not depth robust. Let each block of the le represent a node in a graph where a directed edge is placed between the ith node and the jth node if the encoding of the jth block of the le depends on the encoding of the ith block. The resulting graph is a directed acyclic graph (DAG). By the properties of H and VDE.Enc the dependencies are cryptographically enforced: if the jth block is dependent on the ith block then the jth encoding cannot be computed unless the ith encoding is known except with negligible probability.

Depth robust graphs What is a depth robust graph? An (n;;;d) depth robust graph is a DAG on n nodes with in-degree d such that any n size subgraph contains a path of length n.

$$ (n,\alpha,\beta,d) $$

$$ \beta n $$

Denition 1. A locally navigatable DRG sampling algorithm for an (n;;;d)-DRG is a pair R s of deterministic algorithms that share a common s-bit seed f0*;* 1g where jsj = O(nlogn) that operate as follows:

$$ (n,\alpha,\beta,d)\ {overline{}}D R G $$

$$ \sigma \leftarrow^ {\mathrm {R}} {0, 1 } ^ {s} $$

$$ |s|=O(n\log n) $$

1. DRG.Sample(n;)! G outputs a graph on the node set indexed by integers in [n].

$$ ..S a m p l e(n,\sigma)\to G $$

2. DRG.Parents(n;;i)!P outputs a list P [n] of the parents of the node at index i 2 [n] in the graph G DRG:Sample(n;).

$$ \mathcal t t(n,\sigma,i)\to\mathcal P $$

$$ \mathcal{P}\subseteq[n] $$

$$ i\in[n] $$

$$ G_{\sigma}\gets D R G.S a m p l e(n,\sigma) $$

Figure 3.2: Illustration of block dependency DAG congurations in cipher block chaining encodings. On the left is a simple chain (as in the chained Basic-VDE-PoRep) whereas the right depicts a mock depth robust chaining. For each chained encoding, the ith encoding is derived as R_iEnc(k_i;d_i) where k_i= H(idjjparents(i)) and parents(i) denotes the set of encodings on nodes j with a directed edge to i.

$$ R_{i}\leftarrow\mathsf{E n c}(k_{i},d_{i}) $$

$$ \bar{k_{i}}H(\ i\ |\mathsf{p a r e n t s}(i)) $$

DRG.Sample(n;) runs in time O(nlogn) and DRG.Parents(n;;i) runs in time O(polylogn). R s Finally the graph G is an (n;;;d)-DRG with probability 1 negl(n) over f0*;* 1g.

$$ \ e(n,\sigma, $$

$$ (n,\sigma,i) $$

$$ O({\it p o l y l o g n}) $$

$$ (n,\alpha,\beta,d)\ !{\ \ }!D R G $$

$$ 1-n e g I(n) $$

$$ \sigma \leftarrow^ {\mathrm {R}} {0, 1 } ^ {s} $$

If the dependency graph is (;) depth robust then deleting any N fraction of the encodings will contain a dependency path of length N inside the deleted subgraph, meaning that it will require at least N sequential calls to VDE.Enc to re-derive the deleted blocks. On the other hand, the dependency graph of the cipher block chained Basic-VDE-PoRep is a line, and as demonstrated by the time/space tradeo attack described above it is at most (1 1*=k;k=N*) depth robust for any k < N (as storing only every kth node partitions the deleted set of nodes into lines of length k).

$$ (\alpha,\beta) $$

$$ (1-1/k,k/N) $$

$$ k<N $$

Pebbling complexity More generally we can consider the pebbling complexity of the dependency graph. This is dened in terms of a game where the player is allowed to place an initial number of pebbles on nodes of the graph. The game then proceeds in steps where in each step the player is allowed to place a new pebble on the graph with the restriction that it can only place a pebble on a node if all of its parents currently have pebbles. The player may also remove pebbles at any point. The game ends when the players has pebbled all nodes in some target set. There are various measures of pebbling hardness that have to do with the minimum number of steps required to pebble the target set from an initial conguration of a given size. The parallel pebbling complexity of the graph is captured by a similar game with the modication that in any \round" of the game the player can simultaneously pebble any node whose parent nodes had pebbles in the previous round, and is hard if from an initial conguration of some maximum size the adversary requires a minimum number of rounds to pebble the target set. Finally, a random pebbling game is one where the challenge node is selected randomly and hardness is measured in terms of the probability a player can win this game from a conguration of some size and some maximum number of moves/rounds.

Proofs of space Many proofs of space [12, 25, 26] and memory hard functions [14, 15] are based on iterated collision-resistant hash function computations with hard-to-pebble dependency graphs, called a labeling of the graph. Depth robust graphs were also used for publicly veriable proofs of sequential work [21]. The generic approach to constructing a PoS from a pebbling-hard graph proceeds in two steps: in an \oine" phase the prover commits to the labeling and demonstrates that the labeling is mostly correct (i.e. edge dependencies were respected) by answering random challenges to the commitment, and in an \online" phase the prover demonstrates that it can retrieve most of the labeling. Our PoRep constructions also follow this structure. Combining the labeling game with sequential encodings results in a smooth spectrum bridging the two techniques. On one end of the spectrum, large les with very large block dependency graphs will not need a large time-delay and are therefore nearly equivalent to proofs of space with data XORed into the labels. On the other end of the spectrum, very small graphs will not benet from chaining and are therefore nearly equivalent to the basic VDE PoRep.

3.1 Depth Robust Chaining of Sequential Encodings

Our new PoRep DRG-PoRep extends the Basic-VDE-PoRep by chaining block dependencies using a depth robust chaining as described above. Using an (N;;;d)-DRG we are able to reduce the time delay T for each block encoding as N increases, such that the total time NT remains the same and the polling period is tuned to TN. A prover that deletes more than an fraction of the block encodings will not be able to respond to challenges correctly (and quickly enough) during the challenge-response period. This achieves-rational replication and replication time that is a factor 1*=* longer than the polling period. Unfortunately, erasure codes no longer guarantee that the data is still recoverable from an fraction of the encodings due to the dense block dependencies. However, the security can be amplied using stronger DRGs for smaller > 0, at the cost of increasing the degree by O(1*=*) as well as the replication time relative to polling period.

$$ (N,\alpha,\beta,d)\mathrm{-}D\mathrm{R G} $$

$$ 1/\beta $$

$$ \alpha>0 $$

$$ O(1/\alpha) $$

Online and oine proofs The protocol separates two kinds of proofs. As a part of the aux output during the replication the prover generates a proof that the depth robust chaining of the encodings were \mostly" correct. The verier cannot check that all the correct dependencies were enforced as this would not be a compact proof. Instead, the prover derives the entire encoding (consisting of labels on each node of the graph) and provides the verier with a compact vector commitment to these labels. The verier queries for several randomly sampled nodes of the graph and challenges the prover to open the commitment to labels on both this node and the labels on all of its parent nodes. The verier can then check that the encodings correctly observed the dependency. This convinces the verier that a constant fraction of the nodes in the graph are correct. Because the graph is depth robust, a suciently large subgraph of correct nodes is also depth robust. Actually, we will make this proof non-interactive using the Fiat-Shamir heuristic. The second \online" proof is a simple proof of retrievable commitment. The verier simply challenges for several indices of the prover’s vector commitment to the replica block encodings and the prover sends back these openings.

3.1.1 DRG-PoRep Construction

PoRep.Replicate(id;; D~)! R;aux D

$$ (i d,\tau_{D},{\dot{D}})\to R $$

1. H(idjj_D) =. This is the seed used to \sample" the DRG graph and \salt" the hash function.

$$ H(i d||\tau_{D})=\sigma $$

2.Parse D~ as data blocks (d₁;:::;d). Run DRGEnc on d;m;N; ~ and. The output is the N replica R.

$$ \tilde{D} $$

$$ (d_{1},...,d_{N}) $$

$$ \vec{d},m,N $$

$$ \sigma $$

DRGEnc(d;m;N; ~)f for i = 1 to N :

(v₁;:::;v_d) DRG.Parents(N;;i) k_iH( jjc_v1jjjjc_vd) c_iVDE.Enc(pp_vde;k_id_i)

R (c₁;:::;c_n) return Rg

$$ \mathsf{\bar{n n n}}(\vec{d},m,N,\sigma)\big{\begin{array}{l l}{end{}}\end{array} $$

$$ i=1\ t o\ N: $$

$$ (v_{1},...,v_{d})\gets\mathsf{D R G.P a r e n t s}(N,\sigma,i) $$

$$ k_{i}\gets H(\sigma||c_{v_{1}}||\cdots||c_{v_{d}}) $$

$$ c_{i}\leftarrow\mathsf{V D E.E n c}(p p_{\mathsf{v d e}},k_{i}\oplus d_{i}) $$

$$ R\leftarrow(c_{1},...,c_{n}) $$

3.Compute a Merkle commitment⁵ com_Rto the replica blocks R.

4.Now use H to non-interactively derive the challenge vector = (¹;:::;^‘1) asⁱ= nodes H( jjcom_Rjji). These specify a set of challenge _nodes C = (c¹;:::;c). The proof ‘1 will provide the labels on the challenge nodes, demonstrate that they were committed to in com_R, and that they are at least locally consistent with their parent labels.

$$ \rho;=;\left(\rho_{1},...,\rho_{\ell_{1}}\right) $$

$$ \rho_{i}\ = $$

$$ H(\sigma||c o m_{R}||i) $$

$$ C ^ {\mathrm {n o d e s}} = \left(c _ {\rho_ {1}},..., c _ {\rho_ {\ell_ {1}}}\right) $$

$$ c o m_{R}. $$

parents For each i set parents(_i) DRG.Parents(N;;_i) and set C (_i) = (c_v1;:::;c_v) where _d fv₁;:::;v_dg = parents(_i).

$$ (\rho_{i})\gets\mathsf{D R G.P a r e n t s}(N,\sigma,\rho_{i}) $$

$$ \mathcal{C}^{\mathsf{p a r e n t s}}(\rho_{i})=\left(c_{v_{1}},...,c_{v_{d}}\right) $$

$$ {v _ {1}, \dots , v _ {d} } = \operatorname {p a r e n t s} \left(\rho_ {i}\right) $$

nodes 5.Compute Merkle proofs _nodesthat all the challenge node labels C and Merkle proofs parents parentsthat their parent labels C are all consistent with the commitment comR.

$$ \Lambda_{\mathsf{n o d e s}} $$

$$ C^{\mathsf{n o d e s}} $$

$$ \Lambda_{\sf p a r e n t s} $$

$$ C^{\mathsf p a a e n t s} $$

nodes parents 6.Output R and aux = com_R;C;^nodes;C;^parents.

$$ \mathsf{u x}=\mathrm{}{c o m}{R},^{{\mathsf{n o d e s}}},\Lambda{{\mathsf{n o d e s}}},C^{{\mathsf{p a r e n t s}}},\Lambda_{{\mathsf{p a r e n t s}}}. $$

R PoRep.Poll(N)! r: For i = 1 to ‘₂randomly sample r_i[N]. Output r = (r₁;:::;r_‘2).

$$ {\mathfrak{z}}.\mathbf{P o l l}(N)\to r{colon\} $$

$$ \ell_{2} $$

$$ r_{i}\xleftarrow{\mathtt{R}}[N] $$

$$ r=(r_{1},...,r_{\ell_{2}}) $$

PoRep.Prove(R;aux;id;r)! : For each rⁱin the challenge vector ~r = (r₁;:::;r^‘2) derive the parents key for the node r_ias k_ri= H( jjC (r_i);i) where R = (c₁;:::;c_n). Provide Merkle inclusion proof fo_r each c, and set = ;:::;, set ~c = (c;:::;c), and set ~k = (k;:::;k). i _riret 1 _‘ r1r‘r1r‘ Output the proof containing the Merkle proofs and key/label pairs, = (_ret;~c; ~k).

$$ r_{i} $$

$$ (R,a u x,i d,r)\to\pi! $$

$$ \ \vec{r}=(r_{1},...,r_{\ell_{2}}) $$

$$ r_{i} $$

$$ k_{r_{i}}=H(\sigma||C^{\mathsf{p a r e n t s}}(r_{i}),i) $$

$$ R=(c_{1},...,c_{n}) $$

$$ \Lambda_{i} $$

$$ c_{\boldsymbol{r}_{i}} $$

$$ \Lambda_{\mathsf{r e t}}=\Lambda_{1},...,\Lambda_{\ell} $$

$$ {\vec{c}}=(c_{r_{1}},...,c_{r_{\ell}}) $$

$$ \vec {k} = \left(k _ {r _ {1}},..., k _ {r _ {\ell}}\right) $$

$$ \pi=(\Lambda_{\mathsf{r e t}},\vec{c},\vec{k}) $$

nodes PoRep.Verify(id;_D;r;aux;)! b Parse the input aux as a list of values com_R,,, C, parents ^parents C (₁),...,C (_‘1), , ₁,...,_‘1as well as the input = _ret;~c. Parse = (_ret;~c; ~k).

$$ \ (mathit i d,\tau_{D},r,a u x,\pi)\to $$

$$ _{R},,\sigma,,,\rho,,C^{\mathsf n o d e s} $$

$$ C^{\mathsf{p a r e n t s}}(\rho_{1}),...,C^{\mathsf{p a r e n t s}}(\rho_{\ell_{1}}),;\mathsf{\Lambda},;\Lambda_{1},...,\Lambda_{\ell_{1}} $$

$$ \pi=\Lambda_{\mathsf{r e t}},{\vec{c}}. $$

$$ \pi=(\Lambda_{\mathsf{r e t}},\vec{c},\vec{k}) $$

6 1.First verify aux. Check H(idjj_D) = and H( jjcom_Rjji) =_ifor each i = 1 to ‘₁. If nodes any checks fail reject the proof. Verify the Merkle proof _nodeson C. Next, for each i parents derive parents(_i) DRG.Parents(N;;_i) and the key k_i= H( jjC (_i);i). Check that d_i= VDE.Dec(pp_vde;k_ic_i). Query the check oracle b O_check(d_i;_i;_D). If b = 0 output 0 and terminate.

$$ H(i d||\tau_{D})=\sigma $$

$$ \therefore^66 $$

$$ H(\sigma||c o m_{R}||i)=\rho_{i} $$

$$ i=1 $$

$$ \ell_{1} $$

$$ \Lambda_{\mathsf{n o d e s}} $$

$$ C^{\mathsf{n o d e s}} $$

$$ \ \cdot(\rho_{i})\gets\mathsf{D R G.P a r e n t s}(N,\sigma,\rho_{i}) $$

$$ k_{\rho_{i}}=H(\sigma||C^{\tt a r e n t s}(\rho_{i}),i) $$

$$ d_{i}=\mathsf{V D E.D e c}(p p_{\mathsf{v d e}},k_{i}\oplus c_{\rho_{i}}) $$

$$ b\gets\mathcal{O}{\mathsf{c h e c k}}(big_d i,\rho{i},\tau_{D}\big) $$

$$ b=0 $$

2.Second verify the \online" proof. First verify the Merkle proof _retfor the challenge vector ~c. Next for each i 2 [‘₂] compute d_iVDE.Dec(pp_vde;k_ic_ri) and query the oracle O_check(d_i;r_i;_D) If any Merkle proof verications or oracle queries fail reject the proof.

$$ i\in[\ell_{2}] $$

$$ \vec{c}. $$

$$ \pi $$

$$ \Lambda_{\mathsf{r e t}} $$

$$ d_{i}\leftarrow\mathsf{V D E.D e c}(p p_{\mathsf{v d e}},k_{i}\oplus c_{r_{i}}) $$

$$ \mathcal{O}{\mathsf{c h e c k}}(d{i},r_{i},\tau_{D}) $$

⁵ More generally, Merkle commitments can be replaced with any vector commitment [10, 20].

⁶ In the interactive protocol, as long as the verier is stateful then the input aux only needs to be veried the rst time the verier runs PoRep.Verify on its rst poll as it can remember the verication result for subsequent polls.

Proof sizes There are two types of proofs, the \oine" non-interactive proof contained in aux and the \online" proofs output by PoRep.Prove. The proof contained in aux is much larger, although it is only sent once to each verier. There are two security parameters, ‘₁is a security parameter determining the number of queries in the oine proof, and ‘₂is a security parameter determining the number of queries in the online proof. The proof size is roughly (d‘₁+ ‘₂) m logN bits because the responses to the ‘₁challenge queries include the d parents of each challenge node whereas the responses to the ‘₂queries do not. Vector commitments with constant size or batched openings, as opposed to Merkle commitments, would reduce the factor log N overhead. As aux is non-interactive the soundness error needs to be exponentially small, therefore we set ‘₁= = log(1). For example to achieve 80-bit security and = 0*:* 20 this is ‘₁= 825.

$$ \ell_{1} $$

$$ \ell_{2} $$

$$ (d\ell_{1}!+!\ell_{2})\times!m\times!,, $$

$$ \ell_{1} $$

$$ \ell_{2} $$

$$ \ell_{1}=\lambda/-\log(1-\alpha) $$

$$ \alpha=0.20 $$

$$ \ell_{1}=825 $$

Relaxing soundness: interaction and time/space tradeos The reason why in general we need to set ‘₁to be large is that otherwise the prover can brute force a favorable challenge in the non-interactive proof. There are two ways to improve on this. First, we could get rid of the non-interactive proof in aux and required the verier to challenge the prover for a fresh aux proof on their rst interaction. Second, the non-interactive challenge \grinding" attack requires the prover to rerun replication many times in expectation. As this is already a memory/sequentially hard computation (taking at least around 10-60 min), we could incorporate this into the rational security model. The question is how much extra replication work a malicious prover is willing to do in order to save a fraction of space during the online phase. If we can just achieve soundness 80 1*=*1000 instead of 2 then even a massively parallelized prover will need to grind in expectation for 3.47 days. For this soundness level we can set ‘₁100.

$$ \ell_{1} $$

$$ 2^{-80} $$

$$ \ell_{1}\approx100 $$

Compressing proofs with SNARGs We can further compress the size of the aux proof by using SNARGs, or any other form of succinct proofs. The prover computes a SNARG over the circuit PoRep.Verify with the proof as a witness. To optimize the performance of this SNARG it would be important to choose instantiations of vector commitments, slow encodings, and collision resistant hash functions that minimize the multiplicative complexity of checking inclusion proofs and decoding. If the VDE is expensive to implement in a SNARG circuit, then just eliminating the labels on parent nodes already substantially decreases the proof size.

$$ \pi $$

The Jubjub⁷ Pedersen hash over BLS12-381 is an attractive candidate as it achieves a circuit complexity of only 4 multiplication gates per input bit (61,440 gates per Merkle commitment opening with a 32GB le). This can be used to instantiate both Merkle commitments and the function H. If the VDE is instantiated with Sloth++ [9] over the scalar eld of BLS12-381, then verication of a 5 min delay involves roughly 6 million multiplication gates. This is due to the fact that Sloth++ iterates a square-root round function 30 million times. However, with a 1GB le the delay T will be reduced drastically, e.g. with = 1*=*100 it will require only 3 iterations of the Sloth++ round function. Furthermore, if a longer delay (on the order of 5 minutes) is necessary then we can instead use a VDE based on inverting permutation polynomials over F_pdescribed in [9]. For sequential security this would require tuning the polling period to the time it would take a prover running on an industry standard GPU as the polynomial GCD computations do admit some parallelism. The total circuit size for verifying aux with 30 m = 256, N = 2, d = 20, and ‘₁= 100 is approximately 124 million gates, and would take approximately 5 hours to compute on a single-threaded 2.4 GHz Intel E7-8870 CPU [8]. With

$$ \beta,=,1/100 $$

$$ \mathbb{F}_{p} $$

$$ m=256 $$

$$ N=2^{30} $$

$$ \ell_{1}=100 $$

⁷ https://z.cash/technology/jubjub.html modest parallelism (e.g. 16 threads) this can easily be reduced to below the replication time.

3.2 Stacked DRG PoRep

The DRG-PoRep construction improved signicantly on replication time while maintaining terric extraction eciency. However, it compromised on-rational security and the tightness of the proof of space. In order to achieve-arbitrarily small, we required DRG graphs that were robust in-fraction subgraphs. Not only does this degrade the practicality of the DRG construction, it also worsens the gap between polling and replication time, which necessarily increases as O(1*=*). Thus, in some sense we cheated, as the Basic-PoRep achieves arbitrarily small-rational security for a xed replication time. In our nal construction we show how to overcome this at the expense of a slower extraction time. Our basic idea is to layer DRGs, iterating the DRG-PoRep construction so that each layer \re-encodes" the previous layer. In our rst variant, we add additional edge dependencies between the layers that are used in the encoding. These edge dependencies are the edges of a bipartite expander graph between the layers. A bipartite expander graph has the property that every constant size subset of sinks is connected to a relatively large subset of sources. Unfortunately, by adding these additional edge dependencies between the layers they can no longer be decoded. Therefore, in this variant we instead use the rst ‘ 1 layers to deterministically derive the keys that are used to encode the data input on the last layer. Data extraction is as expensive as data replication because it requires re-deriving the keys in the same way.

$$ O(1/\epsilon) $$

As we will show, this has the eect of amplifying the DRG security by exponentially blowing up the dependencies between nodes on the last level and nodes on the rst level. Deletion of a small fraction of node labels on the last level will require re-derivation of nearly all the node labels on the rst level (or even rst several levels). Therefore, a relatively weak (constant) depth-robustness on the rst few levels is all that is necessary to guarantee parallel pebbling hardness. In particular, we are able to prove that an (n;0: 80n;(n)) DRG is sucient, i.e. deletion of 20% of nodes leaves a high depth graph on the 80% remaining nodes, regardless of the value of. Moreover, the number of levels required to achieve this is only O(log(1*=)). This results in a factor log(1=) gap between polling and replication time as opposed to the previous O(1=*) gap.

$$ (n,0.80n,\Omega(n)) $$

$$ O(\log(1/\epsilon)) $$

$$ (1/\epsilon) $$

$$ O(1/\epsilon) $$

Tight PoS In fact, this construction also gives the rst concretely practical (and provably secure) tight proof of space, outperforming [2, 12, 25, 26] in its ability to achieve arbitrarily tight proofs of space with xed degree graphs. The only other tight PoS is Pietrzak’s DRG construction [25] and requires special DRGs of degree O(1*=) where is the space gap. A PoS 2 based on pebbling a graph of degree O(1=) results in a total proof size of O(1=). Already by stacking O(log(1=)) xed degree DRGs we are able to achieve proof complexity O(1=* log(1*=)). However, we are able to go even further and show that the total number of queries over all layers can be kept at O(1=), achieving proof complexity O(1=). This is in fact the optimal proof complexity for the (generic) pebbling-based PoS with at most an space gap. If the prover claims to be storing n pebbles and the proof queries less than 1=* then a random deletion of an 1= fraction of these pebbles evades detection with probability at least (1) ¹=e. The same applies if a random fraction of the pebbles the prover claims to be storing are red (i.e. errors).

$$ O(1/\epsilon) $$

$$ O(1/\epsilon) $$

$$ O(1/\epsilon^{2}) $$

$$ O(\log(1/\epsilon)) $$

$$ O(1/\epsilon{\cdot}\log(1/\epsilon)) $$

$$ O(1/\epsilon) $$

$$ O(1/\delta) $$

$$ 1/\epsilon $$

$$ (1-\epsilon)^{1/\epsilon}\approx1/e $$

Data extraction and zig-zag As we mentioned, the downside of our rst variant is the data extraction time, which is now as expensive as data replication. Our second variant xes this with a simple tweak. Instead of adding edge dependencies between the layers, we add the edges of a constant degree expander graph in each layer so that every layer is both depth-robust and has high \expansion". A non-bipartite expander graph has the property that the boundary of every constant size subset, i.e. the number of neighboring nodes, is relatively large. Technically, the graph we construct in each layer is an undirected expander, meaning that the union of the dependencies and targets of any subset in our DAG is large. However, by alternating the direction of the edges between layers, forming a \zig-zag", we are able to show that the dependencies between layers expand. Now the only edges between layers are between nodes at the same index, and the label on each node encodes the label on the node at the same index in the previous level. The dependencies used for keys are all contained in the same layer; thus, the labels in any layer can be used to recover the labels in the preceding layer. Furthermore, the decoding step can be done in parallel just as in DRG-PoRep.

It is easy to see that without alternative the direction of the edges between layers this construction would fail to be a tight proof of space because the topologically last n nodes in a layer would only depend on the topologically last n nodes in the previous layer. Moreover, if the prover stores the labels on the topologically rst (1)n nodes it can quickly recover the labels on the topologically rst (1)n nodes in the preceding level, allowing it to recover the missing n labels as well in parallel-time O(n). This is no more secure than DRG-PoRep and cannot tolerate arbitrarily small for a xed polling period.

$$ \epsilon n $$

$$ \epsilon n $$

$$ (1-\epsilon)n $$

$$ (1-\epsilon)n $$

$$ O(\epsilon n) $$

Related techniques Pietrzak [25] also proposed using depth robust graphs for proofs of replication and presented a slightly dierent construction to DRG-PoRep that partially resolves the issues of space-tightness in an elegant way. The construction uses the recent [5] DRGs which are (n;;;O(log n=))-depth robust for all (;) such that 1 + 1. Instead of embedding the data on all nodes of the graph, the construction generates a graph on 4n nodes, but only encodes the data on the topologically last n nodes. The replication procedure still generates a labelling of the entire graph upon which the last n block encodings are dependent, but only outputs the labels on the last n nodes. This is similar in spirit to our idea of layering DRGs as it divides the graph into 4 layers by depth, hower here a single DRG is dened over 0 all the nodes. Pietrzak shows that a prover who deletes an fraction of the labels on the 0 last n nodes will not be able to re-derive them in fewer than n sequential steps. The value ⁰ can be made arbitrarily small however < =4, so the degree of the graph must increase as ⁰ 1*=*. Furthermore, although the graphs in [5] achieve asymptotic eciency and are incredibly intriguing from a theoretical perspective, they still do not have concretely practical degree. (As a side point, Pietrzak’s construction does not incorporate delay encodings into the DRG PoRep construction. If only SHA256 is called for each labeling this means that only graphs of a minimum size over 1 billion nodes can achieve a 10 min delay. SHA256 can be intentionally slowed with iterations, but then extraction becomes as inecient as the replica generation).

$$ (n,\alpha,\beta,O(\log n/\epsilon), $$

$$ (\alpha,\beta) $$

$$ 1-\alpha+\beta\geq1-\epsilon. $$

$$ n $$

$$ \epsilon^{\prime} $$

$$ \epsilon^{\prime} $$

$$ \epsilon<\epsilon^{\prime}/4 $$

$$ 1/\epsilon^{\prime} $$

Ren and Devadas [26] construct a proof of space from stacked bipartite expander graphs. Our construction can be viewed in some sense as a merger of this technique with DRGs, however it requires a very new and more involved analysis. Their construction can easily be modied into a \proof of replication" as well by encoding data only on the last level (similar to Pietrzak’s DRG construction and our rst variant of stacked DRGs). Specically, the labels on all levels V₁;:::;V_{r 1}are rst derived and then each label ‘_ion the ith node of the last level L_ris replaced

$$ V_{1},...,V_{r-1} $$

$$ \ell_{i} $$

$$ L_{r} $$ with VDE.Enc(‘_id_i) where d_iis the ith block of data. The data extraction is as inecient as replica generation because it must be extracted by re-running the computation from the start to derive the labels ‘_iand then decoding each block. However, their construction would also not satisfy our stronger denition for PoRep security (with a time bounded adversary) as it is not secure against parallel attacks. Furthermore, the space gap is quite weak (i.e. it cannot beat = 1*=*2 according to their analysis). Our construction is a strict improvement as it is both space-tight and secure against parallel attacks.

$$ \mathsf{V D E.E n c}(\ell_{i}\oplus d_{i}) $$

$$ d_{i} $$

$$ \ell_{i} $$

$$ \epsilon=1/2 $$

CBC layering Finally, we draw a comparison to a PoRep proposal hinted at in [1] which suggested iterating CBC encryption over the data with a permutation interlaced between layers. This is the direct inspiration for our construction, and it is instructive to observe the pitfalls of implementing this approach with CBC-mode encryption and why they are resolved when using a depth robust chaining mode instead.

The CBC-layering method is as follows. Let denote a random permutation on the block indices of the le, i.e. : [N]! [N]. (In practice can be represented compactly using a Feistel cipher and a random seed to generate the Feistel round keys). Let CBCEnc(id;D) denote the Basic-VDE-PoRep in CBC-mode as illustrated in Figure 3.1. Additionally for any length N input vector ~x dene the function Shue (x₁;:::;x_N) = (x₍₁₎;:::;x_(N)). Starting with the plaintext blocks D = d₁;:::;d_N, compute the encoding c₁;:::;c_NCBCEnc(id;D) and set V₀ = (c₁;:::;c_N). Next shue and re-encode the blocks of V₀ so that V₁ = CBCEnc(id; Shue (V₀). Continue iterating the process so that V_i= CBCEnc(id; Shue (V_{i 1})). Output the last layer V_‘as the replica encoding R. Extraction can be run in the reverse direction, with a factor k parallel speedup on k parallel processors.

$$ \Pi,:,[N],\to,[N] $$

$$ (i d,D) $$

$$ \vec{x} $$

$$ \mathrm {S h u f f l e} ^ {\Pi} \left(x _ {1},..., x _ {N}\right) = \left(x _ {\Pi (1)},..., x _ {\Pi (N)}\right) $$

$$ D=d_{1},...,d_{N} $$

$$ c_{1},...c_{N}\leftarrow C B C E n C(i d,D) $$

$$ V_{0}= $$

$$ (c_{1},...,c_{N}) $$

$$ V_{0} $$

$$ V_{1}=\mathsf{C B C E n c}(i d,\mathsf{S h u f l e e}^{\mathsf{I I}}(V_{0}) $$

$$ V_{i}=\mathsf{C B C E n c}(i d,\mathsf{S h u f l e}^{\mathrm{I I}}(V_{i-1})) $$

$$ V_{\ell} $$

There are two main issues with this approach:

1.It is hard to verify that the prover maintains the edge dependencies (i.e. computes the p CBC encoding correctly). If the prover cheats on only a 1= N fraction of edges in each p level then it cuts the sequential work by a factor N and the probability of catching the prover with only a small number of queries is very small. Basically this is for the same reason that a hash chain is not a publicly veriable proof of sequential work⁸ (unless we use SNARGs over a circuit of size N‘, which would be impractical for large N).

$$ 1/\sqrt{N} $$

$$ \sqrt{N} $$

2.The prover could use the time/space tradeo attack on CBC-mode encodings to storing only =‘ fraction of the block labels on each level, for total space storage N and it can 2 re-derive any block label on the last level in ‘ = sequential steps. For xed polling period of 5 min, in order to catch an adversary using N storage ‘ must be suciently large so ² that ‘ = steps (i.e. calls to VDE.Enc) must take at least 5 min. As each call therefore 2 takes 5*=‘* min it implies that the total replication time takes 5N=‘ minutes. Let = 1*=*2, 30 11 N = 2 (16GB le), and consider two cases. If N=‘ > 2 then replication takes 3.5 days. 11 11 49 On the other hand if *‘ > N=*2 then ‘N = *N²=*2 = 2. Even if each call to VDE.Enc 49 9 on a 16 byte block is reduce to 1 cycle on a 2 GHz machine, 2 cycles still takes 3 days.

$$ \epsilon/\ell $$

$$ \ell^{2}/\epsilon $$

$$ \ell^{2}/\epsilon $$

$$ 5\epsilon/\ell^{2} $$

$$ \epsilon=1/2. $$

$$ N/\ell $$

$$ N=2^{3\ } $$

$$ N/\ell>2^{11} $$

$$ \ell>N/2^{11} $$

$$ \ell N=N^{2}/2^{11}=2^{49} $$

$$ 2^{49} $$

⁸ In fact, MMV11 [22] use depth robust graphs for the very purpose of obtaining publicly veriable proofs of sequential work.

⁹ The attack is much worse when the permutation is not applied between layers. For any ‘, if the adversary stores N=‘ evenly spaced columns of block labels for total space N then it is easy to see that the adversary can (with unlimited parallelism) recompute all the labels on the last level in 2*‘=*) parallel steps by deriving blocks along diagonals (lower left to upper right), deriving a block in the next level as soon as its dependencies in the

$$ \epsilon N/\ell $$

$$ \epsilon N $$

$$ 2\ell/\epsilon) $$

Depth robust layering Using a depth robust chaining rather than CBC on each level gets rid of both of these issues. It would be nice to prove security just from permutations between layers, however our analysis relies heavily on the additional expander edges instead of permutations. Intuitively, the permutations between layers would prevent the attacker from nding a depth reducing set of nodes whose dependencies in all previous layers also belong to a depth reducing set.

Expander construction We use the randomized construction of bipartite expander graphs originally due to Chung [11]. This samples the edges of the graph using a random permutation. More precisely, the edges of a d-regular bipartite expander on 2n vertices are dened by connecting the dn outgoing edges of the sources to the dn incoming edges of the sinks via a random permutation : [d] [n]! [d] [n]. That is, the ith source is connected to the jth sink if there is some k₁;k₂ 2 [d] such that (k₁;i) = (k₂;j). This has been shown to result in a bipartite expander with overwhelming probability in n [7, 26, 28]. Our construction uses 8-regular bipartite graphs constructed in this way. We also use this to construct an undirected non-bipartite expander graph by treating the N nodes as both the targets and the sinks, dening the edge (i;j) if and only if there exists k₁;k₂ 2 [8] such that either (k₁;i) = (k₂;j) or (k₁;j) = (k₂;i). We will revisit expander graphs in more depth in our formal analysis section.

$$ \Pi:[d]\times[n]\to[d]\times[n] $$

$$ \Pi(k_{1},i)=(k_{2},j) $$

$$ k_{1},k_{2},\in,[d] $$

$$ k_{1},k_{2}\in[8] $$

$$ \Pi(k_{1},i)=(k_{2},j) $$

$$ \Pi(k_{1},j)=(k_{2},i) $$

Number of layers and degree In the protocol description we set the number of layers to a parameter L = 10. Based on our analysis, using a degree d = 8 expander graph and targeting = 1% then we can safely set L = 10. There are two options for targeting smaller. One is to increase the degree d, but the other is to increase the number of layers. In general, for xed expander degree d = 8 the number of required layers increases as O(log(1*=)) as!* 0. This is the better option in our opinion. Unless the le is so large that the time for each VDE.Enc call is optimally small (e.g. a single call to AES, or 20 cycles on an Intel CPU with AES-NI), as we increase the layers we can still maintain the same initialization time by lowering the delay parameter of each block encoding. Importantly, the dierence between replication time and the polling period remains the same. We are also able to achieve constant proof complexity as we increase the number of layers. The number of queries to the vector commitment of the nal layer is O(1*=*), but we can reduce this exponentially (i.e. by a multiplicative factor) between layers. Increasing the degree on the other hand increases the proof size.

$$ L=10 $$

$$ d=8 $$

$$ \epsilon=1% $$

$$ L=10 $$

$$ \epsilon\rightarrow0 $$

$$ d=8 $$

$$ O(\log(1/\epsilon)) $$

$$ O(1/\epsilon) $$

3.2.1 Stacked-DRG-PoRep

Our presentation of the construction follows the second \zig-zag" variant.

m As before, H is a random oracle H : f0*;* 1g! f0*;* 1g and : f0*;* 1g [8] [N]! R [8] [N] is a random permutation oracle where for each seed f0*;* 1g the function (;) is computationally close to a random permutation of [8] [N], where N = poly(). As N = poly(), can be realized using a cryptographic PRG to generate (N logN) pseudorandom bits from the seed in order to sample a random permutation, however in practice it is better if both ¹ and can be evaluated more eciently, i.e. in polylog(N) time and space.

$$ H:{0,1}^{*},\to,{0,1}^{m} $$

$$ :{0,1}^{\lambda}\times[\ ]]\times[N] $$

$$ \ \ [8aleph]\times[N] $$

$$ \sigma\xleftarrow{\ {R R}}{0,1}^{\lambda} $$

$$ \Pi(\sigma,\cdot) $$

$$ [ 8 ] \times [ N ] $$

$$ N=\mathrm{p o l y}(\lambda) $$

$$ N=\mathrm{p o l y}(\lambda) $$

$$ \Pi^{-1} $$

previous level are available. Therefore, to catch an adversary that is using only N storage, it is necessary to set the polling period T 2*‘=*, which implies that the total replica generation time is *‘N TN=*2, i.e. a factor 12 *N=2 longer than the polling period. If the polling period is 5 minutes, = 1=*2, and N = 2 blocks this already takes 3.5 days.

$$ \epsilon N $$

$$ T\leq2\ell/\epsilon $$

$$ \ell N\geq\epsilon T N/2 $$

$$ \epsilon N/2 $$

$$ \epsilon=1/2, $$

$$ N=2^{12} $$ can be instantiated using a Feistel cipher with keys derived pseudorandomly from. If 8N is not an even power of 2, then we can use a standard cycle-walking technique. nd the smallest 2k 1 2k k such that 8N 2 [2*;* ²] and implement a Feistel cipher F over 2k-bit block size. On each input x 2 [8N] iterate F (x) until reaching the rst output that is an integer in the range [8N]. The inverse permutation runs the inverse Feistel cipher, employing the same technique. If y is the rst integer in [8N] output by iterating F on x then it is easy to see that x will be the 1 rst integer in [8N] output by iterating F on y.

$$ 8N\in[2^{2k-1},2^{2k}] $$

$$ x\in[8N] $$

$$ F^{-1} $$

In what follows, DAG.Enc is the encoding subroutine DRG.Enc called by PoRep.Replicate in the DRG-PoRep construction, but replacing the function DRG.Parents with a new function DAG.Parents. This new function calls DRG.Parents but also adds \expander" edges. Furthermore, there is an \even" and \odd" mode of selecting the expander edges. The expander edges added in the odd mode are equivalent to reversing the edges of the even mode and renumbering the nodes in the reverse direction. That is, there is a directed edge (i;j) in the even mode graph if and only if there is a directed edge (N j + 1*;N i* + 1) in the even mode graph. The DRG edges are sampled the same way in both graphs. DAG.Enc(~x;m;N;;b) makes calls to DAG.Parents(N;;i;b) for i 2 [N]. In pseudocode, the function DAG.Parents operates as follows:

$$ \left(N-j+1,N-i+1\right) $$

$$ \mathsf{i.E n c}(\vec{x},m,N,\sigma,b) $$

$$ i\in[N] $$

DAG.Parents(N;;i;b)f

V := fv₁;:::;v_dg DRG.Parents(N;;i)

W :=; for k = 1 to 8 : case b = 0 : (j;k⁰) (; (i;k)); (j⁰;k⁰⁰) if j < i then W := W [fjg if j⁰ < i then W := W [fj⁰g case b = 1 :

¹ (; (i;k))

1 (j;k⁰) (; (N i + 1*;k*)); (j⁰;k⁰⁰) (; (N i + 1*;k*)) if N j + 1 < i then W := W [fN j + 1g if N j⁰ + 1 < i then W := W [fN j⁰ + 1g

return W [ V g

$$ W:=W\cup{j} $$

$$ N-j+1<i $$

$$ N-j^{\prime}+1<i $$

PoRep.Setup(;;T)! pp: The setup obtains as input security parameters*;, as well as the delay parameter T and runs pp_vdeVDE.Setup(1 ). This determines a block size m and m M = f0;* 1g. The setup then runs pp_vcVC.Setup(1*;N*_max; M) where N_maxis the maximum supported data length. Finally the setup also denes two integers ‘₁= ‘₁() and ‘₂= ‘₂(). The setup outputs pp = (pp_vde;pp_vc;m;‘₁;‘₂). We x the number of layers L in the construction.

$$ {\mathfrak{S e t u p}}(\lambda,\kappa,T)\to p p $$

$$ \lambda,\kappa, $$

$$ p p_{\mathsf{v d e}}\leftarrow\mathsf{V D E.S e t u p}(1^{\lambda}) $$

$$ \mathcal{M}={0,1}^{m} $$

$$ p p_{v c}\gets\mathsf{V C.S e t u p}(1^{\lambda},N_{m a x},M) $$

$$ N_{m a x} $$

$$ \ell_{1}=\ell_{1}(\lambda) $$

$$ \ell_{2}=\ell_{2}(\kappa) $$

$$ p p=\left(p p_{\mathsf{v d e}},p p_{\mathsf{v c}},m,\ell_{1},\ell_{2}\right) $$

PoRep.Replicate(id;; D)! R;aux: The input to the replicate procedure is the preprocessed D data le D consisting of N blocks of size m, along with data tag and replica identier id. D

$$ :(i d,\tau_{D},\tilde{D})\to R $$

$$ \tau{boldsymbol}D\ \boldsymbol{} $$

1.Apply random oracle H(idjj_D) =.

$$ H(i d||\tau_{D})=\sigma $$

~ as data blocksm 2.Parse D d~ = (d₁;:::;d_N), each d_i2f0*;* 1g.

$$ \tilde{D} $$

$$ \vec{d}=(d_{1},...,d_{N}) $$

$$ d_{i}\in{0,1}^{m} $$

Initialize ~x = (x₁;:::;x_N) consisting of N data blocks where initially x_i= d_i. Dene swap(~x) = (x_N;:::;x₁), which reverses the indexing of the elements. Iterate DAG.Enc L times over ~x as follows:

$$ {\vec{x}},=,(x_{1},...,x_{N}) $$

$$ x_{i},=,d_{i} $$

$$ {mathsf\mathsf s{w p p}}\big(\vec{x}\big)=\big(x_{N},...,x_{1}\big) $$

$$ \mathsf{S t a c k e d D R G E n n}(\vec{d},m,N,\sigma){ $$

$$ \vec{x}:=\mathsf{D A G.E n c}(\vec{x}^{*},m,\sigma,i\not0) $$

$$ \ {\vec{x}}^{*}:={\mathsf s w a p}({\vec{x}}) $$

$$ \Phi_{i}\leftarrow\mathsf{V C.C o m}(p p_{\mathsf{v c}},\vec{x}) $$

$$ \Phi\leftarrow\mathsf{V C.C o n}(p p_{\mathsf{v c}},\Phi_{1},...,\Phi_{\ell}) $$

When implementing StackedDRGEnc, the values x_ican be updated in place, so only a single buer of size N blocks is needed. Some extra storage is needed to store the vector commitment, however this can be made relatively small using time/space tradeos discussed below.

$$ x_{i} $$

(j) 3.Use H to derive a challenge vector for each jth level as = ⁽_1;j;:::;_‘1;j) where_i;j= H(idjj jjijjj).

$$ \rho^{(j)}=\left(\rho_{1,j},...,\rho_{\ell_{1},j}\right) $$

$$ \rho_{i,j}= $$

$$ H(i d||\Phi||i||j) $$

0N 4.Rerun¹⁰ StackedDRGEnc and on the jth iteration let (c⁰₁;:::;c) denote the output labels on the jth inputs (c₁;:::;c_n).

$$ (c_{1}^{\prime},...,c_{N}^{\prime}) $$

$$ \left(c_{1},...,c_{n}\right) $$

(j) Compute vector commitment opening proofs on the indices specied by the challenges :

$$ \rho^{(j)} $$

nodes (a)Set C = (c_1;j;:::;c). j _‘1;j

$$ C_{j}^{\sf n o d e s}=\left(c_{\rho_{1,j}},...,c_{\rho_{\ell_{1},j}}\right) $$

parents 0v 0v (b)For each i set C (^i;j) = (c;:::;c) where fv₁;:::;v_dg DAG.Parents(m;;_i;j;i j 1 d mod 2). Let parents(_i;j) = (v₁;:::;v_d).

$$ C_{j}^{\mathfrak{p a r e n t s}}(\rho_{i,j})=(c_{v_{1}}^{\prime},...,c_{v_{d}}^{\prime}) $$

$$ {v_{1},...,v_{d}}\leftarrow\mathsf{D A G.P a r e n t s}(m,\sigma,\rho_{i,j},i $$

$$ \left(\rho_{i,j}\right)=\left(v_{1},...,v_{d}\right) $$

pred (c)Set C = (c_1;j;:::;c). j _‘1;j

$$ C_{j}^{\mathsf{p r e d}}=\left(c_{\rho_{1,j}},...,c_{\rho_{\ell_{1},j}}\right) $$

nodes nodes parents parents pred Let C = (C1nodes;:::;C), and C = fC (i;j)gj2[L];i2[‘], and C = L j 1 pred pred (C₁*;:::;C*). L

$$ {\mathcal{C}}^{\sf n o d e s},=,(big(C_{1}^{\sf n o d e s},...,C_{L}^{\sf n o d e s}\big) $$

$$ C^{\sf p a r e n t s},=,{C_{j}^{\sf p a r e n t s}(\rho_{i,j})}{j\in[L],i\in[\ell{1}]} $$

$$ C^{\mathsf{p r e d}}=,\, $$

$$ (C_{1}^{\mathsf{p r e d}},...,C_{L}^{\mathsf{p r e d}}) $$

5.Compute vector commitment opening proofs on the indices specied by the challenges:

for j = 1 to L :

$$ \begin{array}{l} \Lambda_ {j} ^ {\mathrm {n o d e s}} \leftarrow \mathrm {V C}. \mathrm {O p e n} \left(p p _ {\mathrm {v c}}, C _ {j} ^ {\mathrm {n o d e s}}, \Phi_ {j}, \rho\right) \ \Lambda_ {j} ^ {\mathrm {p r e d}} \leftarrow \mathrm {V C}. \mathrm {O p e n} \left(p p _ {\mathrm {v c}}, C _ {j} ^ {\mathrm {p r e d}}, \Phi_ {j}, \rho\right) \ \mathbf {f o r} i = 1 t o \ell_ {1}: \ \Lambda_ {i, j} ^ {\mathrm {p a r e n t s}} \leftarrow \mathrm {V C}. \mathrm {O p e n} \left(p p _ {\mathrm {v c}}, C ^ {\mathrm {p a r e n t s}} \left(\rho_ {i, j}\right), \mathrm {p a r e n t s} \left(\rho_ {i, j}\right)\right) \ \end{array} $$

6.Output R, and aux = ;::;;C

$$ R, $$

$$ \dot{\mathsf{a a w e}=\Phi_{1},..,\Phi_{L},C^{\mathsf{m o d e s}},C^{\mathsf{p a r e n t s}},C^{\mathsf{p r e d}},{\Lambda_{j}^{\mathsf{n o d e s}}}{j\in[L]},{\Lambda{j}^{\mathsf{p r e d}}}{j\in[L]},{\Lambda{i,j}^{\mathsf{p r r e n t s}}}{j\in[L],i\in[\ell{1}]}.} $$

¹⁰ The prover can of course choose between using a larger buer (up to NL) and re-running the StackedDRGEnc computation once.

R PoRep.Poll(N)! r: For i = 1 to ‘₂randomly sample r_i[N]. Output r = (r₁;:::;r_‘2).

$$ \mathsf{P o R e p.P o l l}(N)\to r; $$

$$ i=1 $$

$$ \ell_{2} $$

$$ r=(r_{1},...,r_{\ell_{2}}) $$

PoRep.Prove(R;aux;id;r)! : The input is id, the aux output of replicate, challenge vector ~r = (r₁;:::;r^‘2), and the replica R = (c₁;:::;c_N). Set ~c = (c_r1;:::;c_r). Compute ‘2 VC.Open(pp_vc;com_R;c;r). Output = _ret;~c.

$$ \ R,a u x,i d,r)rightarrow pipi; $$

$$ i d. $$

$$ {\vec{r}},=,(r_{1},...,r_{\ell_{2}}) $$

$$ R,=,(c_{1},...,c_{N}) $$

$$ \mathsf{V C.0p p n}(p p_{\mathsf{v c}},c o m_{R},\vec{c},\vec{r}) $$

$$ \Lambda\leftarrow $$

$$ \ \vec{c}=(c_{r_{1}},...,c_{r_{\ell_{2}}}) $$

$$ \pi=\Lambda_{\mathsf{r e t}},\vec{c}. $$

nodes parents pred nodes PoRep.Verify(id;_D;r;aux;): Parse the input aux as ₁;:::;_L, C, C, C, f g, _j pred parents f g, f g. Parse = ret*;~c*. j i;j

$$ ((i d,\tau_{D},r,a u x,\pi) $$

$$ \mathbf{\Phi}{1},\dots,\mathbf{\Phi}{L},,C^{\mathbf{n o d e s}},,C^{\mathbf{p a r e n t s}},,C^{\mathbf{p r e d}},,{\mathbf{\Lambda}_{\gamma}^{\mathbf{n o d e s}}} $$

$$ {\Lambda_{j}^{\mathsf{p r e d}}},{\Lambda_{i,j}^{\mathsf{p a r e n t s}}} $$

$$ \pi=\Lambda_{\mathsf{r e t}},\vec{c}. $$

1.(This is only done the rst time, otherwise skip to 2). Derive H(idjj_D) =, and_i;j= H(idjj jjijjj) for each i 2 [‘₁] and j 2 [L]. Derive for each i;j the set parents(_i;j) nodes DAG.Parents(m;;_i;j). Run verications of all the vector commitment openings on C, parents pred C, and C.

$$ H(i d||\tau_{D})=\sigma. $$

$$ H(i d||\Phi||i||j) $$

$$ \rho_{i,j} $$

$$ i\in\left[\ell_{1}\right] $$

$$ j\in[L] $$

$$ i,j $$

$$ \ \cdot\left(\rho_{i,j}\right)\leftarrow $$

$$ \mathsf{D A G.P a r e n t s}(m,\sigma,\rho_{i,j}) $$

$$ C^{\mathsf{n o d e s}} $$

$$ C^{\mathsf p a a e n t s} $$

$$ C^{\mathsf{p r e d}} $$

2.Second verify the proof. Compute b VC.Verify(pp_vc;c;r;_ret). Output b.

$$ b\leftarrow V C.V e r i f y(p p_{v\ {\sf v c}},\vec{c},\vec{r},\Lambda_{\sf r e t}) $$

Vector commitment overhead If the prover uses a Merkle tree as its vector commitment then it will either need to additionally store the hashes on internal Merkle nodes or recompute them on the y. At rst glance this may appear to destroy the tightness of the PoS because storing the Merkle tree is certainly not a PoS. However, because the time/space tradeo in storing this tree is so smooth the honest prover can delete the hashes on nodes on the rst k k levels of the tree to save a factor 2 space and re-derive all hashes along a Merkle path by reading k k at most 2 nodes and computing at most 2 hashes. If k = 7 this is less than a 1% overhead in space, and requires at most 128 additional hashes and reads. Furthermore, as remarked in [25] k these 2 reads are sequential memory reads, which in practice are inexpensive compared to the random reads for challenge labels. Similar time/space tradeos are possible with RSA vector commitments.

$$ 2^{k} $$

$$ 2^{k} $$

$$ k=7 $$

$$ 2^{k} $$

$$ 2^{k} $$

Reducing number of challenges In the description of the protocol above we set the number of non-interactive challenges ‘₁to be the same at every level, for a total of ‘₁L challenges. Since ‘₁= O(=) to achieve-rational-security this results in proof size of O(L=). However, we can actually decrease the number of challenges between levels by a multiplicative factor, and provided that the number of challenges remains above a certain threshold. In particular, letting (^{i) (}L) ‘ denote the number of challenges for the ith level, we prove security with ‘¹= ‘ = O⁽=^{) 1} 1 (i) (i+1) and ‘ = min₍20*;₍2=3₎‘), although the analysis could be tightened for better parameters. 1 1 P(i) L The total number of challenges is therefore O(=) because ‘ 3‘*₁. _i=1 1

$$ \ell_{1} $$

$$ \ell_{1}L $$

$$ \ell_{1}=O(\lambda/\epsilon) $$

$$ O(\lambda L/\epsilon) $$

$$ \ell_{1}^{(i)} $$

$$ \ell_{1}=\ell_{1}^{(L)}=O(\lambda/\epsilon) $$

$$ \ell_{1}^{(i)}=m i n(20,(2/3)\ell_{1}^{(i+1)\cdot}) $$

$$ \textstyle{\sum_{i=1}^{L}\ell_{1}^{(i)}\leq3\ell_{1}} $$

$$ O(\lambda/\epsilon) $$

Data extraction The data extraction is less ecient compared to DRG-PoRep (which coincide with L = 1). There is a still a large asymmetry between the replication time and data extraction due to the asymmetry of VDE.Enc and VDE.Dec, however this dierence is reduced as the le size grows larger. The extraction can still be highly parallelized allowing for a large speedup given suciently many parallel cores.

Proof size estimates The online proof size is comparable to the proof size of the DRG-PoRep, although now that an arbitrarily small-rational replication is actually achievable (also space gap) it will be necessary to set ‘₂appropriately in the online proof. As in Basic-DRG-PoRep, to verify that the prover can still retrieve an fraction of the commitment with soundness requires ‘₂> log()=log(1). For example, if = 0: 01 and = 1*=*3 then ‘₂= 109. With 16- byte block sizes this is 1.6KB. (Considering the le may be up to terabytes in size this is highly reasonable). A SNARG proof can also be used to compress the online proof size, and in this case would have multiplicative complexity around 10 million gates using a Merkle commitments with the Jubjub pedersen hash, and can be generated in 1.5 minutes on 16 parallel cores.

$$ \ell_{2} $$

$$ \mu=1/3 $$

$$ \epsilon=0.01 $$

$$ \ell_{2}>\log(\mu)/\log(1-\epsilon) $$

$$ \ell_{2}=109 $$

The non-interactive proof included in aux is now somewhat larger than in DRG-PoRep because of the increase in levels, i.e. it is a factor L = O(log(1*=)) larger without considering the optimization of reducing the number of challenges between levels as described above. When applying this optimization, then asymptotically it is only O(1=) as!* 0. This can still be compressed with SNARGs, but now has a larger circuit complexity as well and will thus take longer to compute. Without using SNARGs and instantiating the vector commitments with RSA vector commitments the bottleneck in the proof size is the labels of the challenges. Let ‘¹= max(20L;3‘₁). The proof size is approximately ‘¹d m bits where m is the block size 8 and ‘₁= O(=). Concretely, for soundness 2 and = 0*:* 03 then according to our analysis we can set ‘¹= 3*=0:* 01 = 300 and L = 10 for total ‘¹= 900. (This soundness level makes the 8 assumption that any rational attacker will not repeat its initialization more than 2 times in order to save = 0*:* 02 space). With m = 128 and d = 13 = 5 + 8 this results in a proof size of approximately 187 KB, independent of the data input size. This is still reasonable consider the data input sizes could range up to gigabytes or terabytes.

$$ L,=,O(\log(1/\epsilon)) $$

$$ O(1/\epsilon) $$

$$ \epsilon\rightarrow0 $$

$$ \ell_{1}^{*}=m a x(20L,3\ell_{1}) $$

$$ \ell_{1}^{*}\cdot d\cdot m $$

$$ m $$

$$ 2^{-8} $$

$$ \ell_{1}=O(\lambda/\epsilon) $$

$$ \epsilon,=,0.03 $$

$$ L=10 $$

$$ \ell_{1}=3/0.01=300 $$

$$ \ell_{1}^{*}=900 $$

$$ 2^{8} $$

$$ \epsilon=0.02~\mathrm{s p a c e}, $$

$$ m=128 $$

$$ d=13=5+8 $$

One observation is that the edges of the DRG can tolerate more error than the expander edges between layers given a suitably strong DRG construction. For example, if the DRG is depth robust in 70% subgraphs and at most 10% of the nodes in the graph contain errors, then a subgraph on 80% of the nodes will still be depth robust. On the other hand, if only an fraction of the dependencies between levels (i.e. the predecessors) are enforced then-rationality takes a direct hit. Likewise, the expander edges are what guarantee expansion of dependencies between levels. Therefore, we could reduce the proof size by adjusting the number of queries checking the DRG edges vs the expander edges. Reducing this can makes a signicant dierence as each time we check the DRG edges we need to open d labels.

4 Instantiating Depth Robust Graphs

DRG-PoRep requires an (n;;;d) DRG where; < 1 and d 2 polylog(n). In general for performance we want to minimize and d while maximizing. Recall that the value of determines the-rational-security achievable, and space gap of the construction as proof of space. The implication of a larger is that the erasure code will have to tolerate up to an fraction deletion of the data, which will require an erasure code blowup factor of r = 1*=(1) (note that r < 2 for < 1=2). The degree impacts the PoRep proof size and verication complexity, which is O(d). On the other hand, Stacked-DRG-PoRep only requires an (n;0: 80;;d*) DRG for some constant and degree d.

$$ (n,\epsilon,\delta,d) $$

$$ \epsilon,\delta,<,1 $$

$$ d,\in,\mathrm{p o l y l o g}(n) $$

$$ r<2 $$

$$ r=1/(1!-!\epsilon) $$

$$ \epsilon<1/2) $$

$$ O(\lambda d) $$

$$ (n,0.80,\beta,d) $$

$$ \beta $$

Explicit Depth Robust Graphs Erd}os et. al. [24] showed how to construct DRGs explicitly from extreme constant-degree bipartite expander graphs. Using their construction, one can obtain an (n;;;clogn) DRG on n nodes for particular constants, e.g. = 0*:* 99 and = 0*:* 1, and suciently large n. The constant factor c depends on the degree of the bipartite expander graphs used in the iterated construction. While explicit constructions of these graphs exist [23], they are complex and have either large constant degree or only achieve the requisite expansion properties for a signicantly large number of nodes. Mahmoody et. al. [22] use denser bipartite expander graphs to construct for any < 1 a DRG family that is (n;;;clog² n) depth robust for all < 1. Again, instantiating this construction with explicit expanders will result in graphs that have an impractically large degree. There is a new construction by Alwen et. al. [5] that improves asymptotically on MMV, but not concretely.

$$ (n,\alpha,\beta,c\log n) $$

$$ \alpha=0.99 $$

$$ \beta=0.1 $$

$$ \alpha<1 $$

$$ \left(n,\alpha,\alpha-\epsilon,c\log^{2}n\right) $$

Probabilistic Constructions If we compromise on explicit constructions then we can instead use probabilistic methods to sample much simpler graphs with more practical concrete parameters that satisfy the desired depth robustness property with high probability. Intuitively, since random graphs have good expansion properties in expectation, we can replace the explicit expanders used inside the DRG constructions with randomly sampled graphs instead. Alwen et. al. [4] proposed and analyzed a more direct probabilistic DRG sampling algorithm that outputs a (n;1 =log n;; 2) DRG on n nodes with failure probability negligible in n. Their construction can be easily modied to output a (n⁰; 1;;clog n⁰) DRG on n⁰ = O(n= logn) nodes for some xed constant c. Unfortunately, their analysis only shows that the output graph is a DRG with good probability for very high values of 1. On the other hand they provide strong empirical evidence that the output graph retains depth robustness for much smaller subgraphs than analyzed theoretically, and thus provides hope that a tighter analysis would yield much better values of (and even).

$$ \mathtt{a}\left(n,1-\alpha/\log n,\beta,2\right) $$

$$ \left(n^{\prime},1-\alpha,\beta,c\log n^{\prime}\right) $$

$$ n^{\prime}=O(n/\log n) $$

$$ 1{-}\alpha. $$

4.1 Bucket Sampling

The starting point of our DRG sampling algorithm is the algorithm of Alwen et. al. [4], which produces a degree-2. The algorithm is extraordinarily simple. It is a small tweak on a random DAG, sampling d edges for each node at index v randomly from the preceding nodes at indices u < v, but biasing the selection towards nodes that are closer to v.

$$ u<v. $$

The construction operates on nodes with integer indices in [n]. First, a directed edge connects i 1 each node u to its successor u + 1. Next, let B_i= f(u;v) : 2 jv ujg where u;v 2 [n] are the integer indices of nodes u and v respectively. For a given node v, let B_i(v) denote the set of all u⁰ < v such that (u⁰;v) 2 Bi, i.e. it contains the nodes u that are within a \distance" in i 1 i the range [2*;* 2] from v. For each node v, a bucket B_iwith i log₂v is selected uniformly R at random and then nally a random node u B_iis selected. The edge (u;v) is added to the graph.

$$ u+1 $$

$$ B_{i}=\left{\left(u,v\right):2^{i-1}\leq\left|v-u\right|\right} $$

$$ u,v\in[n] $$

$$ v $$

$$ u^{\prime}<v $$

$$ B_{i}(v) $$

$$ (u^{\prime},v)\in B_{i} $$

$$ [2^{i-1},2^{i}] $$

$$ B_{i} $$

$$ i\leq l o g_{2}v $$

$$ \ leftarrow^{\mathrm{R}}B_{i} $$

$$ (u,v) $$

BucketSample[n]f V := [n]; E :=; for v = 2*;:::;n* : E := E [f(v 1*;v*)g R ^R i f1*;:::;* log₂ vg; u B_i(v) E := E [f(u;v)g return(V;E)g

BucketSample[n;m]f (V;E) BucketSample[nm] W := [n]; E⁰ :=; for(i;j) 2 E : uii % n; ujj % n E⁰ := E⁰ [f(u_i;u_j)g return(W;E⁰)g

$$ V:=[n];;E:=\emptyset $$

$$ v=2,...,n $$

$$ E:=E\cup\left{\left(v-1,v\right)\right} $$

$$ i\xleftarrow{\mathbb{R}}{1,...,\mathrm{l o g}{2}v};;u\xleftarrow{\mathbb{R}}B{i}(v) $$

$$ W:=[n];;E^{\prime}:=\emptyset $$

$$ E:=E\cup{(u,v)} $$

$$ \mathbf{f o r}(i,j)\in E $$

$$ u_{i}\leftarrow i\not\supset_{0}n;;u_{j}\leftarrow j\not\supset_{0}n $$

$$ E^{\prime}:=E^{\prime}\cup{(u_{i},u_{j})} $$

$$ \mathbf{r e t u r n}(W,E^{\prime})\big} $$

This construction, denoted BucketSample[n], outputs a graph that is asymptotically block depth robust with overwhelming probability. Furthermore, if the sampling is xed by a seed to a pseudorandom generator then BucketSample[n] is both deterministic and locally navigatable. The function DRG.Parents(n;;v) is naturally dened by the construction, which would use the seed to sample the parents of node v. The denition of block depth robustness is as follows.

$$ (n,\sigma,v) $$

Denition 2 (ABH17). A (n;;;m;d) block depth robust graph is directed acyclic graph G with d-regular indegree on n nodes indexed by integers in [n] such that if any set S of size (1)n and its left neighborhood set D_m(S) = fx 2 G : 9u 2 Ss:t: 0 u x mg are removed, then the graph G n D_m(S) contains a path of length at least n.

$$ (n,\alpha,\beta,m,d) $$

$$ |n| $$

$$ (1{-}\alpha)n $$

$$ D_{m}(S)={x\in G:\exists u\in S s.t.0\leq u-x\leq m} $$

$$ G\setminus D_{m}(S) $$

$$ \beta n $$

The bucket sampling algorithm of Alwen et. al. [4] outputs a (n;1 c₁=log n;;c₂ log n; 2) block depth robust graph with failure probability negligible in n. Note that (n;;;m;d) block depth robustness is only possible for m(1) < 1, so the bucket sampling algorithm outputs a graph whose block depth robustness is within a constant factor (i.e., (1)*=*(*c₁c₂*)) of the optimal. According to the concrete lower bounds on parameters proved in their analysis, for = 4 0*:* 03 they get *m*(1) *> 160 2: ⁴3 10 > 0:* 038, which is within a factor 25*:* 5 of optimal. Next, we show how to use the block depth robust BucketSample[n] construction to construct larger degree DAGs with better depth robustness. The construction BucketSample[n;m] outputs a graph on n nodes of degree m that is a \factor" m more depth robust, i.e. improves (n;1;; 2) depth robustness to (*n;*1 m;;m + 1) depth robustness.

$$ \left(n, 1 - c _ {1} / \log n, \beta , c _ {2} \log n, 2\right) $$

$$ (n,\alpha,\beta,m,d) $$

$$ m!(1!-!\alpha)\ <!1!-!\beta $$

$$ (1-\beta)/(c_{1}c_{2})) $$

$$ \beta= $$

$$ :[n,m] $$

$$ (n,1{-}\alpha,\beta,2) $$

$$ \left(n,1-\alpha m,\beta,m+1\right) $$

\Metagraph" construction Suppose we are given an algorithm that for any (suciently large) n outputs a graph that is (n;1;;m;d) block depth robust. We construct a new graph G on nodes in [n] of degree dm as follows. First construct a graph G⁰ on nodes in [nm]. We dene the graph G such that there is a directed edge from node i to node j if and only if G⁰ contains a directed edge (u;v) for some u 2 [(i 1)m + 1*;i m*] and v 2 [(j 1)m + 1*;j m*]. It is easy to see that if G⁰ has in-degree d then the graph G has in-degree at most dm. Following the terminology of Alwen et. al., we call G the metagraph of G⁰, which can also notate as ^0m G = G. Using the underlying DRG construction BucketSample[n] the corresponding metagraph construction BucketSample[n;m] actually has degree at most m+ 1 because one of the two edges is to the immediate predecessor.

$$ (n,1-\alpha,\beta,m,d) $$

$$ G^{\prime} $$

$$ [n m] $$

$$ G^{j} $$

$$ u\in[(i-1)m+1,i\cdot m] $$

$$ (u,v) $$

$$ v\in[(j-1)m+1,j\cdot m] $$

$$ G^{\prime} $$

$$ G=G_{m}^{\prime} $$

$$ G^{\prime} $$

We prove the following lemma, which essentially says that G inherits the absolute depth robustness of G⁰ except now on a vertex set of 1*=m* the size.

$$ G^{\prime} $$

$$ 1/m $$

Lemma 1. If G is an (mn;1;;m;d) block depth robust robust graph then its meta graph G_mis (*n;*1 m;;dm) depth robust.

$$ 1-\alpha,\beta,m,d) $$

$$ G_{m}\ i s\ (n,1-\alpha m,\beta,d m) $$

Proof. Denote by B_ithe interval [(i 1)m + 1*;i m*] of nodes in G. Let B = fB₁;:::;B_ng. As noted in the graph construction, each node of the meta graph G_mcorresponds to one of the intervals B_i2 B, and has degree at most dm. Consider removing at most e = mn nodes from G_m. This corresponds to removing at most e of the intervals in B from G. By the block depth robustness of G, since e = mn then the remaining set of nodes in G contains a path of length mn. Any path of length mn nodes in G must intersect at least dne n intervals in B because a path intersecting at most k < n intervals of length m would contain at most km < mn nodes. This implies that there remains a path of length at least n in the meta graph G_m.

$$ B_{i} $$

$$ \mathcal{B}={B_{1},...,B_{n}} $$

$$ [(i-1)m+1,i\cdot m] $$

$$ G_{m} $$

$$ B_{i},\in,\mathcal{B} $$

$$ G_{m} $$

$$ G, $$

$$ e=\alpha m n $$

$$ \beta m n $$

$$ \lceil\beta n\rceil\geq\beta n $$

$$ k m,<,\beta m n $$

$$ k<\beta n $$

$$ \beta n $$

$$ G_{m} $$

20 Figure 4.1: Results of the attacks against BucketSample[n;m] for m = 1, 5, 10 and n = 2. We plot on the y-axis for each value of e < n on the x-axis the smallest depth among any of the subgraphs of size n e that any of the attacks were able to nd. For example, with BucketSample[n; 5] the attacks could not locate any subgraph on 70% of the nodes that had depth below *n=*4. With BucketSample[n; 20] the best attack on 10% subgraphs reduced the depth to *n=*64.

$$ n=2^{20} $$

$$ e,<,n $$

$$ n-e $$

$$ n/4 $$

$$ n/64 $$

Analytical and empirical results Looking under the hood in the analysis of [4], the metagraph G_mwith m = 160 logn is analytically a (n;0: 961*;* 0*:* 3*;160 logn*) depth robust graph with overwhelming probability. Alwen et. al. also give an empirical analysis on their 2-regular 24 graph construction for n = 2 nodes where they implement the best known depth reducing attacks to locate subsets of various sizes that contain short paths. The graph in their paper shows pairs (d;e) where d is the lowest depth found in any subgraph of size at least n e. 7 For example, their experiment results show that for e = 0*:* 2 10 the smallest depth found 6 24 was around 4 10 0*:* 24n nodes, suggesting that the sampled graph is (2*;* 0*:* 88*;* 0*:* 24*;2) depth robust. We implemented the same attacks against the larger degree graphs output by BucketSample[n;m], which are mostly based on a classical algorithm by Valiant [29] for locating a depth reducing set, shown below in Figure 4.1. The empirical results suggest that the graph out- 20 put by BucketSample[n; 5] on n = 2 is (n;0: 70;* 1*=4;*6) depth robust, that BucketSample[n; 10] is

$$ \ {\mathcal{G}}_{m} $$

$$ \left(n,0.961,0.3,160\log{n}\right) $$

$$ n=2^{24} $$

$$ (d,e) $$

$$ n-e $$

$$ e,=,0.2\times10^{7} $$

$$ 4\times10^{6},\approx,0.24n $$

$$ (2^{24},0.88,0.24,2) $$

$$ n=2^{20} $$

(n;0: 28*;* 1*=32;11) depth robust, and that BucketSample[n; 20] is (n;0: 10;* 1*=64;*21) depth robust, retaining high depth even in 10% subgraphs.

[1]Proof of replication. Protocol Labs, 2017. https://filecoin.io/proof-of-replication. pdf. [2]Hamza Abusalah, Joel Alwen, Bram Cohen, Danylo Khilko, Krzysztof Pietrzak, and Leonid Reyzin. Beyond hellman’s time-memory trade-os with applications to proofs of space. In ASIACRYPT, 2017. [3]Martin R. Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiessen. Mimc: Ecient encryption and cryptographic hashing with minimal multiplicative complexity. In ASIACRYPT, pages 191{219, 2016. [4]Joel Alwen, Jeremiah Blocki, and Benjamin Harsha. Practical graphs for optimal sidechannel resistant memory-hard functions. In CCS, 2017. [5]Joel Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Sustained space complexity. In EUROCRYPT, 2018. [6]Frederik Armknecht, Ludovic Barman, Jens-Matthias Bohli, and Ghassan O. Karame. Mirror: Enabling proofs of data replication. In 25th USENIX Security Symposium, 2016. [7]Leonid Alexandrovich Bassalygo. Asymptotically optimal switching circuits. In Problemy Peredachi Informatsii, 1981. [8]Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. Snarks for C: verifying program executions succinctly and in zero knowledge. In CRYPTO, 2013. [9]Dan Boneh, Joseph Bonneau, Benedikt Bunz, and Ben Fisch. Veriable delay functions. 2018. To appear in CRYPTO 2018. [10]Dario Catalano and Dario Fiore. Vector commitments and their applications. In PKC 2013, 2013. [11]F.R.K. Chung. On concentrators, superconcentrators, generalizers, and nonblocking networks. In Bell System Technical Journal, 1979. [12]Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of space. In CRYPTO, 2015. [13]Ben Fisch. Poreps: Proofs of space on useful data. Cryptology ePrint Archive, Report 2018/678, 2018. https://eprint.iacr.org/2018/678. [14]Christian Forler, Stefan Lucks, and Jakob Wenzel. Catena: A memory-consuming password scrambler. IACR Cryptology ePrint Archive, 2013. [15]Dan Boneh Henry Corrigan-Gibbs and Stuart Schechter. Balloon hashing: a provably memory-hard function with a data-independent access pattern. In Asiacrypt, 2016. [16]Ari Juels and Burton S Kaliski Jr. Pors: Proofs of retrievability for large les. In Proceedings of the 14th ACM conference on Computer and communications security, pages 584{597. Acm, 2007. [17]Arjen K Lenstra and Benjamin Wesolowski. A random zoo: sloth, unicorn, and trx. IACR Cryptology ePrint Archive, 2015, 2015. [18]Hendrik W Lenstra Jr. Factoring integers with elliptic curves. Annals of mathematics, pages 649{673, 1987. [19]Sergio Demian Lerner. Proof of unique blockchain storage, 2014. https://bitslog.

References

wordpress.com/2014/11/03/proof-of-local-blockchain-storage/. [20]Beno^t Libert and Moti Yung. Concise mercurial vector commitments and independent zero-knowledge sets with short proofs. In TCC, 2010. [21]Mohammad Mahmoody, Tal Moran, and Salil Vadhan. Publicly veriable proofs of sequential work. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science. ACM, 2013. [22]Mohammad Mahmoody, Tal Moran, and Salil P Vadhan. Time-lock puzzles in the random oracle model. In CRYPTO. Springer, 2011. [23]Salil Vadhan Omer Reingold and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In FOCS, 2000. [24]Ronald L. Graham Paul Erdos and Endre Szemeredi. On sparse graphs with dense long paths. In Computers & Mathematics with Applications, 1975. [25]Krzysztof Pietrzak. Proofs of Catalytic Space. Cryptology ePrint Archive # 2018/194, 2018. [26]Ling Ren and Srinivas Devadas. Proof of space from stacked expanders. In TCC, 2016. [27]Randal Burns Reza Curtmola, Osama Khan and Giuseppe Ateniese. Mr-pdp: Multiplereplica provable data possession. In In Distributed Computing Systems, 2008. ICDCS08., 2008. [28]Uwe Schoning. Better expanders and superconcentrators by kolmogorov complexity. In SIROCCO, 1997. [29]Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical Foundations of Computer Science, 1977. [30]Gaven J. Watson, Reihaneh Safavi-Naini, Mohsen Alimomeni, Michael E. Locasto, and Shivaramakrishnan Narayan. Lost: location based storage. In CCSW, 2012.