next.orly.dev/docs/GRAPH_IMPLEMENTATION_PHASES.md

Graph Query Implementation Phases

This document provides a clear breakdown of implementation phases for NIP-XX Graph Queries.

---

Phase 0: Filter Extension Parsing (Foundation) ✅ COMPLETE

Goal: Enable the nostr library to correctly "ignore" unknown filter fields per NIP-01, while preserving them for relay-level processing.

Deliverables (Completed)

• Modified filter.F struct with Extra field
• Modified Unmarshal() to skip unknown keys
• skipJSONValue() helper function
• graph.ExtractFromFilter() function
• Integration in handle-req.go
• Rate limiter with token bucket for graph queries

---

Phase 1: E-Tag Graph Index ✅ COMPLETE

Goal: Create bidirectional indexes for event-to-event references (e-tags).

Index Key Structure

Event-Event Graph (Forward): eeg
  eeg|source_event_serial(5)|target_event_serial(5)|kind(2)|direction(1) = 16 bytes

Event-Event Graph (Reverse): gee
  gee|target_event_serial(5)|kind(2)|direction(1)|source_event_serial(5) = 16 bytes

Direction Constants

• EdgeDirectionETagOut = 0 - Event references another event (outbound)
• EdgeDirectionETagIn = 1 - Event is referenced by another (inbound)

Deliverables (Completed)

• Index key definitions for eeg/gee (pkg/database/indexes/keys.go)
• Direction constants for e-tags (pkg/database/indexes/types/letter.go)
• E-tag graph creation in SaveEvent (pkg/database/save-event.go)
• Tests for e-tag graph creation (pkg/database/etag-graph_test.go)

Key Bug Fix: Buffer reuse in transaction required copying key bytes before writing second key to prevent overwrite.

---

Phase 2: Graph Traversal Primitives ✅ COMPLETE

Goal: Implement pure index-based graph traversal functions.

2.1 Core traversal functions

File: pkg/database/graph-traversal.go

// Core primitives (no event decoding required)
func (d *D) GetPTagsFromEventSerial(eventSerial *types.Uint40) ([]*types.Uint40, error)
func (d *D) GetETagsFromEventSerial(eventSerial *types.Uint40) ([]*types.Uint40, error)
func (d *D) GetReferencingEvents(targetSerial *types.Uint40, kinds []uint16) ([]*types.Uint40, error)
func (d *D) GetFollowsFromPubkeySerial(pubkeySerial *types.Uint40) ([]*types.Uint40, error)
func (d *D) GetFollowersOfPubkeySerial(pubkeySerial *types.Uint40) ([]*types.Uint40, error)
func (d *D) GetPubkeyHexFromSerial(serial *types.Uint40) (string, error)
func (d *D) GetEventIDFromSerial(serial *types.Uint40) (string, error)

2.2 GraphResult struct

File: pkg/database/graph-result.go

// GraphResult contains depth-organized traversal results
type GraphResult struct {
    PubkeysByDepth  map[int][]string      // depth -> pubkeys first discovered at that depth
    EventsByDepth   map[int][]string      // depth -> events discovered at that depth
    FirstSeenPubkey map[string]int        // pubkey hex -> depth where first seen
    FirstSeenEvent  map[string]int        // event hex -> depth where first seen
    TotalPubkeys    int
    TotalEvents     int
    InboundRefs     map[uint16]map[string][]string  // kind -> target -> []referencing_ids
    OutboundRefs    map[uint16]map[string][]string  // kind -> source -> []referenced_ids
}

func (r *GraphResult) ToDepthArrays() [][]string       // For pubkey results
func (r *GraphResult) ToEventDepthArrays() [][]string  // For event results
func (r *GraphResult) GetInboundRefsSorted(kind uint16) []RefAggregation
func (r *GraphResult) GetOutboundRefsSorted(kind uint16) []RefAggregation

Deliverables (Completed)

• Core traversal functions in graph-traversal.go
• GraphResult struct with ToDepthArrays() and ToEventDepthArrays()
• RefAggregation struct with sorted accessors
• Tests in graph-result_test.go and graph-traversal_test.go

---

Phase 3: High-Level Traversals ✅ COMPLETE

Goal: Implement the graph query methods (follows, followers, mentions, thread).

3.1 Follow graph traversal

File: pkg/database/graph-follows.go

// TraverseFollows performs BFS traversal of the follow graph
// Returns pubkeys grouped by first-discovered depth (no duplicates across depths)
func (d *D) TraverseFollows(seedPubkey []byte, maxDepth int) (*GraphResult, error)

// TraverseFollowers performs BFS traversal to find who follows the seed pubkey
func (d *D) TraverseFollowers(seedPubkey []byte, maxDepth int) (*GraphResult, error)

// Hex convenience wrappers
func (d *D) TraverseFollowsFromHex(seedPubkeyHex string, maxDepth int) (*GraphResult, error)
func (d *D) TraverseFollowersFromHex(seedPubkeyHex string, maxDepth int) (*GraphResult, error)

3.2 Other traversals

File: pkg/database/graph-mentions.go

func (d *D) FindMentions(pubkey []byte, kinds []uint16) (*GraphResult, error)
func (d *D) FindMentionsFromHex(pubkeyHex string, kinds []uint16) (*GraphResult, error)
func (d *D) FindMentionsByPubkeys(pubkeySerials []*types.Uint40, kinds []uint16) (*GraphResult, error)

File: pkg/database/graph-thread.go

func (d *D) TraverseThread(seedEventID []byte, maxDepth int, direction string) (*GraphResult, error)
func (d *D) TraverseThreadFromHex(seedEventIDHex string, maxDepth int, direction string) (*GraphResult, error)
func (d *D) GetThreadReplies(eventID []byte, kinds []uint16) (*GraphResult, error)
func (d *D) GetThreadParents(eventID []byte) (*GraphResult, error)

3.3 Ref aggregation

File: pkg/database/graph-refs.go

func (d *D) AddInboundRefsToResult(result *GraphResult, depth int, kinds []uint16) error
func (d *D) AddOutboundRefsToResult(result *GraphResult, depth int, kinds []uint16) error
func (d *D) CollectRefsForPubkeys(pubkeySerials []*types.Uint40, refKinds []uint16, eventKinds []uint16) (*GraphResult, error)

Deliverables (Completed)

• TraverseFollows with early termination (2 consecutive empty depths)
• TraverseFollowers
• FindMentions and FindMentionsByPubkeys
• TraverseThread with bidirectional traversal
• Inbound/Outbound ref aggregation
• Tests in graph-follows_test.go

---

Phase 4: Graph Query Handler and Response Generation ✅ COMPLETE

Goal: Wire up the REQ handler to execute graph queries and generate relay-signed response events.

4.1 Response Event Generation

Key Design Decision: All graph query responses are returned as relay-signed events, enabling:

• Standard client validation (no special handling)
• Result caching and storage on relays
• Cryptographic proof of origin

4.2 Response Kinds (Implemented)

Kind	Name	Description
39000	Graph Follows	Response for follows/followers queries
39001	Graph Mentions	Response for mentions queries
39002	Graph Thread	Response for thread traversal queries

4.3 Implementation Files

New files:

• pkg/protocol/graph/executor.go - Executes graph queries and generates signed responses
• pkg/database/graph-adapter.go - Adapts database to graph.GraphDatabase interface

Modified files:

• app/server.go - Added graphExecutor field
• app/main.go - Initialize graph executor on startup
• app/handle-req.go - Execute graph queries and return results

4.4 Response Format (Implemented)

The response is a relay-signed event with JSON content:

type ResponseContent struct {
    PubkeysByDepth [][]string `json:"pubkeys_by_depth,omitempty"`
    EventsByDepth  [][]string `json:"events_by_depth,omitempty"`
    TotalPubkeys   int        `json:"total_pubkeys,omitempty"`
    TotalEvents    int        `json:"total_events,omitempty"`
}

Example response event:

{
    "kind": 39000,
    "pubkey": "<relay_identity_pubkey>",
    "created_at": 1704067200,
    "tags": [
        ["method", "follows"],
        ["seed", "<seed_pubkey_hex>"],
        ["depth", "2"]
    ],
    "content": "{\"pubkeys_by_depth\":[[\"pk1\",\"pk2\"],[\"pk3\",\"pk4\"]],\"total_pubkeys\":4}",
    "sig": "<relay_signature>"
}

### Deliverables (Completed)
- [x] Graph executor with query routing (`pkg/protocol/graph/executor.go`)
- [x] Response event generation with relay signature
- [x] GraphDatabase interface and adapter
- [x] Integration in `handle-req.go`
- [x] All tests passing

---

## Phase 5: Migration & Configuration

**Goal**: Enable backfilling and configuration.

### 5.1 E-tag graph backfill migration

**File**: `pkg/database/migrations.go`

```go
func (d *D) MigrateETagGraph() error {
    // Iterate all events
    // Extract e-tags
    // Create eeg/gee edges for targets that exist
}

5.2 Configuration

File: app/config/config.go

Add:

• ORLY_GRAPH_QUERIES_ENABLED - enable/disable feature
• ORLY_GRAPH_MAX_DEPTH - maximum traversal depth (default 16)
• ORLY_GRAPH_RATE_LIMIT - queries per minute per connection

5.3 NIP-11 advertisement

Update relay info document to advertise support and limits.

Deliverables

• Backfill migration
• Configuration options
• NIP-11 advertisement
• Documentation updates

---

Summary: Implementation Order

Phase	Description	Status	Dependencies
0	Filter extension parsing	✅ Complete	None
1	E-tag graph index	✅ Complete	Phase 0
2	Graph traversal primitives	✅ Complete	Phase 1
3	High-level traversals	✅ Complete	Phase 2
4	Graph query handler	✅ Complete	Phase 3
5	Migration & configuration	Pending	Phase 4

---

Response Format Summary

Graph-Only Query (no kinds filter)

Request:

["REQ", "sub", {"_graph": {"method": "follows", "seed": "abc...", "depth": 2}}]

Response: Single signed event with depth arrays

["EVENT", "sub", {
    "kind": 39000,
    "pubkey": "<relay_pubkey>",
    "content": "[[\"depth1_pk1\",\"depth1_pk2\"],[\"depth2_pk3\",\"depth2_pk4\"]]",
    "tags": [["d","follows:abc...:2"],["method","follows"],["seed","abc..."],["depth","2"]],
    "sig": "..."
}]
["EOSE", "sub"]

Query with Event Filters

Request:

["REQ", "sub", {"_graph": {"method": "follows", "seed": "abc...", "depth": 2}, "kinds": [0]}]

Response: Graph result + events in depth order

["EVENT", "sub", <kind-39000 graph result>]
["EVENT", "sub", <kind-0 for depth-1 pubkey>]
["EVENT", "sub", <kind-0 for depth-1 pubkey>]
["EVENT", "sub", <kind-0 for depth-2 pubkey>]
...
["EOSE", "sub"]

Query with Reference Aggregation

Request:

["REQ", "sub", {"_graph": {"method": "follows", "seed": "abc...", "depth": 1, "inbound_refs": [{"kinds": [7]}]}}]

Response: Graph result + refs sorted by count (descending)

["EVENT", "sub", <kind-39000 with ref summaries>]
["EVENT", "sub", <kind-39001 target with 523 refs>]
["EVENT", "sub", <kind-39001 target with 312 refs>]
["EVENT", "sub", <kind-39001 target with 1 ref>]
["EOSE", "sub"]

---

Testing Strategy

Unit Tests

• Filter parsing with unknown fields
• Index key encoding/decoding
• Traversal primitives
• Result depth array generation
• Reference sorting

Integration Tests

• Full graph query round-trip
• Response format validation
• Signature verification
• Backward compatibility (non-graph REQs still work)

Performance Tests

• Traversal latency at various depths
• Memory usage for large graphs
• Comparison with event-decoding approach