Kademlia-Netzwerk

Kademlia-Netzwerk

Das Kademlia-Netzwerk ist ein verteiltes Peer-to-Peer-Protokoll und eine Implementierung einer Distributed Hash Table (DHT). Es wurde 2002 von Petar Maymounkov und David Mazieres entwickelt und bietet ein effizientes, robustes und ausfallsicheres Verfahren zur Speicherung und Suche von Daten in dezentralen Netzwerken.

Kademlia wird in vielen bekannten Systemen eingesetzt, darunter BitTorrent DHT, IPFS, I2P und Ethereum.

Grundprinzip

Kademlia organisiert Peers in einem dezentralen DHT-Netzwerk, in dem jeder Knoten eine eindeutige Node-ID besitzt. Daten werden unter Schlüsseln (Keys) gespeichert, die ebenfalls über Hashfunktionen (z. B. SHA-1, SHA-256) erzeugt werden. Das Netzwerk sorgt dafür, dass jeder Schlüssel bei den Peers gespeichert wird, deren IDs dem Schlüssel am nächsten sind.

[Key: 0xA1B2]  →  gespeichert bei den Knoten mit IDs nahe 0xA1B2

Eigenschaften

• Dezentral: Kein zentraler Server oder Index erforderlich
• Deterministisch: Jeder Schlüssel hat einen eindeutigen Ort im Netzwerk
• Effizient: Suchen erfolgen in O(log N) Schritten
• Fehlertolerant: Automatische Redundanz und Selbstheilung
• Symmetrisch: Gleicher Mechanismus für Speicherung und Suche

Adressierung und Distanzmaß

Kademlia definiert die „Nähe“ zwischen Knoten über die XOR-Distanz (bitweises exklusives Oder).

distance(A, B) = A XOR B

Diese Distanzmetrik hat besondere Eigenschaften:

• Symmetrisch: distance(A, B) = distance(B, A)
• Erzeugt eine totale Ordnung
• Einfach zu berechnen (bitweise Operation)

Die XOR-Distanz bestimmt, wie „nah“ zwei Knoten oder Schlüssel im DHT sind. Daten werden auf den Knoten gespeichert, deren IDs die geringste XOR-Distanz zum Schlüssel aufweisen.

Netzwerkstruktur

Jeder Knoten speichert Informationen über andere Knoten in sogenannten k-Buckets:

Begriff	Beschreibung
k-Bucket	Liste von bis zu *k* bekannten Knoten, deren IDs in einem bestimmten Distanzbereich liegen. Typischerweise ist *k = 20*.
Routing-Tabelle	Besteht aus mehreren k-Buckets, die zusammen den Adressraum abdecken.
Node-ID	Eindeutiger 160-Bit- oder 256-Bit-Hashwert, z. B. SHA-1(Key).

Beispielhafte Struktur:

Knoten-ID: 10110010...

k-Buckets:
0: [IDs, die sich im ersten Bit unterscheiden]
1: [IDs, die sich im zweiten Bit unterscheiden]
2: [IDs, die sich im dritten Bit unterscheiden]
...

Protokoll-Operationen

Kademlia definiert vier Hauptnachrichten für den Datenaustausch:

Befehl	Zweck
PING	Prüft, ob ein Knoten aktiv ist.
STORE	Speichert ein (Key, Value)-Paar auf einem Knoten.
FIND_NODE	Sucht Knoten, die einer bestimmten Node-ID am nächsten sind.
FIND_VALUE	Sucht den Wert zu einem bestimmten Key, falls vorhanden.

Jede dieser Operationen wird über UDP oder TCP ausgetauscht und kann parallelisiert werden.

Beispiel: Suchvorgang

1. Knoten A sucht Schlüssel 0xD1E2.
2. A berechnet XOR-Distanzen zu bekannten Knoten.
3. A fragt die α (z. B. 3) nächstgelegenen Knoten ab.
4. Diese liefern ihrerseits weitere, nähergelegene Knoten zurück.
5. Der Vorgang wiederholt sich iterativ, bis der Zielknoten erreicht ist.

→ Die Suche benötigt im Durchschnitt O(log N) Netzwerkabfragen.

Parameter

Typische Parameter für Kademlia-basierte Netzwerke:

Parameter	Bedeutung	Typischer Wert
α (alpha)	Anzahl paralleler Abfragen	3
k	Anzahl Knoten pro Bucket	20
ID-Länge	Länge der Node-ID	160 Bit (SHA-1)
TTL	Lebensdauer gespeicherter Daten	Einige Stunden bis Tage

Datenspeicherung

• Jeder Dateneintrag wird mit einem Key = hash(data) adressiert.
• Der Datensatz wird an die *k* Knoten gespeichert, die dem Key am nächsten sind.
• Redundanz und periodische Replikation sorgen für Datenerhalt, auch wenn Knoten offline gehen.

Selbstorganisation und Wartung

• Knoten pflegen ihre k-Buckets durch periodische PINGs.
• Abgelaufene Einträge werden ersetzt oder gelöscht.
• Neue Knoten finden Anschluss über Bootstrap-Knoten.
• Routing-Tabellen werden dynamisch angepasst (selbstheilendes Netzwerk).

Beispielhafte Implementierungen

• BitTorrent DHT: Verwendung von Kademlia für Peer-Suche (BEP 5).
• eMule / Kad-Netzwerk: Direkte Nutzung von Kademlia für Dateiindizierung.
• IPFS: Adressierung und Verteilung von Inhalten über DHT.
• Ethereum: Peer-Discovery für Blockchain-Knoten basiert auf modifiziertem Kademlia.
• I2P: Verwendung in verteilten anonymen Routing-Strukturen.

Vorteile

• Sehr effiziente Suche (O(log N))
• Kein zentraler Server notwendig
• Robust gegenüber Knotenausfällen
• Automatische Replikation und Fehlerkorrektur
• Gute Skalierbarkeit bei Millionen von Knoten

Nachteile

• Aufwendige Implementierung und Wartung
• Daten sind nicht dauerhaft garantiert (flüchtige Peers)
• Zusätzliche Sicherheitsmaßnahmen notwendig (z. B. gegen Sybil-Angriffe)
• Hoher Overhead bei häufig wechselnden Knoten (Churn)

Sicherheit

Kademlia selbst definiert keine Sicherheitsmechanismen, daher werden oft folgende Schutzmaßnahmen ergänzt:

• Sybil-Resistenz: Begrenzung gefälschter Node-IDs
• Signierte Nachrichten: Authentifizierung der Peers
• Rate Limiting: Schutz vor Flooding-Angriffen
• Replikation: Speicherung von Daten auf mehreren unabhängigen Knoten

Kademlia und DHTs

Kademlia ist eine der bekanntesten Implementierungen einer Distributed Hash Table (DHT). Es löst das Problem der dezentralen Schlüsselverwaltung, indem es Hashwerte im Netzwerk gleichmäßig verteilt und effiziente Routingtabellen nutzt.

DHT-System	Distanzmaß / Struktur	Beispielhafte Nutzung
Kademlia	XOR-Distanz, Binärbaum	BitTorrent, IPFS, Ethereum
Chord	Ringstruktur	Academic Networks
Pastry	Präfix-Routing	FreePastry, PAST
CAN	d-dimensionaler Koordinatenraum	Forschungsnetzwerke

Beispielhafte Pseudostruktur

Node A (ID: 0xA1B2)
  ├─ k-Bucket 0: [0xA1B3, 0xA1B4]
  ├─ k-Bucket 1: [0xA3C1, 0xB234]
  └─ k-Bucket 2: [0xD1E5, 0xF112]

Suche nach Key 0xA1B9 → Routing durch die k-nächsten Knoten.

Varianten und Weiterentwicklungen

• Kad (eMule): Vereinfachte Kademlia-Implementierung mit eigenem Hashschema
• Mainline DHT: BitTorrent-Version von Kademlia (BEP 5)
• Kademlia 2.0: Erweiterte Version mit besserer Redundanz und Sicherheit
• Kademlia-like DHTs: Grundlage vieler Blockchain-Netzwerke

Fazit

Kademlia ist eines der effizientesten und robustesten P2P-Protokolle zur Organisation verteilter Systeme. Es kombiniert einfache mathematische Konzepte (XOR-Distanz) mit hoher Skalierbarkeit und Selbstorganisation – und bildet die Grundlage vieler moderner dezentraler Anwendungen.

Siehe auch

• Distributed Hash Table (DHT)
• Peer-to-Peer-Netzwerke (P2P)
• BitTorrent
• Blockchain
• Distributed Systems
• Event-Driven Architecture

Quellen

• Petar Maymounkov, David Mazieres: *Kademlia: A Peer-to-Peer Information System Based on the XOR Metric*, 2002
• Original Paper (MIT)
• BitTorrent Enhancement Proposal BEP 5 – *DHT Protocol*
• Wikipedia: Kademlia
• Tanenbaum, Andrew S.: *Distributed Systems: Principles and Paradigms*