3
$\begingroup$

Say I have a graph of messages like this:

   A
   |
   B
  / \
 C   D

By including the parent hash in the message to be hashed I can show that B is a child of A, and C and D are children of B.

For example

Hash("This is message A") = ab3ed
Hash("This is message B + ab3ed") = e4c90
Hash("This is message C + e4c90") = 83e39
Hash("This is message D + e4c90") = 456aa

This way I can prove that C and D are children of B, and descendants of A.

Is there a way I can cryptographically prove that a certain node is the only child ie has no siblings?

$\endgroup$
7
  • $\begingroup$ So, how do you prove that B doesn't have a sibling, that is, you don't have a node E with Hash("This is message E + ab3ed") = 31415 ? $\endgroup$
    – poncho
    Oct 26 '15 at 17:06
  • 2
    $\begingroup$ Sounds pretty similar to the double spending problem of digital money. Perhaps you need some kind of blockchain or a global ledger. $\endgroup$
    – user27950
    Oct 26 '15 at 17:35
  • $\begingroup$ Do you have all the data in advance or is it added dynamically? $\endgroup$
    – mikeazo
    Oct 26 '15 at 17:48
  • $\begingroup$ @poncho: Yes, indeed. As it is constructed in the example is impossible to prove that B doesn't have a sibling E. My question can be rephrased as: How can I change the example so that I can prove that B doesn't have a sibling. $\endgroup$
    – Victor
    Oct 26 '15 at 18:04
  • $\begingroup$ @mikeazo: It is added dynamically $\endgroup$
    – Victor
    Oct 26 '15 at 18:05
2
$\begingroup$

Given only the information in the original question, it would be easy for an attacker to calculate generate an arbitrary message E, then calculate the Hash("This is message E + ab3ed") = 31415, and if the system can be tricked into trusting that 31415 is the hash of a valid message, there's no way to prove that E isn't really a valid sibling of B.

This may be why every hash tree implementation I've ever seen doesn't include the hash of the parent in the hash of the child. Instead, it includes the hash of the children in the hash of the parent.

Say I have a graph of messages like this:

   A
   |
   B
  / \
 C   D

By including every child hash in the message to be hashed I can show that B is the only child of A, and C and D are the only children of B.

For example

Hash("This is message A; its child has hash e4c90") = ab3ed
Hash("This is message B; its children have hashes 83e39 and 456aa") = e4c90
Hash("This is message C") = 83e39
Hash("This is message D") = 456aa

Assuming a cryptographically secure hash, and assuming I somehow get the root hash ab3ed from a trusted source, This way I can prove that C and D are the only children of B, and B is the only child of A -- i.e., B has no siblings.

$\endgroup$
1
$\begingroup$

If dynamically added, then I assume you know of the siblings at the time a node needs to be added, and ideally some order to the siblings. If that's all true, then instead of adding the hash of the parent, add the hash of the last sibling. If there are no siblings at insertion time, then revert to adding the parent's hash. So then you'll be able to prove that a node has no siblings if and only if its hash can be recalculated correctly when referencing the parent node's hash.

That should work regardless of any later changes to the siblings' content, unless all siblings are later deleted. Then the function can then only tell you that there used to be siblings at the time a node was added.

$\endgroup$
1
$\begingroup$

I would like to extend Chrystographer answer.

If this is a part of a incoming or outgoing message, you cannot prove it. Anybody can write valid messages. You need Merkle tree and digital signature of the root's hash.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.