Doubts about Authenticated Data Structures logic

Question

I am studying the theory of authenticated data structures, like Merkle Trees and I have a doubt: Why use them?

For example, to be sure that a cloud provider didn't modify my files, why do I have to ask for a particular data block and have the cloud reply with a hash path from the leaf to the root to authenticate all the tree (and then all the database)?

Isn't it simpler to ask a for particular piece of the DB (suppose the DB is divided in blocks) and receive from the cloud provider that block with a digital signature? In this way, I can ask continually for a lot of blocks without using a Merkle tree at all.

I am reading materials about the RSA accumulator, bilinear maps, Bloom filters, etc., and every time I read about different protocols built over particular data structures. Since using these techniques has a computational cost (e.g., RSA accumulators can be expensive) my question is as asked before: Instead of having a single digest that authenticates the entire set or DB, why not require different pieces of data with the digital signature?

I hope you can answer my strange question!

Thank you!

Answer 1

One reason I see is that simple signatures only prove the data block was produced by you, but not that the block is what you queried for.

A simple example: suppose you have 4 data blocks $d_1,d_2,d_3,d_4$ which you can query by index, i.e. on query = 1, the server should return $d_1$.

Now when using a signature scheme, you store $(d_1,d_2,d_3,d_4)$ as well as their signatures $(s_1,s_2,s_3,s_4)$. Later you query 3, and the server returns $(d_{x},s_{x})$. At this point, you can verify that $s_x$ is indeed a signature of $d_x$. But how can you be sure $d_x$ is $d_3$ you asked for? What you have got can be $(d_1,s_1)$ for example, which will pass the check. Remember that the main spirit of using a cloud is that you store your data in the cloud without having to keep a local copy. Now you won't be able to tell whether you get the right answer.

If you use a Merkle tree, then you will get a tree like this:

Now when you query 3, you will get $(d_3',h0',h11')$. You can hash $H(h0'||H(H(d_3')||h11'))$. If the result is the same as the root you saved, you must have got $d_3$ as you requested, as the path is unique for this item.

A similar issue when using signatures is that what if the server returns an old version of the data item? There is no way to tell because the signature does not prove freshness. When using a Merkle tree, the root is updated every time you update the data, so it gives you freshness guarantee.

Answer 2

Merkle trees provide authentication with no secrets, and can
more efficiently authenticate large-enough contiguous regions.

It is "more simple to ask" for "a particular piece of Db (suppose a database divided in blocks)
and receive from the cloud provider that block with the digital signature".

(I believe "with no secrets" is the more important consideration in its sentence.)

Answer 3

Using Merkle tree reduces the offline storage on the client's side (root node), but it may increase bandwidth cost as you have to send the authentication nodes, $\log_2(n)$ nodes + the file itself.

Doing it your way should work. It's no better than storing hash digests of different pieces of data. It increases the storage on the client side as the client needs to store and manage a signature for each data block and 1 public key, but the bandwidth cost is now only the file itself.