@ergots/avltree

Pure-TypeScript AVL+ authenticated dictionary verifier. Browser-compatible. Validated byte-for-byte against ergo_avltree_rust (HEAD 879545c).

Given a starting digest, a serialized AD proof, a tree configuration, and a batch of operations, verifyAvlBatch reconstructs the mutated tree, checks every leaf hash, and returns the resulting 33-byte digest plus the old value at each key — or null if the proof is invalid. The package is independently useful to wallets, DEX simulators, and light clients verifying Ergo state transitions, and is also a runtime dependency of @ergots/ergoscript (phase 2h-b).

Install

npm install @ergots/avltree

Usage

import { verifyAvlBatch, verifyAvlLookup, type AvlTreeConfig, type Operation } from '@ergots/avltree';

// Config matches the on-chain tree parameters.
const config: AvlTreeConfig = {
  keyLength: 32,
  valueLengthOpt: null,   // variable-length values
};

// Starting digest from the chain state (33 bytes: 32-byte root label + 1-byte height).
const startingDigest = new Uint8Array(33);
// (fill from actual chain state)

// Serialized AD proof bytes from the block's extension section.
const proof = new Uint8Array([/* aabb...cc */]);

// A batch of operations to verify.
const operations: Operation[] = [
  { tag: 'Lookup',  key: new Uint8Array(32) /* actual key bytes */ },
  { tag: 'Insert',  key: new Uint8Array(32), value: new Uint8Array([0x01, 0x02, 0x03]) },
];

const result = verifyAvlBatch(startingDigest, proof, config, operations);
if (result === null) {
  // Proof invalid — digest mismatch, malformed proof, or operation precondition failed.
} else {
  console.log('new digest:', result.newDigest);  // Uint8Array, 33 bytes
  console.log('old values:', result.results);    // (Uint8Array | null)[] — null = key was absent
}

// Single-key read convenience wrapper:
const lookup = verifyAvlLookup(startingDigest, proof, config, new Uint8Array(32));
if (lookup === null) {
  // Proof invalid.
} else if (lookup.value === null) {
  console.log('key absent from tree');
} else {
  console.log('value:', lookup.value);
}

See API.md for the full reference (every export, signature, error codes, and type definitions).

Browser compatibility

Runs unchanged in evergreen browsers and Node >= 20. No Buffer, no node:crypto, no dynamic Node built-ins, no WASM. ESM-only.

The verifier is stateless: inputs in, structured result (or null) out. No I/O, no clock, no storage.

What this package does NOT do

• Proof construction. The prover (BatchAVLProver) is not ported. Fixture generation lives in the Rust fixture-gen/ crate.
• Storage. No versioned AVL storage, no IndexedDB, no persistent tree state.
• Cost accounting. Ergo's per-operation cost charging is the responsibility of @ergots/ergoscript's SAvlTree.* method handlers.

Reference implementation

This package is a clean-room TypeScript port of ergo_avltree_rust (verifier path only), validated byte-for-byte against fixtures generated by the Rust reference. The algorithmic basis is the KMZ16 AVL+ authenticated dictionary; KMZ17 Appendix B documents the keyMatchesLeaf range semantics.

See facts/avltree.md for the load-bearing interface contract.

License

MIT