2

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?

1

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.

  • 1
    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. – Adam Dossa Dec 11 '18 at 19:40

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.