PoReps: Proofs of Space on Useful Data

Ben Fisch

Stanford University, Protocol Labs

Abstract

A proof-of-replication (PoRep) is an interactive proof system in which a prover defends a publicly veriable claim that it is dedicating unique resources to storing one or more retrievable replicas of a data le. In this sense a PoRep is both a proof of space (PoS) and a proof of retrievability (PoR). This paper establishes a foundation for PoReps, exploring both their capabilities and their limitations. While PoReps may unconditionally demonstrate possession of data, they fundamentally cannot guarantee that the data is stored redundantly. Furthermore, as PoReps are proofs of space, they must rely either on rational time/space tradeos or timing bounds on the online prover’s runtime. We introduce a rational security notion for PoReps called-rational replication based on the notion of an-Nash equilibrium, which captures the property that a server does not gain any signicant advantage by storing its data in any other (non-redundant) format. We apply our denitions to formally analyze two recently proposed PoRep constructions based on veriable delay functions and depth robust graphs. Lastly, we reect on a notable application of PoReps|its unique suitability as a Nakamoto consensus mechanism that replaces proof-of-work with PoReps on real data, simultaneously incentivizing and subsidizing the cost of le storage.

1 Introduction

A proof-of-replication (PoRep) builds on the two prior concepts of proofs-of-retrievability (PoR) [30] and proofs-of-space (PoS) [24]. In the former a prover demonstrates that it can retrieve a le and in the latter the prover demonstrates that it is using some minimum amount of space to store information. Most proofs of space require the prover to use this space to store junk information that is only relevant to the PoS protocol. A PoRep, in essence, embeds a PoR within a PoS. It enables the prover to demonstrate that it is using some minimum amount of space while simultaneously allowing it to actually use that space to store useful information. An additional critical property of a PoRep is that the storage costs required to succeed in the protocol depend only on the size of the data inputs and are otherwise independent of the data inputs. In particular, the cost to succeed in the protocol should not depend on whether or not this data was privately preprocessed (e.g. encrypted by a client) or generated by the server itself. As another special case, if the input to the protocol were k redundant copies of the same le then this would cost the same as running the protocol on k distinct data les. Intuitively, this would achieve the following property: even if a PoRep prover could pass the protocol without storing the data redundantly (e.g. by deduplicating the k copies), there would be no advantage to doing so. In other words, it would be rational for a PoRep prover in this scenario to honestly store k copies of the data.

Consider as a thought exercise a simple composition of a PoR protocol and PoS protocol that would not succeed in achieving these goals. This simple protocol requires the prover to use a total of 2N space. The prover uses half of this space to produce a PoS (i.e. it runs a standard PoS protocol that requires it to ll this space with random data) and it uses the other half to actually store some useful data le of size N and produce PoRs of the le. This satises both a PoR and a PoS with only 2N storage and therefore shows both that the prover is using some minimum (N) amount of storage and is able to retrieve the data of interest. However, it fails the \independent cost" criterion. Namely, it is more expensive for the prover to run this protocol on useful data (requiring 2N space to store both the useful data and the random data) than to just store the useless random data required for the PoS and provide a PoR for this random data (requiring only N space). Moreover, consider if the prover were asked to store k redundant copies of the same le D and use this protocol to prove that it (a) is using at least kN space to store these copies and (b) is able to retrieve D. Following the protocol honestly requires 2kN space: kN space to store the k copies of D and kN space to store the random data required for the PoS. Unfortunately, the most rational strategy would be to store only the random data and a single copy of D as this uses only (k + 1)N space and still allows the prover to successfully pass the protocol.

While standard PoRs can provide proofs of data duplication in a private-verier¹ setting where the client preprocesses its own data before sending it to the server, their security relies on a non-colluding client to privately preprocess the data. One advantage of PoReps over standard PoRs for proofs of data duplication is that multiple clients could contribute data to a single database and would not need to trust any single client to preprocess the data. PoReps could also be used to provide proofs of storage for publicly available data. For example, a consensus server in a massively distributed and open state-replication system such as Bitcoin could provide a PoRep that it is storing a complete history of the state-machine transcript (i.e. in blockchain systems like Bitcoin this is referred to as a \full node" storing the \chain"). Unlike PoRs, PoReps could be used to provide this proof without requiring all the veriers to send the server their own preprocessed copy of the public transcript (incurring impractical communication).

PoReps provide a publicly veriable proof of data duplication, secure against adversaries who will not deviate from an-rational honest strategy. The notion of an-equilibrium is used in game theory as a generalization of a Nash equilibrium where players gain at most an advantage from deviating. This solution concept is appropriate for a malicious-but-lazy adversary, or in conjunction with the status-quo-bias assumption: you are on the couch and the TV remote is across the room, so you continue to watch the same channel. This may seem like a strangely weak security property to achieve in a cryptographic protocol. For a very simple reason it is actually the best possible security that PoReps can achieve, at least in the standard² model of computation for cryptographic analysis. In short, any prover storing k independent replicas of the le could intentionally correlate these replicas in a way that it can still eciently retrieve each in its original format. For example, it could encrypt them and store the key.

However, the primary use case of PoReps is probably not a proof of storage system that weakly discourages de-duplication. The properties achieved by PoReps make it uniquely suited

¹ Verication of PoRs can also be outsourced. Proofs of retrievability where a client can outsource the work of verifying proofs were previously referred to as publicly veriable PoRs or \public PoRs", however the label outsourceable appropriately distinguishes their security property from the public veriability of PoReps and proofs of space.

² This does not preclude secure hardware solutions or proofs based on network timing.

for a Nakamoto consensus mechanism (also known as blockchain consensus) that use PoReps as a useful proof of space in place of Bitcoin’s proof-of-work to achieve sybil-resistance. Briey, Nakamoto consensus mechanisms and its variants are a special type of state-machine replication process managed by an unpermissioned, asynchronous, and distributed network of consensus participants, with the additional feature that the state-machine itself encodes fungible tokens of value. In particular, a dening characteristic of these consensus mechanisms is their ability to mint new tokens in the state machine in order to reward and incentivize consensus participants (termed miners), taking for granted that these tokens represent real-world assets.

Blockchain systems based on proof-of-space have been proposed [19,42] and are in active de- 3 velopment, pursuing goals including energy eciency and more egalitarian distribution. PoReps target a dierent advantage entirely: they simultaneously incentivize useful peer-to-peer data storage. This is the basis of Filecoin [1]. The miners that manage the system’s distributed state-machine are required to produce PoReps in order to append transactions, or equivalently, be elected as temporary consensus leaders, and are rewarded with freshly minted coins in return. Accepting the hypothesis that the miners will be incentivized by these rewards alone to produce PoReps, just as Bitcoin miners produce wasteful proofs-of-work, the rewards{in eect{subsidize the auxiliary useful work accomplished by the PoRep: le storage.

The utility of-rational replication in this context is immediately transparent. It characterizes the cost required to nudge a data replication strategy from a weak equilibrium strategy into a strong one. In other words, it represents the cost that clients must pay (in a stylized model that ignores other market variables) to convince miners to encode their real data inside PoReps rather than \useless" generated data, and therefore the degree to which a system such as Filecoin subsidizes storage costs. PoReps thus sit at an exciting crossroads of economics and cryptography:

PoReps epitomize a cryptographic mechanism that is concerned not solely with the actions and capabilities of an adversary, nor penalties levied for misbehavior, but rather its broader eect on behaviors in an economy.

1.1 Related work

Proofs of storage Cryptographic proofs of storage have been proposed in a variety of avors throughout the literature. Broadly speaking, proofs of storage are interactive protocols between a server (prover) and client (verier) with dierent goals relating to statements about the server’s storage. Proofs-of-retrievability (PoR) [30] demonstrate that the prover can retrieve some specied data known to the verier. A public-key PoR is outsourceable, meaning that the client can provide a public authentication tag that any verier can use to verify the server’s proofs. Unless the data itself is incompressible, a PoR does not necessarily prove anything to the verier about how much space the prover is using in order to retrieve the le. In particular, in the public-key setting the third party verier does not know whether the client is colluding with the server or not, and therefore a PoR is not a truly publicly veriable claim of storage. In proofs-of-space (PoS) [24] a time-constrained prover demonstrates that it is storing some incompressible string of (N) bits, and therefore using at least (N) bits of space. This formulation of PoS is sometimes referred to as a proof of persistent space as opposed to a proof of transient space [46]. Timing assumptions are inherently required in proofs of persistent space due to the eciency

3 The Chia Network is a blockchain system based on PoS, https://chia.net/.

requirement that the communication between the prover and verier is required to be compact, as otherwise the prover can store only the communication transcript and recompute the advice. Proofs-of-secure-erasure (PoSE) [44] are protocols similar to a PoS intended to demonstrate that a storage-bound prover has erased all of its storage. An important dierence between PoSE and the standard PoS notion is that they involve a private-key verier who preprocesses data, similar to a PoR proof. They were suggested as a protocol for a memory-bound embedded device to prove to a server that it has erased private data or all prior code before an update, e.g. to ensure that any malware has been erased.

Rationally secure storage protocols All of the above proof of storage protocols are unconditionally secure, or at least characterize security in terms of strong time-space lower bounds. However, there are additionally a class of proof of storage protocols that are secure in a weaker rational adversary model. The model considered in all of these works is an adversary that acts to minimize its storage costs. Storage enforcing commitments [28] were a precursor to PoR that require the prover to dedicate a minimum amount of storage in order to pass the protocol for a committed le F (preprocessed by a client with a secret key). Their constructions did not guarantee unconditionally that the prover was actually storing F, and were therefore only secure in an epsilon-rational sense. Hourglass schemes [51] were proposed as a generic method to prove that a server is storing data encoded in a specied format, in particular for the use cases of encryption-at-rest and le watermarking. Similarly, they leave open the possibility that the server is also storing a plaintext or non-watermarked version of the le. It only guarantees that such a server must use twice the storage resources to act maliciously.

Proof of data replication vs PoReps A proof of data replication/duplication, specically in the sense of proving that data is stored in a redundant format, is a special case of hourglass schemes. Proofs of data replication/duplication have been explored primarily in the privateclient setting similar to proofs of retrievability [7,47]. In this setting a client is somehow involved in preprocessing the data and either the client is the verier or the client outsources its own verication work. The system Mirror [7] is one such example, which proposed a way for the server to replicate the client’s initially preprocessed le without requiring further communication from the client. The main technique in Mirror is a variant on RSA time-lock puzzles, and the security relies on timing assumptions similar to PoS. Several days ago another paper exploring this line of work was posted, which proposed a construction of proof of data replication in the private-client setting without timing assumptions [21].

The term proof-of-replication (PoRep), which is the focus of our work, was proposed by the Filecoin project [2] in reference to a hybrid of a PoR and PoS that demonstrates in a publicly veriable way that the prover is using space to store a unique replica of a le, or even several unique replicas of the same le. The main intent of this proposed primitive was to resist the so called \generation attack", i.e. it should be a publicly veriable proof of space even when the server may collude with a client. A nearly equivalent concept to proof-of-replication was proposed earlier by Sergio Demian Lerner in 2014 under the name proof of unique blockchain storage [33]. It focussed on the special case where all provers/veriers in the system know at least one copy of the replicated le. For instance, it was proposed as a mechanism for demonstrating publicly that the Bitcoin blockchain is highly replicated. Lerner proposed using time-asymmetric encodings to apply a slow transformation to a le using a unique identier as a key. Boneh et. al. generalized this construction using a new primitive called a decodable veriable delay function

(VDF) [14]. New constructions of PoReps using more traditional tools from proofs of space (i.e. hard-to-pebble graphs) were concurrently proposed in [26,45].

Tight proofs of space As we develop in this work, there is a strong connection between tight proofs of space and PoReps. A tight proof of space is one where any adversarial prover implementing an attack uses only an fraction less space than the honest prover where can be made arbitrarily small. Intuitively, if a PoRep is not a tight proof of space (e.g. = 1*=2) then there may be some adversary that would be rationally incentivized to deviate from honest behavior and therefore likely destroy the replication format. Pietrzak [45] constructed 2 the rst tight PoS, although the proof size is O(1=) and depended on depth robust graphs with rather special properties [6]. Concretely, according to the analysis it requires graphs of degree 2;760 logN* just to achieve 1*=*2 space gap. The PoRep based on veriable delay encodings as a moderately hard function [14] is in fact an arbitrarily tight PoS, however it is exceedingly inecient to generate on large data (scaling quadratically in the data size).

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

1.2 Contributions and Organization

This work is a foundational study of PoReps. Primarily, we motivate the goals of PoReps and explore what they are in contrast to other cryptographic primitives. Although many of the related primitives including proofs of retrievability, proofs of space, and proofs of data replication (private-client setting) were formally dened and studied in prior works, this is the rst comprehensive formal study of PoReps. While a presentation at BPASE 2018 [26] provided the rst basic denitions for PoReps and intuition about both the impossibility of ideal security and how to dene-rational replication, we build upon this further and provide a comprehensive model and denitions. In particular, our framework also addresses issues of composable security noted in a recent paper by Fisch and Silas [27]|namely the issue that the prover may be incentivized to deviate from a rational replication strategy if deviating somehow benets another simultaneous storage mechanism (e.g., perhaps it could use the PoRep data to compress auxiliary data that it is storing).

Relevant background information and preliminary tools are discussed in the AppendixA. While for the most part this is a review, we also present a new formulation of a primitive we call proof of retrievable commitment (PoRC) and a simple generic construction based on vector commitments. This generalizes the simple public proof of retrievability on Merkle commitments that is used ubiquitously, particularly as a subprotocol in proofs of space. Section2denes PoReps abstractly and presents our security model for-rational replication (Denition6). We show that this denition implies that the PoRep is a PoS, although it does not demand it explicitly. Proving that a PoRep construction satises the denition also likely requires \knowledge of compression assumptions" [27]. We formulate one such assumption along with a key lemma (Lemma2) that establishes sucient criteria for-rational replication, showing that if a PoRep construction satises PoRC and PoS in a certain sense then it will also satisfy -rational replication. This greatly simplies the analysis of candidate PoRep constructions. Section3presents in detail the two constructions Basic-VDE-PoRep from VDFs [14] and DRG- PoRep [26] that fuses more traditional techniques in PoS (hard-to-pebble DAGs) with VDFs. Finally, Section4applies the model, denitions, and Lemma2of Section2to formally analyze and prove secure both constructions DRG-PoRep and Basic-VDE-PoRep.

Contents

1 Introduction 1 1.1 Related work. ........... ... .......................3 1.2 Contributions and Organization. ... ..... ... .. ..............5 2 Proof-of-Replication6 2.1 Replication Security Model. .... ... ..... .. ...............10 2.1.1 Impossibility of ideal replication security. ... .... ... ........13 2.1.2 Rational adversary model.. ... ..... ... ............. .13 2.1.3 Security for decentralized storage networks........ ... ......20 3 Constructions21 3.1 Basic PoRep from Veriable Delay Encodings....... ..... ... .....21 3.1.1 Basic-VDE-PoRep . .. ... ... ..... .. .. ..............22 3.2 Block Chaining Encodings. . .. ... ..... ... ............... .23 3.3 DRG PoRep.. .. ....... ... .. .......................25 3.3.1 DRG-PoRep. ...... ..... ... .. ..................26 4 Formal security analysis30 4.1 Labeling games with VDEs. .. ... ... ..... .. ..............31 4.2 Security claims. .......... .................. ........32 A Preliminaries and Background37 A.1 Compression and Erasure Codes.. ... ..... ... ..............37 A.2 Proofs of Retrievability.. .. ..... ... ................. ...38 A.3 Vector Commitments. .. .. .. ... ........................39 A.4 Proof of Retrievable Commitment.. .... ... ................ .40 A.4.1 PoRC Syntax and Denitions. .. ... ..... ... ...........41 A.4.2 PoRC from Vector Commitments... .... ... .. ...........44 A.5 Veriable Delay Encodings. ... ..... ... ..................46 A.5.1 VDE security. . ...... ..........................47 A.6 Depth Robust Graphs.. ... ... ..... ....................48 A.7 Proofs of Space.......... ...........................50 A.8 Graph pebbling games. ...... ......... .................51

2 Proof-of-Replication

We begin with dening the syntax for a proof-of-replication (PoRep). A PoRep operates on arbitrary data D 2 f0*;* 1g of up to O(poly()) size for a given security parameter. All algorithms are assumed to operate in the RAM model of computation (in particular reading a bit of an input is assumed to be an O(1) operation). Parallel algorithms operate in the PRAM model.

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

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 4 period.

$$ \lambda, $$

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

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} $$

$$ N=|D| $$

$$ \tilde{D} $$

$$ \tau_{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).

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

$$ \tau_{D} $$

4. PoRep.Extract(pp;id;;R)! D~ on input replica R and identier id and data tag _D D outputs the data D~ (and veries its consistency with). _D

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

$$ \tau_{D} $$

$$ \tau_{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.

$$ i d,r)\to\pi $$

$$ R, $$

$$ \pi_{i d} $$

6. PoRep.Poll(aux)! r;s: This takes as input the auxiliary replica information aux and outputs a public challenge r along with any private randomness s used to produce this challenge. For public coin constructions s =?.

$$ \mathsf{P O R e p.P o l l(a u x)},\rightarrow,r,s: $$

$$ s=\bot $$

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

$$ i d, $$

$$ \left(i d,\tau_{D},r,s,\mathsf{a u x},\pi\right)\to\left{0,1\right} $$

$$ \tau_{D} $$

$$ 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, such as one involving a public random source) 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 D D to the prover and_Dto the verier.

$$ D, $$

$$ (\tilde{D},\tau_{D})\leftarrow\mathsf{P O R e p P e C}(8h,D) $$

$$ \tilde{D},\tau_{D} $$

$$ \tau_{D} $$

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 on the other hand may use a secret-key, but it is not trusted. In

⁴ An alternative formulation may allow for a variable challenge-response period T that might depend on the size of the data input. Our formulation does not allow this, implying that the online prover PoRep.Prove must run in parallel time less than T (including transmission time of the its proof to the verier) independent of the data size (up to O(poly()) in length). Achieving a xed polling period T for all input data of any reasonable length (i.e.poly()) is important in practice.

$$ T $$

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

$$ (\mathrm{i.e.p o l y}(\lambda)) $$

⁵ 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

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

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

Figure 2.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\leftarrow\mathsf{P o R e p.S e t u p}(\lambda,T) $$

$$ \tilde{D},\tau_{D}\gets $$

particular, the verier is oblivious to whether the preprocessor colludes with the server or not. As we will discuss next the 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 the notion of proof of data replication proposed in the system Mirror. A PoRep scheme may be private coin if the private input r to PoRep.Poll is non-empty, and it is public coin if r = s. A public coin PoRep has the additional desirable property that the challenge output by PoRep.Poll could be replaced by a challenge derived from an unpredictable public random beacon⁶.

Data preprocessing and data retrievability When the data input is preprocessed using a secret-key the resulting PoRep is a public-coin PoR (among satisfying other properties regarding replication and proof of space that we will discuss further in the following section on the PoRep security model). In this scenario we can imagine 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

$$ \tau_{D} $$

⁶ Proofs-of-space-time [2] is a proposed construction that non-interactively chains several PoReps by using the output of the last PoRep as a seed to the next, and would only work for an underlying PoRep that is public coin.

Figure 2.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 $$

work. When the preprocessor runs in keyless mode the resulting PoRep is a PoRC (SectionA.4) with respect to the output_D, which includes a commitment to 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.

$$ D $$

$$ \tau_{D} $$

Treating data preprocessing in this way as a separate \layer of the stack" allows for a wider variety of constructions appropriate in dierent settings without impinging on the eciency of the underlying PoRep protocol itself. In fact, a PoRep protocol that (without preprocessing) satises (; C)-PoRC (e.g. for C partitioning the data into constant size blocks) can immediately be compiled into either a public-key PoR or a PoRC using any number of previous techniques. We highlight the two scenarios:

1.A client has a data le D and uses a randomly generated secret key sk to produce D; ~ _D PoRep.Preproc(sk;D) which applies a rate-adversarial erasure code [15] to D (i.e. one that is resilient to arbitrary adversarial deletions of up to fraction of the blocks in D). The tag is a commitment to D. The adversarial erasure code may involve a D secret transformation using sk and requires sk as well to recover from these errors. The private-key setting enables using more ecient erasure codes that only tolerate random deletions because they can be combined with a secret pseudorandom permutation of the data so that an adversary will only succeed in targeted deletions with up to negligible probability [15,48]. The client then uses_Dfor verication in the PoRep protocol, which we assume is already a (; C)-PoRC with respect to^D. Any verier V can publicly verify that a fraction of the committed D~ is retrievable (and indeed there is a public extraction algorithm for a fraction of blocks in D~), which is sucient for the private client to recover D using sk.

$$ \tilde{D},\tau_{D}\gets $$

$$ .!s k,D) $$

$$ \delta $$

$$ \tau_{D} $$

$$ {tilde\cal D}) $$

$$ \tilde{D} $$

$$ s $$

$$ \tau{cal D D} $$

$$ \delta $$

$$ \tau_{D} $$

$$ \tilde{D} $$

$$ \delta $$

$$ {tilde\cal D}) $$

2.A keyless preprocessor transforms the data le D into a single code word of a deterministic rate-optimal erasure code (e.g., Reed-Solomon) with symbol size equal to the block size in C. It outputs as a deterministic commitment to D, which is also a deterministic D commitment to D. Due to the resilience of the erasure code (D can be recovered from any fraction of the symbols in D), the PoRep (; C)-PoRC of D~ becomes a PoRC of D.

$$ -\delta $$

$$ \tau_{D} $$

$$ \tilde{D} $$

$$ D $$

Eciency All algorithms must run in time O(poly()) and with up to at most O(poly()) parallelism. We don’t directly impose further eciency requirements in the PoRep denition, but implicitly a PoRep scheme cannot be simultaneously correct and secure unless PoRep.Poll and PoRep.Prove have a lower parallel time complexity than PoRep.Replicate on O(poly()) processors. Otherwise, for correctness to hold the challenge-response period will be long enough for an adversarial prover to rerun the replica generation from scratch. Furthermore, for practical purposes it is highly desirable for PoRep.Prove and PoRep.Verify to run in constant or O(polylog(jDj)) time, where jDj is the length of the data le. Among other benets, this enables batched proofs and verication of multiple replicas of the same (or distinct) les, which scales sublinearly in the number of replicas/les. Replica generation PoRep.Replicate runs in time greater than max(T; jDj), however it is desirable for this runtime to be sublinear in T jDj as the size of the le increases.

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

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

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

$$ O(\mathrm{p o l y l o g}(|D|)) $$

$$ m a x(T,|D|) $$

$$ T\cdot|D| $$

Correctness In a correct PoRep construction, a prover who runs PoRep.Replicate and PoRep.Prove honestly must pass verication with probability 1. In order to pass verication the algorithm PoRep.Prove must run in parallel time at most T as otherwise the verier will not receive the output within the challenge-response period. In addition, PoRep.Extract must correctly extract the original data from a replica generated with PoRep.Replicate.

Denition 1 (PoRep correctness). A PoRep construction is correct if for any security parameter , any id and data input D, there exists T such that for all T T , pp PoRep.Setup(;T), and (R;) PoRep.Replicate(pp;id;D) it holds that:

$$ T_{\lambda} $$

$$ T\geq T_{\lambda},;p p\leftarrow\mathit{P o R e p.S e t u p}(\lambda,T) $$

$$ (,tau\)gets mathitmathit{P o R e p.R e p h c a t e(p p,i d,D)} $$

$$ P r \left[ \text {P o R e p . V e r i f y} (p p, i d, r, s, \tau , \pi) = A c c e p t \mid \begin{array}{c} (r, s) \leftarrow \text {P o R e p . P o l l} (p p, \tau) \ \pi \leftarrow \text {P o R e p . P r o v e} (p p, R, i d, r) \end{array} \right] = 1 $$

7 and PoRep.Prove(pp;R;id;r) runs in parallel time at most T . Additionally:

$$ .P r o v e(p p,R,i d,r) $$

$$ T_{\lambda}.^{7} $$

$$ P r\Biggl[\tilde{D}=D\ \Bigg|\begin{array}{l}{R\leftarrow P o R e p.R e p l i c a t e(p p,i d,D)}\ {\tilde{D}\leftarrow P o R e p.E x t r a c t(p p,i d,R)}\end{array}\Biggr]=1 $$

2.1 Replication Security Model

An ideal security goal for PoRep protocols, beyond satisfying the standard denition of a PoR, would be to guarantee the following properties, described informally:

⁷ Mere existence of T may seem like a weak requirement as T could be arbitrarily large, however it is soundness that will fail in this case not correctness. For both soundness and correctness to hold there must exist some T such that the honest prover can succeed in time T and the cheating adversary cannot.

$$ T_{\lambda} $$

$$ T_{\lambda} $$

$$ T_{\lambda} $$

$$ T_{\lambda} $$

$$ \mathcal{A}{\mathrm{p r e}};\mathrm{c h o o s e s};\vec{D}=D{1},...,D_{k}; $$

$$ \vec{i d}=i d_{1},...,i d_{k}; $$

$$ \vec{\tau}=\tau_{D_{1}},....,\tau_{D_{k}} $$

$$ 2:\quad\sigma,\ {vec\\ {x x}}\gets{\mathcal{A}}_{\operatorname{p r e}}(p p,z,{\vec{d}},{\vec{\ }},{\vec{D}}) $$

$$ z,\vec{i d},\mathsf{a}\vec{\mathsf{u}}\mathsf{x}=\mathsf{a}\mathsf{u}\mathsf{x}{1},...,\mathsf{a}\mathsf{u}\mathsf{x}{k} $$

$$ r _ {i} \leftarrow^ {\mathrm {R}} \operatorname {P o R e p}. \operatorname {P o l l} \left(\operatorname {a u x} _ {i}\right) $$

$$ \ {\vec{r}}=r_{1},...,r_{k} $$

$$ \hat{z},\vec{\pi}\leftarrow\mathcal{A}_{\mathrm{o n l}}(p p,\sigma,\mathsf{a u x},\vec{\mathrm{}{i d}},\vec{r}) $$

$$ \ {\vec{\pi}}=\pi_{1},...,\pi_{k} $$

$$ b_{i}\leftarrow\mathsf{P o R e p.}V e r i f y(i\ mathit d_{i},\tau_{D_{i}},r_{i},\mathsf{a u x}{i},\pi{i}) $$

$$ \ \mathrm{O u t p u t}\ {\hat{b}}=\bigwedge b_{i} $$

Figure 2.3: The diagram illustrates the PoRep security game between an adversary and a challenger. Several inputs come from the environment, which runs the setup pp PoRep.Setup(;T) and chooses an auxiliary input z for the adversary. The adversary is split into two components: A_preand A_onl. They may share initial static state but cannot communicate during the game. In particular, A^onldoes not see the input z nor D~ chosen by A (z). It does obtain the inputs pp;; ~aux. This restriction captures the pre fact that may encode a function of auxiliary information z in addition to the replicas of D~. Moreover, A_onlruns in parallel time at most T_onlwhereas A_preis only restricted to run in total time O(poly()).

$$ p p\gets\mathsf{P o R e p} $$

$$ \ _{\mathrm{p r e}} $$

$$ \ _{\mathrm{n l}} $$

$$ \mathcal{A}_{\mathrm{o n l}} $$

$$ \vec{D} $$

$$ \mathcal{A}_{\mathrm{p r e}}(z) $$

$$ p p,\sigma, $$

$$ \sigma $$

$$ \vec{D} $$

$$ \ {mathcal A A}_{\mathrm{o n l}} $$

$$ T_{\mathsf{o n}}| $$

$$ \mathcal{A}_{\mathrm{p r e}} $$

$$ O(p o l y(\lambda)) $$

1.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} $$

2.A prover who passes verication in a PoRep protocol where the input to PoRep.Replicate is a le D~ = D D (consisting of k copies of the same le D) must be storing k independent physical copies of D.

$$ {\tilde{D}}=D\circ\cdots\circ D $$

We will capture these security goals more formally through a game between a PoRep prover (adversary) and a challenger (Figure2.3). A high level overview of the game is as follows. The prover/adversary is split into two components: a replication adversary and an online adversary whose sequential running time (i.e. parallel time) is bounded by a parameter T. The replication adversary is allowed to select the data inputs and the number of replicas k. The replicas do not need to be of all the same les. Specically, we represent this input as a vector D = (D₁;:::;D_k) of data les D_ieach of size N, where some (or all) of the les are identical. The adversary also chooses k unique distinct identiers for each le and k le tags. The prover can then

$$ D=(D_{1},...,D_{k}) $$

$$ D_{i} $$ compute on the data (as in phase 1 of replication) to produce an advice string for the online adversary as well as the auxiliary output ~aux, which includes N (the claimed size of each data le component). The online adversary receives a vector of k challenges from the challenger and must output k proofs. The challenger then runs the PoRep verier on each and outputs the verier’s accept/reject decision.

$$ \sigma $$

k-replication To capture \storing k independent replicas" we say 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. Formally:

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

n Denition 2. Let S be a data source on f0*;* 1g. A string is a k-replication of a data sample k D = (d₁;:::;d_k) S if and only if there is a lossless randomized encoding scheme (enc; dec) and a partition of into k substrings₁;:::;_ksuch that enc(d_i) =_iand dec(_i) = d_ifor all i = 1*;:::;k.*

$$ {0,1}^{n} $$

$$ D=(d_{1},...,d_{k})\leftarrow\mathcal{S}^{k} $$

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

$$ e n c(d_{i})=\sigma_{i} $$

$$ d e c(\sigma_{i})=d_{i} $$

$$ i=1,...,k. $$

Intuitively, security goal (1) can be captured by requiring that any online adversary in the PoRep game who is not given a k-replication of the data by the preprocessor adversary will fail with overwhelming probability. 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. Instead, we will need to relax the security model to consider rational adversaries and bound the cost savings (measured in storage resources) of adversaries who do not store a k-replication of the data input. The security notion we call-rational replication could be informally interpreted as security against an \honest-butopportunistic" adversary that will only employ a malicious strategy if they stand to save more than some cost doing so.

Data tag verication oracle In order to be as general as possible we don’t explicitly require Dto be a commitment to D. Instead, we assume the existence of an oracle Ocheckthat implements a verication procedure on a data/tag pair, perhaps provided additional advice aux, i.e. on input (D;_D;aux) it returns O_check(D;_D;aux)! b 2f0*;* 1g. A special case is where_Dis a commitment to D, aux is the opening hint, and O_checkruns the commitment verication. In other scenarios O_checkmight verify signatures. As discussed previously, we allow for constructions that run in a private-key preprocessor mode and the data inputs/tags are provided by the preprocessor. For instance, they may be data authentication tags like in a more standard PoR scheme.

$$ D $$

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

$$ \mathcal{O}_{\mathsf{c h e c k}} $$

$$ (D,\tau_{D},\mathsf{a u x}) $$

$$ \mathcal {O} _ {\mathrm {c h e c k}} \left(D, \tau_ {D}, \mathrm {a u x}\right)\rightarrow b \in {0, 1 } $$

$$ \tau_{D} $$

$$ D, $$

$$ \mathcal{O}_{\tt{c h e c k}} $$

$$ \mathcal{O}_{\mathsf{c h e c k}} $$

(A)^ Denition 3. PoRep-Exp (z;pp) = (^z;b) is the PoRep game experiment (dened in Fig- ure2.3) with adversary A = (A^pre; A^onl) on inputs z;pp from the environment, represented as a random variable where z^ is the output of A and ^b is the challenger’s output. Out (pp;z) = ^z is A

$$ P o R e p\ E E p sp{(A)}(z,p p),=,\bigl(\hat{z},\hat{b}\bigr) $$

$$ \mathcal{A}=(\mathcal{A}{p r e},\mathcal{A}{o n l}) $$

$$ \hat{b} $$

$$ O u t_{\mathcal{A}}(p p,z)=\hat{z} $$

⁸ 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.

⁹ 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 [52]

(A) the random variable representing the rst component of PoRep-Exp ⁽z;pp⁾, and Succ_Ais the probability that ^b = 1*.*

$$ P o R e p_E x p^{(\mathcal{A})}(z,p p) $$

Denition 4 (Admissible PoRep adversary). For any pp PoRep.Setup(;T) a PoRep game (A) adversary A = (A_pre; A_onl) is admissible for the experiment PoRep-Exp ⁽z;pp⁾ if A_preruns in O(poly()) and A^onlruns in parallel time at most T. The adversary A is-admissible if additionally A chooses data inputs D~ and tags ~ where for each i there exists aux such that pre i O_check(D_i;_Di; aux_i) = 1 and Succ_A.

$$ S u c c_{\mathcal{A}} $$

$$ \hat{b}=1 $$

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

$$ \mathcal{A}=(\mathcal{A}{p r e},\mathcal{A}{o n l}) $$

$$ P o R e p\mathit{-}E x p^{(\mathcal{A})}(z,p p) $$

$$ O(p o l y(\lambda)) $$

$$ \mathcal{A}_{p r e} $$

$$ \mathcal{A}_{o n l} $$

$$ \mathcal{O}{c h e c k}(D{i},\tau_{D_{i}},\mathsf x x_{i})=1 $$

$$ \vec{D} $$

$$ \mathcal{A}_{p r e} $$

$$ \vec{\tau} $$

$$ S u c c_{\mathcal{A}}\geq\mu $$

$$ a u u x{}i $$

2.1.1 Impossibility of ideal replication security

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. 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. We state this formally in the following proposition. Our proof is in the random oracle model for simplicity, although an analogous statement can be proven in the plain model from symmetric key encryption (i.e. PRPs) as long as j j > (this will always be true for A that succeeds on jD~ j > , i.e. causes the challenger to output 1 with non-negligible probability).

$$ \lambda $$

$$ \sigma. $$

$$ \sigma^{\prime} $$

$$ \sigma^{\prime} $$

$$ \sigma^{\prime} $$

$$ \sigma, $$

$$ |\sigma|>\lambda $$

$$ |\vec{D}|>\lambda. $$

Proposition 1. For any admissible adversary A = (A_pre; A_onl) there exists an admissible 0pre 0onl adversary A⁰ = (A; A) (with access to a random oracle H) such that for all pp;z and (A) D = (D₁*;:::;D*_k) chosen by A_prefor any k > 1 the distributions PoRep-Exp (z;pp) and (A0) 0 0onl PoRep-Exp ⁽z;pp⁾ are identical and for ; output by A^onl/A respectively (in Figure2.3, 0**0 line 3), at most one of ; is a k-replication of D and yet j j = j j.

$$ \mathcal{A},=,\big(\mathcal{A}{p r e},\mathcal{A}{o n l}\big) $$

$$ \mathcal{A}^{\prime},=,(\mathcal{A}{p r e}^{\prime},\mathcal{A}{o n l}^{\prime}) $$

$$ p p,z $$

$$ \vec{D};=;(D_{1},...,D_{k}) $$

$$ \mathcal{A}_{p r e} $$

$$ k,>,1 $$

$$ P o R e p\mathit{-}E x p^{(\mathcal{A})}(z,p p) $$

$$ P o R e p_E x p^{(\mathcal{A}^{\prime})}(z,p p) $$

$$ \sigma,\sigma^{\prime} $$

$$ \mathcal{A}{o n l}/\mathcal{A}{o n l}^{\prime} $$

$$ \sigma,\sigma^{\prime} $$

$$ \vec{D} $$

$$ |\sigma^{\prime}|=|\sigma| $$

Proof. A⁰ runs exactly as A with the following modications. A⁰_preruns A_preuntil Line 2 of the game, obtaining*; ~aux*. If j j = 1 then A⁰_preoutputs*; ~aux* and A⁰ on a 1-bit runs exactly onl like A_onl. By hypothesis k > 1, hence a 1-bit is not a k-replication by denition. In case j j > 1, then let₀denote the rst bit of. A⁰_precomputes H(₀) = r, truncating the output of H such that jrj = j j 1 (as A_preruns in time O(poly()) we may assume w.l.o.g. that the 0 0 output of H is longer than) and sets = ⁰jjr. Note that only the rst bit of (i.e. ⁰) contains information about. All substrings of the remaining j j 1 bits are uniformly distributed (they have zero mutual information with the remainder of). Therefore, assuming ~0 0 that is a k-replication of D, then is not a k-replication for k > 1. Finally, A⁰ receives, onl ⁰ 0 computes r = H(₀) by reading the rst bit of, and then recovers = ₀jjr. Then A⁰ _onl (A) uses to run A_onl. The output is identical to PoRep-Exp ₍z;pp₎.

$$ \ {mathcal A}_{\mathrm{p r e}}^{\prime} $$

$$ \mathcal{A}_{\mathrm{p r e}} $$

$$ {\operatorname{I f}}\left|\sigma\right|=1 $$

$$ \ {cal A}_{\mathrm{p r e}}^{\prime} $$

$$ \sigma, $$

$$ \sigma $$

$$ {mathcal A_{\mathrm{o n l}}^{\prime}} $$

$$ \ {\mathcal{A}}_{\mathrm{o n l}} $$

$$ k>1 $$

$$ \sigma $$

$$ |\sigma|>1 $$

$$ \sigma_{0} $$

$$ \mathcal{A}_{\mathrm{p r e}}^{\prime} $$

$$ H(\sigma_{0})=r $$

$$ |r|=|\sigma|-1 $$

$$ \mathcal{A}_{\mathrm{p r e}} $$

$$ O(p o l y(\lambda)) $$

$$ \mathrm{W.l.0g.g} $$

$$ \sigma^{\prime}=\sigma\oplus0||r $$

$$ \sigma^{\prime}\ \mathrm{({i.e.}} $$

$$ \sigma_{0}) $$

$$ \sigma) $$

$$ |\sigma|-1 $$

$$ \sigma $$

$$ \sigma) $$

$$ {mathcal A}_{\mathrm{o n l}}^{\prime} $$

$$ \vec{D} $$

$$ r=H(\sigma_{0}) $$

$$ \sigma^{\prime} $$

$$ \sigma^{\prime} $$

$$ k>1 $$

$$ \sigma=\sigma^{\prime}\oplus0||r $$

$$ \sigma^{\prime}. $$

$$ \sigma $$

$$ {mathcal A_{\mathrm{o n l}}^{\prime}} $$

$$ \mathcal{A}_{\mathrm{o n l}} $$

2.1.2 Rational adversary model

$$ \mathsf{P o R e p-E x p}^{(\mathcal{A})}(z,p p) $$

Given the impossibility of achieving PoRep security entirely based on cryptographic guarantees, we turn instead to a framework of modeling attacks based on incentives. A rational adversary model has been used many times before in related works. In fact, it is implicit in proofs of space where security is reasoned via time/space tradeos [40] rather than challenge-response timing, which is necessary in proofs of space that are not parallel sound [3,46]. It was also invoked to model security in storage enforcing commitments, hourglass schemes, and private-client proof of data replication [7,28,51]. The threat model considered in all of these works is an adversary that acts to minimize its costs, measured in storage or work (and combinations of the two).

In our setting, independent from any client setup/preprocessing, any prover that passes k independent PoRep interactive protocols on k data le commitments should not save any costs by running a strategy that does not store a recoverable copy of the le in each protocol, even if this involves storing duplicate copies of the same le. The same holds if the prover passes a single PoRep interactive protocol on a single committed data le that contains redundant data. More precisely, for any successful strategy there is another \well-behaved" and eciently computable strategy satisfying k-replication that uses no more than a factor 1*=*(1) more storage, i.e the adversarial strategy saves at most an fraction of the storage by deviating from honest k-replication. Importantly, this \well-behaved" strategy should still retain all the information that the original adversary was storing, which we capture by saying that the new strategy simulates the output distribution of the original adversary in the security game. We call this security notion-rational replication.

Security under composition A challenge that arises in both dening and proving-rational replication for PoReps is showing that adversarial strategies do not save costs even in composition with other protocols, in particular in the presence of auxiliary data on the server. While composition is always a security challenge often overlooked, it is especially salient here. One might think it would be sucient to show that the adversary cannot compress its replicas by encoding them in a dierent (malicious) format that no longer preserves replication. However, we must also consider that the adversary may be able to use the replica storage to help store other useful information on its hard drive. Suppose, for instance, that the (incompressible) replicas could be used as a seed to compress this auxiliary data, yet in a way that also entangles the seed together with the auxiliary data, destroying the replication format (i.e. a weak compression Denition11). In this case, the adversary may actually save costs by deviating.

Fisch and Silas [27] showed that proving this is likely impossible without strong knowledge assumptions. Their analysis focussed on the \weak compression attack" described above, where the PoRep storage could be used as a seed to compress auxiliary data in a way that also destroys the replication format. One might hope to prove rational security by showing that any adversary who weakly compresses auxiliary data in this way can be converted to a better adversary that compresses its auxiliary storage just as well without destroying its replicas, i.e. coverts the weak compression to a strong compression (Denition12) that would save the seed independently in its original format. However, they prove that any black-box reduction of strong compression to weak compression for a given class of sources would yield a universal compression scheme for that class in the random oracle model. In other words, proving this is as hard as constructing a universal compression scheme that works on any source in the class.

\Knowledge-of-compression" assumptions In light of their result, Fisch and Silas propose using a \knowledge of compression" assumption. Intuitively, any adversary who knows a way to compress auxiliary data z using an incompressible string s must only be taking advantage of the compressibility of z, hence entangling z together with s should not help. Specically, the minimal assumption proposed in their paper is that any adversary who can compute a weak compression of z with an independent uniformly sampled seed s can also extract a strong compression of z.

They also remark that some PoS constructions are proven secure by showing that the advice output s directly encodes part of a random oracle’s function table, and in this case the minimal assumption suces to show that any weak compression involving the PoS advice s as a seed can be converted to a strong compression. Unfortunately, this property is not true of PoReps 10 because the underlying PoS advice actually encodes the committed data le D. Therefore, we require a stronger knowledge of compression assumption that applies to any incompressible seed s, even where the incompressibility applies only to strictly time bounded compression schemes.

$$ D.^{10} $$

Denition 5 (Time bounded incompressibility). A source S is (T₁;T₂)-incompressible to k bits if there does not exist (for any constant) a-lossy strong compression scheme (enc; dec) where enc runs in parallel time T₁ and dec runs in parallel time T₂ that compresses S to k log(1*=*) bits.

$$ (T_{1},T_{2}) $$

$$ T_{1} $$

$$ T_{2} $$

$$ k-\log(1/\delta) $$

Assumption 1 (Knowledge of strong compression). Let S and X be any two samplable sources n over f0; 1g such that S is (T₁;T₂)-incompressible to (1)n bits for some < 1. For any compression scheme (enc; dec) that compresses SX to m bits where enc runs in parallel time T₁ or dec runs in parallel time T₂, there exists a strong compression scheme (enc ; dec) running in parallel time T₁ and T₂ respectively that compresses X to length m (1)n bits sampling seeds from S. Moreover, for any algorithm A that on inputs S and n outputs (enc; dec), there exists an ecient \extractor" which observes A’s internal state and outputs (enc ; dec).

$$ {0,1}^{n} $$

$$ (T_{1},T_{2}) $$

$$ (1-\epsilon)n $$

$$ \epsilon,<1 $$

$$ S\times X\ $$

$$ T_{1} $$

$$ T_{2} $$

$$ (e n c^{},d e c^{}) $$

$$ {_T T} $$

$$ T_{2} $$

$$ m-(1-\epsilon)n $$

$$ (e n c^{},d e c^{}) $$

Denition of rational replication We will x several notations regarding discrete probability distributions before presenting our formal denition of-rational replication. If X is a 0/1 random variable with probability mass function p_Xand Y is a discrete random variable on the same probability space then p_XjY : Sup(Y)! R is the function p_XjY (w) = Pr[X = 1jY = w]. If f;g are two real valued functions on a set then f g if and only if f (w) g(w) for all w 2, i.e. f is an upper bound on g.

$$ 0/1 $$

$$ p_{X}|Y:\operatorname*{S u p}(Y)\to\mathbb{R} $$

$$ p_{X}\ Y(w)=P r\big[X=1\big|Y=w\big] $$

$$ f,g $$

$$ f\succeq g $$

$$ f(w)\geq g(w) $$

$$ w\in\Omega $$

Finally, for any two random variables X;Y let X() Y () denote that the distributions 11 of X and Y are computationally indistinguishable.

$$ X(\lambda)\stackrel{\lambda}{\approx}Y(\lambda) $$

Denition 6 (Rational replication). A PoRep construction is a-sound-rational replication if for any-admissible adversary A = (A^pre; A^onl) there exists an admissible adversary A⁰ = 0pre _0onl~ (A; A) such that for all pp;z sampled by the environment and D = (D₁;:::;D_k) chosen by 0 0onl A_pre, and for ; output by A_onl/A respectively (in Figure2.3, line 2) then for all z from the environment and pp PoRep.Setup(;T) it holds that:

$$ \mathcal{A}=(\mathcal{A}{p r e},\mathcal{A}{o n l}) $$

$$ {\mathcal{A}}^{\prime},= $$

$$ (\mathcal{A}{p r e}^{\prime},\mathcal{A}{o n l}^{\prime}) $$

$$ \vec{D}=(D_{1},...,D_{k}) $$

$$ \mathcal{A}_{p r e} $$

$$ \sigma,\sigma^{\prime} $$

$$ \mathcal{A}{o n l}/\mathcal{A}{o n l}^{\prime} $$

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

$$ |\sigma|\leq(1-\epsilon)|\sigma^{\prime}| $$

⁰~ 2. is a k-replication of D

$$ \sigma^{\prime} $$

$$ \vec{D} $$

$$ \mathit{O u t}{\mathcal{A}^{\prime}}(p p,z)\overset{\lambda}{\approx}\mathit{u t}{\mathcal{A}}(p p,z)\mathrm{}{a n d}\mathit{S u c c}{\mathcal{A}^{\prime}}|\mathit{O u t}{\mathcal{A}^{\prime}}(p p,z)\succeq\mathit{u c c}{\mathcal{A}}|\mathit{O u t}{\mathcal{A}}(p p,z).{}^{.12} $$

¹⁰ The security might still be proven by showing how to encode a random oracle table using S together with D [45], but the remark in [27] no longer applies in this case. Moreover, the prover can even choose D to be correlated with the auxiliary data z.

¹¹ The standard denition of computationally indistinguishable distributions with respect to a security parameter is that no poly() time algorithms can distinguish samples from the two distributions except with probability negligible in.

¹² This says that for any value of z^ the probability A succeeds given that it outputs z^ is bounded by the probability that A⁰ succeeds given that it outputs ^z.

Necessary and sucient conditions for-rational replication PoReps satisfyingrational replication are implicitly proofs of space with an space gap. The converse is not necessarily true, i.e.-tight proofs of space are not immediately PoReps satisfying-rational replication. Furthermore, unless_Dis binding to D relative to O_check, meaning that for any_D there does not exist (or it is computationally dicult to produce) D⁰ 6= D and aux⁰*;aux such that O_check(D;_D;aux) = O_check(D⁰;_D;*aux⁰) = 1, then it is unclear how a scheme could satisfy our denition (or any meaningful denition of replication security for that matter where the adversary is allowed to choose the data). If O_checkis not binding then even rational replication security would likely fail because the adversary could nd an alternative data input D⁰ 6= D consistent with the same tag and run the rest of the protocol successfully on D⁰ as if it were the input. Formally, this would fail our security denition if any adversary that stores a k-replication of the original data input D could not output the same distribution (e.g. the adversary’s output z^ is some function of z and D⁰).

$$ D $$

$$ \tau_{D} $$

$$ \tau_{D} $$

$$ \mathcal{O}{\mathsf{c h e c k}}(D,\tau{D},\mathsf{a u x})=\mathcal{O}{\mathsf{c h e c k}}(D^{\prime},\tau{D},\mathsf{a u x}^{\prime})=1 $$

$$ D^{\prime}\neq D $$

$$ \mathcal{O}_{\mathsf{c h e c k}} $$

$$ D^{\prime}\neq D $$

$$ D^{\prime} $$

$$ D $$

$$ D^{\prime}) $$

Implicit PoS protocol If a PoRep construction satises Denition6then PoRep.Setup, PoRep.Replicate, PoRep.Prove, and PoRep.Verify implicitly dene a secure PoS as follows:

Setup runs PoRep.Setup(;T)

R~) and outputs Initialization The prover runs R; aux PoRep.Replicate(id;_D; D_D= aux and S = R.

$$ R,\mathsf{a u x}\xleftarrow{\tt R}\ mathsf{P o R e p.R e p l i c a t e}(\mathrm{}{i d},\tau_{D},\tilde{D}) $$

$$ \tau_{D}=\mathsf{a u x} $$

$$ S=R $$

Execution The verier’s challenge is r PoRep.Poll(aux) and the prover responds with the proof PoRep.Prove(R; aux*;id;r*). The verier runs PoRep.Verify(id;_D;r; aux*;*).

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

$$ \pi\gets\mathsf{P o R e p.o r o}(R,\mathsf{a u x}d,r) $$

$$ \mathsf{V e r i f y}(i d,\tau_{D},r,\mathsf{a u x},\pi) $$

We say that a PoRep scheme is an (s;t;)-sound PoS if its implicit PoS protocol is an (s;t;)-sound PoS (see SectionA.7, or Denition23).

$$ (s,t,\mu) $$

$$ (s,t,\mu) $$

Lemma 1 (PoS is necessary). If a PoRep is a-sound-rational replication then it is an ((1)kN;T;)-sound PoS.

$$ ((1-\epsilon)k N,T,\mu) $$

Proof. Suppose not, i.e. there is some PoS adversary that succeeds in passing verication with probability greater than using only (1)kN storage.

Let D~ be a vector of k identical copies of an incompressible data input D. By incompressible, we mean that for any randomized enc*=dec scheme such that Pr[enc(dec(D)) = D] = then jenc(D)j N log(1=) where N = jDj. It follows that any k-replication of D must be at least kN bits long because by denition it can be partitioned into k substrings each of which are a deterministic encoding of D. Now take the PoS adversary A_PoSwho is able to pass Execution within time T with (1)kN storage and construct A_PoRep= (A_pre; A*_onl). A_presimulates the Initialization phase for A_PoSto obtain the outputs (;S). It then sets aux = and = S. Then for each challenge query, A_onlsimulates the Execution phase for A_PoS, passing it and S. Thus, by assumption A_onlsucceeds (i.e. the challenger outputs ^b = 1) with probability greater than. In other words, A_PoRepis-admissible. Now, since j j (1)kN it cannot be a k-replication of D due to the fact that D is incompressible and any k-replication of D 0 0 must be at least kN bits long. In fact, if any (A⁰_pre; A⁰) outputs where is a k-replication onl 0 of D then j j kN > j j=(1). On the other hand, by the hypothesis that the PoRep is a-sound-rational replication, there exists some ( negl())-admissible A⁰ that outputs a 0 0 k-replication (Condition 3 + Condition 2) such that j j < j j=(1) (Condition 1). This is a contradiction.

$$ \mu $$

$$ (1-\epsilon)k N $$

$$ \vec{D} $$

$$ P r[\mathsf{e n c}(\mathsf{d e c}(D))=D]=\xi $$

$$ |\mathsf{e n c}(D)|\geq N-\log(1/\xi) $$

$$ N=|D| $$

$$ \mathcal{A}_{P o S} $$

$$ T $$

$$ \mathcal{A}{P o R e p}=\left(\mathcal{A}{\mathrm{p r e}},\mathcal{A}_{\mathrm{o n l}}\right) $$

$$ (1-\epsilon)k N $$

$$ \mathcal{A}_{P o S} $$

$$ \mathcal{A}_{\mathrm{p r e}} $$

$$ \sigma,=,S $$

$$ \ {\mathcal{A}}_{\mathrm{o n l}} $$

$$ \mathcal{A}_{P o S} $$

$$ \ {\mathcal{A}}_{\mathrm{o n l}} $$

$$ S, $$

$$ \mathcal{A}_{P o R e p} $$

$$ \mu. $$

$$ \hat{b}=1) $$

$$ |\sigma|\leq(1-\epsilon)k N $$

$$ (\mathcal{A}{\mathrm{p r e}}^{\prime},\mathcal{A}{\mathrm{o n l}}^{\prime}) $$

$$ \sigma^{\prime} $$

$$ \sigma^{\prime} $$

$$ | \sigma^ {\prime} | \geq k N > | \sigma | / (1 - \epsilon) $$

$$ (\mu-\mathsf{n e g}(\lambda)) $$

$$ \sigma^{\prime} $$

$$ |\sigma^{\prime}|<|\sigma|/(1-\epsilon) $$

Implicit PoRC protocol If the data tag_Dis binding to the data input D and aux ~ is a binding commitment to the replica R then a PoRep may implicitly dene a (; C)-PoRC protocol of (D;R) with respect to (_D;aux) (SectionA.4). The cover C in this case is the set of pairs of blocks (R_i;D_i) such that R is dened to be the correct output of PoRep.Replicate(id_i;_D;D), D_iis the ith block of D, and R_iis the ith block of R. The setup just runs the PoRep setup and outputs parameters pp. The PoRC.Prove and PoRC.Verify procedures simply run the PoRep prover and verify procedures.

$$ \tau_{D} $$

$$ (D,R) $$

$$ (R_{i},D_{i}) $$

$$ (\mathrm{{d}}{i},\tau{D},D) $$

$$ R_{i} $$

$$ D_{i} $$

PoRC.Commit(pp;D): Run PoRep.Preproc(sk;D) to obtain the data tag along with D. D Then run PoRep.Replicate(id;; D) to get (R; aux). Save the hint = (R;id). Output the D commitment com = (_D*;*aux).

$$ \tau_{D} $$

$$ \tilde{D} $$

$$ \Lambda=(R,i d) $$

$$ c o m=(\tau_{D},\mathsf{a u x}) $$

PoRC.Open(pp;com;): Parse = (R;id) and com = (_D;aux). Next run the extraction procedure PoRep.Extract(pp;id;_D;R) to obtain D. Query b O_check(D;_D;aux). If b = 0 output? otherwise output (D;R).

$$ \Lambda,=,(R,i d) $$

$$ c o m,=,\ \big(\tau_{D},\mathsf{a u x}\big) $$

$$ b\gets\mathcal{O}{\mathsf{c h e c k}}(D,\tau{D},\mathsf{a u x}) $$

$$ b=0 $$

PoRC.Prove(pp;com;;c): Parse = (R;id) and com = (_D;aux). Generate the PoRep proof 0 ⁰ as PoRep.Prove(R; aux;id;r) output the PoRC proof = (;id).

$$ \Lambda=(R,i d) $$

$$ {\mathfrak o m}=(\tau_{D},{\mathsf{a u x}}) $$

$$ \pi^{\prime} $$

$$ \pi=(\pi^{\prime},i d) $$

0 PoRC.Verify(pp;com;c;): Parse com = (_D;aux) and = (;id). Output the result b of 0 PoRep.Verify(id;_D;c; aux*;*).

$$ {\bf\sf}=(\tau_{D},{\sf a u x}) $$

$$ \pi,=,(\pi^{\prime},i d) $$

We say that a PoRep scheme is a-sound-PoRC if its implicit (; C)-PoRC protocol as just described is-sound (see Denition18).

The following powerful lemma establishes criteria that along with Assumption1are sucient for-rational replication. This greatly simplies the analysis for any PoRep construction that is also implicitly a secure public-coin PoRC protocol.

Lemma 2 (Sucient conditions for rational replication). Given Assumption1, if a PoRep construction with setup parameters T; satises the following conditions for some integer c:

$$ T,\lambda $$

(a)It is correct (see Denition1)

(b)It is a-sound (1)-PoRC, and the parallel runtime blowup of the extractor is less than a factor c, i.e. it is PRAM strongly-sound (see Denition18).

(c) k independent PoReps are a parallel ((1 +)kN;(c+1)T;)-sound PoS (see SectionA.7, or Denition23).

then the PoRep construction is a-sound-rational-replication.

Proof. The outline for the proof is as follows. We consider any-admissible PoRep adversary A = A = (A^pre; A^onl) and construct the \well-behaved" adversary A = (A⁰_pre; A⁰) that satises onl the three conditions of Denition6. Since A is-admissible for each i it chooses each D_i;_Di and outputs aux_isuch that O_check(D_i;_Di;aux_i) = 1. A-admissible PoRep adversary is also a -admissible PoRC adversary in the implicit (1; C)-PoRC protocol. Hypothesis (b), that the implicit (1*; C*)-PoRC protocol is-sound, by denition means there exists a public extraction algorithm E^Athat A⁰ could run with A^onlto extract at least a (1) fraction of the correct onl blocks in each (R_i;D_i), denoted by (R;D). Let R = (R₁;:::;R) and D = (D₁;:::;D). E_A i i k k

$$ \mathcal{A}=\mathcal{A}=\left(\mathcal{A}{\mathrm{p r e}},\mathcal{A}{\mathrm{o n l}}\right) $$

$$ \mathcal{A}=(\mathcal{A}{\mathrm{p r e}}^{\prime},\mathcal{A}{\mathrm{o n l}}^{\prime}) $$

$$ \mathtt{a u x}_{i} $$

$$ D_{i},\tau_{D_{i}} $$

$$ \mathcal{O}{\mathsf{c h e c k}}\big(D{i},\tau_{D_{i}},\mathsf{a u x}_{i}\big)=1 $$

$$ (1!-!\delta,\mathcal{C})\mathrm{-P}\mathrm{o R C} $$

$$ \mathcal{E}_{A} $$

$$ \ {\mathcal A}_{\mathrm{o n l}}^{\prime} $$

$$ \ {\mathcal{A}}_{\mathrm{o n l}} $$

$$ (R_{i},D_{i}) $$

$$ (R_{i}^{},D_{i}^{}) $$

$$ R^{}=(R_{1}^{},...,R_{k}^{*}) $$

$$ D^{}=(D_{1}^{},...,D_{k}^{*}).~\mathcal{E}_{\mathcal{A}} $$ runs in time at most c tonlwhere tonl< T is the runtime of Aonl(by the assumption that A is admissible).

$$ \mathcal{A}_{\mathrm{o n l}} $$

$$ t_{\mathrm{o n l}}<T $$

$$ c\cdot t_{\mathrm{o n l}} $$

We show (in Subclaim 1) that A^pre, A^onl, and E^Acan be used to construct a lossless com- A pression scheme (enc*;dec) that encodes E^A’s output R and A’s output z^ = Out (pp;z) in (A PoRep-Exp ₍pp;z), where enc(R ; z^) = (;aux) such that j jj j + negl() and dec runs in total time cT. On the other hand, we show (in Subclaim 2) that Hypothesis (c) implies that R is (poly(N);* (c+1)T;)-incompressible to (1)kN bits. Together with Assumption 1, Subclaim 1 and Subclaim 2 imply that A⁰ can compute a new strong compression scheme (enc*;*dec ) onl that uses R as a seed to encode compress z^ to j j (1)kN j j (1)kN + negl() 0 bits. Finally, A⁰_preoutputs = Rjjenc (R ; z^) and the same aux ~, and A⁰ uses dec to recover onl 0 z^. Note that j jjRj + j j (1)kN + negl() = j j + kN + negl(). A⁰ nally runs the onl honest PoRep.Prove so Succ_A0 = 1 and Out_A0 Out_Aare identically distributed.

$$ \mathcal{A}{\mathrm{p r e}},,\mathcal{A}{\mathrm{o n l}} $$

$$ \mathcal{E}_{A} $$

$$ R^{*} $$

$$ \ {{\cal A}^{\prime}}mathrm{~s} $$

$$ {\hat{z}},=,\mathsf{O u t}^{\mathcal{A}}(p p,z) $$

$$ \mathcal{E}_{\mathcal{A}}{}^{\prime}\varsigma $$

$$ \mathsf{P o R e p x E x p}^{(\mathcal{A}}(p p,z) $$

$$ (R^{},\hat{z})=(\sigma^{} $$

$$ |\sigma^{*}|\leq|\sigma|+{\mathsf{n e g l}}(\lambda) $$

$$ R^{*} $$

$$ \ {\cal A_{\mathrm{o n l}}^{\prime}} $$

$$ (\mathsf{e n c}^{},\mathsf{d e c}^{}) $$

$$ R^{*} $$

$$ | \sigma^ {*} | - (1 - \epsilon) k N \leq | \sigma | - (1 - \epsilon) k N + \operatorname {n e g l} (\lambda) $$

$$ {cal A}_{\mathrm{p r e}}^{\prime} $$

$$ \sigma^{\prime}=R||e n c^{}(R^{},\hat{z}) $$

$$ {mathcal A}_{\mathrm{o n l}}^{\prime} $$

$$ d e c^{*} $$

$$ |\sigma^{\prime}|\leq|R|+|\sigma|-(1-\epsilon)k N+\mathsf{n e g l}(\lambda)=|\sigma|+\epsilon k N+\mathsf{n e g l}(\lambda).\ \mathcal{A}_{\mathrm{o n l}}^{\prime} $$

$$ \mathsf{O u t}{\mathcal{A}^{\prime}}\approx\mathsf{O u t}{\mathcal{A}} $$

$$ \ div mathcal A{'}=1 $$

The existence of this A⁰ for any-admissible adversary A shows that the PoRep satises A0 0 -sound-rational replication. It satises Out Out^Aand SuccA jOutA0 SuccAjOutA. 0 0 The the advice includes R and is thus a k-replication of D (Condition 2) with j j kN + j j + negl() j j + j j + negl() j j=(1) + negl() (Condition 1). 1

$$ \mathsf{O u t}^{\mathcal{A}^{\prime}}:\approx:\mathsf{O u t}_{\mathcal{A}} $$

$$ \mathcal A^{\prime}|\sf{O u t}{\mathcal A^{\prime}}\succeq\sf{S u c c}{\mathcal A}|\sf{O u t}_{\mathcal A} $$

$$ \sigma^{\prime} $$

$$ |\sigma^{\prime}|\ \leq $$

$$

$$

Proof of Subclaim 1: Let R denote the distribution of R extracted by E_Aover the randomness of E_A, A_pre, and A_onl. Note that because A is-sound R always contains a 1 fraction of the blocks of R, where R is the correct output on the input D chosen by A_preexcept with at most probability negl() (that either the binding of O_checkis broken or the extraction fails). Let Z denote the distribution of ^z given the xed environment inputs z;pp. By simulating the game for A and running the extractor E_Awe can perfectly sample both of these distributions. The sampled values R and ^z are given as input to enc along with aux and the randomness used in the sampling. The randomness and aux will be shared by both enc and dec so we treat this as a seed.

$$ R^{*} $$

$$ \mathcal{A} $$

$$ \mathcal{E}_{\mathcal{A}} $$

$$ \mu $$

$$ R^{*} $$

$$ \ {\mathcal{A}}_{\mathrm{o n l}} $$

$$ 1-\delta $$

$$ \mathcal{E}{\mathcal{A}},,\mathcal{A}{\mathrm{p r e}} $$

$$ \mathcal{A}_{\mathrm{p r e}} $$

$$ \mathcal{O}_{\mathrm{c h e c k}} $$

$$ z,p p $$

$$ \mathcal{E}_{A} $$

$$ R^{*} $$

$$ \rho $$

$$ \hat{z} $$

$$ \rho $$

enc uses to deterministically rerun A_preto obtain and sets enc(;R ; z^) =.

$$ \rho $$

$$ \mathcal{A}_{\mathrm{p r e}} $$

$$ \sigma $$

$$ (\rho,R^{*},\hat{z})=\sigma $$

dec runs E_Awith inputs and aux ~ to extract R from A_onl(in parallel time at most c t_onl) and outputs R while also using to rerun A_onlon a given challenge vector to obtain ^z. dec outputs R and ^z. Hence, (enc*;dec) is a strong compression scheme on the source RZ with loss negligible in, i.e. Pr[dec(;enc(;R ; z*^) = R ; z^] > 1 negl(). Finally, by Fact1, it can be converted to a lossless compression with a negl() increase in output length.

$$ \sigma $$

$$ R^{*} $$

$$ \mathcal{E}_{\mathcal{A}} $$

$$ \ {\mathcal{A}}_{\mathrm{o n l}} $$

$$ c\cdot t_{\mathrm{o n l}}) $$

$$ R^{*} $$

$$ \rho $$

$$ \mathcal{A}_{\mathrm{o n l}} $$

$$ \hat{z}, $$

$$ R^{*} $$

$$ \hat{z}, $$

$$ \mathcal{R}\times\mathcal{Z} $$

$$ P r[\mathsf{d e c}(\rho,\mathsf{e n c}(\rho,R^{},\hat{z})\ \mathrm=\ R^{},\hat{z}]\ \mathrm{}{>}\ \mathsf{1\mathrm}{}-\mathsf mathsf{n e g l}(\lambda)} $$

$$ {\lambda,} $$

Proof of Subclaim 2: As R is the correct output of PoRep.Replicate and the PoRep construction is a ((1 +)kN;(c + 1)T;)-sound PoS, R is (poly(N); (c + 1)T;)-incompressible to 0 (1 +)kN bits. Otherwise, for some > an adversary could compress R during the 0 replication phase to (1 +)kN bits and store this-lossy compression as its advice. It 0 could then recover R in the challenge-response phase with probability and run the honest PoRep.Prove in total parallel time less than (c + 1)T. This adversary would break the presumed PoS soundness. Likewise, as R consists of a 1 fraction of blocks from R, it is (poly(N); (c + 1)T;)-incompressible to (1)kN bits, because compressing R to (1)kN bits is equivalent to compressing R to (1 +)kN bits.

$$ \mathfrak{k}\ \ \
$$

$$ (\mathrm{p o l y}(N),(c+1)T,\mu) $$

$$ (1-\epsilon+\delta)k N $$

$$ \mu^{\prime}>\mu $$

$$ \mu^{\prime} $$

$$ \mu^{\prime}\mathrm{l l o s y} $$

$$ (1-\epsilon+\delta)k N $$

$$ R, $$

$$ R^{*} $$

$$ 1-\delta $$

$$ (\mathrm{p o l y}(N),(c+1)T,\mu) $$

$$ R^{*} $$

$$ (1-\epsilon)k N $$

$$ (1-\epsilon+\delta)k N $$

Remark on loss: Lemma2requires that the PoRep has only a space gap as PoS in order to prove it satises-rational-replication, where is the loss in the PoRC. The reason this aects

$$ \delta $$

$$ \epsilon!-! $$

$$ \delta $$ the proof that the PoRep is-rational-replication is entirely due to the environment auxiliary input z and the need to show that the adversary A⁰ can still output the same distribution (including the function of z) as the adversary A. (This necessitated constructing A⁰ that extracts the replica R from A). If this requirement were dropped (or the auxiliary input z is empty) then conditions (a) and (c) suce without any loss, i.e. if the PoRep is correct and a (1)kN;T)- sound PoS then it is-rational secure. The reason is that A⁰ could just run the honest replication 0 strategy, where = R and jRj = kN. Any adversary that causes the challenger to output ^b = 1 must use of size at least (1)kN by the PoS soundness.

$$ (1-\epsilon)k N,T) $$

$$ \sigma^{\prime}=R $$

$$ |R|=k N $$

$$ \hat{b}=1 $$

What is missed by simply composing PoR and PoS? It is instructive to consider simply combining a proof of retrievability (PoR) with a proof of space (PoS) as a trivial candidate PoRep. For a le D of size N, the honest prover would use N bits of storage to produce a PoS and separately store D. First, this results in at least a factor two space gap (the gap between the honest prover’s total space usage and the lower bound on an adversary’s space). The more criticial issue is that the adversary is clearly incentivized to only use N bits of storage for the PoS and drop the le entirely, provided that it can recover the le from another source. There is explicitly a factor two added cost for storing the le in addition to producing a proof of space. A prover is strongly incentivized to deduplicate its storage. In other words, this protocol fails -rational replication for any < 1, nor does it have data-independent costs. Thus we can see that at a minimum our denition requires that PoReps are simultaneously a PoS and PoR without costing the miner any extra space to store the entire le (or some encoding thereof that allows full recovery).

Space utilization There is still a silly way to combine PoS and PoR to achieve-rational replication without imposing another eciency requirement on the construction that has to do with space utilization. Suppose a PoS of N bits guarantees that the adversary is using at least N bits (while the honest prover uses N bits). The trivial PoRep construction on a le D of size N would be a-PoS on m >> N bits (say m kN) combined with a PoR of D. The naive prover following this protocol uses at least (k + 1)N bits, while an adversary must use at least kN bits. The additional cost to this adversary of storing D is at most N bits, for a total storage of (k + 1)N, which is an = 1*=(k) overhead. This can be made arbitrarily small by increasing k. More generally, we can modify any PoRep scheme that is both a PoR and a m -PoS to operate on padded data Djj0 for m = kjDj so that there is ony an = 1=(k) cost to additionally storing the le. However, at the same time, this generic construction utilizes only an fraction of the prover’s total space for useful storage. Ideally, we would like a construction that utilizes most of the space, independent of. Restricting to PoRep constructions that can be tuned to satisfy-rational replication using O(N) space even as!* 0 excludes these wasteful constructions.

$$ m:>:N $$

$$ m\geq k N) $$

$$ (\delta k+1)N $$

$$ m=k|D| $$

$$ D||0^{m} $$

$$ \epsilon=1/(\delta k) $$

Private-verier setting We note that these subtleties in dening proofs of replication are also relevant in the private-verier setting of proofs of data replication. They were missed in the security model proposed by Mirror [7], whose denition is in fact satised by even the trivial combination of a PoS and PoR. Mirror’s security denition compares the adversary’s storage to the storage of a prover who stores both the original le D and r replicas specied by the protocol. Consider the trivial construction in which each \replica" is simply an independent proof of space initialization, and the verication procedure involves a PoR of D along with r PoS verications. Since in this setting the data le is chosen by the verier/challenger and is assumed to be incompressible, the adversary must use as much space as the honest prover in 13 order to pass verication.

2.1.3 Security for decentralized storage networks

As we touched upon in the introduction, a primary intended use-case for PoReps is as a protocol that will help both incentivize and monitor le storage in a distributed network of nodes, which are compensated by the network in return for storing client data. Critically, these nodes are not directly compensated by the client. Rather, they are compensated for storing any data as long as the network veriers (distinct from clients submitting data) can publicly verify they are storing the data. In fact, the network protocol may aggregate data pieces from several clients together and pass that to a storage node.

If clients were to pay storage nodes directly, say by putting a lump sum of money in escrow that the storage node receives in installments for continuing to store the le, then PoReps aren’t necessary. The role of network veriers would be to verify that the storage node is still storing the client’s le using a standard proof of retrievability with outsourced verication, and then approve transfer of installment funds from the escrow account to the storage node. The storage node has nothing to gain from colluding with the client. It is only when we want the network itself to incentive storage participation from a source external to the client/node that PoReps actually become relevant.

The main thesis of the Filecoin [1] protocol is that by double using PoReps as a \proof-ofresource" (i.e in place of proof-of-work) and proof-of-storage both the network and the client 14 simultaneously benet. The network rewards the storage miners by printing inationary rewards (similar to mining rewards for Bitcoin proofs-of-work miners), thereby subsidizing the cost of le storage. Notice how this application of PoReps as a \useful" proof-of-storage to mine Filecoin and subsidize storage costs is extremely sensitive to the security property of PoReps. Consider a PoRep such as the naive combination of PoS and PoR, which does not satisfyreplication (for < 1). A miner would actually double its prots in Filecoin mining rewards by deduplicating storage because it could now use the extra storage space to generate twice as many proofs of storage. Morever, miners could double their Filecoin rewards by producing PoReps for useless les that the prover generates from a small seed instead of storing real client data (called the \generation attack" in [2]. This means that Filecoin miners will charge even more to use their space to store user les, raising rather than subsidizing the cost of storage. More generally, if the PoReps do not have data-independent costs then the Filecoin mining rewards could have adverse eects on storage costs, driving miners to increase the cost of some les while lowering the cost of others.

¹³ It satises Mirror’s denition of-binding as long as the PoS has at most a 1 space gap.

¹⁴ Decentralized transactional networks that follow the Nakamoto paradigm for consensus, i.e. proof-of-work blockchains, require consensus nodes to produce some form of \proof-of-resource" to ensure Sybil resistance. Depending on its instantiation, this proof-of-resource may also contribute global costs to transacting by adding an expense to transaction processing. Often these systems reduce the local impact of this cost on transaction fees by printing an inationary reward that goes directly to the consensus node processing the transaction (although the ination silently taxes the economy). This has the eect of subsidizing the cost of transacting, the same way that governments may use ination to subsidize food or economic activity to stimulate an increase in GDP. It has been observed that the inationary reward is more than just a subsidy mechanism, as it is actually critical to the

3 Constructions

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 also assume there is an external verication procedure that the verier D may query on any block d of the le D~, its position i, and, which returns a result that we i D denote by O_check(d_i;i;_D)! b 2f0*;* 1g.

$$ \tilde{D} $$

$$ \tau_{D} $$

$$ i, $$

$$ \tilde{D} $$

$$ d_{i} $$

$$ \tau_{D} $$

$$ \mathcal{O}{\mathsf{c h e c k}}(d{i},i,\tau_{D})\to b\in{,11}right! $$

Building blocks All constructions use a VDE scheme fVDE.Setup*;VDE.Enc;VDE.Decg* with m identical input space and code space over f0*;* 1g for so^me m = O() determined by the VDE m setup, as well as a hash function H : f0*;* 1g!f0*;* 1g ^modeled as a random oracle (i.e. mapping strings of arbitrary length to strings of length m).

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

$$ m=O(\lambda) $$

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

The construction DRG-PoRep uses DRG.Sample(n;d), which outputs an (n;n;d) depth robust graph with probability 1 negl(n) for d = O(logn). In the Section?? we discuss instantiations of DRG.Sample and how d can be chosen to target dierent values of the constants 0 < < < 1 (both analytically and empirically given our implementation of the best known attacks). In particular, in DRG-PoRep the value of must be very small, as this will determine the-rational security of the scheme (in fact =).

$$ {\mathsf e{}}(n,d) $$

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

$$ 1\mathrm{-}\mathsf{n e g}(n) $$

$$ d,=,{\cal O}(\log n) $$

$$ 0<\beta<\alpha<1 $$

$$ \alpha $$

$$ \epsilon=\alpha) $$

The latter two constructions also use a vector commitment scheme with algorithms VC.Setup, VC.Com, VC.Open, and VC.Verify.

Security parameters Each PoRep scheme will take two security parameters*;* as input. The parameter determines the overall security level of the construction (e.g. 80-bit, 128-bit, 256-bit), whereas the parameters determines the soundness of the \online" proofs generated by PoReP.Prove. Since these are run repeatedly in a challenge-response protocol, we leave open the possibility that certain applications may target a non-negligible online soundness error such as 1*=1;000, 1=100 or even 1=*3. Each challenge-response proof will be subject to this soundness bound independently thus security is amplied against a prover that tries to cheat many times. We will discuss how concrete choices for each of the schemes impact security/eciency.

$$ \lambda,\kappa $$

$$ \lambda $$

$$ 1/3. $$

3.1 Basic PoRep from Veriable Delay Encodings

A very basic PoRep construction is simply to use the VDE scheme to derive a unique replica R_idas a slow encoding of the le F on a given id. This scheme was already sketched in [14], which generalized a scheme originally proposed by Sergio Demian Lerner [33], although neither works provided a formal security analysis. During the challenge-response period, the verier periodically checks that the server has been persistently storing the encoding R_idby challenging the server for R_iditself. If the delay parameter of the VDE scheme is set appropriately relative to the verier’s polling period, then a prover that has deleted the replica R_idat any point during the polling period will not be able to re-derive the encoding in time to respond to the verier’s challenge. We also need to ensure that the replicas on two dierent ids are independent, and cannot be derived from one another more quickly than deriving each from scratch. The

$$ R_{i d} $$

$$ R_{i d} $$

$$ R_{i d} $$

$$ R_{i d} $$

security of Nakamoto consensus [39]

relevant security property of a VDE scheme is that on any independent random challenge it is sequentially hard to compute, even given a polynomial number of prior encodings of other points. We can enforce the independence of inputs by using a random oracle¹⁵ H applied to the replica id. Specically, instead of encoding F directly, we encode F H(id). Recovery of F is still possible as id is known to the decoder. Technically, as F may consist of multiple blocks of length m we will encode each ith block individually XORed with H(ijjid). The verier only needs to challenge for a randomly sampled constant number of the encoded blocks (and check them individually) in order to ensure that no more than an fraction have been deleted.

$$ F\oplus H(i d) $$

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

Lerner’s initial proposal of this protocol used a Pohlig-Hellman cipher as a weak instantiation of the VDE and also focussed on the special use-case of proving unique storage of a copy of a xed le known to all the veriers (it was proposed as a way to prove unique storage of a copy of a blockchain). In our case, we need to adapt the protocol to handle data les specied only by their commitment tag_Dthat may be initially unknown to the verier. The PoRep needs to still be a PoS in this case. Fundamentally, for this to be secure the slow replica encoding must depend on this tag. Otherwise, the prover can rst set the PoRep replica to any arbitrary value and then run the data extraction algorithm on a particular id to nd data consistent with this replica. This requires only a simple modication which is to use both id and_Das input to the random oracle H.

$$ \tau_{D} $$

$$ \tau{boldsymbol}D
$$

3.1.1 Basic-VDE-PoRep

PoRep.Setup(;T)! pp Set = 2T and run VDE.Setup(;)! pp_vde. This species the block length m, and provides implicit input parameters to VDE.Enc and VDE.Dec. Lastly the setup species an integer ‘ = ‘() of size O().

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

$$ \Delta=2T $$

$$ \mathsf{V D E.S e t u p}(\Delta,\lambda)\to p p_{\mathsf{v a e}} $$

$$ m. $$

$$ \ell=\ell(\lambda) $$

$$ O(\lambda) $$

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

$$ (i d,\tau_{D},\check{D})\rightarrow R,a u x $$

$$ \tilde{D} $$

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

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

$$ R_{i}\ \mathrm{{=}}\ \mathsf{V D E.E n c}(d_{i}\oplus H(\mathit{}i i d||\tau_{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) D N _i i H(idjj jji). Output D~ = (d₁;:::;d). D _N

$$ \mathfrak{L}(i d,\tau_{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||\tau_{D}||i) $$

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

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

$$ ,\mathbf{P o l l}(N)\to r $$

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

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

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

$$ :(R,N,i d,r)\to\pi $$

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

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

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

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

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

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

$$ i=1 $$

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

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

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

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

$$ \cdot\boldsymbol{b}{i}\gets\mathcal{O}{\mathsf{c h e c k}}(\dot{d}{i},r{i},\tau_{D}) $$

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

$$ b_{i}=1 $$

¹⁵ The random oracle can be replaced with a collision-resistant hash function if only a pebbling adversary is considered in the security analysis.

VDE instantiation We can instantiate the basic PoRep construction with the Sloth [32] VDE. With a block size of m = 4096 and time delay T of 10 minutes the Sloth decode takes approximately 0*:* 15 seconds. For the same target delay with m = 512 decoding takes approximately 3 seconds. These were measured on a 2.3 GHz Intel Core i7.

$$ m=4096 $$

$$ m=512 $$

Replication time 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) takes approximately 1 hour on 16 parallel cores. With block size m = 256 we can only support les up to 320 bytes for replication 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 $$

$$ \kappa, $$

Proof size The proof size is a constant ‘m bits independent of the le size. To ensure (with soundness error) that no more than an fraction of the blocks have been deleted the number of queries ‘ should be set to ‘ = log( )*=log(1). For example to detect deletion of 1% of the data blocks with soundness error 1=*3 we would require ‘ 100, in which case the proof might as well include the entire replica for N < 100. To detect deletion of 5% with soundness 1=3 only requires ‘ 20. For 80% we can set ‘ 5.

$$ \ell=\log(\delta)/\log(1-\epsilon) $$

$$ \ell\approx100 $$

$$ N<100 $$

$$ \ell\approx20 $$

$$ \ell\approx5 $$

Correctness and Security Correctness is immediate from the construction and correctness of the underlying primitives. The construction’s rational security is optimally tight, i.e. it satises-sound-rational-replication for any arbitrary < 1 and = negl(). We provide the formal analysis in Section4(Theorem1). The construction is also therefore a tight¹⁶ (Lemma1).

$$ \mu={\mathsf{n e g l}}(\lambda) $$

Erasure code preprocessing In combination with an optimal rate 1 erasure code during preprocessing then it becomes perfectly rational for the prover to store a recoverable encoding of the le because even if it deletes an fraction of the blocks it will still be perfectly recoverable. Likewise, if the prover generates k independent replicas of a le D then because it uses (1)kN space overall it can store N blocks of each replica so that D is still recoverable from each. Increasing the tolerance of the erasure codes results in an increase in replica size, but may justify reducing the tightness of the PoS/rational-replication security (i.e. reduce). For example, on N = 100 blocks, setting = 0*:* 01 and using an erasure code that recovers from 1% deletion results in only a 1% increase in le size but reducing a proof that is equal in size to the original le. On the other hand if = 0*:* 20 and D is preprocessed with an erasure code that tolerates 20% deletion, then we trade an increase in the replica size by 20% for a proof size of only 6% of the original le size.

$$ \epsilon=0.20 $$

3.2 Block Chaining Encodings

The Basic-VDE-PoRep is impractical 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

¹⁶ Although the VDE based PoRep is a concretely tight proof of space with practical proof sizes, unlike other proofs of space in the literature it does not have an ecient execution time, which scales quadratically as O(NT) = O(N²) where T is the time delay parameter.

$$ O(N^{2}) $$

$$ O(N T)= $$

$$ {\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} $$

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

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

$$ D_{1} $$

Figure 3.2: Basic-VDE-PoRep in CBC-mode (insecure).

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 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 take time TN. In fact, the prover can re-derive the specic challenged blocks in total time ‘T (or parallel time T with only ‘ parallelism).

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-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 Figure3.2. 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.

$$ R_{i} $$

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

$$ d_{i)} $$

$$ d_{i+1}) $$

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

$$ R_{i} $$

$$ 3.2 $$

$$ 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}) $$

$$ T\cdot N $$

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

Figure 3.3: 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)) $$

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.

$$ k I $$

Dependency graphs The issue with the simple cipher block chaining method is that the dependency graph of the block encodings is not depth robust (see SectionA.6). 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. 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). More generally we can consider the parallel pebbling complexity of the dependency graph (SectionA.8).

$$ (\alpha,\beta) $$

$$ \beta N $$

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

$$ k<N $$

3.3 DRG PoRep

The construction DRG-PoRep [26] extends the Basic-VDE-PoRep by chaining block dependencies using a depth robust chaining as described above. As a PoS, it can be viewed as the generic PoS from the graph labeling game (SectionA.8) on a depth robust graph, where the random oracle queries are combined with VDE queries to introduce more asymmetry between initializing the PoS and extracting data from it. 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. The security can be amplied using stronger DRGs

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

$$ 1/\beta $$ for smaller > 0, at the cost of increasing the degree by O(1*=*) as well as the replication time relative to polling period.

$$ O(1/\alpha) $$

$$ \alpha>0 $$

As in the generic PoS from labeling games, the protocol separates out 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. Unlike in the Basic-VDE-PoRep where the verier can completely verify the correctness of a block using VDE.Dec, here the verier cannot check that all the correct dependencies were enforced as this would not be a compact proof. Here, the prover will rst derive the entire encoding (consisting of labels on each node of the graph) and provide the verier with a compact vector commitment to these labels. The verier will query for several randomly sampled nodes of the graph and challenge 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, the (suciently large) subgraph of correct nodes is also depth robust. Put another way, the small fraction of incorrect labels do not help the adversary any more than putting several additional initial pebbles on the graph \for free". The proof is made non-interactive using the Fiat-Shamir heuristic.

$$ (\alpha,\beta) $$

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.3.1 DRG-PoRep

PoRep.Setup(;;T)! pp: The setup obtains as input security parameters*;, as well as the delay parameter T, sets = 2T=(N 1) to be the VDE delay parameter and runs m pp_vdeVDE.Setup(;). This determines a block size m and 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;‘₁;‘₂).

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

$$ \lambda,\kappa, $$

$$ T cdot $$

$$ \Delta,=,2T/(\beta N,-1) $$

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

$$ m $$

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

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

$$ N_{m a x} $$

$$ \mathrm{\ l e n g t h^{17}} $$

$$ \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

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

$$ \tilde{D} $$

$$ m $$

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

1.Apply random oracle H(idjj_D) =. Implicitly denes a graph G DRG.Sample(N;), however the prover does not need to run this function explicitly as it will use the parent function instead.

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

$$ \sigma $$

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

~ as data blocks (m 2.Parse D d₁;:::;d^N), each dⁱ2f0*;* 1g. We dene the following subroutine DRGEnc that operates on d;m;N; ~ and and outputs the replica R.

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

$$ \tilde{D} $$

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

$$ d,m,N $$

$$ \sigma $$

¹⁷ Some vector commitments, such as a Merkle commitment, do not require speciying the data length in the setup. In this case Nmax = 1.

$$ N_{m a x}=\infty $$

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

$$ 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 vector commitment com_R;_RVC.Com(pp_vc;R).

$$ \mathsf{s}{R},\tau{R}\gets\mathsf{V C.C o n}(p p_{\mathsf{v c}},R) $$

4.Now use H to derive the (non-interactive) a challenge vector = (¹;:::;^‘1) by comnodes putingⁱ= H( jjcom_Rjji). Set C = (c₁;:::;c). For each i set parents(_i) ‘1 parents DRG.Parents(N;;_i) and set C (_i) = (c_v1;:::;c_v) where fv₁;:::;v_dg = parents(_i). d

$$ \boldsymbol{\rho},=,(\rho_{1},...,\rho_{\ell_{1}}) $$

$$ C^{\mathsf{n o d e s}},=,\big(c_{\rho_{1}},...,c_{\rho_{\ell_{1}}}\big) $$

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

$$ {\mathfrak{i}}(\rho_{i})\leftarrow, $$

$$ (N,\sigma,\rho_{i}) $$

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

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

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

$$ \Lambda\leftarrow\mathsf{V C.O p e n}(p p_{\mathsf{v c}},\mathcal{C}^{\mathsf{n o d e s}},\rho,\tau_{R}) $$

for i = 1 to ‘₁:

$$ \Lambda_{i}\xleftarrow{}\mathsf{V C.O p e n}(p p_{\mathsf{v c}},C^{\mathsf{p a r e n t s}}(\rho_{i}),\ \ {mathsf\ p}a r e n t s(\rho_{i}),\tau_{R}) $$

$$ \ell_{1} $$

nodes parents parents 6.Output R and aux = com_R;;;C;C (₁);:::;C (_‘1);;₁;:::;_‘1.

$$ \mathrm {a u x} = c o m _ {R}, \sigma , \rho , C ^ {\mathrm {n o d e s}}, C ^ {\mathrm {p a r e n t s}} \left(\rho_ {1}\right),..., C ^ {\mathrm {p a r e n t s}} \left(\rho_ {\ell_ {1}}\right), \Lambda , \Lambda_ {1},...,\Lambda_ {\ell_ {1}}. $$

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

$$ \ {\mathfrak{s.}l\ {{\sf P o l l}}}(N)\to r{\mathrm{:}} $$

$$ \ell_{2} $$

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

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

PoRep.Prove(R;aux;id;r)! : The input is the replica R = (c₁;:::;c_N), id, aux output of replicate (which includes com^R), a challenge vector ~r = (r₁;:::;r^‘2). Derive = H(idjj^D). Set parents ~c = (c_r1;:::;c_r). For each r_ialso derive parents(r_i) DRG.Parents(N;;r_i), set C (r_i) to ‘2 be the concatenation of c_jfor all j 2 parents(r_i) (ordered by increasing indices), and compute parentsk k_ri= H( jjC (r_i);i). Set = (k_r1;:::;k_r). _‘2 Compute VC.Open(pp;com;c;r;). Output = (;c; ~k).

$$ :R,a u x,i d,r)\to\pi; $$

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

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

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

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

$$ r_{i} $$

$$ \mathsf{d e r i v e\ p a r e n t s}(r_{i})\leftarrow\mathsf{D R G.P a r e n t s}(N,\sigma,r_{i}) $$

$$ C^{\mathsf{p a r e n t s}}(r_{i}) $$

$$ c_{j} $$

$$ j\in\mathsf{p a r e n t s}(r_{i}) $$

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

$$ \vec{k}=(k_{r_{1}},...,k_{r_{\ell_{0}}}) $$

$$ \mathbf{C o m p u t e}\ \Lambda\leftarrow\mathsf{V C.O e n e}(p p_{\mathsf{v e}},,o m m_{R},\vec{c},\vec{r},\tau_{\mathcal{H}}).\ \ {mathbf{O u t p u t}}\ \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).

$$ \mathcal{V e r i f y}(i d,\tau_{D},r,a u x,\pi)\rightarrow b $$

$$ _{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}}),;\Lambda,;\Lambda_{1},...,\Lambda_{\ell_{1}} $$

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

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

18 1.First verify aux. Check H(idjj_D) = and H( jjcom_Rjji) =_ifor each i = 1 to ‘₁. If any checks fail output 0 and terminate. Next derive parents(_i) DRG.Parents(N;;_i). Run the following verications on the vector commitment openings ;₁;:::;_‘1:

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

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

$$ i=1 $$

$$ \ell_{1} $$

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

$$ b_{0}\gets\mathsf{V C.V e r i f y}(p p_{\mathsf{v c}},\mathcal{C}^{\mathsf{n o d e s}},\rho,\Lambda) $$

$$ \Lambda,\Lambda_{1},...,\Lambda_{\ell_{1}}. $$

for i = 1 to ‘₁:

$$ i=1 $$

$$ \ell_{1} $$

$$ b_{i}\xleftarrow{}\mathsf{V C.V e r i f y}(p p_{\mathsf{v c}},C^{\mathbf{p a r e n t s}}(\rho_{i}),\mathtt{p a r e n t s}(\rho_{i}),\Lambda_{i}) $$

$$ \wedge,b_{1}\wedge\cdots\wedge b_{\ell_{1}}=0 $$

If b₀ ^ b₁ ^^ b_‘1= 0 then output 0 and terminate.

¹⁸ 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.

nodes Finally for each c_i2 C the key k_i= H( jjc_v1jjjjc_v) where fv₁;:::;v_dg = parents(_i) d and compute d_iVDE.Dec(pp_vde;k_ic_i) and query the check oracle b O_check(d_i;_i;_D). If b = 0 output 0 and terminate.

$$ c_{\rho_{i}}\in C^{\mathsf{n o d e s}} $$

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

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

$$ d_{i}\leftarrow\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}}(d{i},\rho_{i},\tau_{D}) $$

$$ b=0 $$

2.Second verify the \online" proof. First compute b VC.Verify(pp_vc;c;r;_ret). Next 0i for each i 2 [‘²] compute dⁱVDE.Dec(pp_vde;k_ic_ri) and query the oracle b 0‘ O_check(d_i;r_i;_D). Output b ^ b⁰₁^^ b. ₂

$$ \pi $$

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

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

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

$$ b_{i}^{\prime}\leftarrow $$

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

$$ b\wedge b_{1}^{\prime}\wedge\cdots\wedge b_{\ell_{2}}^{\prime} $$

Replication and extraction time The main achievement of the DRG PoRep construction is its scalable replication time, which is now a xed multiple of the polling period (dependent only on*;) and in particular is independent of the number of blocks in the le. The extraction time is also optimal, as any block can be locally decoded by applying the hash function H to d = O(logn*) labels and making a single call to VDE.Dec, which should take under 1 second.

$$ \alpha,\beta) $$

$$ d=O(\log n) $$

Batched vector commitment openings In the construction description above we listed the nodes parents vector commitment openings , ₁,...,_‘1for C and all C (_‘i) separately inside the parameter aux, and they were veried separately as well. This was done mostly for clarify of presentation. This would be necessary if the vector commitments are instantiated with Merkle commitments. However, one of the major advantages of using vector commitments with batchable openings is that these can all be compressed to a single constant size opening. In this case nodes parents aux only includes the labels C and all C (_‘i) for each i along with a single opening proof .

$$ \Lambda,:\Lambda_{1},...,\Lambda_{\ell_{1}} $$

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

$$ C^{\mathsf{p a r e n t s}}(\rho_{\ell_{i}}) $$

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

$$ C^{\mathsf{p a r e n t s}}(\rho_{\ell_{i}}) $$

Vector commitment storage 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 levels of the k k tree to save a factor 2 space and re-derive all hashes along a Merkle path by reading at most 2 ^k nodes and computing at most 2 hashes. If k = 7 this is less than a 1% overhead in space, and k requires at most 128 additional hashes and reads. Furthermore, as remarked in [45] these 2 reads are sequential memory reads, which in practice are inexpensive compared to the random reads for challenge labels.

$$ 2^{k} $$

$$ 2^{k} $$

$$ 2^{k} $$

$$ k=7 $$

$$ 2^{k} $$

Relaxing soundness: interaction and time/space tradeos The size of ‘₁is a signicant factor in blowing up the size of aux. 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 ignores the fact that the prover will need to rerun replication many times in expectation. As this is already a memory/sequentially hard computation (taking at least around 10-60 min), we can relax the security model to assume there is some bound on the initial computation that the malicious prover is willing to do in order to save a fraction of space during the online phase. If we can just achieve soundness 1*=*1000 80 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} $$

$$ \ell_{1} $$

$$ 2^{-80} $$

$$ \ell_{1}\approx100 $$

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, which amortizes the cost). The proof size in aux is ‘₁(d+ 1)m + L(N;m;‘₁(d+ 1)) where L(N;m;‘₁(d+ 1)) is the size of the vector commitment opening proof on a vector of length N of elements of size m. As aux is non-interactive the soundness error needs to be exponentially small, therefore we set ‘₁= = log(1). For example with = 80 and = 0*:* 20 this is ‘₁= 825. However, as described above, in practice we could set ‘₁= 100 if we are willing to assume a malicious prover will not nd it rational to work for 4 days to save a fraction of the space. With d = 5 and m = 128 the total proof size is approximately 10 KB, independent of the data input size. Note that the data input size could range up to gigabytes or terabytes.

$$ \ell_{1}(d!+!1)m!+!L(N,m,\ell_{1}(d!+!1)) $$

$$ L(N,m,\ell_{1}(d+)) $$

$$ \lambda=80 $$

$$ \ell_{1}=\lambda/-l o g(1-\alpha) $$

$$ \ell_{1}=825 $$

$$ \ell_{1}=100 $$

Compressing proofs with SNARGs We can further compress the size of the aux proof by using SNARGs, or any other form of succinct proofs. To maximally compress the proof size, the prover can compute 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 and slow encodings that minimize the multiplicative complexity of checking inclusion proofs and decoding. If the main cost in the proof size comes from the degree d of the DRGs (see Section ??), then we can already substantially decrease the proof size by using SNARGs only to eliminate the parent nodes of each c_i. In this case, the SNARG would only prove knowledge of d encodings c₁;:::;c_d, their valid inclusion proofs in com_Rat the appropriate positions, and that k_i= H(c₁;:::;c_d). We can also replace the hash function H with a suitable key-derivation function (KDF) that minimizes multiplicative complexity. Since the proof of security holds in the random oracle model, it is important that the KDF should retain properties similar to a random oracle. At a minimum it needs to be collision-resistant.

$$ \pi $$

$$ c_{i} $$

$$ c_{1},...,c_{d}; $$

$$ k_{i}=H(c_{1},...,c_{d}) $$

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++ [14] 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_p described in [14], which is a nominal added cost in combination with the Merkle inclusion proof. 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 30 some parallelism. The total circuit size for verifying aux with 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 [12]. With modest parallelism (e.g. 16 threads) this can easily be reduced to below the raw replication time.

$$ \beta=1/100 $$

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

$$ \ell_{1}=100 $$

$$ m=256,,N=2^{30},,d=20 $$

Towards both tight and ecient PoReps The DRG-PoRep construction improved significantly on replication time while maintaining terric extraction eciency. However, it com-

¹⁹ https://z.cash/technology/jubjub.html promised 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 it does not really achieve arbitrarily small-rational security in the same sense as Basic-PoRep. Furthermore, by increasing dependencies between blocks, erasure code preprocessing is no longer guaranteed to recover the le from arbitrary deletion of an fraction of the blocks (only the N topologically last blocks).

$$ O(1/\epsilon) $$

Pietrzak [45] 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 [6] 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 0 on the last n nodes. Pietrzak shows that a prover who deletes an fraction of the labels on the last n nodes will not be able to re-derive them in fewer than n sequential steps. The value 0 ⁰ can be made arbitrarily small however < =4, so the degree of the graph must increase as ⁰ 1*=*. Furthermore, although the graphs in [6] achieve asymptotic eciency and are incredibly intriguing from a theoretical perspective, they still do not have concretely practical degrees (their asymptotic degree starts to kick in on graphs with over a billion nodes).

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

$$ (\alpha,\beta) $$

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

$$ \epsilon^{\prime} $$

$$ \epsilon^{\prime} $$

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

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

Pietrzak’s construction did not incorporate delay encodings into the DRG PoRep construction and this could easily be added just as in DRG-PoRep. 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. Hence the main advantage of the VDEs is in lowering the gap between extraction/replication on graphs of smaller size. However, since Pietrzak’s construction only embeds the data on the last level the data extraction is already as inecient as data replication (the labels on the rst 3n labels needs to be re-derived before the data can be extracted), hence the VDEs will not help as much.

4 Formal security analysis

This section applies the framework and denitions of Section2to formally analyze the security of the two constructions Basic-VDE-PoRep and DRG-PoRep. The focus of our analysis is on proving-rational-security. In fact, Lemma2established suciency conditions that greatly simplify proving-rational security. Both constructions are each a-PoRC of the replica R and data D almost by construction (and PRAM strongly sound as proven in Lemma3), and the main work left is show that each is a parallel sound proof of space. Both of the constructions can be viewed as PoS variants of the generic graph labeling PoS (with a tweak for incorporating VDEs). Furthermore, due to Pietrzak’s recent result [45], we can contain our analysis to parallel pebbling games, which translates to unconditional security in the random oracle model with some small loss (Theorem4). (Before this result graph labeling PoS constructions were still analyzed via pebbling games and the correspondence was taken for granted). There is a small catch in relying on this correspondence in our setting, however, which is that Pietrzak’s analysis applied to pure random oracle labeling games and did not involve VDEs.

4.1 Labeling games with VDEs

Pebbling game model Pebbling games appropriately model labeling games with collision resistant one-way hash functions informally because of the property that labels on distinct nodes do not repeat with any signicant probability and computing new labels cannot be predicted without knowing all the inputs to the labeling function, i.e. all the dependency labels. The independence of labels even holds when there are no dependency edges by incorporating the unique index of the node as the rst input. In the labeling games with VDEs that we consider, a collision resistant hash function (or random oracle) is used to rst derive a key from all the dependencies of a node. The key is then XORed with a (non-unique) data input, and the result is passed to a VDE to derive the node’s label. Conditioned on xed data inputs, these \key labels" are uniquely determined, and are derived as the output of collision resistant hash functions just as in usual labeling games.

The important distinction, however, is that the call to the VDE is much more expensive than the call to the hash function to derive the key. The cost of \placing a pebble" is dominated by the VDE time delay. The sequentiality security property of a VDE (Denition19) says that evaluating the VDE on a point will be hard on a random input, even given an arbitrary polynomially sized table of evaluations on other points. If the hash function used to derive the key labels is modeled as random oracle then the input to each VDE call is an independent uniform random point.

As we are focussed on a parallel adversary, we may assume for the purpose of our analysis that the adversary always calls the VDE to derive the label whenever a key and input is available. In fact, for the purpose of analyzing PoS security of PoRep constructions we may assume that the data inputs are (they are assumed to be available externally in the worst case). This way the underlying pebbling game is largely unchanged, and we can model the VDE and random oracle queries as a single pebbling move that can be made only when there are labels on all the dependencies.

Committed data inputs As we already noted, it is crucial that the auxiliary data inputs are committed (or publicly known) and that the labeling is uniquely dependent on this commitment. Otherwise, the prover can place any arbitrary labels on the nodes and use the VDE decode algorithm to nd corresponding data inputs consistent with these labels and the key derived from labels on all neighboring nodes. This allows the prover to circumvent the labeling dependencies of the underlying graph or even the cost of evaluating the VDE. The issue is resolved by using the data commitment_Dof all data inputs to sample the random oracle H. Intuitively, the pebbling game is still an accurate security model because the adversary must \know" D before labeling the graph using H.

$$ H_{\sigma} $$

$$ \tau_{D} $$

$$ H_{\sigma} $$

Parallel pebbling vs labeling Intuitively, any labeling strategy starting from an initial advice string that simply stores a set of graph labels then this directly translates to a pebbling strategy in the corresponding pebbling game and thus inherits the security of the pebbling game. Moreover, when the labels themselves encode entries in a random oracle’s function table they are incompressible (Fact2). However, the labeling adversary’s initial advice (equiv. the PoS adversary’s persistent storage) need not encode these labels explicitly.

Pietrzak’s unconditional proof of this equivalence in the random oracle model rst demonstrates how to translate a certain set F called \fresh" queries (roughly those queries that contain any label which has not yet been received as an output of another query) made by a successful labeling strategy into a successful parallel pebbling strategy that uses jF j initial pebbles. Hence, if the pebbling game is hard without (n) initial pebbles then jF j = (n). Intuitively, the labeling adverary’s initial advice s must somehow encode F, and therefore should have at least the same size as F is incompressible (Fact2). The next step of the proof demonstrates this formally by showing how to construct an encoding scheme that uses the adversary as a black box to encode these jF j entries in the random oracle’s function table using just jsj bits.

$$ \Omega(n) $$

$$ |F|=\Omega(n) $$

$$ \approx|s s| $$

It is not immediately clear that this equivalence still holds when comparing the parallel pebbling game with the VDE cost function to the parallel hardness of the VDE labeling game. Pietrzak proved the equivalence still holds when the auxiliary data inputs are simply XORed with the random oracle \key" outputs, and assuming the commitment_Dis extractable (e.g., a commitment that uses the random oracle itself, such as a Merkle commitment, is extractable in the random oracle model). In this case the encoding scheme in the proof works roughly the same way but rst extracts the data inputs from the adversary and uses the data to recover the incompressible \keys". In the constructions we analyze in this paper the \keys" are similarly XORed with the data inputs before they are passed to the VDE. Moreover, the VDE is invertible so the the key labels are still extractable from the output given the data.

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

However, the security of the construction relies on the cost of querying the VDE, which is signicantly greater than querying the random oracle. One way to address this is to use the IDP oracle (Denition20) to model queries to the VDE separately from queries to the random oracle, and then adapt the analysis of [45] to show that an adversary who wins the labeling storing too little advice either can compress the random permutation table of VDE.Enc or the random function table of H. This analysis is beyond the scope of the current document.

$$ H_{\sigma} $$

4.2 Security claims

For the following claims we assume that O_checkis perfectly binding on pairs (_D;D) such that each_Dis a position binding vector commitment to D, i.e. for each_Dand i there exists a unique D_isuch that O_check(_D;i;D; aux) = 1 for some aux.

$$ \mathcal{O}_{\mathrm{c h e c k}} $$

$$ (\tau_{D},D) $$

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

$$ D, $$

$$ \tau_{D} $$

$$ D_{i} $$

$$ \mathcal{O}{\mathrm{c h e c k}}(\tau{D},i,D,\mathsf{a u x})=1 $$

‘() Claim 1. Basic-VDE-PoRep is (PRAM strongly)-sound (1)-PoRC for any > (1) + negl⁽⁾ and with constant additive extractor blowup.

$$ \mu>(1!-!\delta)^{\ell(\lambda)}+ $$

$$ n e g/(\lambda) $$

Proof. The implicit PoRC protocol of Basic-VDE-PoRep is just an instantiation of PoRC from vector commitments SectionA.4.2. The vector commitment is (_D;N) and the opening advice is (R;id). Each R_i= VDE.Enc(d_iH(idjj_Djji) where H is a collision hash function and each output of VDE.Enc is uniquely decodable. VC.Open on_D, an index i 2 [N], block d_i, and the opening advice R_icomputes VDE.Dec(R_i) H(idjj_Djji) = d_iand then veries O_check(_D;i;D; aux) = 1. This satises position binding by the assumption that O_checkis position binding. Moreover, since R_iis uniquely determined from d_iby the properties of VDE and collision resistance of H the commitment to d_iis also position binding to R_i. In the PoRC protocol each challenge in the challenge vector species an index i for the ith pair (R_i;d_i), and the proof value R_iis an opening of this pair. Therefore the claim follows from Theorem3.

$$ (\tau_{D},N) $$

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

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

$$ i\in[N] $$

$$ R_{i} $$

$$ d_{i} $$

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

$$ \mathcal{O}{\mathrm{c h e c k}}(\tau{D},i,D,\mathsf{a u x})=1 $$

$$ \mathcal{O}_{\mathrm{c h e c k}} $$

$$ R_{i} $$

$$ d_{i} $$

$$ d_{i} $$

$$ R_{i} $$

$$ (R_{i},d_{i}) $$

$$ R_{i} $$

Claim 2. The composition of k instances of Basic-VDE-PoRep on distinct ids id₁;:::;id_kis a ‘() parallel ((1 +)kN;2T; ⁽1 +⁾)-sound PoS for any 1 > > > 0*.*

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

$$ ((1-\epsilon+\delta)k N,2T,(1-\epsilon+\delta)^{\ell(\lambda)}) $$

$$ 1>\epsilon>\delta>0 $$

Proof. The implicit PoS in a single instance of Basic-VDE-PoRep is a graph labeling PoS on a disconnected graph on N, with V_C= [N], and Chal the uniform distribution over [N]. The cost of placing a single pebble is T, i.e. c(N) = = 2T, i.e. when the VDE delay is set to 2T. The random black pebbling game on a disconnected graph on N nodes with V_C= [N] is (; 1*;*)-parallel-hard for any because the challenge node is unpebbled with probability at least 1 and it requires 1 move/round to pebble an unpebbled challenge node. Since there are no edge dependencies the adversary cannot place any red pebbles, i.e. = 0. Therefore, k Claim8can actually be strengthened in this case to say the PoS is parallel (N;T;)-sound. k Composition follows from Claim9. Setting = 1 + gives = (1 +).

$$ V_{C}=[N] $$

$$ T $$

$$ \Delta $$

$$ c(N)=\Delta=2T $$

$$ V_{C}=[N] $$

$$ \gamma $$

$$ (\gamma,1,\gamma) $$

$$ 1-\gamma $$

$$ \delta=0 $$

$$ (\gamma N,T,\gamma^{k}) $$

$$ \gamma=1-\epsilon+\delta $$

$$ \mu=(1-\epsilon+\delta)^{k} $$

Theorem 1. Basic-VDE-PoRep with VDE delay parameter = 2T is e-sound-rational secure when ‘() = 2*=.*

$$ \Delta:=:2T $$

$$ e^{-\lambda} $$

$$ \ell(\lambda)=2\lambda/\epsilon $$

Proof. Claim1proves condition (b) of Lemma2with extractor blowup factor c 1 and Claim2 proves condition (c) of Lemma2. Together with the correctness of the construction for an honest prover, these claims therefore establish that Basic-VDE-PoRep is-sound-rational secure for ‘ ‘ any > max((1);(1 +)) and any < . The maximum value of is at = =2, where ‘ 2 ‘ 2= = (1 =2). If ‘ = then (1) = (1) < e. ₂ 2

$$ c\approx1 $$

$$ \mu>m a x((1!-!\delta)^{\ell},(1!-!\epsilon+!\delta^{\ell})) $$

$$ \delta<\epsilon. $$

$$ \delta=\epsilon/2 $$

$$ \mu $$

$$ \mu=(1-\epsilon/2)^{\ell} $$

$$ \ell=\frac{2\lambda}{\epsilon} $$

$$ \big(1-\frac{\epsilon}{2}\big)^{\ell}=\big(1-\frac{\epsilon}{2}\big)^{2\lambda/\epsilon}<e^{-\lambda} $$

‘2() Claim 3. DRG-PoRep is a (PRAM strongly)-sound (1)-PoRC for any > (1) + negl⁽⁾ with constant additive PRAM extractor blowup.

$$ \mu>(1-\delta)^{\ell_{2}(\kappa)}+ $$

$$ n e g/(\lambda) $$

Proof. We similarly claim that the implicit PoRC protocol of DRG-PoRep is a PoRC from vector commitments with the security parameter ‘₂() determining the number of challenges. Here the vector commitment explicitly uses a vector commitment scheme VC as an abstract primitive. The commitment is (_D;com_R;N) where com_Ris a vector commitment to the replica R consisting of labels on the DRG nodes. The opening advice for an index i is the label R_i= c_ion the ith node along with the key k_iderived from the parent labels. The opening value d_iis then computed as VDE.Dec(c_ik_i) = d_iand the opening to d_iis then checked by querying the oracle on O_check(_d;i;D; aux). Additionally the opening value R_iis veried against com_Rusing the VC functionality. Correctness is immediate and binding follows from the assumption that O_checkis position binding and the security properties of VC (i.e. it is also position binding). The opening advice is contained in the \online proof" _ret. Note that PoRep.Verify also runs a verication procedure on aux (this is important for the PoS property), however this is not necessary for the PoRC verication and can be ignored for the purpose of showing that this is a PoRC. Finally the claim follows from Theorem3.

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

$$ (\tau_{D},c o m_{R},N) $$

$$ R_{i}=c_{i} $$

$$ d_{i} $$

$$ k_{i} $$

$$ \left(c_{i}\oplus k_{i}\right)=d_{i} $$

$$ d_{i} $$

$$ \ {{\mathsf{c h e c k}}}(\tau{d},i,D,\mathsf{a u x}) $$

$$ R_{i} $$

$$ '! $$

$$ \mathcal{O}_{\mathrm{c h e c k}} $$

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

Claim 4. The composition of k instances of DRG-PoRep on distinct ids id₁;:::;id_kis a parallel ‘1() ‘2() ((1 +)kN;2T;)-sound PoS for = maxf⁽1⁾;(¹ + + ^{2 )} g for any > 0 when the graph used is an (N;;) DRG and the delay parameter is = 2 T=(N 1).

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

$$ \left((1-\epsilon+\delta)k N,2T,\mu\right) $$

$$ \mu=m a x{(1-\delta)^{\ell_{1}(\lambda)},(1-\epsilon+\alpha+2\delta)^{\ell_{2}(\lambda)}} $$

$$ \delta>0 $$

$$ \Delta=2T/(\beta N-1) $$

$$ (N,\alpha,\beta) $$

Proof. The implicit PoS protocol of each instance of DRG-PoRep is the generic graph labeling PoS on a (N;;) depth robust graph. By Lemma4, the graph labeling PoS on a family G(N) of (N;;) depth robust graphs with labeling cost function c(N) is an (n;(N 1)c(N);maxf(1 ‘^1‘2 ); ( + +) g-parallel-sound PoS for any < 1. Setting = 1 + gives = max((1 ‘1() ^‘2⁽⁾ );⁽¹ +² +⁾). For simplicity we set = (recall the distinction was to heuristically allow for dierent levels of security for online vs. oine proofs). Finally, the pebbling cost is

$$ (N,\alpha,\beta) $$

$$ G(N) $$

$$ (N,\alpha,\beta) $$

$$ c(N) $$

$$ (\gamma n,(\beta N!-!1)c(N) $$

$$ \delta)^{\ell_{1}},(\alpha+\gamma+\epsilon)^{\ell_{2}}} $$

$$ \delta<1 $$

$$ {(1- $$

$$ \gamma=1-\epsilon+\delta $$

$$ \mu=m a x((1- $$

$$ \delta)^{\ell_{1}(\lambda)},(1!-!\epsilon!+!2\delta!+!\alpha)^{\ell_{2}(\kappa)}. $$

$$ \lambda=\kappa $$

c(N) = 2T when the VDE delay parameter = 2T=(N 1). Moreover, this PoS is secure under composition (Lemma4).

$$ \Delta=2T/(\beta N-1) $$

$$ c(N)=2T $$

Theorem 2. DRG-PoRep on an (N;;) DRG and with VDE delay parameter = 2 T=(N 1) is e-sound-rational secure when ‘1< ‘2and ‘1() = = and ‘2() = =( 2 ) for any 0 < < ()=2.

$$ (N,\alpha,\beta) $$

$$ \Delta=2T/(\beta N!-1!) $$

$$ e^{-\lambda} $$

$$ \ell_{2}(\lambda)=\lambda\big/\big(\epsilon-\alpha-2\delta\big) $$

$$ \ell_{1}<\ell_{2} $$

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

$$ 0<\delta<(\epsilon-\alpha)/2 $$

Proof. Claim1proves condition (b) of Lemma2with extractor blowup factor c 1 and Claim2 proves condition (c) of Lemma2. Together with the correctness of the construction for an honest prover, these claims therefore establish that DRG-PoRep is-sound-rational secure for any:

$$ c\approx1 $$

$$ \mu>m a x{(1-\delta)^{\ell_{2}},(1-\delta)^{\ell_{1}},(1-\epsilon+\alpha+2\delta)^{\ell_{2}}}, $$

In general for practicality it is desirable that ‘₁is as small as possible, whereas ‘₂may be larger. ‘2 Therefore, we may assume that ‘1< ‘2and can ignore the (1) term. Finally, setting ‘₁‘2 ‘1= = and ‘2= =( 2 ) yields (1) < e and (1 + + 2 ) < e.

$$ \ell_{1} $$

$$ \ell_{2} $$

$$ \ell_{1},\prec<\ell_{2} $$

$$ (1-\delta)^{\ell_{2}} $$

$$ \ell_{1}=\lambda/\delta $$

$$ \ell_{2}=\lambda/big(\epsilon-\alpha-2\delta\big) $$

$$ (1-\delta)^{\ell_{1}}<e^{-\lambda} $$

$$ (1 - \epsilon + \alpha + 2 \delta) ^ {\ell_ {2}} < e ^ {- \lambda} $$

The parameter in Theorem2allows one to tune the relative size of ‘₁and ‘₂to maintain the same level of security in the parameter. Decreasing increases ‘₁and decreases ‘₂.

$$ \ell_{1} $$

$$ \ell_{2} $$

$$ \delta $$

$$ \ell_{1} $$

$$ \ell_{2} $$

Acknowledgements

Joseph Bonneau, Nicola Grecco, and Juan Benet provided critical input throughout the development of this work and are coauthors on a related systems project prototyping practical implementations of PoReps, including the constructions presented at BPASE 2018 and discussed in further detail in this work. Nicola Grecco also helped run the experimental attacks on DRGs presented in Section ??. Many others have contributed through helpful comments and conversations, including Dan Boneh, Rafael Pass, Ethan Cecchetti, Benedikt Bunz, and Florian Tramer.

References

[1]Filecoin: A decentralized storage network. Protocol Labs, 2017. https://filecoin.io/ filecoin.pdf. [2]Proof of replication. Protocol Labs, 2017. https://filecoin.io/proof-of-replication. pdf. [3]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. [4]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. [5]Joel Alwen, Jeremiah Blocki, and Benjamin Harsha. Practical graphs for optimal sidechannel resistant memory-hard functions. In CCS, 2017.

[6]Joel Alwen, Jeremiah Blocki, and Krzysztof Pietrzak. Sustained space complexity. In EUROCRYPT, 2018. [7]Frederik Armknecht, Ludovic Barman, Jens-Matthias Bohli, and Ghassan O. Karame. Mirror: Enabling proofs of data replication. In 25th USENIX Security Symposium, 2016. [8]Giuseppe Ateniese, Randal Burns, Reza Curtmola, Joseph Herring, Lea Kissner, Zachary Peterson, and Dawn Song. Provable data possession at untrusted stores. In ACM Conference on Computer and Communications Security, 2007. [9]Giuseppe Ateniese, Seny Kamara, and Jonathan Katz. Proofs of storage from homomorphic identication protocols. In Asiacrypt, 2009. [10]Niko Barc and Birgit Ptzmann. Collision-free accumulators and fail-stop signature schemes without trees. In Advances in Cryptology - EUROCRYPT ’97, International Con- ference on the Theory and Application of Cryptographic Techniques, Konstanz, Germany, May 11-15, 1997, Proceeding, pages 480{494, 1997. [11]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. [12]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. [13]Josh Cohen Benaloh and Michael de Mare. One-way accumulators: A decentralized alternative to digital sinatures (extended abstract). In EUROCRYPT, 1993. [14]Dan Boneh, Joseph Bonneau, Benedikt Bunz, and Ben Fisch. Veriable delay functions. 2018. To appear in CRYPTO 2018. [15]Kevin D. Bowers, Ari Juels, and Alina Oprea. Proofs of retrievability: theory and implementation. In CCSW’09 Proceedings of the 2009 ACM workshop on Cloud computing security), 2009. [16]Jan Camenisch and Anna Lysyanskaya. Dynamic accumulators and application to ecient revocation of anonymous credentials. In CRYPTO, 2002. [17]Dario Catalano and Dario Fiore. Vector commitments and their applications. In PKC 2013, 2013. [18]F.R.K. Chung. On concentrators, superconcentrators, generalizers, and nonblocking networks. In Bell System Technical Journal, 1979. [19]Bram Cohen. Proofs of space and time. Blockchain Protocol Analysis and Security Engineering, 2017. https://cyber.stanford.edu/sites/default/files/bramcohen.pdf. [20]Moni Naor Cynthia Dwork and Hoeteck Wee. Pebbling and proofs of work. In CRYPTO, 2005. [21]Ivan Damgard, Chaya Ganesh, and Claudio Orlandi. Proofs of replicated storage without timing assumptions. Cryptology ePrint Archive, Report 2018/654, 2018. https://eprint. iacr.org/2018/654. [22]Anindya De, Luca Trevisan, and Madhur Tulsiani. Time space tradeos for attacks against one-way functions and prgs. In CRYPTO, 2010. [23]Yevgeniy Dodis, Salil Vadhan, and Daniel Wichs. Proofs of retrievability via hardness amplication. In Theory of Cryptography Conference (TCC), 2009. [24]Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of space. In CRYPTO, 2015. [25]Uriel Fiege, Amos Fiat, and Adi Shamir. Zero-knowledge proofs of identity. In Journal of Cryptology, 1988.

[26]Ben Fisch, Joseph Bonneau, Juan Benet, and Nicola Greco. Proofs of replication using depth robust graphs. In Blockchain Protocol Analysis and Security Engineering 2018, 2018. https://cyber.stanford.edu/bpase2018. [27]Ben Fisch and Shashwat Silas. Weak compression and (in)security of rational proofs of storage. Cryptology ePrint Archive, Report 2018/514, 2018. https://eprint.iacr.org/ 2018/514. [28]Philippe Golle, Stanislaw Jarecki, and Ilya Mironov. Cryptographic primitives enforcing communication and storage complexity. In Financial Cryptography, 2002. [29]Chethan Kamath Vladimir Kolmogorov Krzysztof Pietrzak Jooel Alwen, Binyi Chen and Stefano Tessaro. On the complexity of scrypt and proofs of space in the parallel random oracle model. In EUROCRYPT, 2016. [30]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. [31]Arjen K Lenstra and Benjamin Wesolowski. A random zoo: sloth, unicorn, and trx. IACR Cryptology ePrint Archive, 2015, 2015. [32]Hendrik W Lenstra Jr. Factoring integers with elliptic curves. Annals of mathematics, pages 649{673, 1987. [33]Sergio Demian Lerner. Proof of unique blockchain storage, 2014. https://bitslog. wordpress.com/2014/11/03/proof-of-local-blockchain-storage/. [34]Beno^t Libert, Somindu C. Ramanna, and Moti Yung. Functional commitment schemes: From polynomial commitments to pairing-based from simple assumptions. In ICALP, 2016. [35]Beno^t Libert and Moti Yung. Concise mercurial vector commitments and independent zero-knowledge sets with short proofs. In TCC, 2010. [36]Mohammad Mahmoody, Tal Moran, and Salil P Vadhan. Time-lock puzzles in the random oracle model. In CRYPTO. Springer, 2011. [37]Ueli Maurer. Unifying proofs of knowledge. In CRYPTO, 2009. [38]Ueli Maurer, Renato Renner, and Clemens Holenstein. Indierentiability, impossibility results on reductions, and applications to the random oracle methodology. In TCC, 2004. [39]S. Matthew Weinberg Miles Carlsten, Harry Kalodner and Arvind Narayanan. On the instability of bitcoin without the block reward. In ACM CCS, 2016. [40]Tal Moran and Ilan Orlov. Rational Proofs of Space-Time. Cryptology ePrint Archive # 2016/035, 2016. [41]Salil Vadhan Omer Reingold and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In FOCS, 2000. [42]Sunoo Park, Krzysztof Pietrzak, Albert Kwon, Joel Alwen, Georg Fuchsbauer, and Peter Gai. Spacemint: A cryptocurrency based on proofs of space. Cryptology ePrint Archive, Report 2015/528, 2015. http://eprint.iacr.org/2015/528. [43]Ronald L. Graham Paul Erdos and Endre Szemeredi. On sparse graphs with dense long paths. In Computers & Mathematics with Applications, 1975. [44]Daniele Perito and Gene Tsudik. Secure code update for embedded devices via proofs of secure erasure. In ESORICS, 2010. [45]Krzysztof Pietrzak. Proofs of Catalytic Space. Cryptology ePrint Archive # 2018/194, 2018. [46]Ling Ren and Srinivas Devadas. Proof of space from stacked expanders. In TCC, 2016. [47]Randal Burns Reza Curtmola, Osama Khan and Giuseppe Ateniese. Mr-pdp: Multiple- replica provable data possession. In In Distributed Computing Systems, 2008. ICDCS08., 2008. [48]Hovav Shacham and Brent Waters. Compact proofs of retrievability. In Asiacrypt, 2008. [49]Luca Trevisan, Salil Vadhan, and David Zuckerman. Compression of samplable sources. Computational Complexity, 14(3):186{227, 2005. [50]Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical Foundations of Computer Science, 1977. [51]Marten van Dijk, Ari Juels, Alina Oprea, Ronald L. Rivest, Emil Stefanov, and Nikos Triandopoulos. Hourglass schemes: how to prove that cloud les are encrypted. In ACM CCS, 2012. [52]Gaven J. Watson, Reihaneh Safavi-Naini, Mohsen Alimomeni, Michael E. Locasto, and Shivaramakrishnan Narayan. Lost: location based storage. In CCSW, 2012.

A Preliminaries and Background

A.1 Compression and Erasure Codes

n n A source S over f0*;* 1g is a distribution over strings in f0*;* 1g. Eⁿcoding schemes consist of a pair of algorithms (enc*;dec) such that enc maps strings from the support Sup(S) of a source S m m to a code space over an alphabet , and dec recovers inputs in Sup(S) from codes in . If n Sup(S) = f0;* 1g aⁿd the distribution S is not relevant to the properties of (enc*;dec) then we n may just call it an encoding scheme oⁿ f0;* 1g. The two types of encoding schemes of interest here are compression and erasure codes, which have opposite goals.

$$ {0,1}^{n} $$

$$ \Sigma^{m} $$

$$ \Sigma^{m} $$

$$ \operatorname{S u p}(\ \mathcal{S})={0,1}^{n} $$

$$ {0,1}^{n} $$

Erasure codes Erasure codes, as the name suggests, can tolerate deletion of a constant fraction of symbols in a code and still recover the encoded data. They are an extreme form of redundant storage.

n n Denition 7. An (r;) erasure code is an encoding scheme (enc; dec) on f0*;* 1g to where ⁿ n=m = r (called the rate) and for all x 2f0*;* 1g such that enc(x) = (w₁;:::;w_m) the decoding algorithm dec can recover x from any (1)m symbols in w, i.e. if E [m] is any m size subset and w^ = ( ^w₁;:::; w^_m) where w^_i=? for i 2 E and w^_i= w_ifor all i 62 E then dec( ^w) = x. A (1*;*) erasure code is called an optimal rate 1 erasure code.

$$ (r,\delta) $$

$$ {0,1}^{n} $$

$$ \Sigma^{n} $$

$$ x\in{0,1}^{n} $$

$$ n/m=r $$

$$ \ n c(x)=(w_{1},...,w_{m}) $$

$$ (1-\delta)m, $$

$$ E\subset[m] $$

$$ \hat{w}=\left(\hat{w}{1},...,\hat{w}{m}\right) $$

$$ {\hat{w}}_{i}=\bot f o r,i\in E $$

$$ \hat{w}{i}=w{i} $$

$$ i\notin,E $$

$$ d e c(\hat{w})=x $$

$$ 1-\delta $$

Compression schemes The goal of compression, in contrast, is to encode the original data source with the smallest possible number of symbols such that the data can still be decoded eciently (at least with high probability). Often a compression scheme will output codes of variable length depending on the input, however for simplicity the following denitions and facts focus on the special case that all outputs are padded to the same length. Unlike erasure codes, compression schemes are not concerned with structural properties of the code other than its overall length, hence without loss of generality the alphabet is = f0*;* 1g.

$$ \Sigma=\left{0,1\right} $$

n Denition 8 (Compression scheme). An (S;k)-compression scheme for a source S over f0*;* 1g ⁿ k is an encoding scheme (enc; dec) such that enc : f0*;* 1g!f0*;* 1g and dec(enc(s)) = s for all s 2 Sup(S).

$$ {0,1}^{n} $$

$$ {0,1}^{n}\rightarrow{0,1}^{k} $$

$$ s\in S u p(\mathcal{S}) $$

Denition 9 (k-Compressible). A source S is said to be k-compressible (or compressible to k bits) if there exists a (S;k)-compression and incompressible to k bits otherwise.

By this denition of an (S;k)-compression scheme it is necessary that k is at least the max entropy of S, i.e. k log₂ jSup(S)j, because it must uniquely encode every string in the support. A lossy compression scheme compromises on the probability of recovery, but may be able to compress to fewer bits than the max entropy.

$$ (S,k) $$

$$ k\geq\log_{2}\ |\operatorname S{u p}(\mathcal{S}) $$

Denition 10. A-lossy (S;k)-compression scheme is an encoding scheme (enc; dec) where n kR enc : f0*;* 1g!f0*;* 1g and Pr_{s S}[dec(enc(s)) = s] = 1*. S is said to be-lossy compressible* to k bits if and only if such an encoding scheme exists and-lossy incompressible otherwise.

$$ {0,1}^{n}\rightarrow{0,1}^{k} $$

$$ P r _ {s} \leftarrow_ {\mathrm {R}} \mathcal {S} [ d e c (e n c (s)) = s ] = 1 - \delta $$

Randomized compression In randomized compression schemes, enc and dec use an additional entropy source to aid in compression. In the most general case enc and dec may simply run independent randomized algorithms. More typically, they will share information about a seed, either communicated through the encoding output itself or pre-shared, which we may assume is R r a uniformly random string U_r(U_rdenotes the uniform distribution ove^r f0*;* 1g). Following the terminology of [27] we distinguish weak and strong randomized compression (similar to weak vs strong randomness extractors). Strong compression stores the seed separately from the compressed data, and is equivalent to compression with shared randomness. Weak compression may entangle the seed and the data in the code in such a way that the decoder can still recover both the data and the seed.

$$ \rho\xleftarrow{\ \ \ \ \} $$

$$ {0,1}^{r}) $$

Denition 11 (Weak compression). A-lossy (S;r;k)-weak compression for a source S over n r n r+k f0*;* 1g is an encoding scheme (enc; dec) such that enc : f0*;* 1g f0*;* 1g! f0*;* 1g and Pr^R R[dec(enc(r;s)) = (r;s)] = 1*.* Ur;s S

$$ (\mathcal{S},\boldsymbol{r},\boldsymbol{k}) $$

$$ \mathcal{S} $$

$$ {0,1}^{n} $$

$$ :;{0,\ 1}^{r};\times;{0,1}^{n};;\to;;{0,,1}^{r+k} $$

$$ P r{}{\rho\xleftarrow{}{\mathbb{U}{r},s}xleftarrow{}{\mathcal{S}}[d\mathsf{e r}(e nmathsf{c}(r,s))=(r,s)]}=1-\delta $$

Denition 12 (Strong compression). A-lossy (S;r;k)-strong compression for a source S over n r n k f0*;* 1g is an encoding scheme (enc; dec) where enc : f0*;* 1g f0*;* 1g! f0*;* 1g and dec : r k nR R f0*;* 1g f0*;* 1g!f0*;* 1g such that Pr_{Ur;s S}[dec(; enc(;s)) = s] = 1*.*

$$ \mathcal{S} $$

$$ (\mathcal{S},\boldsymbol{r},\boldsymbol{k}) $$

$$ {0,1}^{n} $$

$$ :{0,1}^{r},\times{0,1}^{n},\to,{0,1}^{k} $$

$$ {0,1}^{r}\times{0,1}^{k}\rightarrow{0,1}^{n} $$

$$ P r_{\rho{xarrow{\longleftarrow}}{\mathbb{U}{r},s}{xleftarrow{\mathbbleftarrow}}_{\mathcal{S}}}[d\mathsf{e c c}(\rho,\mathsf{e n c}(\rho,s))=s]=1-\delta $$

A lossy strong compression scheme can be made lossless for a small decrease in compression [49]. Even strong compression schemes cannot compress a uniformly random data source [22].

Fact 1. If there exists a-lossy (S;r;k)-strong compression for a source S then there exists an (S;r;k + (n k) + 1)-strong compression of S with no loss.

$$ (\mathcal{S},\boldsymbol{r},\boldsymbol{k}) $$

$$ \left(\mathcal{S},r,k+\delta(n-k)+1\right) $$

n Fact 2. The uniform distribution U_nover f0*;* 1g is incompressible to n 1 bits and-lossy incompressible to n log(1*=) 1. Likewise, there does not exist a-lossy* (U_n;r;n log(1*=) 1)-* strong compression scheme.

$$ U_{n} $$

$$ {0,1}^{n} $$

$$ n-1 $$

$$ n{-}\log(1/\delta){-}1 $$

$$ \bigl(U_{n},r,n{-}\log(1/\delta){-}1\bigr). $$

A.2 Proofs of Retrievability

A proof-of-retrievability (PoR) is an interactive proof system in which a verier sends a le F to a prover, retains a compact verication key, and later obtains a compact proof that prover can retrieve F intact. The compactness requirement excludes trivial solutions, such as sending the full le F back to the verier or requiring the verier to retain F. They were introduced in [30] and further developed in [15,23,48]. The related (weaker) concept of provable-datapossession (PDP) was independently introduced in [8]. Abstractly, these constructions involve two layers of encodings. First an erasure code is applied to the le F to generate F, which guarantees that F can be decoded from adversarial deletion of an fraction of F. Next, the

$$ \tilde{F}, $$

$$ \tilde{F} $$ le F~ is transformed using a secret-key encoding (essentially a type of authentication code), and the verier retains the key. The second encoding can be checked through a constant size challenge-response protocol, which the prover will fail if it cannot recover at least a 1 fraction of F~. An important security property of PoR is that the verier can extract and recover the le F through suciently many successful challenge-response queries to the prover.

$$ \tilde{F} $$

$$ \tilde{F} $$

While a standard PoR requires a secret key to verify, there are also constructions that allow for outsourced verication where anyone can verify without knowledge of the secret [30,48]. We refer to this as a public-key PoR to distinguish it from a private-key PoR that requires a private key for verication. Shacham and Waters [48] construct an ecient public-key PoR (from CDH in bilinear groups) using the homomorphic properties of BLS signatures. Their construction was generalized to rely on a broader class of homomorphic linear authenticators [9]. This property has been described as \public veriability", however these proofs still rely on a private-key client to privately preprocess the le. If the prover and client collude then the proof does not demonstrate anything meaningful to a third party observer.

A Merkle commitment (i.e. a Merkle tree over the blocks of the le) can be be used to construct a simple, albeit less ecent, publicly veriable PoR [30]. The verier need only retain the Merkle commitment root. To verify that the prover is still storing a (1) fraction of the committed le blocks it queries for a randomly selected constant number of blocks. The prover then responds with the blocks and Merkle inclusion proofs for each. This public PoR is keyless, which is an important dierence from the public PoR of Shacham and Waters. For example, it can be used to give a publicly veriable proof-of-retrievability of a committed le, where the even the prover itself sets up the commitment. We present this as a standalone primitive and describe a generalized construction using vector commitments.

A.3 Vector Commitments

A vector commitment (VC) [17,35] is a cryptographic commitment to an ordered sequence of m values (x₁;:::;x_m) that admits succinct openings at specic positions (e.g., prove that x_iis the i-th committed message). For security, VCs are required to satisfy position binding, which states that an adversary should not be able to open a commitment to two dierent values at the same position. Moreover, VCs are required to be concise, i.e. the size of the commitment string and of its openings is independent of the vector length. Usually VCs are also required to be hiding, meaning that opening at several positions does not leak any information about the committed values at other positions. A Merkle tree is an example of a simple vector commitment that is binding and concise but not hiding. The main drawback of Merkle commitments are that proofs are of size log₂ m bits where m is the length of the vector and is the length of the hash output (e.g. = 256 for collision resistance).

$$ (x_{1},...,x_{m}) $$

$$ x_{i} $$

$$ \lambda\log_{2}m $$

Catalano and Fiore [17] gave several constructions of vector commitments achieving both hiding and constant size openings, one from RSA and the other from CDH over bilinear groups. These were further improved upon in [34]. The main drawback of these constructions are the size of the public parameters, which are linear in the length of the vectors. As noted in [17], the RSA-based vector commitment can be modied to reduce the size of the public parameters, but at the expense of a signicant increase in verication work.

Cryptographic accumulators [10,13] give constant size commitments to a set of elements with constant size inclusion proofs of a single element, however they do not yield a vector commitment (i.e. commitment to an ordered set) with ecient inclusion proof at a specied index. This is due the fact that they are not naturally binding to an element at a particular index|the natural idea of prepending an index to each element inserted does not preclude inserting more than one element with the same prepended index.

Vector commitment syntax We provide a redacted syntax for vector commitments (omitting functionality for updating commitments) and allowing for batched openings.

1. VC.Setup(1*;n; M*)! pp Given security parameter, length n of the vector, and message space of vector components M, output public parameters pp, which are implicit inputs to all the following algorithms.

$$ {\mathsf{S e t u p}}(1^{\lambda},n,{\mathcal{M}})\to p p $$

$$ \lambda, $$

2. VC.Com(~m)! ;c Given an input ~m = (m₁;:::;m_n) output a commitment c and advice .

$$ .\mathsf{C o m}(\vec{m})\to\tau,c $$

$$ \ {\vec{m}}=\left(m_{1},...,m_{n}\right) $$

3. VC.Open(~m;c;S;)!_SOn input ~m, a vector of indices S, the commitment c, and advice output an opening _Sthat proves m_iis the ith committed element of c for all S[i] (where S[i] denotes the ith element of S).

$$ \ \mathsf{O p e n}(\vec{m},c,S,\tau),\to,\Lambda_{S} $$

$$ {\vec{m}}, $$

$$ c, $$

$$ m_{i} $$

$$ S[i] $$

0q 4. VC.Verify(c;m⁰₁;:::;m;S;_S)! 0*=1 On input commitment c, a vector S of indices in [n], and an opening proof _Soutput 1 (accept) if and only if _Sis a valid proof that c is a 0j commitment to a vector ~m such that m_S^[j]= m for j 2 [q]. If S =;* then should be a 0i normal opening, i.e. proof that c is a commitment to m s.t. m_i= m for all i (and q = n).

$$ \mathsf{V C}.\mathsf{V e r i f y}(c,m_{1}^{\prime},...,m_{q}^{\prime},S,\Lambda_{S})\to0/1 $$

$$ c, $$

$$ [n] $$

$$ \Lambda_{S} $$

$$ \Lambda_{S} $$

$$ \vec{m} $$

$$ m_{S[j]}=m_{j}^{\prime} $$

$$ j\in[q] $$

$$ S=\emptyset $$

$$ m_{i}=m_{i}^{\prime} $$

$$ q=n) $$

Binding commitments The main security property of vector commitments (of interest in the present work) is position binding. The security game augments the standard binding commitment game

Denition 13. A vector commitment scheme VC is position binding if for all O(poly(;n)-time adversaries A and for all S⁰;S [n] with jSj = q and jS⁰j = q⁰ and i 2 [q];j 2 [q⁰] the following probability is at most negligible in :

$$ O(p o l y(\lambda,n) $$

$$ \ {mathcal S,}\ {mathcal S subseteq\left[{n}\right]} $$

$$ |S|=q $$

$$ |S^{\prime}|=q^{\prime} $$

$$ i\in[q],j\in[q^{\prime}] $$

$$ P r \left[ \begin{array}{c c} V C. V e r i f y (c, \vec {m}, S, \Lambda) = 1 \wedge V C. V e r i f y (c, \vec {m} ^ {\prime}, S ^ {\prime}, \Lambda^ {\prime}) = 1 & p p \leftarrow V C. S e t u p \left(1 ^ {\lambda}, n, \mathcal {M}\right) \ \wedge S [ i ] = S ^ {\prime} [ j ] \wedge m _ {i} \neq m _ {j} ^ {\prime} & \left(c, \vec {m}, \vec {m} ^ {\prime}, \Lambda , \Lambda^ {\prime}\right) \leftarrow \mathcal {A} (p p) \end{array} \right] $$

A.4 Proof of Retrievable Commitment

We describe here a primitive that we call a proof of retrievable commitment (PoRC), or alternatively a keyless PoR, which allows a prover to give a compact proof of retrievability for a committed value. Similar to a public PoR, the proof verication algorithm does not take a private key. However, it additionally does not involve any private-key preprocessing of the le. Therefore, unlike public-key PoRs where the verication may only be outsourceable, PoRs are truly publicly veriable: a PoRC is a standard PoR to any verier that is rst given the opening of the commitment (to a particular le) and retains the commitment as a tag. Indeed the concepts of a PoRC and keyless PoR are roughly equivalent, as any keyless PoR must involve a keyless data extractor, implying that it can be used as a binding commitment scheme (where 20 opening is through extraction). A PoRC is also similar to a succinct proof of knowledge (PoK),

²⁰ This has also been referred to as a PoR with public extraction in [48].

or SNARK [11], of a committed value. The dierence lies still in the type of extraction, which unlike knowledge extraction does not require reading the prover’s internal state.

The notion of a PoRC was already implicit in the literature on proofs of retrievability, a simple example being the PoR from Merkle commitments suggested by [30], although a formal presentation and proof of security was not given therein. We present a more general construction 21 of PoRC from any vector commitment scheme and provide a formal proof of security.

A.4.1 PoRC Syntax and Denitions

n Our syntax for a PoRC with a message space Mf0*;* 1g is as follows.

$$ \mathcal{M}\subseteq{0,1}^{n} $$

1. PoRC.Setup(1*; M*)! pp; M on input security parameter and message space M output public parameters pp.

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

2. PoRC.Commit(pp;m)! com;; on input pp and a message m 2M outputs a binding commitment com to the message m along with an opening hint and additional advice for the prover.

$$ (p p,m)\rightarrow c o m,\Lambda,\alpha $$

$$ m\in{\mathcal{M}} $$

3. PoRC.Open(pp;com;)! m opens the commitment com to a message m 2M[? given the opening hint . The output is*?* if and only if is an invalid opening.

$$ .\mathsf{O p e n}(p p,c o m,\Lambda)\to m $$

$$ m\in\mathcal{M}\cup\bot $$

$$ \perp\mathrm{i f} $$

$$ {\mathsf{e}}(p p,\alpha,c o m,c)\to\pi $$

4. PoRC.Prove(pp;;com;c)! is a proof generation algorithm that takes pp, the storage advice, the commitment com, a challenge c (from either the verier or possibly a public source) and outputs a proof.

5. PoRC.Verify(pp;com;c;)! 0*=*1 receives pp, the commitment com, challenge c, and proof and outputs either 1 (accept) or 0 (reject).

$$ \ {mathfrak i f f}(p p,c o m,c,\pi)\to0/1 $$

PoRC protocol We dene the PoRC interactive protocol between a prover P and verier V. The PoRC interactive protocol as we dene it here is public coin, but could be expanded to allow for private coin protocols as well. First P runs PoRC.Commit(pp;m), sends the output com to the verier, and stores both the opening hint and additional advice. Next V samples a random challenge c and sends this to P. Finally, P runs PoRC.Prove(pp;;com;c) and sends the output to V, who runs PoRC.Verify(pp;com;c;) and outputs its decision 0/1. Note that PoRC.Open is not used in the protocol, but its existence (satisfying a message binding property) is necessary for security. Furthermore, a verier may use PoRC.Open to obtain an opening of the commitment at any point, or alternatively its description (e.g. in order to verify a zeroknowledge proof of some property of the message).

$$ \pi $$

$$ \nu $$

Correctness For a PoRC to be correct we require the commitment com to be compact, i.e. logarithmic in the length of m. Furthermore, in the PoRC interactive protocol with an honest prover and verier (for any m 2 M) should output 1 (accept) with probability 1. (We omit further formalism as this is standard).

$$ m\in{\mathcal{M}}) $$

²¹ Our proof is a straightforward coupon collector’s argument, following the same proof technique from [48] and [23]. The reason the proof is non-trivial to begin with arises from the fact that all challenges are given to the prover in parallel (rather than sequentially) to amplify soundness. This is more broadly connected to direct product theorems in hardness amplication. In fact, Lemma 1 follows from a more general and previously known result (Lemma 7 of [23]), however we still include our own analysis in the special setting of PoRC from vector commitments, both for completeness of presentation and the benet of the reader.

$$ 7 $$

Soundness The PoRC soundness property is more subtle and has two components: commitment binding and retrievability. These properties are intertwined as together they say that for any admissible prover (loosely one that is suciently successful) there exists an extraction process that extracts a message m unique to the commitment com.

The rst requirement is that PoRC.Commit/PoRC.Open is a binding commitment scheme in the standard sense:

Denition 14. A PoRC scheme is binding if for all O(poly()) adversaries A the probability 0 over pp PoRC.Setup(; M) and (;;c) A (pp) and m PoRC.Open(pp;c ;) and 0 m⁰ PoRC.Open(pp;c ;) that m⁰ 6= m 6=? is negligible in.

$$ O(o l y(\lambda)) $$

$$ p p\gets\mathit{P o R C.S e t u p}(\lambda,\mathcal{M}) $$

$$ (\Lambda,\Lambda^{\prime},c^{*}),\leftarrow,\mathcal{A}(p p) $$

$$ m\gets P o R C.O p e n(p p,c^{*},\Lambda) $$

$$ m^{\prime}\gets\mathit{P o R C.O p e n}(p p,c^{*},\Lambda^{\prime}) $$

$$ \neq m\neq\bot $$

$$ {lambda\cdot}. $$

Next we dene retrievability. Intuitively, the desired property is that any adversary who is a able to produce a commitment com, open this commitment to a value m (e.g. for a client), and then succeed with non-negligible probability in the PoRC protocol with a public verier must still be able to retrieve the value m, i.e. there is an extractor that can run the prover on public verier challenges in order to uniquely extract the same value m. We dene a game played between an adversary A = (A₁;A₂) and a challenger which essentially just runs the public-coin PoRC protocol. The game is simpler than the PoR games in [23,48] because of our restriction to a public coin verier. The game is parametrized by input m 2M and public parameters pp and runs as follows:

$$ \mathcal{A}=(A_{1},A_{2}) $$

$$ m\in{\mathcal{M}} $$

1. A₁ on input pp and m outputs a message com (adversarial commitment) along with ;. It passes to A₂ and sends com ; to the challenger. The challenger runs m PoRC.Open(pp;com ;). If m 6= m then the challenger outputs 0 and terminates the game.

$$ A_{1} $$

$$ \alpha^{},\Lambda^{} $$

$$ \alpha^{*} $$

$$ A_{2} $$

$$ c o m ^ {}, \Lambda^ {} $$

$$ m^{}\gets\mathsf{P O R C.O p e n}(p p,c o m^{},\Lambda) $$

$$ m^{*}\neq $$

2.The challenger samples a challenge c uniformly at random from the domain of challenges and sends this to A₂.

$$ A_{2} $$

3. A₂ (running on c,, and com) outputs an adversarial proof.

$$ c,,\alpha^{*} $$

$$ \pi^{*} $$

4.The challenger computes b PoRC.Verify(pp;com ;c;) and outputs b.

$$ b\gets P o R C.V e r i f y(p p,c o m^{},c,\pi^{}) $$

For any m 2 M we denote the challenger’s output in the game as a probability distribution PoRC-Exp(A;m;pp) over the randomness of A, the challenger’s queries, and pp 22 PoRC.Setup(; M).

$$ m\ \in\ \mathcal{M} $$

$$ \mathsf{P o R C-E E p p}(\mathcal{A},m,p p) $$

$$ {\mathcal A}, $$

$$ p p\leftarrow $$

$$ \mathsf{P o R C.S e t u p}(\lambda,\mathcal{M}).^{22} $$

Denition 15. A PoRC adversary A is-admissible on input m if and only if A₁ outputs com such that PoRC.Open(pp;com ;) 6=? with probability 1 negl() and PoRC-Exp(A;m;pp) = 1 with probability at least.

$$ A_{1} $$

$$ O p e n(p p,c o m^{*},\Lambda)\neq\bot $$

$$ 1-n e g/(\lambda) $$

$$ P o R C\cdot E x p(\mathcal{A},m,p p)=1 $$

We dene a PoRC extractor E (akin to the extractor in a proof of knowledge) as an oracle algorithm that is given the output com of the PoRC adversary A and simulate the interaction between the challenger and A₂. An important modication is that the extractor can rewind A₂ and reissue fresh challenges (for further formalism on extractor machines that can rewind adversaries see [25,37]). The key dierence between our extractor and a standard knowledge

$$ A_{2} $$

$$ A_{2} $$

²² The adversary in the game is non-adaptive, which at rst glance may appear to weaken the adversary. Note that the challenger in the game is entirely public-coin. The adversary can simulate any polynomial number of adaptive rounds of the game in his head before engaging in a nal real round with the challenger.

extractor is that it cannot read the internal state or inputs of the adversary in the game, only the power to rewind its randomness. More specically, in each run of the extractor playing the game PoRC-Exp(A;m;pp) with A, it rst obtains a commitment c and then repeatedly queries A₂ (possibly rewinding A₂ at some points), until it nally outputs either a message m 2M or A(m) ? (indicating failure). Let m E ⁽pp⁾ denote the output distribution of this experiment.

$$ \mathsf{P o R C-E E p p}(\mathcal{A},m,p p) $$

$$ c^{*} $$

$$ A_{2} $$

$$ A_{2} $$

$$ m^{*}\in{mathcal M M} $$

$$ \perp $$

$$ m^{*}\leftarrow\mathcal{E}^{\mathcal{A}(m)}(p p) $$

Denition 16. A PoRC is-sound if it is binding and additionally for every there exists a PoRC extractor E that runs in time poly(;n;1=) such that for any m 2M and any adversary A(m) A that is-admissible on m the probability over pp PoRC.Setup(; M) and m E ⁽pp⁾ that m 6= m is at most negl().

$$ \lambda $$

$$ p o l y(\lambda,n,1/\epsilon) $$

$$ m\in{\mathcal{M}} $$

$$ p p\gets P o R C.S e t u p(\lambda,\mathcal{M}) $$

$$ m^{*}\leftarrow\pmb{\mathcal{E}}^{\mathcal{A}(m)}(p p) $$

$$ m^{*}\neq $$

Denition16captures that any adversary who passes the PoRC protocol with non-negligible probability at least must be able to retrieve the underlying data by running the extractor in 23 time O(1*=*poly( )) with its own code. If on the other hand the adversary does not pass the PoRC with probability at least then the soundness error of the protocol with this adversary is in the standard sense (i.e. it is caught with probability at least 1).

$$ O(1/\mathrm{p o l y}(\epsilon)) $$

Extractor runtime Extractors always have a larger runtime complexity than the original adversary A. Extractors are considered stronger the smaller this overhead. In our case A₁ rst generates a commitment that is then given to A₁ (we do not count the runtime of A₁ on pp as part of the extractor’s runtime). We say that the extractor has constant blowup if the runtime is only a constant factor larger than A₂. It turns out that the parallel runtime of the PoRC extractor will be highly relevant to the security analysis of PoRep schemes. We say the extractor has constant PRAM blowup if the parallel runtime is only a constant factor larger than the parallel runtime of A₂.

$$ A_{1} $$

$$ A_{1} $$

$$ A_{1} $$

$$ A_{2} $$

$$ A_{2} $$

Denition 17. A PoRC is PRAM strongly-sound if it is-sound and additionally the extractor has constant PRAM blowup.

Partial retrievability Sometimes proofs of retrievability can be useful even if they only prove partial recovery, e.g. that a constant fraction of the bits of the message can be retrieved. In fact, all known constructions of PoR eectively rst prove partial recovery, which is amplied to a proof of full recovery through erasure coding. The proof of partial recovery itself is more ecient because it does not require blowing up the size of the message. Even if partial recovery is not the end goal it is useful to abstract this as a standalone primitive that can be used as a subcomponent of cryptographic protocol (in our case PoReps).

We dene a-PoRC as a proof that a fraction of a committed message can be retrieved. We generalize this even further to a (; C)-PoRC where C is any set cover of the committed message m, each set consisting of bit indices of m (assume w.l.o.g. that m is represented as a bit vector). This is useful when it is important to ensure that the missing fraction of bits isn’t completely arbitrary, for example that at least a fraction of complete message blocks are retrievable. A-PoRC is equivalent to the special case where the set cover consists of disjoint singleton sets, each containing a single bit of the message.

$$ m. $$

²³ Due to the fact that the extraction algorithm is public, this is stronger than standard knowledge extraction, where only the adversary who generated the adversarial code in the rst place necessarily can extract the witness. For instance, the interactive adversary in the protocol may have been given obfuscated code that hides the witness.

The security game and extractor for a (; C)-PoRC is unchanged from the denition of PoRC and only the denition of-soundness needs to be modied. For any pair of equal length messages 0i jmj = jm⁰j = n and index subset S [n] let m_Sm⁰ denote that m_i= m for all i 2 S.

$$ |m|=|m^{\prime}|=n $$

$$ S\subseteq[n] $$

$$ m\equiv_{S}m^{\prime} $$

$$ m_{i}=m_{i}^{\prime} $$

$$ i\in S $$

Denition 18. A (; C) PoRC is-sound if it is binding and additionally for some²⁴_;2 O(log*=log) and every > _;there exists an extractor E that runs in time poly(;n;1=) such that for any m 2M and any adversary A that is-admissible on m the probability over A(m) pp PoRC.Setup(; M*) and m E ⁽pp⁾ that m_Sm for at least a fraction of the sets S 2C is greater than 1 negl(). It is PRAM strongly-sound if E has constant PRAM blowup.

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

$$ c^{24}\ \lambda_{\epsilon,\delta}\ \in $$

$$ \lambda>\lambda_{\epsilon,\delta} $$

$$ p o l y(\lambda,n,1/\epsilon) $$

$$ m\in{\mathcal{M}} $$

$$ p p\gets P o R C.S e t u p(\lambda,\mathcal{M}) $$

$$ m^{*}\leftarrow\pmb{\mathcal{E}}^{\mathcal{A}(m)}(p p) $$

$$ m\equiv_{S}m^{*} $$

$$ S\in{\mathcal{C}} $$

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

A.4.2 PoRC from Vector Commitments

We describe a construction of a (; C)-PoRC for blocked messages of a xed length consisting of n blocks from a message space M, and any set cover C consisting of unions of at most O(logn) k blocks. For applications with variable length commitments we can run the setup for each n = 2 up to a maximum size. The construction also easily generalizes to set covers consisting of sets that are unions of at most O(polylog(n)) bit indices, regardless of the block size. We use a vector commitment scheme VC = (VC.Setup*;VC.Com;VC.Open;*VC.Verify) as a black box.

$$ O(\log n n) $$

$$ n=2^{k} $$

Construction VC-PoRC

1. PoRC.Setup(1 ): Run VC.Setup(1*;n; M*)! pp_vc. Output pp.

$$ \ {\mathsf{V C.S e t u p}}(1^{\lambda},n,{\mathcal{M}})\to p p_{v c} $$

2. PoRC.Commit(pp;m): Parse m as a vector ~m = (m₁;:::;m_n) where m_i2 M. Run VC.Com(~m)! ;com, and output*;com*.

$$ \vec{m};=;\left(m_{1},...,m_{n}\right) $$

$$ m_{i}\ \in\ \mathcal{M}. $$

$$ 1\mathsf{C.C o m}({\vec{m}})\to\tau,c o m. $$

$$ {\boldsymbol{\tau}}, $$

3. PoRC.Prove(pp;;com;c): Let C = fS₁*;:::;Skg* where each Si[n]. Parse c as integers S c₁;:::;c 2 [k]. Let S = S_ci. Run VC.Open(~m;c;S;)!. Output the proof i=1 consisting of all fm_jg for j 2 S and .

$$ (p p,\tau,c o m,c) $$

$$ \mathcal{C}={S_{1},...,S_{k}} $$

$$ \ {mathcal S_{{i}}}\subset[n] $$

$$ c_{1},...,c_{\lambda},\in,[k] $$

$$ \textstyle S,=\bigcup_{i=1}^{\lambda}S_{c_{i}} $$

$$ \pi $$

$$ \mathsf{V C.O p e n}(\vec{m},c,S,\tau)\to\Lambda $$

$$ {m_{j}} $$

$$ j\in S $$

S 4. PoRC.Verify(pp;com;c;): On c = c₁;:::;c 2 [k] dene S = S^ci. Parse = i=1 0‘ 0‘ (m⁰₁;:::;m;) and output 0 (reject) if jSj6= ‘. Run VC.Verify(com;m⁰₁;:::;m;S;) (given input S as a sorted ordered list) and output the result.

$$ c,=,c_{1},...,c_{\lambda},\in,[k] $$

$$ S;=;\bigcup_{i=1}^{\lambda}S_{c_{i}} $$

$$ \pi\ = $$

$$ (m_{1}^{\prime},...,m_{\ell}^{\prime},\Lambda) $$

$$ |S|\neq\ell. $$

$$ V C.V e r i f y(c o m,m_{1}^{\prime},...,m_{\ell}^{\prime},S,\Lambda) $$

$$ S $$

Proof size Let s(n;k) denote an upper bound on the size of proofs output by VC.Open for vectors of length n over the message space M and index subset of size k. Let k_maxdenote the largest set in C. The total proof size output by PoRC.Prove is at most s(n;k_max) + k_maxlog(jMj), which by denition of VC is asymptotically O( log² n). For instantiations of 2 VC with constant size openings, i.e. s(n;k) 2 O(k), the proof size is O( logn). If VC supports batching the size is brought down to O( logn), which is the size of the sampled sets (i.e. the vector commitment opening proof is no longer the bottleneck).

$$ s(n,k) $$

$$ k_{m a x} $$

$$ s(n,\lambda k_{m a x})\ + $$

$$ \lambda k_{m a x}l o g(|\mathcal{M}|) $$

$$ s(n,k)\in O(\lambda k) $$

$$ O(\lambda\log^{2}n) $$

$$ O(\lambda^{2}\log\boldsymbol{n}) $$

Correctness As explained above, the proof size is compact, i.e. at most O( log² n). An honest prover who stores the input message m is able to pass verication by correctness of the vector commitment scheme VC.

$$ O(\lambda\log^{2}n) $$

²⁴ The denition would still be technically equivalent in an asymptotic sense if it read \for every " without further requirement, however the rewording helps to clarify that in general we cannot hope the extractor will succeed for.

$$ \lambda^{2} $$

$$ \epsilon\leq\delta^{\lambda} $$

A(m) Soundness We show that there is an extractor E such that E ⁽pp⁾ outputs the le m with overwhelming probability for any adversary A that is-admissible on m, where > is non-negligible.

$$ {\mathcal{E}}^{{\mathcal{A}}(m)}(p p) $$

$$ m $$

$$ \epsilon>\delta^{\lambda} $$

Theorem 3. VC-PoRC with security parameter is an-sound (; C)-PoRC for any > 0 such that > negl().

$$ \lambda $$

$$ \epsilon-\delta^{\lambda}>n e g I(\lambda) $$

$$ \epsilon>0 $$

Proof. We dene E_Awith A = (A₁;A₂) is given pp from PoRC.Setup(1 ) (sampled in the game PoRC-Exp(A;)), and the index set cover C = fS₁;:::;S_kg and runs as follows.

$$ \mathcal{E}_{A} $$

$$ \mathcal{A}=(A_{1},A_{2}) $$

$$ .mathsf\mathsf S{t u u}(1^{\lambda}) $$

$$ \mathsf{P o R C\ E E p p}(\mathcal{A},\lambda)) $$

$$ \mathcal{C}={S_{1},...,S_{k}} $$

1.Query A₁ to get com. Initialize a round counter r = 0. Initialize a set D =; and initialize a length n vector ~v = (0*;::::;* 0) of 0s.

$$ A_{1} $$

$$ r=0 $$

$$ D=\emptyset $$

$$ \vec{v}=(0,...,0, $$

2.Increment the counter r := r + 1. Sample a random challenge vector c = (c₁;:::;c) 2 [k] and query A₂ on c and record the response_c.

$$ r:=r+1 $$

$$ c=\left(c_{1},...,c_{\lambda}\right)\in[k]^{\lambda} $$

$$ \pi_{C} $$

$$ A_{2} $$

S 3.Run b PoRC.Verify(pp;com ;c;^c). If b = 0 do nothing. If b = 1, let S = S^ciand i=1 0‘ parse_c= (m⁰₁;:::;m;) where ‘ = jSj (if_ccould not be parsed this way it would have been rejected). Write S as a sorted list of its elements and for any j 2 [‘] let S[j] denote the index at the jth position of the sorted list. If any c_i62 D (for 1 i), then update 0j D := D [fc_ig. For each j 2 [‘] update v_S[j]= m.

$$ b\gets P o R C.V e r i f y(p p,c o m^{*},c,\pi_{c}) $$

$$ b=0 $$

$$ b=1 $$

$$ \textstyle{S=\bigcup_{i=1}^{\lambda}S_{c_{i}}} $$

$$ \ell=|S|\ (mathrm i f f\ \pi_{c} $$

$$ \pi_{c}=(m_{1}^{\prime},...,m_{\ell}^{\prime},\Lambda) $$

$$ j\in[\ell] $$

$$ S[j] $$

$$ 1\leq i\leq\lambda) $$

$$ c_{i}\not\in D $$

$$ D:=D\cup{c_{i}} $$

$$ j\in[\ell] $$

$$ v_{S[j]}=m_{j}^{\prime} $$

2( +1)n 4.If r =₂or if jDj k then terminate and output m = ~v. Otherwise rewind A₂ () and repeat from Step 2.

$$ r=\frac{2(\lambda+1)\delta n}{(\epsilon-\delta^{\lambda})^{2}} $$

$$ A_{2} $$

$$ |D|\geq\delta k $$

$$ m^{*}=\vec{v}. $$

The extractor’s goal is to obtain components of m for all indices covered by a fraction of index sets in C. Step 3 runs the adversary on a fresh challenge to open com on all indices of sampled sets from C. If the adversary passes the challenge (verication succeeds) in Step 3, then by the security of the commitment scheme the extractor obtains the components of m on all these queried indices. The extractor checks o any newly covered index sets and terminates if it has already covered at least a fraction. Otherwise it repeats (rewinding the adversary to use the same randomness) until the max round is reached. Finally, note that although in the description of E_Aruns for r sequential rounds, observe that all the queries to A₂ (Step 2) are independent of state and thus can be run in parallel. A₂ is rewound for each query, therefore querying r copies of A₂ in parallel achieves the same result. The bookkeeping in Step 3 can be run in parallel on the outputs of all these queries.

$$ \delta $$

$$ {\mathcal C,} $$

$$ c o m^{*} $$

$$ \delta $$

$$ \mathcal{E}_{\mathcal{A}} $$

$$ A_{2} $$

$$ A_{2} $$

$$ A_{2} $$

Lemma3proves that the (; C)-PoRC from vector commitments is-sound for any >

• negl(). In light of the above remark, the construction is PRAM strongly-sound with only constant additive PRAM blowup.

$$ \delta^{\lambda}+\mathsf{n e g l}(\lambda) $$

$$ \epsilon\ > $$

Lemma 3. Assuming VC is a position binding vector commitment scheme, then for any- admissible A where > is non-negligible, the extractor E_Aoutputs m such that m_Sm for at least a fraction of index sets S 2C except with probability 2*.*

$$ \epsilon>\delta^{\lambda} $$

$$ \mathcal{E}_{\mathcal{A}} $$

$$ m^{*} $$

$$ m^{*}\equiv_{S}m $$

$$ S\in{\mathcal{C}} $$

Proof. First recall that an-admissible adversary will cause the challenger to output 1 in Step 1 except with negligible probability.

From here the proof proceeds in two parts. First, we say that A = (A₁;A₂) is well- behaved if whenever A₁ passes Step 1 of the game PoRC-Exp(A;)) (i.e. presents com and

$$ {\mathcal{A}};=;(A_{1},A_{2}) $$

$$ A_{1} $$

$$ \mathsf{P o R C_E x\times p}(\mathcal{A},\lambda), $$

m = (m₁;:::;m_n) to the challenger with opening such that VC.Verify(com ;m₁;:::;m_n;) = 1) and A₂ responds to some query c with a proofcsuch that PoRC.Verify(pp;com ;c;c) = 1 then S 0 _c= (m⁰₁;:::;m⁰;) and m⁰ = m_S[j]for all j 2 [‘], where S = S_ci(the indices covered by ‘ j i=1 the query c). We claim that A is well-behaved except with probability negl().

$$ m=(m_{1},...,m_{n}) $$

$$ \mathsf{N e r i f y}(c o m^{*},m_{1},...,m_{n},\Lambda),=,1 $$

$$ \pi_{c} $$

$$ A_{2} $$

$$ \mathsf{V e r i f y}(p p,c o m^{*},c,\pi_{c})=1 $$

$$ \pi_{c}=\left(m_{1}^{\prime},...,m_{\ell}^{\prime},\Lambda^{\prime}\right) $$

$$ m_{j}^{\prime}=m_{S[j]} $$

$$ j\in[\ell] $$

$$ S=\bigcup_{i=1}^{\lambda}S_{c_{i}} $$

0‘ 0 Indeed if the PoRC verication passes on^cthen VC.Verify(com ;m⁰₁;:::;m;S;) = 1. If ^0j 0 m 6= m_S[j]on some j then com ;m⁰;;m; is an opening collision of the vector commitment scheme. If this happens with non-negligible probability (conditioned on A₁ passing Step 1), then because by hypothesis A₁ passes Step 1 at least with non-negligible probability, we can use A to break the position binding of VC with non-negligible probability, a contradiction.

$$ \pi_{C} $$

$$ \ \ .\mathsf{V e r i f y}(c o m^{*},m_{1}^{\prime},...,m_{\ell}^{\prime},S,\Lambda^{\prime}),=,1 $$

$$ m_{j}^{\prime}\neq m_{S[j]} $$

$$ j $$

$$ c o m^{*},m^{\prime},\Lambda^{\prime},m,\Lambda $$

$$ A_{1} $$

$$ A_{1} $$

For the second part we assume that A is well-behaved. Queries c for which A₂ passes verication are \good" queries, and all other queries are \bad" queries. Consider any iteration of the extractor where D [n] and jDj < k. If the extractor asks a \good" query c = (c₁;:::;c) such that c_w62 D for some w 2, then in Step 3 it adds c_wto D increasing the size by (at least) 0j

1. Furthermore, because A is well-behaved the extractor updates v_S[j]= m = m_S[j]for each index S[j];j 2 ‘ covered by the query. Thus at the end of each round, for any i 2 D the vector v is identical to m on all indices in S_i, i.e. v_Sim. If the extractor asks a \bad" query or a query that does not hit any new sets, i.e. c_w2 D for all w 2 [], then the size of D does not increase in this round. The query is \bad" with at most probability 1 and since each c_wis uniformly sampled from [k] the latter occurs with probability at most. Thus, by a union bound, in each round the size of D increases by 1 with probability at least 1 (1 +) =.

$$ A_{2} $$

$$ D\subset[n] $$

$$ |D|<\delta k $$

$$ c=(c_{1},...,c_{\lambda}) $$

$$ c_{w}\not\in D $$

$$ w\in\lambda $$

$$ c_{w} $$

$$ v_{S[j]}=m_{j}^{\prime}=m_{S[j]} $$

$$ \ {mathcal S[j]},j\in $$

$$ i\in D $$

$$ S_{i}. $$

$$ v\equiv_{S_{i}}m $$

$$ c_{w}\in D $$

$$ w\in[\lambda] $$

$$ c_{w} $$

$$ 1-\epsilon $$

$$ \delta^{\lambda} $$

$$ \ -\left(1-\epsilon+\mathring{\delta}^{\lambda}\right)=\epsilon-\mathring{\delta}^{\lambda} $$

Let r denote the total number of rounds, and let X_ifor 1 i r be an indicator random variable such that X_i= 1 if either jDj increases in the ith round or jDj k by the ith round. Above we established that Pr[Xⁱ= 1] p =. The size of D after r rounds is at least P P min( X_i;k). Thus it suces to establish that X_ik with probability at least 1 2. The variables X_iare not independent so we cannot immediately apply the Cherno-Hoeding bound. However due to the fact that Pr[X_i] p conditioned on any values of X₁;:::;X_{i 1}, if we dene independent 0/1 variables Z₁*;:::;Zrsuch that Pr[Zi= 1] = p for all i, then it follows that P P Pr[ Xⁱk] Pr[ Z_ik]. Finally, setting r (2k=p*) and the Cherno-Hoeding i _i P P₂ rp =2 bound then implies: Pr[ Zik] Pr[ Zirp=2] < 2e. Finally we can choose r i i such that rp²=2 + 1. Finally, to satisfy both conditions we set r max(2k=p; 2( + 1)=p²), 2 e.g. r = 2k( + 1)=p² = 2k( + 1)=().

$$ X_{i} $$

$$ X_{i}=1 $$

$$ 1\leq i\leq r $$

$$ |D|\geq\delta k $$

$$ P r[X_{i}=1]\succeq p=\epsilon-\delta^{\lambda} $$

$$ m i\ textstyle\sum(X_{i},\delta k) $$

$$ \sum X_{i}\geq\delta k $$

$$ 1-2^{-\lambda} $$

$$ X_{i} $$

$$ \ r[X_{i}]\geq p $$

$$ X_{1},...,X_{i-1} $$

$$ Z_{1},...,Z_{r} $$

$$ P r[Z_{i}=1]=p $$

$$ \textstyle\mathrm{}{P r}[\sum_{i}X_{i}:\leq:\delta k]:\leq:\mathrm{}{P r}[\sum_{i}Z_{i}:\leq:\delta k] $$

$$ r,\geq,(2\delta k/p) $$

$$ P r \left[ \sum_ {i} Z _ {i} \leq \delta k \right] \leq P r \left[ \sum_ {i} Z _ {i} \leq r p / 2 \right] < 2 e ^ {- r p ^ {2} / 2} $$

$$ r p^{2}/2\geq\lambda\ 1 $$

$$ r\geq m a x(2\delta k/p,2(\lambda+1)/p^{2}) $$

$$ r=2\delta k(\lambda+1)/p^{2}=2\delta k(\lambda+1)/(\epsilon-\delta^{\lambda})^{2} $$

A.5 Veriable Delay Encodings

A veriable delay encoding (VDE) is an encoding that is slow to compute yet fast to decode. 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 veriable delay function recently introduced in [14]. Practical (heuristic) examples of VDEs include Sloth [31], MiMC [4], and a special class of permutation polynomials [14].

Formally, a VDE is a tuple of three algorithms VDE = VDE.Setup*;VDE.Enc;*VDE.Dec dened as follows.

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. VDE.Setup might need secret randomness, leading to a scheme requiring a trusted setup.

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

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

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

$$ \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} $$

Correctness For all pp generated by VDE.Setup(;t) and all x 2X, algorithm VDE.Enc(pp;x) must run in parallel time t with poly(log(t);) processors, and VDE.Dec(pp; VDE.Enc(pp;x)) = x with probability 1.

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

$$ p p $$

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

$$ \mathrm{p o l y}(\log(t),\lambda) $$

Parallelism The practical signicance of allowing poly(log(t);) parallelism in VDE.Enc is that any implementation must have this much parallelism in order to evaluate within the delay time t. The security property of a VDE will bound the success probability of an adversary running in less than time t. If the construction demands VDE.Enc to use a signicant amount of parallelism to complete in a time t for which this sequentiality bound holds (i.e. the adversary cannot gain further speedup) then it may only be useful for applications where the \honest" evaluators have this much parallelism available. Constructions that do not require any parallelism to evaluate VDE.Enc in the optimal number of sequential steps are obviously superior. However, it is unlikely that such constructions exist (without trusted hardware). In fact, it is necessary that Y > poly(t) (otherwise the output can be guessed and checked quickly using VDE.Dec) and hence the challenge inputs have size poly log(t). Therefore, at a minimum we must allow up to poly log(t) parallelism. In practice, much of this parallelism may already be taken advantage of by the hardware (e.g. word sizes on modern processors and/or SIMD instructions).

$$ \ (\log(t),\lambda) $$

$$ \mathcal{Y}>\mathrm{p o l y}(t) $$

A.5.1 VDE security

The main security property of a VDE is-sequentiality, which characterizes that no adversary running in parallel time signicantly less than t is able to compute VDE.Enc on a random input 25 in X, even given preprocessing advice. This captures an unpredictability property given time constraints on the adversary.

Denition 19 (sequentiality). For a function (t) a VDE is-sequential if for any pair of randomized algorithms A₀, which runs in total time O(poly(t;)), and A₁, which runs in parallel time t (t) on at most O(poly(t)) processors, the following probability distribution over pp VDE.Setup(t;) is negligible:

$$ \sigma(t) $$

$$ \mathcal{A}_{0} $$

$$ O(p o l y(t,\lambda)) $$

$$ \mathcal{A}_{1} $$

$$ t-\sigma(t) $$

$$ O(p o l y(t)) $$

$$ p p\gets $$

$$ V E.S e t u p(t,\lambda) $$

$$ P r \left[ \begin{array}{c c} y \leftarrow \mathcal {A} _ {1} (\alpha , \mathbf {p p}, x) \ \wedge y = V D E. E n c (x) \end{array} \right| \begin{array}{c} x \leftarrow^ {\mathrm {R}} \mathcal {X} \ \alpha \leftarrow \mathcal {A} _ {0} (\lambda , \mathbf {p p}, t) \end{array} ] < n e g l (\lambda) $$

A second (stronger) property concerns the pseudorandomness of the output. Clearly the output of VDE.Enc on an input x is not indistinguishable from random as we can run VDE.Dec to recover the input, however we may want the property that Encode(pp;) is indistinguishable from a random permutation (if X = Y) for pp sampled from the setup, similar to modeling block ciphers as an ideal cipher. We formalize the ideal delay encoding object (for the special case of a permutation) as an oracle in the following denition.

$$ \mathcal{X}=\mathcal{Y}) $$

$$ (p p,\cdot) $$

²⁵ Asymptotically t must be subexponential in. The reason for this is that the adversary needs to be able to run in time at least t, and if t is exponential in then the adversary might be able to break the computational security underlying-sequentiality. Of course, if-sequentiality is somehow achieved unconditionally then this constraint no longer applies.

$$ ^, $$

(t) Denition 20. An ideal delay permutation (IDP) is a family of oracles fO g that implement IDP (t) a random permutation and respond to two types of queries. On a query (q; 0) the oracle O _IDP 1 internally simulates t sequential queries to and then outputs (q). On a query (q; 1) it 1 outputs (q).

$$ {\mathcal{O}_{I D P}^{(t)}} $$

$$ \mathcal{O}_{I D P}^{(t)} $$

$$ \Pi^{-1} $$

$$ \Pi^{-1}(q) $$

Indierentiability on random inputs One would hope to instantiate an IDP given ora- 1 cle access to a random permutation ,, and any o(1)-sequential VDE. A rst attempt would be the system C which rst samples pp VDE.Setup(t;) for suciently large and 1 then on input (q; 0) returns (q) = (VDE.Enc(pp;(q))) and on input (q; 1) returns (q) = ^{1 1} (t) (VDE.Dec(pp; (q))). We would further hope to argue that C is indierentiable from O ^IDP in ^the sense of Maurer et. al. [38]. Unfortunately, due to the fact that used in the construction is necessarily available to the adversary as well, the adversary can choose any value (say 0) and 1 query for x = (0), and then query C on input x. Since VDE is only necessarily sequential on random inputs the adversary may be able to nd an input x in this way that causes C to output (x) in signicantly fewer than t steps, which would enable it to distinguish C from ^(t) O. Nonetheless, it is still possible that indierentiability is achieved when the distinguisher IDP is restricted to random queries (and for applications that only make random queries this may be good enough).

$$ \Pi^{-1} $$

$$ o(1) $$

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

$$ (q,0) $$

$$ (q,1) $$

$$ \iota^{-1}(q)= $$

$$ \Pi^{-1}(\mathsf{V D E.D e c}(p p,\Pi^{-1}(q))) $$

$$ \mathcal{O}_{\mathsf{l D P}}^{(t)} $$

$$ x=\Pi^{-1}(0) $$

$$ \mathcal{O}_{\mathsf{l D P}}^{(t)} $$

A.6 Depth Robust Graphs

An (n;;;d) depth robust graph (DRG) is a directed acyclic graph G = (V;E) on n = jV j nodes with regular in-degree d that has the property that any subgraph of at least n nodes contains a path of length at least n. We dene the depth of a node v in a DRG, denoted depth(v), as the longest path from some other node w in the graph to v. Depth robust graphs thus have the property that any suciently large subgraph contains some node of high depth in that subgraph. In fact, we can show that suciently large subgraphs contain many nodes of high depth.

$$ G,=,(V,E) $$

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

$$ n=|V| $$

$$ \beta n $$

$$ d e p t h(v) $$

Claim 5. In any (n;;;d) DRG for constants ; < 1, every subgraph of size ( +)n nodes contains at least bnc nodes of depth at least n.

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

$$ \alpha,\beta<1 $$

$$ (\alpha+\delta)n $$

$$ \beta n $$

0 0 Proof. Let = +< 1. Consider any subgraph G₁ of size n. There exists a node v₁ 2 G₁ of depth n. Remove v₁ from G₁ to form the subgraph G₂. Continue this process, removing a node 0 v_iof depth n from the ith subgraph G_i, which can be found as long as jG_ij = n i n. This process locates a sequence of distinct nodes v₁:::;v_tall of depth at least n in G₁, where t = bnc.

$$ \alpha^{\prime}\ !=!\alpha!+!\delta<1 $$

$$ G_{1} $$

$$ \alpha^{\prime}n $$

$$ v_{1}\in G_{1} $$

$$ \beta n $$

$$ v_{1} $$

$$ G_{1} $$

$$ G_{2} $$

$$ v_{i} $$

$$ \beta n $$

$$ G_{i} $$

$$ |G_{i}|=\alpha^{\prime}n-i\geq\alpha n $$

$$ v_{1}...,v_{t} $$

$$ \beta n $$

$$ t=\lfloor\delta n\rfloor $$

$$ G_{1} $$

For example, if G is a (n;1=2; 1*=4;d*) DRG then at least 15% of the nodes in any subgraph on 50% of the nodes have depth at least *n=*10.

$$ (n,1/2,1/4,d) $$

$$ n/10 $$

A directed graph has B-bounded outdegree if the outdegree of any node is bounded by some integer B. Not that any DAG with regular in-degree d has average out-degree d, however it may not have bounded outdegree. Intuitively, any DRGs with regular in-degree should have bounded out-degree, as otherwise one could delete many edges by removing only several nodes of high degree, reducing the depth of the remaining subgraph substantially.

Depth robust graph constructions A classical construction by Erd}os, Graham, and Szemeredi [43] 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 [41], they are complex and have either large constant degree or only achieve the requisite expansion properties for a signicantly large number of nodes. Mahmoody, Moran, and Vadhan [36] 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. Alwen et. al. [6] recently improved the EGS construction to obtain DRGs for arbitrary*;* as well and O(logn) degree (an asymptotic improvement over MMV), however all of these constructions still require concretely high degree due to their use of bipartite expander graphs with extreme expansion properties.

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

$$ \alpha,=,0.99 $$

$$ \beta=0.1 $$

$$ n. $$

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

$$ \epsilon<1 $$

$$ \alpha<1 $$

$$ \alpha,\beta $$

A probabilistic DRG construction compromises on explicitness, and instead outputs a graph that is a DRG with overwhelming probability. This allows for much more ecient constructions. For example, one can immediately replace the bipartite expander graphs in the MMV/EGS constructions with random bipartite graphs, which are known to have strong expansion properties with high probability. Recently, Alwen et. al. [5] proposed and analyzed a highly ecient probabilistic DRG sampling algorithm that outputs concretely low-degree DRGs on n nodes with with failure probability negligible in n.

Another useful property of the ABH probabilistic DRG construction is that they are locally navigatable. That is, it outputs a graph equipped with an ecient parent function to derive the parents of any node in the graph using polylog time and space. A probabilistic instantiation of MMV with random bipartite graphs would also have this property. This is a critical property that we take advantage of in our construction as it allows our prover and verier to interactively agree on a freshly sampled DRG with only O(1) communication and O(polylog(n)) computation/space on the verier.

Denition 21. 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)\ {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].

$$ 1.\ D R G.S a m p l n,\sigma)\rightarrow 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;).

$$ \ n,\sigma,i\rightarrow\mathcal{P} $$

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

$$ i\in[n] $$

$$ \ {mathcal G_{{sigmasigma}}}leftarrow D D D.S a m p l e(n,{sigma}) $$

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.

$$ 0(n\log n) $$

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

$$ (n, \alpha , \beta , d) - D R G $$

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

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

In practice, the s-bit size of size O(nlogn) can be derived pseudorandomly from a much smaller seed of size O() given a strong pseudorandom number generator (PRNG) with security parameter, or a random oracle. As n is presumed to be of feasible size, i.e. O(poly()), we do not require PRNGs with exponential stretch and thus cryptographic PRGs built from any one-way function suce.

$$ O(n\log n) $$

$$ \lambda, $$

A.7 Proofs of Space

A proof of space (PoS) [24] is an interactive proof between and prover and verier that demonstrates the prover is storing an advice string of a minimum size. The framework for proofs of space inherently requires a computational resource bound on the adversary. PoS constructions are built from puzzles that have time/space tradeos, and the PoS guarantees that an adversary who has not stored advice of a sucient length will require computation exceeding this bound in order to pass the interactive proof. If the time/space tradeo holds in the parallel computation model (i.e. passing the verier’s challenge with too few bits of advice is sequentially hard) then security can be enforced unconditionally by forcing the prover to respond to the verier within a time bound.

We present here a slight variant on the PoS denition from [24] that additionally incorporates a data input D. This is a blend of the storage enforcing commitment concept and PoS. The PoS interactive protocol involves two phases and a setup procedure.

Setup The setup runs on security parameters and outputs public parameters pp for the scheme. The public parameters are implicit inputs to the next two protocols.

Initialization is an interactive protocol between a prover P and verier V that run on shared input (id;N) and P is additionally given data D. P outputs and S, where S is its storage advice and is a compact O(polylog(N)) string given to the verier.

Execution is an interactive protocol between P and V where P runs on input S and V runs on input . V sends challenges to P, obtains back a proof, and outputs accept or reject.

Eciency, Completeness, and Soundness PoS protocols are required to have ecient verication, namely the verier should run in time O(polylog(N)). The PoS protocol has perfect completeness if the verier always outputs accept in interaction with an honest prover with probability 1 over the randomness of both parties. The PoS protocol is (s;t;)-sound if any adversarial prover P that runs in time complexity at most t and storage at most s during Execution, where s = jSj N, passes verication with probability at most = negl(). We may also express that the protocol is parallel (s;t;)-sound if the time bound t is in parallel time (e.g. circuit depth, PRAM complexity, or parallel rounds of queries to an oracle). In either case there is no time bound on P’s running time during Initialization, other than O(poly()) when the scheme’s security depends on computational assumptions about the setup parameters. We additionally say the PoS is data committing if the output is a binding cryptographic commitment (not necessarily hiding) to the data input D.

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

$$ (s,t,\mu) $$

$$ P^{*} $$

$$ s=|S|,N,\leq,N $$

$$ \mu={\mathsf{n e g l}}(\lambda) $$

$$ (s,t,\mu) $$

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

Tight security and the space gap The space gap in a PoS is the fraction = (N s)=N. This captures the dierence between the (persistent) space utilization of the best possible attack and the honest prover’s storage. A PoS with a tighter lower bound on the adversarial prover’s space (persistent storage) will have a smaller space gap. As the best possible attack is probably not known, a PoS protocol with a larger space gap has a weaker security guarantee. Nearly all known PoS protocols to date have considerably large space gaps.

$$ \epsilon=(N-s)/N $$

1 The original PoS of Dziembowski et. al. [24] leaves a space gap of at least 1. The ⁵¹² construction of Ren and Devadas from stacked bipartite expander graphs made dramatic improvements, but still leaves space gap of at least 1*=*2 (and much larger with practical parameters,

$$ 1-{\frac{1}{512}} $$ e.g. their construction requires at least degree 40 graphs to achieve a space gap of less than 2*=*3). This appears fundamental to the construction, which is also not secure against parallel attacks, rather than a gap in the analysis. The recent proofs of space based on function tables²⁶ [3] has 1 an enormous (even asymptotic) space gap of ¹. ^{64 logN}

$$ 1-{\frac{1}{64\log N}} $$

Most recently, Pietrzak constructed an asymptotically tight PoS relying on a strong property of the EGS depth robust graphs that was also recently proven [6]. This property (which is stronger than normal depth robustness) is that for any arbitrarily small a graph G on N nodes with degree O(log N=) can be constructed such that if any fraction of nodes are removed the remaining nodes contain a path of length such that + < 1. Using a graph with this property, Pietrzak’s PoS then achieves a space gap of 4 . However, the construction relies on bipartite graphs with extreme expansion called-local expanders²⁷ where < = 4, and the nal graph has degree at least 10c logN where c is the degree of the-local expander. Concretely, even the best known non-explicit randomized construction of a-expander (e.g. Chung’s expander, which dene edges by a random permutation [18]) would require degree greater than 40 for = 1*=2 and degree greater than 276 for = 1=8. To achieve just an 1=2 space gap would thus require a graph with degree d = 2;760 logN*. Even for 10-bit security the 28 proof size would be at least 26MB!

$$ G_{\epsilon} $$

$$ \beta $$

$$ \alpha+\beta<1-\epsilon $$

$$ \delta<\epsilon/4 $$

$$ 10c_{\delta} $$

$$ c\delta $$

$$ \epsilon=1/2 $$

$$ \epsilon=1/8 $$

$$ 1/2 $$

A.8 Graph pebbling games

Pebbling games are the main analytical tool used in graph-based proofs of space and memory hard functions.

Black pebbling game The black pebbling game is a single-player game on a DAG G = (V;E). At the start of the game the player chooses a starting conguration of P₀ V of vertices that contain black pebbles. The game then proceeds in rounds where in each round the player may place a black pebble on a vertex only if all of its parent vertices currently contain pebbles placed in some prior round. In this case we say that the vertex is available. Placing a pebble constitutes a move, whereas placing pebbles on all simultaneously available vertices consumes a round. The adversary may also remove any black pebble at any point. The game stops once the adversary has placed pebbles on all vertices in some target/challenge set V_CV.

$$ \mathcal{G}=(V,E) $$

$$ P_{0}\subseteq V $$

$$ V_{C}\subseteq V $$

Pebbling complexity There are dierent pebbling complexity measures taking into account how many rounds, steps, and/or pebbles are needed to nish the game from any given starting conguration. We say that the pebbling game on graph G with vertex set V and target set V_CV is (s;t)-hard if no player can pebble the set V_Cin t moves (or fewer) starting from s initial pebbles, and is (s;t)-parallel-hard if no player can complete the pebbling in t rounds (or fewer) starting from an initial conguration of at most s pebbles. These are the two measures we are most interested in. If the hardness holds for any subset containing an fraction of V_Cthen we write that the pebbling game on (G;V_C) is (s;t;)-(parallel)-hard. From a xed starting

$$ V_{C}\subseteq V $$

$$ (s,t) $$

$$ V_{C} $$

$$ (G,V_{C}) $$

26 These are the proofs of space that are being deployed by Chia Network, https://chia.net/.

²⁷ Bipartite-local expanders require the property that there is an edge between any fraction of sinks and fraction of sources.

$$ \delta $$

²⁸ 30 The proof size is at least O(d), so even for = 10 (i.e. 10 bit security) and N = 2 (i.e. a 32GB PoS because each node is a 32 bytes value) the proof size would be at least 26MB. Furthermore, as decreases = O(1*=) to maintain the same security level. To achieve a space gap of 1=10 with 10-bit security would require d = 19;310 logN* and = 60 for a proof size of at least 1GB.

$$ O(\lambda d) $$

$$ N=2^{30} $$

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

$$ \lambda=60 $$ conguration P₀ the number of parallel rounds required to pebble all nodes in the set V_Cis equal to the maximum number of parallel rounds requires to pebble any individual v 2 V_C.

$$ P_{0} $$

$$ V_{C} $$

Random pebbling games are also considered, where a challenge node is sampled randomly from V_Cafter the player commits to the initial conguration P₀ of s vertices, and the hardness measure includes the adversary’s probability of success. The random pebbling game is (s;t;)- (parallel)-hard if from any s xed initial pebbles the probability that a uniformly sampled challenge node can be pebbled in t or fewer moves (resp. t or fewer rounds) is less than. There is also a general correspondence between the parallel hardness of random and deterministic pebbling games on a given graph.

$$ v\in V_{C} $$

$$ V_{C} $$

$$ P_{0} $$

$$ (s,t,\epsilon). $$

Claim 6. The random pebbling game on a DAG G on n nodes with target set V_Cis (s;t;)- parallel-hard if and only if the deterministic pebbling game on G with target set V_Cis (s;t;)- parallel-hard.

$$ V_{C} $$

$$ (s,t,\alpha)\cdot $$

$$ V_{C} $$

$$ (s,t,\alpha) $$

Proof. Fix any P₀ of size s. If the random pebbling game on G with target set V_Cis (s;t;)- parallel-hard then less than an fraction of the nodes in V_Ccan be pebbled individually in t rounds starting from P₀. Therefore, every subset U in V_Cof size jV_Cj contains at least one node that cannot be pebbled individually in t rounds, hence the (deterministic) pebbling game is (s;t;)-parallel-hard. Conversely, if G is (s;t;)-parallel-hard then less than an fraction of nodes in V_Ccan be pebbled individually in r rounds. Otherwise, these nodes form a subset U of size jV_Cj and they can all be simultaneously pebbled in parallel in t rounds. This implies that the probability a randomly sampled node from V_Ccan be pebbled in t rounds is less than .

$$ P_{0} $$

$$ G $$

$$ V_{C} $$

$$ V_{C} $$

$$ (s,t,\alpha). $$

$$ P_{0} $$

$$ V_{C} $$

$$ \alpha|V_{C}| $$

$$ (s,t,\alpha) $$

$$ (s,t,\alpha) $$

$$ V_{C} $$

$$ \alpha|V_{C}| $$

$$ V_{C} $$

$$ \alpha $$

Claim 7. A random pebbling game with a single challenge is (s;t;)-parallel-hard if and only k if the the random pebbling with challenges is (s;t;)-parallel-hard.

$$ (s,t,\alpha) $$

$$ (s,t,\alpha^{k}) $$

Proof. If the random pebbling game is (s;t;) hard then by Claim6the deterministic pebbling game is (s;r;) hard, hence there are at most an fraction of the nodes in V_Cthat can be pebbled in r rounds from s initial pebbles. The probability that independent random challenges are all nodes from this fraction is at most. Conversely, if the random pebbling game is not (s;t;) hard then the adversary can pebble all the challenges simultaneously in parallel time t succeeding on each challenge individually with probability greater than, hence succeeding on all the challenges with probability greater that.

$$ (s,t,\alpha) $$

$$ (s,r,\alpha) $$

$$ V_{C} $$

$$ \alpha $$

$$ \alpha^{\kappa} $$

$$ (s,t,\alpha_{t}^{\circ} $$

$$ \alpha. $$

$$ \alpha^{\kappa} $$

From pebbling to graph labeling A labeling game on a degree d DAG G is analogous to the pebbling game except that the pebbling rules are \enforced" using a cryptographic hash function dm m H : f0*;* 1g!f0*;* 1g, often ^modeled as a random oracle. The vertices of the graph are indexed in [n] and each ith vertex associated with the label c_iwhere c_i= H(i) if i is a source vertex, or otherwise c_i= H(ijj‘_parents(i)) where ‘_parents(i) = fc_v1;:::;c_vg if v₁;:::;v_dare the parents of the d ith vertex, i.e. the vertices with a directed edge to vertex i. The game ends when the player has computed all the labels on a target/challenge set of vertices V_C. A \fresh" labeling of G could be derived by choosing a salt id for the hash function so that H_id(x) = H(idjjx), and the labeling may be associated with the identier id. The complexity of the labeling game (on a fresh identier id) is measured analogously to the pebbling game, but in terms of queries to the hash function instead of pebbles. This includes the number of labels initially stored, the total number of queries, and the total rounds of sequential queries, etc. The labeling game is

$$ \mathcal{G} $$

$$ H:{0,1}^{d m}\rightarrow{0,1}^{m} $$

$$ c i_{i} $$

$$ c_{i}=H(i) $$

$$ c_{i}=H(i||\ell_{\mathsf{p a r e n t s}}(i)) $$

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

$$ v_{1},...,v_{d} $$

$$ V_{C} $$

$$ \mathcal{G} $$

$$ H_{i d}(x)=H(i d||x) $$

$$ i d) $$

(s;r;q;;)-labeling-hard if no algorithm that stores initial advice of size s and after receiving a uniform random challenge node v 2 [n] makes a total of q queries to H in r sequential rounds can output the correct label on v with probability greater than over the challenge v and over the random oracle H.

$$ (s,r,q,\epsilon,\delta) $$

$$ v\in[n] $$

Random oracle query complexity While the pebbling complexity of the underlying graph G provides strong intuition about the query complexity of the labeling game, proving this equivalence is highly non-trivial. The \ex post facto" technique of [20] allows one to prove this when the initial conguration of pebbles is empty and the target set V_Cis chosen deterministically. Progress towards a general correspondence was made in [29,45]. In particular, Pietrzak [45] showed an equivalence between the parallel hardness of the randomized pebbling game and the parallel hardness of the random oracle labeling game for arbitrary initial congurations S₀. Demonstrating (or refuting) an equivalence for the non-parallel hardness of the two games is still open.

$$ \delta $$

$$ V_{C} $$

$$ S_{0} $$

Theorem 4 (Pietrzak [45]). If the random pebbling game on a DAG G with n nodes and in- md degree d is (s;r;)-parallel-hard then the labeling game on G with a random oracle H : f0*;* 1g! ^m f0*;* 1g is (s⁰;r;;;q)-labeling-hard with s⁰ = s(m 2(logn + logq)) log(1*=).*

$$ (s,r,\epsilon) $$

$$ H:{0,1}^{m d}\rightarrow $$

$$ {0,1}^{m};i s;(s^{\prime},r,\epsilon,\delta,q) $$

$$ s^{\prime}=s(m-2(\log n+\log q))-\log(1/\delta) $$

Generic PoS from graph labeling game Most PoS constructions are based on the graph labeling game [24,45,46]. Let G( ) be a family of d-in-regular DAGs such that G_n G (n) is a d-in-regular DAG on N > n nodes and V_C(n) is a subset of n nodes from G_n. Let H : dm m f0*;* 1g!f0*;* 1g be a collision-resistant hash function (or random oracle). Let Chal(n) denote a distribution over [N] . For each n 2 N, the generic PoS based on the labeling game with G_n and target set V_C(n) is as follows:

$$ \mathcal{G}(\cdot) $$

$$ G_{n},\leftarrow,\ {mathcal G G}(n) $$

$$ N>n $$

$$ V_{C}(n) $$

$$ G_{n} $$

$$ H $$

$$ {0,1}^{d m}\to{0,1}^{m} $$

$$ [N]^{\lambda} $$

$$ n\in\mathbb{N} $$

$$ G_{n} $$

$$ V_{C}(n) $$

1. Initialization: The prover plays the labeling game on G_nusing a hash function H salted with the proof identier id, i.e. H_id= H(idjj). While computing the labels on all nodes of G, the prover adds these to a vector commitment (e.g. Merkle tree) denoted com. Then R it derives non-interactive challenges by sampling a vector ~c Chal(n) using as a seed H_id(com). For each of the challenges c₁;:::;c, the prover opens the label on the c_ith node of G_n, which was committed in com, as well as the labels of all its parent nodes. The labels are added to a list L with corresponding opening proofs in a list and the prover outputs the non-interactive proof = (com;L;). A verier (at any point in time) accepts if it successfully veries the openings with respect to com and also that for each challenge (v) (v) v 2 [N] with corresponding ‘^vand purported parent labels ‘;:::;‘ liste^d in L that 1 d (v) (v) ‘_v= H_id(vjj‘ jjjj‘₎. Finally, the prover stores as S only the n labels in V_C. 1 d

$$ G_{n} $$

$$ i d, $$

$$ \mathcal{G} $$

$$ H_{i d}=H(i d||\cdot) $$

$$ {\vec{c}}\xleftarrow{\mathsf{R{}a l l}}(n) $$

$$ H_{i d}(c o m) $$

$$ c_{1},...,c_{\lambda} $$

$$ c_{i} $$

$$ G_{n} $$

$$ \Phi=(c o m,L,\Lambda) $$

$$ v\in[N] $$

$$ \ell_{1}^{(v)},...,\ell_{d}^{(v)} $$

$$ \ell_{v} $$

$$ \ell_{v}=H_{i d}(v||\ell_{1}^{(v)}||\cdots||\ell_{d}^{(v),} $$

$$ V_{C} $$

2. Execution: The verier selects challenge nodes v₁;:::;v uniformly at random from V_C. The online prover uses its input S to respond with the label on v and an opening of com at the appropriate index.

$$ v_{1},...,v_{\kappa} $$

$$ V_{C} $$

Roughly, the generic construction is a PoS when the pebbling game on G and V_Cis \hard" in some pebbling complexity sense. Our security analysis will focus on parallel pebbling complexity as this is a stronger security notion, particularly considering its general correspondence to the parallel hardness of the labeling game in the random oracle model.

$$ V_{C} $$

Red-black pebbling game The soundness of the generic labeling PoS is a bit more nuanced than just the parallel hardness of the black pebbling game on G with V_C. It is best abstracted through the red-black pebbling game, where red pebbles correspond to incorrect labels that the adversary computes and includes in its commitment during Initialization (i.e. where the adversary cheats). We may assume without loss of generality that whenever the adversary cheats it generates some label that does not require any space to store, essentially placing a \free" pebble on this node. Naturally, by committing to the labels the adversary commits to all these red pebbles during Initialization. The adversary’s choice of red pebble placements is also constrained by the non-interactive challenges, which may catch these red pebbles and reveal them to the verier. The formal description of the red-black pebbling security game for a graph labeling PoS construction with G(n), V_C(n), and Chal(n) is as follows.

$$ \mathcal{G} $$

$$ V_{C} $$

$$ \lambda $$

$$ \mathsf{R e c l-B I a c k-P e b b l e s}^{\mathcal{A}}(\mathcal{G},\mathit{V}_{C},\mathsf{C h a l},t)\colon $$

1. A outputs a set R [N] (of red pebble indices) and S [N] (of black pebble indices).

$$ R\subseteq[N] $$

$$ S subseteqsubseteq[N] $$

R 2.The challenger samples c₁;:::;c Chal(n). If c_i2 R for some i then A immediately loses. The challenger additionally samples v₁;::::;v uniformly at random from indices in V_C(n) and sends these to A.

$$ c_{1},...,c_{\lambda}\xleftarrow{\mathsf{R h a l}}(n) $$

$$ c_{i}\in R $$

$$ v_{1},...,v_{\kappa} $$

$$ V_{C}(n) $$

3. A plays the random (black) pebbling game on G(n) with the challenges v₁;:::;v and initial pebble conguration P₀ = R[S. It runs for t parallel rounds and outputs its nal pebble conguration P_t. A wins if P_tcontains pebbles on all of v₁;:::;v.

$$ \mathcal{G}(n) $$

$$ v_{1},...,v_{\kappa} $$

$$ P_{0}=R\cup S $$

$$ P_{t.~\mathcal{A}} $$

$$ P_{t} $$

$$ v_{1},...,v_{\kappa}. $$

Although we have been loosely referencing PoS (S;T)-soundness, we now formally dene this for the special case of any graph labeling PoS in terms of complexity of Red-Black- A Pebbles (G;V_C;t). Let c : N*! N* denote a cost function c : N*!* N representing the parallel time cost (e.g. in sequential steps on a PRAM machine) of computing a label on a node of G(n) for each n 2 N.

$$ \mathsf{P e b b l e s}^{\mathcal{A}}(\mathcal{G},V_{C},t) $$

$$ c:\mathbb{N}\to\mathcal{N} $$

$$ c:\mathbb{N}\rightarrow\mathbb{N} $$

$$ n\in\mathbb{N} $$

Denition 22. A graph labeling PoS with G(n);V_C(n); Chal(n) and cost function c(n) is parallel A (s;c(n) t;)-sound if and only if the probability that any A wins Red-Black-Pebbles (G;V_C; Chal;t) is bounded by where jSj = s.

$$ \mathcal{G}(n),V_{C}(n),C h a l(n) $$

$$ c(n) $$

$$ (s,c(n){\cdot}t,\mu) $$

$$ |S|=s $$

Composition For the security of several graph labeling games to compose the independent instances of the games must involve either independent labelings or independent hash function. This is the function of id in the generic PoS construction from a graph labeling, which species a fresh hash function H_id. In the random oracle model this is represented as a freshly sampled random function. When this is the case the composition of k independent games is equivalent to a single game on a large graph containing k distinctly labeled copies of the graph, where the new distribution of Chal is a k fold direct product.

$$ H_{i d} $$

Denition 23. An (s;c(n) t;)-sound graph labeling PoS with G(n);V_C(n); Chal(n) and cost function c(n) is secure under k-fold composition if and only if the graph labeling PoS with G (n);V (n); Chal (n) is (sk;c(n) t;)-sound, where G (n) consists of k copies of G(n), V (n) ^C C is the union of the images of V_C(n) in each copy, and Chal (n) is the direct product distribution Chal₁(n) Chal_k(n) where each Chal_i(n) is the distribution Chal(n) projected onto the ith copy of the graph.

$$ (s,c(n)\cdot t,\mu) $$

$$ c(n) $$

$$ \mathcal{G}(n),V_{C}(n),C h a l(n) $$

$$ \mathcal{G}^{}(n),V_{\mathcal{C}}^{}(n),\mathcal{C}h a^{*}(n) $$

$$ (s k,c(n)\cdot t,\mu) $$

$$ {mathcal G^{{*}}}(n) $$

$$ V_{C}(n) $$

$$ \mathcal{G}(n),,V_{C}^{*}(n) $$

$$ C h a l_{1}(n)\times\cdots\times C h a l_{k}(n) $$

$$ C h a l_{i}(n) $$

Uniform challenges In the special case that Chal is the uniform distribution over [N] then A the hardness of Red-Black-Pebbles (G;V_C;Chal;t) is simply implied by the hardness of the random black pebbling game.

$$ [N]^{\lambda} $$

$$ \mathsf{R e d l-B l a c k-P e b b l e s}^{\mathcal{A}}(\mathcal{G},V_{C},\mathsf{C h a l},t) $$

Claim 8. If the random black pebbling game on G(n) is (( +)n;t;)-parallel-hard and Chal is the uniform distribution over [N] then the graph labeling PoS with G(n), V_C(n), and c(n) is (n;c(n) t;max((1);))-sound.

$$ \mathcal{G}(n) $$

$$ ((\gamma+\delta)n,t,\mu) $$

$$ [N]^{\lambda} $$

$$ c(n) $$

$$ (\gamma n,\mathit c(n)\cdot\mathit t,a x((1-\delta)^{\lambda},\mu\kappa\mathit))\ \ \ s s o n c $$

A Proof. The challenges ensure that that A wins the game Red-Black-Pebbles (G;V_C;Chal;t) with probability at most (1) if the number of red pebbles (i.e. jRj) exceeds N. If jRj N and jSj N, then the adversary plays the random black pebbling game with challenges and an initial conguration of at most ( +)N pebbles. If the random black pebbling game (with a single challenge) is (( +)N;t;)-parallel-hard then A succeeds in playing this game with simultaneous challenges (Step 3) with probability at most (by Claim7). Therefore, if the random black pebbling game is hard then the adversary’s overall success probability is bounded by the maximum of its success probability in the two cases regarding the size of R, i.e. max(;(1) ).

$$ \mathsf{P e b b l e s}^{\mathcal{A}}(\mathcal{G},V_{C},\mathsf{C h a l},t) $$

$$ (1-\delta)^{\lambda} $$

$$ (\mathrm{i.e.~}|R|) $$

$$ \ cdot R R|\leq\delta N $$

$$ \vert S\rightvert\leq\gamma N $$

$$ (\gamma+\delta)N $$

$$ ((\gamma+\delta)N,t,\mu) $$

$$ \mathcal{A} $$

$$ \mu^{\kappa} $$

$$ (\mu^{\kappa},(1-\delta)^{\lambda}) $$

In this case we can also make a simple claim about the composition of a graph labeling PoS where Chal is the uniform distribution. It follows from a general claim pertaining a graph G(n) that is the composition of k subgraphs G₁(n);:::; G_k(n) which all have the same random black pebbling complexity and Chal samples challenges from the uniform distribution on each.

$$ \mathcal{G}(n) $$

$$ \mathcal{G}{1}(n),...,\mathcal{G}{k}(n) $$

Claim 9. If G(n) contains subgraphs G₁(n);:::; G_k(n) and for each i the random black pebbling game on G_i(n) is (( +)n;t;)-parallel-hard and Chal = Chal₁ Chal_kwhere Chal_iis the uniform distribution over the indices of the nodes contained in G_ithen the graph labeling PoS with G(n), V_C(n), and c(n) is (kn;c(n) t;max((1);))-sound.

$$ \mathcal{G}(n) $$

$$ \mathcal{G}{1}(n),...,\mathcal{G}{k}(n) $$

$$ \mathcal{G}_{i}(n) $$

$$ ((\gamma+\delta)n,t,\mu) $$

$$ C h a l=C h a l_{1}\times\cdots\times C h a l_{k} $$

$$ \mathcal{G}_{i} $$

$$ c(n) $$

$$ \big(k\gamma n,c(n)\cdot t,m a x\big((1-\delta)^{\lambda},\mu^{\kappa}\big), $$

Proof. The challenges sampled from each Chal_iensure that that A wins the game Red-Black- A Pebbles (G;V_C;Chal;t) with probability at most (1) if the number of red pebbles exceeds N in any subgraph Gi. Suppose there areiN black pebbles initially on each Giand at most N P red pebbles (total of_iinitial black pebbles overall. The adversary plays the random black i pebbling game with challenges on each G_iwith an initial conguration of at most (_i+)N pebbles. Since the random black pebbling game on each G_iis (( +)N;t;)-parallel-hard then A succeeds in playing this game with simultaneous challenges (Step 3) with probability at most ifi< . The probability A succeeds in all the k games is bounded by the minimum of its success probabilities in each, hence its overall success probability is at most ifi< for P any i, i.e. ifi< k. Therefore, if the total number of initial pebbles is less than k then i the adversary’s overall success probability is bounded by max(;(1) ).

$$ \mathsf{P e b b l e s}^{\mathcal{A}}(\mathcal{G},V_{C},\mathsf{C h a l},t) $$

$$ (1-\delta)^{\lambda} $$

$$ \delta N $$

$$ \delta N $$

$$ \mathcal{G}_{i} $$

$$ \gamma_{i}N $$

$$ \mathcal{G}_{i} $$

$$ \sum_{i}\gamma_{i} $$

$$ (\gamma_{i}+\delta)N $$

$$ \mathcal{G}_{i} $$

$$ \ _{i} $$

$$ ((\gamma+\delta)N,t,\mu) $$

$$ \mathcal{A} $$

$$ \mu^{\kappa} $$

$$ \gamma_{i}<\gamma $$

$$ \mu^ {\kappa} \mathrm {i f} \gamma_ {i} < \gamma $$

$$ \textstyle\sum_{i}\gamma_{i},<,k\gamma $$

$$ k\gamma $$

$$ (\mu^{\kappa},(1-\delta)^{\lambda}) $$

Pebbling DRGs We now state several facts regarding the pebbling complexity of a depth robust graph.

Claim 10. If G is a (n;;)-depth-robust DAG then pebbling any n initially unpebbled nodes requires at least n rounds.

$$ a\left(n,\alpha,\beta\right) $$

Proof. A subgraph of unpebbled n nodes contains a path P of length n. To pebble the entire set of unpebbled n nodes requires sequentially pebbling all the n nodes along the path P.

$$ \beta n. $$

Claim 11. For any < < 1, the random black pebbling game on an (n;;)-depth-robust DAG G is (()n;n 1*;)-parallel-hard.*

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

$$ \alpha,<,\mu<,1 $$

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

Proof. Consider any > . If ()n black pebbles are placed anywhere on the graph then at least (1 +)n nodes are missing pebbles. Any subset of n nodes of the graph therefore include at least n nodes that are missing pebbles. By Claim10these subsets require at least n rounds to pebble. This means that the pebbling game on G is (()n;n 1*;*)-parallel-hard. The random pebbling game on G is equivalently hard by Claim6.

$$ \mu>\alpha $$

$$ (\mu-\alpha)n $$

$$ \mu n $$

$$ (1+\alpha-\mu)n $$

$$ \beta n $$

$$ ((\mu!-!\alpha)n,\beta n!-!1,\mu) $$

PoS from DRGs The claims established thus far imply PoS soundness of the generic graph labeling PoS on a graph G that is (n;;;d) depth robust, with challenge set V_C= [n], and where Chal is the uniform distribution over [n] . By Claim8and Claim11, this PoS is (( )n;c(n) (n 1);max((1);))-sound for any > +. In particular, setting = and = 1, the PoS is ((1 2 )n;c(n) (n 1);(1) )-sound. As can be made arbitrarily small for an increase in, the space gap of this PoS is approximately. Theoretically, there are DRG constructions that achieve arbitrarily small which would seem to imply tight space-hardness. However, this space-hardness is not really tight as decreasing decreases the space gap but also reduces the time bound t = n).

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

$$ V_{C}=[n] $$

$$ [n]^{\lambda} $$

$$ \alpha-\hat{\delta})n,c(n)\cdot(\beta n\eta-1) $$

$$ ((\mu- $$

$$ \left(\left(1 - \delta\right) ^ {\lambda}, \mu^ {\kappa}\right)) $$

$$ \mu>\alpha+\delta $$

$$ \kappa=\lambda $$

$$ \mu=1-\delta $$

$$ ((1-\alpha-2\delta)n,c(n)\cdot(\beta n-1),(1-\delta)^{\lambda}) $$

$$ \delta $$

$$ \lambda, $$

$$ \alpha $$

$$ t=\beta n, $$

Lemma 4. The graph labeling PoS on a family G(n) of (n;;) depth robust graphs with labeling cost function c(n) is an (s;t;)-parallel-sound PoS where for any < 1:

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

$$ c(n) $$

$$ \delta<1 $$

$$ s=\gamma n\qquad\iota=c(n)(\beta n-1)\qquad\mu=m a x((1-\delta)^{\lambda},(\alpha+\delta+\gamma)^{\kappa}) $$

The composition of k independent graph labeling PoS protocols on this family of depth robust graphs is a (k s;t;)-parallel-sound PoS.

$$ a\left(k\cdot s,t,\mu\right){\cdot}p a r a l l e l-80u n d P_{0}S $$

Proof. As described above, this follows from Claim8and Claim11, setting =. Composition follows from Claim9because this is equivalent to a graph labeling PoS on G (n) that is the concatenation of k copies of G(n) and Chal = Chal₁ Chal_kwhere each Chal_iis the uniform distribution over [i n;(i + 1)n) .

$$ \gamma = \mu - \alpha - \delta $$

$$ G^{*}(n) $$

$$ G(n) $$

$$ {\mathsf{C h a l}}={\mathsf{C h a l}}{1}\times\cdots{\mathsf{C h a l}}{k} $$

$$ \ \mathrm{C h l l}_{i} $$

$$ [i\cdot n,(i+1)n)^{\lambda} $$