# Doubts about Authenticated Data Structures logic

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!

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.

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.)

• Suppose I need to authenticate a hash table, so a lot efficient data structure on complexity: if I ask for a particular element to the cloud and it answers me with that element + the digital signature, is not more efficient than have, on cloud provider side, to mantain another data structure (like Merkle Tree) to authenticate the DB? Do you think that do an encryption or a decryption is less efficient to make a series of hash operations? And what about RSA accumulators? On performance side is not so useful use them... Dec 8 '15 at 20:50
• I don't think that Merkle Tree gives you more control over the entire DB (even if it is a digest of entire datas), since in general you have to contact the cloud provider more times to check the integrity as you should do with block + digital signature. Dec 8 '15 at 20:54
• (For some reason, I didn't get a notification of your comments.) ​ The cloud provider answering you "with that element + the digital signature, is not more efficient than" having the cloud provider "mantain another data structure (like" a Merkle tree) "to authenticate the DB". ​ However, a Merkle tree would require any long-term storage, since it doesn't use secrets, so they can generate it on their own. ​ I have no clue about the runtime of encryption/decryption versus hashing, or RSA accumulators. ​ ​ ​ ​
– user991
Dec 10 '15 at 22:08
• Why would you "you have to contact the cloud provider more times to check the integrity as you should do with block + digital signature"? ​ ​
– user991
Dec 10 '15 at 22:09
• In general the "verifier" need to contact more times the cloud provider to check the file integrity, since it is a verifier. Maybe the probability to check a forgery is more simple using a data structure like Merkle Tree. But it is just a suppose... Dec 13 '15 at 16:57

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.