Markdown source for agents: https://npub1d70emggs6jzun5lhvqnfqsd9reqmaarn2qjf6q3r02gryyl4v8sqjn44xe.nsite.lol/docs/patterns/merkle-ots-extension.md

Nostr Agent Onboarding · start here · index · source: nostr-dev/docs/patterns/merkle-ots-extension.md · snapshot 2026-10-10

Paths such as ~/Documents/…, ~/Production Environment/…, repos/… and services on localhost refer to the author's workstation and are not available to you — read them as worked examples of a setup you can recreate.

Pattern: OpenTimestamps Merkle-extends-downward

Source: designed and verified end-to-end in ~/work/nostr-archive/docs/ots-proofs.md. The test harness that used to sit at ~/work/nostr-archive/tests/ots-extension/ is gone as of 2026-09-21 — the algorithm below is still correct, but the reference implementation is not on this machine any more; pipeline/nap/ots.py and client/js/ots.js in that repo are the surviving code. Verified against both python-opentimestamps and github.com/fiatjaf/ots for leaf-set sizes {1, 2, 3, 5, 8}. Property holds.

This document generalizes the primitive away from archives. It applies to anything that needs shared Bitcoin time-attestation across a set of related digests.

The primitive

You have N sha256 digests (files, blob hashes, signed-event ids, arbitrary content) that you want Bitcoin-anchored timestamps on. Naïve approach: stamp each with OpenTimestamps individually, get N .ots files. Cost: N rounds of calendar-server interaction, eventually N Bitcoin block confirmations to pay attention to.

Better approach: stamp once over a Merkle root of all N, and derive per-leaf .ots proofs that verify with stock OpenTimestamps tooling.

Cost: 1 calendar interaction, 1 Bitcoin block, and a small piece of client-side surgery to extend the proof down to a chosen leaf.

Why the construction works

The OpenTimestamps "virtual machine" expresses each Merkle step as two ops: OpAppend(sibling) (or OpPrepend(sibling)) followed by OpSHA256. These are exactly the operations a calendar's own aggregation tree uses. So a bundle's Merkle layer is just an extra aggregation level below the calendar's — indistinguishable in form. Concatenating your bundle's Merkle path to the front of an OTS file's operation chain yields a single uninterrupted operation sequence from leaf to Bitcoin block header.

The only design constraints that matter:

  1. Internal node = sha256(left || right). No length prefix, no leaf-tag byte, no domain separation.
  2. Tree shape: bottom-up, with odd nodes carried up unchanged (not duplicated as in Bitcoin's coinbase tree). An odd carry-up is a no-op at that level; the node is paired one level higher. This is the calendar's convention.
  3. For n = 1, the root is the leaf itself with no SHA-256 applied.

If you do those three things, an OTS proof over the root extends to any leaf with stock-format output. If you violate any of them, the extension still composes mathematically but the resulting .ots file is non-standard and stock ots verify won't accept it.

When to use this

This is a generic primitive. Some places it earns its keep:

Sketch in pseudocode

Tree build (deterministic; lex-sort by hex digest):

def build_root(leaves: list[bytes32]) -> bytes32:
    assert len(leaves) >= 1
    level = sorted(set(leaves))
    while len(level) > 1:
        next_level = []
        for i in range(0, len(level) - 1, 2):
            next_level.append(sha256(level[i] + level[i+1]))
        if len(level) % 2 == 1:
            next_level.append(level[-1])     # odd carries up unchanged
        level = next_level
    return level[0]

Per-leaf proof extraction:

def extract_leaf_proof(leaves, target, bundle_ots_bytes) -> bytes:
    # Walk from `target` up to root, recording (sibling_digest, side)
    # at each pairing step. Concatenate the resulting ops in front of
    # the existing OTS operation chain. The output deserializes as a
    # standard .ots file.
    ...

Reference impls of the OTS surgery exist in python-opentimestamps (Timestamp.merge, direct op-list manipulation) and in ots-rs (operation-chain access). The archive project has a working Python implementation, formerly at ~/work/nostr-archive/tests/ots-extension/extend.py (removed; see the note at the top).

Verification (any consumer)

The leaf and a derived .ots proof are sufficient input:

ots verify --digest <leaf-hex> leaf.ots
# or, if you have the bytes:
ots verify leaf.ots --file leaf-content.bin

The verifier walks: leaf → (your appended Merkle ops) → bundle root → (calendar's aggregation ops) → Bitcoin block header → block height + timestamp. Stock client; no special tooling.

"Earliest timestamp wins" for federated content

If the same digest appears in multiple bundles by different curators, you can have multiple valid OTS proofs for it. The canonical time is the earliest Bitcoin block height across all valid proofs. Verifiers MUST take the minimum, not the most recent or most accessible.

This composes naturally because:

The corollary: a re-archiver MAY carry forward an earlier curator's per-leaf proof rather than re-stamping. The original timestamp survives the re-curation, so provenance is preserved.

Tooling on this machine

What the OTS proof does NOT prove