2.1.2. Merkle Consistency Proofs (Merkle-Konsistenzbeweise)
2.1.2. Merkle Consistency Proofs (Merkle-Konsistenzbeweise)
Merkle consistency proofs (Merkle-Konsistenzbeweise) belegen die Append-Only-Eigenschaft des Baums. Ein Merkle consistency proof für einen Merkle Tree Hash MTH(D[n]) und einen zuvor bekannt gegebenen Hash MTH(D[0:m]) der ersten m Blätter, m <= n, ist die Liste von Knoten im Merkle Tree, die nötig ist, um zu verifizieren, dass die ersten m Eingaben D[0:m] in beiden Bäumen gleich sind. Ein Konsistenzbeweis muss also eine Menge Zwischenknoten (d. h. Commitments zu Eingaben) enthalten, die ausreicht, um MTH(D[n]) zu verifizieren, sodass (eine Teilmenge) derselben Knoten auch zur Verifikation von MTH(D[0:m]) genutzt werden kann. Wir definieren einen Algorithmus, der den (eindeutigen) minimalen Konsistenzbeweis ausgibt.
Gegeben eine geordnete Liste von n Eingaben in den Baum, D[n] = {d(0), ..., d(n-1)}, ist der Merkle consistency proof PROOF(m, D[n]) für einen früheren Merkle Tree Hash MTH(D[0:m]), 0 < m < n, definiert als:
PROOF(m, D[n]) = SUBPROOF(m, D[n], true)
Der Subproof für m = n ist leer, wenn m der Wert ist, für den PROOF ursprünglich angefordert wurde (d. h. der Subtree-Merkle-Tree-Hash MTH(D[0:m]) bekannt ist):
SUBPROOF(m, D[m], true) = {}
Der Subproof für m = n ist der Merkle Tree Hash, der die Eingaben D[0:m] festhält; andernfalls:
SUBPROOF(m, D[m], false) = {MTH(D[m])}
Für m < n sei k die größte Zweierpotenz kleiner als n. Der Subproof ist dann rekursiv definiert.
Wenn m <= k, existieren die rechten Subtree-Einträge D[k:n] nur im aktuellen Baum. Wir beweisen, dass die linken Subtree-Einträge D[0:k] konsistent sind, und fügen ein Commitment zu D[k:n] hinzu:
SUBPROOF(m, D[n], b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])
Wenn m > k, sind die linken Subtree-Einträge D[0:k] in beiden Bäumen identisch. Wir beweisen, dass die rechten Subtree-Einträge D[k:n] konsistent sind, und fügen ein Commitment zu D[0:k] hinzu.
SUBPROOF(m, D[n], b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k])
Hier ist : Konkatenation von Listen, und D[k1:k2] bezeichnet wie zuvor die Liste der Länge (k2 - k1) {d(k1), d(k1+1),..., d(k2-1)}.
Die Anzahl der Knoten im resultierenden Beweis ist nach oben durch ceil(log2(n)) + 1 begrenzt.