# NOMT
## Scaling Blockchains with a High Throughput State Database

---

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.

<img src="https://hackmd.io/_uploads/HygqiZNsWJg.png" style="width: 60%; height=auto">

<small>and funded with a grant from Sovereign Labs (targeted first user)</small>

---

Scan for GitHub

<img src="https://hackmd.io/_uploads/ryAJf7ibke.png" style="width: 33%; height=auto">

or navigate to

https://github.com/thrumdev/nomt

---

Built with care by

<img src="https://hackmd.io/_uploads/r1Hhm7iW1g.png" style="width: 20%; height=auto">
<img src="https://hackmd.io/_uploads/rkk5X7sWke.png" style="width: 20%; height=auto">
<img src="https://hackmd.io/_uploads/S1D6mQiZyx.png" style="width: 20%; height=auto">

<small>three Rust systems programmers from the Polkadot sphere</small>

---

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

---

<img src="https://hackmd.io/_uploads/Bk6t87sZke.png" style="width: 60%; height=auto">

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.
<small>increases as more requests are queued</small>

---


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

---

## What's an I/O?

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

<small>SSDs only work in data of exactly one page.</small>

---

## SSDs are advancing rapidly

---

## SSDs are advancing rapidly

| | Crucial T705 | Samsung 980 |
| -------- | -------- | -------- |
| Release Date | Feb. 2024 | Sep. 2020 |
| IOPS | 1.5M | 1M |
| Price at Launch| $689 | $430 |
| Price (Nov. 2024)| $564 | $199
| Capacity | 4TB | 2TB

---

## SSDs are advancing rapidly

<small>source: Tom's Hardware</small>

---


---

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

<img src="https://hackmd.io/_uploads/H1noBg2W1x.png" style="width: 90%; height=auto">

---

## Bitbox: Merkle Node Storage 🥁

<img src="https://www.rob.tech/assets/images/merklization_diagrams/page_1.svg" style="width: 80%; height=auto">

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

---

## Beatree: Key-Value Store 🪘


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

---

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

<small>
Assume 10 billion accounts and simple transactions (2 random read-writes).

Reads: 3 (1 beatree, 2 merkle)
Writes: 5 (2 beatree, 3 merkle)
Total I/O per TX: 16

At 1M IOPS: 62kTPS
At 500k IOPS: 31.5kTPS
</small>

---

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

<br>

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

---

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

<img src="https://hackmd.io/_uploads/ryAJf7ibke.png" style="width: 40%; height=auto">

https://github.com/thrumdev/nomt

---

## (Appendix: New Bottlenecks)

---

## Bottleneck: Bandwidth

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

<small>this is 25kTPS * 6 seconds</small>

Proof size is <span style="color: red">120MB</span>, requiring 160Mbps of bandwidth.

<small>Note that Polkadot PoVs are only 5MB!</small>

---

## Bottleneck: Bandwidth


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

---

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