Eine Beschreibung des Aufbaus von Entropy

Dies ist zum großen Teil nicht mehr aktuell - Update kommt

Entropy wurde entwickelt, um verschiedene Anforderungen gleichzeitig zu erfüllen:

1. Verteilung von Daten im Netzwerk in einer weitverteilten Art und Weise, so daß es praktisch unmöglich ist sie zu lokalisieren (z.B. um Zensur unmöglich zu machen)
2. Verfügbarkeit von Daten gewährleisten, sogar wenn ein Teil der Entropy-Netzknoten nicht verfügbar ist. (Ausfallsicherheit, Fehlertoleranz)
3. Verbergen vor den Nutzern oder Außenstehenden, welche Netzknoten welche Teile (Teilstücke, Fragmente) von welchen Dokumenten haben (Verschlüsselung).
4. Optimierung des Datentransfers für die Benutzung mit ADSL, wobei die Download-Bandbreite größer als die Upload-Bandbreite ist (z.b. 768kbit/s vs. 128kbit/s mit T-DSL).
5. Die Art der Kommunikation zwischen den Entropy-Netzknoten soll verborgen bleiben (Übertragungs-Verschlüsselung).

Diese Ziele (und einige mehr) sind mittlerweile komplett oder teilweise erreicht. Einiges muß noch getestet und optimiert werden, besonders in einem sehr großen Netzwerk.

Entropy gliedert sich in verschiedene Module, welche als separate Prozesse laufen (forked). Dabei wird shared memory als Kommunikationsmethode verwendet. Diese Module sind:

• Peer-Management mit einem Bandbreiten-Begrenzer
• Starter für ausgehende Verbindungen
• Empfänger für eingehende Verbindungen
• Datei bzw. Dokument-Aufteilung in Fragmente und Chunks
• Datenbank Management
• Warteschlangen und Routing
• Freenet Client Protocol (FCP) Server
• HTTP Gateway, aka Proxy

Peer-Management mit Bandbreitenbegrenzer

Dieses Modul und seine Prozesse sind sehr einfach. Du kannst eine maximale Bandbreite für eingehende und ausgehende Verbindungen konfigurieren. Du konfigurierst eine totale Anzahl von Bytes pro Sekunde in entropy.conf. Der Begrenzer läuft nun mit 10 Ticks pro Sekunde (in der Datei include/config.h gibt's eine Zeile #define TICKS 10) und addiert zu 2 "shared memory" Variablen 1/10th der Bandbreite pro Sekunde in beide Richtungen. Die Socket I/O Funktionen benutzen diese Variablen um ihre benötigte Bandbreite zu konfigurieren. Wenn z.B. ein Sende-Puffer 10K bytes hat und es sind z.Zt. nur 1000 byte/s verfügbar, wird die sock_writeall() Funktion warten und später versuchen mehr Bandbreite zu bekommen bis alle Daten fertig rausgeschrieben wurden. Die verschiedenen Prozesse einer Verbindung versuchen gegenseitig die Bandbreiten-Variablen zu verriegeln, um einen Bruchteil (80%, hard-coded in src/sock.c) der benötigten Bandbreite zu bekommen bis sie fertig sind.

Diese Methode ist vielleicht weit davon entfernt perfekt zu sein. Einige Betriebssysteme mögen auch viel bessere Wege zum Begrenzen eines Sockets oder der Netzwerkbandbreite haben. Jedoch läuft entropy auch auf Systemen, wo solche Sachen nicht verfügbar sind. Und einen generellen Standardweg gibt es jedenfalls sowieso nicht.
Auf jeden Fall erlaubt es Entropy etwas Bandbreite aufzuheben für andere gute Sachen :-) und das ist alles, wofür der Bandbreitenbegrenzer gedacht ist.

Starter für ausgehende Verbindungen aka outgoing connections launcher

Entropy hat seinen eigenen Weg, um mögliche Kontakte (peer nodes) zu finden. Es gibt eine Startliste, welche in der Form hostname:port oder IP-Addresse:port in der seed.txt definiert ist (oder wie immer man die Datei in der entropy.conf nennt). Außerdem übermittelt Entropy seinen ausgehenden Kontakten Informationen über seine anderen Kontakte.

Diese sogenannten node announcements werden innerhalb des Entropy-Netzwerkes gemacht. Für diesen Zweck erzeugt ein Node Dateien mit Null Inhalt, aber nur mit Meta-Daten. In diesen Meta-Daten gibt es einen XML-Text, welcher Informationen über einen Node enthält:

• node's IP Addresse
• node's Kontakt Port (WAN Port)
• node's bevorzugtes Verschlüsselungsmodul

  <?xml version="1.0" standalone='yes'?>
  <p2p>
    <peer hostname='aaa.bbb.ccc.ddd' port='nnnn' />
    <crypto module='something' />
  </p2p>

Diese Ankündigungen (announcements) sind also nun in Dokumenten (mit Null Länge) in den Metadaten enthalten. Diese Dokumente haben bekannte Namen (Schlüssel bzw. Keys) nach folgendem Muster:

1. entropy:KSK@utc-timeslice-ipaddr:port
2. entropy:KSK@utc-timeslice-2-digit-hex-value

Der Starter für ausgehende Verbindungen durchsucht alle 256 möglichen Schlüssel des aktuellen Zeitbereichs bis er eine Eintrag findet, der:

• noch nicht verbunden ist
• nicht blockiert ist (wegen Fehlern oder permanent)
• zu IP-Addressen auflösbar ist (wenn es ein Hostname ist)

Der Starter versucht dann eine neue Verbindungen zu diesem Kontakt aufzubauen. Die Frequenz, mit der nach neuen Verbindungen gesucht wird nimmt mit der Anzahl der schon existierenden Verbindugen ab. Mit anderen Worten: umso mehr Verbindungen dein Entropy-Knoten schon hat, umso langsamer werden neue Verbindungen erzeugt. Wenn ein Entropy-Knoten alle seine ausgehenden Verbindungen aufgebraucht hat (z.Zt. 32) sucht er keine neuen mehr, bis eine oder mehrere Verbindungen gekappt werden.

Wenn ein Verbindungsaufbau fehlschlägt, wird die entsprechende IP-Addresse und Port-Nummer in eine Fehlerliste (im shared Memory) eingetragen. Geschieht das innerhalb einer bestimmten Zeit nochmal (z.Zt. eine Stunde) wird diese IP-Addresse und PortNummer für 10 Minuten blockiert. Sie wird deshalb in die Blockierungsliste eingetragen mit einem Zeitstempel von (jetzt + 10 Minuten). Das bedeutet, daß die peer_node_search() Funktion in src/peer.c diesen ip/port für einige Zeit überspringt.

Du wirst dich fragen, ob 2 Entropy-Nodes denselben 2-stelligen Hex-Wert für einen spezifischen Zeitbereich erzeugen könnten? Ja, sie können und manchmal passiert das auch. Das ist aber kein großes Problem, da einer der Schlüssel irgendwo im Netzwerk sein wird. Im nächsten Zeitfenster ändern sich die Nummern wieder, und die Wahrscheinlichkeit daß 2 Nodes fortwährend mit ihren Announcements kollidieren ist sehr klein (Es sei denn sie haben dieselben IP-Addresse/Port, was es natürlich nicht giebt, wenn du mal drüber nachdenkst :-). Sollte das Netz aber (jemals) so groß werden, daß 256 Slots nicht ausreichend sind, damit jeder Entropy-Node genug ausgehende Verbindungen findet, könnte ich genauso einen 3-stelligen Hash-Wert nehmen und nach 4096 Slots suchen. Ich glaube allerdings nicht, daß das jemals nötig sein wird.

Empfänger für eingehende Verbindungen aka incoming connections listener

Dieses Modul ist ebenfalls einfach gebaut. Es erzeugt einen (TCPIP-) Sockel und bindet ihn an die spezielle IP-Addresse 0.0.0.0 (IPADDRANY) mit der konfigurierten Port-Nummer für Entropy (nodeport= in der entropy.conf). Danach wartet es auf eingehende Verbindungen. Jedesmal wenn der listen() Aufruf beendet ist, wird eine neue Verbindung akzeptiert. Dann wird ein Kind-Prozess gestartet um die ankommende Verbindung zu verarbeiten.

Dieser Kind-Prozess überprüft zuerst, ob ein Slot für eingehende Verbindungen frei ist. Ein Entropy-Knoten akzeptiert maximal 32 eingehende Verbindungen. Das passiert im jetzigen (kleinen) Netzwerk noch nicht, aber es wird wahrscheinlich mal passieren.

Sobald eine neue Verbindungsanforderung eintrifft, generiert unser Kind-Prozess (mit der fork() Methode erzeugt) ein neues McEliece Schlüsselpaar. Der öffentliche Schlüssel wird dann zur Gegenstelle gesendet. Dieser Schlüssel ist eine Zeichenkette (string) von 1024 * 654 bits = 83'712 bytes.

Der andere Entropy-Knoten empfängt diesen öffentlichen Schlüssel, erzeugt einen 4096 bytes großen Session key (oder seed) von seinem Zufallsgenerator (PRNG - Pseudo Random Number Generator) und verschlüsselt diese Daten mit unserem öffentlichen Schlüssel. Der nun verschlüsselte Session key wird in eine Anfangsnachricht geschrieben, welche dann LZW-komprimiert an uns gesendet wird.

Unser Kind-Prozess liest nun diese Nachricht von der Gegenstelle in der Form:

  <?xml version="1.0" standalone='yes'?>
  <p2p>
    <peer hostname='knoten.irgendwo.net' port='nnnn' />
    <node type='entropy' major='0' minor='0.30' build='xyz' />
    <store fingerprint='[32 hex digits]' />
    <crypto module='irgendwas' size='xxx' initial='[2 * size hex digits]' />
  </p2p>

Das sieht doch irgendwie bekannt aus, oder? Ja, die Nachricht ist ähnlich dem XML-text in den Node-Announcments und wird tatsächlich durch dieselben Funktionen gelesen (geparst, wie der Programmierer sagt -:). Allerdings haben wir jetzt etwas mehr Informationen, da der Entropy-Knoten hostname= selber uns kontaktiert. Zumindest nehmen wir das an.
Eine der ersten Sachen, die die peer_in_child() Funktion in src/peer.c tut, ist nämlich den Hostnamen mit der IP-Addresse zu vergleichen. Die IP-Addresse wird während des accept() von dem Listening-Prozess gesetzt und in der Verbindungs-Info gehalten. Ergibt eine DNS-Abfrage nun Übereinstimmung ist alles gut und Entropy aktualisiert seine interne Liste der kontaktierten Gegenstellen, um Hostname:Port für jede Verbindung zu dieser Gegenstelle anzuzeigen. Aber das ist eigentlich nur Kosmetik. Wenn eine Gegenstelle behauptet bundestag.de zu sein, und (höchstwahrscheinlich) nicht unter dieser Addresse erreichbar ist, wird es trotzdem mit Entropy funktionieren. Und da seine Addresse, nicht sein DNS-Name, weitergegeben wird, wird er -- früher oder später -- auch von anderen Entropy-Knoten kontaktiert werden.

Der Node-Tag gibt offensichtlich die verwendete Entropy-Version an. Das ist zwar anscheinend nur informatorisch, aber damit können leicht uralte bzw. defekte Entropy-Versionen ausgeschlossen werden. Allerdings wird das hier nicht weiter überprüft, so daß jemand in böswilliger Absicht diese Felder fälschen kann.

Das "fingerprint" Attribut des "store" Tags hat eine wichtige Funktion. Ein Fingerprint (Fingerabdruck) eines Entropy-Nodes bestimmt seinen Platz in der Routing-Tabelle innerhalb des Entropy-Netzwerkes. So ein Fingerabdruck besteht aus 16 Byte-Werten , also 16 vorzeichenlose Zahlen zwischen 0 und 255. Jeder Node leitet seinen Fingerprint aus der Gewichtung von Schlüsseln (Keys) aus seinem Datastore ab. Entropy nutzt hierbei für den Fingerprint und das Routing die letzte Stelle des SHA1-Hashes der Schlüssel. So ergibt z.B. ein Datastore mit einem Maximum von 1000 keys auf 9 endend, 500 auf 3 endend und 100 auf F endend (und einigen mehr in unbedeutenden Mengen, sagen wir < 10) einen Fingerprint der Form:

01 03 00 7f 00 02 00 00 01 ff 00 00 02 00 00 19

Man sieht also die FF im 'Slot' Nummer 9 (von Null an gezählt), die 7F im Slot 3 und die 19 im Slot 15. Der Fingerprint ergibt also eine normalisierte Verteilungskurve des Datastores. Das hat allerdings nichts mit dem "Daten-Inhalt" des Datastores zu tun, es ist lediglich eine statistische Beschreibung eines Datastores. Diese Zahlen ergeben also die Wahrscheinlichkeit, mit der ein Node Anforderungen (requests) oder Bekanntmachungen (advertize) bekommt.

Fingerprints werden von Zeit zu Zeit aktualisiert (z.Zt. alle 5 min) wenn ein Node seinen Fingerprint an alle seine Kontakte sendet. Das passiert in einer Reihe von Funktionen, die in den Log-Files als node maintenance (Wartung) angekündigt werden. Ein wichtiger Unterschied dieser sogenannten MSG_FPR Nachrichten zu anderen ist, daß diese einen HTL-Wert (hops-to-live) von Null haben. Normalerweise verlassen Nachrichten mit HTL=0 nicht den eigenen Node und das bedeutet, daß unser Fingerprint nur den nächsten "Hop", unsere direkten Kontakte, erreicht. Wenn also der Fingerprint eines Nodes sich ändert -- langsam oder heftig, z.B. weil er eine Menge Daten von lokal oder anderen Entropy-Knoten bekommt -- werden seine direkten Kontakte darüber informiert, welche Art von Schlüsseln von ihm (mit hoher Wahrscheinlichkeit) zu erwarten sind. Gleichzeitig sollte ein Node auch seinerseits dann solche Keys geschickt kriegen, damit sich eine gewisse Spezialisierung herausbilden kann. Im Idealfall sollten sich in den Fingerprints deutliche Maxima herausbilden.
Am Ende soll der Aufwand mit den Fingerprints nicht mehr -- und nicht weniger -- sein, als ein Weg, um dem Netzwerk ein Load-Balancing zu ermöglichen und Daten bzw. Schlüssel zu verteilen, so daß auch eine Redundanz entsteht.
Die Methode ist sicherlich noch nicht perfekt, aber für das jetzige Netzwerk völlig ausreichend.

Im letzten Tag der Nachricht (crypto) teilt ein Node seinen Peers mit, welches Krypto-Modul er gerne benutzen will und welche Anfangswerte, seed oder Session Key er benutzen wird. Die Namen der crypto module= sind einfach Platzhalter für die jeweils implementierte Methode. Ich experimentiere mit einigen Strom-Chiffren, z.B. heißt ein Module 'crypt3', was eine Implementation eine S-Box Algorithmus ist. Das Standardmodul heißt z.Zt. 'ikg3'. Andere Module sind experimental oder tun einfach nichts (crypt0 ist nur ein Null-Layer und sollte mit der Zeile crypto_reject= in der entropy.conf deaktiviert werden). Alle Module machen aber durchaus ihren job, nämlich einen schwierig zu erratenden Strom von Zufallszahlen zu erzeugen (außer crypt0 natürlich). An der Analyse und Qualität dieser Kryptomodule wird dabei ständig weitergearbeitet, so daß aufgrund des modularen Aufbaus kryptografisch schwache Module leicht ausgetauscht werden können.

Unser Node, und nur unser Node, kann nun den initial='001122...' Teil der ersten Nachricht mit seinem privaten McEliece Schlüssel dechiffrieren. Nachdem er das getan hat, initialisiert er das gewählte Kryptomodul mit den 4K bytes von Pseudo-Zufallszahlen, welche von dem Node kommen der uns gerade kontaktiert hat.
Von nun an sind alle Nachrichten auf diesem Kanal verschlüsselt, unter Benutzung der gewählten Strom-Chiffre und des Session keys oder seed.

Aufteilung in Fragmente und Chunks

Bevor Entropy ein dokument oder eine Datei ins Netzwerk einfügt, wird alles in Fragmente aufgeteilt.

Bild 1 - Fragmentierung

Wie man in der Grafik sieht, jedes Fragment hat eine feste Größe von 128k und das letzte Fragment hat dann meistens einige Nullen angehängt, um auf die 128k aufzufüllen.

Für jedes Fragment wird dann ein Hash erzeugt: zuerst EK5 (ein modifizierter MD5 hash für Entropy's Zwecke) und dann SHA1. Aber zuerst einen Blick auf die Verschlüsselung eines Fragments:

Bild 2 - Fragment Verschlüsselung

Wie man sieht wird der EK5-Hash benutzt, um einen sogenannten LFSR (liner feedback shift register)-Algorithmus mit dem Namen Lili2 (lokale Kopie mit Korrektur eine Fehlers in der Formel für fc auf der Originalseite) zu initialisieren (zu "seeden"). Dieser Algorithmus wurde entworfen von Leuten an der Queens University of Technology, Australia. Er unterstützt 2 LFSRs. Einer wird benutzt, um das Taktsignal für den zweiten zu liefern. In jedem Zyklus wird der Data-LFSR und der Clock-LFSR einmal geschoben (shift). Abhängig von zwei Bits des Clock-LFSR wird der Data-LFSR noch ein oder drei mal geschoben. Mit anderen Worten: Der Data-LFSR wird zwischen ein und vier mal pro Ausgangsbit geschoben, abhängig vom Status des Clock-LFSR. Zwölf bits des Data-LFSR werden schließlich benutzt, um ein Ausgabe oder Ergebnis Bit von einer Tabelle von Bits zu bestimmen. Die Entwickler behaupten, daß diese Tabelle von 4096 Bits hilft, um den resultierenden Bit-Strom weitgehend frei von Linearitäten zu machen.

Die LFSRs des Lili2 Algorithmus' sind 128 bit (Clock) und 127 bit (Data). Ich benutze den 128 bit EK5 Hash, um den clock-LFSR zu initialisieren und in umgekehrter Reihenfolge für den data-LFSR. Der resultierende Strom von bits ist dann XORed mit dem Klartext eines Fragments (jeweils ein Byte), um das verschlüsselte Fragment zu erzeugen.

Nachdem die Fragmente nun verschlüsselt sind, sind es nun Chunks (Stück,Brocken) und zur selben Zeit FEC (Forward Error Correction) kodiert. Ich nenne das in Entropy genutzte FEC-Schema FEC84, weil es 4 Chunks mit Check-Bits für jeweils 8 Chunks mit Daten-Bits erzeugt. Gleichzeitig -- und durch reinen Zufall (?) -- kann man das als eine Parallele zu George Orwell's Horror-Szenario eines totalen Überwachungsstaates in seinem Buch "1984" sehen. Entropy zerteilt wirklich die Daten in Bits, so daß für jedes 128K Byte Fragment von Daten 8 mal 128K Bit Chunks entstehen. Das macht dann wieder 16K Bytes, wenn man die Bits wieder in Oktets anordnet.

Bild 3 - "Chunking" (Aufteilen in Blöcke)

Der SHA1 Hash von jedem verschlüsselten Fragment wird zusammen mit dem EK5 Hash vom unverschlüsselten Fragment in einer (beschreibenden) XML-Datei gespeichert. Dieses Schlüssel-Paar ist sowas wie ein top level CHK@ Schlüssel. Man braucht den EK5 Hash um das Fragment wieder zu entschlüsseln. Die ganze Übertragung und Speicherung der Chunks benutzt immer nur den SHA1 Hash. Für eine Rekonstruktion der Daten muß man also Zugriff zu dem beschreibenden XML-Dokument haben.

Wie man also sehen kann, produziert der FEC84 Kodierungs-Prozess 50% Redundanz für jedes Fragment, welches in das Netzwerk eingefügt wird. Das heißt z.B. daß eine Datei von 100k Größe zwölf chunks benötigt, oder 12 mal 16K im Data-Store. Warum ist das so? Der FEC Code macht es möglich, die 128K Daten aus verschiedenen Teilen zu rekonstruieren. Dabei ist es egal, welche der 8 von den 12 chunks eines Fragments wir haben. Das ist ein wesentlicher Teil der Fähigkeit von Entropy Daten zu heilen während ein Node sie anfordert. Wenn irgendwelche 8 von den 12 chunks gefunden werden, wird dein Node die fehlenden 4 chunks rekonstruieren und (manchmal) die neu erzeugten chunks weiterverteilen. Das bedeutet außerdem, daß nicht notwendigerweise alle 50% Redundanz durch daß Netzwerk gehen muß. In der Praxis macht es dieser Ansatz mit der Aufteilung der Fragmente es sogar schwerer zu erraten, was ein Node wirklich tut. Er empfängt einige (bis zu Acht) "Chunks" von Daten und sendet dann einge (bis zu 4) neue Chunks von Daten. Hat dieser Node nun die Daten (neu) eingefügt oder nur gerade fehlende Chunks neu erzeugt? Das ist unmöglich zu sagen, ohne einen Blick in den ausgeführten Programmcode des Nodes zu tun.

So ist also der innerste Kern aus denen ein Dokument oder eine Datei besteht, ein chunk von höchstens 16K Bytes, plus ein XML-Dokument welches seine Konstruktion beschreibt:

Bild 4 - Keyroute

Die keyroute Funktion (svw. Schlüssel-Weg) ist ein einfacher Algorithmus der alle 40 Nibbles (Halb-Bytes, 4 bit words) eines SHA1 Hash XOR'ed. Das Ergebnis ist dann ein Wert zwischen 0 und 15 (bzw. 0x0 und 0xf hex). Dieses "X" ist die Routing Information für jeden Chunk. Sie wird benutzt im Zusammenspiel mit den Fingerprints (Fingerabdrücken) aller Nodes um zu entscheiden, welche Nodes am wahrscheinlichsten einen Chunk erhalten, haben oder behalten. Da die Verteilung von Keyrouten entlang der 16 möglichen Werte durchschnittlich ist, werden die meisten Dokumente mehr oder weniger ideal zu den 16 (oder mehr) direkt kontaktierten Nodes verteilt. Das Einfügen einer Datei ins Entropy-Netzwerk bedeutet also, es aufzuteilen, die Teilstücke zu verschlüsseln und dann die Daten- und Check-Chunks in einer nicht vorhersagbaren Art und Weise im Netz zu verteilen. (Die Verteilung der Chunks hat nichts mehr mit dem eigentlichen Dokument zu tun) Solange wie man genug Verbindungen hat, ist es sehr unwahrscheinlich, daß ein eingefügtes Dokument nur an einem Peer-Node komplett verfügbar ist -- das kann aber passieren bei sehr schnellen Nodes in einem z.B. LAN, wobei diese Nodes dann auch einen sehr weißen Fingerprint haben, weil sie schon sehr viele Keys haben.

Das XML Dokument, welches nun schon einige Male erwähnt wurde, ist der Schlüssel zu den ansonsten unnützen Daten in einer Datenbank und sieht folgendermaßen aus:

  <?xml version="1.0" standalone='yes'?>
  <content size='xxx' key='abcdef...,...vwxyz'>
    <fragment number='x' mode='fec84' size='xxx' key='ABCDEF...,...VWXYZ'>
      <chunk number='0' hash='000000...000' />
      <chunk number='1' hash='111111...111' />
      ...
      <chunk number='b' hash='bbbbbb...bbb' />
    </fragment>
    <fragment number='y' mode='fec84' size='yyy' key='012345...,...6789~'>
      <chunk number='0' hash='000000...000' />
      <chunk number='1' hash='111111...111' />
      ...
      <chunk number='b' hash='bbbbbb...bbb' />
    </fragment>
    ...
    <metadata size='xxx'>001122334455...ff</metadata>
  </content>

Das Element der obersten Ebene (bzw. Root-Element) ist das content Element. Es hat die Attribute size und key. Das size='xxx' Attribut enthält die Größe des ganzen Dokuments als hexadezimale Zahl (z.B. 3e8 für 1000 bytes).

Die Liste der fragment Elemente kann keinen oder mehr Einträge haben. Wenn ein Dokument überhaupt keine Daten sondern nur Metadaten enthält, gibt es keine Fragment-Einträge in dem XML-Dokument. (Zu einer zweiten Möglichkeit für XML content ohne fragment Elemente später mehr.)

In Fragment number='x' ist x ein "zero based hex digit string", so daß das erste Fragment die Nummer "0" hat, der zweite die Nummer "1" usw. Im Moment ist die Kodierung eines Fragments immer mode='fec84'. Das kann sich natürlich in der Zukunft mal ändern, deshalb hat jedes Fragment seinen eigenen Modus zugeordnet. Die Zeichenkette key='xxx...,...yyy' des Fragments ist ähnlich einem top level CHK@ zusammengesetzt. In der Entropy Logdatei sieht man diese Art von Keys als BIT@ -Keys bezeichnet, wenn man das Loglevel hochsetzt. Sie bestehen aus dem base64-kodierten SHA1 Hash der Daten des verschlüsselten Fragments und dem Entschlüsselungskey. Dieser ist gleichzeitig der EK5 Hash der Daten des entschlüsselten Fragments.

Im Modus 'fec84' enthält jedes Fragment eine Liste von 12 chunk Elementen, und jeder Chunk hat als seine Attribute eine Nummer (zero based hex digit string - zu schön zum übersetzen :-) und einen Hash. Der Hash ist der SHA1 Hash des Chunks wie schon weiter oben beschrieben. Das Größen-Attribut des Fragments ist meistens 128K (131072 dezimal, gespeichert im XML als Hexadezimal-Zahl, z.B. size='20000"). DEas letzte Fragment ist natürlich dann meistens kürzer.

Das metadata Element eines Dokuments enthält einige Informationen, welche vom FCP-Protokoll (Freenet Client Protocol) während des Einfügens hinzugefügt werden. Das ist meistens eine Freenet-kompatible Beschreibung des Dokuments (z.B. das MIME-Format). Es kann alles mögliche an Daten sein, wenn man nicht kompatibel mit den verschiedenen FCP-Anwendungen (z.B. auch zum Proxy) bleiben will. Diese Daten werden also nur von den verschiedenen Client-Anwendungen ausgewertet, nicht von Entropy selbst (außer eben im Proxy).

Jedes dieser XML-Dokumente wird nun mit dem in Entropy integrierten LZW-Algorithmus komprimiert. Das reduziert normalerweise die Größe auf etwas zwischen 50 und 90 Prozent des blanken Texts. Sollte der sich ergebende LZW-komprimierte Puffer kleiner als CHUNKSIZE (das sind 16K) sein, werden die Daten einfach als Fragment verschlüsselt. Dabei wird wieder der EK5 hash des chunk und Lili2 verwendet. Ein CHK@ Chunk ist nicht unterscheidbar von einem der BIT chunks. Er wird auch in gleicher Weise gerouted (verteilt), entsprechend der keyroute für den SHA1 Teil.

Wann immer Entropy einen CHK@ Key abruft, guckt es nach einem Chunk mit dem SHA1 Hash. Dieser wird immer im ersten Teil eines CHK@ Keys angegeben. Zusammen mit dem zweiten Teil des CHK@'s, dem EK5 Hash, wird dieses Datenstück dann entschlüsselt. Dabei wird der EK5-initiierte Lili2 Algorithmus benutzt (der natürlich symmetrisch ist). Der sich ergebende dechiffrierte Puffer kann dann LZW-dekomprimiert werden und an den expat XML parser übergeben werden.

In diesem Stadium hat Entropy eine komplette Liste aller Teile einer Datei im Speicher. Es versucht nun ein Fragment zu rekonstruieren indem es nach den entsprechenden Chunks sucht. Wie schon gesagt, reicht es, 8 beliebige der 12 chunks zu haben, um das Fragment zu rekonstruieren. Jeder lokal nicht verfügbare Chunk kann nun von den kontaktierten Peers angefordert werden. Das wird quasi-parallel für alle 12 Chunks jedes Fragments getan. Idealerweise kommen jetzt die 8 schnellsten Antworten von den Peers mit optimalen Routen/Fingerprints herein. Die ersten 8 chunks von (bis zu) 16K Länge sind dabei ausreichend, um ein 128K Fragment zu rekonstruieren. Einige Routen für bestimmte Chunks sind vielleicht (zur Zeit) nicht verfügbar. Die Peers mit den optimalen Routen sind evtl. langsam oder überlastet. Deshalb braucht es mehrere Versuche, um alle 8 Chunks für ein Fragment zu erhalten. Dabei werden verschiedene Wege beschritten. Einerseits werden auch sub-optimale Peers (Routen) abgefragt. Andererseits wird derselbe Peer nach einem gewissen Timeout wiederholt abgefragt. Der Timeout hängt dabei von dem HTL-Wert ab (hops to live) mit dem dieser Key von einem Nachbar-Node abgefragt wurde.

Wenn es, auf welche Weise auch immer, nun 8 von den für ein Fragment benötigten Chunks in Deinen lokalen Datastore geschafft haben, ist dieses Fragment komplett. Glücklicherweise passiert das ziemlich oft. Zumindest solange wie (Entropy-) Inhalt durch Abfragen bzw. Neueinfügen am Leben gehalten wird. Entropy überprüft nun den Hash des Fragments mit dem SHA1 aus dem XML-Dokument. Bei Übereinstimmung wird das entschlüsselte Dokument dann im temporären Speicher abgelegt. Sollten jetzt noch einige der 12 benötigten Chunks fehlen, werden diese nun rekonstruiert und (manchmal) an die kontaktierten Peers verteilt. Dann wird das nächste Fragment versucht, solange bis alle Fragment einer Datei in deinem Datastore sind. Das bedeutet nicht, daß die Datei in irgendeinem Klartextforamt in deinem Datastore (auf der Festplatte) ist. Die Daten sind nur im temporären Speicher (im RAM) und von dort auf dem Weg zum Browser, zu den News-Einträgen oder irgendeiner Deiner FCP-Applikationen im Klartext vorhanden.

Am Ende, wenn das Dokument nun komplett ist und seine Gültigkeit überprüft wurde, durch Vergleich des SHA1 Hash's des kompletten Dokuments mit dem von dem originalen Key, wird die temporäre Datei zu dem anfordernden Programm geschickt.

Oben beschrieben wurde der Fall, daß ein LZW-komprimiertes XML-Dokument in "CHUNKSIZE" paßt. Was passiert aber, wenn es größer ist? In diesem Fall wird das Dokument selbst als temporäre Datei gespeichert und eingefügt, als ob es ein User-Dokument wäre. Das ist ein Umweg, der sogar mehrmals nötig sein kann für sehr große Dateien. Beim Anfordern von den Dateien wird dieser Weg dann wieder rückwärts gegangen. Hat eine Datei nach dem Sammeln und Dechiffrieren einen internen Key-Type, wird sie nicht sofort zu der anfordernden Frontend-Applikation gesendet, sondern als nächster, größerer Layer eines XML-Dokuments ausgewertet. Dieses Dokument beschreibt dann eine längere Liste von Fragmenten mit mehr Chunks.Der ganze Prozeß geht solange weiter bis das äußerste XML-Dokument, welches dann wirklich ein User-Dokument beschreibt, empfangen und rekonstruiert wurde.

Eine weitere, schon erwähnte Ausnahme war für ein XML-Dokument ohne Fragmente. Wenn ein Dokument oder eine Datei komplett LZW-komprimiert werden kann, so daß es in einen 16K Puffer paßt, wird es als short key gespeichert. Dieser Key-Typ vermeidet die Notwendigkeit den XML-Chunk und die 12 Check- und DatenChunks für kleine Dateien zu verarbeiten. Das XML-Dokument, welches unter einem CHK@ für diesen Key-Typ gespeichert wird, sieht folgendermaßen aus:

  <?xml version="1.0" standalone='yes'?>
  <content size='xxx' key='abcdef...,...vwxyz'>
    <data size='xxx'>001122334455...ff</data>
    <metadata size='xxx'>001122334455...ff</metadata>
  </content>

Anstatt einer Liste von Fragmenten und Chunks werden die Daten der Datei direkt in den XML Text eingefügt - als eine Zeichenkette von Hex-Ziffern. Dann wird die LZW-Komprimierung auf das resultierende XML-Dokument angewendet und wenn das Ergebnis kleiner als 16K ist, wird dieser Key zu einem short key. Der LZW komprimierte Puffer wird in der selben Art und Weise verschlüsselt, wie jeder der long key XML Dokumente. Außerdem können entweder die data oder die metadata Elemente fehlen. Zur Zeit können beide fehlen für einen speziellen Key: der NULL Key ohne Daten oder Metadaten :)

Datenbank Management

Das Basis-Element von Daten innerhalb des Entropy-Netzwerkes ist ein chunk, welcher meistens (und maximal) eine Größe von 16KB hat. Siehe Abschnitt Datei bzw. Dokument-Aufteilung in Fragmente und Chunks für eine geneuere Beschreibung. Der Datenspeicher (datastore) muß also in der Lage sein, eine große Menge von kleinen, schnell zu findenden Datenstückchen zu verwalten: den Chunks.

Der wahrscheinlich effizienteste Typ einer Datenbank für diese Art von Daten ist ein monolithischer Speicher, der Standardtyp in Entropy's makefile. Diese Datenbank besteht aus einem Satz von ein paar wenigen, großen Dateien. Jede Datei hat eine feste Größe (bis zu 2GB@FAT, 4GB@FAT32). Die (optimale) Position eines Chunks in dieser Datenbank wird durch seinen SHA1-Hash bestimmt. Es werden dafür nur ein paar Bits des Hash benutzt und deswegen kommt es zu Kollisionen, d.h. der ermittelte, ideale Platz in der Datenbank ist schon belegt. Deshalb werden Keys auch "drumherum" abgelegt: bis zu 16 Positionen nach dem idealen Platz werden nach einem leeren Speicherplatz (beim Speichern) oder einem Key (beim Abrufen) gescannt. Außerdem kommt es natürlich auch zum überschreiben von älteren Keys.

Dieser Datenbank-Type scheint den wenigsten (negativen) Einfluß auf die Gesamtperformance von Betriebssystemen (wie Windows), mit nicht-so-perfekter Verwaltung von riesigen Mengen kleiner Dateien zu haben.

Entropy's zweiter Datenbanktype, der "Speicherbaum" (store_tree) besteht aus einem Verzeichnis-Baum unterhalb eines konfigurierbaren Basis-Verzeichnisses (storepath=store ist der Standardpfad in der entropy.conf). Abhängig vom Setzen der storedepth=x in der Konfiguration, gibt es Null, Eins, Zwei oder Drei Verzeichnis-Ebenen. Jeder Verzeichnisname ist einfach eine Hex-Ziffer, also 0-9 und a-f.

Die beste Speichertiefe hängt dabei von den Möglichkeiten des verwendeten Dateisystems ab. Für die meisten UNIX-Dateisysteme und NTFS scheint eine Baumtiefe von 1 eine gute Wahl zu sein. Jedesmal wenn Entropy nach einem Key oder einem Speicherplatz für einen Key sucht, muß es den ganzen Verzeichnisbaum durchsuchen, um zu sehen, ob ein Dateiname schon existiert. Bei einem (hoffentlich) großen Datastore ist es wahrscheinlich nicht klug, eine flache Struktur, d.h. alle Dateien in einem Verzeichnis (storedepth=0), zu verwenden, da dann einige hundertausend oder millionen Dateinamen für jede Aktion zu scannen sind.

Auf der anderen Seite ist es auch nicht ratsam eine allzu große Verzeichnistiefe zu verwenden, z.B. bei einem relativ kleinen Datastore. Das liegt daran, daß viele Betriebssysteme in der Lage sind ein paar Verzeichnisse im Speicher zu halten. Das System versucht das für einige der zuletzt benutzten Verzeichnisse, aber vielleicht nicht für 256 (storedepth=2) oder sogar 4096 (storedepth=3). Mit FreeBSD und einem UFS Filesystem bekam ich die besten Ergebnisse mit storedepth=1.

Nun, wie entscheidet Entropy wo es nach einer Datei sucht? Jede Dateiname ist ein 40-stelliger Hex-string. Dieser repräsentiert den SHA1 Hash-Wert für die Datei (=Key bzw. Schlüssel). Für die meisten Dateien ist das der SHA1 Hash des Dateiinhalts (bei den Bit Chunks). Für umgeleitete Schlüssel (CHK@, SSK@, und KSK@) dagegen ist der Dateiname der SHA1 Hash des Inhalts der Datei, die man erhält, wenn man den Inhalt anhand der Liste der Chunks in dem Key rekonstruiert.

Für detaillierte Informationen, wie ein Verzeichnis für einen Key von Entropy gewählt wird, siehe src/store_tree.c. Die letzten 4 Stellen des SHA1 Hash werden zur Vorauswahl eines Verzeichnisses und für Routinginformationen benutzt. Die 4. Stelle von rechts bestimmt die erste Verzeichnisebene, die 3.Stelle die zweite Ebene (wenn vorhanden) und die 2.Stelle die dritte Ebene. Die erste Stelle von rechts wird nicht für die Datenbank benutzt.

Warteschlangen und Routing

Nun, es war viel die Rede von Fingerprints, Routen (oder Arten von Schlüsseln) und der Keyroute-Funktion, welche die Route für einen spezifischen Key berechnet. Wie entscheidet Entropy, welcher Node welchen Key bekommt, oder welche nodes nach einem bestimmten Key gefragt werden? Zuerst einmal eine Grafik, welche zeigt, wie der Entscheidungsprozeß funktioniert:

Bild 5 - Warteschlangen (Queues)

Das X auf der linken Seite ist eine Key-Route: ein wert zwischen 0 und 15 inklusive. Nun schaut Entropy sich den Fingerabdruck (fingerprint) aller ausgehenden Peer-Nodes an. Dabei wird dieser Wert fingerprint[X] (z.B. fingerprint[0] oder fingerprint[1] bis zu fingerprint[15]) mit einem bestimmten Grenzwert verglichen. Dieser Grenzwert wiederum hängt von der Anzahl der "hops-to-live" (HTL, sovielwie "Anzahl der Sprünge") einer Nachricht ab. Er ist immer zwischen 0 und 255.

Für sehr niedrige HTL-Werte ist der Grenzwert sehr hoch - 255 oder 100%. Dagegen ist für den höchsten HTL-Wert (normalerweise 25) der Grenzwert sehr niedrig (0). Der Wertebereich liegt also zwischen 0 und 255, da jeder fingerprint aus 16 Zeichen (Bytes, unsigned char) zusammengesetzt ist. Wenn ein Fingerprint-Wert eines kontaktierten Partners an der Position X größer oder gleich dem aktuellen Grenzwert ist, wird Entropy versuchen, die Nachricht an diesen Entropy-Knoten zu senden. Die Fragezeichen (im Bild 5) in den Kreisen links von den Peer-Kontakten sind einfache Platzhalter für die Frage: "Entpricht der Fingerprint dieses Kontakts an der Position X der Keyroute X der aktuellen Nachricht gut genug?". Die Antwort ist dann ein einfaches ja oder nein.

Nun zu der Grafik: Der erste Peer Peer #1 hat einen gut genug passenden Fingerprint für unseren Key. Die roten Kästchen jedoch bedeuten, daß die Warteschlange für Nachrichten z.Zt. voll ist. Deshalb bekommt dieser Peer auch kein Nachricht bzgl. des aktuellen Keys. In unserem Beispiel bedeutet der Fingerprint für Peer #2 daß dieser Node wahrscheinlich keine Keys vom Typ X möchte (oder hat). Das gleiche gilt leider auch für Peer #3, welcher auch in den meisten Fällen keine Keys vom Typ X von uns akzeptieren wird bzw. auch keine Keys vom Typ X uns liefert. Das ist schlecht, da Peer #3 gerade eine leere Warteschlange hat. Für Peer #4 wäre der fingerprint[X] gleich oder größer dem aktuellen Grenzwert und - Hurra! - dieses Peer hat sogar freien Platz in seiner Warteschlange. Und genauso ist Peer #5 gut genug, um diese Nachricht zu bekommen. Seine Warteschlange ist nur etwas voller als die von Peer #4. Das bedeutet gewöhnlich, daß es etwas länger dauert, bis die Nachricht gesendet ist.

So würde in unserem Beispiel die Nachricht für einen Key mit Route X an zwei unserer Ausgangs-Kontakte gesendet. Diese Nachricht könnte z.B. eine Anfrage nach einem Schlüssel (key) sein. Im Beispiel würde Peer #4 theoretisch die Anfrage eher als Peer #5 sehen. In der Praxis könnte allerdings eine Reihe von Umständen dagegensprechen: Peer #4 könnte zu beschäftigt (sprich: überlastet) sein um eingehende Anforderungen zu bearbeiten, Peer #5 könnte eine bedeutend schnellere Anbindung haben, das lokale Prozeßmanagment könnte dem Prozeß von Peer #5 mehr Rechenzeit zuordnen...

Die Warteschlangen jeder ausgehenden Verbindung sind ein Maß zum entkoppeln der Nachrichtenverarbeitung vom aktuellen Prozeß-Timing. Ein Key wird eingefügt oder angefragt und die Nachrichten, welche diese Aktion behandeln, werden in die Nachrichten-Warteschlange des ausgewählten Peers eingefügt. Dann wartet der aktive Prozeß einige Zeit, abhängig von der Anzahl der zu sendenden Nachrichten, der zur Zeit verfügbaren Bandbreite und des hops-to-live (HTL) Wertes einer Nachricht bevor er weitermacht. Im Falle einer Key-Anfrage überprüft der Prozeß die lokale Datenbank (datastore), ob der oder die Key(s) schon in unserem Node angekommen sind.

Wie man sehen kann gibt es keinen Handshake irgendeiner Art mit den ausgehenden Verbindungen. Sie empfangen einfach Nachrichten mit Key's und manchmal die Daten eines Key's. Unser Node weiß nicht, ob der Kontakt-Node wirklich diese Nachricht bearbeitet, ob er sie ignoriert oder ob er die Nachricht an einen anderen Node weiterschickt.

Man könnte nun fragen, wie man Ergebnisse ohne irgendeinen Handshake erhalten kann? Unser Node hat außerdem einige eingehenden Verbindungen. Auf diesen eingehenden Verbindungen senden uns andere Nodes Nachrichten, genauso wie wir ihnen Nachrichten schicken. Nachdem wir eine Anfrage an einen oder mehrere Nodes in der ausgehenden Richtung gesendet haben, sehen wir evtl. ein oder mehrere "Angebote" des Keys. Oder sogar ein "Einfügen" exakt des Keys, den wir angefragt haben auf einer unserer eingehenden Verbindung(en). Angebote ("Advertizements") werden auch manchmal ignoriert. Das hängt dann von unserem eigenen Fingerprint und der Route des beworbenen Keys ab. Außerdem wird auch eine auf Zufall basierende Entscheidung zum akzeptieren oder ignorieren eines Keys getroffen. Einfügungen (inserts) werden gewöhnlich akzeptiert, es sei denn wir haben den Key schon. Einfügungen werden des weiteren"überwacht" durch eine Liste mit kürzlich angefragten Keys, so daß kein Nachbar-Node unsere Datenbank überfluten kann mit Daten, die wir nicht wollen - weder für uns selbst noch im Interesse eines anderen Nodes (der von uns Daten abfragt).

Freenet Client Protocol

The Freenet Client Protocol, as the name suggests, was designed by the developers of Freenet. It is a specification for a set of names and conventions for a client application to talk to a Freenet node. Entropy implements a very similiar interface, except for some minor differences that should not hurt any well designed client (some differences _do_ hurt FCP clients, but that is because they are relying on undocumented details or definitions of Freenet).

A Freenet node usually listens on 127.0.0.1:8481 for FCP clients, that's why I've chosen the default port number (or service) 8482 for Entropy. You can run both, Freenet and Entropy, on the same machine without collisions.

After a client made a socket connection to the FCP port, it will send a request that is plain text for the most part. But prior to any text, it must send a header of four bytes. This header might be used for protocol identification in the future. Right now, the only possible and accepted header is 00 00 00 02 - this is true for Freenet as well as for Entropy and all FCP clients seem to have this hardcoded.

The text part of every Request consists of two or more lines, terminated with CR (\n in C notation). The first line is the type of request that is send. Then there can be from zero to several lines with parameters for a request, and finally there is a message terminating line.

The list of commands or requests that entropy understands is as follows:

• ClientHello ... EndMessage
• ClientGet ... EndMessage
• ClientPut ... Data
• GenerateCHK ... EndMessage
• ClientDelete ... EndMessage
• GenerateSVKPair ... EndMessage
• FECSegmentFile ... EndMessage
• FECEncodeSegment ... Data
• FECDecodeSegment ... EndMessage
• FECMakeMetadata ... Data
• GenerateSHA1 ... Data

ClientHello

[00][00][00][02]
ClientHello
EndMessage

NodeHello
Node=ENTROPY,0,3.0,215
Protocol=1.2
MaxFilesize=1fffff
EndMessage

[00][00][01][02]
ClientHello
EndMessage

NodeHello
Node=ENTROPY,0,3.0,215
Protocol=1.2
MaxFilesize=1fffff
MaxHopsToLive=a
SVKExtension=BCMA
EndMessage

ClientGet

ClientGet
URI=entropy:KSK@gpl.txt
HopsToLive=19
EndMessage

NodeFailed
Reason=Some description of the reason why the request failed
EndMessage

URIError
URI=xxx
EndMessage

RouteNotFound
Reason=No route found
EndMessage

DataNotFound
Reason=No data found
EndMessage

ClientGet
URI=xxx
[HopsToLive=xx]
[MaxFileSize=xxxx]
[Verbose={boolean}]
EndMessage

NodeGet
URI={internal-fragment-key}
Offset=xxx
DataLength=xxx
Percent=dd%
EndMessage

DataFound
DataLength=xxxx
MetadataLength=xxxx
EndMessage

DataChunk
Length=xxxx
Data
{raw binary data}

ClientPut

GenerateCHK

ClientDelete

GenerateSVKPair

FECSegmentFile

FECEncodeSegment

FECDecodeSegment

FECMakeMetadata

GenerateSHA1