Wanderland Core: Merkle DAG

The trace chain is a Merkle DAG. Every crossing carries a backreference hash to the crossing that caused it. Mutating any node invalidates every descendant's signature.

Not a classical balanced Merkle tree with a single root hash over all leaves. A linked Merkle structure: every node is a commitment to its ancestry, and walking any path from a leaf to the root re-verifies the whole prefix.

Two Hash Fields Per Crossing

Every crossing record carries:

• sig — signature over the rest of the crossing's fields
• trace — the sig of the crossing that caused this one

That is the entire construction. No external trace ID, no separate chain ledger, no roll-up root.

Signing a Single Crossing

lib/wanderland/crossing.rb — Crossing#sign

def sign(storage)
  return self unless storage && @has_identity
  begin
    Activities::PKI.generate(storage, @identity)
    @signature = Activities::PKI.sign(storage, @identity, canonical)
  rescue
    # Signing failed — crossing goes unsigned
  end
  self
end

def canonical
  JSON.generate(to_h.reject { |k, _| k == "signature" }.sort.to_h)
end

Three deterministic steps, same as ever:

• Strip the signature field — you can't sign over your own signature.
• Sort keys alphabetically — canonical form, so verification reproduces the same bytes.
• JSON-encode, sign with the identity's private key (read from storage at :pki:keys:{identity}).

Because trace is part of the signable payload, the parent hash is bound into this crossing's signature.

Signing is soft: if the boundary has no identity, or if key material can't be generated, the crossing goes unsigned rather than raising. Context#verify_chain surfaces that as sig_valid: false without breaking the chain walk. Production deployments provision real keys into :pki: at boot via resolver tags (!SSM, !Vault); dev/test auto-generates ephemeral keys on first sign.

Linear Links

lib/wanderland/crossing.rb — Crossing#link

def link(prev)
  @trace = prev&.respond_to?(:signature) ? prev.signature : prev&.dig("signature")
  self
end

The walker calls link on every crossing before signing, passing the previous event from Context. Root crossings are linked against nil and get a nil trace.

crossing 0:  sig = "aaa"                       <- root, trace = nil
crossing 1:  trace = "aaa",  sig = "bbb"       <- binds aaa into bbb
crossing 2:  trace = "bbb",  sig = "ccc"       <- binds bbb into ccc

Tamper with crossing 1's payload: its sig no longer verifies. Re-sign crossing 1 to fix that: now its sig differs from "bbb", so crossing 2's trace is wrong. To repair the chain you would have to re-sign every descendant, which requires every descendant's private key. That is the tamper-evidence.

Forks

The current build is linear — every crossing links to the single previous event on the Context stack. Fork encoding (parent_sig:child_index) is parked and returns alongside the reactivity model (trigger registry + wave executor), where a single write can fire multiple boundaries in one wave.

When it lands, the scheme is the same as the old prototype: a child trace is parent_sig:N, rpartition(":") recovers the parent sig and child index, and verify_link accepts either an exact match or the parent portion for fork children. Convergence (two parents into one child) stays out of band — a boundary that needs to reference multiple ancestors embeds their sigs in its payload.

Until then: one trace per crossing, pure linear DAG, one predecessor per node.

Composing a Whole Chain

lib/wanderland/boundary.rb — the walker composes the chain inline as boundaries execute. There is no standalone sign_chain function anymore; every crossing is linked and signed at the moment Boundary.execute returns it.

# Inside Boundary.execute, per slot:
crossing = Wanderland::Crossing.new(boundary: reg, signal: signal, from: caller)
crossing.link(ctx&.events&.last)   # trace = prev.signature (or nil for root)
crossing.sign(storage)              # canonical JSON, signed by the boundary's identity
ctx.append(crossing)                # Context verifies the signature on append

Three things fall out of this for free:

• Root: the first crossing links against nil, so trace is nil. No special-casing.
• Cross-identity: each link is signed by a different identity — the boundary (or user session) that produced it. The chain is co-signed by everyone who touched it, not rolled up by a single signer.
• Soft verification: Context#append calls crossing.verify!(storage) and stores the boolean in a parallel array. Forged or unsigned crossings still enter the log (audit trail preserved); they're just invisible through trust filters like .signed / .by_identity.

Verifying

lib/wanderland/context.rb — Context#verify_chain

def verify_chain
  results = @events do |crossing, i|
    sig_valid = @verified == true
    link_valid = if i == 0
                   true
                 else
                   prev = @events[i - 1]
                   prev_sig = prev.respond_to?(:signature) ? prev.signature : prev["signature"]
                   trace = crossing.respond_to?(:trace) ? crossing.trace : crossing["trace"]
                   trace == prev_sig
                 end
    { "index" => i, "boundary" => crossing["boundary"],
      "identity" => crossing["identity"],
      "sig_valid" => sig_valid, "link_valid" => link_valid }
  end
  { "valid" => results.all? { |r| r["sig_valid"] && r["link_valid"] }, "results" => results }
end

Two independent checks per crossing:

• sig_valid — read from the @verified parallel array (true if the crossing's signature verified against its identity's public key when Context#append accepted it).
• link_valid — trace equals the previous crossing's signature. Root (index 0) is trivially link-valid.

The chain is valid: true only if every crossing passes both. Unsigned crossings (no identity, signing failed, or forged) show sig_valid: false without breaking the walk — the chain is valid where it can be verified, transparent where it can't.

The User-to-Boundary Chain

The chain is not internal bookkeeping. It spans the full request lifecycle.

user JWT signs   -> crossing 0 (identity: :sessions:user-xyz)
boundary signs   -> crossing 1 (identity: :boundaries:auth_gate,   trace: sig_0)
boundary signs   -> crossing 2 (identity: :boundaries:enforce_denials, trace: sig_1)
boundary signs   -> crossing 3 (identity: :boundaries:echo,        trace: sig_2)
engine signs     -> crossing N (identity: :boundaries:format,      trace: sig_{N-1})
engine signs     -> crossing N+1 (identity: engine:seal,           trace: sig_N)

The chain answers four questions cryptographically:

Question	Answered by
Who initiated?	root crossing's identity (and, when present, its JWT sig)
What executed?	each crossing's boundary field, bound into that crossing's signature
In what order?	trace links, verified left-to-right by Context#verify_chain
Nothing tampered?	every sig_valid: true and every link_valid: true

Identity naming is still settling. In the current build, boundary identities use the boundary:name / engine:name scheme; the case task-bac15977 (Crossing ↔ 4-address convergence) will rename identity → from_addr to align with the crossings-architecture four-address model.

Roll-Up to a Single Root

There is no pre-computed root hash over the whole chain. When an external system needs one — compliance export, cross-org attestation, a notary handoff — the seal boundary produces it as just another crossing.

... normal chain ...
crossing N:    sig = "zzz"
crossing N+1:  boundary  = "seal"
               identity  = "engine:seal"
               trace     = "zzz"
               payload:
                 chain_valid:  true
                 chain_depth:  12
                 sealed_sigs:  ["ddd", "fff", "zzz", ...]   # sorted leaves
                 sealed_at:    "2026-04-16T18:20:00Z"
               signature = "root"         # commitment over the whole chain

The seal's signature is a commitment over both its payload (which lists every leaf sig, sorted) and its trace (which is itself a commitment to the linear prefix). One sig binds the entire DAG.

Live implementation — lib/wanderland/boundaries/seal.rb:

class Seal
  include Wanderland::Boundary

  IDENTITY = Wanderland::Identity.new(
    id: "engine:seal", name: "Chain Seal",
    roles: [:engine], type: :service, scopes: [:seal]
  ).freeze

  boundary :seal,
    identity: IDENTITY,
    capabilities: [:seal],
    when_shape: { "always" => true }

  def call(input)
    context = input["context"]
    verification = context.verify_chain
    signatures = context.events
      .map { |c| c.respond_to?(:signature) ? c.signature : c["signature"] }
      .compact

    Signal.ok(
      chain_valid:  verification["valid"],
      chain_depth:  context.size,
      sealed_sigs:  signatures.sort,
      sealed_at:    Time.now.utc.iso8601
    )
  end
end

Key changes from the prototype:

• Injected at the tail of every chain via core_injections (position last), after format.
• when_shape: { always: true } — runs on halts and errors too, so sealed audit trails cover failure paths.
• Signed by the engine's own identity (engine:seal), not by a user or boundary. The seal is a framework act, not a participant in the request.
• chain_valid from Context#verify_chain rides in the payload, so consumers can see whether the prefix verified at seal-time without re-walking.

Sorted sig list in canonical form means reproduction is deterministic across hosts. No new primitive — the engine signs the seal crossing on the way out, same as any other.

What It Isn't

Not a classical Merkle tree:

• No balanced binary structure
• No single pre-computed root over all leaves
• No proof paths with sibling hashes

What it is:

• A linked Merkle DAG
• Every node commits to its direct ancestor via trace
• Every node commits to its own content via sig
• The chain proves ancestry by walking sigs, not by hashing a tree

Think blockchain without the blocks — or Git commit ancestry with authenticated signatures on every link.

Where It Is Exercised

• lib/wanderland/crossing.rb — Crossing struct; owns #link, #sign, #canonical, #verified?
• lib/wanderland/context.rb — Context#append soft-verifies on entry; Context#verify_chain walks the stack checking sigs and links
• lib/wanderland/boundary.rb — walker composes the chain inline (link(prev).sign(storage) per slot)
• lib/wanderland/boundaries/seal.rb — tail injection producing the root commitment
• lib/wanderland/activities/pki.rb — generate/sign/verify primitives against :pki:keys:{identity} storage
• spec/wanderland/merkle_chain_spec.rb — full-dispatch integration: links, verify_chain, signed-vs-unsigned distinction

Removed in commit a92dbfd (kept here for historical context):

• lib/wanderland/activities/trace_chain.rb — the standalone hash-based prototype (replaced by inline Crossing methods)
• lib/wanderland/boundaries/trace_chain_ops.rb — prototype boundary wrapper
• spec/scenarios/trace_chain/*.yml — prototype scenarios (replaced by merkle_chain_spec)

Source

• wanderland-core/lib/wanderland/crossing.rb
• wanderland-core/lib/wanderland/context.rb
• wanderland-core/lib/wanderland/boundary.rb
• wanderland-core/lib/wanderland/boundaries/seal.rb