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.
96
questions
0
votes
1
answer
40
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 ...
- 2,513
1
vote
1
answer
77
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, ...
- 111
0
votes
0
answers
18
views
Data structures for linking blockchain accounts
I want to use a data structure like merkle tree in a hypothetical blockchain that, if needed, can fast check whether a wallet/account has received directly or indirectly from a specific list of ...
- 1
2
votes
1
answer
81
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{...
- 139
1
vote
1
answer
95
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 ...
- 73
-1
votes
1
answer
112
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 ...
- 1
2
votes
0
answers
41
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 ...
- 21
4
votes
1
answer
118
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 ...
- 1,375
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 : ...
- 51
0
votes
1
answer
75
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&...
- 678
1
vote
0
answers
196
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 ...
- 11
0
votes
0
answers
130
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 ...
- 103
2
votes
1
answer
81
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 ...
- 9,001
1
vote
0
answers
81
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 ...
- 33
0
votes
1
answer
61
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 ...
- 25
1
vote
2
answers
714
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 ...
- 113
0
votes
1
answer
348
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 ...
0
votes
1
answer
124
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 ...
- 896
1
vote
2
answers
349
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 ...
- 11
1
vote
1
answer
159
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 ...
- 121
1
vote
1
answer
197
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 ...
- 43
1
vote
1
answer
272
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 ...
1
vote
1
answer
244
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? ...
- 123
0
votes
2
answers
372
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 ...
- 41
7
votes
1
answer
619
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)$ ?
1
vote
1
answer
182
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 ...
- 1,443
2
votes
2
answers
131
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 ...
- 1,443
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 ...
- 101
6
votes
1
answer
2k
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 ...
- 183
0
votes
1
answer
139
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 ...
0
votes
0
answers
73
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 ...
- 135
1
vote
1
answer
64
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 ...
- 403
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/...
- 101
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)...
- 187
1
vote
1
answer
202
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 ...
- 73
3
votes
1
answer
337
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 ...
- 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 ......
- 969
0
votes
0
answers
87
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 ...
- 203
0
votes
1
answer
734
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 ...
- 15
2
votes
2
answers
594
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 ...
- 123
0
votes
0
answers
489
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 ...
- 123
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 ...
- 259
1
vote
1
answer
144
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 ...
- 1,573
1
vote
0
answers
100
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 ...
- 161
3
votes
1
answer
750
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 ...
- 161
2
votes
1
answer
164
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 ...
- 21
1
vote
0
answers
125
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 ...
- 11
1
vote
1
answer
385
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)$
...
- 575
0
votes
1
answer
58
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. ...
- 11
0
votes
1
answer
240
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 ...
- 31