Kademlia

Kademlia (DHT) ist eine verteilte Hash-Tabelle für dezentrale Peer-to-Peer-Computernetzwerke, die 2002 von Petar Maymounkov und David Mazières entwickelt wurde. Sie spezifiziert die Struktur des Netzwerks und den Austausch von Informationen durch Knoten-Lookups. Kademlia-Knoten kommunizieren untereinander über UDP. Ein virtuelles oder Overlay-Netzwerk wird von den Teilnehmerknoten gebildet. Jeder Knoten wird durch eine Nummer oder eine Knoten-ID identifiziert. Die Knoten-ID dient nicht nur zur Identifikation, sondern der Kademlia-Algorithmus verwendet die Knoten-ID, um Werte zu lokalisieren (normalerweise Datei-Hashes oder Schlüsselwörter). Tatsächlich stellt die Knoten-ID eine direkte Zuordnung zu Datei-Hashes bereit und dieser Knoten speichert Informationen darüber, wo die Datei oder Ressource zu erhalten ist.

Bei der Suche nach einem Wert muss der Algorithmus den zugehörigen Schlüssel kennen und das Netzwerk in mehreren Schritten untersuchen. In jedem Schritt werden Knoten gefunden, die näher am Schlüssel liegen, bis der kontaktierte Knoten den Wert zurückgibt oder keine näheren Knoten gefunden werden. Dies ist sehr effizient: Wie viele andere DHTs kontaktiert Kademlia nur Knoten während der Suche von insgesamt -Knoten im System.

Weitere Vorteile ergeben sich insbesondere in der dezentralen Struktur, die den Widerstand gegen einen Denial-of-Service-Angriff (DDoS) erhöht. Selbst wenn eine ganze Gruppe von Knoten überflutet wird, hat dies begrenzte Auswirkungen auf die Netzwerkverfügbarkeit, da das Netzwerk sich selbst wieder herstellt, indem es das Netzwerk um diese “Löcher” herum strickt.

Systemdetails

Die Peer-to-Peer-Filesharing-Netzwerke der ersten Generation, wie z. B. Napster, beruhten auf einer zentralen Datenbank, um Nachschlagevorgänge im Netzwerk zu koordinieren. Peer-to-Peer-Netzwerke der zweiten Generation, wie z. B. Gnutella, verwendeten Flooding, um Dateien zu suchen, und durchsuchten jeden Knoten im Netzwerk. Die Peer-to-Peer-Netzwerke der dritten Generation verwenden verteilte Hash-Tabellen, um Dateien im Netzwerk nachzuschlagen. Verteilte Hash-Tabellen speichern Ressourcenstandorte im gesamten Netzwerk. Ein Hauptkriterium für diese Protokolle ist das schnelle Auffinden der gewünschten Knoten.

Kademlia verwendet eine “Distanz” -Berechnung zwischen zwei Knoten. Diese Entfernung wird als die Exklusiv- oder (XOR) der zwei Knoten-IDs berechnet, wobei das Ergebnis als eine ganze Zahl genommen wird. Schlüssel und Knoten-IDs haben das gleiche Format und die gleiche Länge, so dass die Entfernung genau so berechnet werden kann. Die Knoten-ID ist typischerweise eine große Zufallszahl, die mit dem Ziel ausgewählt wird, für einen bestimmten Knoten eindeutig zu sein. Es kann und kann passieren, dass geographisch weit getrennte Knoten – beispielsweise aus Deutschland und Australien – “Nachbarn” sein können, wenn sie ähnliche zufällige Knoten-IDs gewählt haben.

Exklusiv oder wurde gewählt, weil es als Abstandsfunktion zwischen allen Knoten-IDs fungiert. Speziell:

  • der Abstand zwischen einem Knoten und sich selbst ist Null
  • es ist symmetrisch: die von A nach B und von B nach A berechneten “Distanzen” sind gleich
  • Es folgt die Dreiecksungleichung: Gegeben A, B und C sind Eckpunkte (Punkte) eines Dreiecks, dann ist der Abstand von A nach B kürzer als (oder gleich) die Summe der Entfernung von A nach C und der Abstand von C zu B.

Diese drei Bedingungen sind ausreichend, um sicherzustellen, dass alle wesentlichen, wichtigen Merkmale einer “echten” Entfernungsfunktion ausgeschlossen oder erfasst werden, während sie billig und einfach zu berechnen sind. Wegen dieser statistischen Verteilung wählt Kademlia lange verbundene Knoten aus, um in den k-Buckets gespeichert zu bleiben. Dies erhöht die Anzahl von bekannten gültigen Knoten zu einem bestimmten Zeitpunkt in der Zukunft und sorgt für ein stabileres Netzwerk.

Wenn ein k-Bucket voll ist und ein neuer Knoten für diesen k-Bucket entdeckt wird, wird der zuletzt gesehene Knoten im k-Bucket PINGed. Wenn festgestellt wird, dass der Knoten noch aktiv ist, wird der neue Knoten in einer sekundären Liste, einem Ersatzcache, platziert. Der Ersetzungscache wird nur verwendet, wenn ein Knoten im k-Bucket nicht mehr reagiert. Mit anderen Worten: neue Knoten werden nur verwendet, wenn ältere Knoten verschwinden.

Protokollnachrichten

Kademlia hat vier Nachrichten.

  • PING – um zu überprüfen, ob ein Knoten noch am Leben ist.
  • STORE – Speichert ein (Schlüssel, Wert) Paar in einem Knoten.
  • FIND_NODE – Der Empfänger der Anfrage gibt die k Knoten in seinen eigenen Buckets zurück, die dem angeforderten Schlüssel am nächsten sind.
  • FIND_VALUE – Wie FIND_NODE, aber wenn der Empfänger der Anfrage den angeforderten Schlüssel in seinem Geschäft hat, wird der entsprechende Wert zurückgegeben.

Jede RPC-Nachricht enthält einen zufälligen Wert vom Initiator. Dies stellt sicher, dass wenn die Antwort empfangen wird, diese der zuvor gesendeten Anfrage entspricht.

Lokalisieren von Knoten

Node-Lookups können asynchron fortfahren. Die Menge der gleichzeitigen Nachschlagevorgänge wird mit α bezeichnet und ist typischerweise drei. Ein Knoten initiiert eine FIND_NODE-Anfrage, indem er die α-Knoten in seinen eigenen k-Buckets abfragt, die dem gewünschten Schlüssel am nächsten sind. Wenn diese Empfängerknoten die Anforderung empfangen, suchen sie in ihren k-Buckets und geben die k nächsten Knoten an den gewünschten Schlüssel zurück, den sie kennen. Der Anforderer aktualisiert eine Ergebnisliste mit den Ergebnissen (Knoten-IDs), die er empfängt, und behält die k besten Werte (die k Knoten, die näher am gesuchten Schlüssel sind), die auf Abfragen antworten. Dann wählt der Anforderer diese k besten Ergebnisse aus und gibt die Anfrage an sie aus, und wiederholt diesen Vorgang immer wieder. Da jeder Knoten ein besseres Wissen über seine eigene Umgebung hat als jeder andere Knoten, werden die empfangenen Ergebnisse andere Knoten sein, die sich immer näher und näher an dem gesuchten Schlüssel befinden. Die Iterationen werden fortgesetzt, bis keine Knoten zurückgegeben werden, die näher als die besten vorherigen Ergebnisse sind. Wenn die Iterationen aufhören, sind die besten k Knoten in der Ergebnisliste diejenigen im gesamten Netzwerk, die dem gewünschten Schlüssel am nächsten sind.

Die Knoteninformationen können mit Round-Trip-Zeiten oder RTT erweitert werden. Diese Information wird verwendet, um ein Zeitlimit auszuwählen, das für jeden konsultierten Knoten spezifisch ist. Wenn eine Abfrage das Zeitlimit überschreitet, kann eine andere Abfrage eingeleitet werden, die gleichzeitig keine α-Abfragen übertrifft.

Ressourcen finden

Informationen werden durch Zuordnen zu einem Schlüssel lokalisiert. Ein Hash wird normalerweise für die Karte verwendet. Die Speicherknoten haben aufgrund einer vorherigen STORE-Nachricht Informationen. Das Auffinden eines Werts erfolgt auf die gleiche Weise wie das Suchen der nächstgelegenen Knoten zu einem Schlüssel, außer dass die Suche beendet wird, wenn ein Knoten den angeforderten Wert in seinem Geschäft hat und diesen Wert zurückgibt.

Die Werte werden an mehreren Knoten (k von ihnen) gespeichert, um zu ermöglichen, dass Knoten kommen und gehen und immer noch den Wert haben, der in einem Knoten verfügbar ist. In regelmäßigen Abständen wird ein Knoten, der einen Wert speichert, das Netzwerk untersuchen, um die k-Knoten zu finden, die nahe am Schlüsselwert liegen, und den Wert darauf replizieren. Dies kompensiert verschwundene Knoten.

Bei populären Werten, die viele Anfragen haben können, wird die Belastung in den Speicherknoten verringert, indem ein Retriever diesen Wert in einem Knoten nahe, aber außerhalb der k nächsten speichert. Diese neue Speicherung wird als Cache bezeichnet. Auf diese Weise wird der Wert je nach Anzahl der Anforderungen weiter und weiter vom Schlüssel entfernt gespeichert. Auf diese Weise können beliebte Suchanfragen schneller gefunden werden. Da der Wert von Knoten zurückgegeben wird, die weiter vom Schlüssel entfernt sind, werden mögliche “Hotspots” vermieden. Caching-Knoten löschen den Wert nach einer bestimmten Zeit abhängig von ihrer Entfernung vom Schlüssel.

Einige Implementierungen haben weder Replikation noch Caching. Der Zweck besteht darin, alte Informationen schnell aus dem System zu entfernen. Der Knoten, der die Datei bereitstellt, aktualisiert die Informationen regelmäßig im Netzwerk (führt FIND_NODE- und STORE-Nachrichten aus). Wenn alle Knoten, die die Datei enthalten, offline gehen, aktualisiert niemand seine Werte (Quellen und Schlüsselwörter) und die Informationen werden schließlich aus dem Netzwerk verschwinden.

Dem Netzwerk beitreten

Ein Knoten, der dem Netz beitreten möchte, muss zuerst einen Bootstrap-Prozess durchlaufen. In dieser Phase muss der beitretende Knoten die IP-Adresse und den Port eines anderen Knotens – eines Bootstrap-Knotens (der vom Benutzer oder von einer gespeicherten Liste erhalten wird) – kennen, der bereits am Kademlia-Netzwerk teilnimmt. Wenn der verbindende Knoten noch nicht am Netzwerk teilgenommen hat, berechnet er eine zufällige ID-Nummer, die keinem anderen Knoten bereits zugewiesen sein sollte. Es verwendet diese ID bis zum Verlassen des Netzwerks.

Der verbindende Knoten fügt den Bootstrap-Knoten in eines seiner k-Buckets ein. Der verbindende Knoten führt dann eine FIND_NODE seiner eigenen ID gegen den Bootstrap-Knoten (den einzigen anderen Knoten, den er kennt) aus. Das “Selbst-lookup” füllt die k-Buckets anderer Knoten mit der neuen Knoten-ID und füllt die k-Buckets des Beitrittsknotens mit den Knoten im Pfad zwischen ihm und dem Bootstrap-Knoten. Danach aktualisiert der beitretende Knoten alle k-Buckets, die weiter entfernt sind als der k-Bucket, in den der Bootstrap-Knoten fällt. Diese Aktualisierung ist nur ein Nachschlagen eines zufälligen Schlüssels, der innerhalb dieses k-Bucket-Bereichs liegt.

Anfänglich haben Knoten einen k-Bucket. Wenn der K-Eimer voll ist, kann er geteilt werden. Die Aufteilung erfolgt, wenn der Bereich der Knoten im k-Bucket die eigene ID des Knotens überspannt (Werte nach links und rechts in einem binären Baum). Kademlia lockert sogar diese Regel für den einen “engsten Knoten” k-Bucket, weil typischerweise ein einzelner Bucket dem Abstand entspricht, wo alle Knoten, die diesem Knoten am nächsten sind, mehr als k sind, und wir wollen es um sie alle zu kennen. Es kann sich herausstellen, dass ein hochgradig unsymmetrischer binärer Teilbaum in der Nähe des Knotens existiert. Wenn k 20 ist und es 21+ Knoten mit einem Präfix “xxx0011 …..” gibt und der neue Knoten “xxx000011001” ist, kann der neue Knoten mehrere k-Buckets für die anderen 21+ Knoten enthalten. Dies stellt sicher, dass das Netzwerk alle Knoten in der nächstgelegenen Region kennt.

Beschleunigte Suche

Kademlia verwendet eine XOR-Metrik, um die Entfernung zu definieren. Zwei Knoten-IDs oder eine Knoten-ID und ein Schlüssel werden XOR-verknüpft und das Ergebnis ist der Abstand zwischen ihnen. Für jedes Bit gibt die XOR-Funktion Null zurück, wenn die zwei Bits gleich sind, und eins, wenn die zwei Bits verschieden sind. XOR metrische Abstände halten die Dreiecksungleichung: Gegeben A, B und C sind Eckpunkte (Punkte) eines Dreiecks, dann ist der Abstand von A nach B kürzer als (oder gleich) die Summe der Entfernung von A nach C nach B.

Die XOR-Metrik ermöglicht es Kademlia, Routing-Tabellen über einzelne Bits hinaus zu erweitern. Gruppen von Bits können in k-Buckets platziert werden. Die Gruppe von Bits wird als Präfix bezeichnet. Für ein m-Bit-Präfix gibt es 2m-1 k-Buckets. Der fehlende k-Bucket ist eine weitere Erweiterung des Routingbaums, der die Knoten-ID enthält. Ein m-Bit-Präfix reduziert die maximale Anzahl von Suchvorgängen von log2 n auf log2m n. Dies sind Höchstwerte, und der Durchschnittswert wird viel geringer sein, was die Wahrscheinlichkeit erhöht, einen Knoten in einem k-Bucket zu finden, der mehr Bits teilt als nur das Präfix mit dem Zielschlüssel.

Knoten können Mischungen von Präfixen in ihrer Routing-Tabelle verwenden, z. B. das von eMule verwendete Kad-Netzwerk. Das Kademlia-Netzwerk könnte sogar in Routing-Tabellen-Implementierungen heterogen sein, auf Kosten der komplizierteren Analyse von Suchvorgängen.

Akademische Bedeutung

Während die XOR-Metrik nicht benötigt wird, um Kademlia zu verstehen, ist sie bei der Analyse des Protokolls kritisch. Die XOR-Arithmetik bildet eine abelsche Gruppe, die eine geschlossene Analyse erlaubt. Andere DHT-Protokolle und Algorithmen erfordern eine Simulation oder eine komplizierte formale Analyse, um das Netzwerkverhalten und die Korrektheit vorherzusagen. Die Verwendung von Gruppen von Bits als Routing-Information vereinfacht auch die Algorithmen.

Mathematische Analyse des Algorithmus

Um den Algorithmus zu analysieren, betrachten Sie ein Kademlia-Netzwerk von -Knoten mit IDs , von denen jeder eine Zeichenfolge der Länge ist. Das besteht nur aus Einsen und Nullen. Es kann als ein Trie modelliert werden, in dem jedes Blatt einen Knoten darstellt und der markierte Pfad von der Wurzel zu einem Blatt seine ID darstellt. Für einen Knoten , sei die Gruppe von Knoten (IDs), die ein Präfix teilen mit der Länge . Dann kann das Füllen des -th-Buckets von als das Hinzufügen von Zeigern aus den Blättern zu -Blättern modelliert werden (IDs) werden gleichmäßig zufällig aus ausgewählt. Somit kann das Routen als Springen zwischen den Blättern entlang dieser Zeiger gesehen werden, so dass jeder Schritt so weit wie möglich auf die Ziel-ID zugeht, d. H. In einer gierigen Weise.

Sei die Anzahl der Sprünge, die benötigt werden, um vom Blatt zu einer Ziel-ID zu gelangen. Unter der Annahme, dass aus deterministisch ausgewählt werden, wurde bewiesen, dass

wobei die -th Harmonische Zahl ist. Seit als , wenn groß ist ist von oben durch ungefähr begrenzt, die IDs und das Ziel werden jedoch ausgewählt. Dies rechtfertigt die Intuition, dass in Kademlia nur -Knoten bei der Suche nach einem Zielknoten kontaktiert werden.

Um das Modell näher an echte Kademlia-Netzwerke zu bringen, kann auch angenommen werden, dass einheitlich und ohne Ersetzung aus . Dann kann bewiesen werden, dass für alle und , wobei eine Konstante ist, die nur von mit als . Für large konvergiert also zu einer Konstanten nahe . Dies bedeutet, dass die Anzahl der Knoten bei der Suche nach einem Zielknoten im Durchschnitt sein muss.

Verwendung in Filesharing-Netzwerken

Kademlia wird in Filesharing-Netzwerken verwendet. Durch die Suche nach Kademlia-Schlüsselwörtern kann man im Filesharing-Netzwerk Informationen finden, die heruntergeladen werden können. Da es keine zentrale Instanz gibt, um einen Index existierender Dateien zu speichern, wird diese Aufgabe gleichmäßig auf alle Clients aufgeteilt: Wenn ein Knoten eine Datei teilen möchte, verarbeitet er den Inhalt der Datei und berechnet daraus eine Zahl (Hash), die dies tut Identifizieren Sie diese Datei im Filesharing-Netzwerk. Die Hashes und die Knoten-IDs müssen gleich lang sein. Es sucht dann nach mehreren Knoten, deren ID nahe dem Hash ist, und hat seine eigene IP-Adresse, die an diesen Knoten gespeichert ist. d. h. es veröffentlicht sich selbst als Quelle für diese Datei. Ein suchender Client verwendet Kademlia, um das Netzwerk nach dem Knoten zu durchsuchen, dessen ID den geringsten Abstand zum Datei-Hash aufweist, und ruft dann die Quellenliste ab, die in diesem Knoten gespeichert ist.

Da ein Schlüssel vielen Werten entsprechen kann, z. Bei vielen Quellen der gleichen Datei kann jeder Speicherknoten andere Informationen haben. Dann werden die Quellen von allen k Knoten in der Nähe des Schlüssels angefordert.

Der Datei-Hash wird normalerweise von einem speziell geformten Internet-Magnet-Link erhalten, der an anderer Stelle gefunden wird oder in einer Indizierungsdatei enthalten ist, die von anderen Quellen erhalten wird.

Die Suche nach Dateinamen erfolgt über Schlüsselwörter. Der Dateiname ist in seine Wortbestandteile unterteilt. Jedes dieser Schlüsselwörter wird im Netzwerk gehashed und gespeichert, zusammen mit dem entsprechenden Dateinamen und dem Hash der Datei. Bei einer Suche müssen Sie eines der Schlüsselwörter auswählen, den Knoten mit einer ID kontaktieren, die diesem Schlüsselwort-Hash am nächsten kommt, und die Liste der Dateinamen abrufen, die das Schlüsselwort enthalten. Da jedem Dateinamen in der Liste sein Hash angehängt ist, kann die ausgewählte Datei dann auf normale Weise erhalten werden.

Implementierungen

Netzwerke

Öffentliche Netzwerke, die den Kademlia-Algorithmus verwenden (diese Netzwerke sind miteinander nicht kompatibel):

  • I2P
  • Kad Network – ursprünglich von der eMule-Gemeinschaft entwickelt, um die serverbasierte Architektur des eDonkey2000-Netzwerks zu ersetzen.
  • Overnet-Netzwerk: Mit KadC steht eine C-Bibliothek für den Umgang mit Kademlia zur Verfügung. (Entwicklung von Overnet wird eingestellt)
  • BitTorrent Verwendet eine DHT basierend auf einer Implementierung des Kademlia-Algorithmus für trägerlose Torrents.
  • Osiris sps (alle Version): Wird verwendet, um das verteilte und anonyme Webportal zu verwalten.
  • Retroshare – F2F dezentrale Kommunikationsplattform mit sicherem VOIP, Instant Messaging, Dateitransfer etc.
  • Tox – Eine vollständig verteilte Messaging-, VoIP- und Video-Chat-Plattform
  • Gnutella DHT – Ursprünglich von LimeWire entwickelt, um das Gnutella-Protokoll zu verbessern, um alternative Dateispeicherorte zu finden, die jetzt von anderen Gnutella-Clients verwendet werden.
  • IPFS – Ein Peer-to-Peer-verteiltes Dateisystem.
  • TeleHash ist ein Mesh-Netzwerk-Protokoll, das Kademlia verwendet, um direkte Verbindungen zwischen Parteien aufzulösen.

Nächste Generation

Im Laufe der Jahre haben die akademische und die praktizierende Gemeinschaft erkannt, dass alle aktuellen DHT-Designs unter einer Sicherheitsschwäche leiden, die als Sybil-Angriff bekannt ist. Petar Maymounkov, einer der ursprünglichen Autoren von Kademlia, hat vorgeschlagen, diese Schwachstelle zu umgehen, indem soziale Vertrauensbeziehungen in das Systemdesign integriert werden.

Das neue System mit dem Codenamen Tonika oder auch bekannt unter seinem Domainnamen als 5ttt basiert auf einem Algorithmusentwurf, der als elektrisches Routing bekannt ist und zusammen mit dem Mathematiker Jonathan Kelner verfasst wurde. Maymounkov hat nun eine umfassende Implementierung dieses neuen Systems vorgenommen, das vollständig auf der Programmiersprache Go basiert. Die Erforschung wirksamer Abwehrmaßnahmen gegen Sybil-Angriffe wird jedoch allgemein als eine offene Frage betrachtet, und jedes Jahr wird eine große Vielfalt möglicher Verteidigungsmöglichkeiten in Spitzenforschungskonferenzen vorgeschlagen.


Siehe auch auf BitcoinWiki