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
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 diffCheckout locally
git fetch origin pull/160/head:pr-160
git checkout pr-160