Cross-Chain Deposits

DepositCheck.sol

// SPDX-License-Identifier: MIT
pragma solidity 0.8.38;

import {EtchdVerifier} from "../EtchdVerifier.sol";
import {EvmProofs} from "./EvmProofs.sol";

/// @title A cross-chain deposit check on etchd chain-head records
/// @author Classix
/// @notice A seller offers ETC for the coin of a remote EVM chain at a fixed price. A buyer pays the seller through
///         DepositBox on the remote chain, naming this contract and an ETC recipient. `proveHead` stores a remote
///         block that a quorum of the listed etchd operators recorded as the chain's head, with its state root.
///         `claim` proves the deposit's word in DepositBox's storage under that state root, with eth_getProof's account
///         and storage proofs, and pays the recipient amount * price / 1e18 once the block is `confirmations` past
///         the deposit. Anyone may submit either call, and the ETC always goes to the recipient the deposit named.
/// @dev The design follows Oracle Bridge, a proof of concept Istora Mandiri published in 2020
///      (https://github.com/web3masons/oracle-bridge), where generalised oracles report remote block hashes and a
///      storage proof against one of them shows a deposit, with the chain-head records of etchd as the oracles. Its
///      repository has no licence, so none of its code is used here. The contract trusts the quorum
///      to record only blocks of the remote chain, and the confirmations to keep a deposit from being reorganised
///      away. A deposit claims once, and a claim the vault cannot pay reverts and stays open.
contract DepositCheck {
    struct Terms {
        address[] operators; // the anchor senders of the listed calendars, strictly ascending
        uint256 quorum; // head records needed, 1 to operators.length
        bytes32 chain; // sha256 of the remote chain's CAIP-2 id, such as sha256("eip155:1")
        address box; // DepositBox on the remote chain
        address payee; // the seller's address on the remote chain
        uint256 price; // ETC wei per remote wei, 18 decimals
        uint64 confirmations; // blocks from the deposit's block to the proven head
        uint64 closeAt; // the seller can take back what is left after this time
    }

    struct HeadProof {
        address operator;
        bytes record; // a 104-byte chain-head record with an RLP header hash
        EtchdVerifier.RecordPath path;
    }

    /// A deposit as DepositBox recorded it. Its vault is this contract and its payee the seller's.
    struct Deposit {
        uint256 nonce;
        address recipient;
        uint256 amount; // remote wei
    }

    struct Head {
        uint64 number;
        bytes32 stateRoot;
    }

    uint32 public constant HEAD_BRANCH = 2;
    uint16 public constant HEAD_SCHEMA = 1;
    uint256 public constant HEAD_RECORD_LENGTH = 104;
    uint8 public constant HEADER_RLP = 2;
    /// The slot of DepositBox.depositedAt.
    uint256 public constant DEPOSITS_SLOT = 0;

    EtchdVerifier public immutable verifier;
    address public immutable seller;
    uint256 public immutable quorum;
    bytes32 public immutable chain;
    address public immutable box;
    address public immutable payee;
    uint256 public immutable price;
    uint64 public immutable confirmations;
    uint64 public immutable closeAt;

    address[] public operators;
    mapping(address => bool) public isOperator;
    /// Remote blocks the quorum recorded, by block hash.
    mapping(bytes32 => Head) public heads;
    /// Deposits paid, by id.
    mapping(bytes32 => bool) public claimed;

    event HeadProven(bytes32 indexed blockHash, uint64 number, bytes32 stateRoot);
    event Claimed(bytes32 indexed id, address indexed recipient, uint256 amount, uint256 paid, uint64 depositBlock, uint64 headNumber);
    event Closed(uint256 amount);

    error BadTerms();
    error TooFewProofs(uint256 n);
    error NotOperator(address operator);
    error OperatorsOutOfOrder(uint256 index);
    error BadHead(uint256 index);
    error HeadMismatch(uint256 index);
    error UnknownHead(bytes32 blockHash);
    error AlreadyClaimed(bytes32 id);
    error TooFewConfirmations(uint256 depositBlock, uint256 headNumber);
    error Underfunded(uint256 due, uint256 balance);
    error PayoutRefused();
    error NotSeller();
    error TooEarly();

    constructor(EtchdVerifier verifier_, Terms memory t) payable {
        if (t.quorum == 0 || t.quorum > t.operators.length || t.chain == bytes32(0)) revert BadTerms();
        if (t.box == address(0) || t.payee == address(0) || t.price == 0 || t.closeAt <= block.timestamp) revert BadTerms();
        for (uint256 i; i < t.operators.length; i++) {
            if (i == 0 ? t.operators[i] == address(0) : t.operators[i] <= t.operators[i - 1]) revert BadTerms();
            isOperator[t.operators[i]] = true;
        }
        operators = t.operators;
        verifier = verifier_;
        seller = msg.sender;
        quorum = t.quorum;
        chain = t.chain;
        box = t.box;
        payee = t.payee;
        price = t.price;
        confirmations = t.confirmations;
        closeAt = t.closeAt;
    }

    function operatorCount() external view returns (uint256) {
        return operators.length;
    }

    /// @notice Stores the remote block of `header` once at least `quorum` listed operators recorded it as the chain's
    ///         head. Each proof is a chain-head record (schema 1, this chain, kind head or final, header format rlp,
    ///         32-byte hash) proven with recordExistedAtBy, naming keccak256(header) and the header's own number.
    function proveHead(HeadProof[] calldata proofs, bytes calldata header) external returns (bytes32 blockHash, uint64 number) {
        if (proofs.length < quorum) revert TooFewProofs(proofs.length);
        blockHash = keccak256(header);
        (bytes32 stateRoot, uint256 n) = EvmProofs.headerFields(header);
        number = uint64(n);
        for (uint256 i; i < proofs.length; i++) {
            HeadProof calldata p = proofs[i];
            if (!isOperator[p.operator]) revert NotOperator(p.operator);
            if (i > 0 && p.operator <= proofs[i - 1].operator) revert OperatorsOutOfOrder(i);
            bytes calldata r = p.record;
            // schema, chain, kind 0 head or 1 final, header_format 2 rlp, hash_len 32
            if (
                r.length != HEAD_RECORD_LENGTH || uint16(bytes2(r[5:7])) != HEAD_SCHEMA || bytes32(r[11:43]) != chain || uint8(r[43]) > 1
                    || uint8(r[70]) != HEADER_RLP || r[71] != 0x20
            ) revert BadHead(i);
            if (bytes32(r[72:104]) != blockHash || uint64(bytes8(r[44:52])) != number) revert HeadMismatch(i);
            verifier.recordExistedAtBy(p.operator, HEAD_BRANCH, r, p.path);
        }
        if (heads[blockHash].stateRoot != bytes32(0)) return (blockHash, number);
        heads[blockHash] = Head(number, stateRoot);
        emit HeadProven(blockHash, number, stateRoot);
    }

    /// @notice Pays deposit `d` to its recipient. The account proof leads from the state root of the proven block
    ///         `blockHash` to DepositBox's account, and the storage proof from its storage root to the word of the
    ///         deposit's id, which holds the deposit's block number.
    function claim(bytes32 blockHash, Deposit calldata d, bytes[] calldata accountProof, bytes[] calldata storageProof)
        external
        returns (uint256 paid)
    {
        Head memory h = heads[blockHash];
        if (h.stateRoot == bytes32(0)) revert UnknownHead(blockHash);
        bytes32 id = keccak256(abi.encode(d.nonce, address(this), payee, d.recipient, d.amount));
        if (claimed[id]) revert AlreadyClaimed(id);
        bytes32 storageRoot = EvmProofs.storageRootOf(EvmProofs.get(h.stateRoot, keccak256(abi.encodePacked(box)), accountProof));
        bytes32 slot = keccak256(abi.encode(id, DEPOSITS_SLOT));
        uint256 depositBlock = EvmProofs.storageWord(EvmProofs.get(storageRoot, keccak256(abi.encode(slot)), storageProof));
        if (depositBlock + confirmations > h.number) revert TooFewConfirmations(depositBlock, h.number);
        paid = d.amount * price / 1e18;
        if (paid == 0 || paid > address(this).balance) revert Underfunded(paid, address(this).balance);
        claimed[id] = true;
        emit Claimed(id, d.recipient, d.amount, paid, uint64(depositBlock), h.number);
        (bool ok,) = d.recipient.call{value: paid}("");
        if (!ok) revert PayoutRefused();
    }

    /// @notice Adds ETC to the vault, from anyone.
    function fund() external payable {}

    /// @notice After closeAt, returns what is left to the seller. Deposits not yet claimed are not paid after that.
    function close() external returns (uint256 amount) {
        if (msg.sender != seller) revert NotSeller();
        if (block.timestamp < closeAt) revert TooEarly();
        amount = address(this).balance;
        emit Closed(amount);
        (bool ok,) = seller.call{value: amount}("");
        if (!ok) revert PayoutRefused();
    }
}

DepositBox.sol

// SPDX-License-Identifier: MIT
pragma solidity 0.8.38;

/// @title The remote side of DepositCheck
/// @author Classix
/// @notice Lives on the remote EVM chain. A deposit names the DepositCheck on ETC it is for, the seller's address on
///         this chain and the ETC address to be paid, forwards the coin to the seller at once and writes the block
///         number under the deposit's id. DepositCheck reads that word with a storage proof. The box holds nothing.
/// @dev `depositedAt` is the first state variable, so it sits at slot 0 and the word of deposit `id` at
///      keccak256(abi.encode(id, 0)). An id is never written twice, since the nonce only grows.
contract DepositBox {
    /// The block number of each deposit, by id.
    mapping(bytes32 => uint256) public depositedAt;
    /// Deposits so far, and the nonce of the next.
    uint256 public count;

    event Deposited(bytes32 indexed id, uint256 nonce, address indexed vault, address payee, address recipient, uint256 amount);

    error BadDeposit();
    error PayeeRefused();

    /// @notice Pays msg.value to `payee` and records the deposit for `vault`, a DepositCheck on ETC.
    function deposit(address vault, address payee, address recipient) external payable returns (bytes32 id, uint256 nonce) {
        if (msg.value == 0 || vault == address(0) || payee == address(0) || recipient == address(0)) revert BadDeposit();
        nonce = count++;
        id = idOf(nonce, vault, payee, recipient, msg.value);
        depositedAt[id] = block.number;
        emit Deposited(id, nonce, vault, payee, recipient, msg.value);
        (bool ok,) = payee.call{value: msg.value}("");
        if (!ok) revert PayeeRefused();
    }

    function idOf(uint256 nonce, address vault, address payee, address recipient, uint256 amount) public pure returns (bytes32) {
        return keccak256(abi.encode(nonce, vault, payee, recipient, amount));
    }
}

EvmProofs.sol

// SPDX-License-Identifier: MIT
pragma solidity 0.8.38;

/// @title EVM headers and state proofs
/// @author Classix
/// @notice Reads an EVM block header and walks a Merkle Patricia trie proof as eth_getProof returns it, root node
///         first. Every input is fixed by a hash before it is read, the header by the block hash and each trie node by
///         the reference in its parent, so the decoder only needs to be safe on any bytes and right on canonical RLP.
/// @dev An internal library, compiled into the contracts that use it. It reads calldata in place, and every item is
///      checked to lie inside its parent before its bytes are read, so no length taken from the input reaches outside
///      it. A node shorter than 32 bytes sits inline in its parent instead of being referenced by hash. Keys of the
///      state and storage tries are keccak256 hashes, so two keys sharing the 60 or so leading nibbles that would make a
///      node that short do not occur, and an inline reference is refused.
library EvmProofs {
    /// A trie path has 64 nibbles, so at most 64 branch nodes and a leaf.
    uint256 internal constant MAX_NODES = 65;
    /// keccak256 of the RLP of an empty string, the root of a trie with no keys, such as an account's storage before
    /// its first write.
    bytes32 internal constant EMPTY_ROOT = 0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421;

    /// The bytes are not the RLP the reader expected.
    error BadRlp();
    /// Node `index` of a proof does not hash to its parent's reference, is not a trie node, or the proof ends early.
    error BadProof(uint256 index);
    /// The proof shows the key absent from the trie.
    error NotInTrie();

    /// The item of `b` that starts at byte `off`: whether it is a list, where its payload starts and its length.
    /// Reverts unless the whole item lies inside b. A byte under 0x80 is its own payload.
    function itemAt(bytes calldata b, uint256 off) internal pure returns (bool list, uint256 start, uint256 len) {
        uint256 total = b.length;
        if (off >= total) revert BadRlp();
        uint256 p;
        assembly ("memory-safe") {
            p := byte(0, calldataload(add(b.offset, off)))
        }
        if (p < 0x80) return (false, off, 1);
        if (p < 0xb8) {
            (start, len) = (off + 1, p - 0x80);
        } else if (p < 0xc0) {
            (start, len) = longForm(b, off, p - 0xb7);
        } else if (p < 0xf8) {
            (list, start, len) = (true, off + 1, p - 0xc0);
        } else {
            list = true;
            (start, len) = longForm(b, off, p - 0xf7);
        }
        if (start > total || len > total - start) revert BadRlp();
    }

    /// The payload start and length of a long-form item, whose length takes the `n` bytes after its prefix.
    function longForm(bytes calldata b, uint256 off, uint256 n) private pure returns (uint256 start, uint256 len) {
        if (n > 8 || b.length - off < 1 + n) revert BadRlp();
        start = off + 1 + n;
        assembly ("memory-safe") {
            len := shr(sub(256, mul(8, n)), calldataload(add(add(b.offset, off), 1)))
        }
    }

    /// `len` bytes of `b` from `start`, which itemAt has already bounded, as a slice without a second check.
    function part(bytes calldata b, uint256 start, uint256 len) private pure returns (bytes calldata s) {
        assembly ("memory-safe") {
            s.offset := add(b.offset, start)
            s.length := len
        }
    }

    /// The payload of `b`, which must be exactly one list.
    function listOf(bytes calldata b) internal pure returns (bytes calldata items) {
        (bool list, uint256 start, uint256 len) = itemAt(b, 0);
        if (!list || start + len != b.length) revert BadRlp();
        return part(b, start, len);
    }

    /// Item `i` of a list payload, which must be a string, as its payload.
    function stringAt(bytes calldata items, uint256 i) internal pure returns (bytes calldata) {
        uint256 off;
        for (uint256 k; k < i; k++) {
            (, uint256 s, uint256 l) = itemAt(items, off);
            off = s + l;
        }
        (bool list, uint256 start, uint256 len) = itemAt(items, off);
        if (list) revert BadRlp();
        return part(items, start, len);
    }

    /// A big-endian unsigned integer of at most 32 bytes.
    function toUint(bytes calldata s) internal pure returns (uint256 v) {
        if (s.length > 32) revert BadRlp();
        for (uint256 i; i < s.length; i++) v = (v << 8) | uint8(s[i]);
    }

    /// The state root (field 3) and the number (field 8) of an RLP block header.
    function headerFields(bytes calldata header) internal pure returns (bytes32 stateRoot, uint256 number) {
        bytes calldata items = listOf(header);
        bytes calldata root = stringAt(items, 3);
        if (root.length != 32) revert BadRlp();
        stateRoot = bytes32(root);
        bytes calldata n = stringAt(items, 8);
        if (n.length > 8) revert BadRlp();
        number = toUint(n);
    }

    /// The storage root of an account, the third field of the account RLP [nonce, balance, storageRoot, codeHash].
    function storageRootOf(bytes calldata account) internal pure returns (bytes32) {
        bytes calldata r = stringAt(listOf(account), 2);
        if (r.length != 32) revert BadRlp();
        return bytes32(r);
    }

    /// A storage value as the trie holds it, the RLP string of the word without leading zeros.
    function storageWord(bytes calldata value) internal pure returns (uint256) {
        (bool list, uint256 start, uint256 len) = itemAt(value, 0);
        if (list || start + len != value.length) revert BadRlp();
        return toUint(part(value, start, len));
    }

    /// @notice The value under `key` in the trie of `root`, from the proof nodes of that key, root first. Reverts
    ///         unless the proof ends in a leaf holding the whole key with a value.
    /// @param key the trie key, keccak256 of the address for an account and of the slot for a storage word
    function get(bytes32 root, bytes32 key, bytes[] calldata proof) internal pure returns (bytes calldata value) {
        if (root == EMPTY_ROOT) revert NotInTrie();
        if (proof.length == 0 || proof.length > MAX_NODES) revert BadProof(0);
        bytes32 want = root;
        uint256 d; // nibbles of the key consumed
        uint256 last = proof.length - 1;
        for (uint256 i; i < last; i++) (want, d) = inner(proof[i], want, key, d, i);
        return leaf(proof[last], want, key, d, last);
    }

    /// The list payload of node `i`, once it hashes to `want`. Only the root may be shorter than 32 bytes.
    function open(bytes calldata node, bytes32 want, uint256 i) private pure returns (bytes calldata items) {
        if (keccak256(node) != want || (i > 0 && node.length < 32)) revert BadProof(i);
        return listOf(node);
    }

    /// A node above the leaf: a branch, which takes one nibble, or an extension, which takes its path. Returns the hash
    /// of the next node and the nibbles consumed after this one.
    function inner(bytes calldata node, bytes32 want, bytes32 key, uint256 d, uint256 i) private pure returns (bytes32, uint256) {
        bytes calldata items = open(node, want, i);
        // A branch has 17 items, one child per nibble and a value slot that no key of 64 nibbles reaches.
        (uint256 n, bool list, uint256 start, uint256 len) = scan(items, d < 64 ? nibble(key, d) : 16);
        if (n == 17) {
            if (d == 64) revert BadProof(i);
            return (childRef(items, list, start, len, i), d + 1);
        }
        if (n != 2) revert BadProof(i);
        bool isLeaf;
        (isLeaf, d) = follow(stringAt(items, 0), key, d, i);
        if (isLeaf) revert BadProof(i);
        (, list, start, len) = scan(items, 1);
        return (childRef(items, list, start, len, i), d);
    }

    /// The last node, a leaf that ends the key and holds a value. A branch with an empty slot for the next nibble, or
    /// a path that parts from the key, proves the key absent.
    function leaf(bytes calldata node, bytes32 want, bytes32 key, uint256 d, uint256 i) private pure returns (bytes calldata value) {
        bytes calldata items = open(node, want, i);
        (uint256 n, bool list, uint256 start, uint256 len) = scan(items, d < 64 ? nibble(key, d) : 16);
        if (n == 17) {
            if (d < 64) childRef(items, list, start, len, i);
            revert BadProof(i);
        }
        if (n != 2) revert BadProof(i);
        (bool isLeaf, uint256 end) = follow(stringAt(items, 0), key, d, i);
        if (!isLeaf || end != 64) revert BadProof(i);
        value = stringAt(items, 1);
        if (value.length == 0) revert BadProof(i);
    }

    /// Walks the items of a node once. Returns how many there are and item `pick` (whether it is a list, where its
    /// payload starts, its length). Short items, all a trie node holds but a long value, are read in place.
    function scan(bytes calldata items, uint256 pick) private pure returns (uint256 n, bool list, uint256 start, uint256 len) {
        uint256 off;
        unchecked {
            while (off < items.length) {
                uint256 p;
                assembly ("memory-safe") {
                    p := byte(0, calldataload(add(items.offset, off)))
                }
                (bool l, uint256 s, uint256 ln) = p < 0x80
                    ? (false, off, uint256(1))
                    : p < 0xb8 ? (false, off + 1, p - 0x80) : p >= 0xc0 && p < 0xf8 ? (true, off + 1, p - 0xc0) : itemAt(items, off);
                if (n == pick) (list, start, len) = (l, s, ln);
                off = s + ln;
                n++;
            }
        }
        // An item that runs past the end leaves off beyond it, so every item, the picked one too, lies inside.
        if (off != items.length) revert BadRlp();
    }

    /// Matches the hex-prefix `path` of an extension or leaf against the key from nibble `d`, and returns whether the
    /// node is a leaf and the nibbles consumed after it.
    function follow(bytes calldata path, bytes32 key, uint256 d, uint256 i) private pure returns (bool isLeaf, uint256) {
        if (path.length == 0 || path.length > 33) revert BadProof(i);
        uint256 flag = uint8(path[0]) >> 4;
        if (flag > 3) revert BadProof(i);
        // The path's nibbles left-aligned in one word. An odd path starts in the low half of the flag byte, an even one
        // in the byte after it. A conversion to bytes32 pads a shorter slice with zeros.
        (bytes32 nibs, uint256 m) = flag & 1 == 1 ? (bytes32(path) << 4, path.length * 2 - 1) : (bytes32(path[1:]), path.length * 2 - 2);
        if (d + m > 64) revert NotInTrie();
        // The top m nibbles of the path against the key's nibbles from d. A shift by 256 bits gives zero.
        bytes32 mask = ~bytes32(type(uint256).max >> (4 * m));
        if ((nibs ^ (key << (4 * d))) & mask != 0) revert NotInTrie();
        return (flag >= 2, d + m);
    }

    /// A child reference, item (list, start, len) of `items`: empty when the key is absent, else the 32-byte hash of
    /// the next node. A list is a node inlined in its parent, which this library refuses.
    function childRef(bytes calldata items, bool list, uint256 start, uint256 len, uint256 i) private pure returns (bytes32 ref) {
        if (!list && len == 0) revert NotInTrie();
        if (list || len != 32) revert BadProof(i);
        assembly ("memory-safe") {
            ref := calldataload(add(items.offset, start))
        }
    }

    function nibble(bytes32 key, uint256 d) private pure returns (uint256) {
        uint256 b = uint8(key[d / 2]);
        return d % 2 == 0 ? b >> 4 : b & 0x0f;
    }
}