Feature request: deep sort payload hashing

[dreamorosi]

Use case

As a customer using the Idempotency utility I want my payloads to be considered idempotent regardless of the ordering of the keys/items within.

Currently, as discovered here, when we hash objects or arrays that have elements ordered differently they result in two different hashes. This causes the requests to be considered unique.

For reference, this is a simplified version of our hashing implementation:

const { createHash } = require("crypto");

/**
 * @param {string} data - The data to be hashed
 * @returns {string} - The hashed data
 */
const hash = (data) => {
  const hash = createHash("sha256");
  hash.update(data);
  return hash.digest("base64");
}

Now, let's take two requests:

const requestA = {
  name: "John",
  age: 30,
  city: "New York",
  address: {
    street: "5th Avenue",
    number: 123,
  },
};

const requestB = {
  city: "New York",
  name: "John",
  age: 30,
  address: {
    number: 123,
    street: "5th Avenue",
  },
};

These two requests should be considered idempotent despite having the keys ordered differently, however in our current implementation, they are considered as two different requests:

console.log(hash(JSON.stringify(objectA)) === hash(JSON.stringify(objectB))); // false

We should implement a function that sorts the objects not only at the top level but also at nested levels.

Solution/User Experience

The change should be completely transparent for customers and the API/DX of the utility should not change.

In terms of implementation, the one found in this blog post could be a good starting point:

function sortObject(object) {
  var sortedObj = {},
    keys = Object.keys(object);

  keys.sort(function (key1, key2) {
    (key1 = key1.toLowerCase()), (key2 = key2.toLowerCase());
    if (key1 < key2) return -1;
    if (key1 > key2) return 1;
    return 0;
  });

  for (var index in keys) {
    var key = keys[index];
    if (typeof object[key] == "object" && !(object[key] instanceof Array)) {
      sortedObj[key] = sortObject(object[key]);
    } else {
      sortedObj[key] = object[key];
    }
  }

  return sortedObj;
}

console.log(
  hash(JSON.stringify(sortObject(objectA))) ===
    hash(JSON.stringify(sortObject(objectB)))
); // true

We could probably improve it when it comes to detecting objects & arrays using the utilities in the commons package as well as making it type safe.

Alternative solutions

Consider other sorting functions if performance is better.

Acknowledgment

• This feature request meets Powertools for AWS Lambda (TypeScript) Tenets
• Should this be considered in other Powertools for AWS Lambda languages? i.e. Python, Java, and .NET

Future readers

Please react with 👍 and your use case to help us understand customer demand.

[karthikeyanjp]

I would like to take this and submit a PR.

[dreamorosi]

Hi @karthikeyanjp, sounds good!

If you have any questions please feel free to ask.

[dreamorosi]

Hi @karthikeyanjp, I just wanted to check if you're still working on this or if I should put back the issue on the backlog.