Kademlia-Netzwerk

Aus dev.kaibel.net
Version vom 1. November 2025, 13:53 Uhr von PhilKa (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „= 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**, *…“)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen

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

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*
Abgerufen von „http://dev.kaibel.net/index.php?title=Kademlia-Netzwerk&oldid=103“