Merkle Root und Merkle Proofs

Wenn ich Ihre Frage lese, vermute ich, dass der Grund für Ihre Verwirrung in der Umgebung liegt, in der Merkle-Bäume verwendet werden. Ich denke, Sie haben Recht, dass in der Bitcoin-Welt die Einstellung als selbstverständlich angesehen wird und normalerweise nicht klar erklärt wird.

Hier sind meine zwei Cent. Um den Effizienzaspekt von Merkle-Bäumen zu verstehen, betrachten Sie die beiden Parteien, die tatsächlich am Protokoll beteiligt sind:

1. Ein vollständiger Bitcoin -Knoten mit vollständigen Blöcken.
2. Ein dünner Bitcoin -Knoten , der Header hat, aber überprüfen möchte, ob sich eine Transaktion in einem der vollständigen Blöcke befindet.
3. (Es könnte erwähnenswert sein, dass das aktuelle Bitcoin-Protokoll es einem Thin Node nicht erlaubt, effizient zu überprüfen, ob sich eine Transaktion nicht in einem der Blöcke befindet.)

Denken Sie zunächst daran, dass beim Empfang eines neuen Blocks Bmit Blockheader Hund Transaktionen Tder vollständige Knoten Folgendes tut:

1. berechnet h = SHA256(H), verifiziert den Proof-of-Work in hund prüft den Zeitstempel in H, etc.
2. t \in Tverifiziert für jede Transaktion die tSignatur(en) von , verifiziert, tdass keine doppelten Ausgaben getätigt werden, und fügt es tals Blatt ganz rechts an den Merkle-Baum des aktuellen Blocks an . (Denken Sie daran, dass für jeden Block ein anderer Merkle-Baum berechnet wird. Natürlich muss das Anhängen der Transaktion in einer kanonischen Reihenfolge erfolgen, um denselben Root-Hash wie im Block-Header zu erhalten H.)
3. Nachdem alle t \in Tverifiziert und angehängt wurden, berechnet und speichert er den Merkle-Baum, wobei natürlich alle inneren Knoten- Hashes und der Root-Hash r berechnet werden (wie in Ihrer Merkle-Baum-Abbildung dargestellt).
4. Entscheidend ist, dass überprüft wird, ob der berechnete Root-Hash rgleich dem Root-Hash im Block-Header ist H.

Moral der Geschichte: Ja, Sie haben Recht, dass der Beweiser (in diesem Fall der vollständige Knoten) die inneren Knoten-Hashes benötigt, um die Zugehörigkeit zu einem Blatt in Bezug auf eine Merkle-Wurzel zu beweisen r: Er kann sie zwischenspeichern oder neu berechnen (es gibt etwas Literatur zu Kompromissen hier). (Ich denke) Bitcoin Full Nodes cachen einfach alle Hashes, wie in Schritt 3 beschrieben. Wichtig ist, dass die inneren Hashes nicht Teil des 1-MB-Blocks sind B: Es wäre Platzverschwendung, da Full Nodes sie einfach aus den Blättern neu berechnen können ( dh die TXNs) und den neu berechneten Root-Hash mit dem im Block-Header abgleichen. Beachten Sie, dass dies verhindert, dass Netzwerkgegner die Transaktionen manipulieren.

Denken Sie zweitens daran, dass ein dünner Knoten beim Empfang eines neuen Blockheaders Hnur Schritt (1) von oben ausführt.

Nun, hier ist die Einstellung in Bitcoin:

1. Der vollständige Knoten enthält alle Blöcke, einschließlich der Hashes der inneren Knoten, die in Schritt 3 oben berechnet wurden.
2. Der dünne Knoten hat alle Blockheader. Denken Sie daran, dass jeder Header die Merkle-Wurzel enthält.
3. Der Full Node möchte den Thin Node davon überzeugen, dass sich eine Transaktion tin einem Block Bmit Blockheader befindet H(den der Thin Node natürlich hat).

These: Merkle-Bäume ermöglichen es dem Full Node, die Thin Nodes effizient davon zu überzeugen , wodurch verhindert wird, dass der Full Node tin wechselt t'(was es einem Full Node ermöglichen würde, einen Thin Node dazu zu bringen, zu glauben, er sei bezahlt worden).

Beweis: Bezeichne rdie Merkle-Wurzel in H. Der dünne Knoten hat das gleiche Hund r. Der vollständige Knoten hat die inneren Knoten "unter" rzwischengespeichert (erinnern Sie sich an Schritt 3 des vollständigen Knotens). Der vollständige Knoten ruft den (bereits zwischengespeicherten) Geschwisterpfad ab, beginnend mit dem Blatt, das die Transaktion enthält, tund geht den ganzen Weg bis zur Wurzel rund sendet ihn an den dünnen Knoten. Der dünne Knoten hasht rekursiv tmit den empfangenen Geschwistern und erhält einen Root-Hash r'(hier mit der Hand winken, vorausgesetzt, Sie verstehen Merkle-Beweise). Das prüft der Thin Node r == r'.

Effizienz: Der vollständige Knoten (dh der Beweiser) muss nur O(\log{n})Geschwister in einem Merkle- nBlattbaum an den dünnen Knoten (dh den Verifizierer) senden, der nur einen 256-Bit-Root-Hash hat r. (Natürlich muss der Beweiser alle Blätter und alle inneren Knoten haben, wie zuvor besprochen.)

Natürlich garantiert dieses Protokoll, dass der vollständige Knoten keine Transaktion „unter“ der Wurzel „lügen“ kann r. Wenn eine Transaktion vorhanden ist, kann der vollständige Knoten sie informell nicht in eine andere Transaktion ändern und einen Beweis dafür fälschen (dh einen Geschwisterpfad). Auch informell, wenn eine Transaktion überhaupt nicht vorhanden ist, kann der Full Node keinen Beweis dafür fälschen, dass sie vorhanden ist.

Um Ihre Fragen zu beantworten:

Bei Frage A scheint es darum zu gehen, wie die Mitgliedschaft in einer Transaktion tfunktioniert. Du sagst,

Würden Sie sich dazu nicht einfach die Liste der Blatt-Hashes ansehen, um festzustellen, ob H(D) vorhanden ist? Warum irgendetwas mit der Merkle-Wurzel machen?

Ich glaube du missverstehst die Einstellung. Denken Sie daran, dass es bei der Diskussion kryptografischer Protokolle unbedingt erforderlich ist, die Namen der Parteien zu nennen, anstatt zweideutige Pronomen wie „Sie“ und „Ich“ zu verwenden. „Prover“ und „verifier“ können knapp und langweilig sein, sind aber präzise .

Der Thin Node kann nicht „nur auf die Liste der Blatt-Hashes schauen“, da er nur den Root-Hash und keine Blätter hat , sondern sicher sein möchte, dass ein Blatt vorhanden ist. Der vollständige Knoten könnte dem dünnen Knoten alle Blätter senden und den dünnen Knoten hashen lassen, wodurch derselbe Root-Hash erhalten wird. Das wäre jedoch ineffizient : O(n)Bandbreite für nBlätter. Im Gegensatz dazu ist ein Merkle-Beweis für ein Blatt unter einem Root-Hash viel effizienter : nur O(\log{n})Hashes + das Blatt selbst.

Frage B sollte jetzt beantwortet sein: Der vollständige Knoten hat alle inneren Knoten-Hashes. Er sendet den Geschwisterpfad an den dünnen Knoten, der einfach rekursiv von dem Blatt, das überprüft wird, nach oben gehasht wird. Der dünne Knoten verifiziert, dass die von ihm erhaltene Wurzel mit der Wurzel im Block-Header übereinstimmt.

Frage C :

Behält Bitcoin die Merkle-Baum-Hashes nicht nur für die Blattknoten, sondern für den gesamten Baum bis zur Wurzel bei?

Nicht in den Blöcken selbst: Das wäre wie gesagt Platzverschwendung. Vollständige Knoten berechnen die internen Hashes und den Root-Hash und speichern alles lokal auf der Festplatte (vermutlich habe ich mir den Quellcode nicht wirklich angesehen). Dann sind sie bereit, Beweise für jede Transaktion in jedem Block an jeden Thin Node zu liefern.

Wo genau und wie genau werden diese Informationen gespeichert? Alles, was ich je sehe, ist die Merkle-Wurzel im Block ...

Vermutlich auf der Festplatte in der Datenbank des vollständigen Knotens. Aber nicht im Block: Sie sind redundante Informationen, da Blöcke, die Blätter enthalten =>, Hashes von inneren Knoten und Wurzelknoten berechnen können.

Ich glaube, ich habe einmal einen Merkle-Wert für einen Transaktionsknoten gesehen, aber ich habe nie Metadaten gesehen, die sich auf Nicht-Baum-Merkle-Knoten in der Bitcoin-Blockchain beziehen ...

Ugh, ich möchte sagen: "Ja, denn es wäre eine Platzverschwendung, interne Node-Hashes in den Blöcken zu speichern." Aber wenn ich genauer hinsehe, weiß ich nicht wirklich, was Sie mit „Merkle-Wert für einen Transaktionsknoten“ und „Metadaten in Bezug auf Nicht-Baum-Merkle-Knoten“ meinen.

Hoffe das hilft!

Sagen Sie einen Block, der aus diesen 10 Transaktionen besteht, die durch ihre txids bei den Indizes 0 bis 9 gekennzeichnet sind:

E1AF205960AE338A37174B407EE71067C3CD7F04D48A5CEC7E13F6ECCB61DCBC
A314970CD7C647D1CC0A477E1A2122B98205B6924B73001B8DAB20EE81C2F4F7
B08EB9DCE0452A1B1970C4D29E88BDEE07669A2A5D1B08586D7FFA17B2E3F6B5
958B9E94AEA9A485BA494C50FB3192558057F7CAED9705D4B11369F071F10642
3D278CA01CC527D4C7D577B668E0B976FBBCB94E6A9BA89664C721F36FADA6A1
95AFFA405501498EF6F4E4B6CDDC1F1B24B9D2E534584B31A9142C453920C889
D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625
AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57
90E03319DDC9D48DA38AB39B2F37C0A5AF5AFC736F6FF2A9D8B8653E0FEB308D
84251842A4C0F0E188E1C2BF643EC37A1402DD86A25A9AB5004633467D16E313

Mit einer Merkle-Wurzel, auf die wir uns beide einigen (sie befindet sich in der Blockchain):

B152ECA4364850F3424C7AC2B337D606C5CA0A3F96F1554F8DB33D2F6F130BBE

Und sagen Sie, Sie wollen, dass ich Ihnen beweise, dass die Transaktion D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625in diesem Block ist.

Ich gebe Ihnen diesen Beweis:

AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57,
EFC2B3DB87FF4F00C79DFA8F732A23C0E18587A73A839B7710234583CDD03DB9,
F1B6FE8FC2AB800E6D76EE975A002D3E67A60B51A62085A07289505B8D03F149,
E827331B1FE7A2689FBC23D14CD21317C699596CBCA222182A489322ECE1FA74

Und Ihnen sagen, dass diese Transaktion im Index 6ist und dass dies ein Baum der Tiefe ist 4.

(2^4) + 6 = 22, und das ist 10110in Basis 2. Diese Darstellung in Basis 2 ist der Weg, den wir von der ersten txid nehmen müssen, für die wir die Inklusion bis zur Wurzel beweisen wollen.

Jetzt müssen Sie nur noch den Pfad von der txid zur Wurzel gehen, und wenn der Beweis korrekt ist, sollten Sie die Merkle-Wurzel des Blocks erhalten. Wir beginnen den Pfad von rechts nach links, also mit dem 0Bit der Zahl zur Basis 2 (die 1 ganz links wird nicht verwendet (es ist wirklich die Wurzel)). Da dies eine ist 0, sollten wir "unseren" Hash (die txid) auf der linken Seite platzieren:

hash256 D97A21CF46FD5AFB0BF9EA4237BC4BF5C84E8B47D38D1EEE2BBEB5C0F8A1C625|AE1E670BDBF8AB984F412E6102C369AECA2CED933A1DE74712CCDA5EDAF4EE57
=
066AD6D9939EC0C90B7F3B775122785BD8ACA2A2C5857205AF7E0615E9AF9796

Das nächste ist ein 1, "unser" Hash ist rechts :

hash256 EFC2B3DB87FF4F00C79DFA8F732A23C0E18587A73A839B7710234583CDD03DB9|066AD6D9939EC0C90B7F3B775122785BD8ACA2A2C5857205AF7E0615E9AF9796
=
8BE15FC2AB11EF3E079568D43B2B09ED5A5690FB13ECB1032F7AAB99238A1847

Als nächstes kommt 1wieder a, also sind wir wieder rechts :

hash256 F1B6FE8FC2AB800E6D76EE975A002D3E67A60B51A62085A07289505B8D03F149|8BE15FC2AB11EF3E079568D43B2B09ED5A5690FB13ECB1032F7AAB99238A1847
=
8D9D737B484E96EED701C4B3728AEA80AA7F2A7F57125790ED9998F9050A1BEF

Als nächstes kommt ein 0, wir sind auf der linken Seite :

hash256 8D9D737B484E96EED701C4B3728AEA80AA7F2A7F57125790ED9998F9050A1BEF|E827331B1FE7A2689FBC23D14CD21317C699596CBCA222182A489322ECE1FA74
=
B152ECA4364850F3424C7AC2B337D606C5CA0A3F96F1554F8DB33D2F6F130BBE

Und das ist die Merkle-Wurzel des Blocks. Der Beweis ist richtig. Die txid existiert in einem Block-on-Chain in diesem spezifischen Index, und der Block hat die richtige Tiefe.

Bei einem sehr großen Baum ist der Effekt sogar noch dramatischer. Die Anzahl der Schritte, die erforderlich sind, um zu beweisen, dass sich ein Element in einem Baum befindet, ist logarithmisch zur Größe des Baums, sodass der Beweis klein bleibt. Hoffentlich haben Sie danach gefragt.

Diese Transaktionen sind 0000000000000a3290f20e75860d505ce0e948a1d1d846bec7e39015d242884bübrigens von Block.

Es gibt zwei Arten von Effizienzen:

1. Berechnung: Der Merkle-Baum ist in Bezug auf Berechnung und Suche so effizient wie jeder andere binäre Suchbaum.

2. Lagerung: Hier passiert die Magie.

Merkle-Wurzel: H _ABCDEFGH
Hash zur Überprüfung: H _D

Prozess:
1. H _CD = Hash( H _C , H _D )
2. H _ABCD = Hash( H _CD , H _AB )
3. H _ABCDEFGH = Hash( H _ABCD , H _EFGH )

Im gesamten Überprüfungsprozess von H _D (von insgesamt 8) müssen wir nur 3 zusätzliche Hashes speichern (H _C , H _AB , H _EFGH ).

Speicherkomplexität: log ₂ n = log ₂ 8 = 3

Wenn n = 1024: log ₂ n = log ₂ 1024 = 10
Wenn n = 1048576: log ₂ n = log ₂ 1048576 = 20

In diesem Sinne sind Merkle-Bäume im Vergleich zu anderen Datenstrukturen effizient.

Damit ein Bitcoin-Block gültig ist, muss der Header des Blocks zu einer Ausgabe gehasht werden, die innerhalb eines bestimmten Wertebereichs liegt (definiert durch die aktuelle Netzwerkschwierigkeit).

Die Merkle-Root ist eine Komponente des Block-Headers, sodass die Merkle-Root tatsächlich eine kryptografische Verpflichtung zu den im Block enthaltenen Transaktionen darstellt. Das Ändern einer einzelnen Transaktion (oder der Reihenfolge der Transaktionen) würde die Merkle-Wurzel und damit den Hash des Blocks ändern (was den Block mit überwältigender Wahrscheinlichkeit ungültig machen würde).

In Bezug auf A: Würden Sie sich dazu nicht einfach die Liste der Blatt-Hashes ansehen, um festzustellen, ob H(D) vorhanden ist? Warum irgendetwas mit der Merkle-Wurzel machen?

Die Blatt-Hashes sind nicht explizit im Block enthalten, aber es ist für jeden Knoten trivial zu überprüfen, ob eine bestimmte Transaktion ordnungsgemäß im Block enthalten ist (und daher im Merkle-Root enthalten ist). Dies geschieht, indem die Transaktion [in Ihrem Beispiel H(D)] gehasht und dann H(D) mit H(C) kombiniert wird, um H(CD) zu erhalten, und so weiter, bis die Merkle-Wurzel erreicht (und gefunden) ist um richtig zu sein gegen die Merkle-Wurzel des Blocks).

Full-Node-Clients laden die gesamte Blockchain herunter und sind somit in der Lage, diese Validierung selbst durchzuführen. 'Litewallet'-Clients laden einfach die Block-Header herunter und können die vereinfachte Zahlungsverifizierung (SPV) verwenden, um eine kryptografische Überprüfung der Transaktionsgültigkeit auf weniger intensive Weise durchzuführen. Bei SPV werden nur die Hashes im relevanten Zweig des Baums angefordert, wobei von der betreffenden Transaktion bis zur Wurzel gearbeitet wird. Jeder Versuch der Peers der Brieftasche, über die Transaktionen/Hashes in einem Block zu lügen, führt zu einem ungültigen Merkle-Root, sodass es für einen Peer unmöglich ist, zu lügen und zu sagen, dass eine Transaktion in einem Block enthalten ist, wenn dies tatsächlich nicht der Fall ist.

In Bezug auf B: Wenn Sie den H(D)-Hashwert haben und wissen, dass sein Blattpaar H(C) ist, können Sie H(CD) berechnen. Aber an diesem Punkt, wenn sich H(D) geändert hat und Sie den alten Wert für H(CD) kennen, könnten Sie Ihre Untersuchung nicht sofort kurzschließen, weil der neue H(CD)-Wert nicht gleich dem alten wäre H(CD)-Wert?

Es geht nicht darum, ein „neues“ oder „altes“ H(CD) zu kennen, es gibt einfach das H(CD), das ein Zwischenschritt bei der Berechnung der Merkle-Wurzel des betreffenden Blocks war. Sobald der Block vom Netzwerk als gültig akzeptiert wird, gibt es keine Möglichkeit, eine Transaktion darin zu ändern (und somit die Hashes der höheren Ebene im Baum zu ändern). Wenn Sie irgendetwas ändern, würde sich die Merkle-Root und damit der Hash des Blocks ändern, sodass das Netzwerk diesen Block nicht mehr als gültig akzeptieren würde.

C. Behält Bitcoin die Merkle-Baum-Hashes nicht nur für die Blattknoten, sondern für den gesamten Baum bis zur Wurzel bei? Wo genau und wie genau werden diese Informationen gespeichert?

Jeder Block enthält die Merkle-Wurzel sowie alle Transaktionsdaten. Die Hashes der Blatt-/Zwischenebene sind nicht explizit enthalten, stattdessen können sie von Knoten berechnet werden, um die Transaktionsdaten des Blocks zu verifizieren und zu validieren. ( Es gibt einige andere Datenbits, die in einem Block enthalten sind , aber es sind die Merkle-Stamm- und Transaktionsdaten, die für Ihre Frage relevant sind.)

Sie könnten daran interessiert sein, die Top-Antworten auf diese Frage zu lesen , sie sind großartige Erklärungen für die Funktion der Merkle-Wurzel.

Beginnen wir damit, die Tatsache zu verstehen, dass BlockChain (das Hauptbuch von Bitcoin) auf mehrere Knoten verteilt ist. Knoten können sich also nicht gegenseitig vertrauen, da sie nicht von einer vertrauenswürdigen Partei verwaltet werden. Immer wenn ein dünner Knoten (Nicht-Miner) P einen vollständigen Knoten (Miner) Q auffordert, das Vorhandensein eines txn t in einem Block B zu verifizieren, muss der vollständige Knoten Q den Knoten P davon überzeugen, dass er (Q) die Wahrheit sagt. Merkle-Bäume kommen hier ins Spiel.

Der dünne Knoten P hat also den Root-Hash von Block B und den Hash von txn t. Das Einzige, was der Full Node den Thin Node nicht fälschlicherweise vom Block B überzeugen kann, ist sein Root-Hash. Als Beweis für "der vollständige Knoten sagt die Wahrheit über das Vorhandensein von txn t in Block B" sendet er auch die Hash-Werte der Geschwisterknoten der Knoten im Pfad von der Wurzel zum txn t im Merkle-Baum. Der Thin-Knoten verfolgt dann die Hash-Werte entlang des Pfads von txn t zur Wurzel des Merkle-Baums zurück, wobei er die vom vollständigen Knoten gesendeten Hash-Werte der Geschwister verwendet. Wenn der resultierende Root-Hash gleich dem im Header von Block B ist, sagt der vollständige Knoten die Wahrheit.

Angenommen, ich bin ein vollständiger Knoten und möchte einen dünnen Knoten fälschlicherweise davon überzeugen, dass sich ein txn t in Block B befindet. Ich kann einfach sagen, dass ich alle Hashes des Blattes überprüft und einen Hash von txn t in der Liste gefunden habe. Aber wer kann sagen, ob ich lüge. Jetzt fordert mich der Blattknoten möglicherweise auf, die Liste der txns zu senden, um die Liste selbst zu überprüfen, aber ich kann die txn t jederzeit zur Liste hinzufügen und die geänderte Liste senden.

Wenn mich nun der dünne Knoten auffordert, den Hash-Wert des übergeordneten Knotens des txn t bereitzustellen, damit er sich selbst verifizieren kann, indem er die Geschwister von txn t und t zusammen hasht und das Ergebnis mit dem Hash des übergeordneten Knotens vergleicht, den ich gerade gesendet habe. Jetzt kann ich einfach einen falschen Hashwert des Elternteils senden, um den dünnen Knoten in die Irre zu führen. Der Thin Node muss also überprüfen, ob dieser Eltern-Hash tatsächlich der tatsächliche Hash im Merkle-Baum ist. Dieser Überprüfungsprozess ist rekursiv, bis ich einen Punkt erreiche, an dem der Elternknoten der Wurzelknoten ist. Diesmal hat der Thin Node den Hash des Parent Nodes und kann sich selbst verifizieren. Wann immer also der dünne Knoten den Root-Hash zu dem im Header des Blocks zurückverfolgen kann, ist der vollständige Knoten nicht lügend/fehlleitend. All dies ist nun aufgrund der Einweg-/nicht invertierbaren Natur der verwendeten Hash-Funktionen möglich.

Eine der vorherigen Antworten beantwortet direkt Ihre Frage zur Effizienz. Es ist sicherlich nicht notwendig, jeden Hash zu kommunizieren oder zu speichern.

Eine große Effizienz bei der Verwendung eines Merkle-Baums ist:

https://en.bitcoin.it/wiki/Block_hashing_algorithm
Der Körper des Blocks enthält die Transaktionen. Diese werden nur indirekt über die Merkle-Wurzel gehasht. Da Transaktionen nicht direkt gehasht werden, erfordert das Hashing eines Blocks mit 1 Transaktion genau den gleichen Aufwand wie das Hashing eines Blocks mit 10.000 Transaktionen.