Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
15 votes
Accepted

How to to calculate the hash of an unordered set

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 ...
fgrieu's user avatar
  • 142k
12 votes
Accepted

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

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 ...
fgrieu's user avatar
  • 142k
9 votes
Accepted

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

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 ...
Christian Matt's user avatar
8 votes
Accepted

Why using hash trees instead using a single hash value?

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 ...
kelalaka's user avatar
  • 48.7k
7 votes
Accepted

Is hashing large files CPU or I/O bound?

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 ...
Elias's user avatar
  • 4,913
7 votes
Accepted

Is there a standardized tree hash?

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-...
otus's user avatar
  • 32.1k
6 votes

Stateless and deterministic number generation

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, ...
poncho's user avatar
  • 148k
6 votes
Accepted

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

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 ...
poncho's user avatar
  • 148k
6 votes

Is there a standardized tree hash?

The BLAKE3 hash function was just announced today. Internally, it's a Merkle tree.
Jack O'Connor's user avatar
6 votes
Accepted

Proof of membership and non-membership in Merkle tree (Hash-tree)

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 ...
user82867's user avatar
  • 366
5 votes
Accepted

Usefulness of blockchain technology in private sector

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 (...
JamesTheAwesomeDude's user avatar
4 votes

Proof of non-membership on a Merkle tree?

This is a less formal answer, but describes the same thing as Alin's answer above. Standard binary merkle tree: ...
kat's user avatar
  • 173
4 votes

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

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 ...
fgrieu's user avatar
  • 142k
4 votes

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

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 ...
Adam54's user avatar
  • 283
4 votes

Merkle tree motivation

Usually you'd use one hash per file yes, but often torrents consist of multiple files. So you'd have a hash per file and possibly a top level hash to make sure that all the files are present. This way ...
Maarten Bodewes's user avatar
  • 92.9k
4 votes
Accepted

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

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....
kelalaka's user avatar
  • 48.7k
4 votes
Accepted

Concatenation in Merkle Trees

The issue at hand stems from mixing up the hexadecimal string representation ('hexdigest') of a hash value with its actual binary value. Recall first that a hash function takes an arbitrary-length (...
Morrolan's user avatar
  • 1,157
3 votes

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

Nevermind, I just realised that the statement says a concise proof of membership Indicating that the Blockchain has indeed proof of membership, just one not as efficient.
koperandus's user avatar
3 votes

Doubts about Authenticated Data Structures logic

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,...
Changyu Dong's user avatar
  • 4,178
3 votes

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

why would someone use Merkle signatures when they have a perfectly fine one-time signature already? Because Merkle signatures are not one-time. Instead, you can use a private key to sign a number of ...
poncho's user avatar
  • 148k
3 votes

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

There is no known attack that an adversary can mount when he knows a collision for the hash function used in the tree. The reason is that the adversary cannot control the inputs to the hash function ...
mephisto's user avatar
  • 2,908
3 votes
Accepted

Verifying authentication by just using the root of a Merkle tree

If you need to verify all the data, you are going to have to recompute the entire tree, and compare your root with the root you were given. The power of the Merkle tree comes into effect when you only ...
mikeazo's user avatar
  • 38.6k
3 votes

Performing a cryptographically secure HMAC using multiple input parameters

Yes, you can simply concatenate unless the encoding is not canonical, e.g. when the order isn't set or when the dynamic size of the fields make it possible that there is room for overlap between the ...
Maarten Bodewes's user avatar
  • 92.9k
3 votes

Is there a standardized tree hash?

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 ...
Jack O'Connor's user avatar
3 votes

Proving set membership in less than $\log{N}$ bandwidth

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 \...
Snoop Catt's user avatar
  • 1,297
3 votes
Accepted

Tiger Tree Hash vs generic Merkle Tree

The Tiger hash function was mainly a notable thing back in the days as it was designed to make efficient use of 64 bit processors. Besides some other uses, Tiger was (and sometimes still is) often ...
e-sushi's user avatar
  • 17.9k
3 votes

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

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 ...
poncho's user avatar
  • 148k
3 votes
Accepted

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

Looks like the question itself needs some correction. My characterization of what happens in "file sharing" was too simplistic, and adding detail to it explains the matter. eDonkey/eMule in the 00's ...
hmijail's user avatar
  • 161
3 votes
Accepted

Zero knowledge proofs for a Merkle Tree

The "path" is only a witness for your proof; you don't actually want to give the path to the verifier. Turns out that going from a NP-problem with witness to an actual zero-knowledge proof is not that ...
Ruben De Smet's user avatar
3 votes

Order-preserving appending log

This is actually quite a common problem in cryptographic systems. This can be looked at as proving two different things: Is the server currently storing all of the elements a specific client has ...
Cyclic3's user avatar
  • 131

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