Why do the non-leaf Nodes of Merkle tree need to be hashed?Question about hash collisionsWhy is EdDSA collision-resilient with SHA-512?Merkle hash tree updatesWhy the $IV$ used in Merkle–Damgård has to be fixed to a specific value?Why can't we use a hash with no collision to compress data reliably?Questions regarding parallel AES CTR with merkle treesWhat happens if I modify the Merkle–Damgård hash method?Why the contrapositive proves a given hash is collision resistant?Merkle-like hash tree that mirrors existing tree structureIs there a hash tree scheme designed for complex data structures?
How to cope with regret and shame about not fully utilizing opportunities during PhD?
How about space ziplines
Single word that parallels "Recent" when discussing the near future
Were any toxic metals used in the International Space Station?
How do I identify the partitions of my hard drive in order to then shred them all?
Why did the soldiers of the North disobey Jon?
Why does the headset man not get on the tractor?
Would life always name the light from their sun "white"
Can a tourist shoot a gun for recreational purpose in the USA?
Why does SSL Labs now consider CBC suites weak?
Can only the master initiate communication in SPI whereas in I2C the slave can also initiate the communication?
Can multiple outlets be directly attached to a single breaker?
How to make a not so good looking person more appealing?
Developers demotivated due to working on same project for more than 2 years
Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?
How might a landlocked lake become a complete ecosystem?
A case where Bishop for knight isn't a good trade
Adding labels and comments to a matrix
Why are BJTs common in output stages of power amplifiers?
Can my Serbian girlfriend apply for a UK Standard Visitor visa and stay for the whole 6 months?
complicated arrows in flowcharts
"The van's really booking"
What is this old US Air Force plane?
Acronyms in HDD specification
Why do the non-leaf Nodes of Merkle tree need to be hashed?
Question about hash collisionsWhy is EdDSA collision-resilient with SHA-512?Merkle hash tree updatesWhy the $IV$ used in Merkle–Damgård has to be fixed to a specific value?Why can't we use a hash with no collision to compress data reliably?Questions regarding parallel AES CTR with merkle treesWhat happens if I modify the Merkle–Damgård hash method?Why the contrapositive proves a given hash is collision resistant?Merkle-like hash tree that mirrors existing tree structureIs there a hash tree scheme designed for complex data structures?
$begingroup$
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 advantageous over just Hash(Leaf A) || Hash(Leaf B)
. I understand that a hash can't be any more collision resistant than it's input, so why can't we just return the concatenation as opposed to double hashing again? Is it just to make the result a fixed size again?
hash collision-resistance hash-tree
New contributor
$endgroup$
add a comment |
$begingroup$
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 advantageous over just Hash(Leaf A) || Hash(Leaf B)
. I understand that a hash can't be any more collision resistant than it's input, so why can't we just return the concatenation as opposed to double hashing again? Is it just to make the result a fixed size again?
hash collision-resistance hash-tree
New contributor
$endgroup$
add a comment |
$begingroup$
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 advantageous over just Hash(Leaf A) || Hash(Leaf B)
. I understand that a hash can't be any more collision resistant than it's input, so why can't we just return the concatenation as opposed to double hashing again? Is it just to make the result a fixed size again?
hash collision-resistance hash-tree
New contributor
$endgroup$
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 advantageous over just Hash(Leaf A) || Hash(Leaf B)
. I understand that a hash can't be any more collision resistant than it's input, so why can't we just return the concatenation as opposed to double hashing again? Is it just to make the result a fixed size again?
hash collision-resistance hash-tree
hash collision-resistance hash-tree
New contributor
New contributor
edited May 9 at 18:30
kelalaka
9,23232352
9,23232352
New contributor
asked May 9 at 18:18
knowadsknowads
1133
1133
New contributor
New contributor
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
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 store Hash(Leaf A) || Hash(Leaf B)
. So there will be many elements to store. Thus, if you stick the Merkles' idea you will have the benefit.
For the comments;
The layer of hashing is necessary since we can store only one element the top hash and we can return only the intended element since the elements are on the leaf level we only need to transfer the requested leaf and path the root hash.
Some purposes: Memory verifications against fault attacks. Also, storing files on the cloud. This will prevent the rollback attack, i.e. an attacker replaces the old version of a file. The Merkle Tree enables detection with negligible false acceptance.
$endgroup$
$begingroup$
Okay so it's purely for storage purposes then? I"m still not clear on why another layer of hashing is necessary, as opposed to a simpler operation. If for example you stored Hash(Leaf A) + Hash(Leaf B) or maybe Hash(Leaf A) XOR Hash(Leaf B) you would end up with 1 result still?
$endgroup$
– knowads
May 9 at 19:45
$begingroup$
Ok I see that the concatenation requires more storage but why could you just use the XOR of Hash(Leaf A) and Hash(Leaf B)? A 256 bit value XOR a 256 bit value is still 256 bits. How is this worse than Hashing them again?
$endgroup$
– knowads
May 9 at 20:38
1
$begingroup$
What if the elements are the same? then we will see the hash of 0. Also, with $oplus$ one can play the order of elements.
$endgroup$
– kelalaka
May 9 at 20:47
$begingroup$
@knowads: XOR would be insecure, as anyone could generate an authentication path 'proving' anything they want (by selecting the appropriate value in the authentication path they provide)
$endgroup$
– poncho
May 9 at 20:58
add a comment |
$begingroup$
In the Merkle tree idea, the internal node combination function is more like Hash( X || Y )
, where X
and Y
are the values of the child nodes.
The idea is that you can prove that X
is the value you originally committed to by displaying only Y
(and in an $n$ level tree, only $n$ values).
The complication that comes in is where we might not want to reveal leaf nodes other than the one we're showing; the straight-forward implementation of the above idea would require us to reveal the value of the leaf adjacent to the one we're proving.
To get around this, we hash each leaf node first, and then supply those hashes to the Merkle tree. So, one way to express this is that the bottom level is Hash( Hash(X) || Hash(Y) )
; that way, to give the authentication path, we show Hash(Y)
and not the actual Y
value.
This initial hash only applies to the bottom (leaf) nodes; everything else can be done simpler (because we don't care if someone learns the value of intermediate Merkle nodes)
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
knowads is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f70440%2fwhy-do-the-non-leaf-nodes-of-merkle-tree-need-to-be-hashed%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
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 store Hash(Leaf A) || Hash(Leaf B)
. So there will be many elements to store. Thus, if you stick the Merkles' idea you will have the benefit.
For the comments;
The layer of hashing is necessary since we can store only one element the top hash and we can return only the intended element since the elements are on the leaf level we only need to transfer the requested leaf and path the root hash.
Some purposes: Memory verifications against fault attacks. Also, storing files on the cloud. This will prevent the rollback attack, i.e. an attacker replaces the old version of a file. The Merkle Tree enables detection with negligible false acceptance.
$endgroup$
$begingroup$
Okay so it's purely for storage purposes then? I"m still not clear on why another layer of hashing is necessary, as opposed to a simpler operation. If for example you stored Hash(Leaf A) + Hash(Leaf B) or maybe Hash(Leaf A) XOR Hash(Leaf B) you would end up with 1 result still?
$endgroup$
– knowads
May 9 at 19:45
$begingroup$
Ok I see that the concatenation requires more storage but why could you just use the XOR of Hash(Leaf A) and Hash(Leaf B)? A 256 bit value XOR a 256 bit value is still 256 bits. How is this worse than Hashing them again?
$endgroup$
– knowads
May 9 at 20:38
1
$begingroup$
What if the elements are the same? then we will see the hash of 0. Also, with $oplus$ one can play the order of elements.
$endgroup$
– kelalaka
May 9 at 20:47
$begingroup$
@knowads: XOR would be insecure, as anyone could generate an authentication path 'proving' anything they want (by selecting the appropriate value in the authentication path they provide)
$endgroup$
– poncho
May 9 at 20:58
add a comment |
$begingroup$
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 store Hash(Leaf A) || Hash(Leaf B)
. So there will be many elements to store. Thus, if you stick the Merkles' idea you will have the benefit.
For the comments;
The layer of hashing is necessary since we can store only one element the top hash and we can return only the intended element since the elements are on the leaf level we only need to transfer the requested leaf and path the root hash.
Some purposes: Memory verifications against fault attacks. Also, storing files on the cloud. This will prevent the rollback attack, i.e. an attacker replaces the old version of a file. The Merkle Tree enables detection with negligible false acceptance.
$endgroup$
$begingroup$
Okay so it's purely for storage purposes then? I"m still not clear on why another layer of hashing is necessary, as opposed to a simpler operation. If for example you stored Hash(Leaf A) + Hash(Leaf B) or maybe Hash(Leaf A) XOR Hash(Leaf B) you would end up with 1 result still?
$endgroup$
– knowads
May 9 at 19:45
$begingroup$
Ok I see that the concatenation requires more storage but why could you just use the XOR of Hash(Leaf A) and Hash(Leaf B)? A 256 bit value XOR a 256 bit value is still 256 bits. How is this worse than Hashing them again?
$endgroup$
– knowads
May 9 at 20:38
1
$begingroup$
What if the elements are the same? then we will see the hash of 0. Also, with $oplus$ one can play the order of elements.
$endgroup$
– kelalaka
May 9 at 20:47
$begingroup$
@knowads: XOR would be insecure, as anyone could generate an authentication path 'proving' anything they want (by selecting the appropriate value in the authentication path they provide)
$endgroup$
– poncho
May 9 at 20:58
add a comment |
$begingroup$
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 store Hash(Leaf A) || Hash(Leaf B)
. So there will be many elements to store. Thus, if you stick the Merkles' idea you will have the benefit.
For the comments;
The layer of hashing is necessary since we can store only one element the top hash and we can return only the intended element since the elements are on the leaf level we only need to transfer the requested leaf and path the root hash.
Some purposes: Memory verifications against fault attacks. Also, storing files on the cloud. This will prevent the rollback attack, i.e. an attacker replaces the old version of a file. The Merkle Tree enables detection with negligible false acceptance.
$endgroup$
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 store Hash(Leaf A) || Hash(Leaf B)
. So there will be many elements to store. Thus, if you stick the Merkles' idea you will have the benefit.
For the comments;
The layer of hashing is necessary since we can store only one element the top hash and we can return only the intended element since the elements are on the leaf level we only need to transfer the requested leaf and path the root hash.
Some purposes: Memory verifications against fault attacks. Also, storing files on the cloud. This will prevent the rollback attack, i.e. an attacker replaces the old version of a file. The Merkle Tree enables detection with negligible false acceptance.
edited May 9 at 21:16
answered May 9 at 18:29
kelalakakelalaka
9,23232352
9,23232352
$begingroup$
Okay so it's purely for storage purposes then? I"m still not clear on why another layer of hashing is necessary, as opposed to a simpler operation. If for example you stored Hash(Leaf A) + Hash(Leaf B) or maybe Hash(Leaf A) XOR Hash(Leaf B) you would end up with 1 result still?
$endgroup$
– knowads
May 9 at 19:45
$begingroup$
Ok I see that the concatenation requires more storage but why could you just use the XOR of Hash(Leaf A) and Hash(Leaf B)? A 256 bit value XOR a 256 bit value is still 256 bits. How is this worse than Hashing them again?
$endgroup$
– knowads
May 9 at 20:38
1
$begingroup$
What if the elements are the same? then we will see the hash of 0. Also, with $oplus$ one can play the order of elements.
$endgroup$
– kelalaka
May 9 at 20:47
$begingroup$
@knowads: XOR would be insecure, as anyone could generate an authentication path 'proving' anything they want (by selecting the appropriate value in the authentication path they provide)
$endgroup$
– poncho
May 9 at 20:58
add a comment |
$begingroup$
Okay so it's purely for storage purposes then? I"m still not clear on why another layer of hashing is necessary, as opposed to a simpler operation. If for example you stored Hash(Leaf A) + Hash(Leaf B) or maybe Hash(Leaf A) XOR Hash(Leaf B) you would end up with 1 result still?
$endgroup$
– knowads
May 9 at 19:45
$begingroup$
Ok I see that the concatenation requires more storage but why could you just use the XOR of Hash(Leaf A) and Hash(Leaf B)? A 256 bit value XOR a 256 bit value is still 256 bits. How is this worse than Hashing them again?
$endgroup$
– knowads
May 9 at 20:38
1
$begingroup$
What if the elements are the same? then we will see the hash of 0. Also, with $oplus$ one can play the order of elements.
$endgroup$
– kelalaka
May 9 at 20:47
$begingroup$
@knowads: XOR would be insecure, as anyone could generate an authentication path 'proving' anything they want (by selecting the appropriate value in the authentication path they provide)
$endgroup$
– poncho
May 9 at 20:58
$begingroup$
Okay so it's purely for storage purposes then? I"m still not clear on why another layer of hashing is necessary, as opposed to a simpler operation. If for example you stored Hash(Leaf A) + Hash(Leaf B) or maybe Hash(Leaf A) XOR Hash(Leaf B) you would end up with 1 result still?
$endgroup$
– knowads
May 9 at 19:45
$begingroup$
Okay so it's purely for storage purposes then? I"m still not clear on why another layer of hashing is necessary, as opposed to a simpler operation. If for example you stored Hash(Leaf A) + Hash(Leaf B) or maybe Hash(Leaf A) XOR Hash(Leaf B) you would end up with 1 result still?
$endgroup$
– knowads
May 9 at 19:45
$begingroup$
Ok I see that the concatenation requires more storage but why could you just use the XOR of Hash(Leaf A) and Hash(Leaf B)? A 256 bit value XOR a 256 bit value is still 256 bits. How is this worse than Hashing them again?
$endgroup$
– knowads
May 9 at 20:38
$begingroup$
Ok I see that the concatenation requires more storage but why could you just use the XOR of Hash(Leaf A) and Hash(Leaf B)? A 256 bit value XOR a 256 bit value is still 256 bits. How is this worse than Hashing them again?
$endgroup$
– knowads
May 9 at 20:38
1
1
$begingroup$
What if the elements are the same? then we will see the hash of 0. Also, with $oplus$ one can play the order of elements.
$endgroup$
– kelalaka
May 9 at 20:47
$begingroup$
What if the elements are the same? then we will see the hash of 0. Also, with $oplus$ one can play the order of elements.
$endgroup$
– kelalaka
May 9 at 20:47
$begingroup$
@knowads: XOR would be insecure, as anyone could generate an authentication path 'proving' anything they want (by selecting the appropriate value in the authentication path they provide)
$endgroup$
– poncho
May 9 at 20:58
$begingroup$
@knowads: XOR would be insecure, as anyone could generate an authentication path 'proving' anything they want (by selecting the appropriate value in the authentication path they provide)
$endgroup$
– poncho
May 9 at 20:58
add a comment |
$begingroup$
In the Merkle tree idea, the internal node combination function is more like Hash( X || Y )
, where X
and Y
are the values of the child nodes.
The idea is that you can prove that X
is the value you originally committed to by displaying only Y
(and in an $n$ level tree, only $n$ values).
The complication that comes in is where we might not want to reveal leaf nodes other than the one we're showing; the straight-forward implementation of the above idea would require us to reveal the value of the leaf adjacent to the one we're proving.
To get around this, we hash each leaf node first, and then supply those hashes to the Merkle tree. So, one way to express this is that the bottom level is Hash( Hash(X) || Hash(Y) )
; that way, to give the authentication path, we show Hash(Y)
and not the actual Y
value.
This initial hash only applies to the bottom (leaf) nodes; everything else can be done simpler (because we don't care if someone learns the value of intermediate Merkle nodes)
$endgroup$
add a comment |
$begingroup$
In the Merkle tree idea, the internal node combination function is more like Hash( X || Y )
, where X
and Y
are the values of the child nodes.
The idea is that you can prove that X
is the value you originally committed to by displaying only Y
(and in an $n$ level tree, only $n$ values).
The complication that comes in is where we might not want to reveal leaf nodes other than the one we're showing; the straight-forward implementation of the above idea would require us to reveal the value of the leaf adjacent to the one we're proving.
To get around this, we hash each leaf node first, and then supply those hashes to the Merkle tree. So, one way to express this is that the bottom level is Hash( Hash(X) || Hash(Y) )
; that way, to give the authentication path, we show Hash(Y)
and not the actual Y
value.
This initial hash only applies to the bottom (leaf) nodes; everything else can be done simpler (because we don't care if someone learns the value of intermediate Merkle nodes)
$endgroup$
add a comment |
$begingroup$
In the Merkle tree idea, the internal node combination function is more like Hash( X || Y )
, where X
and Y
are the values of the child nodes.
The idea is that you can prove that X
is the value you originally committed to by displaying only Y
(and in an $n$ level tree, only $n$ values).
The complication that comes in is where we might not want to reveal leaf nodes other than the one we're showing; the straight-forward implementation of the above idea would require us to reveal the value of the leaf adjacent to the one we're proving.
To get around this, we hash each leaf node first, and then supply those hashes to the Merkle tree. So, one way to express this is that the bottom level is Hash( Hash(X) || Hash(Y) )
; that way, to give the authentication path, we show Hash(Y)
and not the actual Y
value.
This initial hash only applies to the bottom (leaf) nodes; everything else can be done simpler (because we don't care if someone learns the value of intermediate Merkle nodes)
$endgroup$
In the Merkle tree idea, the internal node combination function is more like Hash( X || Y )
, where X
and Y
are the values of the child nodes.
The idea is that you can prove that X
is the value you originally committed to by displaying only Y
(and in an $n$ level tree, only $n$ values).
The complication that comes in is where we might not want to reveal leaf nodes other than the one we're showing; the straight-forward implementation of the above idea would require us to reveal the value of the leaf adjacent to the one we're proving.
To get around this, we hash each leaf node first, and then supply those hashes to the Merkle tree. So, one way to express this is that the bottom level is Hash( Hash(X) || Hash(Y) )
; that way, to give the authentication path, we show Hash(Y)
and not the actual Y
value.
This initial hash only applies to the bottom (leaf) nodes; everything else can be done simpler (because we don't care if someone learns the value of intermediate Merkle nodes)
answered May 9 at 20:53
ponchoponcho
95.4k2153249
95.4k2153249
add a comment |
add a comment |
knowads is a new contributor. Be nice, and check out our Code of Conduct.
knowads is a new contributor. Be nice, and check out our Code of Conduct.
knowads is a new contributor. Be nice, and check out our Code of Conduct.
knowads is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f70440%2fwhy-do-the-non-leaf-nodes-of-merkle-tree-need-to-be-hashed%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown