Confusing of leafs and nodes in render()

[billbaobab]

Hi,

Background: I'm currently working on a Merkle Tree construction using a zk domain specific language (Noir). I want it to be compatible with OZ's contracts and JS tooling. For that reason I'm trying to re-implement the OZ implementation. What I'm essentially doing is constructing a Merkle Tree using the JS lib and trying to get to the same outcome in Noir.

During that exercise I got quite confused about the result of the render() method. This is the output:

0) 0a011c2e1f95bf901ad43b1cfc3d115644b43d01f6874c711d9b170bf7a12b85
├─ 1) 654483444109f3ee991310d9602559847810f95ad4e5e364ff26287732ffc9df
│  ├─ 3) 8b111d9c2a63533862fc38fd00318863a8a979027d243afcf3541986efa07eff
│  │  ├─ 7) f8330a2c877270873c192c2bc9468a45f87284fcf68ef5c8aeed39a26721e6eb
│  │  └─ 8) eb02c421cfa48976e66dfb29120745909ea3a0f843456c263cf8f1253483e283
│  └─ 4) efec3a4c8afd502e041a85cf63d8795b03d9cee6d9f126a972131d7912c07e85
│     ├─ 9) b9c7e0d81a7d808cfd3058fedd657c6ff51c95c3af8c1fd8be9d5c416b1b8d6c
│     └─ 10) b92c48e9d7abe27fd8dfd6b5dfdbfb1c9a463f80c712b66f3a5180a090cccafc
└─ 2) 64762e46a05136a358342de9993be89b14a17cf6de8c5fac8657e550f516b06e
   ├─ 5) e8ab5092a959d6fcd6c196c0d45066cee7457f2a1bc97910d3afc70619a76695
   │  ├─ 11) 99d34ac9269a939bf57828b114d22e3b906ef79fd21c891623c930569e3a70b0
   │  └─ 12) 793a6a518194f9f6305002d8c21205e151badf160e118efcb069f270131c9edb
   └─ 6) c9bce53760bdf7b9114c26708af3a47c8761f510ea94c7de81e2682ce553b396
      ├─ 13) 5de4e9a9ee8b2d3d399cb8d2e86b3e49a1579968d722640f25c31e30039035f8
      └─ 14) 0730334eb8f8c63981dd1c15ca2dcd670440d3cf0cbbe33687ccb38d499b06bf

However when re-implementing that tree in Noir I noticed that in order to get to the same root value, the tree actually has to look like this (the numbers in my visualization correspond to the "indices" as returned by the render() method, so for instance 14 corresponds to 14) 0730334eb8f8c63981dd1c15ca2dcd670440d3cf0cbbe33687ccb38d499b06bf):

I understand from this issue #26 that it is expected that leafs are stored backwards. So far so good, but what I don't understand is the irregularity in the sorting as highlighted in red in my visualization.

Can you help me understand this? Or is it a bug?

Thanks!

[billbaobab]

For the sake of completeness, this is how I'm creating & rendering the tree:

// (1)
const values = [
  ["0x1111111111111111111111111111111111111111", "5000000000000000000"],
  ["0x2222222222222222222222222222222222222222", "2500000000000000000"],
  ["0x3333333333333333333333333333333333333333", "5000000000000000000"],
  ["0x4444444444444444444444444444444444444444", "2500000000000000000"],
  ["0x5555555555555555555555555555555555555555", "5000000000000000000"],
  ["0x6666666666666666666666666666666666666666", "2500000000000000000"],
  ["0x7777777777777777777777777777777777777777", "5000000000000000000"],
  ["0x8888888888888888888888888888888888888888", "2500000000000000000"],
];

// (2)
const tree = StandardMerkleTree.of(values, ["address", "uint256"]);

// (3)
console.log("Merkle Root:", tree.render());

[frangio]

When you hash an inner node you need to sort the two children:

merkle-tree/src/core.ts

Line 6 in 0951d3c

const hashPair = (a: Bytes, b: Bytes) => keccak256(concatBytes(...[a, b].sort(compareBytes)));

This is probably the reason for what you're observing.

Make sure to look at core.ts if you are reimplementing the algorithm.