Peer-to-Peer-Netzwerke: Algorithmen und Methoden

h(x) = y, wobei h eine kryptographisch sichere Hash-Funktion ist. Hierbei wurde y = h(x) von einem her- ausfordernden Peer (Challenger) gewahlt. Die Schwierigkeit der Aufgabe lasst sich durch die teilweise Bekanntgabe der Bits von x einstellen. Innerhalb einer gewissen Zeit kann jeder virtuelle Peer nur eine bestimmte Anzahl von solchen Challenges losen.
    Der Vorteil dieser Strategie ist, dass hiermit ein Ansatz vorhanden ist, uberhaupt Sybil-Attacken zu begegnen.
Nachteile
    Der Hauptnachteil ist sicherlich die unglaubliche Verschwendung von Rechenressourcen (Energie, Zeit, Rechenleistung etc.). Andererseits stehen einem Angreifer eventuell durch Einbruch in fremde Rechner enorme Rechenkapazitaten zur Verfugung. Daneben sind die den Benutzern zur Verfugung stehenden Rechenressourcen enorm heterogen. Studenten an Universitaten konnen durch Pool-Recher uber groBe Rechenkapazitaten verfugen, staatliche Einrichtungen verfUgen uber noch groBere Ressourcen (siehe Motivation). Wenig leistungsfahige Peers konnen durch das Challenge Uberfordert werden, wie zum Beispiel altere PCs, Pocket-PCs etc. Das Challenge selbst ist eine institutionalisierte Form des Denial-of-Service- Angriffs.

10.4 Das Problem der Byzantinischen Generale
    Ein ganz typisches Problem im Netzwerkbereich ist das so genannte Problem der Byzantinischen Generale [87]. Im ostromischen Reich besaBen die Generale immer Ambitionen Kaiser zu werden and verfolgten daher mit ihren Armeen mitunter ausschlieBlich eigenntitzige Ziele. Daher konnten sich Generale im Falle eines Krieges nicht unbedingt auf ihre Kollegen verlassen. Wir modellieren hier den Fall von drei Generalen.
    Drei Byzantinische Armeen stehen unter dem Kommando dreier Generale bereit, die gegnerische Burg zu erobern. Die Armeen sind raumlich getrennt and kommunizieren nur uber Boten. Die militarische Lage ist die Folgende: Greift nur eine Armee an, so verliert sie. Greifen zwei an, so gewinnen diese. Greift keine an, so gewinnen die Armeen auch, da durch die fortwahrende Belagerung die Burg ausgehungert wird. Jetzt ist aber ein General ubergelaufen and man weib nicht, welcher es ist. Insbesondere kann dieser General durch widerspruchliche Botschaften die anderen verwirren.
    Abb. 10.1. Der ubergelaufene General X gibt widerspruchliche Anweisungen.
    Wie in Abbildung 10.1 gezeigt, versucht der ubergelaufene General X den General A zum Angriff zu uberreden and General B zum Abwarten. Wenn nun B diesen Befehl A ubermittelt and A den gegenteiligen Befehl an B, so konnen die beiden Generale diesen Widerspruch nicht auflosen. Schlimmer wiegt der Umstand, dass weder B noch A den General X als Uberlaufer uberfuhren konnen oder als Ubermittler wi- dersprUchlicher Befehle, da dieser jeweils einen der anderen Generale beschuldigen kann.

    Abb. 10.2. Unauflosbare Verwirrung unter den Generalen.
    Theorem 10.1. Das Problem der drei Byzantinischen Generale kann nicht gelost werden. Fur vier Generale ist das Problem losbar.
    Wir werden die Strategie fur vier Generale kurz skizzieren. Im Falle von vier Generalen mUssen alle drei ehrlichen Generale angreifen oder alle drei abwarten. Dieses Problem kann auf das Ein-General-und-drei-Offiziere-Problem reduziert werden, siehe Abbildung 10.3.
    Nun sei der General loyal and einer der drei Offiziere ein Uberlaufer. So gibt der General konsistente Anweisungen fur den Angriff. Diese geben die Information an alle anderen Offiziere weiter. Die wiederum berechnen eine Mehrheitsentscheidung, die durch einen der drei Offiziere nicht behindert werden kann, siehe Abbildungen 10.3 and 10.4.
    Ist der General nicht loyal, so werden seine (widerspruchlichen) Befehle korrekt unter den Offizieren ausgetauscht. Diese folgen dann der Mehrheitsentscheidung wie bei einem loyalen General, der damit ein gemeinsames Handeln der Offiziere nicht verhindern kann, siehe Abbildung 10.5.
    Im Allgemeinen gilt das folgende Theorem.
    Theorem 10.2. Falls m Generale Uberlaufer Sind, mussen mindestens 2m + 1 Generale ehrlich sein, damit das Problem der Byzantinischen Generale losbar ist.
    Diese Schranke ist genau, wenn keine kryptographischen Annahmen gemacht werden, wenn also asymmetrische Kryptographieverfahren nicht verfugbar sind. Im strengen Berechenbarkeitsbegriff der Rekursionstheorie ist jedes asymmetrische Verfahren unsicher, da man „nut" jeden geheimen Schlussel ausprobieren muss, der zum offentlichen Schlussel passen konnte. Das berucksichtigt aber nicht die kombinato- rische Vielfalt der