2
$\begingroup$

Assume there is a graph $G = (V, E)$ and a hash function $H: V^n \rightarrow \{0,1\}^m$. Given a path $p = (v_1, v_2, ..., v_n)$ from the graph $G$, compute its hash value $H(p) = h_p$.

Question: Given only the value $h_p$ for any path in the graph (or any "non-path" in the graph), can one prove or disprove that the path exists in the graph?

Possible solution: Expand the graph $G$ into a (possibly) infinite Merkle tree considering every vertex in $V$ as the respective root of the tree (designate these $m_v$). Try to match the hash value $h_p$ with all of the $m_v$ trees. If at least one tree can authenticate the $h_p$ value, then the path exists.

Remark: A non-path would be a sequence of vertices that does not correspond to the edges in the graph.

$\endgroup$
  • $\begingroup$ How do you define the hash value $h_p$? $\endgroup$ – baharampuri Jul 27 '15 at 17:01
  • $\begingroup$ This is trivially possible if there are finitely many vertices, so I assume there is an infinite number of vertices - but in this case, there could be infinitely many paths of length $n$, how are you "given" all these hash values? $\endgroup$ – Jesko Hüttenhain Jul 27 '15 at 18:01
  • $\begingroup$ It's a finite graph. You are given the hash values in that you can define the hash function to solve the problem, if it helps. (@baharampuri) It's not trivially possible, since to turn a graph into a tree, (say the graph has a cycle) the resulting tree may be infinitely large. $\endgroup$ – stojanman Jul 27 '15 at 20:31
  • $\begingroup$ What if the hash tells you all vertices are present. Wouldn't you need to show that your graph contains a hamilton path? At least in the case of simple non-backtracking paths... $\endgroup$ – draks ... Jul 28 '15 at 7:22
  • $\begingroup$ Good observation @draks... That means that this problem looks like NP complete. $\endgroup$ – stojanman Jul 28 '15 at 11:17
1
$\begingroup$

If it is a finite graph, the answer is yes, because for fixed $n$ there is only a finite number of paths of length $n$ in the graph. For example, you can enumerate all $n$-tuples of distinct vertices in the graph, check whether they form a path, compute the hash value of that path if they do, and check if that hash occurs in your list of hashes.

$\endgroup$
  • $\begingroup$ Yes, that is the brute-force solution. Is there any other way, so that you do not have to enumerate all paths and hash them? $\endgroup$ – stojanman Jul 28 '15 at 11:15
  • $\begingroup$ At this point you'd need to make the question more formal, I think. What are your exact requirements and what properties does the hash function have? $\endgroup$ – Jesko Hüttenhain Jul 28 '15 at 13:08

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.