Methods, systems, and apparatus, including computer programs encoded on computer storage media, for establishing a proof of storage over a specified period of time. One of the methods includes: (a) receiving, at a prover, an input challenge at a start time; (b) producing a proof responsive to the input challenge, wherein the proof is based at least in part on a proof of storage; (c) generating a new input challenge based at least in part on the proof; (d) repeating steps (b)-(c) a number of times resulting in a final proof; (e) receiving a proof result based at least in part on the final proof from the prover within a specified period of time from the start time; and (f) forwarding, to the verifier, the proof result.