Directed Graph Hashing (Directed Graph Hashing)

from arxiv, To be submitted to Algorithmica. Earlier version of paper presented at 51st Southeastern International Conference on Combinatorics, Graph Theory & Computing but was not published in conference proceedings

This paper presents several algorithms for hashing directed graphs. The algorithms given are capable of hashing entire graphs as well as assigning hash values to specific nodes in a given graph. The notion of node symmetry is made precise via computation of vertex orbits and the graph automorphism group, and nodes that are symmetrically identical are assigned equal hashes. We also present a novel Merkle-style hashing algorithm that seeks to fulfill the recursive principle that a hash of a node should depend only on the hash of its neighbors. This algorithm works even in the presence of cycles, which would not be possible with a naive approach. Structurally hashing trees has seen widespread use in blockchain, source code version control, and web applications. Despite the popularity of tree hashing, directed graph hashing remains unstudied in the literature. Our algorithms open new possibilities to hashing both directed graphs and more complex data structures that can be reduced to directed graphs such as hypergraphs.

翻译：本文提出了多种用于哈希有向图的算法。这些算法能够对整个图进行哈希，同时也能够为给定图中的特定节点分配哈希值。通过计算节点轨道和图自同构群，本文明确了节点对称性的概念，并将对称相同的节点分配相等的哈希值。我们还提出了一种新颖的类Merkle哈希算法，它试图遵循一个递归原则：一个节点的哈希仅应取决于其邻居的哈希。即使存在循环，该算法也能够正常工作，这在一种朴素的方法下是不可能的。在区块链、源代码版本控制和Web应用程序中，结构哈希树（或称为Merkle树）已广泛使用。尽管哈希树的流行度很高，但是有向图哈希在文献中仍未得到研究。我们的算法为哈希有向图和更复杂的可简化为有向图的数据结构（例如超图）开辟了新的可能性。