1
$\begingroup$

In the paper Provable Data Possession at Untrusted Stores, there is a mechanism that allows a client to efficiently check if the server still has the client's data. They define two constraints for their system: server-side data access and communication complexity.

Also, they state that a scheme based on just Merkle tree cannot be secure (so they don't talk about the complexity here). They have cited a paper but cannot find any explanation for that.

Question: Why cannot we design a PDP using just a Merkle tree?

$\endgroup$
1
$\begingroup$

I'd say that like with the naive variant of simply asking for the hash of the data, the server can just throw away the data and store the hashes and still answer queries. It is important for such schemes that a query requires the server to use sufficient randomness together with the data in the computation of the answers. Then precomputing the potential answers will require too much storage and it is then actually less costly to keep the data itself.

| improve this answer | |
$\endgroup$
  • $\begingroup$ thanks for the answer. We can build a Merkle tree on top of data blocks (so the leaf nodes are data blocks). In this case, the client can send random challenges, as it does in PDP, and the server provides proofs that include the blocks and their related paths in the tree. $\endgroup$ – user153465 Oct 9 '18 at 9:35
  • $\begingroup$ Yes sure. But then you will have to maintain a potentially large state at the client right? This is what PDP wants to avoid. $\endgroup$ – DrLecter Oct 9 '18 at 12:15
  • $\begingroup$ thanks for your comment, but why do you think that the client needs to maintain a large state. Everything except the root of the tree is outsourced ot the server. Am I missing something? $\endgroup$ – user153465 Oct 9 '18 at 13:41
  • $\begingroup$ How does a fixed root work together with random challenges? Wouldnt you need to locally compute and store a root per challenge before outsourcing? $\endgroup$ – DrLecter Oct 9 '18 at 13:45
  • $\begingroup$ the tree is built on top of data blocks. then the random challenges specify the indices of leaf nodes (or data blocks). Every time a set of challenges is sent to the server, it proves that the challenged blocks are in the tree. As you know, this requires sending the challenged blocks and some sibling nodes to the client. $\endgroup$ – user153465 Oct 9 '18 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.