MMR Transparency v1.1 Specification

Status: v1.1 — drafted 2026-05-05 Spec URI: https://projectmaya.deoscomputing.io/mmr/transparency/v1 Maintainer: DEOS Computing (did:web:deos.computing) Companions: /merkle/log/v1, /interop/scitt/v1

A v1.0 substrate is structurally a trusted third party: it publishes a Merkle root, but nothing prevents it from publishing root R1 to one verifier and root R2 — where R2 is not a forward-extension of R1 — to another. This document specifies the v1.1 mechanisms that make substrate equivocation detectable: consistency proofs between two observed roots, a gossip protocol for cross-verifier comparison, fork detection, and a log-of-logs cross-witnessing pattern.

1. Goals

A v1.1 substrate's MMR must support:

1. Consistency proofs between any two roots R1 (at leaf count N1) and R2 (at leaf count N2 ≥ N1). A verifier given R1, R2, and the proof confirms that R1 is a forward-prefix of R2 — i.e. that no leaves below position N1 have been rewritten.
2. Witness-driven gossip so that verifiers comparing notes detect a substrate showing different roots to different parties.
3. Fork detection as an automatic action: when gossip reveals two non-extending roots, the verifier flags the substrate as compromised and refuses further trust.
4. Cross-substrate witnessing via a log-of-logs: a meta-substrate that periodically commits to each member substrate's tree head, providing third-party-attested evidence of every substrate's history at every observed point.

A v1.1 substrate is not required to:

• Implement BFT consensus across substrate replicas (deferred to v2).
• Anchor every gossip event in Bitcoin (the OTS chain provides offline-verifiable timestamping; gossip provides equivocation detection).

2. Consistency proofs (MMR1.1-2)

2.1 Construction

For an MMR with new_count leaves, a consistency proof to a smaller old_count (where 0 < old_count ≤ new_count) consists of:

pub struct ConsistencyProof {
    pub old_count: u64,
    pub new_count: u64,
    /// Hashes of all peaks in the OLD tree. The verifier reconstructs
    /// R1 by bagging these.
    pub old_peak_hashes: Vec<Hash>,
    /// Sibling hashes needed to walk each old peak forward through
    /// the new tree to the new peaks. Encoded in the order they're
    /// consumed during the merge walk.
    pub extra_nodes: Vec<Hash>,
}

The substrate generates the proof by (a) computing the peaks of the old tree from the new tree's nodes (peaks at old_count are well-defined positions in the post-order layout), and (b) walking each old peak forward to identify the sibling subtree it merges with in the new tree, recording each sibling's hash.

2.2 Verification

Input:  old_root, new_root, proof
Output: bool (true iff old is a prefix of new)

1. Reconstruct R1: bag proof.old_peak_hashes left-to-right.
   If hash_root(bagged, proof.old_count) != old_root → reject.
2. Walk forward through new tree:
   a. Identify peaks of size proof.new_count.
   b. For each old peak that merged into a larger new peak,
      consume one extra_node as the merge sibling and recompute
      the merged-peak hash.
   c. For each old peak that survived unchanged, it must appear
      verbatim in the new peaks at its expected position.
3. Bag the recomputed new peaks.
   If hash_root(bagged, proof.new_count) != new_root → reject.
4. Return true.

The proof size is O(log new_count) in the typical case. Pathological cases (highly fragmented old trees) approach O(log² new_count).

2.3 New endpoint

GET /attestation/v1/consistency?from={old_count}&to={new_count}

Returns:

{
  "old_count": 100,
  "old_root": "<hex>",
  "new_count": 250,
  "new_root": "<hex>",
  "proof": {
    "old_peak_hashes": ["<hex>", "<hex>", ...],
    "extra_nodes": ["<hex>", ...]
  }
}

Verifiers fetch this any time they observe two roots from the substrate (e.g. a cached root from a prior verification + the current root) and run the verification per §2.2.

The same shape applies to the SCITT (SHA-256) MMR via:

GET /attestation/v1/scitt-consistency?from={old_count}&to={new_count}

2.4 Verifier obligations

Verifiers SHOULD cache observed roots with timestamps and the source they came from (e.g. "fetched directly from substrate at T_a" vs "received from witness W at T_b"). Whenever any two cached roots from the same substrate are compared, the verifier MUST:

1. Order them by leaf_count.
2. Fetch a consistency proof for the pair.
3. Reject the substrate if the proof does not verify.

Roots received from different sources (substrate vs witness) are particularly important to compare — that's how equivocation is caught.

3. Witness-driven gossip (MMR1.1-4)

3.1 Witness role

A witness is a third party (typically another substrate operator, an independent monitoring service, or a regulator) that periodically fetches the substrate's current (leaf_count, root, signed_at_ns) tuple via GET /attestation/v1/log and re-publishes it.

A witness is NOT required to validate inclusion proofs; it only re-publishes what the substrate said its current tree head was at observation time. The witness's signature on its observation makes the observation undeniable (the witness can't claim "I never saw that root").

Witness publication format:

{
  "v": 1,
  "schema": "deos_witness_observation_v1",
  "witness_did": "<witness DID>",
  "substrate_did": "<observed substrate DID>",
  "tree_id": "<observed tree id>",
  "observed_root": "<hex>",
  "observed_leaf_count": <u64>,
  "observed_at_ns": <unix ns>,
  "signatures": [
    { "kid": "<witness kid>", "alg": "ed25519", "sig": "<base64url>" }
  ]
}

The signed body excludes signatures and is signed with "deos-witness-observation-v1:" || JCS(body) per the substrate's domain-separation pattern.

3.2 Gossip protocol

Witnesses publish their observations via:

1. Substrate-side endpoint: each substrate maintains GET /attestation/v1/witnesses — a list of witness observations of ITSELF that the substrate has received and accepted. Witnesses POST observations to POST /attestation/v1/witness (auth required: substrate-issued witness token).
2. Witness-side endpoint: each witness publishes GET /witnesses/{substrate_did} returning all observations the witness has made of that substrate.
3. Cross-witness query: verifiers can fetch from EITHER source and compare. If a witness's published observation differs from what the substrate has accepted (i.e. the substrate is hiding observations that don't match its current narrative), the substrate's behavior is detectable.

3.3 Gossip cadence

Witnesses observe at a configurable cadence (default: every hour). Each observation is independently published. Verifiers' comparison frequency is up to them; for high-stakes operations a verifier MAY observe in real time before trusting a receipt.

3.4 What gossip catches and what it doesn't

Catches:

• A substrate publishing two roots at the same leaf_count (impossible if substrate is honest — leaves at counts 1..N uniquely determine the root).
• A substrate publishing a root that is NOT a forward-extension of an earlier observed root (caught via consistency-proof failure when comparing two witnesses' observations).
• A substrate that selectively shows different observations to different witnesses (caught when witnesses cross-publish).

Doesn't catch:

• A substrate that lies to ALL witnesses (no information advantage to any single witness vs another). Mitigation: §4 log-of-logs.
• A substrate that publishes a single consistent narrative with completely fabricated leaves (the cryptographic chain still verifies; gossip detects equivocation, not fabrication of authorized but never-actually-issued receipts). Mitigation: capability-chain validation in Registration Policy already ensures every leaf is accompanied by a valid UCAN chain signed by the principal.

4. Fork detection (MMR1.1-5)

4.1 Detection rules

A verifier MUST report the substrate as forked when ANY of the following is observed:

1. Same-count conflict. Two (leaf_count = N, root = R) observations from the same substrate with the same N but different R values.
2. Forward-extension violation. Two observations (N1, R1) and (N2, R2) with N1 < N2, where the consistency proof from R1 to R2 fails verification.
3. Witness-substrate divergence. A witness's published observation of the substrate at time T differs from what the substrate's /witnesses endpoint says was accepted at the same time.

4.2 Verifier action on detection

A forked substrate is a substrate that has lost its tamper-evidence guarantee. Verifiers MUST:

1. Stop trusting any new receipts from the substrate.
2. Surface the contradicting observations as evidence (cache both with their signatures).
3. Report to whatever incident-response channel the deployment defines (out of substrate scope).
4. Continue to honor receipts they already accepted before the fork, BUT note in their audit that those receipts come from a substrate that later forked.

Recovery: a forked substrate cannot un-fork itself. The operator's options are:

• Roll back to a known-good tree state and re-emit any lost receipts under a new substrate DID + tree_id (this is operationally a new substrate; verifiers re-evaluate trust).
• Continue operating as a forked substrate and accept reduced trust from verifiers (rarely useful).

4.3 New endpoint

GET /attestation/v1/witnesses

Returns the substrate's accepted witness observations, ordered by observed_at_ns. Verifiers cross-reference this with each witness's /witnesses/{substrate_did} to detect divergence.

5. Log-of-logs (MMR1.1-6)

5.1 The pattern

A log-of-logs is a meta-substrate that periodically observes each member substrate's (leaf_count, root) and appends each observation as a leaf in its own MMR. The meta-substrate is itself anchored via OTS (or a separate chain) so its observations are timestamp-bounded.

This solves the "all witnesses lie" problem: even if every individual witness collude with the substrate they're observing, the meta-substrate's observations are public, third-party-signed, and time-bounded by an external chain. A substrate caught equivocating against the log-of-logs is provably misbehaving.

5.2 Protocol

1. The log-of-logs operator runs a substrate of its own (recursive; the meta-substrate's MMR holds witness-observation leaves rather than action receipts).
2. At a configurable cadence (default: hourly), the meta-substrate POSTs to each member substrate's /attestation/v1/witness endpoint with its own observation.
3. The meta-substrate's tree head is published publicly and refreshed every cadence.
4. Verifiers consult the meta-substrate's tree head to confirm that any specific member substrate's observed root at time T was a leaf of the meta-substrate at the next-cadence tick after T.

5.3 Bootstrapping

Bootstrapping the meta-substrate requires a known-good initial trust state. v1.1 baseline: DEOS Computing operates the reference log-of-logs at https://logs.deoscomputing.io (hypothetical URL; production deployment dependent), and verifiers configure trust against its DID + initial root out-of-band.

v1.2 will allow multiple competing logs-of-logs (federation of meta-substrates), so no single operator is the chokepoint.

6. Implementation status

The v1.1 deliverable is this specification plus the core MMR primitives in /merkle/log/v1. v1.2 implements the spec without changes to the spec itself:

7. Security considerations

This section satisfies the RFC 3552 requirement.

7.1 Witness compromise

A compromised witness can publish false observations or refuse to publish observations of a misbehaving substrate. Mitigations:

• Multiple independent witnesses (verifiers consult ≥3 distinct witnesses for high-stakes operations).
• Log-of-logs cross-witnessing (§5).
• Witness reputation: verifiers track which witnesses have historically caught substrate misbehavior vs which have stayed silent.

7.2 Substrate-witness collusion

A substrate operator may run their own witnesses or pay witness operators to underreport. Mitigations:

• Operator DID published in the witness observation (verifiers can check for cross-ownership via out-of-band records).
• Diversity requirement: deployment policies SHOULD specify a minimum number of unrelated-operator witnesses.
• Log-of-logs operated by an entity with no commercial relationship to the substrate operator.

7.3 Network partition between witness and substrate

A network partition can cause a witness to observe a stale tree head while the substrate continues operating. This is benign: the witness's observation eventually becomes inconsistent with later observations and is detected as the partition heals. Verifiers MUST NOT treat a partition-induced lag as equivocation; they SHOULD wait for at least one cross-witness confirmation before declaring a fork.

7.4 Consistency-proof DoS

A substrate must answer /consistency queries; an attacker requesting many large proofs could DoS the substrate. Mitigations:

• Rate-limit /consistency per source IP / per admin token.
• Cache consistency proofs for common (old_count, new_count) pairs (e.g. consecutive snapshots at hourly intervals).

7.5 Verifier cache-poisoning

A verifier that caches witness observations without verifying their signatures is vulnerable to a man-in-the-middle injecting fabricated observations. Mitigations:

• Verifiers MUST verify each observation's signature against the witness's published verifying key.
• Witness verifying keys are pinned out-of-band (in the verifier's trust anchors).

8. References

• /merkle/log/v1 — base MMR construction
• /anchor/v1 — OTS anchoring (witnesses also OTS-anchor their observations)
• /interop/scitt/v1 §10 — SCITT log-gossip semantics this spec implements
• RFC 9162 — Certificate Transparency v2.0 (consistency-proof reference for binary trees)
• RFC 3552 — security considerations format (this §7)

9. Maintainer

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

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