Where am I wrong in my understanding of Second Preimage Attack in Merkle Tree Implementation of merkle Airdrop

[a1111198]

I have been working on a Solidity Merkle tree proofs for an airdrop contract,by @ciaranightingale using the OpenZeppelin JavaScript library to create the Merkle tree and generate proofs. According to the article "The second preimage attack for Merkle Trees in Solidity" , there's a potential vulnerability where an intermediate node in a Merkle tree can be presented as a leaf, referred to as the second preimage attack.

The article suggests that a better name for this attack would be "node as leaf attack" or "shortened proof attack." To mitigate this attack, it is recommended to avoid using 64-byte leaves prior to hashing or use a different hash function for the leaves.

Current Implementation:

Here is the current implementation for generating the Merkle tree and proofs:

Input File (input.json):

{
  "types": ["address", "uint"],
  "count": 4,
  "values": {
    "0": {
      "0": "0x6CA6d1e2D5347Bfab1d91e883F1915560e09129D",
      "1": "25000000000000000000"
    },
    "1": {
      "0": "0xf39Fd6e51aad88F6F4ce6aB8827279cffFb92266",
      "1": "25000000000000000000"
    },
    "2": {
      "0": "0x2ea3970Ed82D5b30be821FAAD4a731D35964F7dd",
      "1": "25000000000000000000"
    },
    "3": {
      "0": "0xf6dBa02C01AF48Cf926579F77C9f874Ca640D91D",
      "1": "25000000000000000000"
    }
  }
}

Index File to Create Merkle Tree with Proof:

import { StandardMerkleTree } from "@openzeppelin/merkle-tree";
import fs from "fs";

const rawData = fs.readFileSync("input.json", "utf8");
const jsonData = JSON.parse(rawData);
const values = Object.values(jsonData.values).map(entry => Object.values(entry));
const tree = StandardMerkleTree.of(values, jsonData.types);

console.log('Merkle Root:', tree.root);

const output = {
  root: tree.root,
  leaves: values.map((value, index) => ({
    value,
    proof: tree.getProof(index),
    leaf: tree.leafHash(value)
  }))
};

fs.writeFileSync("tree_with_proofs.json", JSON.stringify(output, null, 2));

Output (tree_with_proofs.json):

{
  "root": "0x3e93831d5aec7426870165bd785ff8a3b3bc4bff63cefb371730813c39c83541",
  "leaves": [
    {
      "value": ["0x6CA6d1e2D5347Bfab1d91e883F1915560e09129D", "25000000000000000000"],
      "proof": ["0x4fd31fee0e75780cd67704fbc43caee70fddcaa43631e2e1bc9fb233fada2394", "0xf4216065bf6ac971b2f1ba0fef5920345dcaeceabf5f200030a1cd530dd44a89"],
      "leaf": "0xd1445c931158119b00449ffcac3c947d028c0c359c34a6646d95962b3b55c6ad"
    },
    {
      "value": ["0xf39Fd6e51aad88F6F4ce6aB8827279cffFb92266", "25000000000000000000"],
      "proof": ["0x0c7ef881bb675a5858617babe0eb12b538067e289d35d5b044ee76b79d335191", "0xffddd254facf6b8433316f9280b3106a5c25e936dad206dc897c4385f0896d79"],
      "leaf": "0x0fd7c981d39bece61f7499702bf59b3114a90e66b51ba2c53abdf7b62986c00a"
    },
    {
      "value": ["0x2ea3970Ed82D5b30be821FAAD4a731D35964F7dd", "25000000000000000000"],
      "proof": ["0x0fd7c981d39bece61f7499702bf59b3114a90e66b51ba2c53abdf7b62986c00a", "0xffddd254facf6b8433316f9280b3106a5c25e936dad206dc897c4385f0896d79"],
      "leaf": "0x0c7ef881bb675a5858617babe0eb12b538067e289d35d5b044ee76b79d335191"
    },
    {
      "value": ["0xf6dBa02C01AF48Cf926579F77C9f874Ca640D91D", "25000000000000000000"],
      "proof": ["0xd1445c931158119b00449ffcac3c947d028c0c359c34a6646d95962b3b55c6ad", "0xf4216065bf6ac971b2f1ba0fef5920345dcaeceabf5f200030a1cd530dd44a89"],
      "leaf": "0x4fd31fee0e75780cd67704fbc43caee70fddcaa43631e2e1bc9fb233fada2394"
    }
  ]
}

I modified Solidity code intentionally.

Solidity Code:

  function claim(
        address account,
        uint256 amount,
        bytes32[] calldata merkleProof,
        bytes32 leaf
    ) external {
        if (s_airdropClaimed[account]) {
            revert MerkleAirdrop__AlreadyClaimed();
        }
        // bytes32 leaf = keccak256(
        //     bytes.concat(keccak256(abi.encode(account, amount)))
        // );
        if (!MerkleProof.verify(merkleProof, i_merkleRoot, leaf)) {
            revert MerkleAirdrop__InvalidProof();
        }
        s_airdropClaimed[account] = true;
        emit Claimed(account, amount);
        i_airDropToken.safeTransfer(account, amount);
    } 

Test Case:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.24;
import {Test, console} from "forge-std/Test.sol";
import {MerkleAirdrop} from "../../src/MerkleAirdrop.sol";
import {BagleToken} from "../../src/BagleToken.sol";
import {DeployMerkleAirdrop} from "../../script/DeployMerkleAirdrop.s.sol";
import {ZkSyncChainChecker} from "lib/foundry-devops/src/ZkSyncChainChecker.sol";

contract MerkleAirdropTest is Test, ZkSyncChainChecker {
    bytes32 private constant ROOT =
        0x3e93831d5aec7426870165bd785ff8a3b3bc4bff63cefb371730813c39c83541;
    bytes32 private constant PROOF1 =
        0xf4216065bf6ac971b2f1ba0fef5920345dcaeceabf5f200030a1cd530dd44a89;
    bytes32 private constant PROOF2 =
        0x4fd31fee0e75780cd67704fbc43caee70fddcaa43631e2e1bc9fb233fada2394;
    bytes32 private constant INTERMEDIARY_NODE =
        0xffddd254facf6b8433316f9280b3106a5c25e936dad206dc897c4385f0896d79;
    // bytes32 private constant LEAF =
    //     0xd1445c931158119b00449ffcac3c947d028c0c359c34a6646d95962b3b55c6ad;
    bytes32[] private PROOF = [PROOF2, PROOF1];
    bytes32[] private PROOF_FOR_ATTACK = [PROOF1];
    uint256 private constant AMOUNT_TO_MINT = 100e18;
    uint256 private constant AMOUNT_TO_CLAIM = 25e18;

    BagleToken s_token;
    MerkleAirdrop s_airdrop;
    address user;
    uint256 privateKey;

    function setUp() external {
        // if (!isZkSyncChain()) {
        //     DeployMerkleAirdrop deploy = new DeployMerkleAirdrop();
        //     (s_token, s_airdrop) = deploy.run();
        // } else {
        s_token = new BagleToken();
        s_airdrop = new MerkleAirdrop(ROOT, s_token);
        s_token.mint(address(s_airdrop), AMOUNT_TO_MINT);
        //  }
        (user, privateKey) = makeAddrAndKey("user");
    }

    function testCanClam() external {
        vm.startPrank(user);
        uint256 initialBalance = s_token.balanceOf(user);
        bytes32 leaf = keccak256(
            bytes.concat(keccak256(abi.encode(user, AMOUNT_TO_CLAIM)))
        );

        s_airdrop.claim(user, AMOUNT_TO_CLAIM, PROOF, leaf);
        uint256 endingBalance = s_token.balanceOf(user);
        console.log(endingBalance);

        assert(endingBalance - initialBalance == AMOUNT_TO_CLAIM);
    }

    function testCanClamWithAttack() external {
        vm.startPrank(user);
        uint256 initialBalance = s_token.balanceOf(user);

        s_airdrop.claim(
            user,
            AMOUNT_TO_CLAIM,
            PROOF_FOR_ATTACK,
            INTERMEDIARY_NODE
        );
        uint256 endingBalance = s_token.balanceOf(user);
        console.log(endingBalance);

        assert(endingBalance - initialBalance == AMOUNT_TO_CLAIM);
    }
}

Issue:

Despite following OpenZeppelin's guidelines, the test case testCanClamWithAttack passes, indicating that the contract is still potentially vulnerable to the second preimage attack.

they have Quoted as :

 * WARNING: You should avoid using leaf values that are 64 bytes long prior to
 * hashing, or use a hash function other than keccak256 for hashing leaves.
 * This is because the concatenation of a sorted pair of internal nodes in
 * the Merkle tree could be reinterpreted as a leaf value.
 * OpenZeppelin's JavaScript library generates Merkle trees that are safe
 * against this attack out of the box.

Expected Behavior:

The contract should reject claims that use an intermediate node as a leaf, thus preventing the second preimage attack.

Conclusion:

Conclusion:

I intentionally edited my Solidity code to pass the leaf node and make it vulnerable, but this raises questions about the OpenZeppelin JavaScript library. According to OpenZeppelin, their library should work out of the box and protect against this attack. However, I am not very proficient and am unsure if my understanding is correct. Additionally, the proofs generated using dmfxyz/murky and the OpenZeppelin JavaScript library are different. Why are we using murky in our course, and what should we select? Could you please assist me in clarifying this confusion?

[ciaranightingale]

@a1111198 Firstly, thank you for the in-depth breakdown of your question!

1. dmfxyz/murky was used in the script to generate the roots and the proofs as the repository was designed to be 100% Solidity rather than switching to JavaScript. In the Murky script, the leaves are also double-hashed to prevent second preimage attacks as they are in the OpenZeppelin JS library.
2. The implementation is such that the account and amount are passed and the leaf node generated as opposed to an arbitrary leaf node bytes being able to be passed to prevent this vulnerability where someone could pass an intermediate leaf node and therefore pass the check. As the article you linked states: "If the contract does not accept 64 byte leaves as input, then the attack will not work." Since the claim() function doesn't accept 64 byte leaves as input, it is not vulnerable.

Therefore, this contract is not vulnerable since an intermediate leaf node cannot be passed to claim() nor can someone construct an input of address and uint256 that would hash together to produce the same hash as an intermediate leaf node as this is computationally infeasible.

OpenZeppelin's JavaScript library is protected against this attack when generating proofs but using their Solidity library to verify leaf nodes does not automatically prevent second preimage attacks. However, since this repo does not use the JavaScript library, this is not relevant.

[EngrPips]

Interesting!