Kademlia-Netzwerk - Versionsgeschichte

PhilKa am 1. November 2025 um 12:54 Uhr

2025-11-01T12:54:32Z

← Nächstältere Version		Version vom 1. November 2025, 14:54 Uhr
Zeile 2:		Zeile 2:

	Das '''Kademlia-Netzwerk''' ist ein verteiltes Peer-to-Peer-Protokoll und eine Implementierung einer '''Distributed Hash Table (DHT)'''.		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.		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.		Kademlia wird in vielen bekannten Systemen eingesetzt, darunter ''BitTorrent DHT'', ''IPFS'', ''I2P'' und ''Ethereum''.

	== Grundprinzip ==		== Grundprinzip ==
	Kademlia organisiert Peers in einem dezentralen DHT-Netzwerk, in dem jeder Knoten eine eindeutige Node-ID besitzt.		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.		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.		Das Netzwerk sorgt dafür, dass jeder Schlüssel bei den Peers gespeichert wird, deren IDs dem Schlüssel am nächsten sind.
Zeile 16:		Zeile 16:

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

	== Adressierung und Distanzmaß ==		== Adressierung und Distanzmaß ==
	Kademlia definiert die „Nähe“ zwischen Knoten über die XOR-Distanz (bitweises exklusives Oder).		Kademlia definiert die „Nähe“ zwischen Knoten über die ''XOR-Distanz'' (bitweises exklusives Oder).

	<syntaxhighlight lang="text">		<syntaxhighlight lang="text">
Zeile 38:		Zeile 38:

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

	{\| class="wikitable"		{\| class="wikitable"
Zeile 88:		Zeile 88:
	</syntaxhighlight>		</syntaxhighlight>

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

	== Parameter ==		== Parameter ==
Zeile 105:		Zeile 105:

	== Datenspeicherung ==		== Datenspeicherung ==
	* Jeder Dateneintrag wird mit einem Key = hash(data) adressiert.		* Jeder Dateneintrag wird mit einem ''Key = hash(data)'' adressiert.
	* Der Datensatz wird an die k Knoten gespeichert, die dem Key am nächsten sind.		* 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.		* Redundanz und periodische Replikation sorgen für Datenerhalt, auch wenn Knoten offline gehen.
Zeile 116:		Zeile 116:

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

	== Vorteile ==		== Vorteile ==
Zeile 137:		Zeile 137:
	== Sicherheit ==		== Sicherheit ==
	Kademlia selbst definiert keine Sicherheitsmechanismen, daher werden oft folgende Schutzmaßnahmen ergänzt:		Kademlia selbst definiert keine Sicherheitsmechanismen, daher werden oft folgende Schutzmaßnahmen ergänzt:
	* Sybil-Resistenz: Begrenzung gefälschter Node-IDs		* ''Sybil-Resistenz:'' Begrenzung gefälschter Node-IDs
	* Signierte Nachrichten: Authentifizierung der Peers		* ''Signierte Nachrichten:'' Authentifizierung der Peers
	* Rate Limiting: Schutz vor Flooding-Angriffen		* ''Rate Limiting:'' Schutz vor Flooding-Angriffen
	* Replikation: Speicherung von Daten auf mehreren unabhängigen Knoten		* ''Replikation:'' Speicherung von Daten auf mehreren unabhängigen Knoten

	== Kademlia und DHTs ==		== Kademlia und DHTs ==
	Kademlia ist eine der bekanntesten Implementierungen einer [[Distributed Hash Table (DHT)]].		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.		Es löst das Problem der ''dezentralen Schlüsselverwaltung'', indem es Hashwerte im Netzwerk gleichmäßig verteilt und effiziente Routingtabellen nutzt.

	{\| class="wikitable"		{\| class="wikitable"
Zeile 169:		Zeile 169:

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

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

PhilKa: 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, *…“

2025-11-01T12:53:45Z

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**, *…“

Neue Seite

= 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.

<pre>
[Key: 0xA1B2] → gespeichert bei den Knoten mit IDs nahe 0xA1B2
</pre>

== 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).

<syntaxhighlight lang="text">
distance(A, B) = A XOR B
</syntaxhighlight>

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**:

{| class="wikitable"
! 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:
<pre>
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]
...
</pre>

== Protokoll-Operationen ==
Kademlia definiert vier Hauptnachrichten für den Datenaustausch:

{| class="wikitable"
! 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 ==
<syntaxhighlight lang="text">
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.
</syntaxhighlight>

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

== Parameter ==
Typische Parameter für Kademlia-basierte Netzwerke:
{| class="wikitable"
! 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.

{| class="wikitable"
! 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 ==
<syntaxhighlight lang="text">
Node A (ID: 0xA1B2)
├─ k-Bucket 0: [0xA1B3, 0xA1B4]
├─ k-Bucket 1: [0xA3C1, 0xB234]
└─ k-Bucket 2: [0xD1E5, 0xF112]
</syntaxhighlight>

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
* [https://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf Original Paper (MIT)]
* BitTorrent Enhancement Proposal BEP 5 – *DHT Protocol*
* [https://en.wikipedia.org/wiki/Kademlia Wikipedia: Kademlia]
* Tanenbaum, Andrew S.: *Distributed Systems: Principles and Paradigms*