What is MTP?

MTP (Merkle Tree Proof) is a memory-hard Proof of Work algorithm that was designed to combine the security benefits of memory-hard computation with the practical advantage of fast verification. The algorithm works in two phases: first, miners must construct a large Merkle tree in memory (requiring approximately 2 GB of RAM), populating it with hash values derived from the block header data. In the second phase, miners generate a compact proof consisting of selected paths through the Merkle tree that demonstrate they performed the memory-intensive computation, without requiring the verifier to rebuild the entire tree. This proof is included in the block header for validation by network nodes.

The key innovation of MTP is its asymmetry between proof generation and verification — while mining requires substantial memory and computation, verifying a proof takes only milliseconds and requires minimal resources. This property makes it ideal for lightweight clients and mobile nodes that need to validate blocks without significant hardware. MTP achieves strong ASIC resistance through its memory requirements, as the 2 GB working set makes ASIC development prohibitively expensive. The algorithm was formally described in an academic paper and underwent security analysis that established its resistance to time-memory trade-off attacks, where an attacker might try to use less memory at the cost of more computation.

MTP was originally adopted by Zcoin (now rebranded as Firo), a privacy-focused cryptocurrency that launched in 2016. Zcoin implemented MTP as its mining algorithm in December 2018, replacing the previous Lyra2REv2 algorithm as part of the project's commitment to egalitarian mining. MTP served Zcoin well during its period of use, enabling GPU miners to participate fairly in block production while keeping verification costs low for the network. Firo later transitioned away from MTP to the FiroPoW algorithm (based on ProgPoW) in October 2021, seeking even stronger ASIC resistance. Despite no longer being actively used by Firo, MTP remains an important contribution to the field of memory-hard proof systems and influenced subsequent algorithm designs.