2.1. Merkle Hash Trees (Merkle-Hash-Bäume)

2.1. Merkle Hash Trees (Merkle-Hash-Bäume)

Logs verwenden einen binären Merkle Hash Tree (Merkle-Hash-Baum) für effiziente Prüfungen. Der Hash-Algorithmus ist SHA-256 [FIPS.180-4] (für dieses Experiment fest; es wird erwartet, dass jedes Log künftig einen Hash-Algorithmus angeben kann). Die Eingabe in den Merkle Tree Hash ist eine Liste von Dateneinträgen; diese Einträge werden gehasht, um die Blätter des Merkle Hash Tree zu bilden. Die Ausgabe ist ein einzelner 32-Byte-Merkle Tree Hash. Gegeben eine geordnete Liste von n Eingaben D[n] = {d(0), d(1), ..., d(n-1)}, ist der Merkle Tree Hash (MTH) wie folgt definiert:

Der Hash einer leeren Liste ist der Hash eines leeren Strings:

MTH({}) = SHA-256().

Der Hash einer Liste mit einem Eintrag (auch Leaf Hash (Blatt-Hash) genannt) ist:

MTH({d(0)}) = SHA-256(0x00 || d(0)).

Für n > 1 sei k die größte Zweierpotenz kleiner als n (d. h. k < n <= 2k). Der Merkle Tree Hash einer n-elementigen Liste D[n] ist dann rekursiv definiert als

MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])),

wobei || Konkatenation ist und D[k1:k2] die Liste {d(k1), d(k1+1),..., d(k2-1)} der Länge (k2 - k1) bezeichnet. (Beachten Sie, dass die Hash-Berechnungen für Blätter und innere Knoten unterschiedlich sind. Diese Domain Separation (Domänentrennung) ist für Second Preimage Resistance (Zweit-Präimage-Widerstand) erforderlich.)

Wir verlangen nicht, dass die Länge der Eingabeliste eine Zweierpotenz ist. Der resultierende Merkle Tree kann daher unausgeglichen sein; seine Form ist jedoch durch die Anzahl der Blätter eindeutig bestimmt. (Hinweis: Dieser Merkle Tree entspricht im Wesentlichen dem Vorschlag History Tree [CrosbyWallach], außer dass unsere Definition nicht volle Bäume anders behandelt.)