> ## Documentation Index
> Fetch the complete documentation index at: https://jephalabs.mintlify.site/llms.txt
> Use this file to discover all available pages before exploring further.

# Plan Compilation

> How QTG compiles a reusable movement template and input parameters into a validated, hash-locked execution plan.

# Plan Compilation

***

## What is a Plan?

**Plan = a blueprint that defines "what to do and in what order" ahead of time.**

Think of it like an international travel itinerary:

* **Departure**: Incheon Airport (= Upbit)
* **Layover**: Singapore transit (= CCTP Attestation)
* **Destination**: Sydney, Australia (= Base Chain)
* **Transport for each leg**: Korean Air ICN–SIN, Qantas SIN–SYD (= CEX Executor, CCTP Executor)

There are two kinds of travel plans:

| Type         | Travel analogy                                                      | QTG                                            |
| ------------ | ------------------------------------------------------------------- | ---------------------------------------------- |
| **Template** | "Southeast Asia 2-week package" catalog                             | `MovementPlanTemplate` + `MovementPlanVersion` |
| **Instance** | "Departing March 25, 2026, 1 passenger: Kim Chulsoo" actual booking | `MovementRequest` + `MovementRequestNode`      |

A Template is a reusable blueprint. Once you create a plan template like "Send XRP from Upbit to Bithumb," you can stamp out requests from that same template — whether for 25 XRP or 100 XRP.

<Tip>
  **Template vs Instance**
  A Template contains **who executes it** — e.g., `executor_selector: {"executor_key": "cex-upbit"}`. An Instance contains **what to send this time** — e.g., `intent: {"asset": "XRP", "amount": "25"}`.
</Tip>

***

## Why do we "compile" a Plan?

A Template is abstract. It contains variables and no concrete amounts or addresses. **Compilation** is the process of turning it into a concrete execution plan.

Analogy: C source code → compiler → executable. Plan Template → Plan Compiler → executable Request.

```mermaid theme={null}
flowchart LR
    subgraph input["Input"]
        T["Plan Template<br/>(nodes + edges)"]
        P["Input Params<br/>(asset, amount, addresses)"]
    end

    subgraph compiler["Compiler"]
        V["①graph validation"]
        R["②executor/signer binding"]
        S["③snapshot build"]
        H["④hash computation"]
        V --> R --> S --> H
    end

    subgraph output["Output"]
        REQ["MovementRequest<br/>+ MovementRequestNodes<br/>+ compiled_plan_hash"]
    end

    T --> V
    P --> S
    H --> REQ

    style input fill:#e1f5fe
    style compiler fill:#fff3e0
    style output fill:#e8f5e9
```

Four things happen sequentially during compilation:

1. **Graph validation** — confirms the plan is in an executable form
2. **Binding resolution** — determines which executor/signer to attach to each node
3. **Snapshot creation** — merges all information into a single immutable document
4. **Hash computation** — generates a fingerprint of the snapshot

<Warning>
  **Why does this order matter?**
  If you execute with an invalid graph, funds get withdrawn but there's no next node — everything stalls. If bindings aren't resolved, the executor can't be found — everything stalls. **All problems must be caught at compile time.**
</Warning>

The movement-create flow runs these four stages in order: it resolves bindings, computes the frontier (root) nodes, builds the snapshot, then computes the hash from that snapshot.

Note that graph validation is already performed at **template registration time** — when a request is created, only the `executable_in_v3_0` flag is checked.

***

## Graph Structure

### A Plan is a DAG

A Plan is a **DAG (Directed Acyclic Graph)** — a directed graph with no cycles.

* **Node** = a unit of execution. Things like "withdraw XRP from Upbit," "poll withdrawal status," "confirm Bithumb deposit."
* **Edge** = a dependency. "Withdrawal must complete before withdrawal confirmation can start."

```mermaid theme={null}
graph TD
    subgraph cex["CEX 3-Node Lane (Upbit → Bithumb)"]
        W["withdrawal_action<br/>🔥 has_side_effect"] -->|on_success| WO["withdrawal_observe<br/>withdrawal status polling"]
        WO -->|on_success| DO["deposit_observe<br/>deposit confirmation polling"]
    end

    subgraph cctp["CCTP 5-Node Lane (Ethereum → Base)"]
        BURN["cctp_burn<br/>🔥 has_side_effect"] -->|on_success| ATT["cctp_attestation<br/>Circle attestation wait"]
        ATT -->|on_success| MINT["cctp_mint<br/>🔥 has_side_effect"]
        MINT -->|on_success| RCV["mint_receive_observe<br/>destination USDC receipt"]
        RCV -->|on_success| FIN["chain_finality_observe<br/>block finality wait"]
    end

    style W fill:#fce4ec
    style BURN fill:#fce4ec
    style MINT fill:#fce4ec
    style cex fill:#e8f5e9
    style cctp fill:#e3f2fd
```

<Tip>
  **What is has\_side\_effect?**
  "Does executing this node cause something irreversible?" Submitting a withdrawal moves funds — that's a side effect. Checking withdrawal status has no side effect (read-only). This flag is critical for **determining recovery strategy on error**.
</Tip>

### Why must it be a DAG?

A cycle causes an infinite loop. "A must finish before B, and B must finish before A..." — you can never start. In a system handling real money, an infinite loop is catastrophic, so **cycles are blocked at compile time**.

***

## Graph Validation

Validation runs in 6 steps. Failure at any step throws a `GraphValidationError` and the template registration is rejected outright.

```mermaid theme={null}
flowchart TD
    START["validation start"] --> DUP["①duplicate node_key check"]
    DUP -->|"pass"| MIN["②minimum node count check<br/>(at least 1)"]
    MIN -->|"pass"| REF["③edge reference integrity<br/>(from/to are real nodes?)"]
    REF -->|"pass"| SELF["④no self-loops<br/>(A→A not allowed)"]
    SELF -->|"pass"| CYCLE["⑤DAG cycle detection<br/>(Kahn's Algorithm)"]
    CYCLE -->|"pass"| COMP["⑥completion_policy validation<br/>(terminal node family match)"]
    COMP -->|"pass"| RESULT["validation result<br/>graph_shape + topological_order"]

    DUP -->|"fail"| ERR1["❌ duplicate node_key detected"]
    MIN -->|"fail"| ERR2["❌ must define at least one node"]
    REF -->|"fail"| ERR3["❌ edge references unknown node"]
    SELF -->|"fail"| ERR4["❌ self-loop edges not allowed"]
    CYCLE -->|"fail"| ERR5["❌ template graph must be a DAG"]
    COMP -->|"fail"| ERR6["❌ completion_assurance requires..."]

    style RESULT fill:#c8e6c9
    style ERR1 fill:#ffcdd2
    style ERR2 fill:#ffcdd2
    style ERR3 fill:#ffcdd2
    style ERR4 fill:#ffcdd2
    style ERR5 fill:#ffcdd2
    style ERR6 fill:#ffcdd2
```

### A closer look at each step

**1. Duplicate node\_key check**
If two nodes share the same name, it becomes ambiguous which node to execute — duplicate `node_key`s are rejected.

**2. Minimum node count check**
A plan with zero nodes does nothing. Meaningless, so it's rejected.

**3. Edge reference integrity**
If an edge says `{from: "withdrawal", to: "deposit_check"}` but no node named `deposit_check` exists, execution will fail with "can't find next node."

**4. Self-loop prohibition**
`{from: "A", to: "A"}` — depending on yourself makes no sense.

**5. DAG cycle detection (Kahn's Algorithm)**

This is the most critical validation step. **Kahn's Algorithm** performs a topological sort while simultaneously detecting cycles.

```mermaid theme={null}
flowchart LR
    subgraph kahns["Kahn's Algorithm operation"]
        Q1["queue: enqueue nodes with indegree=0"] --> POP["dequeue"]
        POP --> REDUCE["child node indegree -1"]
        REDUCE --> CHECK{"child indegree=0?"}
        CHECK -->|"Yes"| ENQUEUE["enqueue"]
        CHECK -->|"No"| POP
        ENQUEUE --> POP
        POP -->|"queue empty"| DONE{"processed count = total?"}
        DONE -->|"Yes"| OK["DAG confirmed!"]
        DONE -->|"No"| FAIL["cycle detected!"]
    end
    style OK fill:#c8e6c9
    style FAIL fill:#ffcdd2
```

Simply put: "Remove nodes one by one, starting with those that have no prerequisites. If all nodes can be removed, there are no cycles. If some nodes remain that can't be removed, there's a cycle."

Mechanically: start with every node whose indegree is 0, repeatedly remove a node and decrement its children's indegree, enqueuing any child that reaches indegree 0. If every node gets processed this way the graph is a DAG; if some nodes can never be reached, a cycle exists and the template is rejected.

The order in which nodes come off the queue is the **topological sort result**, which also becomes the basis for execution order.

**6. completion\_policy validation**

Verifies that the criteria for declaring a plan "complete" are correct.

Each completion-assurance level requires a matching terminal-node family:

| Completion assurance    | Required terminal node family        |
| ----------------------- | ------------------------------------ |
| `provider_completed`    | `source_provider_observe`            |
| `destination_observed`  | `destination_chain_receive_observe`  |
| `destination_credited`  | `destination_provider_observe`       |
| `destination_finalized` | `destination_chain_finality_observe` |
| `protocol_finalized`    | `protocol_observe`                   |

Examples:

* `destination_credited`: "complete when deposit is confirmed at the destination exchange" → the terminal node must be from the `destination_provider_observe` family
* `destination_finalized`: "complete when N confirmations accumulate on the destination chain" → the terminal node must be `destination_chain_finality_observe`, and `config.confirmations_required` must be set
* `protocol_finalized`: "complete when confirmed at the protocol level (e.g., CCTP attestation)" → the terminal node must be from the `protocol_observe` family

***

## compiled\_plan\_hash

### Why is a hash needed?

Analogy: **detecting tampering after signing a contract**.

An operator approved a plan to "send 25 XRP from Upbit to Bithumb." But what if someone swaps the plan to "2500 XRP" between approval and execution? `compiled_plan_hash` prevents this.

Approval flow:

1. `compiled_plan_hash` is computed at request creation → stored in DB
2. Operator sends `compiled_plan_hash` along with the approval request
3. Server compares it against the stored hash → **mismatches are rejected**

If the hash submitted with the approval does not match the one stored for the request, approval fails with a conflict error and nothing executes.

### How is it computed?

Hash computation follows this procedure:

```mermaid theme={null}
flowchart TD
    A["①extract key fields from snapshot<br/>nodes, edges, input_params,<br/>resolved_bindings, risk_controls"] --> B["②sort nodes by node_key"]
    B --> C["③sort edges by (from, to, edge_type)"]
    C --> D["④JSON serialization<br/>sort_keys=True, separators=(',',':')"]
    D --> E["⑤SHA-256 hash"]
    E --> F["'sha256:' + hex digest"]

    style F fill:#c8e6c9
```

Key points:

* **Sorting is mandatory**: the same content in a different order produces a different hash. Nodes are sorted by `node_key`; edges by `(from, to, edge_type)`.
* **Fixed separators**: `(",", ":")` with no spaces — `{"a":1}` not `{"a": 1}`
* **ensure\_ascii=False**: Korean and other Unicode characters may appear — keep them as-is
* **Result format**: `"sha256:a1b2c3d4..."` — the prefix explicitly identifies the algorithm

<Warning>
  **There are two distinct hashes**

  * **Plan graph hash** — computed at template registration. Hashes the **graph structure itself**. Includes `approval_policy`.
  * **Compiled plan hash** — computed at request creation. Hashes the **concrete execution plan**. Includes `input_params` and `resolved_bindings`.

  The former answers "is this the same template structure?"; the latter answers "is this the same execution plan?"
</Warning>

***

## Compiled Snapshot

A snapshot is an **immutable document**. Once created it never changes, and it serves as the source of truth for the hash.

The snapshot bundles everything needed to describe one concrete execution plan into a single object, with these fields:

* `schema_version` — snapshot schema version (e.g. `"v3.0"`)
* `template_key` / `template_version` — which template and version this was compiled from
* `completion_policy` — the criteria for declaring the plan complete
* `nodes` / `edges` — the validated graph
* `input_params` — the concrete values for this instance (asset, amount, addresses)
* `resolved_bindings` — the executor/signer attached to each node
* `risk_controls` — caps and guards
* `callback_config` — where to send status callbacks

Example snapshot (CEX XRP transfer):

```json theme={null}
{
  "schema_version": "v3.0",
  "template_key": "cex-upbit-binance",
  "template_version": 1,
  "completion_policy": {
    "completion_assurance": "destination_credited"
  },
  "nodes": [
    {
      "node_key": "withdrawal",
      "node_kind": "action",
      "action_type": "cex_withdrawal",
      "executor_selector": {"executor_key": "cex-upbit"},
      "has_side_effect": true
    },
    {
      "node_key": "withdrawal_observe",
      "node_kind": "observe",
      "action_type": "cex_withdrawal_status",
      "executor_selector": {"executor_key": "cex-upbit"},
      "has_side_effect": false
    },
    {
      "node_key": "deposit_observe",
      "node_kind": "observe",
      "action_type": "cex_deposit_status",
      "executor_selector": {"executor_key": "cex-binance"},
      "has_side_effect": false
    }
  ],
  "edges": [
    {"from": "withdrawal", "to": "withdrawal_observe", "edge_type": "on_success"},
    {"from": "withdrawal_observe", "to": "deposit_observe", "edge_type": "on_success"}
  ],
  "input_params": {
    "asset": "XRP",
    "amount": "25",
    "network": "XRP"
  },
  "resolved_bindings": {
    "withdrawal": {"executor": {"executor_key": "cex-upbit"}, "signer": null},
    "withdrawal_observe": {"executor": {"executor_key": "cex-upbit"}, "signer": null},
    "deposit_observe": {"executor": {"executor_key": "cex-binance"}, "signer": null}
  },
  "risk_controls": {"max_amount": "1000"}
}
```

***

## Binding Resolution

This is the process of deciding "which executor and signer to attach to each node."

In the current v3.0 it is straightforward — the `executor_selector` and `signer_selector` already specified on each node in the template are carried through as-is, producing a per-node map of `{executor, signer}`.

<Info>
  **Why is this so simple?**
  The current behavior starts with explicit assignment. In the future, capability-based dynamic resolution — e.g., `executor_selector: {"capabilities": ["cex", "withdrawal"], "prefer": "lowest_fee"}` — may be added.
</Info>

***

## Frontier Computation

Frontier = "the list of nodes that can be executed right now." These are nodes that are not the successor of any other node — the **root nodes**.

Simple logic: "nodes not referenced as the `to` of any edge = starting nodes."

```mermaid theme={null}
graph LR
    W["withdrawal<br/>✅ frontier"] --> WO["withdrawal_observe"]
    WO --> DO["deposit_observe"]

    style W fill:#c8e6c9,stroke:#2e7d32,stroke-width:3px
```

In the CEX 3-node lane, only `withdrawal` is the frontier. Once approved, this node transitions from `BLOCKED` → `READY` and execution begins.

***

## GraphShape

Validation classifies the "shape" of the graph:

| Shape       | Description                                   | Example                      | Executable in v3.0? |
| ----------- | --------------------------------------------- | ---------------------------- | ------------------- |
| `LINEAR`    | Straight line                                 | A → B → C                    | Yes                 |
| `SPLIT`     | One node fans out to multiple (unconditional) | A → B, A → C                 | No                  |
| `BRANCHING` | One node fans out to multiple (conditional)   | A →(if ok) B, A →(if fail) C | No                  |
| `MERGING`   | Multiple nodes converge into one              | A → C, B → C                 | No                  |
| `HYBRID`    | Mix of BRANCHING + MERGING                    | Complex structure            | No                  |

```mermaid theme={null}
graph TD
    subgraph linear["LINEAR"]
        L1["A"] --> L2["B"] --> L3["C"]
    end
    subgraph split["SPLIT"]
        S1["A"] --> S2["B"]
        S1 --> S3["C"]
    end
    subgraph branching["BRANCHING"]
        B1["A"] -->|"condition"| B2["B"]
        B1 -->|"else"| B3["C"]
    end
    subgraph merging["MERGING"]
        M1["A"] --> M3["C"]
        M2["B"] --> M3
    end

    style linear fill:#c8e6c9
    style split fill:#fff3e0
    style branching fill:#fff3e0
    style merging fill:#fff3e0
```

Classification logic, in plain terms:

* A node with more than one outgoing edge means the graph **branches** — `BRANCHING` if those edges carry conditions, otherwise `SPLIT`.
* A node with more than one incoming edge means the graph **merges** (`MERGING`).
* Both branching and merging → `HYBRID`.
* Neither → `LINEAR`.

<Info>
  **v3.0 only executes LINEAR**
  The data model accepts DAGs, but the runtime only supports sequential execution. You can register non-LINEAR templates (for future use), but attempting to create a request from a template that is not marked `executable_in_v3_0` is rejected. `non_executable_reasons` records the specific reason (e.g., `"graph shape 'branching' requires graph runtime"`).
</Info>

***

## End-to-end compilation flow summary

```mermaid theme={null}
sequenceDiagram
    participant Caller as External System
    participant API as POST /v3/movements
    participant Template as Template Store
    participant Compiler as Plan Compiler
    participant DB as Database

    Caller->>API: template_key + intent + input_params
    API->>Template: template + version lookup
    Template-->>API: nodes, edges, policies

    Note over API,Compiler: compilation start
    API->>Compiler: resolve bindings
    Compiler-->>API: resolved_bindings
    API->>Compiler: compute frontier nodes
    Compiler-->>API: frontier = ["withdrawal"]
    API->>Compiler: build compiled snapshot
    Compiler-->>API: snapshot dict
    API->>Compiler: compute compiled plan hash
    Compiler-->>API: "sha256:a1b2c3..."
    Note over API,Compiler: compilation done

    API->>DB: INSERT MovementRequest
    API->>DB: INSERT MovementRequestNodes (BLOCKED)
    API-->>Caller: movement_id + compiled_plan_hash

    Note over Caller: operator can now<br/>approve with compiled_plan_hash
```

<Tip>
  **Key takeaways**

  1. **Plan = a DAG-based execution blueprint** (nodes = steps, edges = dependencies)
  2. **Compilation = Template + Params → executable Request** (validation + binding + snapshot + hash)
  3. **compiled\_plan\_hash = a signed seal on the contract** (detects tampering after approval)
  4. **v3.0 executes LINEAR graphs only** (the model for future DAG parallel execution is already in place)
</Tip>