NOMT is a state database, a critical component of a blockchain node.

• High Throughput Commits
• Low latency lookups
• Optimized for merklized state
• Optimized for modern Solid State Drives (SSDs)
• Full-block state proofs

NOMT is designed to be a drag-and-drop replacement for RocksDB, MDBX, LMDB, etc

And to encapsulate all the Merkle Trie logic within it.

Inspired by this blog post.

and funded with a grant from Sovereign Labs (targeted first user)

Scan for GitHub

or navigate to

https://github.com/thrumdev/nomt

Built with care by

three Rust systems programmers from the Polkadot sphere

Why?

• Large State = many users = bigger network effects
• Large State = more complex apps = more value-add
• Every 10k TPS of throughput gives space for ~100M DAU.
• SSDs are getting better fast
• Trend of industry to scale with RAM is misguided long-term
• it's cool

TL;DW

• Support billions of accounts on a 4TB SSD
• Targeting 25k worst-case TPS for V1
• Potential for cheap scaling with multiple SSDs and SSD improvements
• Fully authenticated, ready for interoperability

State Database?

Every node needs to store state: token balances, contract code, prices, etc.

Nodes keep this state in an embedded database on their disk.

Authenticated State Trees

Authenticated State Trees

• Encode the entire state of the blockchain
• With a super light commitment (the "root")
• That can be used to prove the value of any item in the state

Incredibly important for interoperability, light clients, bridging, coprocessors, etc.

NOMT uses a Binary Merkle Trie

Let's talk about SSDs

Typical high-end SSD specs (Q4 2024):

• 4TB capacity
• 40 microsecond latency
• 1M IOPS (I/Os per Second)

Latency: time to serve a single request.
increases as more requests are queued

Throughput: number of requests per second.
note that average latency at 1M IOPS is 1 microsecond!

What's an I/O?

A 4 KB (single page) read or write operation on the disk.

SSDs only work in data of exactly one page.

SSDs are advancing rapidly

SSDs are advancing rapidly

SSDs are advancing rapidly

source: Tom's Hardware

Why not just add more RAM?

• A SuperMicro 12TB motherboard + 12TB of compatible RAM would cost over $40k (for DDR4, not DDR5 RAM)
• A 4TB RAM configuration would cost $5k USD
• 3 4TB SSDs would cost $1500.
• SSD reads can be faster than RAM copies due to Direct Memory Access
• PCI is getting crazy fast

The SSD caveat: Parallelism

• You need a parallel VM to take advantage of SSD IOPS.
• Theoretical max sequential throughput at 40us latency is only ~6K TPS

Back To NOMT

NOMT Architecture

Bitbox: Merkle Node Storage 🥁

Just like this, except each page is 4KB and stores 6 layers
This is known as a "proto-VEB layout"
Pages stored in an on-disk Hash-Table with a WAL
Top 4 levels of the page tree are kept in memory

Beatree: Key-Value Store 🪘

Branches use bitwise prefix compression and separators
Optimized for high-entropy, short keys
Typical Branching factor of 375
~200MB memory per billion items

Engineering Decisions

• Targets Linux as first-class (needed for io-uring)
• Targets generic Unix/macOS as functional (for development)
• Direct I/O for max IOPS
• Single-state DB, stores only finalized state. Unfinalized state must live in-memory.
• Rust 🦀

Space Usage

• 1 billion items estimated at 150GB on-disk
• Large occasional jumps in space usage in bitbox every time the number of items increases by ~64.
  • We are working to make this gradual
• Aiming to support tens of billions of items per 4TB of storage.

Theoretical Performance Example

At 1M IOPS: 62kTPS
At 500k IOPS: 31.5kTPS

Our performance goal for NOMT V1 (EOY 2024) is 25kTPS with 1 billion accounts.

Current benchmarks on 128M accounts at ~40kTPS
side note: we assume random worst-case access

Node Requirements

• RAM/Disk size scale with DB size. 4GB RAM and 256GB SSD for 1B items.
• Disk: >500k IOPS
• CPU: 8 cores

Thank You

https://github.com/thrumdev/nomt

(Appendix: New Bottlenecks)

Bottleneck: Bandwidth

Scenario: Prove 300k state reads against a database of 1B items.

this is 25kTPS * 6 seconds

Proof size is 120MB, requiring 160Mbps of bandwidth.

Note that Polkadot PoVs are only 5MB!

Bottleneck: Bandwidth

Possible solution: use succinct proving techniques to "compress" state proofs. Likely needs GPU acceleration.

Bottleneck: Signature Verification

• Ed25519 signature verification is 26us or 11.5us when batched.
• Secp256k1 verification is 70us

Solution: have dedicated CPU cores or GPU acceleration for signature verification