TOB-FUEL-5: compactProof function gives incorrect result whenever there are more than one non-empty side nodes

[xgreenx]

Description

A missing increment operation leads to the compactProof function giving an incorrect result for any case where there are more than one non-zero side nodes.
The compactProof function is used to compact a full Sparse Merkle Proof into a compact version. In a compact version all of the empty side nodes are not stored, but a bitmask is used to indicate which side nodes are empty. The accompanying decompactProof function can be used to convert the compact version back to the full version, where also empty side nodes are present.
The sideNodesCount variable is used as an index at which to store each non-empty side node. However, there is no increment of the sideNodesCount variable. As a result each non-empty side node will overwrite the previous one, and is stored at index zero in the compactedSideNodes array.

Figure 5.1: The compactProof function in fuel-merkle-sol/contracts/tree/sparse/Proofs.sol

function compactProof(SparseMerkleProof memory proof)
    pure
    returns (SparseCompactMerkleProof memory)
{
    uint256[] memory bitMask = new uint256[](proof.SideNodes.length);
    // Create a large-enough dynamic array for the sidenodes
    bytes32[] memory compactedSideNodes = new bytes32[](256);
    bytes32 node;
    uint256 sideNodesCount = 0;

    /// Compact proof into array of non-zero sidenodes and a bitmask
    for (uint256 i = 0; i < proof.SideNodes.length; i += 1) {
        node = proof.SideNodes[i];
        if (node == Constants.ZERO) {
            bitMask[i] = 0;
        } else {
            compactedSideNodes[sideNodesCount] = node;
            bitMask[i] = 1;
        }
    }

    /// Shrink the array of sidenodes to its final size
    bytes32[] memory finalCompactedSideNodes = shrinkBytes32Array(
        compactedSideNodes,
        sideNodesCount
    );

    return
        SparseCompactMerkleProof(
            finalCompactedSideNodes,
            proof.NonMembershipLeaf,
            bitMask,
            proof.SideNodes.length,
            proof.Sibling
        );
}

The Fuel frontend might make use of the Solidity compactProof function to compact a proof, which would lead to an incorrect result. However, it seems more likely that the Fuel Typescript SDK is used instead, which also contains a compactProof function, and that does function correctly.

Figure 5.2: The compactProof function in fuels-ts/packages/merkle/src/sparse/proofs.ts

export function compactProof(proof: SparseMerkleProof): SparseCompactMerkleProof {
  const bitMask: number[] = [];
  const compactedSideNodes: string[] = [];
  let node;

  for (let i = 0; i < proof.SideNodes.length; i += 1) {
    node = proof.SideNodes[i];
    if (node === ZERO) {
      bitMask.push(0);
    } else {
      compactedSideNodes.push(node);
      bitMask.push(1);
    }
  }
  const compactedProof = new SparseCompactMerkleProof(
    compactedSideNodes,
    proof.NonMembershipLeafData,
    bitMask,
    proof.SideNodes.length,
    proof.SiblingData
  );
  return compactedProof;
}

Exploit Scenario

The Fuel frontend makes use of the Solidity compactProof function to compact a Sparse Merkle Proof. Alice uses the UI to generate a compact proof. Alice then calls a contract operation that requires the proof. The transaction fails since the proof is incorrect.

Recommendations

Short term, increment the sideNodesCount variable inside the else case (figure 5.1, line 91) in the Solidity compactProof function. This will mitigate the bug and correctly store all of the non-empty side nodes in a compact Sparse Merkle Proof.
Long term, implement differential unit tests for the Merkle Tree-related functions across the Solidity and Typescript SDK (and possibly the Rust implementation) that verifies that they all behave identically for a given set of inputs. An improvement upon these tests would be to implement differential fuzzing tests across these three languages to test that they behave identically for all given inputs.