search

dat-ecosystem-archive / book

Documentation on how to implement the Dat Protocol [ DEPRECATED - see https://github.com/hypercore-protocol/new-website/tree/master/guides for similar functionality. More info on active projects and modules at https://dat-ecosystem.org/ ]
https://datprotocol.github.io/book/
Apache License 2.0
68 stars 9 forks source link

Merkle tree indices #19

Closed aral closed 5 years ago

aral commented 5 years ago

The Merkle Tree chapter is hugely useful in understanding how DAT implements a Merkle Tree in hypercore. However, while reading it, I was confused by the following:

  1. Inconsistent application of indices between the steps of the example. e.g., Indices for the tree change from 1-based to 0-based in Entry 4 and a zero-based index is added to the data file in Entry 3.

  2. Ambiguity between indices of elements in the files and the node index of the tree. (e.g., Does sig(0) in entry 4 mean signature of data[0], tree[0], or hash 0?

  3. The odd-numbered nodes in the tree file. Given the lack of indices in the presentation (and given they can be calculated at will), it is easy to deduce that these are not stored in the file but it would be good to have this explicitly stated.

In an attempt to clarify things, this pull request:

  1. Implements consistent 0-based indices for file indices.
  2. Uses array look-up syntax when referring to file indices (e.g., data[0] to refer to the 0th item in the data file).
  3. Uses #n notation to refer to hashes within the tree (e.g., #4 is stored in index 2 of the tree file).
  4. Explicitly states that odd-numbered nodes are not stored in the tree file.
  5. Consistently applies function notation to represent hashing – hash() – and signatures – sig().
aral commented 5 years ago

Thank you :) And thanks for writing it to begin with :)