DEOS Receipt Log — Merkle Mountain Range v1

Status: v1.0 — published 2026-05-02 Spec URI: https://projectmaya.deoscomputing.io/merkle/log/v1 Maintainer: DEOS Computing (did:web:deos.computing) Reference impl: Rust crate + CLI in DEOS Computing's working repo (access-controlled during v1 alpha).

The receipt log is an append-only, tamper-evident Merkle Mountain Range keyed by canonical receipt bytes. Each appended receipt becomes a leaf; whenever the right edge of the structure has two adjacent same-height nodes they are merged into a parent. The root of the log is the bagged hash of the resulting peaks, mixed with the leaf count.

This document is normative for v1.

1. Why MMR

A flat Merkle tree requires the size to be known up front, or pads to the next power of two and rewrites the structure when it grows. An MMR appends in amortized O(log n) work per leaf, produces O(log n) inclusion proofs, and never rewrites past nodes — a property that maps cleanly onto persistent CAS.

Receipts can therefore be added one at a time, with each append producing a new root that is committed (and eventually anchored externally in M5).

2. Hash domain separation

All hashes are BLAKE3-256. Every hash computation uses one of four domain tags to prevent cross-context collisions:

Tag Used for
b"deos-mmr-leaf-v1:" Hashing leaf data (canonical receipt bytes)
b"deos-mmr-node-v1:" Hashing two children into a parent internal node
b"deos-mmr-bag-v1:" Bagging two peaks
b"deos-mmr-root-v1:" Final root: tag || leaf_count_be || bagged_peaks 
leaf_hash    = BLAKE3(LEAF_TAG || leaf_data)
parent_hash  = BLAKE3(NODE_TAG || left_child || right_child)
bag(L, R)    = BLAKE3(BAG_TAG || L || R)
root         = BLAKE3(ROOT_TAG || u64_be(leaf_count) || bagged_peaks)

3. Node positions

Nodes are stored in append order. Position numbering is 1-based in the spec; the reference impl uses 0-based indices internally.

The 1-based MMR position of leaf i (0-based leaf index) is:

leaf_position(i) = 2*i + 1 - popcount(i)

Examples (1-based positions): leaf 0 → 1, leaf 1 → 2, leaf 2 → 4, leaf 3 → 5, leaf 4 → 8, leaf 7 → 12, leaf 8 → 16.

4. Append algorithm

append(leaf_data):
    h = leaf_hash(leaf_data)
    push h
    merges = trailing_zeros(leaf_count + 1)        # number of merges to perform
    height = 0
    while height < merges:
        sibling_pos = current_pos - (2^(height+1) - 1)  # 1-based
        parent = node_hash(nodes[sibling_pos], nodes[current_pos])
        push parent
        height += 1
    leaf_count += 1
    return (leaf_count - 1, compute_root())

Append is deterministic: given the same sequence of leaves, the resulting nodes vector and root are byte-identical across implementations.

5. Root computation

compute_root():
    if leaf_count == 0:
        return ZERO_HASH
    peaks = peaks_for(leaf_count)              # left-to-right, highest first
    acc = nodes[peaks.last().pos]
    for peak in peaks reversed (skipping last):
        acc = bag(nodes[peak.pos], acc)        # right-to-left fold
    return BLAKE3(ROOT_TAG || u64_be(leaf_count) || acc)

peaks_for(L) returns one peak per set bit in L. The leftmost peak corresponds to the highest bit and the largest perfect-tree subtree.

6. Inclusion proofs

A proof for leaf i in a log of leaf count L consists of:

{
  "leaf_index": <u64>,
  "leaf_count": <u64>,
  "siblings": ["<hex>", ...],         // h hashes, one per height up to the leaf's peak
  "bag_peaks_left": ["<hex>", ...],   // peaks left of the leaf's peak (left-to-right)
  "bag_peaks_right": ["<hex>", ...]   // peaks right of the leaf's peak (left-to-right)
}

6.1 Generating

Walk from leaf_position(i) upward to the peak that contains it. At each height h, bit (i >> h) & 1 decides whether the leaf is a left or right descendant; the sibling at the same height is at:

Push that sibling's hash into siblings. Move current_pos to the parent position.

The other peaks (everything except the one we walked to) become bag_peaks_left and bag_peaks_right.

6.2 Verifying (standalone)

The verifier needs only the leaf bytes, the proof, and the published root — no log state.

verify(leaf_data, proof, root):
    h = leaf_hash(leaf_data)
    for level, sibling in enumerate(proof.siblings):
        bit = (proof.leaf_index >> level) & 1
        h = node_hash(h, sibling) if bit == 0 else node_hash(sibling, h)
    all_peaks = proof.bag_peaks_left + [h] + proof.bag_peaks_right
    if len(all_peaks) != popcount(proof.leaf_count): reject
    acc = all_peaks[-1]
    for peak in all_peaks[:-1] reversed:
        acc = bag(peak, acc)
    return BLAKE3(ROOT_TAG || u64_be(proof.leaf_count) || acc) == root

7. Snapshot format (on-disk persistence)

The log persists across restarts as a single binary blob:

offset  size  field
------  ----  -----
0       8     magic = b"DMMR0001"
8       8     leaf_count        (u64, big-endian)
16      8     node_count        (u64, big-endian)
24      32*N  nodes             (concatenated 32-byte hashes)
24+32N  32    integrity         (BLAKE3 over the preceding bytes)

On read: verify magic; read counts; read node hashes; verify integrity checksum. Mismatch is a fatal error — the log MUST NOT be loaded silently under corruption.

The reference impl writes via <path>.tmp + atomic rename to avoid torn writes.

8. CLI

# Initialize an empty log on disk.
receipt-canon log init <log.bin>

# Append a receipt (canonical bytes are the leaf payload).
# Prints {"leaf_index","leaf_count","root"} as JSON.
receipt-canon log append <log.bin> <receipt.json>

# Print {"leaf_count","root"} for the current log.
receipt-canon log root <log.bin>

# Emit a JSON inclusion proof for the given leaf index.
receipt-canon log prove <log.bin> <leaf_index>

# Standalone verification: succeeds with exit 0, fails with exit 1.
receipt-canon log verify <receipt.json> <proof.json> <root-hex>

9. Integration with the substrate

The reference MMR is std-only and standalone. A substrate integrates it by:

  1. Serving GET /attestation/v1/log/<root> and GET /attestation/v1/receipt/<id> from the attestation API (/attestation/api/v1).
  2. Persisting the log under content-addressed storage. Each appended receipt is blob-stored and indexed by receipt id so attestation requests can re-fetch the original receipt and produce a fresh inclusion proof.
  3. Anchoring the root to OpenTimestamps every N receipts (see /anchor/v1).

The on-disk snapshot format from §7 is the same format DEOS Computing's reference substrate uses internally; the blob lives in the persistent CAS partition.

10. Performance (informational)

Reference-impl numbers on macOS arm64 (M-series), release build:

11. Beyond v1

12. Maintainer

DEOS Computing — design questions, conformance reports, and proposed additions to github.com/DEOS-Computing.

License: CC BY 4.0 (text), Apache-2.0 (reference code).