Trees

Implementations of Merkle and Patricia Trees.

Installation

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

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

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

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

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

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 - Hash function library used
• @scintilla-network/signatures - Post-quantum signatures.