Repository: 0xs34n/starknet.js
Pull request #343 (2022-09-23 14:18:21)

fix: fixed hash arg sorting in merkle tree generation
## Motivation and Resolution
Merkle tree generation was relying on a sorted pedersen hash function (as described in #341 ). The sorting function was doing a string compare which can easily fail when comparing to hex strings. For example: `'0xa' > '0x12' = true` when of course `10 > 18 = false`. Given that the vast majority of (all?) on-chain Merkle tree verifiers also sort this causes mismatching roots and proofs with higher and higher likelihood the larger the number of leaves.

This change simply casts the hex strings to BN to compare.

### RPC version (if applicable)

N/A

## Usage related changes

No usage / API changes.

## Development related changes

No development related changes.

## Checklist:

- [x] Performed a self-review of the code
- [x] Rebased to the last commit of the target branch (or merged it into my branch)
- [x] Linked the issues which this PR resolves
- [x] Documented the changes
- [x] Updated the docs (www)
- [x] Updated the tests
- [x] All tests are passing



Patch:
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
index dc49a8d6..1682d3d6 100644
--- a/CONTRIBUTING.md
+++ b/CONTRIBUTING.md
@@ -19,7 +19,7 @@ ALways start from `develop` branch and merge back to `develop` branch.
 To build you changes run:
 
 ```bash
-npm build
+npm run build
 ```
 
 Run linters and tests:
@@ -31,7 +31,7 @@ npm test
 Or run tests in watch mode:
 
 ```bash
-npm run test --watch
+npm test --watch
 ```
 
 **Don’t forget to add tests and update documentation for your changes.**
diff --git a/src/utils/merkle.ts b/src/utils/merkle.ts
index 1dd288c0..03879147 100644
--- a/src/utils/merkle.ts
+++ b/src/utils/merkle.ts
@@ -1,4 +1,5 @@
 import { pedersen } from './hash';
+import { toBN } from './number';
 
 export class MerkleTree {
   public leaves: string[];
@@ -31,7 +32,7 @@ export class MerkleTree {
   }
 
   static hash(a: string, b: string) {
-    const [aSorted, bSorted] = [a, b].sort();
+    const [aSorted, bSorted] = [toBN(a), toBN(b)].sort((x: any, y: any) => (x.gte(y) ? 1 : -1));
     return pedersen([aSorted, bSorted]);
   }
 


Test patch:
diff --git a/__tests__/utils/merkle.test.ts b/__tests__/utils/merkle.test.ts
index 2c1fb876..a47cc6b6 100644
--- a/__tests__/utils/merkle.test.ts
+++ b/__tests__/utils/merkle.test.ts
@@ -1,6 +1,21 @@
+import { pedersen } from '../../src/utils/hash';
 import { MerkleTree, proofMerklePath } from '../../src/utils/merkle';
+import { toBN } from '../../src/utils/number';
 
 describe('MerkleTree class', () => {
+  describe('calculate hashes', () => {
+    test('should generate hash with sorted arguments', async () => {
+      let leaves = ['0x12', '0xa']; // 18, 10
+      let merkleHash = MerkleTree.hash(leaves[0], leaves[1]);
+      let rawHash = pedersen([toBN(leaves[1]), toBN(leaves[0])]);
+      expect(merkleHash).toBe(rawHash);
+
+      leaves = ['0x5bb9440e27889a364bcb678b1f679ecd1347acdedcbf36e83494f857cc58026', '0x3'];
+      merkleHash = MerkleTree.hash(leaves[0], leaves[1]);
+      rawHash = pedersen([toBN(leaves[1]), toBN(leaves[0])]);
+      expect(merkleHash).toBe(rawHash);
+    });
+  });
   describe('generate roots', () => {
     test('should generate valid root for 1 elements', async () => {
       const leaves = ['0x1'];