Mdthbs

Cryptography and elliptic curves

Why was wildfire not used during the Battle of Winterfell?

Was Mohammed the most popular first name for boys born in Berlin in 2018?

How to select certain lines (n, n+4, n+8, n+12...) from the file?

Two researchers want to work on the same extension to my paper. Who to help?

Are there non-military uses of 20%-enriched Uranium?

Names of the Six Tastes

What's the "magic similar to the Knock spell" referenced in the Dungeon of the Mad Mage adventure?

Windows OS quantum vs. SQL OS Quantum

Intersecting with the x-axis / intersecting the x-axis

Why was the ancient one so hesitant to teach Dr Strange the art of sorcery

Is ‘despite that’ right?

date -d 'previous Monday" to display the preceding Monday

How to slow yourself down (for playing nice with others)

How to efficiently lower your karma

Ex-manager wants to stay in touch, I don't want to

When quoting someone, is it proper to change "gotta" to "got to" without modifying the rest of the quote?

Should I pay on student loans in deferment or continue to snowball other debts?

Is there a need for better software for writers?

Extending Kan fibrations, without using minimal fibrations

Exception propagation: When to catch exceptions?

Is there an application which does HTTP PUT?

How is CoreiX like Corei5, i7 is related to Haswell, Ivy Bridge?

Best species to breed to intelligence

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?

2

$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

share|improve this question

edited 8 hours ago

kelalaka

9,21032352

asked 8 hours ago

knowadsknowads

1133

New contributor

knowads is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

2

$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

share|improve this question

edited 8 hours ago

kelalaka

9,21032352

asked 8 hours ago

knowadsknowads

1133

New contributor

knowads is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$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

share|improve this question

edited 8 hours ago

kelalaka

9,21032352

asked 8 hours ago

knowadsknowads

1133

New contributor

knowads is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|improve this question

edited 8 hours ago

kelalaka

9,21032352

asked 8 hours ago

knowadsknowads

1133

New contributor

knowads is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this question

edited 8 hours ago

kelalaka

9,21032352

asked 8 hours ago

knowadsknowads

1133

New contributor

knowads is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited 8 hours ago

kelalaka

9,21032352

edited 8 hours ago

kelalaka

9,21032352

asked 8 hours ago

knowadsknowads

1133

New contributor

knowads is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 8 hours ago

knowadsknowads

1133

2 Answers
2

active

oldest

votes

3

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

share|improve this answer

edited 5 hours ago

answered 8 hours ago

kelalakakelalaka

9,21032352

$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
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  6 hours ago
  

  
  
  
  

add a comment | 

1

$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)

share|improve this answer

answered 6 hours ago

ponchoponcho

95.2k2153249

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

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

3

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

share|improve this answer

edited 5 hours ago

answered 8 hours ago

kelalakakelalaka

9,21032352

$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
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  6 hours ago
  

  
  
  
  

add a comment | 

3

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

share|improve this answer

edited 5 hours ago

answered 8 hours ago

kelalakakelalaka

9,21032352

$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
  7 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  6 hours ago
  

  
  
  
  

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.

share|improve this answer

edited 5 hours ago

answered 8 hours ago

kelalakakelalaka

9,21032352

$endgroup$

share|improve this answer

edited 5 hours ago

answered 8 hours ago

kelalakakelalaka

9,21032352

answered 8 hours ago

kelalakakelalaka

9,21032352

answered 8 hours ago

kelalakakelalaka

9,21032352

1

$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)

share|improve this answer

answered 6 hours ago

ponchoponcho

95.2k2153249

$endgroup$

add a comment | 

1

$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)

share|improve this answer

answered 6 hours ago

ponchoponcho

95.2k2153249

$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)

share|improve this answer

answered 6 hours ago

ponchoponcho

95.2k2153249

$endgroup$

share|improve this answer

answered 6 hours ago

ponchoponcho

95.2k2153249

answered 6 hours ago

ponchoponcho

95.2k2153249

answered 6 hours ago

ponchoponcho

95.2k2153249