Skip to main content
The 2024 Developer Survey results are live! See the results

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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
69 views

SPHINCS+ signature calculation and FORS public key

I was trying to understand the SPHINCS+ document from https://sphincs.org/data/sphincs+-r3.1-specification.pdf and have the below doubts. Consider the example of SPHINCS+-128s , the value of n,h,d,log(...
Gappu's user avatar
  • 31
1 vote
1 answer
86 views

ADRS in WOTS+ signature scheme

I am trying to understand the sphincs+ from [1] and have a fair understanding of WOTS+ scheme from [2] However, in the OTS scheme defined in [1] , it seem to use ADRS for storing chain address, hash ...
Gappu's user avatar
  • 31
1 vote
0 answers
70 views

How secure is this hash combination function for merkle trees?

I am exploring the class of functions that I have seen called "hash combination functions". These functions are arguably distinct from hash functions, generally providing second-preimage ...
Justin Martin's user avatar
0 votes
1 answer
92 views

What are the statefulness and signature count limits of SPHINCS+?

SPHINCS+ is an interesting post-quantum algorithm, and I'm curious about what its limitations are. What I know about hash-based signature formats in the past are that you needed to remember which ...
Myria's user avatar
  • 2,615
1 vote
1 answer
155 views

Proof of non membership in a Verkle Tree?

According to the author of the original paper[1], Verkle Trees basically let you save space (typically bandwidth, which can be expensive) by replacing a secure hash with a vector commitment scheme, ...
afm's user avatar
  • 111
2 votes
1 answer
110 views

Merkle tree alternating hash and polynomial

I want to get feedback on the security of a modified merkle tree data structure. Using the image above as a reference assume I have a random oracle function $H$. Assume $H$ outputs a value in $\mathbb{...
vimwitch's user avatar
  • 139
1 vote
1 answer
175 views

Can proofs be generated from Merkle Patricia Tries in the same way as merkle trees?

I'm kind of confused about this, I have read that nodes in Merkle Patricia tries are key-value pairs, can someone provide a proof of membership for a data in a Merkle Patricia Trie just as he would ...
Abol_Fa's user avatar
  • 73
-1 votes
1 answer
206 views

Merkle Tree Proofs Implementations

I'm currently implementing a Merkle Tree in Rust. One of the problems I'm facing is the complexity of generating the proof. Meaning the vector I give to the verifier in order to check if an element is ...
Tito's user avatar
  • 1
2 votes
0 answers
45 views

Why use different hash personalization for each level of Merkle tree?

For example zcash uses such approach with Pederesen hash which is collision-resistant, but not preimage-resistant. I assume that it’s used to ensure that we can’t reuse hash from one level which ...
Dulem's user avatar
  • 21
4 votes
1 answer
195 views

Can I get a Merkle proof out of blake3?

The overview of Blake3 states that Blake3 is internally a Merkle tree. Diving a bit deeper into the paper one finds out that Blake3 splits its input in chunks of 1 KiB (1024 B), organizing chunks in a ...
Matteo Monti's user avatar
  • 1,427
2 votes
1 answer
42 views

How to prove that a line belongs to a final hash without knowing/re-hashing all other lines?

Let's suppose : I have a record/database (D) of 754 lines and each line correspond to a SHA256 hash.(Hn) I hash all this record to a final and unique SHA256 hash like this : ...
JeremyDEX's user avatar
0 votes
1 answer
108 views

LMS signatures : Complexity of Classic Merkle Tree Traversal

I'm trying to understand the complexity of computing the Merkle root for stateful hash based signature schemes. Section 4.1 of the chapter on hash based signatures in "Post Quantum Cryptography&...
Rohit Khera's user avatar
1 vote
0 answers
236 views

Complete Binary Merkle Tree and second pre-image attack

To prevent second pre-image attacks, the Merkle Tree implementations I've looked at add a 0 prefix to the leaves and a 1 prefix ...
GuestMeNot's user avatar
0 votes
0 answers
152 views

Is this implementation of Merkle Trees susceptible to second preimage attack?

I am trying to find a good implementation of Merkle Tree generation in Golang, and I need the tree to be resilient to Second Preimage Attack I have found this standard implementation in the golang ...
Barney Chambers's user avatar
2 votes
1 answer
86 views

API design that maximizes the potential of parallel and tree hashing

Traditionally, hash functions are single-threaded, and have the 'Init-Update-Final' API style. This is true of MD5, SHA-1/2/3, BLAKE2, to name a few. However, there have been proposal of parallel hash ...
DannyNiu's user avatar
  • 9,519
1 vote
0 answers
84 views

Is there any structure similar to GGM but more efficient?

Although Goldreich-Godlwasser-Micali (GGM) construction of a pseudo-random function (PRF) from a pseudo-random number generator (PRNG) is widely in many cryptographic applications, it needs to consume ...
user102777's user avatar
0 votes
1 answer
82 views

How come we only need to generate the first tree in each layer in XMSS MT

From what I understand, to reduce the time taken for public key generation, you can use nested trees in XMSS to form Multi-tree XMSS. For an instantion of 2 layers, it seems that the leaf of each L ...
João Diogo Duarte's user avatar
1 vote
2 answers
918 views

Concatenation in Merkle Trees

Consider a simple Merkle Tree with leaves alice +100 and bob +50. Using the SHA256 hash algorithm, the digest of the respective ...
onlyphantom's user avatar
0 votes
1 answer
477 views

Storing data in a Merkle tree

I had the idea of storing large amounts of data in a small space using a Merkle tree. But from what I understand about Merkle trees is you cannot extract the data from the Merkle root (since hashes ...
Apollo 11's user avatar
0 votes
1 answer
168 views

Verifying Merkle root correctness without completely reconstructing the tree

Lets say Alice has a list of values, and Bob sends Alice a Merkle root that he claims is for this list of values. The Merkle tree construction algorithm is mutually known of course. Alice can then ...
Adam Ierymenko's user avatar
1 vote
2 answers
404 views

Commitment scheme for a possible unordered growing collection of elements

Merkle trees can be used for vector commitment scheme. In particular given two sequences S, S' with the same elements in the same order the merkle root for S will be the same as the one for S'. What ...
mr_bovo's user avatar
  • 11
1 vote
1 answer
171 views

Usefulness of blockchain technology in private sector [closed]

I understand that blockchain technology works for cryptocurrency. But I don't get why it should be used in private sector. For example, I often read that it is useful to monitor the supply chain of ...
DanielG's user avatar
  • 121
1 vote
1 answer
220 views

Building content-defined chunking with adversarial data preserving guarantees on splitting probability and global stability

I'm using the Prolly tree data structure. This structure operates on serialized data which it chunks at the byte level into pieces. To build trees recursively, the list of chunk hashes is itself ...
trenta3's user avatar
  • 43
1 vote
1 answer
332 views

Speeding up XMSS

To compute the XMSS Tree root, one needs to compute all the 2^h keys and hash them together. The higher the height of the tree, the more keys there are and the longer the KeyGen computation. The ...
silverwater_mikali's user avatar
1 vote
1 answer
307 views

What exactly is the purpose of the multi-tree variant in hash-based schemes?

In hash-based signature schemes that use Merkle trees (e.g. XMSS), what is exactly the purpose of the multi-tree variant? Seems like the same number of keys can be represented by a single larger tree? ...
doc's user avatar
  • 123
0 votes
2 answers
467 views

Winternitz Parameter in WOTS+ and XMSS

What is the parameter for? I read that in XMSS it is a member of the set {4, 16}, but what does it exactly mean? I also read that the bigger the $w$ parameter, the shorter the signatures but the ...
user86443's user avatar
7 votes
1 answer
660 views

Why using hash trees instead using a single hash value?

If one have files $x_1, x_2, .., x_n$. What are the benefits of using hashing trees $-$ also known as Merkle trees $-$ (for example in git) instead of computing one hash value $h(x_1,x_2,..,x_n)$ ?
funidentifier's user avatar
1 vote
1 answer
190 views

Can we use a Merkle Tree structure to reduce digest size?

A 2nd preimage attack is possible on the standard Merkle tree as pictured below. I'm aware that we can add identifiers (to differentiate nodes) to the input of each hash as discussed in the link. If ...
Modal Nest's user avatar
  • 1,453
2 votes
2 answers
152 views

Can we place the WOTS scheme into a Merkle tree structure?

In post-quantum signature schemes that are (to put it simply) built out of merkle trees, they usually employ some sort of OTS scheme on the very bottom leaves. I.e WOTS Winternitz scheme. A ...
Modal Nest's user avatar
  • 1,453
0 votes
1 answer
44 views

Invalidate a hash of a sequence of values given only the first N elements of a sequence?

I want to develop a system where before some activity is performed, the user is sent a hash of a sequence of values which will be an inputs to the activity. The number of possible values is fixed and ...
C R Johnson's user avatar
6 votes
1 answer
3k views

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

If we just know the Merkle root and the data block and we want to know this block is a member of this merkle tree. We need to know all the blocks from the leaf to the root that are associated with ...
Sai Teja T's user avatar
0 votes
1 answer
154 views

How SPHINCS+ Hash Signature ADRS structure define

can anyone help me to elaborate the structure of ADRS with example ( tree ADRS, layer ADRS, keypair ADRS etc)used to generate root SPHINCS+ signature. Also can some one help me to describe tree hash ...
Anonymous's user avatar
0 votes
0 answers
76 views

Hash chain based secret revealing using homorphic princples?

I have recently been looking into Homomorphic encryption and I am looking for a specific hash-based encryption/decryption scheme. I don't need a full implementation but I am not sure if what I want ...
ovanwijk's user avatar
  • 155
1 vote
1 answer
71 views

Order-preserving appending log

Sorry for not having a better name, but I cannot seem to find a better name. Each client will append an element $a_i$ to the server at some time, and the server keeps appending the element to the ...
DiamondDuck's user avatar
0 votes
0 answers
23 views

How to disperse personal data before returning?

I am working on a project that is dealing with personal data. The task is to find a method such that when user makes a query into multiple institutions, the result will contain already scattered/...
AverageJoe9000's user avatar
3 votes
1 answer
2k views

Merkle Tree space complexity

When searching by using the Merkle tree, the time complexity is $\mathcal O(\log n)$ but I don't understand how space complexity is $\mathcal O(n)$. In my opinion, it should be also $\mathcal O(\log n)...
jhdm's user avatar
  • 187
1 vote
1 answer
230 views

Merkle tree vs chronological merkle tree

I've been reading some papers about using blockchain in VANETs (Vehicular Adhoc Networks). Some of them have mentioned something called a chronological merkle tree (CMT). Is this different from the ...
Abol_Fa's user avatar
  • 73
3 votes
1 answer
401 views

Proof of membership on a merkle tree

I read the zcash paper recently. But I have been puzzled by a question. How did the authors prove that the coin commitment appears as a leaf of a Merkle tree with root rt? Apparently, the authors ...
Xin's user avatar
  • 61
1 vote
0 answers
50 views

Security of querying multiple Merkle trees

Suppose Alice has committed to several sets of values using Merkle trees. For example, let's say there are 2 sets of values, and each set represents leaves of a separate tree like this: $a_0, a_1 ......
irakliy's user avatar
  • 979
0 votes
0 answers
92 views

Could this Method be Used to Create a highly Compressed Alternative to Merkle Proofs?

See equation below as I see an easier alternative, as I'm having trouble explaining it. Is there a hash function where many hashes can be combined together in a way where any single hash can be ...
mczarnek's user avatar
  • 203
0 votes
1 answer
799 views

would parallel crypto mining work

Hi everyone I was wondering would it be possible to mine a cryptocurrency like bitcoin in parallel. I have read a little about mining pools https://en.wikipedia.org/wiki/Mining_pool , But that's not ...
ACRS3044's user avatar
2 votes
2 answers
658 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 ...
knowads's user avatar
  • 123
0 votes
0 answers
534 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 ...
user1870400's user avatar
5 votes
1 answer
3k 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 ...
user2505282's user avatar
1 vote
1 answer
147 views

Provable data possession (PDP) VS Merkle tree

In the paper Provable Data Possession at Untrusted Stores, there is a mechanism that allows a client to efficiently check if the server still has the client's data. They define two constraints for ...
user153465's user avatar
  • 1,583
1 vote
0 answers
117 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 ...
Bernd Strehl's user avatar
3 votes
1 answer
798 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 ...
hmijail's user avatar
  • 161
2 votes
1 answer
172 views

Merkle tree motivation

In this Hacker Noon article, the author seems to give an overview of Merkle trees. However, I have one problem. The author claims you can use Merkle trees to verify the authenticity of data, e.g., if ...
dave's user avatar
  • 21
1 vote
0 answers
134 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 ...
aaa's user avatar
  • 11
1 vote
1 answer
441 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)$ ...
Infinity's user avatar
  • 585