[BUG] MerkleTreeLib

[ungaro]

MerkleTreeLib – Bug Report & Repro Cases

Context

• Solidity: pragma solidity 0.8.28
• Library: MerkleTreeLib (as provided)
• Summary: Several correctness bugs (two out-of-bounds reads), edge-case handling gaps (empty input, duplicate leaves), and one structural inefficiency.

---

1) Out-of-bounds read when building a layer with an odd number of leaves

Severity: High (hard revert)
Location: _buildTrees, sibling selection
Root cause: The code assumes i + 1 exists for every i += 2 pair. When layer_length is odd, the last iteration uses i = layer_length - 1, so i + 1 is out of range.

Repro (3 unique leaves):

bytes32;
L[0] = keccak256("A"); L[1] = keccak256("B"); L[2] = keccak256("C");
MerkleTreeLib.generateMerkleTree(L); // reverts: read at [i+1] out of bounds

Expected: For odd layers, the last element should be paired with itself (duplicate last).
Actual: Revert due to out-of-bounds access.

Suggested fix (one line logic change):

bytes32 right = (i + 1 < layer_length) ? merkleTreeIn[last][i + 1] : merkleTreeIn[last][i];

---

2) Out-of-bounds read in _generateProof for odd-length layers when the target leaf is last

Severity: High (hard revert)
Location: _generateProof, sibling selection
Root cause: The code does proof[i] = j % 2 == 0 ? tree[i][j + 1] : tree[i][j - 1]. If j is the last index on an odd-length layer and j is even, j + 1 is out of range.

Repro (assuming a correctly built tree, e.g., from a fixed builder):

// tree has layer 0 of length 3. Ask proof for the leaf at index 2 (last).
// Inner loop finds j == 2 (even) and reads tree[i][3] -> out of bounds -> revert.

Expected: When there is no right sibling, use the node itself as the sibling (duplicate last).
Actual: Revert due to out-of-bounds access.

Suggested fix (guard j + 1):

bytes32 sibling = (j & 1) == 0
    ? (j + 1 < layerLen ? tree[i][j + 1] : tree[i][j])  // duplicate when missing right sibling
    : tree[i][j - 1];

---

3) Empty input produces a malformed tree; proof code can silently continue without reverting

Severity: Medium–High (invalid structure; potential silent misuse)
Locations:

• generateMerkleTree (accepts 0 leaves and returns a “tree” whose last layer has length 0)
• _generateProof (the “not found” revert relies on j == tree[i].length - 1 inside the inner loop; when tree[i].length == 0, the loop body never runs and the revert is never hit)

Repro:

bytes32;
bytes32[][] memory tree = MerkleTreeLib.generateMerkleTree(L);
// tree.length == 2, but tree[0].length == 0 and tree[1].length == 0
// Accessing root via tree[tree.length - 1][0] will revert (empty last layer).

If a caller passes such a layer to _generateProof, the inner loop is skipped and the function can return a default-initialized proof without reverting.

Expected: Either reject empty input up front, or define a consistent root/proof convention.
Actual: Malformed tree with empty last layer; “leaf not found” may not trigger in _generateProof.

Suggested fixes:

• Validation:

  require(inputLeafs.length > 0, "No leaves");

• Proof search robustness: After the inner for j loop, check a found flag and revert("Leaf not found in tree") if not found (avoids zero-length underflow edge case).

---

4) Ambiguous proofs when leaves contain duplicate values (value-based search)

Severity: Medium (semantic bug / API limitation)
Location: getProofsUsingTree → _generateProof
Root cause: _generateProof locates leaves by value, not by position. When the same leaf value occurs multiple times, only the first match in each layer is used to compute the path. This makes it impossible to generate a proof for a specific index.

Repro (duplicate value):

bytes32 x = keccak256("X");
bytes32 y = keccak256("Y");
bytes32;
L[0] = x; L[1] = y; L[2] = x;

bytes32[][] memory tree = /* correct tree for [x,y,x] */;
bytes32[][] memory proofs = MerkleTreeLib.getProofsUsingTree(L, tree);

// proofs[2] is effectively the proof for the *first* occurrence of x, not the third element (index 2).

Expected: Ability to generate proofs for a specific occurrence (index) even when values repeat.
Actual: Proofs for duplicates always correspond to the first matching value in a layer.

Suggested fix: Provide an index-based API, e.g. proofAtIndex(uint256 index, bytes32[][] memory tree), which uses index ^ 1 to select the sibling each layer and index >>= 1 to ascend. This is deterministic and supports duplicates.

---

5) Inefficient tree construction due to recursive full-copy per level

Severity: Low (performance / memory)
Location: _buildTrees (recursive; copies all previous layers into a new 2D array at every recursion depth)

Impact: For a tree of height h, building the tree repeatedly allocates and copies O(h) layers at each step → superlinear memory traffic. With large trees, this inflates gas and memory usage.

Expected: Iterative construction with a single pre-allocated 2D array (or dynamic vector of layers) and in-place assignment of each subsequent layer.
Suggested change: Replace recursion with an iterative loop that computes (prevLen + 1) >> 1 until the root, filling tree[level + 1] directly without re-copying prior layers.

---

6) Fragile “not found” detection in _generateProof

Severity: Low–Medium (correctness in malformed or adversarial inputs)
Location: _generateProof, end-of-layer check
Root cause: The code only reverts when j == tree[i].length - 1 inside the loop. If the loop never runs (e.g., empty layer), there’s no revert and the function proceeds with default zeros.

Repro: Use a tree where some intermediate layer is empty (e.g., from the empty-input case above) and request a proof → function returns a zero-initialized proof without reverting.

Expected: If a leaf is not found in a layer, revert unconditionally after scanning the layer.
Suggested fix: Use a bool found flag per layer; revert if !found after the inner loop.

---

7) Interoperability caveat: canonical (sorted-pair) hashing

Severity: Informational (compatibility)
Location: _hashPair
Note: The library hashes pairs in sorted order (a < b ? (a,b) : (b,a)), which is different from many left-right ordered Merkle implementations (e.g., keccak(left || right) without sorting). Proofs and roots from this library will not be compatible with ordered-pair trees.

Example difference (2 leaves):

• This library: root = keccak256(min(A,B) || max(A,B))
• Ordered trees: root = keccak256(A || B)

Action: Document clearly or provide a mode flag to choose ordered vs. sorted pairs.

---

Consolidated Fix Recommendations

1. Odd layers: Duplicate the last element when pairing both in _buildTrees and _generateProof.
2. Empty input: require(inputLeafs.length > 0, "No leaves"); and/or define explicit single-leaf behavior.
3. Proof search: Replace the in-loop end check with a post-loop found guard to ensure a revert on “leaf not found,” even for empty layers.
4. Duplicate leaves: Add an index-based proof API (e.g., proofAtIndex(index, tree)) to disambiguate.
5. Performance: Switch to an iterative builder that pre-allocates all layers and avoids recursive re-copying.
6. Docs: Call out the sorted-pair hashing so users understand cross-library incompatibilities.

---

Minimal Patch Sketches (for reference)

Sibling guard (build):

bytes32 right = (i + 1 < layer_length) ? merkleTreeIn[last][i + 1] : merkleTreeIn[last][i];

Sibling guard (proof):

bytes32 sibling = (j & 1) == 0
    ? (j + 1 < layerLen ? tree[i][j + 1] : tree[i][j])
    : tree[i][j - 1];

Empty input reject & robust “not found”:

require(inputLeafs.length > 0, "No leaves");

// In _generateProof:
bool found;
for (uint256 j; j < layerLen; ++j) {
    if (leaf == tree[i][j]) { found = true; /* ... */ break; }
}
require(found, "Leaf not found in tree");

Index-based proof (duplicate-safe):

function proofAtIndex(uint256 index, bytes32[][] memory tree)
    internal pure returns (bytes32[] memory proof)
{
    proof = new bytes32[](tree.length - 1);
    for (uint256 level; level < tree.length - 1; ++level) {
        uint256 layerLen = tree[level].length;
        uint256 sibIndex = index ^ 1;
        proof[level] = sibIndex < layerLen ? tree[level][sibIndex] : tree[level][index];
        index >>= 1;
    }
}

[ungaro]

// SPDX-License-Identifier: MIT
pragma solidity 0.8.28;

import "forge-std/Test.sol";
import {MerkleTreeLib} from "../src/MerkleTreeLib.sol"; // <-- adjust path

/// ------------------------------------------------------------
/// Pre-Patch tests: show the original bugs (expected to REVERT)
/// ------------------------------------------------------------
contract MerkleTreeLibPrePatchTest is Test {
    // 1) _buildTrees: out-of-bounds on odd leaf count
    function test_PrePatch_BuildOdd_Reverts() public {
        bytes32;
        L[0] = keccak256("A");
        L[1] = keccak256("B");
        L[2] = keccak256("C");

        vm.expectRevert(stdError.indexOOBError); // array index out of bounds
        MerkleTreeLib.generateMerkleTree(L);
    }

    // 2) _generateProof: out-of-bounds when target leaf is last in an odd-length layer
    function test_PrePatch_ProofOddLastLeaf_Reverts() public {
        // Craft a minimal "tree" that trips j+1 access on the last (even index) element.
        bytes32 a = keccak256("a");
        bytes32 b = keccak256("b");
        bytes32 c = keccak256("c");

        bytes32;
        // layer 0: length 3 (odd). c is at index 2 (even) -> j+1 out-of-bounds
        tree;
        tree[0][0] = a;
        tree[0][1] = b;
        tree[0][2] = c;

        // layer 1: any non-empty length; not used by the bug itself
        tree;
        tree[1][0] = bytes32(uint256(1));
        tree[1][1] = bytes32(uint256(2));

        bytes32;
        wantProofFor[0] = c;

        vm.expectRevert(stdError.indexOOBError); // sibling at j+1 read overflows
        MerkleTreeLib.getProofsUsingTree(wantProofFor, tree);
    }

    // 3) Empty input builds a malformed tree (last layer length == 0)
    function test_PrePatch_EmptyInput_MalformedTree_NoRoot() public {
        bytes32;
        bytes32[][] memory tree = MerkleTreeLib.generateMerkleTree(L);

        assertEq(tree.length, 2);        // often 2 layers are returned
        assertEq(tree[0].length, 0);     // but both layers are empty
        assertEq(tree[1].length, 0);

        // Accessing the root should revert due to out-of-bounds
        vm.expectRevert(stdError.indexOOBError);
        bytes32 _root = tree[tree.length - 1][0];
        _root; // silence unused var
    }
}

/// ------------------------------------------------------------
/// Post-Patch tests: validate behavior after fixes
/// Assumptions:
/// - Builder duplicates last node on odd layers
/// - _generateProof guards j+1 with duplication when missing right sibling
/// - (Optional) generateMerkleTree requires at least 1 leaf
/// ------------------------------------------------------------
contract MerkleTreeLibPatchedTest is Test {
    // Local helper: sorted-pair hashing (must match library semantics)
    function _hashPair(bytes32 a, bytes32 b) internal pure returns (bytes32) {
        return a < b ? keccak256(abi.encodePacked(a, b))
                     : keccak256(abi.encodePacked(b, a));
    }

    function _processProof(bytes32 leaf, bytes32[] memory proof) internal pure returns (bytes32 h) {
        h = leaf;
        for (uint256 i; i < proof.length; ++i) {
            h = _hashPair(h, proof[i]);
        }
    }

    function _leaves(uint256 n) internal pure returns (bytes32[] memory L) {
        L = new bytes32[](n);
        for (uint256 i; i < n; ++i) {
            L[i] = keccak256(abi.encodePacked("leaf-", i));
        }
    }

    // After patch: odd leaf counts should build and all proofs should verify.
    function test_Patched_OddLeafCount_ProofsVerify() public {
        bytes32[] memory L = _leaves(5);
        bytes32[][] memory tree = MerkleTreeLib.generateMerkleTree(L);

        // Root is at last layer, index 0
        bytes32 root = tree[tree.length - 1][0];

        for (uint256 i; i < L.length; ++i) {
            bytes32;
            single[0] = L[i];
            bytes32[][] memory proofs = MerkleTreeLib.getProofsUsingTree(single, tree);

            // one proof per query
            assertEq(proofs.length, 1);
            // proof height should be tree height - 1
            assertEq(proofs[0].length, tree.length - 1);

            bytes32 computed = _processProof(L[i], proofs[0]);
            assertEq(computed, root);
        }
    }

    // After patch: even leaf counts should also work and verify.
    function test_Patched_EvenLeafCount_ProofsVerify() public {
        bytes32[] memory L = _leaves(8);
        bytes32[][] memory tree = MerkleTreeLib.generateMerkleTree(L);
        bytes32 root = tree[tree.length - 1][0];

        for (uint256 i; i < L.length; ++i) {
            bytes32;
            single[0] = L[i];
            bytes32[][] memory proofs = MerkleTreeLib.getProofsUsingTree(single, tree);
            bytes32 computed = _processProof(L[i], proofs[0]);
            assertEq(computed, root);
        }
    }

    // After patch: single-leaf tree convention — parent layer = hash(leaf, leaf)
    // If you chose the OZ-style convention (root == leaf, empty proof), adjust assertions accordingly.
    function test_Patched_SingleLeaf_ProofVerifies() public {
        bytes32[] memory L = _leaves(1);
        bytes32[][] memory tree = MerkleTreeLib.generateMerkleTree(L);

        // Expect 2 layers: [leaf], [root]
        assertEq(tree.length, 2);
        assertEq(tree[0].length, 1);
        assertEq(tree[1].length, 1);

        bytes32 root = tree[1][0];

        bytes32;
        single[0] = L[0];
        bytes32[][] memory proofs = MerkleTreeLib.getProofsUsingTree(single, tree);

        assertEq(proofs.length, 1);
        assertEq(proofs[0].length, 1); // one sibling = the leaf itself (duplicated)

        bytes32 computed = _processProof(L[0], proofs[0]);
        assertEq(computed, root);
    }

    // Optional: if you added `require(leaves.length > 0)`, this should revert. Comment out if not.
    function test_Patched_EmptyInput_Reverts() public {
        bytes32;
        vm.expectRevert(); // "No leaves" (or your chosen revert)
        MerkleTreeLib.generateMerkleTree(L);
    }
}

Notes

PrePatch: demonstrates the current crashes/malformed behavior (run these against the unmodified lib).

Patched: validates behavior after applying the fixes (run after patching).

The PrePatch suite proves the two out-of-bounds bugs + malformed empty-tree behavior.

The Patched suite verifies correctness for odd/even/single-leaf cases and (optionally) that empty input is rejected.

The tests re-implement the library’s sorted-pair hashing to check proofs without adding new APIs. If you switch to left-right ordered hashing, update _hashPair accordingly.