Task graphs

The graph fixes depth and fan-out before any child runs

Delegation edges carry authority outward. Joins carry results back. The verifier checks the two relationships separately.

task-root delegates to three depth-1 children. The graph signs maxDepth 2 and maxFanout 3, so every node stays at or below depth 2, each edge advances one level, and no parent has more than three children; the fixture itself uses one delegation level. The results meet at join-child-results, whose next task is task-root, without adding a delegation edge.

Read more in Swarm authority, which verifies this graph together with every record it names.

An application sets the ceilings on the grant it hands a coordinator

A coordinator receives its ceilings with its grant. Here the fixer gets room to split issue #417 two levels deep and three wide, on a fork of the pricing project, with a USD 2 pool every helper draws from.

import { Computer, USD } from "@chio-protocol/sdk";

const project = await Computer.open("quickstart");
const fixer = await project.agent("fixer");
const fork = await project.fork();
const authority = fork.grant({
  to: fixer,
  resources: { "/workspace": ["read", "write"] },
  delegation: { depth: 2, fanout: 3 },
  budget: USD(2),
  expiresIn: "20m",
});
console.log(authority.describe());

grant      cap-01b3…6d20, signed by your kernel
to         fixer, delegating up to 2 deep and 3 wide
on         quickstart, fork 51c07ae
allows     /workspace         read, write
budget     USD 2.00 pool shared by all of its agents, charged at your door
expires    in 20 minutes

from chio import Computer, Delegation, USD

project = Computer.open("quickstart")
fixer = project.agent("fixer")
fork = project.fork()
authority = fork.grant(
    to=fixer,
    resources={"/workspace": ["read", "write"]},
    delegation=Delegation(depth=2, fanout=3),
    budget=USD(2),
    expires_in="20m",
)
print(authority.describe())

grant      cap-01b3…6d20, signed by your kernel
to         fixer, delegating up to 2 deep and 3 wide
on         quickstart, fork 51c07ae
allows     /workspace         read, write
budget     USD 2.00 pool shared by all of its agents, charged at your door
expires    in 20 minutes

use chio::{Computer, Delegation, Grant, USD};

let project = Computer::open("quickstart").await?;
let fixer = project.agent("fixer").await?;
let fork = project.fork().await?;
let authority = fork.grant(
    Grant::to(&fixer)
        .resource("/workspace", ["read", "write"])
        .delegation(Delegation::depth(2).fanout(3))
        .budget(USD(2))
        .expires_in("20m"),
)?;
println!("{}", authority.describe());

grant      cap-01b3…6d20, signed by your kernel
to         fixer, delegating up to 2 deep and 3 wide
on         quickstart, fork 51c07ae
allows     /workspace         read, write
budget     USD 2.00 pool shared by all of its agents, charged at your door
expires    in 20 minutes

The signed graph carries the same ceilings as maxDepth and maxFanout. It holds one depth-0 root, uniquely identified tasks, directed delegation edges, and separately declared joins. A parented task references its continuation token, which agrees with the task’s route and budget allocation, and scope hashes let a witness bind parent and child at each edge.

A malformed graph stops at the first structural rule

verify_swarm_authority_bundle refuses an empty trusted key set, then runs validate_task_graph, then verify_task_graph_signature, then require_signed_swarm_delegation_evidence. Inside the first, once the header fields are checked, the structural rules run in a fixed order.

Structure comes before the signature, so a graph whose ceiling was edited without being re-signed is refused by the structural check. Changing a signed ceiling takes a fresh signature from a trusted issuer.

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)?;

Each delegation edge advances exactly one level

The declared depth is a claim the edge set has to corroborate. The verifier compares it with the parent’s depth plus one.

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
    )));
}

Overflow is a rejection. Depth is a u32, so a wrap needs a parent declared at u32::MAX, and the depth-0 child it would produce is one validate_roots already refuses; the arithmetic refuses on its own as well. swarm_authority_stage0_rejects_edge_depth_bypass lowers max_depth to 1, reparents the second child under the first at depth 1, rebuilds the witness chain, and refreshes the continuation digests. It is refused with swarm task depth mismatch: understating depth fails on the arithmetic before it reaches the ceiling.

A planner cannot widen a ceiling it already signed

validate_graph_limits refuses any node whose depth exceeds max_depth, then counts edges per from_task_id and refuses the first source over max_fanout. The counter keys on the edge source, so the ceiling bounds outgoing edges: a dependency edge draws on the same allowance as a lineage edge.

The signature body, built by task_graph_signature_body, is the canonical JSON of the whole graph with the signature field removed, and both ceilings sit inside it. Each continuation token also carries graphSha256, which the verifier recomputes. swarm_authority_stage0_rejects_task_graph_tampering_after_continuations_are_resealed adds one to max_fanout and re-signs every continuation against the new digest; the bundle is still refused with swarm task graph signature invalid.

A ceiling is a commitment by whoever signed the graph. Any holder of a trusted key can sign a different graph with different ceilings, so the trusted set is the caller’s decision, upstream of everything here; Swarm authority states what an empty set costs. Together, one root, the parent-edge rule, and depth plus one make the lineage a tree, so a full tree at both ceilings grows exponentially in maxDepth. Swarm Scarcity carries the closed form, and the budget pool bounds what the graph may spend.

Joins gather results, and every other record hangs off the graph

Joins are declared in the graph and stay out of the edge set, so they take no part in depth arithmetic, fan-out accounting, the acyclicity walk, or witness coverage. validate_joins checks that join ids and parents are unique, parents and the next task resolve, the next task is not one of its own parents, and there are at least two parents. In the fixture the join names task-root, the depth-0 node, as its next task: the ceilings bound the delegation tree, and the join adds no edge they count.

• Continuation token. Same graphId, recomputed graphSha256, and a child task in the graph. A parented node without a continuationTokenRef, or a token naming a different child, is refused.
• Witness chain. Its (parentTaskId, childTaskId) pair is an edge, and each edge gets exactly one chain.
• Route-plan receipt. routePlanRefs covers the receipts both ways, the node’s ref equals the token’s, and the receipt’s taskId is the token’s child.
• Budget allocation. Every allocation’s taskId is a node, the node’s ref equals the token’s, each unit rollup sums to maxUnits, and the maxUnits values sum within the pool total. The allocation a token points at is Active.
• Revocation epoch. No revoked task id names a node, and the graph issuer, the planner, and every witness-hop issuer are absent from the revoked subjects.
• Terminal graph receipt. completedTaskIds equals the node set exactly, and the join and route id sets match the bundle.

In the fixture, task-child-a names continuation-child-a, route-child-a, and budget-child-a, witness-child-a covers its edge, and the graph names budget-pool-swarm-valid and revocation-epoch-swarm-valid. The terminal receipt lists all four tasks, the one join, and the three route plans, with a rollup of 7,500 active usd_minor units under the 10,000-unit pool. Join and terminal receipts are signed declarations checked against the graph; the verifier schedules and executes no task.

The prepared negatives refuse a lowered ceiling and a cycle

The max-depth-exceeded negative is the valid four-task graph with maxDepth lowered from 2 to 0, carrying the valid graph’s signature byte for byte. A coordinator that tried to widen its own ceiling after signing would produce exactly this file. Read the field from the graph the generator wrote:

jq '.maxDepth' ./swarm/negatives/max-depth-exceeded/task-graph.json

0

Verify it beside the graph-cycle negative. Both must be refused:

$ chio proof verify \
  ./swarm/negatives/max-depth-exceeded \
  ./swarm/negatives/graph-cycle \
  --trust ./swarm/trust.toml --expect refuse

REFUSED   max-depth-exceeded  swarm task exceeds max depth: task-child-a
REFUSED   graph-cycle         swarm task graph cycle at task-child-a
2 of 2 refused, as expected
trust     ./swarm/trust.toml (fixture keys)

You should see both refusals name the node, and the summary line confirm that each input was refused as expected. Each code is a slug of the verifier’s message: the collected bundle for the recursive-runtime-swarm stage records the same string under observed_failure_code, and the cycle case is recorded as proof-room.negative.swarm-task-graph-cycle-at-task-child-a. In the worked example below, you sign a branching graph and change its fan-out.

cargo run --locked --bin task-graph -- 2

use chio_swarm_authority::verify_swarm_authority_bundle;
use swarm_authority_examples::*;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let fanout: u32 = std::env::args()
        .nth(1)
        .unwrap_or_else(|| "2".into())
        .parse()?;
    let mut bundle = build_bundle()?;
    bundle.task_graph.max_fanout = fanout;
    // Re-sign the graph, then rebind and sign the continuations to its new digest.
    refresh_continuation_graph_digests(&mut bundle)?;
    let report = verify_swarm_authority_bundle(&bundle, &trusted_witness_keys())?;
    println!(
        "graph: {} tasks; max fanout {fanout}; {} join",
        report.task_count, report.join_count
    );
    bundle.task_graph.max_depth = 0;
    refresh_continuation_graph_digests(&mut bundle)?;
    let error = verify_swarm_authority_bundle(&bundle, &trusted_witness_keys())
        .expect_err("depth-1 children must refuse at depth 0");
    println!("depth mutation: {error}");
    Ok(())
}

let mut task_graph = SwarmTaskGraph {
        schema: CHIO_SWARM_TASK_GRAPH_SCHEMA.to_string(),
        graph_id: "analysis-graph".to_string(),
        root_transaction_ref: "passport-analysis".to_string(),
        planner_subject: "did:chio:planner".to_string(),
        issuer: witness_issuer(),
        signature: String::new(),
        created_at_unix_ms: now_ms() - 1_000,
        expires_at_unix_ms: now_ms() + 60_000,
        max_depth: 2,
        max_fanout: 2,
        multi_hop_witness_chains: false,
        nodes: vec![
            SwarmGraphNode {
                task_id: "task-root".to_string(),
                parent_task_id: None,
                route_plan_ref: None,
                continuation_token_ref: None,
                budget_allocation_ref: None,
                scope_hash: parent_scope_hash.clone(),
                depth: 0,
            },
            SwarmGraphNode {
                task_id: "task-child-a".to_string(),
                parent_task_id: Some("task-root".to_string()),
                route_plan_ref: Some("route-child-a".to_string()),
                continuation_token_ref: Some("continuation-child-a".to_string()),
                budget_allocation_ref: Some("budget-child-a".to_string()),
                scope_hash: child_scope_hash.clone(),
                depth: 1,
            },
            SwarmGraphNode {
                task_id: "task-child-b".to_string(),
                parent_task_id: Some("task-root".to_string()),
                route_plan_ref: Some("route-child-b".to_string()),
                continuation_token_ref: Some("continuation-child-b".to_string()),
                budget_allocation_ref: Some("budget-child-b".to_string()),
                scope_hash: child_scope_hash.clone(),
                depth: 1,
            },
        ],
        edges: vec![
            SwarmGraphEdge {
                from_task_id: "task-root".to_string(),
                to_task_id: "task-child-a".to_string(),
                edge_type: "delegates".to_string(),
            },
            SwarmGraphEdge {
                from_task_id: "task-root".to_string(),
                to_task_id: "task-child-b".to_string(),
                edge_type: "delegates".to_string(),
            },
        ],
        joins: vec![SwarmGraphJoin {
            join_id: "join-child-results".to_string(),
            parent_task_ids: vec!["task-child-a".to_string(), "task-child-b".to_string()],
            next_task_id: "task-root".to_string(),
        }],
        budget_pool_ref: "budget-pool-analysis".to_string(),
        revocation_epoch_ref: "revocation-epoch-analysis".to_string(),
        route_plan_refs: vec!["route-child-a".to_string(), "route-child-b".to_string()],
    };
    sign_task_graph(&mut task_graph)?;
    let graph_sha256 = canonical_hash(&task_graph)?;

graph: 3 tasks; max fanout 2; 1 join
depth mutation: swarm task exceeds max depth: task-child-a

Next: give every edge its witness