Help needed regarding merkle implementation in noir

Noir
1 
let is_member = std::merkle::check_membership(root, leaf, index, hashpath);
```|

In the above , what is index? In the examples, we are using index = 0 . Why is that the case?

is index used to denote the position of the leaf, left or right?
50 Likes
2

So the index is the position of the leaf in the tree. In a binary merkle tree it is broken down into a bit array where each bit is used to determine whether the current leaf we are hashing is on the left or right. In our stdlib you can see this in more detail: noir/noir_stdlib/src/merkle.nr at bd8379e2e847ab5196ff01e23add5a277fc6eb1c · noir-lang/noir · GitHub. We are going to be deprecating the check_membership method in favor of the method linked in the next version of Noir.

19 Likes
3

Just to supplement the other answer, I think the “position of the leaf in the tree” means that leftmost “leaf index” is 0 and the rightmost is ( 2^height)-1 (if height does not include root).

                                  ┏━━━┓
root:               ╭─────────────┨ r ┠─────────────╮
                    │             ┗━━━┛             │
                  ┏━┷━┓                           ┏━┷━┓
lyr2:       ╭─────┨ x ┠─────╮               ╭─────┨ x ┠─────╮
            │     ┗━━━┛     │               │     ┗━━━┛     │
          ┏━┷━┓           ┏━┷━┓           ┏━┷━┓           ┏━┷━┓
lyr1:   ╭─┨ x ┠─╮       ╭─┨ x ┠─╮       ╭─┨ x ┠─╮       ╭─┨ x ┠─╮
        │ ┗━━━┛ │       │ ┗━━━┛ │       │ ┗━━━┛ │       │ ┗━━━┛ │
      ┏━┷━┓   ┏━┷━┓   ┏━┷━┓   ┏━┷━┓   ┏━┷━┓   ┏━┷━┓   ┏━┷━┓   ┏━┷━┓
lry0: ┃ 0 ┃   ┃ 1 ┃   ┃ 2 ┃   ┃ 3 ┃   ┃ 4 ┃   ┃ 5 ┃   ┃ 6 ┃   ┃ 7 ┃
      ┗━━━┛   ┗━━━┛   ┗━━━┛   ┗━━━┛   ┗━━━┛   ┗━━━┛   ┗━━━┛   ┗━━━┛

height = 3
num_leaves = (2^height) = 2^3 = 8
59 Likes
4

Thanks for the explanation

25 Likes