The Nearly Optimal Merkle Tree (NOMT)

One of the biggest performance bottlenecks in blockchain systems is state management - how quickly can you update and verify the system's state? Traditional Merkle trees, while secure, are slow because they require many disk reads and complex hash calculations.

Let's break down how NOMT solves this with a concrete example:

In a traditional 16-ary Merkle tree (like Ethereum's), to update a single account balance:

1. Read 16 sibling nodes at each level

2. Compute 16 hashes at each level

3. Update the entire path to the root

This means that for a tree with 1 million accounts (depth ~5), you need:

• ~80 disk reads (16 * 5)

• ~80 hash computations

• Multiple disk writes

NOMT optimises this process:

The result? The same account update in NOMT requires:

• ~10 disk reads (2 * 5)

• ~10 hash computations

• Efficient batch writes

Real-world impact: NOMT enables Spicenet to process thousands of state updates per second, essential for a high-performance exchange.