QMDB All The Things

Over the last year, we've developed a family of append-only, authenticated databases (ADB) inspired by LayerZero's novel Quick Merkle Database (QMDB). Today, we are excited to announce that this family of databases will now be known as QMDB and that we are collaborating with LayerZero to productionize QMDB in the Commonware Library.

When I first learned about QMDB, I was blown away. Through my work on Vilmo, I had already concluded that append-only databases were the path to a new factor of throughput but had yet to figure out how to add efficient authentication (the ability to prove some key exists in some root at some time, or doesn't). I found a way to enable “state sync” but gave up on an efficient lite client.

Figure 1: Vilmo provides state sync through a fixed set of rotating WALs. Once a node has the last k rotations, they have the current state.

With QMDB, researchers at LayerZero found an (elegant) solution to authentication by layering a Merkle Mountain Range (MMR) over a log of key updates. By linking keys in lexicographic order, this log can generate exclusion proofs (provide an inclusion proof of the keys before and after). Because the root spans the entire log, proofs for any key can be verified against the current root. Merklization can be performed with little memory and no disk access because new operations exclusively modify the right side of the tree.

Figure 2: Over an ever-growing log of linked key operations, QMDB builds a Merkle Mountain Range (MMR).

QMDB can “do it all” (inclusion and exclusion proofs over both current and historical state). At Commonware, however, we found a number of applications that didn't need to. Rather than requiring all applications to support all proof types, we opted to instead build our own family of MMR-over-log databases (ADB) with granular control over proof support. The simplest database you need, for example, only supports inclusion proofs!

This family of databases, however, never diverged far from QMDB. We found coherent ways to break apart QMDB and introduced support for state sync but never departed from the core MMR-over-log abstraction (we couldn't find a way to do better). After discussion with LayerZero, we both determined that instead of building our own versions of QMDB that we should direct our work towards a single implementation that we could both optimize. We're excited to share that single point of focus will be our family of authenticated databases, now renamed to QMDB. And yes, it is licensed as MIT/Apache-2.

Learn more about QMDB and its industry-leading performance on arXiv. Play around with the rapidly maturing implementation of QMDB in the Commonware Library.