Is there such thing as an order independent, updatable hash? I have an application where I have a set of primitive units, $P = \{p_0 ... p_n\}$ (they are byte-arrays, in my application).

I want to be able to create a hash value $H(S)$ for any subset $S \subset P$, such that:


I can update a hash without knowing what it hashes. So given $H(S)$ and $T$ (where $S, T \subset P$), there is some function $f(H(S), T) = H(S \cup T)$. Note this works without knowing the contents of S, only its hash.
The hash value is independent of the order. So $f(H(S), T) = f(H(T), S)$.
The answer largely depends on what security properties you want.

The scheme I would use here is to hash all of the individual parts, then take some Diffie-Hellman group, and then raise the generator of that group to the power of the product of the individual hashes. That is,

$ H(a_1, ..., a_n) = g^{\operatorname{SHA256}(a_1) * ... * \operatorname{SHA256}(a_n)} \bmod p $

for $ * $ being multiplication and $ g $, $ p $ being the generator and modulus of the Diffie-Hellman group. (This could also be done with an elliptic curve group to the same effect).

This provides a number of properties:


It is secure given a reasonable Diffie-Hellman group (if you're using Diffie-Hellman based on modular arithmetic, then $ g $ needs to be reasonably large, or $ g^{a} $ may not be larger than $ n $), and reasonable assumptions similar to DDH
It is communitive; that is, the hash value is independent of the order of the hash (and it can be updated after it's computed by raising the computed hash to the power of a new block)
It is reasonably fast


You may also want to consider using a block chain; it's faster, although it isn't communitive, which is one of the properties you asked for. (I also initially considered using XOR in place of exponentiation in a group, but I quickly realized that can be defeated with Gaussian Elimination. It's possible I'm missing something there, though).