@mixerx/fixed-merkle-tree

Hardened append-only fixed-depth Merkle tree for MixerX.

Version 1 is intentionally not a drop-in replacement for the historical fixed-merkle-tree package. It removes PartialMerkleTree, simpleHash, default exports, arbitrary leaf updates and legacy layer serialization because those contracts were unsafe or ambiguous. Import the named MerkleTree class.

Security contract

• hashFunction and zeroElement are mandatory. The package does not provide a non-cryptographic fallback. Callers must inject the protocol's audited hash.
• Elements are non-empty strings of at most 256 characters. The zero element is reserved for padding and cannot be inserted as a leaf. Callers remain responsible for providing one canonical representation for field elements.
• Levels are limited to 1–31, the largest fixed capacity representable by the array-backed implementation.
• Insertion is sequential. replaceLast is the only explicit frontier rewrite; arbitrary historical leaves cannot be changed. Mutations are committed only after every hash succeeds.
• Serialized state is versioned and contains levels, zero element, leaves and their root. Deserialization rebuilds every layer and rejects a root mismatch.
• Returned layers, elements, zeros, proofs and serialized state are copies or frozen values, never live references.

Usage

import { createHash } from 'node:crypto';
import { MerkleTree } from '@mixerx/fixed-merkle-tree';

const hash = (left: string, right: string): string =>
  createHash('sha256').update(left).update('\0').update(right).digest('hex');

const tree = new MerkleTree(20, {
  hashFunction: hash,
  zeroElement: '0',
});

tree.insert('1');
tree.bulkInsert(['2', '3']);
const proof = tree.path(1);
const trustedRoot = tree.root; // In production, read this from the protocol contract.
const valid = MerkleTree.verifyProof('2', 1, proof, hash, {
  levels: tree.levels,
  root: trustedRoot,
  zeroElement: tree.zeroElement,
});

The verification context must be trusted independently from the submitted proof. In particular, zeroElement identifies structural padding and can never prove membership.

Scripts

• yarn typecheck
• yarn lint
• yarn test
• yarn validate

The project is GPL-3.0-only. NOTICE preserves the original ISC attribution.