MerkleTree
In-memory BitTorrent v2 merkle tree for one file: a focused pure-computation port of libtorrent's aux::merkle_tree (include/libtorrent/aux_/merkle_tree.hpp
src/merkle_tree.cpp).
Each file in a v2 torrent has its own merkle tree. The leaves are the file's 16 KiB block hashes; somewhere above them sits the piece layer (whole pieces); the apex is the file's root hash, which is published in the .torrent. The number of blocks is rounded up to a power of two by padding the leaf layer with the all-zero block hash.
libtorrent's production class carries several space-optimised storage modes (empty_tree, piece_layer, block_layer, full_tree) plus resume-data and on-disk plumbing. This port keeps the conceptual core that is pure computation:
a flat
2*numLeafs-1node array (the "full tree" representation),filling interior nodes from a complete leaf set (fillFromLeaves),
filling interior nodes from the piece layer (fillFromPieces),
reading the root and arbitrary nodes,
verifying a candidate root / piece layer against a known root,
tracking which block hashes have been verified against the root.
The verification helpers rely on the invariant libtorrent maintains: interior nodes are either correct or all-zero, never wrong.
Index arithmetic and the standalone root computation live in Merkle.
Parameters
number of real (non-padding) block hashes in the file. Must be >= 1.
blocks contained in one piece, always a power of two. This fixes where the piece layer sits relative to the leaves. For the common case where a piece is a block, pass 1.
the file's known root hash (the apex). Verification compares against this. May be null when the root is not yet known (e.g. building a tree to then read its root).
Types
Properties
Functions
Verifies a BitTorrent v2 hashes proof against this tree and, on success, inserts the proven hashes and their uncle nodes. Pure-computation analogue of merkle_validate_and_insert_proofs: the run of baseHashes (starting at flat base-layer offset startIndex) is folded into a subtree root, then the proofLayers uncle hashes are walked upward until they reach a hash already known in this tree (or the expectedRoot). If the proof checks out, the subtree root, the uncle hashes, and the recomputed ancestors are written in and the function returns true; otherwise the tree is left unchanged.
Blocks per piece, reconstructed from blocksPerPieceLog.
The known/expected root supplied at construction, if any.
Places leaves at the block layer (padding the rest with the all-zero block hash) and computes every interior node up to the root. The resulting tree[0] is the file root. Mirrors loading the block layer and calling merkle_fill_tree.
Places the pieces hashes at the piece layer, pads the piece layer with the proper pad hash (Merkle.pad), computes the nodes from the piece layer up to the root, and computes each piece's block-layer descendants as padding so the tree is internally consistent for the levels at and above the piece layer.
The hash at flat node idx (all-zero if unknown).
Extracts the hashes needed to answer a BitTorrent v2 hash_request (BEP-52) from this tree. This is the inverse of addHashesWithProof / Merkle.verifyProof. Direct port of merkle_tree::get_hashes (src/merkle_tree.cpp).
True if block blockIndex's hash has been verified against the root.
True if every block hash has been verified. From is_complete (full-tree).
True if every block belonging to pieceIndex has been verified against the root. A piece is considered verified once all of its (real) constituent block hashes are verified. Mirrors merkle_tree::blocks_verified collapsed to a single piece. For single-block pieces this is just isBlockVerified.
Loads a file's whole piece layer (the per-piece roots) and validates it against the expectedRoot before committing. On success the piece layer and all of its ancestors up to the root are filled in. The block layer below the piece layer stays padding/unknown, so only piece-level nodes and above become meaningful, exactly like libtorrent's mode_t::piece_layer.
Loads a single piece-layer row for this file: the contiguous run of piece roots pieces, the first of which is piece number startPiece. Each supplied piece root is written into its piece-layer slot. The interior nodes are not recomputed (an enclosing proof or a later full loadPieceLayer establishes verification); this is the building-block libtorrent uses when filling the tree row-by-row from get_hashes responses.
Flat index of the first node in the piece layer.
The root hash. If the tree has been filled this is tree[0]; otherwise the expectedRoot passed to the constructor (or all-zero if neither is set). Mirrors merkle_tree::root().
Sets the hash at flat node idx directly (no validation).
Sets a single block hash and, if the surrounding subtree is now fully known, verifies it against the already-known ancestor hashes, marking the affected blocks as verified on success. A focused analogue of merkle_tree::set_block for the full-tree representation.
True if every adjacent leaf pair in this tree hashes to its stored parent. That means the layer immediately above the leaves is internally consistent. Direct port of merkle_validate_single_layer. (A one-node tree is trivially valid.)
Recomputes the root from the currently-set block layer and reports whether it matches the expectedRoot. Requires all numBlocks real leaves to be present.
Validates a candidate piece layer against the expectedRoot without mutating this tree. Mirrors the check inside load_piece_layer: pad the piece layer to a power of two with Merkle.pad, fold to a root, and compare.
Verifies a run of a single piece's block-leaf hashes against that piece's already-known piece-layer root, without marking anything. Folds the supplied leaves (padded as needed) and compares to the stored piece root.