ECIP 1046: Precompiled contract for verification of Merkle Inclusion Proofs Source

AuthorKostis Karantias, Dionysis Zindros
TypeStandards Track

ECIP 1046 - Precompiled contract for Merkle Inclusion Proofs


Verification of Merkle Inclusion Proofs is obviously possible in EVM bytecode. However, the gas cost for such an operation is very high.

We propose adding this functionality to Ethereum Classic as a precompiled contract in order to combat this cost.


Interoperability is a very important goal for Ethereum Classic. We believe that having a way to efficiently tell whether a transaction is included in a Bitcoin/Bitcoin Cash block by utilizing only the block’s Merkle Tree Root and a short proof is a great first step in that direction.

Moreover, new efficient constructions which enable cross-chain asset transfers like NIPoPoWs heavily rely on Merkle Inclusion Proofs.


If block.number >= MERKLE_FORK_BLKNUM, add a precompiled contract for Merkle Inclusion Proofs (MERKLEVERIFY).

The proposal adds a new precompiled function MERKLEVERIFY with the following input and output.

MERKLEVERIFY takes as input at least 72 bytes:

  1. root hash: the 256-bit merkle tree root hash
  2. leaf: the 256-bit leaf we want to prove is included in the merkle tree
  3. leaf index: the 64-bit index of the leaf
  4. siblings: an array of 256-bit values, arranged from the leaves to the root

MERKLEVERIFY returns as output 4 bytes:

  • 0x00000000 if the proof is valid
  • any non-zero value indicates an invalid proof


The address of MERKLEVERIFY is 0x9.

Gas costs

Gas cost for MERKLEVERIFY is ????.


The hash function used is SHA256(SHA256(_)), to be compatible with Bitcoin/Bitcoin Cash.

The merkle tree construction assumed is described in detail in the Bitcoin Developer Reference.

Here follows an example implementation of the verification in Solidity:

function merkleVerify(bytes32 root, bytes32 leaf, bytes8 leafIndex, bytes32[] siblings)
  returns (bool verificationSucceeded)
  bytes32 h = leaf;
  for (uint i = 0; i < siblings.length; ++i) {
    bool siblingOnTheLeft = leafIndex & 0x1 == 1;
    if (siblingOnTheLeft)
      h = sha256(abi.encodePacked(sha256(abi.encodePacked(siblings[i], h))));
      h = sha256(abi.encodePacked(sha256(abi.encodePacked(h, siblings[i]))));
    leafIndex >>= 1;
  return h == root;