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: (i) receiving, at a prover, an initial input challenge; (ii) producing, at the prover, an output proof proving that the prover has access to specified data for a specified time, wherein producing the output proof includes: (a) producing, at the prover, an initial proof responsive to the initial input challenge, the initial proof proving that the prover is storing specified data; (b) generating, at the prover, a new input challenge based at least in part on the initial proof: (c) producing, at the prover, a new proof responsive to the new input challenge, the new proof proving that the prover is storing the specified data; and (d) repeating, at the prover, the generating step and the producing a new proof responsive to the new input challenge step a number of times, the repeating step generating sequential proofs of storage to determine time of storage, wherein each generating step is based at least in part on a most recent new proof; and (iii) forwarding the output proof, e.g., to a blockchain.