search

noir-lang / docs

19 stars 22 forks source link

Unclear explanation of merkle implementation #192

Closed supernovahs closed 1 year ago

supernovahs commented 1 year ago

Problem

I am trying to understand how merkle proof works in noir.

I have the following doubts:

Happy Case

would be great if we can get more info related to this

Alternatives Considered

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

Yes

Support Needs

No response

critesjosh commented 1 year ago

The index is the index of the leaf in the merkle tree. The docs page is just showing index 0 as an example. You can pass any valid index and hash path to the compute_merkle_root function.

You have to either lookup or calculate the hash path for the merkle tree that you want to compute. The hash path on the example page is from an example merkle tree, but this could be anything.

I will update the page to make it more clear, thanks for raising this issue.

supernovahs commented 1 year ago

What do u mean by index of the leaf of the 🌲?

If a merkle tree has height of 3 . Then what will be the index of the most bottom left leaf?0? Example

Thanks

On Mon, 12 Jun, 2023, 22:53 crites, @.***> wrote:

The index is the index of the leaf in the merkle tree. The docs page is just showing index 0 as an example. You can pass any valid index and hash path to the compute_merkle_root function.

You have to either lookup or calculate the hash path for the merkle tree that you want to compute. The hash path on the example page is from an example merkle tree, but this could be anything.

I will update the page to make it more clear, thanks for raising this issue.

— Reply to this email directly, view it on GitHub https://github.com/noir-lang/docs/issues/192#issuecomment-1587751768, or unsubscribe https://github.com/notifications/unsubscribe-auth/AVYNMGV42C4CQRNF6IPW5ULXK5GALANCNFSM6AAAAAAZDBFHZE . You are receiving this because you authored the thread.Message ID: @.***>

TomAFrench commented 1 year ago

Only the bottom row of the tree are considered leaves so you'll have

   root
  /   \
 /\   /\
0 1  2  3

When you're proving the existence of a leaf in the tree then the index just represents which of the 4 leaves you're proving for. This encodes which path you're taking to get to the root and so how you should use the hash path (e.g. for index 0 you're always hashing in values on the right, whereas for an index 1 hash the first element in the hash path in from the left and then the second in from the right).

supernovahs commented 1 year ago

thx