@ergots/avltree

Pure-TypeScript AVL+ authenticated dictionary — verifier and prover. Browser-compatible, no WASM. Validated byte-for-byte against ergo_avltree_rust (our fork, pin 568e7c3). 374 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).

Storage codec

serializeNode / deserializeNode encode one node for persistence, byte-identical to ergo_avltree_rust's AVLTree::pack / AVLTree::unpack for well-formed input — four checks are deliberately stricter than the reference on malformed input; see API.md for what they are. Traversal is yours: walk the tree and store one record per node, keyed by label(node).

import { serializeNode, label, type AvlNode, type AvlTreeConfig } from '@ergots/avltree'

const config: AvlTreeConfig = { keyLength: 32, valueLengthOpt: null }

export function store(node: AvlNode, write: (key: Uint8Array, value: Uint8Array) => void) {
  write(label(node), serializeNode(node, config))
}

Internal records hold child labels, not child subtrees, so deserializeNode returns internals whose children are LabelNode stubs — relink them by label lookup after loading. Once loaded, call BatchAVLProver.restoreRoot(root, height) before using the prover further. See API.md for the byte layout, error conditions, and a full load-then-restore example.

Storage GC

BatchAVLProver.removedNodes() returns the previous cycle's nodes whose labels are no longer reachable from the current root — the rows a VersionedAVLStorage backend should delete. Call it after applying a batch's operations and before generateProof() / restoreRoot(); both rebase the proof cycle, after which it returns [].

import { label, type BatchAVLProver, type VersionedAVLStorage } from '@ergots/avltree'

class MyStorage implements VersionedAVLStorage {
  // rollback / version / rollbackVersions / flush elided for brevity — see
  // API.md's VersionedAVLStorage entry for their full contracts.
  update(prover: BatchAVLProver, additionalData: [Uint8Array, Uint8Array][]): void {
    // ... write current nodes ...
    for (const node of prover.removedNodes()) {
      this.deleteRow(label(node)) // must tolerate absent rows
    }
  }
  // PersistentBatchAVLProver.generateProofAndUpdateStorage() calls update()
  // BEFORE generateProof() — the ordering removedNodes() requires.
}

See API.md for the full ordering contract, purity guarantees, and the first-cycle sentinel note.

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