Zcoin: Merkle Tree Proof, version 1.2

Introduction
Merkle Tree Proof (MTP) is a Proof-of-Work algorithm designed by Alex Biryukov and Dmitry Khovratovich and detailed in the initial version of their paper, Egalitarian Computing (MTPv1). The same duo also designed another Proof-of-Work algorithm, Equihash. MTP is their effort to improve upon Equihash.

MTP was designed to provide a fairer and more democratic process. It was designed to be closer to the initial intention presented by Satoshi Nakamoto in his landmark Bitcoin paper as “one-cpu-one-vote”.

The development of ASICS that far outpaced any CPU or GPU lead to miner centralization where only a handful of companies that could produce these ASICS effectively controlled the supply of new hashrate to a coin. Several past attempts have been made at building ASIC resistance which involved chaining several algorithms together (such as x11) or involving a little memory (such as Scrypt which uses 128kb) both which have failed to provide true ASIC resistance.

In fact, on March 11th, 2018 an ASIC manufacturing company announced the development of miners for “ASIC resistant” using the CryptoNight and CryptoNight algorithms.

MTP aims to solve this issue by introducing memory-hardness on a different scale. Finding a solution is difficult and requires lots of memory. In Zcoin’s reference implementation, 2 GB of RAM are used. MTP can use up to 10 GB of RAM, if elected. However, unlike previous memory hard algorithms, verification is extremely quick and requires little memory, which helps protect against Denial-of-Service attacks on verifiers.

The huge memory requirement also helps mitigate the risk of botnets as the infected system would be more likely to notice any abnormalities caused by mining due to the increased memory load.

Zcoin was ready to implement MTP in August 2017, but a vulnerability was found and they put off implementation while waiting upon the designers to release an update paper that addressed any attacks found. Further, Zcoin funded a bounty to help find any additional attacks on MTP.

Attacks on MTP v1
From the challenge bounty that Zcoin started and funded, a total of five submissions were accepted spanning the MTP paper itself and implementation issues. Four submissions came from Marc Bevand and one submission came from Fabien Coelho and Hidetoshi. Listed below are the submissions for each party. These submissions can also be viewed in their entirety on the dedicated page of Zcoin’s GitHub wiki, MTP Audit and Implementation Bounty Submissions.

Fabien Coelho and Hidetoshi

1. Parallel searches using transposed search hardware

Marc Bevand

1. Argon2 Segment Sharing

2. Location in Merkle tree not verified

3. 1/3rd of openings not verified

4. Time-memory trade-off with 1/16th the memory, 2.88× the time

Bevand’s second attack (above) was submitted under the Audit portion of the bounty. Upon review, a judge declared that the attack was not considered a flaw in the paper but a point not touched upon instead. As such, the judge ruled that it would be considered an implementation bug instead and accepted it under the Implementation portion of the bounty.

MTP v1.2
With these new attacks and bugs in mind, it was time to fix these issues in MTP before Zcoin implemented it. At the beginning of 2018, Biryukov and Khovratovich released an updated version of the paper Egalitarian Computing in which the issues found in MTP were fixed.

At the end of the paper, after the references, a new section can be found, Difference to the Original MTP. Its contents are reproduced below, detailing what has been fixed from MTPv1 to MTPv1.2.

The Argon2 compression function is moified where 3 16-byte blocks of its intermediate block R are replaced with the block index i and input hash H0.

The Merkle tree opening for X[ij] is now included, though the block itself doesn’t need to be included, since it is computed from the blocks (X[φ(ij)],X[ij −1]). Opening the paths of X[ij-1] and X[ij] share most of the nodes, which can be used by efficient implementation;

The positions of opened blocks are now included in the proof and are verified;

4-round Blake2 is used in the Merkle tree generation;

New “skewed blocks” attack strategy is presented in Sect. 4.2. However it does not effect the security parameter recommendations for MTP-Argon2, while it might effect other other MTP-based PoWs such as Itsuku.

Conclusion
With these fixes implemented, Zcoin is now ready to begin implementing MTP. While it is a bit later than its originally scheduled 2017 release, the team wanted to make sure that this would be done correctly and securely. In a YouTube video featuring Chief Operations Officer of Zcoin, Reuben Yap, then community manager, he stated that they’ve already begun using their existing MTPv1 code and are adapting it to comply with MTPv1.2, with an estimated release date at the end of Q2 2018. Also of note is that a potential alternative, Itsuku, will not be used at this time with Zcoin due to its drawbacks highlighted in the paper.