Thread by @tarides_

We’re excited to contribute an important feature to the next #Tezos protocol proposal: first-class _sub-trees_ of the blockchain context. 🌲

This feature has an interesting #OpenSource #OCaml history, dating back to before Tezos was born. A thread 🧵. (1 / N)

The Tezos protocol runs on top of a versioned tree called the “context”, which holds the chain state (balances, contracts etc.).

Ever since pre-Alpha, the context has been implemented using Irmin – a Merkle tree database written for OCaml #MirageOS kernels. (2 / N)

For MirageOS, Irmin’s key strength is flexibility: it can run over arbitrary backends. A perfect fit for Tezos, which must be agile & widely-deployable.

Tezos has already leveraged this many times, all the way from initial prototypes using a Git backend to irmin-pack. (3 / N)

But Irmin can do more than just swapping backends! It also allows users to reason about the underlying Merkle trees in the store.

This “Tree” API enables lots of interesting use-cases for Irmin, from mergeable data types (MRDTs) to zero-knowledge proofs. (4 / N)

Tezos doesn’t use these powerful features directly yet; that’s where Merkle proofs come in!

Merkle trees have a neat feature: individuals only need a _fragment_ of the tree, provided they can show this fragment is valid by sending “proofs” to the other participants. (5 / N)

This can be used to support ultra-light Tezos clients with minimal storage requirements – a feature currently being developed by @smelc3 of @TweagIO. (gitlab.com/smelc/tezos/-/…).

To make this a reality, the Tezos protocol needs fine-grained access to context sub-trees … (6 / N)

… in order build Merkle proofs out of them. Fortunately, Irmin already supports this! We extended the protocol to understand sub-trees (gitlab.com/tezos/tezos/-/…), lifting the power of Merkle trees to the user.

This will be part of the next Tezos proposal, coming soon! (7 / N)

We’re excited to work with @TweagIO and @LabosNomades on lowering the barriers to entering the Tezos ecosystem & look forward to seeing what they achieve with sub-trees!

Understanding sub-trees isn’t all: light clients will also need to _serialize_ them efficiently, … (8 / N)

… since proofs must be exchanged over the network between collaborating nodes. Enter Plebeia (dailambda.jp/blog/2020-05-1…),

Plebeia is an alternative Tezos storage layer – developed by @DaiLambda – with strengths that complement those of Irmin. (9 / N)

In particular, Plebeia can generate very compact Merkle proofs. This is partly due to its specialized store structure, and partly due to clever optimizations (e.g. path compression, inlining).

Like Irmin, Plebeia has efficient sub-tree support, meaning it can take … (10 / N)

… advantage of our recent additions to the protocol – thanks to @camlspotter for his help honing the API.

We’re working with the @DaiLambda team to unite the strengths of Irmin and Plebeia. The future is bright for Merkle proofs in Tezos! (11 / N)

Trees don’t just enable _new_ features; they’ll have a big impact on performance too!

Currently, indexing into the context always happens from its _root_, which duplicates effort when accessing adjacent values deep in the tree. Fortunately, the new sub-trees provide … (12 / N)

… a natural representation for “cursors” into the context, allowing the protocol to optimize interactions with the storage layer.

To take one example, @DaiLambda exploited this feature to reduce the migration time of Baking Accounts by 10x! (13 / N)

gitlab.com/tezos/tezos/-/…

We’ll be teaming up with @LabosNomades, @DaiLambda and the @TezosFoundation to ensure that Tezos extracts every bit of performance from its storage.

It's especially exciting to have lightning-fast migrations, since this enables Tezos to evolve even more quickly. (14 / N)

Of course, the storage layer isn’t just an #OCaml project: Tezos also has a performant #Rust context as part of TezEdge (github.com/simplestaking/…).

We’re working with @SimpleStaking to bring Irmin to the Rust community, building on the FFI toolchain begun by @zachshipko. (15 / N)

All in all, it’s an exciting time to work on #Tezos storage, with many #OpenSource collaborators from around the world.

We’re especially happy to see Tezos taking greater advantage of Irmin’s features, which will strengthen both projects and help them grow together. (16 / N)

If all of this sounds interesting, you can play with it yourself using the recently-released Irmin 2.4.0 (github.com/mirage/irmin/).

We’ll be covering the technical details of the Irmin sub-tree implementation in an upcoming blog post. Stay tuned!

(17 / N, N = 17)