Bitcoin begreifen

Lisa beginnt, indem sie eine Blockschablone erstellt, einen Block ohne Signatur (Abbildung 5).

Sie sammelt mehrere Transaktionen, die sie dem Block hinzufügen will. Dann erzeugt sie den Block Header. Sie erzeugt die Vorgänger-Block ID, indem sie den Block Header des Vorgängerblocks hasht und das Ergebnis in den neuen Block Header schreibt. Der Merkle Root wird anhand der Transaktionen in der Blockschablone ermittelt und die Zeit wird auf die aktuelle Zeit gesetzt.

Die erste Transaktion in ihrem Block ist die Coinbase Transaktion. Solche Coinbase Transaktionen erzeugen 50 CT pro Block anstatt 7.200 CT, wie es in [ch05] der Fall war. Die Idee ist die, dass Lisa alle 10 Minuten einen neuen Block erzeugt, was bedeutet, dass ihre Tagesvergütung über 144 Blocks verteilt wird: es gibt 144 in 24 Stunden, und 144*50 CT = 7.200 CT. Wir sprechen mehr über Blockvergütungen und die Coinbase in [ch07].

Bevor Lisa mit dem Block fertig ist, muss sie ihn erst noch mit einem private Key signieren, den nur sie kennt, wie in Abbildung 6 dargestellt.

Lisa verwendet ihren Blocksignierer private Key, um den Block Header zu signieren. Die digitale Signatur legt sich fest auf

Würde sich irgendetwas in der Blockchain vor dem neuen Block oder in den Transaktionen innerhalb dieses Blockes ändern, so müsste sich auch der Inhalt dieses Block Headers ändern; dadurch würde die Signatur ungültig.

Der public Key, der zu Lisas Blocksignierer private Key gehört, muss allen öffentlich zugänglich sein. Die Firma kann den public Key auf ihrem Intranet veröffentlichen und an das schwarze Brett am Eingang hängen. Die Signatur wird benötigt, weil (zur Zeit) nur Lisa neue Blocks an die Blockchain hängen darf. Zum Beispiel kann John einen neuen Block erzeugen und in den Share legen. Aber er wird ihn nicht korrekt signieren können, da er nicht über Lisas private Key verfügt, also wird niemand sonst Johns Block akzeptieren.

Die Benutzung von private Keys zum Signieren von Blocks könnte sich aus zwei Gründen als schlechte Idee entpuppen:

Die Art, wie Blocks signiert werden, wird sich in [ch07] ändern, von digitalen Signaturen auf Proof of Work.

Ist der Block einmal signiert, muss Lisa ihn den Prüfern zugänglich machen. Sie benutzt den Share dafür, indem sie eine neue Datei erzeugt, block_20.dat, in die sie ihren neuen Block speichern will (Abbildung 7).

Der Block ist jetzt veröffentlicht. Jeder, der Interesse hat, kann den Block aus dem Share lesen. Denk daran, dass keiner die Datei ändern oder löschen kann, weil die restriktive Rechtevergabe auf dem Share dies nicht zulässt. Nicht einmal Lisa selbst kann das. Es gibt aber einen Systemadministrator, der volle Rechte dazu hat und alles mit dem Share anstellen kann. Wir werden in [ch08] den Systemadministrator loswerden, wenn wir das Peer-to-Peer Netzwerk einführen.

Wenn Lisa ihren Block zusammenbaut, sucht sie sich die Transaktionen aus, die sie darin einbetten will. Sie kann sich alles aussuchen, von null Transaktionen bis alle unbestätigten Transaktionen. Die Reihenfolge der Transaktionen ist nicht wichtig, solange alle Transaktionen nur Output ausgeben, die entweder in der Blockchain davor oder früher innerhalb dieses Blocks vorkommen. Zum Beispiel ist der Block in Abbildung 8 völlig in Ordnung.

Alle Transaktionen in diesem Block geben Transaktionen aus, die schon in der Blockchain sind, was bedeutet, sie nehmen alle nur Bezug auf Transaktionen links von sich. Aber der Block in Abbildung 9 ist ungültig.

Er ist ungültig, weil eine Transaktion einen Output ausgibt, der nach–rechts von der ausgebenden Transaktion–platziert ist.

Um zu vernebeln, welche Adressen zusammengehören, erzeugt Johns Wallet einen Bloom Filter, den es dem Full Node schickt (Abbildung 16).

Der Bloom Filter ist eine Reihe von Bits, die, wie in [ch02] erwähnt, einen Wert von 0 oder 1 haben können. Johns Bloom Filter ist 8 Bit lang. [fig0617] stellt dar, wie er erzeugt wurde.

Das Wallet erzeugt die Reihe von Bits (den Bloom Filter) und initialisiert sie vollständig mit Nullen. Dann addiert sie die public Key Hashes (PKH) von allen Adressen von John zum Bloom Filter, beginnend mit PKH_a, dem PKH von @_a.

Es schickt PKH_a durch die erste der drei Hashfunktionen. Diese Hashfunktion liefert als Ergebnis den Wert 2. Dieser Wert ist der Index in den Bloom Filter. Das Bit an Index 2 (das dritte von links) wird dann auf 1 gesetzt. Dann wird PKH_a durch die zweite Hashfunktion geschickt, die 0 als Resultat liefert, und das korrespondierende Bit (in der Abbildung das erste von links) wird auf 1 gesetzt. Schliesslich liefert die dritte Hashfunktion den Wert 6, und das Bit an Index 6 (das siebte von links) wird auf 1 gesetzt.

Als nächstes kommt der PKH_b an die Reihe, mit dem auf die genau gleiche Weise verfahren wird. Die drei Hashfunktionen liefern als Outputs 5, 0 und 3. Diese drei Bits werden alle auf 1 gesetzt. Wohlgemerkt war Bit 0 bereits durch PKH_a gesetzt, sodass dieses Bit hier nicht mehr geändert wird.

Der Bloom Filter ist fertig und kann an den Full Node geschickt werden.

Der Full Node empfängt den Bloom Filter vom Wallet und möchte ihn benutzen, um die Transaktionen herauszufiltern, die er an das Wallet schicken soll.

Angenommen, Lisa hat gerade einen neuen Block im Share veröffentlicht und der Full Node hat den Block verifiziert. Der Full Node will jetzt den neuen Block Header und alle darin enthaltenen relevanten Transaktionen an das Wallet schicken. Wie benutzt der Full Node den Bloom Filter, um herauszufinden, welche Transaktionen er schicken soll?

Der Block enthält drei Transaktionen: Tx₁, Tx₂, and Tx₃ (Abbildung 17).

Tx₁ und Tx₃ haben nichts mit Johns Adressen zu tun, aber Tx₂ zahlt an Johns Adresse @_b. Schauen wir uns an, wie der Full Node den Bloom Filter benutzt (Abbildung 18).

Für jeden Output in einer Transaktion prüft der Node, ob irgendein PKH zu dem Filter passt. Er beginnt mit Tx₁, die einen einzelnen Output an PKH_L enthält. Um zu prüfen, ob PKH_L durch den Filter passt, schickt er PKH_L durch dieselben drei Hashfunktionen, die Johns Wallet beim Erzeugen des Filters benutzt hat. Die Hashfunktionen liefern die Indizes 5, 1 und 0. Die Bits an Index 5 und 0 sind beide 1, doch das Bit an Index 1 ist 0. Ein 0 Bit bedeutet, PKH_L interessiert Johns Wallet definitiv nicht. Wenn Johns Wallet Interesse am PKH_L hätte, hätte das Wallet ihn zu dem Filter hinzugenommen und damit Bit 1 auf 1 gesetzt. Weil PKH_L der einzige PKH in Tx₁ ist, ist Johns Wallet folglich nicht an dieser Transaktion interessiert.

Die nächste Transaktion ist Tx₂. Sie enthält zwei PKHs: PKH_b und PKH_X. Es beginnt mit PKH_b. Der Durchlauf durch die drei Hashfunktionen liefert die Indizes 5, 0 und 3. Alle drei Bits haben den Wert 1. Das heisst, der Code kann nicht sicher sagen, dass die Transaktion das Wallet wirklich interessiert, aber er kann auch nicht mit Sicherheit sagen, dass sie es nicht interessiert. Weitere PKHs in der Transaktion zu überprüfen ist sinnlos, weil der Node bereits beschlossen hat, dass Tx₂ an das Wallet geschickt werden sollte.

Die letzte Transaktion hat zwei Outputs an PKH_Y und PKH_Z. Es beginnt mit PKH_Y, was auf 2, 7 und 4 zeigt. Sowohl Bits 4 als auch 7 sind 0, was bedeutet, PKH_Y ist für das Wallet definitiv nicht von Interesse. Machen wir mit PKH_Z weiter, was als Resultat Bits 2, 3 und 0 liefert. Alle drei Bits haben den Wert 1. Das wiederum bedeutet, dass Tx₃ für das Wallet vielleicht von Interesse sein könnte, also schickt der Node auch diese Transaktion. Johns Wallet enthält PKH_Z zwar nicht, aber der Bloom Filter versucht, mehr zu finden als nötig um einen gewissen Grad an Privacy zu erreichen. Wir nennen dies einen false positive Treffer oder Scheintreffer.

Das Ergebnis der Bloom Filterung ist, dass der Node die Transaktionen Tx₂ und Tx₃ an das Wallet schicken wird. Wie die Transaktionen geschickt werden, ist eine völlig andere Geschichte, die in Abschnitt 6.5 beschrieben wird.

Die obige Beschreibung ist eine Vereinfachung dessen, was tatsächlich passiert. Wir haben nur die PKHs der beschriebenen Transaktions Outputs getestet, was alle Transaktionen erwischen würde, die Cookie Token an irgendwelche von Johns Adressen zahlen. Aber was ist mit den Transaktionen, die Geld von Johns Adressen ausgeben? Wir könnten zwar sagen, dass der Full Node dies Transaktionen nicht an das Wallet zu senden braucht, weil es die ja selbst erzeugt hat und sie deshalb sowieso schon kennt. Leider muss man aber diese Transaktionen trotzdem übermitteln, und zwar aus zwei Gründen.

Erstmal kann es sein, dass nicht diese Wallet App die Transaktion erzeugt hat. John kann viele Wallet Apps benutzen, die Adressen aus demselben Seed erzeugen. Erinnere dich zum Beispiel daran, wie in [ch04] ein Wallet aus einem mnemonic sentence wiederhergestellt wurde? Dieser mnemonic sentence kann von vielen Wallets gleichzeitig benutzt werden. John möchte vielleicht von einem der Wallets eine Zahlung tätigen und einem anderen Wallet über die Zahlung auf informiert werden, damit er dort das Gesamtsaldo überschauen kann.

Zweitens möchte John bescheid bekommen, wenn die Zahlung bestätigt wurde. Die Wallet App mag die Transaktion zwar schon haben, aber sie wird in der App noch als unconfirmed angezeigt. John möchte wissen, wann die Transaktion in einen Block Eingang gefunden hat, also muss der Node ihm diese Transaktion schicken, sobald sie in einem Block gelandet ist.

Was der Node tatsächlich testet, sind die folgenden Dinge: (Abbildung 19):

Damit Johns Wallet über Geldausgaben informiert wird, muss es entweder alle seine public Keys oder alle seine UTXO Verweise zum Bloom Filter hinzufügen.

Der Sinn der Bloom Filter ist die Verbesserung der Benutzer-Privacy. Der Level an Privacy kann durch das Verhältnis von 1en im Bloom Filter und durch dessen Grösse justiert werden. Je mehr 1en im Bloom Filter relativ zu seiner Grösse auftauchen, desto mehr Scheintreffer gibt es. Je mehr Scheintreffer, desto mehr unnötige Transaktionen muss der Full Node an das Wallet schicken. Mehr unnötige Transaktion bedeuten mehr verschwendeter Datenverkehr aber auch verbesserte Privacy.

Machen wir ein paar Überschlagsrechnungen. Der Bloom Filter im Beispiel vorhin hat 8 Bit, vom dem fünf 1en sind. Der Output einer einzelnen Hashfunktion hat daher eine 5/8 Wahrscheinlichkeit, eine dieser 1en zu treffen. Für einen einzelnen Test ist also die Wahrscheinlichkeit, dass alle drei Hashfunktionen eine 1 treffen, (5/8)³. Die Wahrscheinlichkeit, dass ein einzelner Test negativ ist–mindestens eine der drei Hashfunktionen zeigt auf eine 0–ist dann 1 – (5/8)³. Der Full Node führt auf jeder Transaktion mehrere Tests aus, typischerweise neun für eine Transaktion mit zwei Inputs und zwei Outputs. Checken wir das gegen die Liste von Tests, die der Full Node abarbeitet:

Die Wahrscheinlichkeit, dass alle neun Tests negativ sind, ist (1 – (5/8)³)⁹ ≈ 0.08. Es werden also fast alle—92/100—Transaktionen an das Wallet gesendet. Das zeigt, dass nur drei 0en in den 8 Bits des Bloom Filter zu haben nicht hilft, die Daten wesentlich zu reduzieren, aber es hilft besser, die Privacy zu schützen.

Um weniger Scheintreffer zu bekommen, muss Johns Wallet einen grösseren Bloom Filter benutzen, damit das Verhältnis (Anzahl Einsen / Grösse des Bloom Filters) sinkt.

Definieren wir ein paar Symbole:

t = Anzahl Tests auf einer Transaktion (9) p = Wahrscheinlichkeit, dass eine Transaktion für uninteressant gehalten wird. r = Verhältnis der Anzahl 1en / Grösse des Bloom Filters

Wir können unsere Berechnung wie folgt verallgemeinern:

Sagen wir, du willst 1/10 aller Transaktionen bekommen (unter der Annahme, dass alle Transaktionen wie die vorige Transaktion aus zwei Inputs und zwei Outputs bestehen). Wie gross musst du den Bloom Filter machen?

Diese Berechnung liefert, dass der Bloom Filter etwa 6/0.23 ≈ 26 sein sollte, um nur 1/10 aller Transaktionen zu bekommen. Der Bloom Filter muss aber ein Vielfaches von 8 Bit sein, also ist 26 nicht erlaubt. Wir können auf 32 Bit aufrunden.

Denk daran, dass diese groben Berechnungen ein wenig auf falschen Annahmen beruhen, was die Transaktions-Merkmale betrifft. Wir berücksichtigen auch nicht, das die Anzahl 1en im Beispiel nicht genau sechs ist, sondern alles zwischen drei und sechs sein kann, angesichts der Tatsache, dass Johns Adressen auch den selben Satz an Indizes für beide Adressen hätten generieren können. Aber dieser Vorgang sollte dir helfen, eine Idee davon zu bekommen, wie gross ein Bloom Filter sein muss.

Bloom Filter werden schon lange bei vielen Lightweight Wallets benutzt, aber sie haben Probleme:

Neue Bitcoin Improvement Proposals (BIPs), BIP157 und BIP158 sind zur Lösung vorgeschlagen worden, aber noch sind sie weder sehr verbreitet noch gut getestet. Die Idee dabei ist, den Vorgang so umzukehren, dass ein Full Node für jeden Block einen Filter zum Lightweight Wallet schickt. Dieser Filter enthält Informationen darüber, welche Adressen der Block betrifft. Das Lightweight Wallet prüft, ob seine Adressen auf den Filter passen und wenn ja, lädt er den ganzen Block. Der Block kann dabei von überall geladen werden, nicht nur von dem Full Node, der den Filter gesendet hat.

Der partielle Merkle Tree ist eine gestutzte Version des vollen Merkle Trees, die nur jene Teile enthält, welche zu dem Beweis nötig sind, dass Tx₂ zu dem Baum gehört. Der Full Node sendet dreierlei an das Wallet:

Konstruieren wir den partiellen Merkle Tree. Der Full Node kennt die Anzahl Transaktionen im Block, also kennt er die Form des Merkle Trees. Um den partiellen Merkle Tree zu konstruieren inspiziert der Full Node die Hashes im Merkle Tree, beginnend am Merkle Root und in einer Abwärtsbewegung den Baum hinab, linker Ast zuerst (Abbildung 26).

Der partielle Merkle Tree besteht aus

Bei jedem Schritt macht man zweierlei mit dem aktuellen Hash, wie in der folgenden Tabelle dargestellt:

Dieser Sortierschritt heisst depth-first, oder erst abwärts, was bedeutet, dass man im Baum erstmal so weit herunter geht wie möglich, bevor man sich seitwärts bewegt. Aber du gehst nicht in Zweige herunter, in denen sich keine interessanten Transaktionen befinden. Das wird in der Liste der Flags als ✘ markiert. Du hörst bei ✘ auf, weil du keine unnötigen Daten an das Wallet schicken willst, daher der Begriff partieller Merkle Tree.

Jetzt, wo der Full Node den partiellen Merkle Tree konstruiert hat, schickt der Node den Block Header und den partiellen Merkle Tree an das Wallet und schickt dann die eigentliche Transaktion Tx₂. Die Block Header zusammen mit dem partiellen Merkle Tree werden oft als Merkle Proof bezeichnet.

Das Wallet hat einen Block Header, einen partiellen Merkle Tree und die Transaktion Tx₂ vom Full Node erhalten. Das ist alles, was das Wallet benötigt, um zu verifizieren, dass Tx₂ sich tatsächlich im Block befindet. Das Ziel ist, zu verifizieren, dass es einen Weg gibt, Tx₂ mit dem Merkle Root des Block Headers zu “verbinden”. Es beginnt damit, den partiellen Merkle Tree zu verifizieren (Abbildung 27).

Benutze die Anzahl Transaktionen (drei), die vom Full Node empfangen wurden, um die Merkle Tree Struktur aufzubauen. Das Wallet weiss, wie ein Merkle Tree mit drei Transaktionen aussieht.

Benutze die Liste der Flags und Hashes, um Hashes an den Merkle Tree zu heften, in depth-first Reihenfolge, wie folgt.

Das Wallet hat jetzt genügend Hashes (3, 4 und 5) an den Merkle Tree gehängt, um die Leerstellen auf dem Weg nach oben im partiellen Merkle Tree auszufüllen. Zuerst wird den Hash von Schritt 2 aus 3 und 4 berechnet, und dann der Root aus 2 und 5.

Vergleiche den berechneten Merkle Root mit dem Merkle Root im Block Header–dem tatsächlichen Merkle Root–und überprüfe, dass beide identisch sind. Prüfe auch, dass der Hash von Tx₂ in der Liste von Hashes ist, die vom Full Node empfangen wurden (Abbildung 28).

Wenn die Transaktion zu einem der Hashes im partiellen Merkle Tree passt, und der partielle Merkle Tree Root zum Merkle Root im Block Header passt, dass hat der Full Node bewiesen, dass Tx₂ Teil des Blocks ist.

Aber der Full Node wollte zwei Transaktionen aus diesem Block schicken. Wie würde der Merkle Proof mit zwei Transaktionen aussehen? Schickt man mehrere Merkle Proofs? Nein–wir lassen das als Übung am Ende des Kapitels.

Der Block im vorigen Beispiel hatte nur drei Transaktionen, Man hat nicht viel Platz gespart, indem man den Header, den partiellen Merkle Tree und Tx₂ geschickt hat. Man hätte genausogut alle drei txids schicken können anstatt den partiellen Merkle Tree–das wäre viel einfacher. Aber der Vorteil von Merkle Proofs werden erkennbar, wenn die Anzahl Transaktionen im Block steigt.

Angenommen, der Full Node hat gerade einen Block mit 12 Transaktionen verifiziert. Durch Testen aller Transaktionen gegen den Bloom Filter des Wallets hat er festgestellt, dass zwei der Transaktionen potentiell interessant für das Wallet sind. Abbildung 29 zeigt, wie das aussehen würde.

Der Full Node braucht nur den Block Header, die Zahl 12, 14 Flags und sieben Hashes zu übermitteln. Das summiert sich zu etwa 240 Bytes, viel weniger Daten als den Block Header und alle 12 txids (etwa 464 bytes).

Checken wir mal ein paar grobe Zahlen, um zu sehen, wie der Merkle Proof grössenmässig dasteht im Vergleich zur Grösse des vollen Blocks und dem vereinfachten Ansatz, alle txids zu schicken, bei wachsender Anzahl Transaktionen (Tabelle 1).

Tabelle 1 geht von einer einheitlichen Grösse aller Transaktionen von 250 Bytes aus, und dass man nur eine Transaktion beweisen möchte. Die Blockgrösse wird berechnet als der 80 Byte Block Header plus die Anzahl Transaktionen mal 250. Der einfache Beweis wird berechnet als der 80 Byte Block Header plus die Anzahl Transaktionen mal 32. Der Merkle Proof ergibt sich zu 80 Bytes Block Header plus die Länge der Hashliste mal 32. Ignoriere die Flags und Anzahl Transaktionen, weil diese vernachlässigbar sind.

Die Merkle Proofs wachsen nicht so schnell wie die vereinfachten Beweise, weil Merkle Proofs_logarithmisch_ mit der Anzahl Transaktionen wachsen, einfache Beweise hingegen linear. Wenn sich der Block in der Grösse verdoppelt, vergrössert sich der Merkle Proof ungefähr um einen konstanten Term von 32 Byte, wogegen sich der einfache Beweis in der Grösse verdoppelt.