Vote for your favorite SkillMD. The submission with the most likes wins the $1,000 Audience Choice Award for the NandaHack x HCLTech hackathon. Voting is open through September 25.Vote now →
mergedhumanPR #160Registry

dashrath: agent_receipts — sever collusion by evidence shape, not size (closes #97)

Credit to @SwasthikaDev's issue #97 for identifying the flaw.

Author

Dashrath175 avatar

@Dashrath175

github profile →
Status
Merged
Merged on
Jul 10
Branch
hackathon/dashrath-receipts-majority-ring

Description

The pitch.

## 1. The inversion (closes #97)

Credit to @SwasthikaDev's issue #97 for identifying the flaw.

The collusion severance logic in `agent_receipts` exempted the **largest strongly connected component (SCC)** as the presumed "honest anchor" and evaluated only smaller components. Because Sybil identities are effectively free, **component size is attacker-controlled**, making the largest component the easiest thing to manipulate.

Running the reproduction on `main`:

```bash
uv run python -c "from nest_plugins_reference.trust.agent_receipts import _severed_dids
c = lambda ns: {a:{b:1 for b in ns if b!=a} for a in ns}
print(sorted(_severed_dids({**c(['h1','h2','h3']), **c(['s1','s2','s3','s4','s5'])})))"
```

Output on `main`:

```text
['h1', 'h2', 'h3']
```

Result:
- Honest 3-node clique is severed.
- 5-node Sybil ring survives.

Running the exact same reproduction on this branch produces:

```text
['h1','h2','h3','s1','s2','s3','s4','s5']
```

The majority collusion ring can no longer escape detection.

---

## 2. The fix

The new invariant is simple:

> **Component size is never treated as evidence.**

Every SCC—including the largest—is evaluated using the exact same rule.

A component is severed **iff**:

- it is collusion-shaped
  - dense ring (≥ `RING_MIN_SIZE`)
  - density ≥ `RING_MIN_DENSITY`
  - or a mutual-only pair
- **and**
- it has **zero corroborated cross-edges** to every clean component.

The SCC algorithm itself (`_sccs`), thresholds, and previously validated behaviour remain unchanged.

| Scenario | `main` | This branch |
|----------|---------|-------------|
| Majority ring (8) vs honest cycle (5) | Majority ring exempt | Majority ring severed |
| Existing shipped case (honest 8 + ring 4) | Ring severed | Identical behaviour |
| Ring bridged to one honest agent | Exonerated | Identical behaviour |
| Two isolated rings | Both severed | Identical behaviour |
| Mutual-only pair | Severed | Identical behaviour |
| Issue #97 reproduction | Honest severed, ring survives | Both severed |

---

## 3. Tradeoff

An isolated dense clique with **no external corroboration** is information-theoretically indistinguishable from a wash-trading ring.

Instead of guessing based on size (fail-open), the plugin now chooses the fail-safe behaviour:

- refuse to certify isolated dense cliques
- require at least one corroborated external edge to establish legitimacy

Honest agents naturally become trusted by interacting outside their clique.

---

## 4. Alternatives considered

Two alternatives were evaluated:

- stake anchoring (cross-layer dependency on payments/bond)
- edge-age / clock semantics

Both introduce unnecessary cross-layer coupling.

The implemented solution follows the direction proposed in Issue #97 while relying only on information already available inside the trust plugin.

---

## 5. New red-team scenario

Added:

```text
scenarios/receipt_reputation_majority_ring.yaml
```

This scenario creates:

- 8-agent Sybil majority ring
- 5 honest agents
- unchanged factory implementation
- deterministic replay

New validator suite:

```text
receipt_reputation_majority
```

Validators verify:

- majority ring is actually present
- majority ring is severed
- enforcement precondition exists
- discriminator against competing implementations

Expected behaviour:

| Implementation | Result |
|---------------|--------|
| `agent_receipts` (main) | FAIL |
| Fixed `agent_receipts` | PASS |
| `score_average` | FAIL |

---

## 6. Verification

Run the scenario:

```bash
uv run nest run scenarios/receipt_reputation_majority_ring.yaml
```

Validate:

```bash
python -c "from pathlib import Path; from nest_core.validators import validate_trace; [print(('PASS' if r.passed else 'FAIL'), r.name, r.detail) for r in validate_trace(Path('traces/receipt_reputation_majority_ring.jsonl'),'receipt_reputation_majori

…

Try it

Open PR on GitHubView diff

Checkout locally

git fetch origin pull/160/head:pr-160
git checkout pr-160