Provable data possession (PDP) VS Merkle tree 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?
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.