11

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

Yes, you should be able to handle this situation readily. There are many optimizations available. One key observation is that if you're going to go to disk, then you might as well read lots of data: it takes just as long to read an entire block of data as to read 1 byte. So, I suggest you store the data on disk in 4096-byte blocks, and do a Merkle tree ...


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


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

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

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


7

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

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


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

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

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

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

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


4

Merkle trees allow several time-memory-tradeoffs: Using larger leaves or store only hashes at a certain level above then leaves. Now you need to hash a bigger leaf for update, but you need to keep fewer intermediate hashes in memory. Using a higher fanout. With fanout=2 you need to keep 2*n hashes in memory. With fanout=4 you only need 1.33*n hashes. But ...


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

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


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


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

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

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

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

First, the passage you refer to is on page 55, 2nd paragraph. And it would also be great if you'd announce that figure 4.1 is actually in a different document ;-) took me quite a while to figure this out. Now to your question. So, I assume you understand the paragraph? You have to note that a round here corresponds to $2^{(i-1)h}$ "whole tree rounds". Now, ...


3

The shorter the hash value the less effort for the attacker to brute force it. If the output is 16bytes then the attacker must spend $2^{128/2}$ "time" to find a collision. If it was 8bytes it would need $2^{64/2}$


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