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.

Byzantine Fault Tolerance (BFT) accounts for faults as the number of faulty nodes and is thus cumber- some to apply to many modern decentralized systems. We introduce the Power Fault Tolerance (PFT) model, which reframes BFT in terms of participants’ influence over the outcome of a protocol, instead of the number of nodes. In PFT, n is the total power, and f is the fraction of power controlled by faulty or adversarial participants. This work:

• (a) provides a formal definition and properties for PFT;
• (b) generalizes Byzantine Consensus (BC) protocols of different classes (permissioned, permissionless, and federated) into a single class of Power Consensus (PC);
• (c) explores new directions for PC protocols, particularly for blockchains, and protocols that can detect and make progress during catastrophic network partitions;