IAVL-TS

TypeScript implementation of IAVL (Immutable AVL Tree), a versioned, persistent Merkle tree for CometBFT and Tendermint applications.

Overview

IAVL-TS is a faithful TypeScript port of the Go IAVL v1.3.5 implementation. It provides a versioned, self-balancing Merkle tree that:

• Persistent: All historical versions of the tree are preserved
• Immutable: Historical tree states cannot be modified
• Merkleized: Each node has a cryptographic hash, enabling efficient proofs
• Balanced: Uses AVL tree balancing for O(log n) operations
• Versioned: Supports multiple versions with efficient storage

IAVL trees are used extensively in Cosmos SDK and CometBFT for storing application state with provability and time-travel capabilities.

Features

• ✅ Full IAVL v1.3.5 API compatibility
• ✅ Versioned tree operations (save, load, delete versions)
• ✅ Efficient Merkle proofs (ICS23 compatible)
• ✅ Fast iteration with FastIterator
• ✅ Import/Export functionality
• ✅ Async pruning for background cleanup
• ✅ Comprehensive test coverage (724 tests)
• ✅ TypeScript with full type safety

Installation

npm install iavl-ts
# or
pnpm add iavl-ts
# or
yarn add iavl-ts

Quick Start

import { MutableTree, NodeDB, MemDB } from "iavl-ts";

// Create a new tree
const db = new MemDB();
const ndb = new NodeDB(db, 10000, {});
await ndb.initialize();

const tree = await MutableTree.create(ndb);

// Set some values
await tree.set(Buffer.from("hello"), Buffer.from("world"));
await tree.set(Buffer.from("foo"), Buffer.from("bar"));

// Save version 1
const { hash, version } = await tree.saveVersion();
console.log(`Saved version ${version} with hash:`, hash);

// Get values
const value = await tree.get(Buffer.from("hello"));
console.log(value); // Buffer containing "world"

// Load a previous version (immutable)
const immutableTree = await tree.getImmutable(1n);
const oldValue = await immutableTree.get(Buffer.from("hello"));

Usage Examples

Basic Operations

import { MutableTree, NodeDB } from "iavl-ts";
import { CrossKV } from "@cross/kv";

// Use a persistent database
const db = await CrossKV.open("./my-iavl-db");
const ndb = new NodeDB(db, 10000, {});
await ndb.initialize();

const tree = await MutableTree.create(ndb);

// Insert data
await tree.set(Buffer.from("key1"), Buffer.from("value1"));
await tree.set(Buffer.from("key2"), Buffer.from("value2"));

// Update existing key
await tree.set(Buffer.from("key1"), Buffer.from("updated"));

// Remove a key
const removed = await tree.remove(Buffer.from("key2"));

// Save the version
await tree.saveVersion();

Working with Versions

// Save multiple versions
await tree.set(Buffer.from("key"), Buffer.from("v1"));
await tree.saveVersion(); // version 1

await tree.set(Buffer.from("key"), Buffer.from("v2"));
await tree.saveVersion(); // version 2

await tree.set(Buffer.from("key"), Buffer.from("v3"));
await tree.saveVersion(); // version 3

// Load a historical version (immutable)
const v1 = await tree.getImmutable(1n);
const value = await v1.get(Buffer.from("key")); // Returns "v1"

// Load the tree at a specific version
await tree.loadVersion(2n);
const currentValue = await tree.get(Buffer.from("key")); // Returns "v2"

// Delete old versions
await tree.deleteVersionsTo(1n); // Deletes version 1

Iteration

// Iterate over all keys in order
const iterator = tree.getWorkingTree().iterator();
await iterator.next(); // Position at first element

while (iterator.valid()) {
  const key = iterator.key();
  const value = iterator.value();
  console.log(`${key}: ${value}`);
  await iterator.next();
}

// Iterate over a range
const start = Buffer.from("a");
const end = Buffer.from("z");
const rangeIterator = tree.getWorkingTree().iteratorRange(start, end);
await rangeIterator.next();

while (rangeIterator.valid()) {
  // Process keys between "a" and "z"
  await rangeIterator.next();
}

Merkle Proofs

// Generate a proof for a key
const proof = await tree.getProof(Buffer.from("mykey"));

// Verify the proof
const isValid = await verifyProof(
  proof,
  tree.workingHash(),
  Buffer.from("mykey"),
  Buffer.from("myvalue")
);

Import/Export

import { Exporter, Importer } from "iavl-ts";

// Export a version
const exporter = new Exporter(tree.getWorkingTree());
for await (const node of exporter) {
  // node contains { key, value, version, height }
  // Store or transmit these nodes
}

// Import into a new tree
const newTree = await MutableTree.create(newNdb);
const importer = new Importer(newTree);

for (const node of exportedNodes) {
  await importer.add(node);
}

await importer.commit();

Fast Iterator

import { FastIterator } from "iavl-ts";

// Use FastIterator for high-performance sequential access
const fastIterator = FastIterator.create(undefined, ndb);
await fastIterator.next();

while (fastIterator.valid()) {
  const key = fastIterator.key();
  const value = fastIterator.value();
  await fastIterator.next();
}

Configuration

NodeDB Options

const options = {
  // Enable async pruning (background deletion)
  asyncPruning: true,

  // Initial version number (default: 1)
  initialVersion: 1n,

  // Cache statistics callbacks
  cacheSize: 10000,
};

const ndb = new NodeDB(db, cacheSize, options);

Tree Options

const tree = new MutableTree(
  ndb,
  workingTree,
  skipFastStorageUpgrade // Skip fast storage upgrade for new trees
);

Architecture

IAVL-TS follows a layered architecture:

┌─────────────────────────────────────┐
│        MutableTree                  │  ← Public API for mutations
├─────────────────────────────────────┤
│        ImmutableTree                │  ← Immutable snapshots
├─────────────────────────────────────┤
│     Node / NodeKey / NodeDB         │  ← Storage layer
├─────────────────────────────────────┤
│        Database (KV Store)          │  ← Pluggable storage
└─────────────────────────────────────┘

Key Components

• MutableTree: Provides mutable operations (set, remove, saveVersion)
• ImmutableTree: Read-only view of a specific version
• Node: AVL tree node with Merkle hashing
• NodeDB: Node storage, caching, and version management
• NodeKey: Unique identifier for nodes (version + nonce)
• FastNode: Optimized storage format for leaf nodes
• Iterator: In-order traversal of tree keys
• FastIterator: High-performance sequential access

Differences from Go Implementation

This TypeScript implementation maintains 100% logic compatibility with Go IAVL v1.3.5, with the following environment-specific differences:

1. Language semantics: JavaScript uses references for objects/arrays vs Go's explicit pointers
2. Async operations: All I/O operations are async (vs sync in Go)
3. BigInt: Uses native BigInt for version numbers (vs int64 in Go)
4. Database: Uses pluggable KV stores (@cross/kv) vs LevelDB/BadgerDB

The core algorithms, data structures, and serialization formats are identical.

Performance

Performance characteristics (on M1 Mac):

• Insertions: ~200,000 ops/sec (sequential)
• Random access: 10K lookups in ~100ms
• 100K tree height: ~17 levels (well-balanced)
• Memory: ~37MB for 10K keys with values

See src/tests/large-tree.test.ts for detailed benchmarks.

Testing

# Run all tests
pnpm test

# Run with coverage
pnpm test:coverage

# Run tests in watch mode
pnpm test:watch

# Run tests with UI
pnpm test:ui

The test suite includes:

• Unit tests for all components
• Integration tests for complex workflows
• Scenario tests (random operations, large trees)
• Compatibility tests against Go implementation

Development

# Install dependencies
pnpm install

# Type checking
pnpm typecheck

# Linting
pnpm lint
pnpm lint:fix

# Build
pnpm build

API Reference

See API.md for detailed API documentation.

Contributing

Contributions are welcome! This implementation aims to maintain 100% compatibility with Go IAVL v1.3.5. Please ensure:

• All tests pass
• New features include tests
• Code follows existing style (enforced by ESLint)
• TypeScript types are properly defined

License

Apache 2.0

Acknowledgments

This implementation is based on the original IAVL implementation by the Cosmos team. Special thanks to the CometBFT and Cosmos SDK communities.

References

• Original Go IAVL
• CometBFT
• Cosmos SDK
• ICS23 Proofs Specification