Merkle Tree Proof (MTP) – An Ideal Solution To Prevent Centralization of Cryptocurrency Mining

 

Proof-of-work (PoW) algorithms were first presented by Dwork and Naor in 1992 as a computational based technique to counteract email spamming, or more specifically, to limit access to specific content. The ideas is that the user has to compute a relatively hard function to be able to access the content, which would prevent excessive use.. With the advent of bitcoin, PoW algorithms have become a rather popular area of academic research.

Within the context of cryptocurrencies, PoW algorithms play a pivotal role in maintaining consensus across nodes of cryptocurrency networks regarding the state of the distributed ledger of blockchains. PoWs are generated by miners across the network, each PoW is computed over a block of recently generated transactions. When a new block of transactions is generated, it propagates across the network and its PoW is validated by the nodes which will accordingly update their view of the state of the blockchain.

Given the fact that each and every node across the network will perform verification of a block’s transactions, slow verification would render nodes susceptible to DDoS attacks and increase the possibility of forking. Accordingly, PoW schemes of cryptocurrency protocols have to promote “efficient verification” of proofs. Also, computing proofs have to be as efficient, on ordinary CPUs, as they are on ASICs. This is crucial to prevent centralization, when the majority of mining hash power comes from centralized ASIC mining farms, as is the case today with bitcoin. Many consider this a contradiction to bitcoin’s philosophy which endorses decentralization.

One of the best ways to minimize centralization of mining is to utilize “memory hard functions“. These functions require relatively large amounts of memory in order to compute PoWs and will impose computational penalties on algorithms attempting to compute them using less amount of memory. Memory hard functions will minimize the advantage of ASIC mining hardware over ordinary PCs, due to the fact that memory intensive operations cannot be executed much more efficiently via dedicated hardware when compared to ordinary PCs.

The most popular cryptocurrency protocol that utilizes memory hard functions is litecoin. Nevertheless, despite the memory hardness of scrypt based coins such as litecoin, a major disadvantage of scrypt based coins is that tuning their protocols to utilize substantial amounts of memory won’t yield efficient verification.

More recently, Alex Biryukov and Dmitry Khovratovich, introduced Merkle Tree Proof (MTP) PoW algorithms during the USENIX Security Symposium in 2016. MTP can provide all the properties needed within a cryptocurrency PoW scheme, such as fast, efficient verification and resistance to ASIC mining. Accordingly, MTP has received significant attention from cryptocurrency enthusiasts during the past few months.

MTP utilizes a design that integrates a memory hard function along with a Merkle hash tree. This design is similar to a previous design that proposed building a Merkle hash tree on top of data produced by computing a memory hard function ( e.g. a graph that is associated with high pebbling complexity). The MTP design is also related to previously proposed proof-of-space (PoS) scheme in 2015.

 

Zcoin is by far the first coin to implement the MTP PoW scheme, yet we can expect more coins to start adopting this idea that can help combat centralization of cryptocurrency mining.