doc/mth.texi

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