Extend MerkleProof with notion of index for unsorted trees or leaf identifiers

[Amxx]

@k06a proposed an implementation for this feature in #2815. A related feature was proposed in https://github.com/OpenZeppelin/openzeppelin-contracts/pull/2851 to compute a leaf identifier when a proof is validated, that could be used as a to index a bitmap.

We feel that this subject requires further thinking/discussion before we commit to providing (and supporting) an implementation.

As a quick summary, this should include two elements:

• A mechanism to verify proofs for "unsorted" trees by providing a "path" to the leaf to properly rebuild the root.
• A mechanism to rebuild a leaf identifier when verifying proofs in "sorted" trees.

Both of these (path and leaf identifier) were called "index" in the linked PRs.

Next steps include:

• [ ] Check similar feature support in other tools/library (such as the MerkleTreeJS library we are using).
• [ ] Discuss the mathematical properties of the corresponding indices.

[frangio]

One thing to note is that our library currently supports trees of depth > 256, while an uint256 index would not support that.

Another concern is that it may be ambiguous if an index refers to an inner node or a leaf.

[Amxx]

About tooling, merkletreejs doesn't include any such index. Depending on the method being called, the path can be encoded differently, but always "extensions to the proof entries".

> merkleTree.getProof(leaf)
[
  {
    position: 'left',
    data: <Buffer 01 7e 66 7f 4b 8c 17 42 91 d1 54 3c 46 67 17 56 6e 20 6d f1 bf d6 f3 02 71 05 5d da fd b1 8f 72>
  },
  {
    position: 'left',
    data: <Buffer 69 de 75 6f ea 16 da dd bb dc cf 85 c8 49 31 5f 51 c0 b5 0d 11 1e 3d 20 63 ca b4 51 80 33 24 a0>
  },
  {
    position: 'right',
    data: <Buffer 19 07 ce 78 77 ec 74 78 2a 26 c1 66 b5 62 bf bd d4 c8 d8 83 3f 98 ad 82 ae 9d c8 e9 8d b2 00 93>
  }
]

> merkleTree.getPositionalHexProof(leaf)
[
  [
    0,
    '0x017e667f4b8c174291d1543c466717566e206df1bfd6f30271055ddafdb18f72'
  ],
  [
    0,
    '0x69de756fea16daddbbdccf85c849315f51c0b50d111e3d2063cab451803324a0'
  ],
  [
    1,
    '0x1907ce7877ec74782a26c166b562bfbdd4c8d8833f98ad82ae9dc8e98db20093'
  ]
]

[frangio]

In the docs for merkletreejs I see that some functions accept an index argument. Do you know what that number is supposed to be?

[Amxx]

These indices are for identifying leaves (from 0 to n-1). This is used, in particular, to distinguish two identical leaves and produce different proofs.

[frangio]

Worth noting that for a balanced tree I think that index is identical to the one that was originally proposed in the linked PRs.

[frangio]

See Generalized Merkle Tree Index in the Ethereum consensus specs.

I said above that uint256 indices wouldn't support trees with depth > 256 but no one should ever need a tree of that size. Merkle trees should be balanced in order to have nice properties. We can still support unbalanced trees but balanced trees should be prioritized.