# Calculating a hash of a set of keys in Solidity

I have the following problem that I'm trying to think of an efficient solution for.

Suppose I have a set of unordered keys (KEY_1, KEY_5, KEY_2, KEY_4), and I want to calculate a unique hash for this set. Is there an easy way to do this in Solidity using data structures / types that are fairly efficient?

One approach would be to order the keys and then take the hash, but this involves sorting the keys which is not ideal (i.e. O(n*log(n))).

Is there a better approach?

• Hash each key separately and XOR the hashes together? Removes the need to sort first. Not sure how strong such a hash would be though. :-\ Dec 11, 2018 at 14:51
• Okay, this reckons it's not safe, so it might not suit your needs -> crypto.stackexchange.com/questions/54544/… Dec 11, 2018 at 14:53

If you do not want to go through the trouble (and gas cost) of sorting the keys, then it logically follows that at some point you must use a both commutative and associative operator to combine the keys, because different orders of the same set must always produce the same result.

Concatenation of the keys does not satisfy commutativity, so you can rule that out immediately.

The only O(1) operators that take and produce 256-bit values and are both commutative and associative are:

• `^`
• `&`
• `|`
• `+`
• `*`

We can rule out `&`, `|` and `*` because they produce weak results:

• `|` tends towards making the result all `1`'s
• `&` tends towards making the result all `0`'s
• `*` tends to accumulate `0`'s at the least significant end of the `uint`

So your only options for combining the keys are `^` and `+`.

Therefore, I recommend hashing all the keys and XOR-ing them together. Depending on your specific security needs, you may then want to take the hash of that result.

• Thanks - I read the article posted about via XOR'ing may not be very safe. In this case I have control over the possible keys so there is less of a security risk of others adding keys to the set that may cause a collision. Dec 11, 2018 at 19:40