Repository: 0xs34n/starknet.js
Pull request #333 (2022-09-17 18:14:37)

fix issue with fix-size merkle tree
## Motivation and Resolution
This issue was not properly corrected in previous attempt (see https://github.com/0xs34n/starknet.js/pull/331 now closed). The goal of this new PR is to have a merkle proof that is fixed in size and matches the depth of the tree. It would also have to be correct!

1. SessionKey.cairo in the contract project, shows 3 things:
- the proof verification does not treat 0x0 in any specific ways. It would simply be applied
- it does not rebuild the root but just compare it with the proof
- the length of the proof has to be the same for all the calls in the multicall

2. The first step of this PR consists in producing some failing tests, A good one is actually the one with 7 values where we pick 0x5 to start. It shows that:

```
      Array [
        "0x6",
    -   "0x6453d426673d0a0a477bd603579a6aa41c8dc1d862b2138c074be609afeb08e",
    +   "0x7",
        "0x38118a340bbba28e678413cd3b07a9436a5e60fd6a7cbda7db958a6d501e274",
      ]
```

This test it is false because:
- if you choose 0x7, you would have to pad it with 0x0 to have 3 in length
- As a result, if you choose 0x5 or 0x6, **you would also have to hash2 0x7 with 0x0** otherwise, you would not match the previous proof.

The problem with the current algorithm is that the key at the right does not get hashed with 0x0 when it is located on an even index, yet it should. This PR just fix that issue!

3. The fix consists in padding the last key on the leaves with "0x0" if it is on an even index. It actually simplifies the cases as you can see from the code. In addition, all the tests pass including the new ones.

### RPC version (if applicable)
N/A. Only the merkle.ts script from the utils directory has been modified

## Usage related changes
- None

## Development related changes
N/A

## 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)
- [ ] Linked the issues which this PR resolves
- [x] Documented the changes
- [ ] Updated the docs (www)
- [x] Updated the tests
- [x] All tests are passing


netlify[bot]: ### <span aria-hidden="true">👷</span> Deploy Preview for *starknetjs* processing.


|  Name | Link |
|---------------------------------|------------------------|
|<span aria-hidden="true">🔨</span> Latest commit | 8764483dfd17ee59f6b18e140278e7dec72cf951 |
|<span aria-hidden="true">🔍</span> Latest deploy log | https://app.netlify.com/sites/starknetjs/deploys/63260e8e736a4700090fd629 |
gregoryguillou: I did not pay attention to those tests. Let me double-check
gregoryguillou: @ivpavici can you let the tests back in again? I should have corrected the snapshots on `typedData.test.ts` this time. Yet I would like to make sure!

@janek26 will review this PR next week. On my side, I would like to have it fix to have @argent/x-sessions fix so I will also need on update on that front so there is no rush. 

Last comment, I would prefer we rename `MerkleTree` to something more convenient because it is not the standard Merkle tree algorithm but a merkle tree with a fixed-size proof. 

Patch:
diff --git a/src/utils/merkle.ts b/src/utils/merkle.ts
index 03879147..2353453a 100644
--- a/src/utils/merkle.ts
+++ b/src/utils/merkle.ts
@@ -23,7 +23,7 @@ export class MerkleTree {
     const newLeaves = [];
     for (let i = 0; i < leaves.length; i += 2) {
       if (i + 1 === leaves.length) {
-        newLeaves.push(leaves[i]);
+        newLeaves.push(MerkleTree.hash(leaves[i], '0x0'));
       } else {
         newLeaves.push(MerkleTree.hash(leaves[i], leaves[i + 1]));
       }
@@ -53,9 +53,7 @@ export class MerkleTree {
         : this.branches.findIndex((b) => b.length === branch.length);
     const nextBranch = this.branches[currentBranchLevelIndex + 1] ?? [this.root];
     return this.getProof(
-      neededBranch === '0x0'
-        ? leaf
-        : MerkleTree.hash(isLeft ? leaf : neededBranch, isLeft ? neededBranch : leaf),
+      MerkleTree.hash(isLeft ? leaf : neededBranch, isLeft ? neededBranch : leaf),
       nextBranch,
       newHashPath
     );


Test patch:
diff --git a/__tests__/utils/merkle.test.ts b/__tests__/utils/merkle.test.ts
index a47cc6b6..85a350fd 100644
--- a/__tests__/utils/merkle.test.ts
+++ b/__tests__/utils/merkle.test.ts
@@ -53,7 +53,7 @@ describe('MerkleTree class', () => {
           MerkleTree.hash(leaves[0], leaves[1]),
           MerkleTree.hash(leaves[2], leaves[3])
         ),
-        MerkleTree.hash(leaves[4], leaves[5])
+        MerkleTree.hash(MerkleTree.hash(leaves[4], leaves[5]), '0x0')
       );
 
       expect(tree.root).toBe(manualMerkle);
@@ -67,7 +67,7 @@ describe('MerkleTree class', () => {
           MerkleTree.hash(leaves[0], leaves[1]),
           MerkleTree.hash(leaves[2], leaves[3])
         ),
-        MerkleTree.hash(MerkleTree.hash(leaves[4], leaves[5]), leaves[6])
+        MerkleTree.hash(MerkleTree.hash(leaves[4], leaves[5]), MerkleTree.hash(leaves[6], '0x0'))
       );
 
       expect(tree.root).toBe(manualMerkle);
@@ -85,7 +85,7 @@ describe('MerkleTree class', () => {
       const manualProof = [
         '0x4',
         MerkleTree.hash('0x1', '0x2'),
-        MerkleTree.hash(MerkleTree.hash('0x5', '0x6'), '0x7'),
+        MerkleTree.hash(MerkleTree.hash('0x5', '0x6'), MerkleTree.hash('0x7', '0x0')),
       ];
 
       expect(proof).toEqual(manualProof);
@@ -101,6 +101,17 @@ describe('MerkleTree class', () => {
 
       expect(proof).toEqual(manualProof);
     });
+    test('should return proof path for valid child', async () => {
+      const proof = tree.getProof('0x5');
+
+      const manualProof = [
+        '0x6',
+        MerkleTree.hash('0x7', '0x0'), // tree should be padded with 0x0 so that all proofs are equals in size
+        MerkleTree.hash(MerkleTree.hash('0x1', '0x2'), MerkleTree.hash('0x3', '0x4')),
+      ];
+
+      expect(proof).toEqual(manualProof);
+    });
     test('should throw for invalid child', () => {
       expect(() => tree.getProof('0x8')).toThrow('leaf not found');
     });
@@ -114,6 +125,7 @@ describe('MerkleTree class', () => {
 
     test('should return true for valid manual proof', async () => {
       const manualProof = [
+        '0x0', // tree should be padded with 0x0 so that all proofs are equals in size
         MerkleTree.hash('0x5', '0x6'),
         MerkleTree.hash(MerkleTree.hash('0x1', '0x2'), MerkleTree.hash('0x3', '0x4')),
       ];
@@ -122,6 +134,17 @@ describe('MerkleTree class', () => {
 
       expect(proofMerklePath(root, leaf, manualProof)).toBe(true);
     });
+    test('should return true for valid manual proof', async () => {
+      const manualProof = [
+        '0x6',
+        MerkleTree.hash('0x7', '0x0'), // tree should be padded with 0x0 so that all proofs are equals in size
+        MerkleTree.hash(MerkleTree.hash('0x1', '0x2'), MerkleTree.hash('0x3', '0x4')),
+      ];
+      const leaf = '0x5';
+      const { root } = tree;
+
+      expect(proofMerklePath(root, leaf, manualProof)).toBe(true);
+    });
     test('should return true for valid proof', async () => {
       const proof = tree.getProof('0x3');
       const leaf = '0x3';
@@ -158,4 +181,76 @@ describe('MerkleTree class', () => {
       expect(proofMerklePath(root, leaf, proof)).toBe(false);
     });
   });
+  describe('verify 2-deep tree with empty data on the right', () => {
+    let tree: MerkleTree;
+    beforeAll(() => {
+      const leaves = ['0x1', '0x2', '0x3'];
+      tree = new MerkleTree(leaves);
+    });
+    test('should return 1-length proof in a 2-length tree', async () => {
+      const proof = tree.getProof('0x3');
+      const manualProof = ['0x0', MerkleTree.hash('0x1', '0x2')];
+      expect(proof).toEqual(manualProof);
+    });
+    test('should check the previous proof works fine', async () => {
+      const manualMerkle = MerkleTree.hash(
+        MerkleTree.hash('0x3', '0x0'),
+        MerkleTree.hash('0x1', '0x2')
+      );
+      expect(tree.root).toBe(manualMerkle);
+    });
+  });
+  describe('verify 3-deep tree with empty data on the right', () => {
+    let tree: MerkleTree;
+    beforeAll(() => {
+      const leaves = ['0x1', '0x2', '0x3', '0x4', '0x5', '0x6'];
+      tree = new MerkleTree(leaves);
+    });
+    test('should return 2-length proof with the 2nd place skipped', async () => {
+      const proof = tree.getProof('0x5');
+      const manualProof = [
+        '0x6',
+        '0x0',
+        MerkleTree.hash(MerkleTree.hash('0x1', '0x2'), MerkleTree.hash('0x3', '0x4')),
+      ];
+      expect(proof).toEqual(manualProof);
+    });
+    test('should check the previous proof works fine', async () => {
+      const manualMerkle = MerkleTree.hash(
+        MerkleTree.hash(MerkleTree.hash('0x5', '0x6'), '0x0'),
+        MerkleTree.hash(MerkleTree.hash('0x1', '0x2'), MerkleTree.hash('0x3', '0x4'))
+      );
+      expect(tree.root).toBe(manualMerkle);
+    });
+  });
+  describe('verify 4-deep tree with empty data on the right', () => {
+    let tree: MerkleTree;
+    beforeAll(() => {
+      const leaves = ['0x1', '0x2', '0x3', '0x4', '0x5', '0x6', '0x7', '0x8', '0x9'];
+      tree = new MerkleTree(leaves);
+    });
+    test('should return 2-length proof with the 2nd place skipped', async () => {
+      const proof = tree.getProof('0x9');
+      const manualProof = [
+        '0x0',
+        '0x0',
+        '0x0',
+        MerkleTree.hash(
+          MerkleTree.hash(MerkleTree.hash('0x1', '0x2'), MerkleTree.hash('0x3', '0x4')),
+          MerkleTree.hash(MerkleTree.hash('0x5', '0x6'), MerkleTree.hash('0x7', '0x8'))
+        ),
+      ];
+      expect(proof).toEqual(manualProof);
+    });
+    test('should check the previous proof works fine', async () => {
+      const manualMerkle = MerkleTree.hash(
+        MerkleTree.hash(MerkleTree.hash(MerkleTree.hash('0x9', '0x0'), '0x0'), '0x0'),
+        MerkleTree.hash(
+          MerkleTree.hash(MerkleTree.hash('0x1', '0x2'), MerkleTree.hash('0x3', '0x4')),
+          MerkleTree.hash(MerkleTree.hash('0x5', '0x6'), MerkleTree.hash('0x7', '0x8'))
+        )
+      );
+      expect(tree.root).toBe(manualMerkle);
+    });
+  });
 });
diff --git a/__tests__/utils/typedData.test.ts b/__tests__/utils/typedData.test.ts
index 78d82b78..ea723070 100644
--- a/__tests__/utils/typedData.test.ts
+++ b/__tests__/utils/typedData.test.ts
@@ -72,7 +72,7 @@ describe('typedData', () => {
     const [, merkleTreeHash] = encodeValue({}, 'merkletree', tree.leaves);
     expect(merkleTreeHash).toBe(tree.root);
     expect(merkleTreeHash).toMatchInlineSnapshot(
-      `"0x551b4adb6c35d49c686a00b9192da9332b18c9b262507cad0ece37f3b6918d2"`
+      `"0x15ac9e457789ef0c56e5d559809e7336a909c14ee2511503fa7af69be1ba639"`
     );
   });
 
@@ -119,7 +119,7 @@ describe('typedData', () => {
     );
     expect(merkleTreeHash).toBe(tree.root);
     expect(merkleTreeHash).toMatchInlineSnapshot(
-      `"0x75c4f467f4527a5348f3e302007228a6b0057fc4c015f981ffb5b3ace475727"`
+      `"0x12354b159e3799dc0ebe86d62dde4ce7b300538d471e5a7fef23dcbac076011"`
     );
   });
 
@@ -217,7 +217,7 @@ describe('typedData', () => {
       '0xCD2a3d9F938E13CD947Ec05AbC7FE734Df8DD826'
     );
     expect(hash).toMatchInlineSnapshot(
-      `"0x1ad0330a62a4a94eae5ea1a7ad96388179d2e4d33e6f909d17421d315110653"`
+      `"0x751fb7d98545f7649d0d0eadc80d770fcd88d8cfaa55590b284f4e1b701ef0a"`
     );
   });
 });