Skip to content

Latest commit

 

History

History
157 lines (109 loc) · 5.55 KB

README.md

File metadata and controls

157 lines (109 loc) · 5.55 KB

QMDB: Quick Merkle Database

Build Status Tests

Overview

The Quick Merkle Database (QMDB) is a high-performance verifiable key-value store, designed to optimize blockchain state storage. It is designed to take advantage of modern SSDs and minimize flash write amplification with an append-only design. QMDB can perform in-memory Merklelization with minimal DRAM usage, and offers efficient cryptographic proofs for inclusion, exclusion, and historical states.

Read the QMDB paper here: https://layerzero.network/publications/QMDB_13Jan2025_v1.0.pdf

QMDB is ongoing research. Designed for high performance and practical use, some features are still evolving. We invite feedback and contributions from the community.

Use Cases

  • Blockchain State Storage: Ideal for maintaining verifiable state in decentralized systems.
  • Database Optimization: Useful for any application requiring high-performance verifiable key-value storage.

Features

  • SSD-Optimized Design
    Reduces flash write amplification by storing updates as append-only twigs.

  • In-Memory Merkleization
    Minimizes disk I/O for proofs and updates, requiring only a small DRAM footprint.

  • Low I/O Overhead
    Achieves O(1) I/O per update and just one SSD read per state access.

  • High Throughput
    Demonstrated 6× gains over RocksDB and 8× over state-of-the-art verifiable databases.

  • Scalable Architecture
    Validated on datasets up to 15 billion entries, with projections up to 280 billion entries on a single machine.

  • Broad Hardware Compatibility
    Runs effectively on both consumer-grade PCs and enterprise servers, lowering barriers to blockchain participation.

Key data structures

  • Entry (qmdb/src/entryfile/entry.rs): The primitive data structure in QMDB, with each Entry corresponding to a single key-value pair.
  • Twigs (qmdb/src/merkletree/twig.rs): A compact and efficient representation of the Merkle tree, minimizing DRAM usage by keeping most data on SSD.

Installation

To get started, clone the repository:

git clone https://github.com/LayerZero-Labs/qmdb
cd qmdb

The following pre-requisites are required to build QMDB:

  • g++
  • linux-libc-dev
  • libclang-dev
  • unzip
  • libjemalloc-dev
  • make

We provide a script to install the pre-requisites on Ubuntu:

./install-prereqs-ubuntu.sh

Build the project using Cargo:

cargo build --release

Run a quick benchmark:

head -c 10M </dev/urandom > randsrc.dat
cargo run --bin speed -- --entry-count 4000000

Run unit tests:

cargo test

Getting started

We include a simple example in examples/v2_demo.rs to create a QMDB instance and interact with the database. You can run it as follows:

cargo run --example v2_demo

Directory Structure

  • qmdb/src/: Main QMDB source code

    • examples/: Example projects demonstrating QMDB usage.
    • tests/: Unit tests.
    • entryfile/: Implements the Entry data structure
    • merkletree/: Contains Twigs (Merkle subtrees ordered by insertion time and not key)
    • indexer/: In-memory indexer to map keys to QMDB entries
    • indexer/hybrid/: Hybrid indexer that is optimized for SSD
    • stateless/: Build a in-memory subset of world state for stateless validation
    • seqads/: Sequential ADS, used to generate input data for stateless validation
    • tasks/: The Create/Update/Delete requests to QMDB must be encapsulated into ordered tasks
    • utils/: Miscellaneous utility and helper functions.
  • bench/: Benchmarking utility.

  • hpfile/: Head-prunable file: HPfile are a series of fixed-size files in QMDB that simulate a single large file, enabling efficient pruning from the front.

Contributing

See CONTRIBUTING.md for more information on how to contribute to QMDB.

Any questions?

Please raise a GitHub issue.

License

This project is dual licensed under the MIT License and the Apache License 2.0.

Acknowledgements

If you use QMDB in a publication, please cite it as:

QMDB: Quick Merkle Database
Isaac Zhang, Ryan Zarick, Daniel Wong, Thomas Kim, Bryan Pellegrino, Mignon Li, Kelvin Wong
https://arxiv.org/abs/2501.05262

@article{zhang2025qmdb,
  title={Quick Merkle Database},
  author={Zhang, Isaac and Zarick, Ryan and Wong, Daniel and Kim, Thomas and Pellegrino, Bryan and Li, Mignon and Wong, Kelvin},
  journal={arXiv preprint arXiv:2501.05262},
  year={2025}
}

QMDB is a product of LayerZero Labs Research.

LayerZero LayerZero

Homepage | Docs | Developers