Glossar / Protokoll und Upgrades
Stapelverifizierung
- Was ist die Stapelverifizierung?
- Die Stapelverifizierung prüft viele Schnorr-Signaturen in einer einzigen Gleichung auf einer elliptischen Kurve statt eine nach der anderen und liefert ein einziges Bestanden oder Nichtbestanden für den gesamten Satz.
Spezifiziert im BIP-340.
Ein Verifizierer bündelt u Signaturen, gewichtet alle bis auf die erste mit einem zufälligen Skalar und löst das Bündel in einer Gleichung statt in u Gleichungen. BIP-340 wurde dafür gebaut und legt Signaturen auf 64 Bytes fest, während das standardisierte ECDSA überhaupt nicht gebündelt werden kann, sofern nicht zusätzliche Witness-Daten hinzugefügt werden. Das Bündeln ist die Wahl jedes einzelnen Verifizierers, es ändert also, wie schnell ein Node die Historie prüft, und nichts an Ihren Bitcoin.
So funktioniert es
Die Stapelverifizierung ist in BIP-340 als BatchVerify spezifiziert, nimmt u öffentliche Schlüssel von 32 Bytes, u Nachrichten und u Signaturen von 64 Bytes und antwortet ein einziges Mal für alle zusammen.
Zuerst kommen die Gewichte. Der Verifizierer erzeugt u-1 ganze Zahlen im Bereich von 1 bis n-1, wobei n die Ordnung der Kurve ist, deterministisch aus einem Generator, der mit einem Hash aller Eingaben des Stapels gespeist wird: Schlüssel, Nachrichten und Signaturen gleichermaßen. BIP-340 bezeichnet SHA256 als sicheren Seed-Hash und ChaCha20 als sicheren Weg, ihn zu 256-Bit-Ganzzahlen zu strecken, wobei alle übersprungen werden, die außerhalb des Bereichs liegen.
Der Stapel fällt dann zu einer einzigen Prüfung zusammen: Die gewichtete Summe der s-Werte, multipliziert mit dem Generatorpunkt, muss derselben Gewichtung entsprechen, angewandt auf die R-Punkte und auf die Challenge jeder Signatur mal ihrem eigenen öffentlichen Schlüssel. Diese u getrennten Prüfungen werden zu einem einzigen Vergleich, dem BIP-340 erhebliche Geschwindigkeitsgewinne zuschreibt.
Diesen Gewinn erkauft man mit Kosten pro Signatur. BatchVerify hebt jeden r-Wert zurück auf die Kurve, was die Einzelverifizierung nie tut: Verify berechnet R aus s und der Challenge neu und prüft dann nur, ob dessen x-Koordinate gleich r ist.
Die Garantie ist bewusst asymmetrisch. Sind alle Signaturen im Stapel gültig, gelingt BatchVerify immer; ist auch nur eine ungültig, gelingt es höchstens mit vernachlässigbarer Wahrscheinlichkeit. Was es nicht tut, ist den Übeltäter benennen, ein Verifizierer, der wissen muss, welche Signatur herausfiel, prüft sie also eine nach der anderen.
Wo Sie es sehen
Die Stapelverifizierung liegt vollständig auf der Seite des Verifizierers im Netzwerk, deshalb taucht sie nie in einer Wallet-Oberfläche oder in einer Gebührenschätzung auf.
Wo sie sich lohnt, ist ein Node, der Jahre von Taproot-Ausgaben auf einmal durcharbeitet, nicht eine Wallet, die eine Zahlung sendet. BIP-340 schreibt das Bündeln nirgends vor: Die Verifizierung einer einzelnen Signatur ist die Definition, und ein Stapel ist etwas, das ein Verifizierer wählen darf. Das BIP verlangt einen auf Byte-Ebene spezifizierten Algorithmus, genau die Exaktheit, die der DER-Analyse bis BIP-66 fehlte, damit niemand eine Signatur bauen kann, die für manche Verifizierer gültig ist und für andere nicht. Weil der Verifizierer seine eigenen Stapel wählt, ist es diese Eigenschaft, die Stapel- und Einzelverifizierung dazu bringt, sich nur mit vernachlässigbarer Wahrscheinlichkeit zu unterscheiden, selbst gegenüber einem Angreifer, der sie zum Auseinanderlaufen bringen will.
Das Bündeln erklärt auch Entscheidungen innerhalb von BIP-340, die allein betrachtet willkürlich wirken. Signaturen hätten eine kürzere Form annehmen können, eine, bei der ein Hash von 16 Bytes für das Sicherheitsziel von 128 Bit genügt, und das BIP lehnte sie ab: Kurze Hashes sind fragil, wenn misstrauische Unterzeichner zusammenarbeiten, und die längere Form, die R trägt, ist die, welche das Bündeln unterstützt. Öffentliche Schlüssel sind 32 Bytes statt der sonst bei Bitcoin üblichen komprimierten Kodierung von 33 Bytes, gewählt wegen der Kompaktheit, und die y-Koordinate, die dabei entfällt, ist auf die gerade festgelegt statt mehrdeutig gelassen, weil effiziente Verifizierung und Bündelung sie beide eindeutig brauchen.
ECDSA bekommt nichts davon. BIP-340 nennt das als einen Grund, das Signaturverfahren zu wechseln: Die standardisierte Formulierung kann im Stapel nicht effizienter verifiziert werden als einzeln, sofern nicht zusätzliche Witness-Daten hinzugefügt werden.
Stapelverifizierung vs. MuSig2
Stapelverifizierung und MuSig2 machen beide einen Haufen Signaturen billiger, aber nur MuSig2 ändert, was übertragen wird.
MuSig2 fasst mehrere Unterzeichner zu einem Schlüssel und einer gewöhnlichen Signatur von 64 Bytes zusammen, bevor die Transaktion das Netzwerk erreicht, sein Gewinn liegt also bei Privatsphäre und Blockplatz, und es ist n-von-n: Jeder Unterzeichner muss mitmachen. Die Stapelverifizierung lässt jede Signatur, wo sie war, und ordnet nur die Arithmetik neu, die ein Validator ausführt, ohne die Mitwirkung oder auch nur das Wissen von irgendjemandem: Ein Node kann Signaturen bündeln, die Fremde Jahre auseinander in nicht zusammenhängenden Transaktionen erstellt haben.