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

Author | Kostis Karantias, Dionysis Zindros |
---|---|

Status | Draft |

Type | Standards Track |

Category | Core |

Created | 2018-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**:

**root hash**: the 256-bit merkle tree root hash**leaf**: the 256-bit leaf we want to prove is included in the merkle tree**leaf index**: the 64-bit index of the leaf**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;
}
```