enhancement(kad-dht): add disjoint lookup paths to find_closest_peers_network
Nobody has claimed this yet.
- Dominant language
- Python
- Stars
- 624
- Forks
- 256
- Avg merge
- 1d 34m
- Merged PRs (30d)
- 47
Description
## Problem
`find_closest_peers_network` in `libp2p/kad_dht/peer_routing.py` runs a single iterative lookup with one shared candidate pool and one shared queried-peers set. Two weaknesses follow:
1. **Deterministic candidate selection**: each round always picks the ALPHA XOR-closest unqueried peers. An attacker who places Sybil peers at the closest XOR positions gets queried deterministically every round, and can steer the entire lookup path from the first hop.
2. **Single path**: all ALPHA parallel queries share one candidate pool. If an attacker controls a peer early in the path, that peer's response shapes the entire subsequent search.
rust-libp2p has shipped disjoint query paths since v0.20 as `disjoint_query_paths` (off by default, path count = ALPHA/parallelism).
**Note on scope**: disjoint paths do NOT protect against an attacker who *already occupies the closest-K bucket* for the target key — all paths converge on the same XOR terminus regardless. That problem is addressed separately by subnet diversity (#1383). This issue is about hardening *intermediate hops* against path-level steering.
## Proposal
### Part 1 — Randomized candidate selection per round (smaller, ships now)
Instead of always picking the strictly first ALPHA unqueried peers:
```python
# before
peers_to_query = [p for p in closest_peers if p not in queried_peers][:ALPHA]
# after
candidates = [p for p in closest_peers if p not in queried_peers][:count]
peers_to_query = random.sample(candidates, min(ALPHA, len(candidates)))
```
Draws randomly from the closest-K window each round. Convergence is preserved (all candidates are already within the K closest known peers); attacker loses guaranteed first-query slot. Already landed in local branch.
### Part 2 — True disjoint paths (larger, separate PR)
1. Partition the initial closest-peer candidate set into `d` disjoint subsets (default `d = 1`, preserving current behavior).
2. Run `d` parallel, isolated iterative lookups — separate candidate list and `queried_peers` tracker per path.
3. No peer crosses between paths mid-lookup.
4. Merge results by XOR distance at the end.
5. Expose `disjoint_paths: int = DISJOINT_LOOKUP_PATHS` on `KadDHT.__init__`.
## Scope
**Part 1** (ready):
- `libp2p/kad_dht/peer_routing.py` — one-line change to candidate selection
- `libp2p/kad_dht/common.py` — `DISJOINT_LOOKUP_PATHS = 1` placeholder constant
**Part 2** (discussion needed):
- `libp2p/kad_dht/peer_routing.py` — refactor `find_closest_peers_network` to support isolated path state
- `libp2p/kad_dht/kad_dht.py` — expose `disjoint_paths` param
- `tests/examples/attack_simulation/` — update sybil/eclipse simulations to use real `KBucket`/`RoutingTable` instances (currently they use Python-string fake IDs and never touch the actual routing table, so they can't validate a real fix)
## Open questions for maintainers
1. Should `disjoint_paths` be exposed on `KadDHT.__init__` now (with `d=1` no-op default) so the API surface stabilises before the implementation lands?
2. What's the right default for `d` when Part 2 ships — match rust-libp2p (ALPHA=3 paths) or start at 2?
3. The attack simulation tests (`tests/examples/attack_simulation/sybil_attack/`, `eclipse_attack/`) use string fake IDs and skip the real routing table. Should fixing those be bundled with Part 2 or tracked separately?
/cc @acul71 @sumanjeet0012 @asmit27rai — you've been most active on the kad_dht path recently
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in libp2p/kad_dht/peer_routing.py and read find_closest_peers_network, then inspect DISJOINT_LOOKUP_PATHS in libp2p/kad_dht/common.py and KadDHT.__init__ in kad_dht.py. Review the sybil and eclipse simulations under tests/examples/attack_simulation/ to understand their current fake-ID setup. Done means the chosen path behavior is implemented, configuration is exposed as agreed, and the simulations or related tests validate it.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- distributed-systems, networking, security
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100