# Tag Info

## Hot answers tagged hash-tree

13

A well known technique to form the hash of an unordered set given hashes of the elements, is to order the hashes lexicographically, concatenate them in this order, and hash the result. The order of the elements in the original set does not influence the result, and this demonstrably inherits the properties of the hash (collision-resistance, preimage ...

9

The general technique for tree hashing (independently of the issue of partially revealing content) is to define the hash of nodes as the hash of the concatenation of the hash of their leaves, with a suffix (or prefix) that makes the input of the hash different for leaves and nodes. Demonstrably, this inherits from the cryptographic hash it's properties of ...

8

Yes, a stateless hashbased signature method called Sphincs was recently proposed. It works by having a moderately large Merkle tree (similar to what D.W. suggested), but instead of using Lamport or Winternitz one time signatures at the bottom, it uses a hash based few-time signature method; this allows an occasional collision at the very bottom of the tree. ...

8

You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say). Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message. As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a ...

8

If you are not worried about revealing information, then you can commit to the set of data items in one Merkle tree, and to the frontier of that set in another Merkle tree. A frontier is the set of ancestors to all values that are not in the tree (note that this is about the same size as the size of the set itself). Then, in order to prove that a value is ...

8

The document you refer to describes a method for hashing lists of data entries. Assume you do not prepend $0$ or $1$. Then, the hash for the list $(e_1, e_2)$ is $H(h_1 \| h_2)$ for $h_1 = H(e_1)$ and $h_2 = H(e_2)$. It is now easy to find a second preimage of that, namely the "list" with the single entry $h_1 \| h_2$, which will be hashed to $H(h_1 \| h_2)$....

7

With SHA-3 Derived Functions (SP 800-185, pdf) there is now a standardized parallel hash based on SHA-3, called ParallelHash, appropriately. However, it is not a tree hash, but more of a hash-list-based mode. The string to be hashed is divided into equal-sized blocks, which are hashed, concatenated and then hashed again. While it is not a tree hash it ...

7

Updating a Merkle hash tree is trivial. For instance, if you want to update a leaf, then you update it and then update every node on the path from it to the root. If you have a particular operation on the tree in mind, the necessary updates follow immediately from the kind of update you want to do. It's all very straightforward. There's no reason to ...

7

Clearly this depends a lot on your setup. Looking at some numbers: According to Wikipedia SHA-3 requires 12.5 cbp (cycles per byte) on a Core 2. Let's also assume this Core 2 has 2.4 GHz. So we get 2.4 GHz / 12.5 cbp = 192 MB/s for the hash calculation. Let's say you have an SSD with 500 MB/s access speed which is plausible according to the Wikipedia ...

7

A Merkle tree is used for effective retrieving or sending data on the network that you can send/retrieve the data on any order and verify the current data with additional $O(\log n)$-data transmit and in $O(\log n)$-time. Actually, only the root hash is stored $O(1)$. While keeping the root hash any data retrieved/send verified. \begin{array}{lcr} & \...

6

Depending on your trust assumptions about this server, you might be able to use cryptographic accumulators which provide constant-sized (non)membership proofs. However, as far as I know, no efficient strong accumulator scheme has been developed yet. Most accumulator constructions rely on the RSA assumption where the server knows the factorization $n = pq$ ...

6

I want a stateless deterministic pseudorandom generator. I don't see how that can work. "Stateless" - the generator is always in the same state "Deterministic" - given the same state (and inputs, but there's no inputs here), the generator always generates the same output. Hence, you end up with something that always generates the same output; hardly ...

5

The BLAKE3 hash function was just announced today. Internally, it's a Merkle tree.

5

If your data is a set $S$ of key-value pairs, such that $S = \{(k,v) \mathrel\vert k \in K, v \in V\}$, you can have non-membership proofs for your data by using a sorted Merkle tree (sorted by the keys in $K$). This tree can be a binary-search tree, a trie, a sparse Merkle Tree (similar to the one in Micali's Zero Knowledge sets paper, and also ...

5

My understanding is that, for the even more special case where a and b are not only of equal length but some power of two times a fixed block size, all hash tree systems (also called a Merkle tree system or a binary hash chain) meet your criteria. E.g. satisfying following relation h(a || b) = h(a) · h(b), where h(x) is hash function itself, x || y is ...

5

If you look at exact security, the height matters. The reason is that it defines the number of OTS key pairs and hence the possible number of one time signatures per MSS key pair. To forge a MSS signature, it is enough to generate a forgery for 1 out of $2^h$ OTS signatures. Hence you get a reduction in the bit security of $h$ bits.

5

There are few papers like XMSS that try to lower the requirement from collision resistant hash function to second-preimage hash function by introducing bit mask. Actually, that's not why XMSS has the bit masks; as you point out, second preimage resistance is essentially all you need for hash based signatures to be secure; the attacker needs to find a ...

5

Why not use a good old standard database in such cases? Am I missing something? No; you understand it perfectly well! It's nothing more than a particularly strange form of data integrity assurance (that, as you quickly realize, is trivially bypassed if not distributed across multiple nodes). If you're not using it as a resistance to adversarial peers, and ...

4

Hash trees alone wont do that. But hash trees in combination with one time signatures (this is called the Merkle signature scheme). If you use hash based one time signatures such as Lamport-Diffie, then yes. Basically, the hash tree is used to "aggregate" $k$ public keys by representing the hash values of the public keys as leaves of the hash tree and ...

4

Assuming that you know that $h_0$ is the root hash of a Merkle tree for the file, you can be sure that $h_1$ is a hash of a section of the file if you know that it's one of the hashes of the sections one level below the root and you know its sibling hashes, i.e. you have values $(h_1^1, \dots, h_1^{m_1})$ such that $\mathscr{H}(h_1^1, \dots, h_1^{m_1}) = h_0$...

4

With the system as described, the last participant to submit its hash can trivially choose "the random number", knowing the initial value of rootHash and what hashes earlier participant submitted, by choosing the values of the hash s/he submits (s/he computes the XOR of these and $d+10^{10}r$ truncated to the hash width, where $d$ is the desired 10-digit ...

4

Is there any reason why don't more cryptographic hash functions use a Merkle tree-like construction directly instead of just adding them as a way to allow parallelism to existing hash functions on top of the Merkle-Damgård or the Sponge construction? The reason is that a Merkle tree comes with computation overheads that the serial hash functions do ...

4

The benefit of the Merkle Tree is that you store only one element, the top hash. You don't need to store any other elements to verify the data. The hash of each element is in the chain to the top hash. In your proposal, if one needs to get A, then you return Hash(Leaf A) || Hash(Leaf B). But, wait; how one can verify it by the top hash. To verify we need to ...

4

If you don't use a merkle tree then checking membership is an O(n) operation, as opposed to O(log n) with a merkle tree. Instead of going through each item in the set, you walk up one branch of the merkle tree which has O(log n) depth. Though, without sorting, proving non-membership still requires O(n) steps. Sorting makes it possible to prove non-membership ...

3

This is a less formal answer, but describes the same thing as Alin's answer above. Standard binary merkle tree: R / \ N N / \ / \ N N N N / \ / \ / \ / \ 6 3 9 0 8 4 7 2 Verifier knows only R, and for prover to prove membership they have to supply leaves along the path from ...

3

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

3

I'm working on a tree hash based on BLAKE2 that's absolutely not in any way official, but it's exactly the sort of design you described. Maybe this would be useful once it's been properly reviewed and stabilized: https://github.com/oconnor663/bao One of the features of Bao that might be nice for authenticated storage, is that it can verify any part of a ...

3

This is in continuation to Alin's answer, describing accumulators in the context of class groups. Class groups provide a setting where computing roots is computationally difficult. That is, given $x \in \mathbb{Z}$ and $g^x \in G$, it is computationally infeasible to compute $g$. This is the same setting provided by RSA modulus, but with one key difference: ...

3

In general there is no reason to use tree hash modes for Merkle trees. The reason is that a Merkle tree itself is already some kind of tree hash mode. The important thing about this kind of mode is that it allows to compute the root node given the value of one leaf and one node per tree level. The possible ambiguity of hashes is not relevant for hash-based ...

3

I believe that the issue is not what we normally call a second preimage attack on the hash function, but is actually a forgery attack on the system. Suppose that the leaf hash was $H(e)$, and that the Merkle node hash was $h_2 = H(h_0 || h_1)$. In that case, if we see a valid signature that involves a Merkle node computation $h_2 = H(h_0 || h_1)$, we can ...

Only top voted, non community-wiki answers of a minimum length are eligible