@ergots/avltree

Pure-TypeScript AVL+ authenticated dictionary — verifier and prover. Browser-compatible, no WASM. Validated byte-for-byte against ergo_avltree_rust (our fork, HEAD 042c830). 192 tests.

Verifier: 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 verifier is independently useful to wallets, DEX simulators, and light clients verifying Ergo state transitions, and is also a runtime dependency of @ergots/ergoscript.

Prover: BatchAVLProver builds in-memory AVL+ trees from a sequence of authenticated operations, records traversal directions, and generates serialized AD proofs identically to ergo_avltree_rust's output (verified byte-for-byte against 10 Rust-generated fixtures). Also ships PersistentBatchAVLProver (versioned-storage wrapper with rollback) and the VersionedAVLStorage interface.

Install

npm install @ergots/avltree

Usage

Verifier

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

const config: AvlTreeConfig = { keyLength: 32, valueLengthOpt: null };
const startingDigest = new Uint8Array(33); // 32-byte root label + 1-byte height
const proof = new Uint8Array([/* … */]);

const result = verifyAvlBatch(startingDigest, proof, config, [
  { tag: 'Lookup',  key: new Uint8Array(32) },
  { tag: 'Insert',  key: new Uint8Array(32), value: new Uint8Array([0x01, 0x02, 0x03]) },
]);
if (result === null) {
  // proof invalid
} else {
  console.log(result.newDigest); // Uint8Array, 33 bytes
  console.log(result.results);   // (Uint8Array | null)[]
}

Prover

import { BatchAVLProver } from '@ergots/avltree';

const prover = new BatchAVLProver(32, null); // 32-byte keys, variable-length values

// Apply operations
prover.performOneOperation({
  tag: 'Insert',
  key: new Uint8Array(32).fill(0x42),
  value: new Uint8Array([1, 2, 3, 4]),
});

// Generate a proof covering all operations since the last generateProof() call
const proof = prover.generateProof();
const digest = prover.digest(); // 33 bytes

// Look up a key without proof generation or tree mutation
const value = prover.unauthenticatedLookup(new Uint8Array(32).fill(0x42));

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

• Cost accounting. Ergo's per-operation cost charging is the responsibility of @ergots/ergoscript's SAvlTree.* method handlers.
• Concrete storage backend. The VersionedAVLStorage interface is provided, but no concrete implementation (redb, IndexedDB, SQLite) ships with the package. Consumers implement the interface for their storage layer.
• Node validation. The verifier checks proof structure and digest consistency, not whether the operations themselves are valid Ergo protocol transitions.

Reference implementation

This package is a clean-room TypeScript port of ergo_avltree_rust (verifier + prover), 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