Merkle
Pure-Kotlin port of libtorrent's merkle-tree free functions (include/libtorrent/aux_/merkle.hpp + src/merkle.cpp).
BitTorrent v2 (BEP 52) represents every file as a binary merkle tree of SHA-256 hashes. The leaves are 16 KiB block hashes; interior nodes are SHA-256(left || right); the root is the file's piece-tree root that ends up in the .torrent. When the number of leaves is not a power of two the tree is padded on the right with a fixed pad hash (SHA-256(0), then SHA-256(pad||pad) one level up, etc.).
Node indexing
libtorrent stores the tree as a flat array in breadth-first ("heap") order:
0 <- layer 0 (root)
1 2 <- layer 1
3 4 5 6 <- layer 2
7 8 9 10 11 12 13 14 <- layer 3 (leaves, for 8 leaves)So node i's children are 2i+1 and 2i+2, and its parent is (i-1)/2. A tree with L leaves (L a power of two) has 2L-1 nodes and its first leaf is at index L-1.
This object carries only the pure computation half of libtorrent's merkle code: index arithmetic, root computation, and node validation. Anything tied to on-disk storage layout lives elsewhere; see MerkleTree for the in-memory tree container.
Types
Result of computeProofRoot: the root the supplied base hashes and proofLayers uncle hashes fold up to, plus the subtreeRoot (the root of just the base-hash subtree, i.e. the node the uncle hashes prove).
Properties
Functions
Folds a run of base-layer hashes into their subtree root, then walks the proofLayers (uncle / sibling) hashes upward, computing the implied tree root. Pure function: it does not consult or mutate any existing tree, it just computes what root these hashes claim. Compare the returned root against the known file root to accept or reject the proof.
Builds a file's BitTorrent v2 merkle root from its 16 KiB-block SHA-256 leaf hashes. This is the clear top-level entry point a v2 download / torrent creator uses: pass the file's block hashes in order and get the pieces root that ends up in the .torrent.
Index of treeNode's first (left) child, 2*treeNode + 1. From merkle_get_first_child.
Index of the first descendant of treeNode exactly depth layers below it, ((treeNode + 1) << depth) - 1. From the two-argument merkle_get_first_child.
Offset of flat node idx within its own layer. From merkle_get_layer_offset.
Sibling node index of treeNode. Even nodes sit to the right of their sibling (so the sibling is to the left, -1); odd nodes sit to the left (sibling to the right, +1). From merkle_get_sibling.
Computes SHA-256(left || right), one interior merkle node.
Index of the first node in layer, counting the root as layer 0. (1 << layer) - 1. From merkle_layer_start.
Computes the merkle root from a list of leaves, padding the right side with padHash when the leaf count is not a power of two. This is the top-level entry point that mirrors merkle_root (it rounds the leaf count up to a power of two and delegates to rootScratch).
The pad hash for a tree level that holds pieces real nodes, given the full leaf level holds blocks nodes. Starts from SHA-256(0) (the all-zero leaf pad) and folds it up (pad = SHA-256(pad || pad)) once per level until the level width reaches blocks. From merkle_pad.
The core root computation, mirroring merkle_root_scratch.
Flat node index given a layer and an offset from the start of that layer. From merkle_to_flat_index.
True if parent == SHA-256(left || right). From merkle_validate_node.
Verifies a BitTorrent v2 hashes proof (BEP 52 / hash_request): given the file's known piecesRoot, a contiguous run of baseHashes starting at startIndex in the base layer, and the proofLayers uncle hashes, returns true iff they hash all the way up to piecesRoot.