Proof of Storage-Time: Efficiently Checking Continuous Data Availability

Giuseppe Ateniese (Stevens Institute of Technology), Long Chen (New Jersey Institute of Technology), Mohammard Etemad (Stevens Institute of Technology), Qiang Tang (New Jersey Institute of Technology)

A high quality outsourced storage system is crucial for many real applications, for example, hospitals and data centers which need to guarantee the high availability of their systems to perform routine daily activities. Such a system should be able to protect users against downtime, whatever the cause and ensure that users remain connected to their data files any time.
Continuous data availability is one of critical properties to measure the quality of a outsourced storage service, which means the outsourced data is continuously available to the server during the whole storage period. We formally study the Proof of Spacetime (PoSt), the notion proposed by the Filecoin whitepaper, which enables a verifier to audit the continuous data availability of a outsourced storage system.
In this paper, we provide a formal security model of PoSt, and generic constructions that are proven secure under our definition. Moreover, our concrete instantiation can yield a PoSt protocol with extremely efficient verification: only around 200 bits proof, and only do one hash computation to verify; also a reasonable setup (which takes only less than 3 minutes for a protocol to audit a file with size 64 MB to be persistently stored for a month).