Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hash-tree]

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.

2
votes
2answers
140 views

Why do the non-leaf Nodes of Merkle tree need to be hashed?

Given the standard Merkle Tree as shown Wikipedia. I am having a hard time understanding why Hash(Hash(Leaf A)|| Hash(Leaf B)) at the parent of A and B is ...
0
votes
0answers
28 views

Why is Proof of non-inclusion in a Merkle Tree harder than Proof of inclusion?

I am new to cryptography and I am wondering Why is Proof of non-inclusion in a Merkle Tree harder than Proof of inclusion? My naive thought for Proof of non-inclusion is that I would look for ...
3
votes
1answer
201 views

Zero knowledge proofs for a Merkle Tree

Say I have a publicly available Merkle tree, and I want to prove the existence of a leaf (containing a number, maybe) in the tree. I could give the path along with the siblings, for a normal Merkle ...
1
vote
0answers
40 views

Validation of Merkle branch for a root

In the paper of the Honey Badger BFT link, which is a BFT algorithm, that makes use of cryptography, there is described an algorithm for a reliable broadcast with erasure codes. Following part of the ...
2
votes
1answer
178 views

File integrity checking: why use a hash tree instead of a hash list?

File sharing systems sometimes use the likes of a Tiger Tree Hash to check the integrity of a file as it is downloaded. Hash trees in general are useful to check integrity of the tree leaves without ...
1
vote
0answers
62 views

Tree structure with XTS and HMAC: MAC in parent

Situation: A file format contains a tree-like data structure; parent nodes can find children and child nodes can also find their (single) parent. To protect confidentiality, the nodes in the file are ...
1
vote
1answer
116 views

Stateless and deterministic number generation

I want a stateless deterministic pseudorandom generator. Following number generation is deterministic, whenever I give $constantValue$, and index it will value $A$ $A = Hash(constantValue + index)$ ...
0
votes
1answer
32 views

AUTHENTICATE MERKLE TREE: In the passage below how is A able to confirm YB in the public file only knowing R, log2 intermediate values, and YB itself?

"If A wishes to confirm B's public enciphering key, then A need only know the first half of the public file, (which is where YB appears) and H(second half of public file) which is only 100 bits long. ...
0
votes
1answer
136 views

Why a Blockchain cannot confirm “Membership Proof” as can a Merkle Tree?

I'm currently reading the Princeton Blockchain Book, and came across this concept: Proof of membership. Another nice feature of Merkle trees is that, unlike the block chain that we built before, it ...
3
votes
1answer
667 views

Is there a hash tree scheme designed for complex data structures?

I have a JSON object with private data. It has the following (complex!) structure: ...
1
vote
1answer
398 views

What are the advantages and disadvantages of Merkle signatures over Lamport signatures?

I know they are both hash-based and post-quantum secure, and that Lamport signatures can form the basis for a Merkle scheme, but what do you actually gain over standard Lamport signatures by doing ...
8
votes
1answer
926 views

How to to calculate the hash of an unordered set

Suppose I have a set of elements, with known hash (e.g. SHA-2). How can I calculate the hash of the set? With it I mean an unordered set, so the order of elements is undefined and shall not play any ...
5
votes
1answer
533 views

Merkle trees instead of the Sponge or the Merkle-Damgård constructions for the design of cryptorgraphic hash functions

Most modern cryptographic hash functions use some form of compression function combined with a construction such as the Merkle-Damgård (MD5, SHA1, SHA2, etc), the Sponge construction (with Keccak as a ...
2
votes
1answer
129 views

CONIKS Prefix Merkle Tree - is it necessary to change tree-wide constant for each update

folks! I'm digging through CONIKS papers and it seems that it is an absolute must to select new tree-wide constant for each update (and to rebuild the whole tree respectively) to prevent parallel ...
3
votes
2answers
103 views

Efficient way to combine collection of hashes into a single hash?

I have a system where each user will submit a set of data. The data will be hashed and their hash will be submitted to the server. My plan is to combine each users hash (converted to bytes XOR'd with ...
2
votes
1answer
88 views

Performing a cryptographically secure HMAC using multiple input parameters

I'm using an HMAC as a way to generate a deterministic challenge token for an authentication system. I've effectively got three string inputs plus a key: Client IP address (string, eg: "127.0.0.1") ...
5
votes
0answers
127 views

Are there conventions for signing JSON as a tree, to allow proofs of signed subtrees?

Given some JSON with a chosen encoding, you can obviously cryptographically-sign the whole thing as a binary blob. However, it might be useful if the logical structure of the JSON-compatible object ...
3
votes
1answer
264 views

Merkle-like hash tree that mirrors existing tree structure

I'm wondering about the security of a hash-tree structure that mirrors the structure of another tree. In an ordinary Merkle tree the block hashes form the leaves of the tree, and all internal nodes ...
6
votes
3answers
749 views

Why do we need Collision Resistant Hash Function for the Merkle Tree Signature Scheme?

I am studying Merkle Tree Construction for digital signature. I don't quite understand why we need collision resistant hash function for Merkle tree construction. There are few papers like XMSS that ...
3
votes
1answer
309 views

Verifying authentication by just using the root of a Merkle tree

Let's say I've a Merkle tree where leaves are the hashes of some data that needs to be authenticated. Can I verify the whole of them by just using the hash of the root of Merkle tree? If yes, how?
10
votes
1answer
706 views

Is hashing large files CPU or I/O bound?

For SHA3, if I were to hash large files (> 1GB), would that operation be CPU or I/O bound? Suppose I were to exploit parallelism and either use multicore/SIMD execution or generate a hash tree, ...
5
votes
0answers
415 views

Dynamically building a Merkle tree for unkown size

Assuming a $k$-ary Merkle tree: If the length of a file is known, based on a fixed chunk size, one could calculate the number of chunks and thus the depth of the tree. Then, based on $k$, the chunk ...
4
votes
3answers
411 views

What is the reason to separate domains in the internal hash algorithm of a merkle tree hash?

From rfc 6962 It is stated that: Note that the hash calculations for leaves and nodes differ. This domain separation is required to give second preimage resistance. That means that ...
8
votes
1answer
128 views

Is it possible to build short proofs of arbitrary computations over a big list?

With the use of Merkle Trees, you can prove the presence of an element of a very big list, with an amount of information logarithmic in the size of the whole tree. Merkle proofs, thus, ...
0
votes
1answer
126 views

Questions regarding parallel AES CTR with merkle trees

I'm planning to implement a parallelizable variant of AES to end-to-end-encrypt files in a web application. As a mode of operation I'm most likely gonna use CTR mode with a 64 bit IV and 64 bit ...
1
vote
1answer
292 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 ...
4
votes
1answer
148 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
943 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 ...
9
votes
4answers
3k views

Proof of non-membership on a Merkle tree?

Assume a user $U$ and a server $S$. $U$ uploads its data and wants later to perform an authenticity check. It also sends a Merkle tree to the server. Let’s say we would like $U$ to ask for a specific ...
3
votes
2answers
316 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 ...
1
vote
3answers
398 views

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 ...
15
votes
2answers
483 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
123 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 ...
3
votes
3answers
137 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
2answers
268 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: ...
3
votes
1answer
129 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 ...
4
votes
1answer
79 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 ...
11
votes
1answer
5k 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 ...
8
votes
1answer
1k 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 ...
6
votes
2answers
620 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. ...
3
votes
1answer
467 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 ...
2
votes
1answer
244 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 ...
10
votes
1answer
929 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, SHA-2 or BLAKE in Merkle tree do not have? ...
8
votes
3answers
1k 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
0answers
430 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
97 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 ...
4
votes
1answer
476 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 ...
1
vote
1answer
151 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 ...
11
votes
2answers
2k 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 ...
1
vote
0answers
208 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 ...