Indexed Merkle Tree

A TypeScript implementation of Indexed Merkle Trees with Poseidon hash function support for generating and verifying non-membership proofs. This library provides an efficient way to prove that a value does not exist in a set using cryptographic proofs.

Features

• 🌳 Indexed Merkle Tree: Efficient tree structure for membership/non-membership proofs
• 🔐 Poseidon Hash: Uses Poseidon hash function for cryptographic security
• ⚡ Circom Circuits: Included zk-SNARK circuits for zero-knowledge proofs
• 📦 Serialization: Complete state serialization/deserialization support
• 💾 File I/O: Save and load tree states to/from files
• ✅ Type Safe: Full TypeScript support with comprehensive type definitions
• 🧪 Well Tested: Comprehensive test suite with 100% functionality coverage
• 🚀 Zero Dependencies: Only requires circomlibjs for Poseidon hashing

Installation

npm install @jayanth-kumar-morem/indexed-merkle-tree circomlibjs

Quick Start

import { IndexedMerkleTree } from '@jayanth-kumar-morem/indexed-merkle-tree';
import { buildPoseidon } from 'circomlibjs';

async function example() {
    // Initialize Poseidon hash function
    const poseidon = await buildPoseidon();
    
    // Create a new Indexed Merkle Tree
    const tree = new IndexedMerkleTree(poseidon);
    
    // Insert values
    await tree.insert(100n);
    await tree.insert(200n);
    await tree.insert(150n);
    
    // Generate a non-membership proof for value 175
    const proof = tree.createNonMembershipProof(175n);
    
    // Verify the proof
    const isValid = tree.verifyNonMembershipProof(proof);
    console.log('Proof is valid:', isValid); // true
    
    // Save tree state
    await tree.saveToFile('./tree-state.json');
    
    // Load tree state
    const loadedTree = await IndexedMerkleTree.loadFromFile('./tree-state.json');
}

example().catch(console.error);

API Reference

Class: IndexedMerkleTree

Constructor

constructor(poseidon: any)

Creates a new Indexed Merkle Tree instance.

Parameters:

• poseidon: Poseidon hash function instance from circomlibjs

Properties

• depth: number - Tree depth (readonly, always 32)
• size: number - Number of leaves in the tree
• root: bigint - Current root hash of the tree

Methods

async insert(value: bigint): Promise<void>

Inserts a new value into the tree.

Parameters:

• value: The bigint value to insert

Throws:

• Error if the value already exists in the tree

createNonMembershipProof(query: bigint): NonMembershipProof

Creates a non-membership proof for a given value.

Parameters:

• query: The bigint value to prove non-membership for

Returns:

• NonMembershipProof object containing proof data

Throws:

• Error if no predecessor is found (empty tree)

verifyNonMembershipProof(proof: NonMembershipProof): boolean

Verifies a non-membership proof.

Parameters:

• proof: The proof object to verify

Returns:

• true if proof is valid, false otherwise

serialize(): SerializedIMT

Serializes the tree state to a JSON-compatible object.

Returns:

• SerializedIMT object with string representations of bigint values

static deserialize(data: SerializedIMT, poseidon: any): IndexedMerkleTree

Deserializes a tree state from a JSON-compatible object.

Parameters:

• data: Serialized tree data
• poseidon: Poseidon hash function instance

Returns:

• New IndexedMerkleTree instance with restored state

async saveToFile(filePath: string): Promise<void>

Saves the tree state to a JSON file.

Parameters:

• filePath: Path where to save the file (directories will be created if needed)

static async loadFromFile(filePath: string, poseidon?: any): Promise<IndexedMerkleTree>

Loads a tree state from a JSON file.

Parameters:

• filePath: Path to the file to load
• poseidon: Optional Poseidon instance (will be built if not provided)

Returns:

• New IndexedMerkleTree instance with loaded state

getLeaves(): Leaf[]

Returns a copy of all leaves in the tree.

Returns:

• Array of Leaf objects

getNodesAtLevel(level: number): bigint[]

Returns all nodes at a specific tree level.

Parameters:

• level: Tree level (0 = leaves, increasing towards root)

Returns:

• Array of bigint node values

Throws:

• Error if level is invalid

Interfaces

Leaf

interface Leaf {
    val: bigint;      // The leaf value
    nextVal: bigint;  // Next value in sorted order (0n if last)
    nextIdx: number;  // Index of next leaf
}

NonMembershipProof

interface NonMembershipProof {
    query: bigint;       // The value being proved absent
    preLeaf: Leaf;       // The predecessor leaf
    path: bigint[];      // Merkle path (sibling hashes)
    directions: number[]; // Path directions (0 = left, 1 = right)
    root: bigint;        // Tree root at time of proof
}

SerializedIMT

interface SerializedIMT {
    depth: number;
    nodes: string[][];    // String representations of bigint values
    leaves: {
        val: string;      // String representation of bigint
        nextVal: string;  // String representation of bigint
        nextIdx: number;
    }[];
}

Use Cases

Privacy-Preserving Applications

• Prove you're not in a blocklist without revealing your identity
• Demonstrate absence from a database without exposing the data

Zero-Knowledge Proofs

• Integration with zk-SNARK circuits for scalable privacy
• Batch verification of multiple non-membership claims

Blockchain Applications

• Efficient state exclusion proofs
• Privacy-preserving transaction validation

Circom Circuits for Zero-Knowledge Proofs

This package includes pre-built circom circuits for generating zero-knowledge proofs of non-membership and insertion operations. These circuits allow you to prove statements about the tree without revealing the actual tree structure or values.

Accessing Circom Files

The circom files are included in the npm package and can be accessed like this:

const path = require('path');
const fs = require('fs');

// Get the package installation path
const packagePath = path.dirname(require.resolve('@jayanth-kumar-morem/indexed-merkle-tree/package.json'));

// Read the circom circuits
const nonMembershipCircuit = fs.readFileSync(
    path.join(packagePath, 'circom', 'IMTNonMembership.circom'), 
    'utf8'
);

const insertionCircuit = fs.readFileSync(
    path.join(packagePath, 'circom', 'IMTInsertion.circom'), 
    'utf8'
);

Available Circuits

1. IMTNonMembership.circom

Proves that a value does not exist in the indexed merkle tree.

Template: IMTNonMembership(depth)

Public Inputs:

• root_pub: The merkle tree root (public)

Private Inputs:

• query: The value to prove non-membership for
• pre_val: The predecessor value (should be 0 for IMT)
• pre_next: The next value after predecessor
• path[depth]: Merkle path (sibling hashes)
• dirs[depth]: Path directions (0 = left, 1 = right)

Usage Example:

// Generate a non-membership proof using the TypeScript library
const tree = new IndexedMerkleTree(poseidon);
await tree.insert(100n);
await tree.insert(200n);

const proof = tree.createNonMembershipProof(150n);

// Use the proof data as circuit inputs
const circuitInputs = {
    query: proof.query.toString(),
    pre_val: proof.preLeaf.val.toString(),
    pre_next: proof.preLeaf.nextVal.toString(),
    path: proof.path.map(p => p.toString()),
    dirs: proof.directions,
    root_pub: proof.root.toString()
};

// Compile and run the circuit with your preferred circom toolchain
// (snarkjs, circom_tester, etc.)

2. IMTInsertion.circom

Proves that a value was correctly inserted into the indexed merkle tree, transforming it from an old state to a new state.

Template: IMTInsertion(depth)

Inputs:

• query: The value being inserted
• pre_val: The predecessor value (should be 0 for IMT)
• pre_next: The next value after predecessor
• path[depth]: Merkle path to the predecessor leaf
• dirs[depth]: Path directions (0 = left, 1 = right)
• old_root: The tree root before insertion

Outputs:

• new_root: The tree root after insertion

Usage Example:

// Before insertion
const tree = new IndexedMerkleTree(poseidon);
await tree.insert(100n);
await tree.insert(300n);
const oldRoot = tree.root;

// Generate non-membership proof for the value to be inserted
const proof = tree.createNonMembershipProof(200n);

// Perform the insertion
await tree.insert(200n);
const newRoot = tree.root;

// Use the data as circuit inputs
const circuitInputs = {
    query: "200",
    pre_val: proof.preLeaf.val.toString(),
    pre_next: proof.preLeaf.nextVal.toString(),
    path: proof.path.map(p => p.toString()),
    dirs: proof.directions,
    old_root: oldRoot.toString()
};

// The circuit will output new_root which should match newRoot.toString()

Integration with zk-SNARK Tools

These circuits are designed to work with standard circom toolchains:

Using with snarkjs

# Compile the circuit
circom circom/IMTNonMembership.circom --r1cs --wasm --sym

# Generate witness
node generate_witness.js IMTNonMembership.wasm input.json witness.wtns

# Generate proof (requires trusted setup)
snarkjs groth16 prove circuit.zkey witness.wtns proof.json public.json

Using with circom_tester (for testing)

const circom_tester = require("circom_tester");
const path = require("path");

describe("IMT Circuits", () => {
    let circuit;
    
    before(async () => {
        const packagePath = path.dirname(require.resolve('@jayanth-kumar-morem/indexed-merkle-tree/package.json'));
        const circuitPath = path.join(packagePath, 'circom', 'IMTNonMembership.circom');
        circuit = await circom_tester.wasm(circuitPath);
    });
    
    it("should verify non-membership proof", async () => {
        const input = {
            query: "150",
            pre_val: "0",
            pre_next: "200",
            path: [...], // from your proof
            dirs: [...], // from your proof
            root_pub: "..." // tree root
        };
        
        const witness = await circuit.calculateWitness(input);
        await circuit.checkConstraints(witness);
    });
});

Advanced Usage

Working with Large Values

const largeValue = BigInt('0x' + 'f'.repeat(64)); // 32-byte value
await tree.insert(largeValue);

const proof = tree.createNonMembershipProof(largeValue - 1n);
const isValid = tree.verifyNonMembershipProof(proof);

Batch Operations

const values = [100n, 200n, 300n, 150n, 250n];

// Insert multiple values
for (const value of values) {
    await tree.insert(value);
}

// Generate multiple proofs
const queries = [125n, 175n, 275n, 400n];
const proofs = queries.map(q => tree.createNonMembershipProof(q));

// Verify all proofs
const results = proofs.map(proof => tree.verifyNonMembershipProof(proof));
console.log('All proofs valid:', results.every(r => r));

State Persistence

// Save tree state
await tree.saveToFile('./data/tree-backup.json');

// Load and continue working
const restoredTree = await IndexedMerkleTree.loadFromFile('./data/tree-backup.json');
await restoredTree.insert(999n);

// Verify proofs still work
const proof = restoredTree.createNonMembershipProof(500n);
const isValid = restoredTree.verifyNonMembershipProof(proof);

Performance

• Tree Depth: Fixed at 32 levels for optimal balance of security and performance
• Insertion: O(log n) time complexity
• Proof Generation: O(log n) time complexity
• Proof Verification: O(log n) time complexity
• Memory Usage: Efficient sparse tree representation

Security Considerations

• Uses Poseidon hash function designed for zero-knowledge applications
• 32-level tree provides 2^32 capacity with strong security guarantees
• All operations are deterministic and verifiable
• Proofs are cryptographically sound and cannot be forged

Contributing

Contributions are welcome! Please feel free to submit a Pull Request. For major changes, please open an issue first to discuss what you would like to change.

Development Setup

git clone https://github.com/jayanth-kumar-morem/indexed-merkle-tree.git
cd indexed-merkle-tree
npm install
npm run build
npm test

Running Tests

npm test           # Run all tests
npm run test:watch # Run tests in watch mode
npm run test:coverage # Run tests with coverage

License

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

Author

Jayanth Kumar

• Email: [email protected]
• GitHub: @jayanth-kumar-morem

Acknowledgments

• Built with circomlibjs for Poseidon hashing
• Inspired by the indexed Merkle tree research in zero-knowledge cryptography

For more examples and detailed documentation, visit the GitHub repository.