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

AuthorKostis Karantias, Dionysis Zindros
StatusDraft
TypeStandards Track
CategoryCore
Created2018-08-02

ECIP 1046 - Precompiled contract for Merkle Inclusion Proofs

Abstract

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.

Motivation

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.

Specification

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

Address

The address of MERKLEVERIFY is 0x9.

Gas costs

Gas cost for MERKLEVERIFY is ????.

Implementation

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)
  pure
  public
  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))));
    else
      h = sha256(abi.encodePacked(sha256(abi.encodePacked(h, siblings[i]))));
    leafIndex >>= 1;
  }
  return h == root;
}

References