Will's blog


Merkle trees and build systems

28 May 2020

An article written by my colleague David Röthlisberger in part describing how the build system that we built at stb-tester works and the philosophy behind it: Merkle trees and build systems.

In traditional build tools like Make, targets and dependencies are always files. Imagine if you could specify an entire tree (directory) as a dependency: You could exhaustively specify a “build root” filesystem containing the toolchain used for building some target as a dependency of that target. Similarly, a rule that creates that build root would have the tree as its target. Using Merkle trees as first-class citizens in a build system gives great flexibility and many optimization opportunities. In this article I’ll explore this idea using OSTree, Ninja, and Python.