npm package: @scintilla-network/trees
Description: Merkle and Patricia Trees for Scintilla Network
Author: Scintilla Labs
Latest version: 1.0.0

# Trees

Implementations of Merkle and Patricia Trees.

## Installation

```bash
npm install @scintilla-network/trees
```

## Supported Hash Algorithms

### Post-Quantum Resistant (Recommended for 2025+)

- **`sha3-256`** - NIST approved, 256-bit security (128-bit post-quantum)
- **`sha3-512`** - NIST approved, 512-bit security (256-bit post-quantum) ⭐ Most Secure
- **`blake3`** - Modern, fast, secure
- **`k12`** - KangarooTwelve, high performance ⚡ Fastest
- **`shake128`** - SHA-3 XOF, variable length
- **`shake256`** - SHA-3 XOF, variable length

### Classic Algorithms (Legacy Support)

- **`sha256`** - Most widely used, 256-bit
- **`sha512`** - 512-bit security
- **`blake2b`** - Fast, 256-bit output
- **`blake2b-64`** - Fast, 512-bit output
- **`blake2s`** - Fast, 256-bit output
- **`ripemd160`** - 160-bit (legacy)

## Usage

### Merkle Tree

#### Basic Usage

```javascript
import { MerkleTree } from '@scintilla-network/trees';
import { randomBytes } from '@scintilla-network/hashes/utils';

// Create some data (Uint8Array)
const elements = [
  randomBytes(32),
  randomBytes(32),
  randomBytes(32),
];

const tree = new MerkleTree(elements, 'sha3-256');

// Get root hash
const root = tree.root('hex'); // or tree.root() for Uint8Array
console.log('Root:', root); 
```

### Dynamic Element Addition

```javascript
// Add elements dynamically
const newElement = randomBytes(32);
const newRoot = tree.addElement(newElement);

console.log('New root after addition:', toHex(newRoot));
console.log('Tree size:', tree.size);
```

### Generating and Verifying Proofs

```javascript
// Generate proof for an element
const proof = tree.proof(elements[0]);

// Verify using instance method
const isValid = tree.verify(elements[0]);
console.log('Is valid?', isValid); // true

// Static verification (without instance)
const staticValid = MerkleTree.verify(
  elements[0],
  proof,
  newRoot,
  'sha3-256'
);
console.log('Static verification:', staticValid); // true
```

## API Reference

### Constructor

```javascript
new MerkleTree(elements = [], algorithm = 'sha3-256')
```

Creates a new Merkle Tree.

**Parameters:**
- `elements` (Uint8Array[]): Initial array of Uint8Array elements
- `algorithm` (string): Hash algorithm name (default: 'sha3-256')

### Instance Methods

- `addElement(element)` - Adds a new element to the Merkle tree and rebuilds it.

- `root([encoding])` - Gets the root hash of the Merkle tree.

- `proof(element)` - Generates a Merkle proof for a given element.

- `verify(element)` - Verifies if an element is part of the Merkle tree.

- `getLeaves()` - Gets all leaves in the tree.

- `getLayer(layerIndex)` - Gets a specific layer of the tree.

- `toJSON()` - Exports the tree to a JSON-serializable format.  

### Static Methods

- `MerkleTree.verify(element, proof, root, algorithm)` - Verifies a Merkle proof without an instance.

- `MerkleTree.fromJSON(json)` - Creates a MerkleTree from a JSON-serialized format.

### Properties

`size` - Gets the number of leaves in the tree.
`depth` - Gets the depth of the tree.
`algorithm` - Gets the hash algorithm name being used.

## Security

### Second Pre-image Attack Prevention

The implementation uses prefix bytes to differentiate between leaf and internal nodes:

- **0x00**: Leaf node prefix
- **0x01**: Internal node prefix

This prevents attackers from creating collisions by treating internal nodes as leaves.

### Post-Quantum Resistance

Following Australian ASD guidelines and NIST recommendations, we recommend using post-quantum resistant hash functions for new projects in 2025+:

- **SHA3-512**: Best overall security (512-bit → 256-bit post-quantum)
- **SHA3-256**: Balanced security (256-bit → 128-bit post-quantum)
- **K12**: High-performance alternative while maintaining security

Grover's algorithm can reduce hash security from 2^n to 2^(n/2) operations, which is why we recommend 512-bit hashes for maximum future-proofing.

### Patricia Tree

/!\ Early stage of development and not yet fully tested. /!\

#### Basic Usage

```javascript
import { PatriciaTree } from '@scintilla-network/trees';

// Create a new Patricia Tree
const tree = new PatriciaTree('sha3-256');
tree.addElement('name', 'Alice');
tree.addElement('age', '30');
tree.addElement('city', 'Tokyo');

// Get the root hash
const root = tree.root('hex');
console.log('Root:', root);

// Get element 
const name = tree.get('name');
console.log('Name:', name);
const age = tree.get('age');
console.log('Age:', age);
const city = tree.get('city');
console.log('City:', city);
const missing = tree.get('country');
console.log('Missing:', missing);

// Proof
const proof = tree.proof('name');
console.log('Proof:', proof);

// Verify
const verified = tree.verify('name', proof);
console.log('Verified:', verified);

// Static verification
const staticVerified = PatriciaTree.verify('name', proof, root, 'sha3-256');
console.log('Static verified:', staticVerified);
```

## License

MIT License - see LICENSE file for details.

## Related

- [@scintilla-network/hashes](https://github.com/Scintilla-Network/hashes) - Hash function library used
- [@scintilla-network/signatures](https://github.com/Scintilla-Network/signatures) - Post-quantum signatures.