Skip to content

Instantly share code, notes, and snippets.

@parseb
Forked from zengzengzenghuy/Merkle.sol
Created November 17, 2023 15:07
Show Gist options
  • Save parseb/a40b5dfd0d1c64a4155cbaf59f20f73c to your computer and use it in GitHub Desktop.
Save parseb/a40b5dfd0d1c64a4155cbaf59f20f73c to your computer and use it in GitHub Desktop.
Created using remix-ide: Realtime Ethereum Contract Compiler and Runtime. Load this file by pasting this gists URL or ID at https://remix.ethereum.org/#version=soljson-v0.8.22+commit.4fc1097e.js&optimize=false&runs=200&gist=
// taken here: https://github.com/maticnetwork/contracts/blob/main/contracts/common/lib/Merkle.sol
pragma solidity ^0.8.20;
library Merkle {
function checkMembership(
bytes32 leaf,
uint256 index,
bytes32 rootHash,
bytes memory proof
) internal pure returns (bool) {
require(proof.length % 32 == 0, "Invalid proof length");
uint256 proofHeight = proof.length / 32;
// Proof of size n means, height of the tree is n+1.
// In a tree of height n+1, max #leafs possible is 2 ^ n
require(index < 2 ** proofHeight, "Leaf index is too big");
bytes32 proofElement;
bytes32 computedHash = leaf;
for (uint256 i = 32; i <= proof.length; i += 32) {
assembly {
proofElement := mload(add(proof, i))
}
if (index % 2 == 0) {
computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
} else {
computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
}
index = index / 2;
}
return computedHash == rootHash;
}
}
// taken here: https://github.com/maticnetwork/contracts/blob/main/contracts/common/lib/MerklePatriciaProof.sol
/*
* @title MerklePatriciaVerifier
* @author Sam Mayo (sammayo888@gmail.com)
*
* @dev Library for verifing merkle patricia proofs.
*/
pragma solidity ^0.8.20;
import {RLPReader} from "solidity-rlp/contracts/RLPReader.sol";
library MerklePatriciaProof {
/*
* @dev Verifies a merkle patricia proof.
* @param value The terminating value in the trie.
* @param encodedPath The path in the trie leading to value.
* @param rlpParentNodes The rlp encoded stack of nodes.
* @param root The root hash of the trie.
* @return The boolean validity of the proof.
*/
function verify(
bytes memory value,
bytes memory encodedPath,
bytes memory rlpParentNodes,
bytes32 root
) internal pure returns (bool) {
RLPReader.RLPItem memory item = RLPReader.toRlpItem(rlpParentNodes);
RLPReader.RLPItem[] memory parentNodes = RLPReader.toList(item);
bytes memory currentNode;
RLPReader.RLPItem[] memory currentNodeList;
bytes32 nodeKey = root;
uint256 pathPtr = 0;
bytes memory path = _getNibbleArray(encodedPath);
if (path.length == 0) {
return false;
}
for (uint256 i = 0; i < parentNodes.length; i++) {
if (pathPtr > path.length) {
return false;
}
currentNode = RLPReader.toRlpBytes(parentNodes[i]);
if (nodeKey != keccak256(currentNode)) {
return false;
}
currentNodeList = RLPReader.toList(parentNodes[i]);
if (currentNodeList.length == 17) {
if (pathPtr == path.length) {
if (keccak256(RLPReader.toBytes(currentNodeList[16])) == keccak256(value)) {
return true;
} else {
return false;
}
}
uint8 nextPathNibble = uint8(path[pathPtr]);
if (nextPathNibble > 16) {
return false;
}
nodeKey = bytes32(RLPReader.toUintStrict(currentNodeList[nextPathNibble]));
pathPtr += 1;
} else if (currentNodeList.length == 2) {
uint256 traversed = _nibblesToTraverse(RLPReader.toBytes(currentNodeList[0]), path, pathPtr);
if (pathPtr + traversed == path.length) {
//leaf node
if (keccak256(RLPReader.toBytes(currentNodeList[1])) == keccak256(value)) {
return true;
} else {
return false;
}
}
//extension node
if (traversed == 0) {
return false;
}
pathPtr += traversed;
nodeKey = bytes32(RLPReader.toUintStrict(currentNodeList[1]));
} else {
return false;
}
}
}
// bytes b must be hp encoded
function _getNibbleArray(bytes memory b) private pure returns (bytes memory) {
bytes memory nibbles;
if (b.length > 0) {
uint8 offset;
uint8 hpNibble = uint8(_getNthNibbleOfBytes(0, b));
if (hpNibble == 1 || hpNibble == 3) {
nibbles = new bytes(b.length * 2 - 1);
bytes1 oddNibble = _getNthNibbleOfBytes(1, b);
nibbles[0] = oddNibble;
offset = 1;
} else {
nibbles = new bytes(b.length * 2 - 2);
offset = 0;
}
for (uint256 i = offset; i < nibbles.length; i++) {
nibbles[i] = _getNthNibbleOfBytes(i - offset + 2, b);
}
}
return nibbles;
}
function _getNthNibbleOfBytes(uint256 n, bytes memory str) private pure returns (bytes1) {
return bytes1(n % 2 == 0 ? uint8(str[n / 2]) / 0x10 : uint8(str[n / 2]) % 0x10);
}
function _nibblesToTraverse(
bytes memory encodedPartialPath,
bytes memory path,
uint256 pathPtr
) private pure returns (uint256) {
uint256 len;
// encodedPartialPath has elements that are each two hex characters (1 byte), but partialPath
// and slicedPath have elements that are each one hex character (1 nibble)
bytes memory partialPath = _getNibbleArray(encodedPartialPath);
bytes memory slicedPath = new bytes(partialPath.length);
// pathPtr counts nibbles in path
// partialPath.length is a number of nibbles
for (uint256 i = pathPtr; i < pathPtr + partialPath.length; i++) {
bytes1 pathNibble = path[i];
slicedPath[i - pathPtr] = pathNibble;
}
if (keccak256(partialPath) == keccak256(slicedPath)) {
len = partialPath.length;
} else {
len = 0;
}
return len;
}
}
// SPDX-License-Identifier: GPL-3.0
pragma solidity ^0.8.0;
import "solidity-rlp/contracts/RLPReader.sol";
import "./Hashi.sol";
import {Merkle} from "./libraries/Merkle.sol";
import {MerklePatriciaProof} from "./libraries/MerklePatriciaProof.sol";
struct EventProof {
bytes receiptsRootProofPath; // proof path
bytes receiptsRootProofParentNodes; // proof parent nodes
bytes receipt; // receipt of the transaction to prove
uint256 logIndex; // log index of the event from receipt
bytes blockHeader; // rlp-encoded block header
}
error InvalidEventEmitter(address proofEmitter, address actualEmitter);
error InvalidTopic(bytes32 topic, bytes32 expectedTopic);
error InvalidBlockHash(bytes32 blockHash, bytes32 expectedBlockHash);
error InvalidReceiptsRootMerkleProof();
error InvalidBlockHeaderLength(uint256 length);
contract VerifyEvent {
Hashi public hashi;
address public expectedPingPong;
IOracleAdapter public ambAdapter;
bytes32 public constant EVENT_SIGNATURE_TOPIC= 0x48257dc961b6f792c2b78a080dacfed693b660960a702de21cee364e20270e2f; //keccak256(ping(uint256))
constructor(address hashi_, address pingpong_, address ambAdapter_){
hashi = Hashi(hashi_);
expectedPingPong = pingpong_;
ambAdapter = IOracleAdapter(ambAdapter_);
}
/// @dev verify certain event of given block number and receipt
/// @param proof The EventProof struct to prove for
function verify(EventProof memory proof) external {
// deserialze block header data
RLPReader.RLPItem memory blockHeaderRLP = RLPReader.toRlpItem(proof.blockHeader);
RLPReader.RLPItem[] memory blockHeaderContent = RLPReader.toList(blockHeaderRLP);
uint256 blockNumber = uint256(RLPReader.toUint(blockHeaderContent[8]));
bytes32 receiptRoot = bytes32(RLPReader.toUint(blockHeaderContent[6]));
// Get log from receipt
RLPReader.RLPItem memory receiptRlpItem = RLPReader.toRlpItem(proof.receipt);
RLPReader.RLPItem[] memory receiptData = RLPReader.toList(receiptRlpItem);
RLPReader.RLPItem[] memory logs = RLPReader.toList(receiptData[3]); // index of 'logs[]' in receipt
RLPReader.RLPItem[] memory log = RLPReader.toList(logs[proof.logIndex]); // index in 'logs[]' of the event to prove
// Check block hash
bytes32 reportedBlockHash = keccak256(proof.blockHeader);
// check the block header with Hashi
IOracleAdapter[] memory oracleAdapters = new IOracleAdapter[](1);
oracleAdapters[0] = ambAdapter;
uint256 sourceChainId = 5;
bytes32[] memory expectedBlockHash = hashi.getHashesFromOracles(oracleAdapters, sourceChainId, blockNumber);
if(expectedBlockHash[0]!=reportedBlockHash){
revert InvalidBlockHash(reportedBlockHash, expectedBlockHash[0]);
}
// Check emitted address
address pingpong = RLPReader.toAddress(log[0]); // index of 'address' in log
if(pingpong != expectedPingPong){
revert InvalidEventEmitter(pingpong, expectedPingPong);
}
// Check event topic
RLPReader.RLPItem[] memory topics = RLPReader.toList(log[7]); // index of 'topics' in log
bytes32 pingPongTopic = bytes32(RLPReader.toBytes(topics[0])); // first index of 'topics'
if(EVENT_SIGNATURE_TOPIC != pingPongTopic){
revert InvalidTopic(pingPongTopic, EVENT_SIGNATURE_TOPIC);
}
// Verify receipt trie
if (
!MerklePatriciaProof.verify(
proof.receipt,
proof.receiptsRootProofPath,
proof.receiptsRootProofParentNodes,
receiptRoot
)
)
{
revert InvalidReceiptsRootMerkleProof();
}
// Define your dApp logic here...
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment