Bug: Idempotency payload hashing is sensitive to JSON key ordering #2721

--- a/packages/idempotency/src/deepSort.ts
+++ b/packages/idempotency/src/deepSort.ts
@@ -0,0 +1,46 @@
...
+const sortObject = (object: JSONObject): JSONObject =>
+  Object.keys(object)
+    .sort((a, b) => (a.toLowerCase() < b.toLowerCase() ? -1 : 1))
+    .reduce((acc, key) => {
+      acc[key] = deepSort(object[key]);
+
+      return acc;
+    }, {} as JSONObject);
...
+const deepSort = (data: JSONValue): JSONValue => {
+  const type = getType(data);
+  if (type === 'object') {
+    return sortObject(data as JSONObject);
+  } else if (type === 'array') {
+    return (data as JSONArray).map(deepSort);
+  }
+
+  return data;
+};

--- a/packages/idempotency/src/persistence/BasePersistenceLayer.ts
+++ b/packages/idempotency/src/persistence/BasePersistenceLayer.ts
@@ -301,7 +302,7 @@ abstract class BasePersistenceLayer implements BasePersistenceLayerInterface {
     }
 
     return `${this.idempotencyKeyPrefix}#${this.generateHash(
-      JSON.stringify(data)
+      JSON.stringify(deepSort(data))
     )}`;
   }
 
@@ -318,7 +319,7 @@ abstract class BasePersistenceLayer implements BasePersistenceLayerInterface {
         this.#jmesPathOptions
       ) as JSONValue;
 
-      return this.generateHash(JSON.stringify(data));
+      return this.generateHash(JSON.stringify(deepSort(data)));
     } else {
       return '';
     }

diff --git a/powertools-idempotency/powertools-idempotency-core/src/main/java/software/amazon/lambda/powertools/idempotency/persistence/BasePersistenceStore.java b/powertools-idempotency/powertools-idempotency-core/src/main/java/software/amazon/lambda/powertools/idempotency/persistence/BasePersistenceStore.java
--- a/powertools-idempotency/powertools-idempotency-core/src/main/java/software/amazon/lambda/powertools/idempotency/persistence/BasePersistenceStore.java
+++ b/powertools-idempotency/powertools-idempotency-core/src/main/java/software/amazon/lambda/powertools/idempotency/persistence/BasePersistenceStore.java
@@ -22,11 +22,13 @@ import java.security.MessageDigest;
 import java.security.NoSuchAlgorithmException;
 import java.time.Instant;
 import java.time.temporal.ChronoUnit;
+import java.util.Map;
 import java.util.Optional;
 import java.util.OptionalInt;
 import java.util.OptionalLong;
 import java.util.Spliterator;
 import java.util.Spliterators;
+import java.util.TreeMap;
 import java.util.stream.Stream;
 import java.util.stream.StreamSupport;
 
@@ -36,6 +38,9 @@ import org.slf4j.LoggerFactory;
 import com.fasterxml.jackson.core.JsonProcessingException;
 import com.fasterxml.jackson.databind.JsonNode;
 import com.fasterxml.jackson.databind.ObjectWriter;
+import com.fasterxml.jackson.databind.node.ArrayNode;
+import com.fasterxml.jackson.databind.node.JsonNodeFactory;
+import com.fasterxml.jackson.databind.node.ObjectNode;
 
 import io.burt.jmespath.Expression;
 import software.amazon.lambda.powertools.idempotency.IdempotencyConfig;
@@ -300,9 +305,10 @@ public abstract class BasePersistenceStore implements PersistenceStore {
      */
     String generateHash(JsonNode data) {
         Object node;
-        // if array or object, use the json string representation, otherwise get the real value
+        // if array or object, use the json string representation with object members sorted by name,
+        // otherwise get the real value
         if (data.isContainerNode()) {
-            node = data.toString();
+            node = sortObjectMembers(data).toString();
         } else if (data.isTextual()) {
             node = data.asText();
         } else if (data.isInt()) {
@@ -328,6 +334,29 @@ public abstract class BasePersistenceStore implements PersistenceStore {
         return String.format("%032x", new BigInteger(1, digest));
     }
 
+    /**
+     * Return a copy of the provided node in which object members are sorted by name, recursively.
+     * Array elements keep their order.
+     *
+     * @param data node to copy
+     * @return canonical copy of the node
+     */
+    private static JsonNode sortObjectMembers(JsonNode data) {
+        if (data.isObject()) {
+            Map<String, JsonNode> sortedMembers = new TreeMap<>();
+            data.properties().forEach(member -> sortedMembers.put(member.getKey(), member.getValue()));
+            ObjectNode sorted = JsonNodeFactory.instance.objectNode();
+            sortedMembers.forEach((name, value) -> sorted.set(name, sortObjectMembers(value)));
+            return sorted;
+        }
+        if (data.isArray()) {
+            ArrayNode copy = JsonNodeFactory.instance.arrayNode(data.size());
+            data.forEach(element -> copy.add(sortObjectMembers(element)));
+            return copy;
+        }
+        return data;
+    }
+
     @SuppressWarnings("java:S4790") // Usage of MessageDigest is OK
     private MessageDigest getHashAlgorithm() {
         MessageDigest hashAlgorithm;