Peer-to-Peer-Netzwerke: Algorithmen und Methoden

verschiedenen moglichen Schlussel and das Unvermogen von Re- chenmaschinen, jede Moglichkeit auszuprobieren. Andererseits beruht die Annahme der asymmetrischen Kryptographie auf der Annahme, dass die Komplexitatsklassen P and NP verschieden sind. Solange these Annahme nicht bewiesen wurde, muss man befurchten, dass jeder kryptographische Code geknackt werden kann.

    Abb. 10.3. Der loyale General gibt konsistente Befehle.
    Abb. 10.4. Eine Mehrheitsentscheidung unter den drei Offizieren kann von einem Uberlaufer nicht gestort werden.

    Theorem 10.3. Steht ein digitales Signaturschema zur Verfiigung, dann kann eine beliebige Anzahl von falschen Generalen verkraftet werden.
    Beweis. Hierbei unterschreibt jeder General seinen Befehl and in der folgenden Runde gibt jeder General alle Befehle mit Unterschriften an alle anderen Generale weiter. Hat nun jeder den korrekten offentlichen Schlussel, kann jeder inkonsistente Befehl oder jede falsche Weitergabe aufgedeckt werden. ❑
    Durch den Einsatz von digitalen Unterschriften reduziert sich das Problem auf den (bosartigen) Ausfall von Peers in einem Netzwerk, wenn die Nachbarn die Kommunikation rekonstruieren konnen. Das Hauptproblem ist, dass dafur 0(n) Nachrichten pro Peer verwendet werden mussen.
    Abb. 10.5. Selbst ein verraterischer General kann das gemeinsame Handeln der Offiziere nicht verhindern.

10.5 Ein zensorresistentes Peer-to-Peer-Netzwerk
    Amos Fiat and Jared Saia stellen in [88] ein Peer-to-Peer-Netzwerk vor, das in der Lage ist, den Ausfall von 50% aller Peers durch einen Angriff zu verkraften. Voraussetzung hierfUr ist, dass der Angreifer nichts uber die interne Netzwerkstruktur weifl. Weist man den Peers die Aufgaben zufallig zu, so fallt jeder Peer mit Wahrscheinlichkeit aus.
    Grob beschrieben besteht das Netzwerk aus einer Butterfly-Struktur, die wir schon bei Viceroy (Seite 126) kennen gelernt haben. Jeder Knoten des Netzwerks wird jetzt durch eine Menge von Peers realisiert, die als Cluster bezeichnet werden. Die Cluster sind so genannte bipartite Expander-Graphen der GrOBe clog n, welche wie folgt definiert sind.
    Definition 10.4. (Bipartiter Graph) Ein bipartiter Graph besteht aus zwei disjunkten Knotenmengen A and B, so dassjede Kante einen Knoten aus A and B verbindet.
    Definition 10.5. (Bipartiter Expander-Graph) Ein bipartiter Graph G = (V, E) mit der Zweiteilung V = A U B ist ein bipartiter Expander-Graph mit Parametern c, k E (0, 1), wenn fur jede Teilmenge X C A mit IX I < cIAI die Menge der Nachbarknoten Y in B mindestens die Kardinalitdt I Y I > kIX I hat.
    Abb. 10.6. Struktur des Peer-to-Peer-Netzwerks von Fiat and Saia[88].
    Abbildung 10.6 skizziert den Aufbau des Netzwerks. Die Knotenmengen A and B sind jeweils fur die Kommunikation zur nachsthoheren (A) and nachsttieferen Schicht (B) zustandig. Das Routing ist analog zum Routing im Butterfly-Netzwerk. Der Aufbau von Expander-Graphen ist ein eigener Forschungsbereich. Hierzu gibt es eine Reihe von Moglichkeiten, wie z.B. Zufallsgraphen and komplexe deterministische Konstruktionen.

    Der Nutzen der Expander-Eigenschaft ergibt sich dann, wenn parallel eine Anfrage in einem Cluster bearbeitet wird. Dann findet sich zu der Teilmenge von A, die diese Anfrage erhalten hat, immer eine genugend groBe Teilmenge von B, so dass ein Angreifer diese nicht mit hoher Wahrscheinlichkeit kompromittiert haben kann. Hierzu wird die vorausgesetzte Unkenntnis des Angreifers uber die Struktur des Netzwerks ausgenutzt. Von diesem Peer in B wird die Suchanfrage jetzt in die nachste Ebene weitergeleitet, wo sie von einer Teilmenge von korrekten Peers von A wieder entgegengenommen wird.
    Auf these Weise werden alle korrekt arbeitenden Peers eines Clusters im Routing an der Suche beteiligt, um eine Losung des lokalen Byzantinischen GeneraleProblems zu erreichen.
Diskussion
    Mit diesem Netzwerk hat man zugleich ein sehr effizientes, robustes and einfaches Verfahren. Auch lasst sick das Funktionsprinzip auf alle bisher diskutierten Verfahren verallgemeinern.
    Problematisch ist nur, dass der Angreifer wenig fiber die interne Struktur wissen darf. Somit funktioniert dieses Verfahren wohl nur bei Systemen mit Zugangskontrolle. Denn falls der Angreifer die Struktur kennt, dann kann er jedes System mit konstantern Grad durch einen Denial-of-Service-Angriff auf wenigen Peers aushe- beln.
    Bis heute ist die Sicherheit in Peer-to-Peer-Netzwerken noch ein weites Feld mit vielen offenen Fragen, so dass dieses Kapitel nur den