aere-contracts/test/interop/trie.js

// -----------------------------------------------------------------------------
// Minimal, correct Ethereum hexary Merkle-Patricia trie BUILDER + proof generator,
// plus EIP-2718 receipt encoding, for the message-inbox tests.
//
// This is an INDEPENDENT implementation from the Solidity MerklePatriciaProof
// verifier: the builder here constructs the trie and the on-chain verifier walks it.
// A passing test means the two agree, which is a real cross-check on both.
//
// Receipt values are always > 32 bytes (a receipt carries a 256-byte logsBloom), so
// every trie node is > 32 bytes and referenced by hash — no inline-node case arises.
// -----------------------------------------------------------------------------
const { RLP } = require("@ethereumjs/rlp");
const { keccak256 } = require("ethers");

const toBuf = (x) => {
  if (Buffer.isBuffer(x)) return x;
  if (typeof x === "string" && x.startsWith("0x")) return Buffer.from(x.slice(2), "hex");
  return Buffer.from(x);
};
function keccakBuf(b) {
  return Buffer.from(keccak256("0x" + toBuf(b).toString("hex")).slice(2), "hex");
}
function rlpEncode(x) {
  return Buffer.from(RLP.encode(x));
}
function rlpDecode(b) {
  return RLP.decode(Uint8Array.from(b));
}

function bytesToNibbles(b) {
  const out = [];
  for (const x of b) {
    out.push(x >> 4);
    out.push(x & 0x0f);
  }
  return out;
}
function hpEncode(nibbles, isLeaf) {
  const odd = nibbles.length % 2 === 1;
  const flags = (isLeaf ? 2 : 0) | (odd ? 1 : 0);
  const bytes = [];
  let start = 0;
  if (odd) {
    bytes.push((flags << 4) | nibbles[0]);
    start = 1;
  } else {
    bytes.push(flags << 4);
  }
  for (let i = start; i < nibbles.length; i += 2) {
    bytes.push((nibbles[i] << 4) | nibbles[i + 1]);
  }
  return Buffer.from(bytes);
}

// Build a trie over [{key: Buffer, value: Buffer}]. Returns { root, nodes } where
// nodes maps hex(hash)->rlp Buffer.
function buildTrie(entries) {
  const nodes = {};
  function store(items) {
    const rlp = rlpEncode(items);
    const h = keccakBuf(rlp);
    nodes[h.toString("hex")] = rlp;
    return h; // referenced by 32-byte hash (all our nodes are > 32 bytes)
  }
  function commonPrefix(pairs) {
    let cp = pairs[0].nibbles.slice();
    for (const p of pairs) {
      let i = 0;
      while (i < cp.length && i < p.nibbles.length && cp[i] === p.nibbles[i]) i++;
      cp = cp.slice(0, i);
    }
    return cp;
  }
  function build(pairs) {
    if (pairs.length === 1) {
      return store([hpEncode(pairs[0].nibbles, true), pairs[0].value]);
    }
    const cp = commonPrefix(pairs);
    if (cp.length > 0) {
      const stripped = pairs.map((p) => ({ nibbles: p.nibbles.slice(cp.length), value: p.value }));
      const child = build(stripped);
      return store([hpEncode(cp, false), child]);
    }
    // branch
    const slots = new Array(16).fill(Buffer.alloc(0));
    let branchValue = Buffer.alloc(0);
    const groups = {};
    for (const p of pairs) {
      if (p.nibbles.length === 0) {
        branchValue = p.value;
      } else {
        const nib = p.nibbles[0];
        (groups[nib] = groups[nib] || []).push({ nibbles: p.nibbles.slice(1), value: p.value });
      }
    }
    for (let nib = 0; nib < 16; nib++) {
      if (groups[nib]) slots[nib] = build(groups[nib]);
    }
    return store([...slots, branchValue]);
  }
  const pairs = entries.map((e) => ({ nibbles: bytesToNibbles(toBuf(e.key)), value: toBuf(e.value) }));
  const root = build(pairs);
  return { root, nodes };
}

// Collect the proof node set (rlp Buffers) along `key` from `root`.
function getProof(root, nodes, key) {
  const path = bytesToNibbles(toBuf(key));
  const out = [];
  let cur = root;
  let idx = 0;
  for (let hop = 0; hop < 512; hop++) {
    const rlp = nodes[toBuf(cur).toString("hex")];
    if (!rlp) break;
    out.push(rlp);
    const items = rlpDecode(rlp).map((x) => Buffer.from(x));
    if (items.length === 2) {
      const enc = items[0];
      const isLeaf = (enc[0] >> 4) & 0x2;
      const odd = (enc[0] >> 4) & 0x1;
      let fragLen = (enc.length - 1) * 2 + (odd ? 1 : 0);
      if (isLeaf) break;
      idx += fragLen;
      cur = items[1];
    } else {
      if (idx >= path.length) break;
      const nib = path[idx];
      idx += 1;
      const child = items[nib];
      if (!child || child.length === 0) break;
      cur = child;
    }
  }
  return out;
}

// rlp(transactionIndex) — the receipts-trie key.
function txIndexKey(i) {
  if (i === 0) return Buffer.from([0x80]);
  return rlpEncode(i);
}

// Build an EIP-2718 type-2 receipt value: 0x02 || rlp([status, cumGas, bloom, logs]).
// log = [address(20), [topics...], data].
function encodeReceipt(type, { status, cumulativeGas, logs }) {
  const bloom = Buffer.alloc(256, 0);
  const rlpLogs = logs.map((l) => [toBuf(l.address), l.topics.map(toBuf), toBuf(l.data)]);
  const body = rlpEncode([status, cumulativeGas, bloom, rlpLogs]);
  if (type === 0) return body; // legacy: value is the rlp list directly
  return Buffer.concat([Buffer.from([type]), body]); // typed
}

module.exports = { buildTrie, getProof, txIndexKey, encodeReceipt, keccakBuf, rlpEncode, bytesToNibbles };