# `_graph` graph queries

`_graph` is an optional extension to the NIP-01 `REQ` filter. It asks the relay
to traverse its materialized social graph instead of scanning events. Relays
that do not know the field ignore it, so the extension is backward compatible.

torly implements orly's current four-element form and the object form it also
accepts:

```json
["REQ", "g", {"_graph": ["<pubkey-hex>", 1, "pp", "out"]}]

["REQ", "g", {"_graph": {
  "pubkey": "<pubkey-hex>",
  "depth": 1,
  "edge": "pp",
  "direction": "out"
}}]
```

`seed` is accepted as an alias for `pubkey` in the object form. The seed is
always a 64-character lowercase hex pubkey, even for `ee`; that traversal
starts from the events authored by that pubkey. Unknown object keys are
ignored, but an empty object key is rejected.

## Fields

| Field | Required | Values |
|---|---|---|
| seed/pubkey | yes | 64 hex characters |
| depth | no | 1–16, default 1 |
| edge | yes | `pp`, `pe`, `ee` |
| direction | yes | `out`, `in`, `both` |

`pp` walks the pubkey↔pubkey graph built from kind-3 `p` tags. `out` follows
the seed's contact list, `in` finds its followers, and `both` unions the two
at every level. Up to `depth` hops are followed.

`pe` walks the pubkey↔event graph. `out` returns events authored by the seed,
`in` returns events with a `p` tag naming the seed, and `both` returns the
union. This is a one-hop query by design: the graph is bipartite, and a second
hop would return pubkeys rather than events.

`ee` walks the e-tag thread graph. It starts from every event authored by the
seed pubkey (those roots are not included in the result), then follows e-tag
edges for `depth` hops. `out` follows the events a root references (parents and
quotes), `in` follows the events that reference it (replies and reactions), and
`both` walks in both directions.

Every node is reported at the depth where it was first discovered. Depth 1 is
index 0 of the response arrays. A node appears only once. An empty frontier
stops the walk early.

## Response

A graph request is answered with one relay-signed event and then `EOSE`:

```json
["EVENT", "g", {
  "kind": 39000,
  "pubkey": "<relay pubkey>",
  "created_at": 1700000000,
  "tags": [
    ["edge", "pp"],
    ["direction", "out"],
    ["seed", "<seed pubkey>"],
    ["depth", "2"],
    ["elapsed", "1.2ms"]
  ],
  "content": "{\"pubkeys_by_depth\":[[\"<depth 1>\"],[\"<depth 2>\"]],\"total_pubkeys\":2}",
  "id": "<id>",
  "sig": "<signature>"
}]
```

The content carries exactly one result family:

```json
{"pubkeys_by_depth":[["..."],["..."]],"total_pubkeys":2,"elapsed":"1.2ms"}
{"events_by_depth":[["..."],["..."]],"total_events":2,"elapsed":"1.2ms"}
```

`pp` produces `pubkeys_by_depth`; `pe` and `ee` produce `events_by_depth`.
Gaps between discovered depths are kept as empty arrays so the array index
still means "depth minus one". The relay signature lets a client verify the
response like any other event. The signing key is `TORLY_SECRET_KEY` when set,
otherwise `DATA_DIR/relay.key`, generated on first start and persisted with
mode 0600.

## Errors and limits

An invalid `_graph` value closes the subscription with an `invalid:` reason.
`COUNT` rejects a graph filter with `_graph queries cannot be counted`.
`depth` above 16 is invalid. Traversal stops at the engine's result cap
(`TORLY_QUERY_LIMIT`, default 5000 nodes), and the response reports what was
collected.

A graph filter is a one-shot request, not a stored subscription: it is not
registered for live delivery. If a `REQ` carries more than one filter, the
first graph filter is executed and the remaining filters are ignored, matching
orly's behavior.

## Indexes

The traversal reads the same indexes orly and morly use, with every edge
written in both directions:

```
epg  event -> pubkey          peg  pubkey -> event
eeg  event -> event (out)     gee  event -> event (in)
ppg  pubkey -> pubkey (out)   gpp  pubkey -> pubkey (in)
```

Pubkeys are interned in `pks`/`spk`, so each edge stores five-byte serials
rather than full 32-byte keys. The direction byte distinguishes an author edge
(0), an outbound p-tag edge (1), and its inbound reverse (2). E-tag and
pubkey-pubkey edges use 0/1.

When an event references an e-tag target that is not stored yet, the edge is
deferred. Saving the target scans the tag index for `#e` references and creates
the missing edge, so replies can arrive before their root. Removal (NIP-09,
expiry, or replacement) scans the forward and reverse edge families and deletes
both halves.

An event carrying more than **256** `p`/`e` tags is not graph-indexed at all.
Partial truncation would change the meaning of a contact list or thread, so
such an event contributes no author, p-tag or e-tag edges. It remains stored and
available to normal NIP-01 queries. The limit is `maxGraphTags` in
`pkg/store/graph.go`.