Repository: 0xs34n/starknet.js
Pull request #293 (2022-08-16 14:56:56)

feat: add merkle trees
using pedersen hash

![Bildschirmfoto 2022-08-16 um 16 55 04](https://user-images.githubusercontent.com/6831124/184912614-aab637ad-2490-4366-a955-fcce8dfedda2.png)




Patch:
diff --git a/__mocks__/typedDataSessionExample.json b/__mocks__/typedDataSessionExample.json
new file mode 100644
index 00000000..75242e40
--- /dev/null
+++ b/__mocks__/typedDataSessionExample.json
@@ -0,0 +1,42 @@
+{
+  "primaryType": "Session",
+  "types": {
+    "Policy": [
+      { "name": "contractAddress", "type": "felt" },
+      { "name": "selector", "type": "selector" }
+    ],
+    "Session": [
+      { "name": "key", "type": "felt" },
+      { "name": "expires", "type": "felt" },
+      { "name": "root", "type": "merkletree", "contains": "Policy" }
+    ],
+    "StarkNetDomain": [
+      { "name": "name", "type": "felt" },
+      { "name": "version", "type": "felt" },
+      { "name": "chain_id", "type": "felt" }
+    ]
+  },
+  "domain": {
+    "name": "StarkNet Mail",
+    "version": "1",
+    "chain_id": 1
+  },
+  "message": {
+    "key": "0x0000000000000000000000000000000000000000000000000000000000000000",
+    "expires": "0x0000000000000000000000000000000000000000000000000000000000000000",
+    "root": [
+      {
+        "contractAddress": "0x1",
+        "selector": "transfer"
+      },
+      {
+        "contractAddress": "0x2",
+        "selector": "transfer"
+      },
+      {
+        "contractAddress": "0x3",
+        "selector": "transfer"
+      }
+    ]
+  }
+}
diff --git a/src/index.ts b/src/index.ts
index fd646039..997d043c 100644
--- a/src/index.ts
+++ b/src/index.ts
@@ -17,6 +17,7 @@ export * as json from './utils/json';
 export * as number from './utils/number';
 export * as transaction from './utils/transaction';
 export * as stark from './utils/stark';
+export * as merkle from './utils/merkle';
 export * as ec from './utils/ellipticCurve';
 export * as uint256 from './utils/uint256';
 export * as shortString from './utils/shortString';
diff --git a/src/signer/default.ts b/src/signer/default.ts
index 82821209..464f5356 100644
--- a/src/signer/default.ts
+++ b/src/signer/default.ts
@@ -1,5 +1,5 @@
 import { Abi, Invocation, InvocationsSignerDetails, KeyPair, Signature } from '../types';
-import { getStarkKey, sign } from '../utils/ellipticCurve';
+import { genKeyPair, getStarkKey, sign } from '../utils/ellipticCurve';
 import { calculcateTransactionHash, getSelectorFromName } from '../utils/hash';
 import { fromCallsToExecuteCalldataWithNonce } from '../utils/transaction';
 import { TypedData, getMessageHash } from '../utils/typedData';
@@ -8,7 +8,7 @@ import { SignerInterface } from './interface';
 export class Signer implements SignerInterface {
   protected keyPair: KeyPair;
 
-  constructor(keyPair: KeyPair) {
+  constructor(keyPair: KeyPair = genKeyPair()) {
     this.keyPair = keyPair;
   }
 
diff --git a/src/utils/hash.ts b/src/utils/hash.ts
index 3c604137..c9f6dab6 100644
--- a/src/utils/hash.ts
+++ b/src/utils/hash.ts
@@ -62,13 +62,15 @@ export function pedersen(input: [BigNumberish, BigNumberish]) {
   for (let i = 0; i < input.length; i += 1) {
     let x = toBN(input[i]);
     assert(x.gte(ZERO) && x.lt(toBN(addHexPrefix(FIELD_PRIME))), `Invalid input: ${input[i]}`);
-    for (let j = 0; j < 252; j += 1) {
-      const pt = constantPoints[2 + i * 252 + j];
-      assert(!point.getX().eq(pt.getX()));
-      if (x.and(ONE).toNumber() !== 0) {
-        point = point.add(pt);
+    if (!x.isZero()) {
+      for (let j = 0; j < 252; j += 1) {
+        const pt = constantPoints[2 + i * 252 + j];
+        assert(!point.getX().eq(pt.getX()));
+        if (x.and(ONE).toNumber() !== 0) {
+          point = point.add(pt);
+        }
+        x = x.shrn(1);
       }
-      x = x.shrn(1);
     }
   }
   return addHexPrefix(point.getX().toString(16));
diff --git a/src/utils/merkle.ts b/src/utils/merkle.ts
new file mode 100644
index 00000000..1dd288c0
--- /dev/null
+++ b/src/utils/merkle.ts
@@ -0,0 +1,70 @@
+import { pedersen } from './hash';
+
+export class MerkleTree {
+  public leaves: string[];
+
+  public branches: string[][] = [];
+
+  public root: string;
+
+  constructor(leafHashes: string[]) {
+    this.leaves = leafHashes;
+    this.root = this.build(leafHashes);
+  }
+
+  private build(leaves: string[]): string {
+    if (leaves.length === 1) {
+      return leaves[0];
+    }
+    if (leaves.length !== this.leaves.length) {
+      this.branches.push(leaves);
+    }
+    const newLeaves = [];
+    for (let i = 0; i < leaves.length; i += 2) {
+      if (i + 1 === leaves.length) {
+        newLeaves.push(leaves[i]);
+      } else {
+        newLeaves.push(MerkleTree.hash(leaves[i], leaves[i + 1]));
+      }
+    }
+    return this.build(newLeaves);
+  }
+
+  static hash(a: string, b: string) {
+    const [aSorted, bSorted] = [a, b].sort();
+    return pedersen([aSorted, bSorted]);
+  }
+
+  public getProof(leaf: string, branch = this.leaves, hashPath: string[] = []): string[] {
+    const index = branch.indexOf(leaf);
+    if (index === -1) {
+      throw new Error('leaf not found');
+    }
+    if (branch.length === 1) {
+      return hashPath;
+    }
+    const isLeft = index % 2 === 0;
+    const neededBranch = (isLeft ? branch[index + 1] : branch[index - 1]) ?? '0x0';
+    const newHashPath = [...hashPath, neededBranch];
+    const currentBranchLevelIndex =
+      this.leaves.length === branch.length
+        ? -1
+        : 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),
+      nextBranch,
+      newHashPath
+    );
+  }
+}
+
+export function proofMerklePath(root: string, leaf: string, path: string[]): boolean {
+  if (path.length === 0) {
+    return root === leaf;
+  }
+  const [next, ...rest] = path;
+  return proofMerklePath(root, MerkleTree.hash(leaf, next), rest);
+}
diff --git a/src/utils/number.ts b/src/utils/number.ts
index 08f3b2e4..8d1d57db 100644
--- a/src/utils/number.ts
+++ b/src/utils/number.ts
@@ -6,7 +6,7 @@ import { addHexPrefix, removeHexPrefix } from './encode';
 export type BigNumberish = string | number | BN;
 
 export function isHex(hex: string): boolean {
-  return hex.startsWith('0x');
+  return /^0x[0-9a-f]*$/i.test(hex);
 }
 
 export function toBN(number: BigNumberish, base?: number | 'hex') {
diff --git a/src/utils/typedData/index.ts b/src/utils/typedData/index.ts
index fbde6ee4..b99540b1 100644
--- a/src/utils/typedData/index.ts
+++ b/src/utils/typedData/index.ts
@@ -1,7 +1,8 @@
 import { computeHashOnElements, getSelectorFromName } from '../hash';
-import { BigNumberish, toBN, toHex } from '../number';
+import { MerkleTree } from '../merkle';
+import { BigNumberish, isHex, toBN, toHex } from '../number';
 import { encodeShortString } from '../shortString';
-import { TypedData } from './types';
+import { StarkNetMerkleType, StarkNetType, TypedData } from './types';
 import { validateTypedData } from './utils';
 
 export * from './types';
@@ -17,6 +18,19 @@ function getHex(value: BigNumberish): string {
   }
 }
 
+export function prepareSelector(selector: string): string {
+  return isHex(selector) ? selector : getSelectorFromName(selector);
+}
+
+export function isMerkleTreeType(type: StarkNetType): type is StarkNetMerkleType {
+  return type.type === 'merkletree';
+}
+
+interface Context {
+  parent?: string;
+  key?: string;
+}
+
 /**
  * Get the dependencies of a struct type. If a struct has the same dependency multiple times, it's only included once
  * in the resulting array.
@@ -27,15 +41,10 @@ function getHex(value: BigNumberish): string {
  * @return {string[]}
  */
 export const getDependencies = (
-  typedData: TypedData,
+  types: TypedData['types'],
   type: string,
   dependencies: string[] = []
 ): string[] => {
-  // `getDependencies` is called by most other functions, so we validate the JSON schema here
-  if (!validateTypedData(typedData)) {
-    throw new Error('Typed data does not match JSON schema');
-  }
-
   // Include pointers (struct arrays)
   if (type[type.length - 1] === '*') {
     // eslint-disable-next-line no-param-reassign
@@ -46,16 +55,16 @@ export const getDependencies = (
     return dependencies;
   }
 
-  if (!typedData.types[type]) {
+  if (!types[type]) {
     return dependencies;
   }
 
   return [
     type,
-    ...typedData.types[type].reduce<string[]>(
+    ...types[type].reduce<string[]>(
       (previous, t) => [
         ...previous,
-        ...getDependencies(typedData, t.type, previous).filter(
+        ...getDependencies(types, t.type, previous).filter(
           (dependency) => !previous.includes(dependency)
         ),
       ],
@@ -64,6 +73,22 @@ export const getDependencies = (
   ];
 };
 
+function getMerkleTreeType(types: TypedData['types'], ctx: Context) {
+  if (ctx.parent && ctx.key) {
+    const parentType = types[ctx.parent];
+    const merkleType = parentType.find((t) => t.name === ctx.key)!;
+    const isMerkleTree = isMerkleTreeType(merkleType);
+    if (!isMerkleTree) {
+      throw new Error(`${ctx.key} is not a merkle tree`);
+    }
+    if (merkleType.contains.endsWith('*')) {
+      throw new Error(`Merkle tree contain property must not be an array but was given ${ctx.key}`);
+    }
+    return merkleType.contains;
+  }
+  return 'raw';
+}
+
 /**
  * Encode a type to a string. All dependant types are alphabetically sorted.
  *
@@ -71,13 +96,13 @@ export const getDependencies = (
  * @param {string} type
  * @return {string}
  */
-export const encodeType = (typedData: TypedData, type: string): string => {
-  const [primary, ...dependencies] = getDependencies(typedData, type);
-  const types = [primary, ...dependencies.sort()];
+export const encodeType = (types: TypedData['types'], type: string): string => {
+  const [primary, ...dependencies] = getDependencies(types, type);
+  const newTypes = !primary ? [] : [primary, ...dependencies.sort()];
 
-  return types
+  return newTypes
     .map((dependency) => {
-      return `${dependency}(${typedData.types[dependency].map((t) => `${t.name}:${t.type}`)})`;
+      return `${dependency}(${types[dependency].map((t) => `${t.name}:${t.type}`)})`;
     })
     .join('');
 };
@@ -89,8 +114,8 @@ export const encodeType = (typedData: TypedData, type: string): string => {
  * @param {string} type
  * @return {string}
  */
-export const getTypeHash = (typedData: TypedData, type: string): string => {
-  return getSelectorFromName(encodeType(typedData, type));
+export const getTypeHash = (types: TypedData['types'], type: string): string => {
+  return getSelectorFromName(encodeType(types, type));
 };
 
 /**
@@ -102,28 +127,47 @@ export const getTypeHash = (typedData: TypedData, type: string): string => {
  * @param {any} data
  * @returns {[string, string]}
  */
-const encodeValue = (typedData: TypedData, type: string, data: unknown): [string, string] => {
-  if (typedData.types[type]) {
+export const encodeValue = (
+  types: TypedData['types'],
+  type: string,
+  data: unknown,
+  ctx: Context = {}
+): [string, string] => {
+  if (types[type]) {
     // eslint-disable-next-line @typescript-eslint/no-use-before-define
-    return [type, getStructHash(typedData, type, data as Record<string, unknown>)];
+    return [type, getStructHash(types, type, data as Record<string, unknown>)];
   }
 
   if (
-    Object.keys(typedData.types)
+    Object.keys(types)
       .map((x) => `${x}*`)
       .includes(type)
   ) {
     const structHashes: string[] = (data as unknown[]).map((struct) => {
       // eslint-disable-next-line @typescript-eslint/no-use-before-define
-      return getStructHash(typedData, type.slice(0, -1), struct as Record<string, unknown>);
+      return getStructHash(types, type.slice(0, -1), struct as Record<string, unknown>);
     });
     return [type, computeHashOnElements(structHashes)];
   }
 
+  if (type === 'merkletree') {
+    const merkleTreeType = getMerkleTreeType(types, ctx);
+    const structHashes: string[] = (data as unknown[]).map((struct) => {
+      // eslint-disable-next-line @typescript-eslint/no-use-before-define
+      return encodeValue(types, merkleTreeType, struct as Record<string, unknown>)[1];
+    });
+    const { root } = new MerkleTree(structHashes as string[]);
+    return ['felt', root];
+  }
+
   if (type === 'felt*') {
     return ['felt*', computeHashOnElements(data as string[])];
   }
 
+  if (type === 'selector') {
+    return ['felt', prepareSelector(data as string)];
+  }
+
   return [type, getHex(data as string)];
 };
 
@@ -135,25 +179,32 @@ const encodeValue = (typedData: TypedData, type: string, data: unknown): [string
  * @param {string} type
  * @param {Record<string, any>} data
  */
-export const encodeData = <T extends TypedData>(typedData: T, type: string, data: T['message']) => {
-  const [types, values] = typedData.types[type].reduce<[string[], string[]]>(
+export const encodeData = <T extends TypedData>(
+  types: T['types'],
+  type: string,
+  data: T['message']
+) => {
+  const [returnTypes, values] = types[type].reduce<[string[], string[]]>(
     ([ts, vs], field) => {
       if (data[field.name] === undefined || data[field.name] === null) {
         throw new Error(`Cannot encode data: missing data for '${field.name}'`);
       }
 
       const value = data[field.name];
-      const [t, encodedValue] = encodeValue(typedData, field.type, value);
+      const [t, encodedValue] = encodeValue(types, field.type, value, {
+        parent: type,
+        key: field.name,
+      });
 
       return [
         [...ts, t],
         [...vs, encodedValue],
       ];
     },
-    [['felt'], [getTypeHash(typedData, type)]]
+    [['felt'], [getTypeHash(types, type)]]
   );
 
-  return [types, values];
+  return [returnTypes, values];
 };
 
 /**
@@ -166,27 +217,30 @@ export const encodeData = <T extends TypedData>(typedData: T, type: string, data
  * @return {Buffer}
  */
 export const getStructHash = <T extends TypedData>(
-  typedData: T,
+  types: T['types'],
   type: string,
   data: T['message']
 ) => {
-  return computeHashOnElements(encodeData(typedData, type, data)[1]);
+  return computeHashOnElements(encodeData(types, type, data)[1]);
 };
 
 /**
- * Get the EIP-191 encoded message to sign, from the typedData object. If `hash` is enabled, the message will be hashed
- * with Keccak256.
+ * Get the EIP-191 encoded message to sign, from the typedData object.
  *
  * @param {TypedData} typedData
  * @param {BigNumberish} account
  * @return {string}
  */
 export const getMessageHash = (typedData: TypedData, account: BigNumberish): string => {
+  if (!validateTypedData(typedData)) {
+    throw new Error('Typed data does not match JSON schema');
+  }
+
   const message = [
     encodeShortString('StarkNet Message'),
-    getStructHash(typedData, 'StarkNetDomain', typedData.domain),
+    getStructHash(typedData.types, 'StarkNetDomain', typedData.domain),
     account,
-    getStructHash(typedData, typedData.primaryType, typedData.message),
+    getStructHash(typedData.types, typedData.primaryType, typedData.message),
   ];
 
   return computeHashOnElements(message);
diff --git a/src/utils/typedData/types.ts b/src/utils/typedData/types.ts
index a99ae584..d626b931 100644
--- a/src/utils/typedData/types.ts
+++ b/src/utils/typedData/types.ts
@@ -1,13 +1,21 @@
+export type StarkNetMerkleType = {
+  name: string;
+  type: 'merkletree';
+  contains: string;
+};
+
 /**
  * A single type, as part of a struct. The `type` field can be any of the EIP-712 supported types.
  *
  * Note that the `uint` and `int` aliases like in Solidity, and fixed point numbers are not supported by the EIP-712
  * standard.
  */
-export interface StarkNetType {
-  name: string;
-  type: 'felt' | 'felt*' | string;
-}
+export type StarkNetType =
+  | {
+      name: string;
+      type: string;
+    }
+  | StarkNetMerkleType;
 
 /**
  * The EIP712 domain struct. Any of these fields are optional, but it must contain at least one field.
diff --git a/www/guides/account.md b/www/guides/account.md
index af446d01..c52773de 100644
--- a/www/guides/account.md
+++ b/www/guides/account.md
@@ -43,9 +43,9 @@ const compiledAccount = json.parse(
 );
 ```
 
-> **Note** 
-> 
-> below example uses [Argent's](https://github.com/argentlabs/argent-contracts-starknet/blob/develop/contracts/ArgentAccount.cairo) account contract 
+> **Note**
+>
+> below example uses [Argent's](https://github.com/argentlabs/argent-contracts-starknet/blob/develop/contracts/ArgentAccount.cairo) account contract
 
 ```javascript
 const accountResponse = await defaultProvider.deployContract({
@@ -54,9 +54,9 @@ const accountResponse = await defaultProvider.deployContract({
 });
 ```
 
-> **Note** 
-> 
-> below example uses [OpenZeppelin's](https://github.com/OpenZeppelin/cairo-contracts/blob/main/src/openzeppelin/account/presets/Account.cairo) account contract 
+> **Note**
+>
+> below example uses [OpenZeppelin's](https://github.com/OpenZeppelin/cairo-contracts/blob/main/src/openzeppelin/account/presets/Account.cairo) account contract
 
 ```javascript
 const accountResponse = await defaultProvider.deployContract({
@@ -74,7 +74,7 @@ Wait for the deployment transaction to be accepted and assign the address of the
 await defaultProvider.waitForTransaction(accountResponse.transaction_hash);
 ```
 
-Once account contract is deployed [Account](../docs/API/account.md) instance can be created. Use your new account instance to sign transactions, messages or verify signatures! 
+Once account contract is deployed [Account](../docs/API/account.md) instance can be created. Use your new account instance to sign transactions, messages or verify signatures!
 
 ```js
 const account = new Account(
@@ -86,4 +86,4 @@ const account = new Account(
 
 ## Fund your new account!
 
-Make sure your Account has enough funds to execute invocations. Use this [faucet](https://faucet.goerli.starknet.io/) for funding on testnet.
\ No newline at end of file
+Make sure your Account has enough funds to execute invocations. Use this [faucet](https://faucet.goerli.starknet.io/) for funding on testnet.
diff --git a/www/guides/erc20.md b/www/guides/erc20.md
index c4a013e0..24867db0 100644
--- a/www/guides/erc20.md
+++ b/www/guides/erc20.md
@@ -24,7 +24,6 @@ const erc20Address = erc20Response.contract_address;
 const erc20 = new Contract(compiledErc20.abi, erc20Address, defaultProvider);
 ```
 
-
 ## Mint tokens to an account address
 
 Make sure you created the `Account` instance following the [Creating an Account](./account.md) guide.
@@ -37,8 +36,8 @@ erc20.connect(account);
 const { transaction_hash: mintTxHash } = await erc20.mint(
   account.address,
   "1000",
-  { 
-    maxFee: "1" 
+  {
+    maxFee: "1"
   }
 );
 
@@ -46,9 +45,9 @@ console.log(`Waiting for Tx to be Accepted on Starknet - Minting...`);
 await defaultProvider.waitForTransaction(mintTxHash);
 ```
 
-> **Note** 
+> **Note**
 >
-> Transaction can be rejected if `maxFee` is lower than actual. 
+> Transaction can be rejected if `maxFee` is lower than actual.
 >
 > _Error: REJECTED: FEE_TRANSFER_FAILURE_
 >


Test patch:
diff --git a/__tests__/utils/__snapshots__/ellipticalCurve.test.ts.snap b/__tests__/utils/__snapshots__/ellipticalCurve.test.ts.snap
index c540f5f8..74ce57b3 100644
--- a/__tests__/utils/__snapshots__/ellipticalCurve.test.ts.snap
+++ b/__tests__/utils/__snapshots__/ellipticalCurve.test.ts.snap
@@ -1,3 +1,5 @@
 // Jest Snapshot v1, https://goo.gl/fbAQLP
 
 exports[`pedersen() 1`] = `"0x5ed2703dfdb505c587700ce2ebfcab5b3515cd7e6114817e6026ec9d4b364ca"`;
+
+exports[`pedersen() with 0 1`] = `"0x1a5c561f97b52c17a19f34c4499a745cd4e8412e29e4ed5e91e4481c7d53935"`;
diff --git a/__tests__/utils/ellipticalCurve.test.ts b/__tests__/utils/ellipticalCurve.test.ts
index 21ed1339..2bba8d4e 100644
--- a/__tests__/utils/ellipticalCurve.test.ts
+++ b/__tests__/utils/ellipticalCurve.test.ts
@@ -25,6 +25,11 @@ test('pedersen()', () => {
   expect(own).toMatchSnapshot();
 });
 
+test('pedersen() with 0', () => {
+  const own = pedersen(['0x12773', '0x0']);
+  expect(own).toMatchSnapshot();
+});
+
 test('computeHashOnElements()', () => {
   const array = ['1', '2', '3', '4'];
   expect(computeHashOnElements(array)).toBe(
diff --git a/__tests__/utils/merkle.test.ts b/__tests__/utils/merkle.test.ts
new file mode 100644
index 00000000..2c1fb876
--- /dev/null
+++ b/__tests__/utils/merkle.test.ts
@@ -0,0 +1,146 @@
+import { MerkleTree, proofMerklePath } from '../../src/utils/merkle';
+
+describe('MerkleTree class', () => {
+  describe('generate roots', () => {
+    test('should generate valid root for 1 elements', async () => {
+      const leaves = ['0x1'];
+      const tree = new MerkleTree(leaves);
+
+      const manualMerkle = leaves[0];
+
+      expect(tree.root).toBe(manualMerkle);
+    });
+    test('should generate valid root for 2 elements', async () => {
+      const leaves = ['0x1', '0x2'];
+      const tree = new MerkleTree(leaves);
+
+      const manualMerkle = MerkleTree.hash(leaves[0], leaves[1]);
+
+      expect(tree.root).toBe(manualMerkle);
+    });
+    test('should generate valid root for 4 elements', async () => {
+      const leaves = ['0x1', '0x2', '0x3', '0x4'];
+      const tree = new MerkleTree(leaves);
+
+      const manualMerkle = MerkleTree.hash(
+        MerkleTree.hash(leaves[0], leaves[1]),
+        MerkleTree.hash(leaves[2], leaves[3])
+      );
+
+      expect(tree.root).toBe(manualMerkle);
+    });
+    test('should generate valid root for 6 elements', async () => {
+      const leaves = ['0x1', '0x2', '0x3', '0x4', '0x5', '0x6'];
+      const tree = new MerkleTree(leaves);
+
+      const manualMerkle = MerkleTree.hash(
+        MerkleTree.hash(
+          MerkleTree.hash(leaves[0], leaves[1]),
+          MerkleTree.hash(leaves[2], leaves[3])
+        ),
+        MerkleTree.hash(leaves[4], leaves[5])
+      );
+
+      expect(tree.root).toBe(manualMerkle);
+    });
+    test('should generate valid root for 7 elements', async () => {
+      const leaves = ['0x1', '0x2', '0x3', '0x4', '0x5', '0x6', '0x7'];
+      const tree = new MerkleTree(leaves);
+
+      const manualMerkle = MerkleTree.hash(
+        MerkleTree.hash(
+          MerkleTree.hash(leaves[0], leaves[1]),
+          MerkleTree.hash(leaves[2], leaves[3])
+        ),
+        MerkleTree.hash(MerkleTree.hash(leaves[4], leaves[5]), leaves[6])
+      );
+
+      expect(tree.root).toBe(manualMerkle);
+    });
+  });
+  describe('generate proofs', () => {
+    let tree: MerkleTree;
+    beforeAll(() => {
+      const leaves = ['0x1', '0x2', '0x3', '0x4', '0x5', '0x6', '0x7'];
+      tree = new MerkleTree(leaves);
+    });
+    test('should return proof path for valid child', async () => {
+      const proof = tree.getProof('0x3');
+
+      const manualProof = [
+        '0x4',
+        MerkleTree.hash('0x1', '0x2'),
+        MerkleTree.hash(MerkleTree.hash('0x5', '0x6'), '0x7'),
+      ];
+
+      expect(proof).toEqual(manualProof);
+    });
+    test('should return proof path for valid child', async () => {
+      const proof = tree.getProof('0x7');
+
+      const manualProof = [
+        '0x0', // proofs should always be as long as the tree is deep
+        MerkleTree.hash('0x5', '0x6'),
+        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');
+    });
+  });
+  describe('verify proofs', () => {
+    let tree: MerkleTree;
+    beforeAll(() => {
+      const leaves = ['0x1', '0x2', '0x3', '0x4', '0x5', '0x6', '0x7'];
+      tree = new MerkleTree(leaves);
+    });
+
+    test('should return true for valid manual proof', async () => {
+      const manualProof = [
+        MerkleTree.hash('0x5', '0x6'),
+        MerkleTree.hash(MerkleTree.hash('0x1', '0x2'), MerkleTree.hash('0x3', '0x4')),
+      ];
+      const leaf = '0x7';
+      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';
+      const { root } = tree;
+
+      expect(proofMerklePath(root, leaf, proof)).toBe(true);
+    });
+    test('should return false for invalid proof (root)', async () => {
+      const proof = tree.getProof('0x3');
+      const leaf = '0x3';
+      const root = '0x4';
+
+      expect(proofMerklePath(root, leaf, proof)).toBe(false);
+    });
+    test('should return false for invalid proof (proof[0])', async () => {
+      const proof = tree.getProof('0x3');
+      const leaf = '0x3';
+      const { root } = tree;
+      proof[0] = '0x7';
+      expect(proofMerklePath(root, leaf, proof)).toBe(false);
+    });
+    test('should return false for invalid proof (proof[1])', async () => {
+      const proof = tree.getProof('0x3');
+      const leaf = '0x3';
+      const { root } = tree;
+      proof[1] = '0x4';
+      expect(proofMerklePath(root, leaf, proof)).toBe(false);
+    });
+    test('should return false for invalid proof (proof[2])', async () => {
+      const proof = tree.getProof('0x3');
+      const leaf = '0x3';
+      const { root } = tree;
+      proof[2] = '0x4';
+      expect(proofMerklePath(root, leaf, proof)).toBe(false);
+    });
+  });
+});
diff --git a/__tests__/utils/typedData.test.ts b/__tests__/utils/typedData.test.ts
index 30d52439..78d82b78 100644
--- a/__tests__/utils/typedData.test.ts
+++ b/__tests__/utils/typedData.test.ts
@@ -1,46 +1,134 @@
 import typedDataExample from '../../__mocks__/typedDataExample.json';
+import typedDataSessionExample from '../../__mocks__/typedDataSessionExample.json';
 import typedDataStructArrayExample from '../../__mocks__/typedDataStructArrayExample.json';
 import { number } from '../../src';
+import { getSelectorFromName } from '../../src/utils/hash';
+import { MerkleTree } from '../../src/utils/merkle';
 import { BigNumberish } from '../../src/utils/number';
-import { encodeType, getMessageHash, getStructHash, getTypeHash } from '../../src/utils/typedData';
+import {
+  StarkNetDomain,
+  encodeType,
+  encodeValue,
+  getMessageHash,
+  getStructHash,
+  getTypeHash,
+} from '../../src/utils/typedData';
 
 describe('typedData', () => {
   test('should get right type encoding', () => {
-    const typeEncoding = encodeType(typedDataExample, 'Mail');
+    const typeEncoding = encodeType(typedDataExample.types, 'Mail');
     expect(typeEncoding).toMatchInlineSnapshot(
       `"Mail(from:Person,to:Person,contents:felt)Person(name:felt,wallet:felt)"`
     );
-    const typeEncodingStructArr = encodeType(typedDataStructArrayExample, 'Mail');
+    const typeEncodingStructArr = encodeType(typedDataStructArrayExample.types, 'Mail');
     expect(typeEncodingStructArr).toMatchInlineSnapshot(
       `"Mail(from:Person,to:Person,posts_len:felt,posts:Post*)Person(name:felt,wallet:felt)Post(title:felt,content:felt)"`
     );
   });
 
   test('should get right type hash', () => {
-    const typeHashDomain = getTypeHash(typedDataExample, 'StarkNetDomain');
+    const typeHashDomain = getTypeHash(typedDataExample.types, 'StarkNetDomain');
     expect(typeHashDomain).toMatchInlineSnapshot(
       `"0x1bfc207425a47a5dfa1a50a4f5241203f50624ca5fdf5e18755765416b8e288"`
     );
-    const typeHashPerson = getTypeHash(typedDataExample, 'Person');
+    const typeHashPerson = getTypeHash(typedDataExample.types, 'Person');
     expect(typeHashPerson).toMatchInlineSnapshot(
       `"0x2896dbe4b96a67110f454c01e5336edc5bbc3635537efd690f122f4809cc855"`
     );
-    const typeHashMail = getTypeHash(typedDataExample, 'Mail');
+    const typeHashMail = getTypeHash(typedDataExample.types, 'Mail');
     expect(typeHashMail).toMatchInlineSnapshot(
       `"0x13d89452df9512bf750f539ba3001b945576243288137ddb6c788457d4b2f79"`
     );
-    const typeHashPost = getTypeHash(typedDataStructArrayExample, 'Post');
+    const typeHashPost = getTypeHash(typedDataStructArrayExample.types, 'Post');
     expect(typeHashPost).toMatchInlineSnapshot(
       `"0x1d71e69bf476486b43cdcfaf5a85c00bb2d954c042b281040e513080388356d"`
     );
-    const typeHashMailWithStructArray = getTypeHash(typedDataStructArrayExample, 'Mail');
+    const typeHashMailWithStructArray = getTypeHash(typedDataStructArrayExample.types, 'Mail');
     expect(typeHashMailWithStructArray).toMatchInlineSnapshot(
       `"0x873b878e35e258fc99e3085d5aaad3a81a0c821f189c08b30def2cde55ff27"`
     );
+    const selectorTypeHash = getTypeHash({}, 'selector');
+    expect(selectorTypeHash).toMatchInlineSnapshot(
+      `"0x1d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470"`
+    );
+  });
+
+  test('should transform type selector', () => {
+    const selector = 'transfer';
+    const selectorHash = getSelectorFromName(selector);
+    const rawSelectorValueHash = encodeValue({}, 'felt', selectorHash);
+    const selectorValueHash = encodeValue({}, 'selector', selector);
+    expect(selectorValueHash).toEqual(rawSelectorValueHash);
+    expect(selectorValueHash).toMatchInlineSnapshot(`
+      Array [
+        "felt",
+        "0x83afd3f4caedc6eebf44246fe54e38c95e3179a5ec9ea81740eca5b482d12e",
+      ]
+    `);
+  });
+
+  test('should transform merkle tree', () => {
+    const tree = new MerkleTree(['0x1', '0x2', '0x3']);
+    const [, merkleTreeHash] = encodeValue({}, 'merkletree', tree.leaves);
+    expect(merkleTreeHash).toBe(tree.root);
+    expect(merkleTreeHash).toMatchInlineSnapshot(
+      `"0x551b4adb6c35d49c686a00b9192da9332b18c9b262507cad0ece37f3b6918d2"`
+    );
+  });
+
+  test('should transform merkle tree with custom types', () => {
+    const leaves = [
+      {
+        contractAddress: '0x1',
+        selector: 'transfer',
+      },
+      {
+        contractAddress: '0x2',
+        selector: 'transfer',
+      },
+      {
+        contractAddress: '0x3',
+        selector: 'transfer',
+      },
+    ];
+    const hashedLeaves = leaves.map(
+      (leaf) =>
+        encodeValue(
+          {
+            Policy: [
+              { name: 'contractAddress', type: 'felt' },
+              { name: 'selector', type: 'selector' },
+            ],
+          },
+          'Policy',
+          leaf
+        )[1]
+    );
+    const tree = new MerkleTree(hashedLeaves);
+    const [, merkleTreeHash] = encodeValue(
+      {
+        Parent: [{ name: 'root', type: 'merkletree', contains: 'Policy' }],
+        Policy: [
+          { name: 'contractAddress', type: 'felt' },
+          { name: 'selector', type: 'selector' },
+        ],
+      },
+      'merkletree',
+      leaves,
+      { key: 'root', parent: 'Parent' }
+    );
+    expect(merkleTreeHash).toBe(tree.root);
+    expect(merkleTreeHash).toMatchInlineSnapshot(
+      `"0x75c4f467f4527a5348f3e302007228a6b0057fc4c015f981ffb5b3ace475727"`
+    );
   });
 
   test('should get right hash for StarkNetDomain', () => {
-    const hash = getStructHash(typedDataExample, 'StarkNetDomain', typedDataExample.domain as any);
+    const hash = getStructHash(
+      typedDataExample.types,
+      'StarkNetDomain',
+      typedDataExample.domain as StarkNetDomain
+    );
     expect(hash).toMatchInlineSnapshot(
       `"0x54833b121883a3e3aebff48ec08a962f5742e5f7b973469c1f8f4f55d470b07"`
     );
@@ -122,4 +210,14 @@ describe('typedData', () => {
       `"0x70338fb11b8f70b68b261de8a322bcb004bd85e88ac47d9147982c7f5ac66fd"`
     );
   });
+
+  test('should transform session message correctly', () => {
+    const hash = getMessageHash(
+      typedDataSessionExample,
+      '0xCD2a3d9F938E13CD947Ec05AbC7FE734Df8DD826'
+    );
+    expect(hash).toMatchInlineSnapshot(
+      `"0x1ad0330a62a4a94eae5ea1a7ad96388179d2e4d33e6f909d17421d315110653"`
+    );
+  });
 });