Last active
November 17, 2023 16:38
-
-
Save zengzengzenghuy/ca935b869f9744e7451a7cc1d78a87f7 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=
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// taken here: https://github.com/maticnetwork/contracts/blob/main/contracts/common/lib/MerklePatriciaProof.sol | |
/* | |
* @title MerklePatriciaVerifier | |
* @author Sam Mayo ([email protected]) | |
* | |
* @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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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