Hash function on byte arrays, with independent order

I would like to have a hash function $H(a_1,...,a_n)$ with the following properties:

1. $a_1 ... a_n$ are byte arrays with same size (typically 32 or 64 bytes).

2. It should also allow "easy" update or deletion of a single element, i.e :

• $H(a_1,...,a_{n+1}) = f(H(a_1,...,a_n), a_{n+1})$
• $H(a_1,...,a_{i-1},a_{i+1},...,a_n) = g(H(a_1,...,a_{n}), a_i)$
3. The order of the $a_1 ... a_n$ terms for $H$ function does not matter.

I found a similar question, but I don't think it can easily handle the single item deletion requirement: Is there such thing as an order independent, updatable hash?

• Actually, Ethan's hash function (that you linked to) wouldn't be hard to modify to make it be able to handle deletes; you'd select $g$in Ethan's function to have a prime order $q$, and you'd have the $g$ function you asked for in question 2 be $g(H(a_1, ..., a_n), a_i) = H(a_1, ..., a_n)^{SHA256(a_i)^{-1} \bmod q} \bmod p$ Dec 20 '17 at 18:56
• Here is a more detailed description of what I'm trying to achieve: - I have $o_1 ... o_n$ objects in datastore (which are returned in random order). - Each object $o_i$ is signed in datastore, the signature is $a_i$ - I want to detect "rogue" insertions (can be done with the signatures) and more importantly rogue deletions, so the need for this kind of hash for this purpose. Dec 20 '17 at 23:16
• What I'm not sure is how to select a "good" $g$ value of prime order $q$. I basically use this algorithm: - Step 1: Generate a prime number $q$ - Step 2: Compute $p = 2q + 1$ - Step 3: Choose a random $h$ and compute $g = h^{(p-1)/q} (mod p)$ - Step 4: if $g^q (mod p) =1$ then keep $p$, $g$ and $q$ otherwise go to step 1 By the way, what would be a good size for the $q$ parameter ? Dec 20 '17 at 23:17