2.1.1. Merkle Audit Paths (Merkle-Audit-Pfade)

2.1.1. Merkle Audit Paths (Merkle-Audit-Pfade)

Ein Merkle audit path (Merkle-Audit-Pfad) für ein Blatt in einem Merkle Hash Tree ist die kürzeste Liste zusätzlicher Knoten im Merkle Tree, die benötigt wird, um den Merkle Tree Hash für diesen Baum zu berechnen. Jeder Knoten im Baum ist entweder ein Blattknoten oder wird aus den beiden direkt darunter liegenden Knoten berechnet (d. h. in Richtung der Blätter). In jedem Schritt nach oben (zur Wurzel) wird ein Knoten aus dem Audit-Pfad mit dem bisher berechneten Knoten kombiniert. Mit anderen Worten besteht der Audit-Pfad aus der Liste fehlender Knoten, die nötig sind, um die Knoten von einem Blatt bis zur Wurzel zu berechnen. Stimmt die aus dem Audit-Pfad berechnete Wurzel mit der echten Wurzel überein, ist der Audit-Pfad ein Beweis, dass das Blatt im Baum existiert.

Gegeben eine geordnete Liste von n Eingaben in den Baum, D[n] = {d(0), ..., d(n-1)}, ist der Merkle audit path PATH(m, D[n]) für die (m+1)-te Eingabe d(m), 0 <= m < n, wie folgt definiert:

Der Pfad für das einzelne Blatt in einem Baum mit ein-elementiger Eingabeliste D[1] = {d(0)} ist leer:

PATH(0, {d(0)}) = {}

Für n > 1 sei k die größte Zweierpotenz kleiner als n. Der Pfad für das (m+1)-te Element d(m) in einer Liste von n > m Elementen ist dann rekursiv definiert als

PATH(m, D[n]) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and

PATH(m, D[n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for m >= k,

wobei : Konkatenation von Listen ist und D[k1:k2] wie zuvor die Liste der Länge (k2 - k1) {d(k1), d(k1+1),..., d(k2-1)} bezeichnet.