# Dendrite (Matrix) — CWE-407 Disclosure Brief
**2026-03-27 · Patch available — awaiting upstream merge**

## Finding

Two O(n²) defects in Dendrite, the second-generation Matrix homeserver written in Go. One fires on every event write during prev-event ID deduplication; the other fires during backfill with an O(E×P) extremity scan. Measured at 16× and 444× respectively. Patches ready for upstream review.

## The Defects

**dendrite-0001 (PATCHED — HIGH):** `storage_consumer.go:243`

```go
// Inside WriteEvent() — per stored event:
// Double loop over PrevEventIDs() × prevEvents:
for _, prevID := range event.PrevEventIDs() {
    for _, prev := range prevEvents {  // O(P×E) nested scan
        if prev.EventID() == prevID {
            ...
        }
    }
}
```

Nested loop over prev event IDs. For P prev event IDs and E events: **O(P × E) per write**. **Measured ratio: 16×.**

**dendrite-0002 (PATCHED — HIGH):** `perform_backfill.go:438`

```go
// Inside backfill — finding prev-event extremities:
for _, bwExtrem := range bwExtrems {
    for _, prevID := range event.PrevEventIDs() {  // O(E×P) total
        if bwExtrem == prevID { ... }
    }
}
```

O(E×P) nested scan over backward extremities and prev event IDs during backfill. **Measured ratio: 444×.**

## Complexity Proof

**dendrite-0001:** For P=16 prev event IDs, E events:
- O(P×E) per `WriteEvent`
- **16× measured ratio.**

**dendrite-0002:** For E extremities and P=444 prev event IDs per backfill:
- O(E×P) total backfill scan
- Fixed: reverse `map[string]struct{}` for O(E) lookup
- **444× measured ratio.**

## Impact

All Dendrite homeserver deployments. Dendrite is the recommended Matrix homeserver for new deployments and powers smaller Matrix instances. dendrite-0001 fires on every event stored — the core Matrix operation. dendrite-0002 fires on every backfill request (room join with history, pagination). Rooms with long event chains and many backward extremities (after network partitions) hit dendrite-0002 worst case.

## The Fix

**dendrite-0001:** Pre-build `map[string]PDU` from `prevEvents` before the outer loop:

```go
// Before: O(P×E) nested scan
// After: O(P+E) with pre-built map
prevEventMap := make(map[string]PDU, len(prevEvents))
for _, prev := range prevEvents {
    prevEventMap[prev.EventID()] = prev
}
// Then: prevEventMap[prevID] — O(1) lookup
```

**dendrite-0002:** Pre-build `map[string]struct{}` from `bwExtrems` before the inner loop.

## Patch

`defects/dendrite/patch/dendrite-0001-0002-backfill-map.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your event storage and backfill test suites.
3. Assess CVE eligibility — dendrite-0002 measured at 444× during backfill.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

Contact: see cover email. This brief is confidential until coordinated disclosure.
