Merkle DAGs

Every module’s version is committed by a single Merkle root. The layout is RFC 9162 over lexicographically sorted leaves:

from boltzmann.merkle import LAYOUT_NAME

LAYOUT_NAME
# 'rfc6962-sorted/1'

Two decisions, each closing something the paper leaves open:

Sorting makes the root a pure function of the set of blocks, so two parties that assembled the same knowledge in different orders agree.
The Merkle Tree Hash of RFC 9162 §2.1.1 avoids the duplicate-leaf ambiguity a naive tree admits (CVE-2012-2459), by splitting at the largest power of two below n and hashing leaves and internal nodes under different prefixes.

Why the identifier still says rfc6962. RFC 9162 obsoletes RFC 6962 and defines the same tree — same empty hash, same 0x00/0x01 prefixes, same split — so no root changes when the citation moves. The identifier names the construction, not the document that describes it, and renaming it would announce a change of tree where none happened. It would also be a hard break: a client refuses a composition whose layout it does not implement, so every published brain would stop opening. The /1 suffix is what moves if the construction ever does.

Internal nodes are derived, not stored. A module with no blocks still has a well-defined root: SHA-256(""), which is MTH({}) in §2.1.1.

Computing a root

from boltzmann.merkle import MerkleTree, merkle_root, sorted_leaves

merkle_root([c, a, b]) == merkle_root([a, b, c])   # True -- order does not matter

tree = MerkleTree([a, b, c])
tree.root
tree.name                      # 'rfc6962-sorted/1'
tree.index_of(b)               # position among the sorted leaves
tree.verify()                  # recompute every leaf's proof against the root

Inclusion proofs

Membership is provable in O(log n), without holding the rest of the module. Verification follows RFC 9162 §2.1.3.2, which is where the algorithm is actually written down — RFC 6962 defined the proof and left verification to the reader.

proof = brain.prove(block_id, MemoryType.SEMANTIC)

proof.block_id
proof.leaf_index
proof.tree_size
proof.audit_path               # the sibling hashes needed to recompute the root

proof.verify(root)             # -> bool
proof.require(root)            # raises InclusionProofError instead of returning False

A proof binds a block to one composition, not to any composition: verifying it against a different root fails. That is what makes a root a version identifier rather than a checksum.

Swapping the layout

MerkleLayout is a protocol, so a deployment can commit to a different tree — but both sides must agree, which is why the layout name travels in every ModuleRef.

from boltzmann.merkle import DEFAULT_LAYOUT, MerkleLayout, SortedRfc9162Layout

class MyLayout:
    @property
    def name(self) -> str: ...
    def root(self, block_ids) -> MerkleRoot: ...
    def inclusion_proof(self, block_ids, target) -> InclusionProof: ...

assert isinstance(MyLayout(), MerkleLayout)

Two implementations can only compare roots if they agree on the layout. A ModuleRef records layout for exactly that reason — a root computed under another layout is not a smaller or larger number, it is a different question’s answer.

Diffing two versions

What a consumer must fetch to move between versions falls out of the composition, with no server-side computation:

from boltzmann.merkle import diff

d = diff(before_ids, after_ids)

d.before, d.after              # the two roots
d.added, d.removed, d.unchanged
d.transfer_size                # how many blocks a consumer must fetch
d.is_empty                     # whether the two compositions are identical

This is the mechanism behind an incremental update: the layers whose root did not change are reused by digest rather than transferred again.

Getting started

Core concepts

Guides

Computing a root

Inclusion proofs

Swapping the layout

Diffing two versions

​Computing a root

​Inclusion proofs

​Swapping the layout

​Diffing two versions

Computing a root

Inclusion proofs

Swapping the layout

Diffing two versions