Wie kommt es, dass der Merkle-Baum effizienter ist, wenn Baumzweige nicht in der Blockchain gespeichert werden?

Angenommen, wir haben 8 Transaktionen in einem Block Xwie folgt und wir kennen den Hash-Wert jedes Knotens des gesamten Merkle-Baums (d. h. einschließlich zwischengeschalteter Knoten wie 45). Wenn dann jemand behauptet, dass die Transaktion tin existiert Xund sie sich unter befindet 6. Um dies zu verifizieren, müssen wir nur die Hash-Werte bei 7, 45, 0123 nachschlagen und den Hash bis ganz nach oben und mit dem Merkle-Stamm 01234567 vergleichen.

Ich nehme an (basierend darauf ), dass der Merkle-Baum schneller ist als das direkte Hashing der Verkettung von TXID0 ~ TXID7, weil der Hash-Algorithmus auf kleinen Dateien schneller läuft (sogar ~log(N)mal ausgeführt wird) als auf einer großen Datei (dh die Verkettung von NTXIDs Nist hier 8 ). ) auf einmal.

Aber wenn ich diesen Beitrag lese, scheint es, dass nur Merkle-Root und NTXIDs in einem Block gespeichert werden und wir jedes Mal, wenn wir eine Transaktion verifizieren, die Baumstruktur neu erstellen müssen, was tatsächlich Hash-Funktionen ~Nmal statt ~log(N)mal ausführen würde (wenn ich mathematisch richtig lag).

Meine Fragen sind:

  1. Ist Hash- ~NZeiten immer noch schneller als Hash-Zeiten bei Nverketteten Hash-Werten?
  2. Warum wird der Merkle-Baum nicht gespeichert? Liegt es an Speicherüberlegungen?

Geben Sie hier die Bildbeschreibung ein

Antworten (1)

Die Geschwindigkeit des Hashs ist ungefähr linear in Bezug auf die Anzahl der verarbeiteten Bytes: SHA2 verarbeitet Blöcke von 64 Bytes gleichzeitig, und die benötigte Zeit entspricht der Anzahl der verarbeiteten Blöcke. Die Berechnung eines Hashtrees verarbeitet aufgrund der Zwischenebenen mehr Blöcke, aber fast die gesamte Verarbeitung kann parallel erfolgen, im Gegensatz zum linearen Hash, der sequentiell durchgeführt werden muss.

Ein Knoten verifiziert einen Block nur einmal. Zu diesem Zweck spielt es keine große Rolle, ob der Hash ein Baum oder linear ist. Wenn jedoch die Parallelität ausgenutzt wird, ist die Berechnung eines Baum-Hash schneller.

[Und Bitcoin Core verwendet Vektoranweisungen, um Baum-Hashes für eine mehrfache Beschleunigung parallel zu verarbeiten. Es macht sich derzeit nicht die Mühe, dafür mehrere Kerne zu verwenden, obwohl es möglich wäre.]

Ein Lite-Client validiert jedoch keinen ganzen Block, er holt normalerweise nicht einmal einen ganzen Block. Stattdessen möchte es wissen, ob sich eine Transaktion in einem Block befindet. Hier spielt die Hash-Struktur eine große Rolle. Wenn ein linearer Hash verwendet würde, wäre die einzige Möglichkeit, zu beweisen, dass sich eine Transaktion in einem Block befindet, an einen Lite-Client, ihm den gesamten Block zu senden. Bei einem Baum-Hash muss man ihm nur log2(n)-Werte und die Transaktion selbst schicken.

Der Baum wird in aktuellen Bitcoin-Implementierungen nicht gespeichert, da es keine Operation gibt, die wirklich davon profitieren würde, wenn sie in den Implementierungen gespeichert wird. Der Nachweis, dass ein Lite-Client bezahlt wurde, ist eine relativ seltene Operation, und die Neuberechnung des Hash-Baums ist kostengünstig. Eine Implementierung könnte mit dem Speichern beginnen, wenn sie einen Grund dafür hätte. TXIDs werden ebenfalls nicht gespeichert, da sie nur aus den Transaktionen selbst berechnet werden können.

Wie kommt es, dass der Merkle-Baum effizienter ist, wenn Baumzweige nicht in der Blockchain gespeichert werden?
AntwortenHierDatenschutz-Bestimmungen1y, 0v