Sparse Merkle Tree TypeScript

A TypeScript implementation of Sparse Merkle Trees with Poseidon hash function support. This library provides efficient sparse merkle tree operations with non-membership proof generation and verification.

Features

• 🌳 Sparse Merkle Tree: Efficient sparse merkle tree implementation
• 🔐 Poseidon Hash: Support for Poseidon hash function (requires circomlib)
• ✅ Non-membership Proofs: Generate and verify non-membership proofs
• 🎯 TypeScript: Full TypeScript support with type definitions
• ⚡ Efficient: Optimized for performance with minimal memory usage
• 🧪 Well-tested: Comprehensive test suite with 100% coverage
• 📦 Zero Dependencies: No runtime dependencies (peer dependency on circomlib)

Installation

npm install @jayanth-kumar-morem/sparse-merkle-tree circomlib

Quick Start

import { SMT } from '@jayanth-kumar-morem/sparse-merkle-tree';
import { buildPoseidon } from 'circomlib';

async function example() {
  // Initialize Poseidon hash function
  const poseidon = await buildPoseidon();
  
  // Create a new Sparse Merkle Tree with depth 20 (default)
  const smt = new SMT(poseidon, 20);
  
  // Add key-value pairs
  smt.add(1n, 100n);
  smt.add(2n, 200n);
  smt.add(42n, 4200n);
  
  // Get values
  console.log(smt.get(1n)); // 100n
  console.log(smt.has(2n)); // true
  console.log(smt.get(999n)); // undefined
  
  // Get the merkle root
  console.log(smt.root); // bigint root hash
  
  // Generate non-membership proof for a key not in the tree
  const proof = smt.createNonMembershipProof(999n);
  
  // Verify the proof
  const isValid = smt.verifyNonMembershipProof(
    999n,
    proof.siblings,
    proof.pathBits,
    proof.root
  );
  console.log(isValid); // true
}

example();

API Reference

Constructor

new SMT(poseidon, depth?)

Creates a new Sparse Merkle Tree instance.

Parameters:

• poseidon - Poseidon hash function instance from circomlib
• depth (optional) - Tree depth (default: 20)

Example:

const smt = new SMT(poseidon, 16); // Tree with depth 16

Methods

add(key: bigint, value: bigint): void

Adds a key-value pair to the tree.

Parameters:

• key - The key as a bigint
• value - The value as a bigint

Example:

smt.add(42n, 1337n);

get(key: bigint): bigint | undefined

Retrieves the value for a given key.

Parameters:

• key - The key to look up

Returns:

• The value if the key exists, undefined otherwise

Example:

const value = smt.get(42n); // Returns 1337n or undefined

has(key: bigint): boolean

Checks if a key exists in the tree.

Parameters:

• key - The key to check

Returns:

• true if the key exists, false otherwise

Example:

if (smt.has(42n)) {
  console.log('Key exists!');
}

root: bigint (getter)

Gets the current merkle root of the tree.

Returns:

• The root hash as a bigint

Example:

const currentRoot = smt.root;

createNonMembershipProof(key: bigint): NonMembershipProof

Creates a non-membership proof for a key that is not in the tree.

Parameters:

• key - The key to prove non-membership for

Returns:

• NonMembershipProof object containing:
  • siblings: bigint[] - Array of sibling hashes
  • pathBits: number[] - Array of path bits (0 or 1)
  • root: bigint - The tree root

Example:

const proof = smt.createNonMembershipProof(999n);

verifyNonMembershipProof(key: bigint, siblings: bigint[], pathBits: number[], expectedRoot: bigint): boolean

Verifies a non-membership proof.

Parameters:

• key - The key that should not be in the tree
• siblings - Array of sibling hashes from the proof
• pathBits - Array of path bits from the proof
• expectedRoot - The expected root hash

Returns:

• true if the proof is valid, false otherwise

Example:

const isValid = smt.verifyNonMembershipProof(
  999n,
  proof.siblings,
  proof.pathBits,
  proof.root
);

Types

NonMembershipProof

interface NonMembershipProof {
  siblings: bigint[];    // Sibling hashes for the merkle path
  pathBits: number[];    // Path bits (0 for left, 1 for right)
  root: bigint;          // Tree root hash
}

Use Cases

This library is particularly useful for:

• Zero-Knowledge Proofs: Proving non-membership without revealing the entire tree
• Blockchain Applications: Efficient state management and proof generation
• Privacy-Preserving Systems: Selective disclosure and private set membership
• Cryptographic Protocols: Building blocks for advanced cryptographic schemes

Performance Considerations

• Tree Depth: Smaller depths (16-20) are recommended for better performance
• Batch Operations: Add multiple values before computing the root for efficiency
• Memory Usage: The tree stores only non-zero leaves, making it memory efficient
• Proof Size: Proof size is O(depth), typically 20-32 elements

Examples

Basic Usage

import { SMT } from '@jayanth-kumar-morem/sparse-merkle-tree';
import { buildPoseidon } from 'circomlib';

async function basicExample() {
  const poseidon = await buildPoseidon();
  const smt = new SMT(poseidon);
  
  // Add some data
  smt.add(1n, 100n);
  smt.add(2n, 200n);
  
  // Check membership
  console.log(smt.has(1n)); // true
  console.log(smt.has(3n)); // false
  
  console.log('Tree root:', smt.root);
}

Non-membership Proofs

async function proofExample() {
  const poseidon = await buildPoseidon();
  const smt = new SMT(poseidon);
  
  // Add some data
  smt.add(10n, 1000n);
  smt.add(20n, 2000n);
  
  // Prove that key 15 is not in the tree
  const proof = smt.createNonMembershipProof(15n);
  
  // Verify the proof
  const isValid = smt.verifyNonMembershipProof(
    15n,
    proof.siblings,
    proof.pathBits,
    proof.root
  );
  
  console.log('Proof is valid:', isValid); // true
  console.log('Proof size:', proof.siblings.length); // equals tree depth
}

Tree Comparison

async function comparisonExample() {
  const poseidon = await buildPoseidon();
  
  const smt1 = new SMT(poseidon);
  const smt2 = new SMT(poseidon);
  
  // Add same data in different order
  smt1.add(1n, 100n);
  smt1.add(2n, 200n);
  
  smt2.add(2n, 200n);
  smt2.add(1n, 100n);
  
  // Trees have the same root regardless of insertion order
  console.log(smt1.root === smt2.root); // true
}

Testing

Run the test suite:

npm test

Run tests with coverage:

npm run test:coverage

Run tests in watch mode:

npm run test:watch

Building

Build the TypeScript code:

npm run build

Linting

Lint the code:

npm run lint

Fix linting issues:

npm run lint:fix

Contributing

1. Fork the repository
2. Create your feature branch (git checkout -b feature/amazing-feature)
3. Commit your changes (git commit -m 'Add some amazing feature')
4. Push to the branch (git push origin feature/amazing-feature)
5. Open a Pull Request

License

This project is licensed under the MIT License - see the LICENSE file for details.

Related Projects

• circomlib - Poseidon hash function implementation
• merkletreejs - Standard Merkle Tree implementation

Changelog

1.0.0

• Initial release
• Basic sparse merkle tree operations
• Non-membership proof generation and verification
• TypeScript support
• Comprehensive test suite