Task Graphs

Source

This page reflects spec/schemas/chio-swarm/v1/task-graph.schema.json and spec/PROTOCOL.md section 6.4.2 in the chio repository. The Swarm Protocol reference carries the full set of artifacts and the verification order.

The first object on the ladder with a depth

A task graph is one signed artifact naming every task in a recursive delegation, the edges between them, the joins that fan results back together, and two integer ceilings on the shape those edges may take. Its schema tag is chio.swarm.task-graph.v1, its Rust type is SwarmTaskGraph in crates/kernel/chio-swarm-authority/src/types.rs, and its published wire shape is spec/schemas/chio-swarm/v1/task-graph.schema.json. That JSON Schema is a spec artifact: no crate loads it to validate a graph. Parsing is what rejects a malformed one.

Depth is what makes this artifact different from anything on the rungs below. Delegation depth is not new there: TierScopeCeiling in crates/platform/chio-control-plane/src/policy/types.rs carries an optional max_delegation_depth. What is new is the record. No artifact at the cluster rung carries a depth field, because a node under one operator does not have to prove to anyone how far a call had already been delegated. A swarm graph declares that number per node and the verifier corroborates it against the edge set, and every check on this page follows from that.

Status. Verification is shipped and sits on a runtime path. verify_swarm_authority_bundle is a pure function with no I/O and no clock of its own: the current time arrives as bundle.now_unix_ms and the trusted issuer keys arrive as an argument. The pre-dispatch admission hook at crates/kernel/chio-runtime-core/src/admission_hook/swarm_authority.rs calls it before a swarm-bound child action runs. Issuance is not shipped: sign_swarm_task_graph is exported, and every call site in the workspace is a test helper or the crate’s own examples/agent_os.rs.

The object

Field names below are the wire spellings. The Rust struct uses snake case and deserializes with deny_unknown_fields, so an unrecognized key is a parse failure rather than a silently ignored extension.

pub struct SwarmGraphNode {
    pub task_id: String,
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub parent_task_id: Option<String>,
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub route_plan_ref: Option<String>,
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub continuation_token_ref: Option<String>,
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub budget_allocation_ref: Option<String>,
    pub scope_hash: String,
    pub depth: u32,
}

pub struct SwarmGraphEdge {
    pub from_task_id: String,
    pub to_task_id: String,
    pub edge_type: String,
}

pub struct SwarmGraphJoin {
    pub join_id: String,
    pub parent_task_ids: Vec<String>,
    pub next_task_id: String,
}

task_id is unique across the graph, and scope_hash must be a lowercase 64-character SHA-256 digest. It is what the witness chain for the edge has to land on at both ends: the chain’s first hop must declare the parent node’s hash, its last hop the child node’s. The four optional node fields are less optional than the type suggests: a node with a parent_task_id must also carry a continuation_token_ref, and its route and budget refs must agree with the ones inside that token. edge_type is required to be non-empty and is otherwise uninterpreted; every fixture in the Chio repo uses delegates.

The checks, in order

verify_swarm_authority_bundle refuses an empty trusted key set first, then validates the graph’s shape, then verifies the graph’s signature, then refuses a bundle that carries no continuation tokens or no witness chains: validate_task_graph runs before verify_task_graph_signature, which runs before require_signed_swarm_delegation_evidence. Inside the first of those, once the header fields are checked, the task index and the edge set are built and the structural checks run in a fixed order.

let task_by_id = task_index(graph)?;
let edge_set = edge_set(&graph.edges);
validate_roots(graph)?;
validate_edges(graph, &task_by_id, &edge_set)?;
validate_joins(graph, &task_by_id)?;
validate_route_refs(graph)?;
validate_acyclic(graph, &task_by_id)?;
validate_edge_depths(graph, &task_by_id)?;
validate_graph_limits(graph)?;

Structure before signature has a consequence worth stating plainly: a graph whose ceiling was edited without being re-signed is refused by the structural check, and the negative fixture is built that way on purpose. fixtures/proof-room/swarm-authority/max-depth-exceeded/task-graph.json is the valid four-task fixture with maxDepth lowered from 2 to 0 while carrying the valid graph’s signature byte for byte. Its descriptor names the failure the proof room must produce, and the collected bundle for the recursive-runtime-swarm stage records the same string under observed_failure_code. The codes are slugs of the verifier’s rejection message: the neighbouring cycle case is recorded as proof-room.negative.swarm-task-graph-cycle-at-task-child-a.

{
  "schema": "chio.swarm-authority.negative-fixture.v1",
  "id": "max-depth-exceeded",
  "claim_ref": "claim.swarm.task_graph_bound",
  "base_fixture": "fixtures/proof-room/swarm-authority/valid-recursive-delegation/task-graph.json",
  "case": "MaxDepthExceeded",
  "expected_failure_code": "proof-room.negative.swarm-task-exceeds-max-depth"
}

Both bundles are on disk beside the descriptors, so the two refusals are two commands from a Chio checkout:

$ source scripts/proof-room-quickstart-env.sh
$ for n in max-depth-exceeded graph-cycle; do
$   chio proof verify \
    "fixtures/proof-room/swarm-authority/$n/transaction-passport.json" 2>&1 | head -1
$   echo "exit=${PIPESTATUS[0]}"
$ done

error [urn:chio:error:cli:other]: proof verify: swarm task exceeds max depth: task-child-a
exit=1
error [urn:chio:error:cli:other]: proof verify: swarm task graph cycle at task-child-a
exit=1

Both name the node, and both exit 1. Slugify either sentence and the descriptor’s expected_failure_code falls out of it, which is the whole binding between the two artifacts.

Depth arithmetic

let expected_child_depth = parent
    .depth
    .checked_add(1)
    .ok_or_else(|| rejected("swarm task depth overflow"))?;
if child.depth != expected_child_depth {
    return Err(rejected(format!(
        "swarm task depth mismatch: {} -> {}",
        edge.from_task_id, edge.to_task_id
    )));
}

Exactly parent depth plus one, not at most. The declared depth is not a hint the verifier recomputes and repairs; it is a claim the edge set has to corroborate. checked_add is the second half: overflow is a rejection, not a wraparound. Depth is a u32, so the wrap needs a parent declared at u32::MAX, and the depth-0 child it would produce is something validate_roots already refuses, because a depth-0 node with a parent rejects. The arithmetic refuses on its own rather than leaning on that ordering.

swarm_authority_stage0_rejects_edge_depth_bypass is the interesting negative, because it satisfies the ceiling by lying about the shape rather than by editing the ceiling. It lowers max_depth to 1, reparents the second child under the first, leaves that child’s depth at 1, repoints the edge, rebuilds the witness chain for the new pair, and refreshes the continuation digests so the downstream bindings stay consistent. The bundle rejects with swarm task depth mismatch: understating depth fails on the arithmetic before it ever reaches the ceiling.

The two ceilings

validate_graph_limits does two things. It walks the nodes and rejects any whose depth exceeds max_depth. Then it walks the edges, counting per from_task_id, and rejects the first source whose count exceeds max_fanout. Because the counter keys on the edge source, the ceiling bounds outgoing edges rather than children: an edge that expresses a dependency rather than lineage draws on the same allowance.

Why a planner cannot widen them

The signature body is the canonical JSON serialization of the whole graph with the signature field removed, built by task_graph_signature_body. Both ceilings are inside it, alongside every node, edge, and join. Widening a ceiling after issuance changes the signed body, and the graph is also bound downstream: each continuation token carries graphSha256, the canonical SHA-256 of the graph, which the verifier recomputes rather than trusts.

swarm_authority_stage0_rejects_task_graph_tampering_after_continuations_are_resealed closes the obvious escape. It adds one to max_fanout, recomputes the graph digest, and re-signs every continuation token against the new digest, so the digest binding is consistent again and the widened ceiling is trivially satisfied by a graph that was already inside the old one. The bundle still rejects, with swarm task graph signature invalid. Re-sealing downstream evidence does not help: max_fanout is inside the signed body, so the old signature no longer verifies over it, and minting a new one needs a key in the caller’s pinned set.

What the ceilings do not cover

Joins are declared in the graph and are not edges. The edge set the verifier builds comes from graph.edges alone, so a join takes no part in depth arithmetic, fan-out accounting, the acyclicity walk, or the requirement that every edge carry exactly one delegation witness chain. What validate_joins does check: join ids are unique, parents are unique and resolve to real tasks, the next task resolves, the next task is not one of its own parents, and there are at least two parents.

The join target is not required to sit below its parents. In the shipped positive fixture the join over three depth-1 children names task-root, the depth-0 node, as its next task, and the edge set stays acyclic because the join is not in it. That is the boundary of the containment on this page: it bounds the delegation tree, not the convergence topology drawn over it.

Schema and verifier also disagree here, in the safe direction. The schema allows a join with minItems: 1 parents; the verifier requires two, asserted by swarm_authority_stage0_rejects_single_parent_join. The schema likewise expresses neither the single root, nor depth plus one, nor either ceiling being enforced.

How the rest of the bundle hangs off the graph

The graph is the index every other artifact is checked against, in both directions. That is what keeps it from being metadata attached to work already authorized elsewhere.

Guarantees and limits

Next Steps

• Swarm Authority · the one function that verifies this graph together with the other seven artifacts
• Swarm Overview · the rung, the verifier entry point, and the other seven artifact roles in the bundle
• 3-Vendor Walkthrough · one delegation carried end to end, graph included
• Cluster Overview · the rung below, where authority is held rather than derived and nothing nests
• Capabilities · attenuation itself, the Kernel mechanism each edge’s witness chain proves a hop obeyed
• Federation · the standing relationship a derived authority travels across