BitTorrent v2 Merkle Tree Storage Overhead

This article explains the storage overhead of Merkle tree hashes in the BitTorrent v2 protocol (BEP 52). It covers the baseline costs of SHA-256 hashes, how the .torrent metainfo file stores piece layers and file roots, memory and disk implications compared to BitTorrent v1, and the network overhead required for transmitting cryptographic proof paths.

Hash Size: SHA-1 vs. SHA-256

BitTorrent v1 utilizes 160-bit SHA-1 hashes (20 bytes per piece), whereas BitTorrent v2 replaces SHA-1 with 256-bit SHA-256 hashes (32 bytes per piece). This transition results in an immediate 60% increase in raw byte storage for each recorded hash entry.

Metainfo (.torrent File) Structure

BitTorrent v2 restructures metainfo to handle Merkle trees per file rather than across the entire torrent payload:

1. Pieces Root (Per-File Overhead): Every file entry in the file tree dictionary contains a 32-byte pieces root hash representing the top of that file’s Merkle tree.
2. Piece Layers: Instead of storing the complete Merkle tree in the .torrent file, the metainfo only stores a specific layer corresponding to the designated piece size (e.g., 512 KiB, 1 MiB, or 2 MiB).
   • Large Files: A file spanning \(N\) pieces requires \(N \times 32\text{ bytes}\) in the piece layers dictionary.
   • Small Files: Files equal to or smaller than the defined piece size do not require entries in piece layers, because the file root itself is the piece hash. This reduces metadata bloat for torrents containing numerous small files.

Quantitative Overhead Calculation

To determine the storage cost of Merkle tree data within a .torrent file:

• Leaf Node Baseline: Leaf hashes are calculated over 16 KiB blocks.
• Piece Layer Calculation: If a 1 GiB file uses a 1 MiB piece size:
  • Number of pieces: \(1\text{ GiB} / 1\text{ MiB} = 1,024\text{ pieces}\).
  • Piece layer storage: \(1,024 \times 32\text{ bytes} = 32,768\text{ bytes}\) (32 KiB).
  • Root hash storage: \(32\text{ bytes}\).
  • Total hash overhead: \(32.03\text{ KiB}\) for that file.

Compared to BitTorrent v1 for the same 1 GiB file at 1 MiB pieces: * \(1,024 \times 20\text{ bytes} = 20,480\text{ bytes}\) (20 KiB).

The relative storage cost in the metainfo file increases by \(12\text{ KiB}\) (60%), matching the difference in digest length.

In-Memory and Dynamic Tree Generation Overhead

BitTorrent v2 clients do not need to store the intermediate layers of the Merkle tree permanently on disk. Intermediate nodes can be derived on the fly by hashing together sibling nodes:

• A complete binary Merkle tree for an \(N\)-block file contains \(2N - 1\) total nodes.
• For a 1 GiB file consisting of 65,536 leaf blocks (16 KiB each), the total tree contains 131,071 nodes.
• Retaining the entire tree in memory consumes approximately \(131,071 \times 32\text{ bytes} \approx 4.19\text{ MiB}\).
• Clients typically reconstruct intermediate hashes dynamically during verification or cache only sparse levels to minimize RAM consumption.

Network Transmission Overhead (Proofs)

During piece exchange, peers verify incoming 16 KiB blocks before the entire piece is complete:

• When transferring blocks within a piece, peers must transmit the uncle hashes (audit path) to validate the block against the known piece root.
• The length of this proof path is \(O(\log_2 M)\), where \(M\) is the number of 16 KiB blocks in a piece.
• For a standard 1 MiB piece (\(2^6 = 64\) blocks), the proof depth is 6 hashes, adding up to \(6 \times 32 = 192\text{ bytes}\) of verification payload per transmitted block unless intermediate hashes are already cached by the receiving peer.