3
$\begingroup$

Context:

I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's children. Additionally, I'd like to be able to replace one of the node's children in constant time (i.e., not doing a full recombination of hash values) as the branching factor for the tree could be quite large.

Question:

I am looking for a set of functions ($combine$, $separate$) that operate on fixed width integers and have the following properties.

Let $X$ be some set of integers with fixed width $b$.

(1) $combine(X)$ outputs an integer with width $b$

(2) $combine(X)$ operates in $O(|X|)$ time complexity

(3) $$combine\Bigl(\left\{t, separate\bigl(combine(X), x\bigr)\right\}\Bigr) = combine\Bigl(\bigl(X \setminus \{x\}\bigr) \cup \{t\}\Bigr)$$ where $x \in X$ and $t$ is some integer of width $b$.

(4) $separate(X, x)$ operates in $O(1)$ time complexity

(5) The outputs of $combine$ are going to be used as hash values so an algorithm with a "good" distribution of output values to avoid collisions is ideal. That said, I'd define good as anything better than trivial addition and subtraction (see below).

Initial thoughts:

A trivial implementation would have $combine$ and $separate$ be addition and subtraction (with some modulo logic); however, this obviously won't have a good distribution for tightly bunched input values.

$\endgroup$
2
$\begingroup$

A simple approach is to use the sum of hashes, e.g.,

$$\begin{align*} \text{combine}(X) &= \sum_{x \in X} H(x)\\ \text{separate}(y,x) &= s - H(x) \end{align*}$$

where $H(\cdot)$ is some good hash function. To make the result suitable as a hash, I recommend that you hash the output of combine one more time before using it as a hash value.

More generally, you can use any commutative hash function. See, e.g., https://crypto.stackexchange.com/q/6497/351 and https://crypto.stackexchange.com/q/11420/351 and https://crypto.stackexchange.com/q/54544/351 and Which fingerprinting/hashing algorithms support compounding?.

Another approach is to use a Merkle hash tree. Store the list of children in a Merkle hash tree, one mini Merkle hash tree per node of your tree (i.e., a binary tree whose leaves are the children of the node, and where each internal node is augmented with the hash of the values in its two children, and the value in the root of hte Merkle tree is the hash of that node of your tree). This allows $O(\lg n)$ updates rather than $O(1)$ updates, but that might be good enough.

$\endgroup$
  • $\begingroup$ Thanks for the response. I see you've written a couple of answers on similar subjects, and if you don't mind sharing a bit more, I am curious on your thoughts about why one would choose a Merkle hash tree over a commutative hash function. $\endgroup$ – Jclangst Apr 5 at 16:30
  • $\begingroup$ @Jclangst, to be honest, in this context, I can't think of any reason why one would choose a Merkle hash tree. In cryptographic contexts, the Merkle hash tree is probably stronger -- but for general non-cryptographic use I doubt that will matter. $\endgroup$ – D.W. Apr 5 at 16:54
  • $\begingroup$ Could you elaborate why hashing once more time the output is recommended? I have seen recommendations of both hashing and word against it (for example with the potential of more collisions, which is unlikely), and idea that hash will not double like with concatenation, but it is not that strong either. $\endgroup$ – Evil Apr 5 at 18:23
  • 1
    $\begingroup$ @Evil, you're right to call that out. I don't have hard evidence for it; it's a gut feeling, and my gut feeling may well be wrong -- it might be totally unnecessary. $\endgroup$ – D.W. Apr 5 at 18:36

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.