doc/mth.texi

   1 @node MTH
   2 @cindex MTH
   3 @cindex hashing
   4 @cindex merkle tree
   5 @cindex BLAKE3
   6 @unnumbered Merkle Tree Hashing
   7
   8 NNCP uses @url{https://github.com/BLAKE3-team/BLAKE3, BLAKE3} hash
   9 function in @url{https://en.wikipedia.org/wiki/Merkle_Tree, Merkle Tree}
  10 mode of operation for checksumming @ref{Encrypted, encrypted packets}
  11 and @ref{Chunked, chunked} files.
  12
  13 Previously ordinary BLAKE2b-256 was used, but it prevented partial
  14 calculations of file parts, so you had to fully read the whole file
  15 again after its resumed download.
  16
  17 MTH divides data on 128 KiB blocks, hashes each of them independently
  18 and then calculates the Merkle tree root:
  19
  20 @verbatim
  21                 node3
  22                /   \
  23               /     \
  24            node2    leaf4
  25           /    \       \
  26          /      \       \
  27         /        \       \
  28        /          \       \
  29       /            \       \
  30     node0         node1    leaf4
  31    /    \        /    \      \
  32   /      \      /      \      \
  33 leaf0  leaf1  leaf2  leaf3  leaf4
  34   |      |      |      |      |
  35 block  block  block  block  block
  36 @end verbatim
  37
  38 Leaf's value is keyed BLAKE3-256 hash of underlying block (128 KiB,
  39 except for probably the last one). Node's value is keyed BLAKE3-256 hash
  40 of two underlying leafs. Keys are
  41 @verb{|BLAKE3-256("NNCP MTH LEAF")|} and
  42 @verb{|BLAKE3-256("NNCP MTH NODE")|}.
  43 Keyed operation allows working with an aligned data (128KiB or 64B
  44 boundaries), unlike popular way of prepending @verb{|0x00|} and
  45 @verb{|0x01|} to the hashed data, being more efficient with an attention
  46 to BLAKE3's internal Merkle tree.