# 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.

[![npm version](https://badge.fury.io/js/@jayanth-kumar-morem/sparse-merkle-tree.svg)](https://badge.fury.io/js/@jayanth-kumar-morem/sparse-merkle-tree)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)

## 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

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

## Quick Start

```typescript
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:**
```typescript
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:**
```typescript
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:**
```typescript
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:**
```typescript
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:**
```typescript
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:**
```typescript
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:**
```typescript
const isValid = smt.verifyNonMembershipProof(
  999n,
  proof.siblings,
  proof.pathBits,
  proof.root
);
```

## Types

### NonMembershipProof

```typescript
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

```typescript
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

```typescript
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

```typescript
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:

```bash
npm test
```

Run tests with coverage:

```bash
npm run test:coverage
```

Run tests in watch mode:

```bash
npm run test:watch
```

## Building

Build the TypeScript code:

```bash
npm run build
```

## Linting

Lint the code:

```bash
npm run lint
```

Fix linting issues:

```bash
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](LICENSE) file for details.

## Related Projects

- [circomlib](https://github.com/iden3/circomlib) - Poseidon hash function implementation
- [merkletreejs](https://github.com/miguelmota/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