Proof of Storage (PoS) enables a cloud storage provider to prove that a client's data is intact. However, existing PoS protocols are not designed for the pay-As-you-go business model in which payment is made based on both storage volume and duration. In this paper, we propose two PoS protocols suitable for the pay-As-you-go storage business model. The first is a time encapsulated Proof of Retrievability (PoR) protocol that ensures retrievability of the original file upon successful auditing by a client. Considering the large size of outsourced data, we then extend the protocol to a privacy-preserving public auditing protocol which allows a third party auditor to audit outsourced data on behalf of its clients without sacrificing the privacy of the data or the timestamp (i.e., time of storage). We formalize the definition, system model and security model of the proposed PoS system and prove the security of the proposed protocols by a sequence of games in the algebraic group model with a random oracle. We analyze the performance of the protocols both theoretically and experimentally and show that the protocols are practical.