We develop a novel method for a user to pay for cloud storage. Compared to traditional cloud storage such as Amazon’s S3, the user does not have have to trust the server. We use Bitcoin smart contracts to ensure the payment is contingent upon the server‘s Proof of Retrievability (PoR), which can only be produced if the data is still available and can retrieved if needed.
Proof of Retrievability (PoR)
Many people outsource storage by uploading their data (like music, photos, and documents) to remote servers for reliability and easy accessibility from many devices, including mobile phones and laptops.
These users are at the mercy of their storage providers and have to trust the servers. A malicious server may discard the data to save resources if it is rarely accessed, or cover up data loss accident to protect their reputation.
A PoR scheme is cryptographic protocol that would allow a user, or a third party like an auditor, to verify that the server stores his data. Such an auditing capability reassures a user his data is still being stored. It can also be crucial to storage providers like an unknown startup, since users may be reluctant to entrust their data to the startup otherwise.
Pay for Storage using PoR
A naïve PoR is for the user to simply request the server to download all of the data and verify authenticity. However, this is enormously inefficient when the stored data is large.
The Shacham/Waters PoR scheme¹ is an efficient audit protocol between client and server. A server that passes the audit must know all of the client data. It is also publicly verifiable, which is needed when we verify the proof in a smart contract.
A file is first encoded with erasure codes, a type of error correcting codes, to allow recovery even if the server loses a fraction² of the file. The coded file is divided into n blocks. A tag (also called an authenticator) is computed for each block, which contains its meta information and is needed for efficient verification. Both the blocks and their tags are sent to the server to store.
To test if the server still has the file, the user randomly selects a set of blocks in a challenge. The server, upon receiving the challenge, needs to send back a response, which is verified by the user.
Formally, the Shacham/Waters PoR consists of three steps.
We need a noninteractive protocol in a blockchain setting, where the user/verifier and server/prover do not have to communicate back and forth. In step 1, we let that the prover, the server in this case, generates challenges by himself. To ensure an unbiased challenge, we need publicly traceable and uncontrollable randomness source, e.g., the latest blockhash³. In step 2, the server generates the PoR off chain based on challenges in step 1. In step 3, a smart contract verifies the PoR. The verification needs elliptic curve arithmetic and pairing, both of which have been implemented.
The user deploys a smart contract, which only releases funds if a valid PoR is provided. The server can only be paid if he can submit a valid PoR, which he can only produce if he is still storing the user’s file.
Recurring payments
We can extend the one-time payment to a subscription by adding recurring payments on top, so that the server is paid periodically a fixed amount.
Payment channels
If the user and server can interact regularly, they can alternatively implement the recurring payments by opening a payment channel. The user issues a challenge to the server, say, every month. The server responds with a PoR. Upon verifying the PoR, the user sends his monthly payment by increasing the server’s channel balance. When the storage subscription expires, either side can close the channel.
[1] Compact Proofs of Retrievability by H Shacham 2008
[2] The fraction depends on the rate of the error-correcting.
[3] This is secure as long as the payment is less than the block reward.
