A hash tree (or Merkle tree) is a method of hierarchically hashing data. They allow efficient parallel hashing and updates and the possibility of verifying partial data.

learn more… | top users | synonyms

1
vote
1answer
40 views

Is the “Hash Tree” described in this paper the same as a Merkle Hash Tree?

I'm implementing an algorithm from a paper, and part of it calls for using a "hash tree". Since I'd never heard of that data structure I looked it up on Wikipedia. It turns out that the name hash tree ...
0
votes
0answers
31 views

What happens if someone implements tree-base signature scheme incorrectly?

I'm learning about signature schemes and read about Merkele's tree-base signature scheme. There are paragraphs about how the key and signings are generated. Using so-called tree structure and pseudo ...
2
votes
0answers
43 views

What is the canonical way of creating merkle tree branches?

I'm currently looking into creating some compact merkle tree branches to prove that a given hash was included in a given merkle root. My initial thought was to list the leaf, the merkle root and all ...
3
votes
1answer
41 views

Updating values authenticated by Merkle Tree

Assume we have 4 values: $v_1,v_2,v_3$ and $v_4$. We construct a Merkle tree on top of them such that the values are leaves of the tree. I send the values and the tree to an untrusted server. But I ...
3
votes
1answer
58 views

Merkle tree (dm-verity) with SHA-256 vs. SHA-1

Is there any knowledge or research on the use of different hash functions within a Merkle tree? My use case is file integrity protection. I am thinking about using different hash functions due to ...
2
votes
3answers
108 views

Proving that a node is the only child

Say I have a graph of messages like this: A | B / \ C D By including the parent hash in the message to be hashed I can show that B is a child of A, ...
4
votes
3answers
133 views

Proof of non-membership on a merkle tree

Assume a user U and a server S. User uploads its data and wants later to perform an authenticity check. It also sends a merklee tree to the server. Lets say we would like the user to ask for a ...
0
votes
1answer
79 views

Doubts about Authenticated Data Structures logic

I am studying the theory of authenticated data structure, like Merkle Tree and I have a doubt: why use them? I explain better: why to be sure, for example, that a cloud provider didn't modify my files ...
8
votes
0answers
96 views

Is there a standardized tree hash?

SHA-1, SHA-2, and the standardized version of SHA-3 are all sequential. This is impractical for hashing very large files distributed across machines. Any sequential hash can be straightforwardly ...
2
votes
0answers
44 views

Signing integers and UUIDs and restoring them from a third party server without tampering

I'm educating myself about cryptography. I know this is a long one, but please, bear with me. :) Now I have a scenario in my mind and I'd like to ask if what I've thought is sound (enough), what more ...
4
votes
1answer
131 views

Proving set membership in less than log(N) bandwidth

I have an unchanging set of unique items, and I want my server to show one of those items to a client, then cryptographically prove that the item is part of the set. How I do this currently: ...
2
votes
1answer
58 views

Can a tree hash with leaf-size of 1 byte support verification of content with elided ranges, at a cost of at most 2 supplied internal-node hashes?

Perhaps someone can confirm my intuition: A tree hash with leaves of size 1 (for example Blake2 in a tree-hash mode) would of course not be very efficient. But it seems that it might be a suitable ...
6
votes
3answers
515 views

Stateless hash based public key cryptography?

Merkle-Winternitz signatures based on fractal hash trees are an attractive alternative to other post-quantum cryptographic schemes, in particular since they are conceptually simple, the security ...
3
votes
1answer
63 views

Given just the hash of a file, can I verify that the file contains a specific data block?

Imagine I only have the hash of a file which we can call hash(file). Then a user sends me a data block (or section) of the same file, which we can call ...
2
votes
1answer
129 views

Comparing n-multiple amount of merkle trees?

I would like to know what best steps are there in finding differences between a high order amount of merkle tree's or if a better associative structure should be used. I ask this questions because ...
4
votes
1answer
299 views

Fractal Merkle Traversal

I am studying Fractal Merkle Tree Traversal algorithm in the book “Post Quantum Cryptography” (PDF). On the [pag. 54] I don't understand this paragraph: We may determine the number of pebbles ...
5
votes
1answer
822 views

Merkle hash tree updates

It seems that merkle hash tree (MHT) traversals have been discussed somewhat in the literature, but there does not appear to be much written on inserting, deleting, and updating leaves. Is this lack ...
7
votes
2answers
301 views

Are there cryptographic hash functions with homomorphic properties? [duplicate]

Are there cryptographic hash functions that have homomorphism-like properties? E.g. satisfying following relation $h(a || b) = h(a) · h(b)$, where $h(x)$ is hash function itself, $x || y$ is ...
5
votes
2answers
317 views

Hash or compression function in Merkle tree nodes?

Wikipedia says about a Merkle tree: Nodes further up in the tree are the hashes of their respective children. Usually, a cryptographic hash function such as SHA-2 or SHA-3 is used for the hashing. ...
2
votes
1answer
217 views

Generalized Merkle Signatures, SHA-3 and Sakura

Sakura specifies a tree hash mode for e.g. Keccak (SHA-3). Are there any reasons to use the Sakura tree hash mode in a Generalized Merkle Signature Scheme? It seems to me Sakura primarily solves a ...
3
votes
0answers
214 views

Tiger Tree Hash vs generic Merkle Tree

Is there any advantage of using Tiger Tree Hash over any other hash function organized as the Merkle tree? Are there maybe any properties of TIGER that, say, SHA2 or BLAKE in Merkle tree do not have? ...
2
votes
0answers
207 views

Infinite depth BLAKE2b tree hashing

In the BLAKE2 paper, the authors define Maximal depth (1 byte): an integer in [1, 255] (set to 255 if unlimited, and to 1 only in sequential mode) Node depth (1 byte): an integer in [0, 255] ...
2
votes
1answer
78 views

How are the lower levels calculated using upper levels in an optimized Merkel Hash Tree?

I was reading about the TIK protocol for thwarting wormhole attacks on adhoc networks. It uses a Merkel Hash Tree to store keys. But since the number of keys can be large, the tree is optimized by ...
9
votes
2answers
1k views

Efficient Incremental Updates to Large Merkle Tree

I have a data set with 300 Million entries and every 5 minutes 4000 random entries in this table change. I need to calculate the merkle root on this data set to validate integrity multiple times ...
11
votes
2answers
810 views

What is the purpose of using different hash functions for the leaves and internals of a hash tree?

I just learned that the THEX hash tree specification which is widely used in P2P requires that two different hash functions be used: one for the leaf nodes (hashes of input data) and one for the ...
1
vote
0answers
159 views

Merkle path authentication

In point 4 of the Algorithm 4.2 (Classic Merkle Tree Traversal) of *"Post_Quantum_Cryptography.pdf"* shows *"Stack_h.update(2)"* each stack receives two updates. I am trying understand to understand ...
1
vote
1answer
110 views

Best hash size for hash trees

I want to know if having a 8-byte hash value is better than 16-byte hash value for use within hash trees. My mind tells me that the shorter the hash value, the better. But doesn't a smaller hash ...
2
votes
1answer
242 views

Tree hash and multithreading for parallelism

I am using tree hash mode of Skein on a 16 core processor. Will it automatically employ parallelism using more than one cores or do I have to use multi-threading within the tree hash for parallel ...
7
votes
1answer
950 views

How does a “Tiger Tree Hash” handle data whose size isn't a power of two?

Constructing a hash tree is simple enough if the data fits into a number of blocks that is a power of two. ...