MTP Audit and Implementation Bounty Submissions

This Wiki is to publish the submissions to the MTP Audit and Implementation Bounty.

Further details on this bounty can be found on our blog post

Submissions under Verification/Classification

Submission 1 by mbevand with fix (Under verification and classification)

MTP as described in its paper https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_biryukov.pdf is flawed. Algorithm 2 (verifier's algorithm), step 2, verifies the opening but not the location of the Argon2 blocks in the tree. Their location is not part of the proof. Their location can only be computed at the next step, step 3, when Y_j is calculated. As a result, the prover can pretend the blocks selected through each of the L=70 steps are always X[3] (MTP does not allow to select X[1] or X[2]) and he can effectively run algorithm 1 (prover's algorithm) by storing only 3 kB. I'll explain later how to further reduce memory usage down to 1 kB.

More specifically an attack against MTP would work as follow: in the prover's algorithm, step 1, the prover computes and stores X[1] through X[3] in memory, and stops here. The prover assumes the rest of the blocks X[4] through X[T] are all zeros. In step 5, the prover doesn't bother computing i_j but assumes i_j is always 3. The rest of the algorithm is run normally. Whenever a nonce N results in a satisfying Y_L, the prover's proof will be the merkle root, the nonce N, and the set Z of L=70 elements where each element is the same:

(opening of X[3], opening of its two input blocks X[2] and X[1], input block X[2], and input block X[1])

On a side note, the Zcoin implementation of MTP would also store X[3] in the proof, but this is unnecessary.

The verifier's algorithm blindly accepts this proof because all the openings are valid and the algorithm doesn't verify whether the location (Y_j mod T) equals 3 or not. Since the location isn't verified or even known by the verifier's algorithm, it seems the paper implies a "canonical" merkle tree is computed: a tree where the hash of the "left" and "right" hashes are computed by first ordering the 2 hashes.

On a side note, the Zcoin implementation of MTP gets around the problem of not knowing the location not by computing a "canonical" merkle tree, but by storing both the left and right hashes in the proof. But it too fails to verify the location, so it doesn't prevent the attack.

In order to fix the verifier's algorithm, step 2 should be removed, and step 3 should be changed to:

Compute from Z for 1 ≤ j ≤ L: X[i_j] = F(X[i_j - 1], X[φ(i_j)]) Verify opening of X[i_j] and its location in tree: (Y_(j-1) mod T) Verify opening of X[i_j - 1] and its location in tree: (Y_(j-1) mod T) - 1 Verify opening of X[φ(i_j)] and its location in tree (*) Y_j = G(Y_j - 1, X[i_j])

(*) The location of X[φ(i_j)] is specified by the first two 32-bit words of X[i_j - 1] as documented in the Argon2 specification (J_1 and J_2 words.)

Since an opening consists of 21 hashes and no additional information, some of these hashes will be "left" hashes, others "right" hashes. So verifying both the opening and location of a block is done by hashing the hash in the proof and the hash computed on the fly while verifying the opening in the order determined by the block's location in the tree.

In the Zcoin implementation, it stores 21*3 hashes per opening (parent, left, right) so verifying the location of the block would consist of verifying the hash is at the expected place (either left or right) instead of freely allowing it to be at either the left or right: https://github.com/zcoinofficial/zcoin/blob/dfb9a0b57ebcc706ae0278b5698792a02d1b66f6/src/libmerkletree/merkletree.cpp#L79

The memory usage of this attack against MTP can be reduced from 3 kB to 1 kB. Because the verifier's algorithm allows any value for X[1] and X[2], the prover can actually assume they are all zeros and not even store them in memory.

MTP Audit Bounty (10,000 USD)

For verified MTP Audit Bounty submissions

MTP Implementation Bounty (2,500 USD)

Submission 1 by mbevand with fix (Accepted)

https://github.com/zcoinofficial/zcoin/blob/dfb9a0b57ebcc706ae0278b5698792a02d1b66f6/src/mtp.cpp#L609 "i < L * 2" should be replaced with "i < L * 3" or else the verifier will only verify the opening of 2/3rds of the blocks in the merkle tree. Failing to verify the remaining 1/3rd means a malicious prover would have to spend the expected computing resources (2GB) only once to compute 1 potential PoW solution. Then he would simply "grind" one block in the remaining 1/3rd by spending minimal resources, completely defeating the memory-hardness of MTP. For example he would calculate Y_j = H(Y_(j−1), X[i_j]) for L-1 blocks, then would grind the last block, potentially on many machines in parallel, by sending the Y_(L-1) value to the machines, each grinding unique random last blocks, and each needing to allocate only 1kB to hold this block.