# QMDB: Quick Merkle Database Source: https://arxiv.org/html/2501.05262v2 Isaac Zhang Ryan Zarick Daniel Wong Thomas Kim Bryan Pellegrino Abstract Quick Merkle Database (QMDB) addresses longstanding bottlenecks in blockchain state management by integrating key-value (KV) and Merkle tree storage into a single unified architecture. QMDB delivers a significant throughput improvement over existing architectures, achieving up to 6×6\times over the widely used RocksDB and 8×8\times over NOMT, a leading verifiable database. Its novel append-only twig-based design enables one SSD read per state access, O⁡(1)O(1) IOs for updates, and in-memory Merkleization on a memory footprint as small as 2.3 bytes per entry enabling it to run on even modest consumer-grade PCs. QMDB scales seamlessly across both commodity and enterprise hardware, achieving up to 2.28 million state updates per second. This performance enables support for 1 million token transfers per second (TPS), marking QMDB as the first solution achieving such a milestone. QMDB has been benchmarked with workloads exceeding 15 billion entries (10× Ethereum’s 2024 state) and has proven the capacity to scale to 280 billion entries on a single server. Furthermore, QMDB introduces historical proofs, unlocking the ability to query its blockchain’s historical state at the latest block. QMDB not only meets the demands of current blockchains but also provides a robust foundation for building scalable, efficient, and verifiable decentralized applications across diverse use cases. ††footnotetext: https://github.com/LayerZero-Labs/qmdb††footnotetext: Copyright © 2024 LayerZero Labs Ltd. All rights reserved. 1 Introduction Updating, managing, and proving world state are key bottlenecks facing the execution layer in modern blockchains. Within the execution layer, the storage layer, in particular, has traditionally traded off performance (throughput) and decentralization (capital and infrastructure barriers to participation). Blockchains typically implement state management using an Authenticated Data Structure (ADS) such as a Merkle Patricia Trie (MPT). Unfortunately, typical MPT-based ADSes incur a high amount of write amplification (WA) with many costly random writes for each state update, which requires storing the entire structure in DRAM to avoid getting bottlenecked by the SSD. As a result, the performance and scaling of blockchains is I/O-bound, and the key to unlocking higher performance with larger datasets is to optimize the use of SSD IOPS more efficiently and reduce WA. We present Quick Merkle Database (QMDB), a resource-efficient SSD-optimized ADS with in-memory Merkleization that implements a superset of the app-level features of existing RocksDB-backed MPT ADSes with 6×6\times throughput on large datasets. Qmdb performs state reads with a single SSD read, state updates with O(1) IO, and performs Merkleization fully in-memory with no SSD reads or writes. These operations are theoretically optimal regarding disk IO complexity. Additionally, QMDB has a DRAM footprint small enough to run on consumer-grade PCs. Blockchain state storage is typically handled by an Authenticated Data Structure (ADS) which acts as a proof layer (e.g. Merkle Patricia Trie (MPT)) in combination with a physical storage layer. The proof layer efficiently generates inclusion and exclusion proofs against the world state, while the physical storage layer stores the actual world state keys and values. In many existing blockchains, these layers are each stored in a separate general-purpose key-value store such as RocksDB, resulting in duplicated data and general inefficiency. Storing a MPT (O⁡(log⁡N)O(\log N) insertion) in a general-purpose key-value store (O⁡(log⁡N)O(\log N) insertion) results in each state update incurring O⁡((log⁡N)2)O((\log N)^{2}) SSD IOs. QMDB eliminates this inefficiency by unifying the world state and Merkle tree storage, persisting all state updates in an append-only log, and eliminating all SSD reads and writes from Merkleization. By grouping updates into fixed-size immutable subtrees called twigs, QMDB can Merkleize state updates without reading or writing any world state; this essentially compresses the Merkle tree by several orders of magnitude, allowing it to be stored in a modest amount of DRAM. QMDB leverages typical blockchain workload characteristics to eliminate features commonly found in KVDBs—such as key iterations—thereby reducing performance bottlenecks. These optimizations enable QMDB to achieve 6×6\times throughput compared to RocksDB, a general-purpose key-value database that does not perform Merkleization. We also show that QMDB outperforms a prerelease version of NOMT, a state-of-the-art verifiable database, by up to 8×8\times. We validate QMDB’s scaling characteristics with experiments up to 15 billion entries (10X of Ethereum’s 2024 state size) and show it scales on both consumer-grade and enterprise-grade hardware. QMDB is a transformative improvement for blockchain developers, addressing today’s storage challenges and unlocking new possibilities for blockchain applications. In particular: 1) QMDB can serve massive workloads with the same amount of DRAM, allowing blockchains to handle more users and transactions; 2) Based on its low memory overhead per entry, QMDB can theoretically scale up to 280 billion entries on a single server, far exceeding any blockchain’s requirements today; and 3) QMDB can scale down to consumer-grade hardware, decreasing barriers to participation and improving decentralization. Figure 1: Entries are inserted sequentially into the leaves of the Fresh twig, and all leaves have the same depth. The twig eventually transitions into the Full state. As Entries are deleted, Full twigs become Inactive, then transition to Pruned. Upper nodes are recursively pruned after both of their children are pruned. 2 Background We explain the design of other verifiable databases and related data structures, including prior work reducing write amplification of verifiable databases [19, 13]. MPTs combine the efficient proof generation of the Merkle tree with the fast lookups of the Patricia trie and are a common choice for ADS on today’s blockchains [23]. In a database of N items, updating a single state entry in an MPT has a time complexity of O⁡(log⁡(N))O(\log(N)) [17]. However, MPT and other existing trie-based ADSes suffer from large proofs and a dependency on the client having a large amount of physical memory to avoid excessive random SSD reads. At the same time, MPTs are not suitable for storage on flash storage, as the randomly distributed update-heavy workload results in high WA. To top it off, the worst-case size for inclusion and exclusion proofs can be quite large. These factors result in Merkleization becoming a significant bottleneck that limits the overall throughput of the execution layer and the blockchain. AVL tree based ADSes are popular alternatives to MPTs, as they achieve faster updates, lookups, and proof generation due to the self-balancing AVL tree. The AVL tree is path-dependent, unlike the MPT, meaning its state root is influenced by the specific sequence of state change actions. AVL trees provide a marginal performance increase over MPTs in the average case, but still suffer from O(log N) tree nodes modifications per state update. LVMT [13] proposes a layered storage model to reduce the space and complexity of maintaining authenticated blockchain states. By partitioning the state into multiple segments and using cryptographic accumulators, it compresses less frequently accessed data while preserving verifiability. Proof generation becomes simpler, as intermediate accumulators shorten authentication paths. However, integrating multiple layers increases system complexity and demands careful configuration—suboptimal settings can lead to poor performance. Furthermore, LVMT depends on well-optimized cryptographic primitives. MoltDB [14] improves on existing two-layer MPT designs by segregating states by recency and coupling that with a compaction process. It reduces I/O and shows increased throughput of 30% over Geth. NOMT is a state-of-the-art ADS that uses a flash-optimized layout for a binary Merkle tree with compressed metadata, overcoming some limitations of existing MPT-based ADS implementations. NOMT implements an array of improvements including tree arity, flash native layout, a write-ahead log, and caching. This design results in better performance than existing solutions and has garnered interest in the space. However, NOMT remains an implementation-level optimization of MPT, offering only constant-factor reductions in disk I/O. It still faces inherent asymptotic limitations and write amplification issues. Additionally, it is affected by the key sparsity problem commonly observed in trie-based structures. Merkle Mountain Range (MMR) [22] enable compact inclusion proofs and are append-only, which makes the IO pattern for updating state conducive to efficient usage of SSD IOPS. Each MMR is a list of Merkle subtrees (peaks), and peaks of equal size are merged as new records are appended. MMRs are not suitable for live state management, as they cannot natively handle deletes, updates, lookups by key, and exclusion proof generation. As a result, MMRs have generally found success in their use for historical data management [18] where the key is just an index. Acceleration of Merkle tree computation has been an area of active research, with several proposed techniques such as caching [8, 5], optimizing subtrees [4], and using specialized hardware [12, 6]. These improvements are orthogonal to QMDB and could be applied to QMDB to further improve its performance and efficiency. Verifiable ledger databases are systems that allow users to verify that a log is indeed append-only, of which blockchains are a subset. A common approach to implementing a verifiable ledger database is deferred verification [25, 24, 3]. GlassDB [25] uses a POS-tree (a Merkle tree variant) as an ADS for efficient proofs. Amazon’s QLDB [2], Azure’s SQLLedger [3], and Alibaba’s LedgerDB [24] are commercially available verifiable databases that use Merkle trees (or variants) internally to provide transparency logs. VeritasDB [21] uses trusted hardware (SGX) to aid verification. The key difference between these databases and QMDB is that QMDB is optimized for frequent state updates and real-time verification of the current state (as opposed to verification of historical logs and deferred verification). Table 1: Fields in a QMDB entry. ID and Version are 8 bytes. Key has up to 282^{8} bytes and Value can hold up to 2242^{24} bytes. 3 QMDB Design QMDB is architected as a binary Merkle tree illustrated in Figure 1. At the top is a single global root that connects a set of shard roots, each of which represents the subtree of the world state that is managed by an independent QMDB shard. The shard root itself is connected to a set of upper nodes, which, in turn, are connected to fixed-size subtrees called twigs; each of these twigs has a root that stores the Merkle hash of the subtree and a bitmap called ActiveBits to track which entries are part of the most current world state. The twig root is determined by the sequence of entries, making it path-dependent. Entries (the twig’s leaves) are append-only and immutable, making it unnecessary to read or write the entry root during Merkleization; this results in QMDB only ever reading/writing the global root, shard roots, upper nodes, and twig roots during Merkleization. The twig essentially compresses the actual state keys and values into a single hash and bitmap, making the data required for Merkleization small enough to fit in a small amount of DRAM rather than being stored on SSD. In this section we begin by explaining the underlying storage primitives used to organize state data (Section 3.1), followed by a discussion of the indexer in Section 3.2. In Section 3.3 we describe the high-level CRUD interface exported by QMDB to clients. In Section 3.4 we describe how the storage backend and indexer facilitate generation of state proofs, and discuss how these state proofs can be statelessly validated. Finally, in Section 3.5 we explain how QMDB takes advantage of additional optimizations such as sharding and pipelining to scale throughput via improved parallelism. 3.1 Entries and Twigs The entry (Table 1) is the primitive data structure in QMDB, encapsulating key-value pairs with the metadata required for efficient proof generation. Entries can be extended to support features such as historical state proof generation (Section 3.4). QMDB keys entries by the hash of the application-level key, resulting in improved load balancing via uniform key distribution across shards (Section 3.5) Table 2: As twigs progress through their lifecycle, their footprint in DRAM gets smaller. An inactive twig has 99.9% smaller memory footprint than a full twig. Twigs are subtrees within QMDB’s Merkle Tree; each twig has a fixed depth, by extension a fixed number of entries stored in the leaf nodes of the same depth (2048 in our implementation). A set of upper nodes connects all twigs to a single shard root, with null nodes to represent uninitialized values; these upper nodes are immutable once all their descendant entries have been initialized. In addition to the actual Merkle subtree, Twigs also store the Merkle hash of their root node and ActiveBits, a bitmap that describes whether each contained entry contains state that has not been overwritten or deleted. The twig essentially compresses the information required to Merkleize 2048 entries and their upper nodes (≥256​k​b\geq 256kb) into a single 32-byte hash and a 256-byte bitmap (99.9% compression). This compression is the key to enabling fully in-memory Merkleization in QMDB. Fresh twigs reside completely in DRAM, and entries are sequentially inserted into its leaf nodes. Once a twig reaches 2048 entries, its contents are asynchronously flushed to SSD in a large sequential write and deleted from DRAM, maximizing SSD utilization and minimizing DRAM footprint. Each twig follows a lifecycle of 4 states: Fresh, Full, Inactive, and Pruned (Table 2). An example of the layout of QMDB’s state tree is presented in Figure 1 There is exactly one fresh twig per shard, and entries are always appended to the fresh twig. After all entries in the twig are marked inactive as a result of update and delete operations, the twig transitions into the inactive state before eventually being pruned and replaced by the Merkle hash of the root. Upper nodes that contain only pruned twigs are recursively pruned, further reducing the memory footprint of QMDB; a dedicated garbage collection thread duplicates old valid entries into the fresh twig, reducing fragmentation and allowing larger subtrees to be pruned. In theory, once the entire subtree originating at a child of the shard root is pruned, the root itself can be pruned to reduce the depth of the tree by one. The grouping of entries into twigs reduces the DRAM footprint of QMDB to the degree that all nodes affected by Merkleization can be stored in a small amount of DRAM. In a hypothetical scenario with 2302^{30} entries (approx. 1 billion), the system must keep at most 2192^{19} (2302048\frac{2^{30}}{2048}) 288-byte (32-byte twig root hash & 2048-bit ActiveBits bitmap) full twigs, 1 fresh twig and 219−12^{19}-1 32-byte (node hash) upper nodes totaling around 160 megabytes. In practice, the majority of the 2192^{19} twigs will be pruned, resulting in the average size being much smaller. Inactive and Pruned twigs cannot be modified, and thus do not require further Merkleization. Fresh and Full twigs must be Merkleized every time the ActiveBits bitmap is changed, and Fresh twigs must additionally be Merkleized every time an entry is added. The upper nodes of the Merkle tree are recomputed on startup and are never persisted to SSD–this recomputation requires reading all twig hashes from SSD and performing 2 hashes per twig, and can be completed in a matter of milliseconds for the previous example of 1 billion entries. QMDB stores an entry every time state is modified, making the state tree grow proportionally to the number of state modifications. To combat this tree growth, a dedicated compaction worker periodically compacts QMDB’s state tree by removing and re-appending old entries to the fresh twig, accelerating the progression of the twig lifecycle and allowing more subtrees to be pruned. The compaction logic must be deterministic when used in a consensus system or for stateless validation. The current implementation ensures that the active entry ratio per shard remains above a predefined threshold, triggering compression during updates and insertions. QMDB’s Merkle proof size and proof generation complexity grow proportionally to log⁡(U)\log(U) of the number of state updates (UU) rather than the number of unique keys (KK) due to its append-only nature. However, the ratio of UU to KK remains small enough that the order-of-magnitude improvement in Merkleization performance dominates the small additional cost. Assuming 10,000 transactions per second and an average of 5 KV updates per transaction, the tree depth after one year will be at most 41 (l​o​g​2​(10000∗5∗3600∗24∗365)log2(10000*5*3600*24*365)); however, in practice the actual depth will be much shallower due to pruning of overwritten subtrees and garbage collection. In addition, ZK-proofs can be used to compress the proof witness data which drastically reduces proof verification cost, avoiding end-to-end bottlenecks in the proof size. 3.2 Indexer The indexer maps the application-level keys to their respective entries, enabling QMDB’s CRUD interface. To support efficient insertion and deletion of entries (Section 3.3), the indexer must support ordered key iteration. The indexer can be freely swapped for different implementations depending on specific application needs, but we expect that QMDB’s default in-memory indexer will meet the resource requirements of the majority of use cases. This modularity potentially enables optimizations to increase the performance or memory efficiency of the indexer such as those found in systems such as SILT [15] or MICA [16]. QMDB’s default indexer consumes approximately 15.4 bytes of DRAM per key and serves key lookups in-memory to minimize SSD I/Os. This efficiency is achieved by using only the 9 most significant bytes of each key, which slightly increases the likelihood of key collisions but strategically trades worst-case performance for reduced DRAM usage. Of these 9 bytes, the first 2 bytes serve as the sharding key for the indexer, leaving a 7-byte memory footprint for key storage. The remaining 8.4 bytes consist of a 6-byte SSD position offset and additional data structure overhead, which is amortized across all keys. Using just 16 gigabytes of DRAM, the in-memory indexer can index more than 1 billion entries, making it suitable for a wide range of applications. We chose the B-tree map as the basis for the underlying structure of QMDB’s default indexer to take advantage of B-tree’s high cache locality, low memory overhead, support for ordered key iteration, and graceful handling of key collisions. We use fine-grained reader-writer locks (determined by the first two bytes of the key hash) to minimize contention when updating entries. 3.3 CRUD interface QMDB exposes a CRUD (Create, Read, Update, Delete) interface, and in this section we provide a high-level overview of how each operation is implemented. In all examples, we present the operation of the system when using the default in-memory indexer; other indexers may require more reads or writes to serve the same workload. For each operation, we present an intuitive explanation followed by a more formal description along with a description of the SSD I/O required to synchronously handle the request. All writes in QMDB are buffered in twigs (DRAM) and persisted to SSD in batches, so each SSD write is amortized across 2048 entries; to precisely express the cost of each operation, we refer to a entry write as 12048\frac{1}{2048} of a single batched flush to SSD. For brevity, we omit the Id, Version, and Value fields when describing new entries (see Table 1), so an entry EE is defined as: E=(K​e​y,N​e​x​t​K​e​y,O​l​d​I​d,O​l​d​N​e​x​t​K​e​y​I​d)E=(Key,~NextKey,~OldId,~OldNextKeyId) Read begins by querying the indexer for the file offset of the entry corresponding to a given key; this file offset is used to read the entry in a single SSD IO. Update first reads the most current entry for the updated key, then appends a new entry to the fresh twig. More formally, if EE is the most current entry, the new entry E′E^{\prime} appended to the fresh twig derives its OldId and OldNextKeyId from EE as follows: E′=(K,E.nextKey,E.Id,E.OldNextKeyId)E^{\prime}=(K,~E.nextKey,~E.Id,~E.OldNextKeyId) Updating a key in QMDB incurs 1 SSD read and 1 entry write. Create intuitively involves appending one new entry and updating one existing entry; the existing entry whose Key and NextKey define a range that coincides with the created key must be updated with a new NextKey. This begins by first reading the entry EpE_{p} corresponding to the lexicographic predecessor (p​r​e​v​K​e​yprevKey) to the created key KK. Note that EpE_{p} must fulfill the condition Ep.K​e​y>> Additionally, QMDB has a DRAM footprint small enough to run on consumer-grade PCs.