Proof of Replication

Technical Report (WIP)

Juan Benet1 David Dalrymple Nicola Greco1

Protocol Labs

July 27, 2017

Abstract

We introduce Proof-of-Replication (PoRep), a new kind of Proof-of-Storage, that can be used to prove that some data D has been replicated to its own uniquely dedicated physical storage. Enforcing unique physical copies enables a verifier to check that a prover is not deduplicating multiple copies of D into the same storage space. This construction is particularly useful in Cloud Computing and Decentralized Storage Networks, which must be transparently verifiable, resistant to Sybil attacks, and unfriendly to outsourcing.

This work (a) reviews Proofs-of-Storage and motivates use cases; (b) defines the novel Proofs-of-Replication, which can be publicly verifiable, transparent, authenticated, and time-bounded; (c) shows how to chain Proofs-of-Replication to establish useful Proofs-of-Spacetime.

1 Motivation and Background on Proofs-of-Storage

This section provides backgrounds and classifications of different Proofs-of-Storage and related proofs, and motivates the need for Proofs-of-Replication. Throughout this section, we explain the distinction between different proofs using a prover, P, that is attempting to convince a verifier, V, that P is storing some data, D. V issues a challenge, c, to P who answers it with a corresponding proof c , according to the scheme in question. Proof schemes vary in their properties, their utility, and in whether D is useful outside the protocol or is a random string with no external utility.

1.1 Common Properties

We use the following properties, common to various proving schemes:

• (Privately Verifiable) A scheme is privately verifiable if V is a user with a secret verifying key generated during setup, or any other party that shares such secret key with the user. These schemes are useful in Cloud Computing settings, where users wish to outsource storage of data to servers and perhaps outsource verifying to a trusted verifier. As of this work, most Proof-of-Storage (PoS) schemes are privately verifiable.

• (Publicly Verifiable) A scheme is publicly verifiable if V can be any party with access to public data (e.g., a verifying key), but no access to the original data, or secret information generated during scheme setup. Publicly verifiable schemes are very useful in Decentralized Storage Network settings, where a verifier may be new participants who have access only to public data as context of previous proof scheme setups.

• (Transparent) A scheme is transparent if there is no extra information, sk, that enables any P to generate a valid proof without having data, D. This means that there is no sk with which a malicious prover can generate proof π* = ForgeProof(c, sk) such that 1 = Verify(c, π*) for a P-chosen c. Transparent schemes are necessary in Decentralized Storage Networks, where provers may also be verifiers or users.

• (Retrievability) A scheme supports retrieval if it is possible for V to extract and reconstruct D merely by issuing many challenges c to P and aggregating corresponding proofs π*.

• (Dynamic) A PoS scheme is dynamic if it enables the user V to dynamically update data D to D' stored at server P, to support mutable data without requiring a completely new setup.

• (Non-Outsourceable) A scheme is non-outsourceable if P cannot outsource her work to some other prover P* (e.g., storage, work, or proof-generation) and convince V that P did the work.

• (Authenticated) A scheme is authenticated if the identity of a prover can be verified during a proof verification. For example, a digital signature might be required as part of generating π* to prove identity, pk_i.

• (Time-Bounded) A proving scheme is time-bounded if a proof is only valid during a span of time.

• (Useful) A scheme is useful if it can achieve separate useful work or useful storage as part of its operation or as a side effect.

1.2 Kinds of Proofs

Here we give an overview of various kinds of proving schemes, in particular Proofs-of-Storage and its variants:

• Provable Data Possession (PDP) schemes allow user V to send data D to server P, and later V can repeatedly check whether P is still storing D.

• Proof-of-Retrievability (PoRet) schemes are similar to PDPs, but also enable extracting D.

• Proof-of-Storage (PoS) schemes allow a user V to outsource the storage of data D to a server P and then repeatedly check if P is still storing D.

• Proof-of-Replication (PoRep) schemes are another kind of PoS that additionally ensure that P is dedicating unique physical storage to storing D.

• Proof-of-Work (PoW) schemes allow prover P to convince verifier V that P has spent some resources.

• Proof-of-Space (PoSpace) schemes allow prover P to convince verifier V that P has spent some storage resources.

• Proof-of-Spacetime (PoSt) schemes allow prover P to convince verifier V that P has spent some "spacetime" (storage space used over time) resources.

2 Proofs-of-Replication

We introduce Proof-of-Replication (PoRep) schemes, which allow a prover P to (a) commit to store n distinct replicas (physically independent copies) of D, and then (b) convince a verifier V that P is indeed storing each of the replicas.

Definition 2.1. (Sybil Attack)

An attacker A has Sybil identities P0...Pn, and makes each commit to storing a replica of D. The attack succeeds if P0...Pn store less than n copies of D (i.e., one copy).

Definition 2.2. (Outsourcing Attack)

Upon receiving challenge c from verifier V, an attacking prover A quickly fetches the corresponding D from another storage provider P and produces the proof, pretending that A has been storing D all along.

Definition 2.3. (Generation Attack)

If attacker A is in a position to determine D, then A may choose D such that A can regenerate D on demand.

Definition 2.4. (RepGame)

In the Replication Game, an adversary, A, with a fixed amount of storage l, adaptively interacts with an honest verifier, V.

Definition 2.5. () A general PoRep proving scheme

(\Pi^{\text{PoRep}} = (\text{Setup}, \text{Prove}, \text{Verify})) is a set of algorithms that enable a prover P to convince a verifier V that P is storing a replica R_D of data D.

2.1 Time Bounded Proofs-of-Replication

There are likely to be many different strategies for constructing Proof-of-Replication protocols. Any secure construction must prevent the Sybil Attack, the Outsourcing Attack, and the Generation Attack and must pass the RepGame.

Definition 2.6. (Seal)

We define a pair of encoding functions Seal and Unseal, inverses of each other, parameterized over any secure block cipher algorithm BC and number of rounds t:

SealBC(ek; D) := BC:CBC:Encrypt(ek; D)

UnsealBC(ek; R_D^ek) := BC:CBC:Decrypt(ek; R_D^ek)

3 Proofs-of-Spacetime

Usually, most PoS and PoSpace schemes are described in terms of interactive challenge settings, where a verifier V issues single or periodic challenges to a prover P. Unpredictable yet frequent challenges can give V confidence that P has been correctly storing the required data D for the duration of time challenged. These challenges must be frequent and unpredictable.

Definition 3.1. (proof-chain)

A proof-chain is a verifiable data structure that chains together a sequence of challenges and proofs.

Definition 3.2. () A general PoSt proving scheme

(\Pi^{\text{PoSt}} = (\text{Setup}, \text{Prove}, \text{Verify})) is a set of algorithms that enable a prover P to produce an incremental time-bounded proof-chain Cn that proves to a verifier V that P has been storing data D during iterations 0 to n of the proof-chain.

Acknowledgements

This work is the cumulative effort of multiple individuals within the Protocol Labs team, and would not have been possible without their help, comments, and review.

References

[1] G. Ateniense et al. Provable data possession at untrusted stores. In Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS ’07.

[2] E. Ben-Sasson et al. Computational integrity with a public random string from quasi-linear pcps. In Annual International Conference on the Theory and Applications of Cryptographic Techniques.

[3] E. Ben-Sasson et al. Snarks for c: Verifying program executions succinctly and in zero knowledge.

[4] N. Bitansky et al. Succinct non-interactive arguments via linear interactive proofs.

[5] D. Boneh et al. Balloon hashing: A memory-hard function providing provable protection against sequential attacks. In International Conference on the Theory and Application of Cryptology and Information Security.

[6] C. Dwork and M. Naor. Pricing via processing or combatting junk mail. In Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO ’92.

[7] R. Gennaro et al. Quadratic span programs and succinct nizks without pcps. In Annual International Conference on the Theory and Applications of Cryptographic Techniques.

[8] A. Juels and B. S. Kaliski, Jr. Pors: Proofs of retrievability for large files. In Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS ’07.

[9] A. K. Lenstra et al. A random zoo: sloth, unicorn, and trx.

[10] T. Moran and I. Orlov. Proofs of space-time and rational proofs of storage. Cryptology ePrint Archive, Report 2016/035.

[11] S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008.

[12] H. Shacham and B. Waters. Compact proofs of retrievability. In Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security.