What is MTP (Merkle Tree Proof) and why is it an ideal Proof of Work algorithm?

The MTP algorithm was devised by Alex Biryukov and Dmitry Khovratovich from the University of Luxembourg in their paper published on the 11 June 2016 titled Egalitarian Computing. These are the same researchers who came up with Equihash that is currently used in ZCash.

MTP was created as a way to remedy the disparity between ordinary users and adversaries/cheaters where the latter could use botnets, GPU, FPGA and ASICS to gain a significant advantage and mount a cheaper attack. The basic concept is that it should establish the same price/cost for a single computation unit on all platforms meaning that there is no single device that should gain a significant advantage over another for the same price hence promoting egalitarian computing. With egalitarian computing, attackers would need to spend the same amount as ordinary users for equivalent 'hashing' power.

You can see this happening with existing proof of work algorithms used in existing algorithms such as SHA256 (Bitcoin), Scrypt (Litecoin, Dogecoin) and X11 (Dash) where hashing power is centralized in ASIC farms and normal users are not incentivised to participate in the security of the network. Even in newer schemes such as Ethash which is used in Ethereum, although it is deliberately designed to be GPU friendly, we feel that it is overly favored with GPUs being more than a hundred times more efficient than CPU, again favoring specialization to GPU farms.

Besides its egalitarian properties, MTP although is computationally and memory intensive to find the solution, once found, its solution can be quickly and efficiently verified without requiring a lot of memory. This is important since by keeping verification quick, this makes the network more resistant to DoS attacks that target verifiers.