Sparse Merkle trees
timkaebisch opened this issue · 4 comments
I think there is a small mistake in the docs for the taproot assets protocol
For example, we may create a Sparse Merkle tree using a fictitious hashing function of sha002, which results in a number between 0 and 3. We generate a Sparse Merkle tree with 4 leaves: 0, 1, 2 and 3. Only leaf 2 is populated, all other leaves are empty. To find leaf 2 (written 10 in binary), we go right at the first branch (1), then left at the second branch (0).
This suggests that in binary format a 1 means turning right and a 0 means turning left (which is correct).
But I think there is a small error in the next section:
In Sparse Merkle trees, every leaf can be described as a guide to itself through a map when expressed in binary form. The map is the Sparse Merkle tree itself, and the guide is represented by instructions on whether to turn left or right at each fork. The 9th leaf in a 2^4 large Sparke Merkle tree for example is expressed in binary as 1001, meaning we find the appropriate leaf by turning left, then right, right and finally left.
This suggests to turn left on a 1 and right on a 0. It should be the other way round.
Furthermore, in my opinion the wording "9th" leaf is is somewhat misleading. Since we start with the index 0 the "9th" leaf would be leaf number 8. I think the text should say something like "leaf number 9".
Can someone confirm the small mistake mentioned above? If so, I will create a pull request.
cc @Liongrass
Thank you for reading closely! You're welcome to make a pull request, or I'll just edit the changes in myself quickly
I've corrected "9th leaf" to "10th leaf" and reversed the order of left and right in the second example, so that 0 means left and 1 means right consistently in the article. Thank you again for bringing this to our attention!
Thank you @Liongrass for the quick changes!