Understanding the concept behind storage proofs

Here I am referring to the concepts that are used in Filecoin. What Filecoin does is that say some users or clients want to store their data. Filecoin provides nodes that are known as storage providers. Internally, under the hood, Filecoin uses the IPFS protocol to achieve the content-based addressing and data storage scheme. These storage providers or retrieval providers are incentivized with the help of FIL tokens to persistently store data. What happens is that if a client wishes to store the data a deal as well as negotiations based on the data size, market price etc takes place between the client and the storage providers and then when a deal is finalized ( all of these usually happen off the chain) the final proof of this deal is submitted on the chain.

Now the storage providers somehow need to prove that they indeed have the data stored inside their devices. For this Filecoin uses the concept of Proof of Replication which is a mixture of Proof of Storage and Proof of Space.

Proving systems are cryptographic protocols where there’s a prover and verifier and the prover is going to prove something to the verifier. In Proof of Work, for example, it’s that the prover has done some amount of work, or spent some amount of computational cycles. The classic example is hashes [in Bitcoin]. Another example is a Verifiable Delay Function (VDF), where I can prove to you that I’ve spent a certain amount of cycles, in sequence, and so I’ve waited a certain amount of time [Filecoin does not use VDFs but it’s a research area]. So all these Proof of Storage systems are proving systems like that, low-level cryptographic primitives used in a wide variety of protocols.

Proofs of Storage are simple proving systems to prove that I have possession of some data. A Proof of Data Possession example is: I can prove to you that I have data X, either without revealing data X or if the data is several GB large, in some more succinct way. Then there’s Proof of Retrievability where, not only am I going to prove that I have X, but also that these proofs can be used to reconstruct X in case I’m malicious and want to withhold X from you.

The abstract code that ChatGPT provided for both these concepts is as follows:

function proof_of_storage(data, storage_proof) {
  // Check if data is stored in the required storage location
  if (check_storage(data, storage_proof)) {
    // Calculate a hash of the stored data
    let data_hash = hash_data(data);

    // Generate a random challenge
    let challenge = generate_challenge();

    // Compute a response to the challenge
    let response = compute_response(storage_proof, challenge);

    // Verify the response
    if (verify_response(data_hash, storage_proof, challenge, response)) {
      // Storage proof is valid
      return true;
    } else {
      // Storage proof is invalid
      return false;
    }
  } else {
    // Data is not stored in the required storage location
    return false;
  }
}

function check_storage(data, storage_proof) {
  // Check if the data is stored in the required storage location
  // using the information in the storage proof
  // Return true if data is stored in the required location, false otherwise
}

function hash_data(data) {
  // Compute a hash of the data using a cryptographic hash function
  // Return the hash value
}

function generate_challenge() {
  // Generate a random challenge using a secure random number generator
  // Return the challenge
}

function compute_response(storage_proof, challenge) {
  // Use the storage proof and challenge to compute a response
  // Return the response
}

function verify_response(data_hash, storage_proof, challenge, response) {
  // Verify the response using the data hash, storage proof, and challenge
  // Return true if the response is valid, false otherwise
}

function proof_of_space(plot_id, challenge_hash, response) {
  // Calculate the hash of the plot using a cryptographic hash function
  let plot_hash = hash_plot(plot_id);

  // Concatenate the plot hash and challenge hash
  let concatenated_hash = concatenate_hash(plot_hash, challenge_hash);

  // Compute a hash of the concatenated hash and the response
  let computed_hash = hash_response(concatenated_hash, response);

  // Check if the computed hash meets the required difficulty target
  if (check_difficulty(computed_hash)) {
    // Proof of space is valid
    return true;
  } else {
    // Proof of space is invalid
    return false;
  }
}

function hash_plot(plot_id) {
  // Compute a hash of the plot ID using a cryptographic hash function
  // Return the hash value
}

function concatenate_hash(plot_hash, challenge_hash) {
  // Concatenate the plot hash and challenge hash
  // Return the concatenated hash value
}

function hash_response(concatenated_hash, response) {
  // Compute a hash of the concatenated hash and the response using a cryptographic hash function
  // Return the hash value
}

function check_difficulty(computed_hash) {
  // Check if the computed hash meets the required difficulty target
  // Return true if the hash meets the target, false otherwise
}

For proof of storage what I am thinking is that when the data is stored for the first time it would already have some size associated with it. So it makes sense to again compare the size of the stored file to see that yes the file is of the same size and generate a proof for that.

For proof of space actually the architecture is designed in such a way that if the merkle root generated is not the same as before obviously there is an error. In that case we need to do a check. This check would be to generate the hash of all the 4 data blocks and compare it with the leafs. If any of the hash doesn't match it means that the data has been manipulated