How are hash trees useful?

Question

I read on hash trees on Wikipedia, and I don't understand the benefits or goals of this structure - they seem to require more hashes than just one per sheet without significant use of additional hashes.

For example, the use of Wikipedia is that they are used to verify data received in a P2P system. But why is it better than having a one-to-one comparison of the numbers of blocks and their hashes without a tree structure?

Can someone explain how and why hash trees are useful?

Thanks in advance,

Moshe

Answer 1

• Hash trees can be computed in parallel. If you have two data blocks for a hash, you can use two processors to calculate the hash twice as fast. This only works if your hash rate is lower than your I / O speed, which is unlikely.

• Hash trees can be computed from hashes of individual blocks or from hashes of larger partitions that are aligned correctly. It is important.

For example, if I want to send you a file, I can split it into 1 MiB chunks and send you each chunk with its SHA-256 hash. If the hash for any of the individual fragments is incorrect, you can request this piece again. In the end, I can sign the tree hash for the file and send the signed hash. You can verify the hash only by hashing each of the hashes of the block (which you have already verified), which is much faster than renaming the entire file.

Why use a tree hash?

A tree hash is beneficial at any time when you want to calculate the hash of both parts of a file and the entire file. Using a regular hash, such as SHA-256, you will have to hash the file and the entire file separately. If the file is 8 GiB, this may take some time. With a tree hash, since the fragment hash is used to calculate the file hash, it does not require additional work to calculate both hashes.

How much extra work is a tree hash?

The “extra work” for computing a tree hash is actually minimal. Yes, this requires computing additional hashes, but only O (1) extra work. If your block size is 1 MiB, then the extra work is zero if your file is 1 MiB or less. As the data size increases, the amount of additional work will approach 1 additional hash of two hashes for each data block - for SHA-256, the kernel will be evaluated only two additional times for 1 MB of data maximum (once for input hashes, once for filling ) This is not very.