Data Structure

Overview

Abstractly, Witness's core state can be modeled as a single ever-growing merkle tree. While merkle trees are a very common data structure used throughout the blockchain space, Witness's merkle tree is a unique flavor called a merkle mountain range (MMR) which affords it some unique properties.

While this section will explain a few specific aspects of MMRs, we recommend consulting these external resources for a deeper and more rigorous dive into MMRs and how they work:

Properties of MMRs

Interval proofs

MMRs allow for efficient proofs of the inclusion of a given interval of leaves for a given tree root. This proof is exactly the minimal set of nodes required to express the sections of the tree not covered by the target interval.

For example, for a tree of size N, the proof of the interval [0, a) would be exactly the minimal set of internal nodes needed to express the interval [a, N).

An interval of a single element can be expressed as a single leaf node.

Consistency proofs

Consistency proofs are a unique type of interval proof. Suppose we have a tree of size N, and we want to update the tree to size M > N, but we want to ensure that the elements expressed by the original tree remain consistent in the new tree. A consistency proof achieves this by proving the interval [0, N), which make up the entirity of the original tree, are still included in the correct positions in the new tree. The new tree's interval, [N, M), is included as the complementary portion of the consistency proof.

Mergable ranges

Suppose we have a proof of an element at index L being in the tree at size N. My proof for this element's inclusion consists of the intervals [0, L), [L, L+1), and [L+1, N). The second interval is just the leaf we want to prove, while the other intervals cover the rest of the tree. By combining the hashes of these intervals, we can get the root of the tree at size N.

Now suppose the tree updates with a consistency proof transitioning to size M. If I want to update my proof to roll up to the new tree root at size M, MMRs allow this by merging the interval covered by the consistency proof with the existing proof. Specifically interval [L+1, N) can be merged in with the [N, M) to become [L+1, M). This new interval can be used to prove the element at index L is included in the tree at size M.

Results for Witness

Succinct consistency

For a client that has some view of Witness at a size N, they can update their view to a size M > N with confidence in the new root's consistency with the previous root by requesting a consistency proof. No matter the size of the interval M - N, this proof will be succinct to verify. This provides a very "light" way for clients to maintain a valid view of Witness, through which to verify proofs.

The canonical use of this is in the Witness smart contract on mainnet Ethereum; when updates are made to the tree, a consistency proof verifies the new root's consistency with the previous root.

Updateable proofs

Thanks to mergeable ranges in MMRs and the fact that both consistency proofs and inclusion proofs are made of ranges, any proof targetting a particular tree size can be updated to point to a new greater tree size by merging proof with the consistency proof for the new tree size.

This means that a client can maintain an inclusion proof rolling up to the most recent root posted onchain by persistently updating their proof with the posted consistency proofs as the root updates.

Statelessness

While the current version of Witness's onchain checkpointer retains all historical roots, thanks to the dynamics around consistency proofs and updateable inclusion proofs, Witness can credibly shave down its onchain footprint to a constant amount of state.

Witness also lends itself very well to content-based and DHT-backed schemes for retrieval of proofs, due to the immutability of nodes in the MMR data structure as it grows.

While not a short-term priority, exploring these directions over time will help make Witness more scalable and sustainable in the long term.

Nesting

Clients aren't limited to checkpointing items directly into Witness; they can also checkpoint a merkle root of a subtree of items. Sophisticated clients can take advantage of this pattern of nesting to do things like locally maintain provenance for many pieces of data in a local MMR that gains onchain provenance in a single batch when the root is submitted to Witness.

ConceptsProvenance