Schnorr kommt näher

Bild von Michael Hicks via flickr.com. Lizenz: Creative Commons

Die Bitcoin-Entwickler träumen schon lange davon, die ECDSA-Signaturen durch Schnorr-Signaturen zu ersetzen. Ein BIP von Bitcoin-Core-Entwickler Pieter Wuille bringt sie diesem Traum ein Stückchen näher …

Ein Bitcoin Improvement Proposal (BIP) von Pieter Wuille könnte die nach SegWit nächste größere Änderung im Bitcoin-Protokoll einleiten. Dabei geht es darum, mit Schnorr-Signaturen eine Alternative zu den heute verwendeten ECDSA-Signaturen anzubieten. Viele Bitcoin-Entwickler wünschen sich das schon lange, weil die Schnorr-Signaturen einige äußerst attraktive Vorteile haben.

Detail mit großer Wirkung

Um zumindest im Ansatz zu verstehen, weshalb Schnorr-Signaturen so begehrt sind, müssen wir ein klein wenig ausholen. Bitcoin verwendet einen Elliptic Curve Signature Algorithm (ECDSA). Signaturen werden mithilfe der Koordinaten eines zufälligen Punktes auf einer bestimmten elliptischen Kurve gebildet, und um sie zu prüfen, muss man die Rechnung umdrehen und schauen, ob man auf einem passenden Punkt landet. Oder so ähnlich.

Dieses Verfahren benötigt nicht allzu viel Rechenleistung, produziert relativ kompakte Signaturen, und gilt als bewährt, da es sich seit Jahren im Einsatz bewährt. Es ist aber nicht perfekt. Die Nachteile sind vor allem, dass die Prüfung von Signaturen einige rechenintensive Operationen, wie Inversionen und Punktmultiplikationen, beinhaltet, man Signaturen nicht aggregieren kann und Signaturen inhärent mallebel sind, also “umgebogen” werden können (siehe Malleable Transaktionen).

Schnorr-Signaturen lösen diese Probleme. Das Verfahren beruht auf der Arbeit des deutschen Mathematikers Claus-Peter Schnorr, der ein Patent auf sie hielt, das 2008 ausgelaufen ist. Seitdem stehen Schnorr-Signaturen mehr und mehr im Fokus der Wissenschaft, auch wenn sie bis heute noch relativ selten in der Praxis angewandt werden. Die Methode unterscheidet sich nicht so sehr von ECDSA; sie beruht ebenfalls auf zufälligen Punkten auf einer elliptischen Kurve, verwendet diese aber ein wenig anders und ändert die Berechnungsformel ein wenig.

Das Ergebnis dieser Detail-Änderungen ist beeindruckend: Schnorr-Signaturen sind absolut nicht malleabel, können leichter verifiziert werden und sind aggregierbar.

Aggregierte, gebatchte, blinde Signaturen

Für Bitcoin haben Schnorr-Signaturen mehrere Vorteile. Pieter Wuille erklärt in seinem BIP, wofür man sie benutzen kann.

Ein großer Fortschritt wären Schwellen-Signaturen für Multisig-Transaktionen. Multisig meint, dass mehrere Parteien eine Transaktion signieren müssen, damit sie gültig ist. Bisher läuft dies so ab, dass man jede benötigte Signatur in die Transaktion schreiben muss. Wenn also eine Transaktion von sieben Parteien signiert wird, speichert man auch sieben Signaturen in der Blockchain ab. Mit Schnorr kann man ein Multisig so aufbauen, dass verschiedene Teilnehmer zusammen eine einzelne Signatur produzieren. Damit würde sich eine Multig-Transaktion genauso verhalten wie eine normale Transaktion – was unbestreitbar vorteilhaft für die Privatsphäre der User wie auch für die Skalierbarkeit der Blockchain wäre.

Weiter erklärt Wuille, dass mit Schnorr sogenannte “Adopter Signaturen” oder “skriptlose Signaturen” möglich werden. Dabei verweist der Entwickler auf die Präsentation von Andrew Poelstra zu MimbleWimble. Ebenfalls möglich werden könnten Blinde Signaturen, was meint, dass jemand eine Nachricht signiert, ohne ihren Inhalt zu kennen. Dies macht beispielsweise blinde Währungswechsel, Treuhänder, denen man nicht vertrauen muss und viele weitere Konstruktionen möglich, mit denen man die Privatsphäre von Bitcoin-Usern verbessert.

Stepan Snigirev, ein Quantenphysiker, der in die Bitcoin-Entwicklung einsteigt, hat kürzlich einen erhellenden Artikel über Schnorr-Signaturen geschrieben. Dabei erklärt er auch, wie viel Rechenarbeit Schnorr-Signaturen sparen können: Während die Verifizierung von einem Block mit 1000 ECDSA-Signaturen erfordert, dass man 1000 Inversionen und 2000 Punkt-Multiplikationen, insgesamt etwa 3000 schwierige Operationen, berechnet, sind mit Schnorr lediglich sehr einfache Punktadditionjen und 1001 Punkt-Multiplikationen notwendig. Die Computer sparen sich insgesamt also rund ein Drittel an Arbeit. Hardware-Wallets oder “kleine” Nodes werden hierfür dankbar sein.

Es gibt auch noch die Idee, um mit Schnorr die Signaturen einer Transaktion zu aggregieren. Bisher braucht eine Transaktion je Input eine Signatur, was bei Transaktionen, die aus vielen “Münzen” (Inputs) bestehen, eine Menge an Blockchain-Speicher und Rechenleistung benötigt. Mit Schnorr wäre es wohl auch möglich, diese Signaturen zu einer Signatur zusammenzufassen (“batching”), was eine große Menge an Speicher sparen und ein massiver Schritt zu einer höheren Kapazität sein würde. Dies ist eines der spannendsten Features von Schnorr.

Vorerst nur ein Standard und noch keine Integration

Bei der Ankündigung des BIPs in der Mailing-Liste der Entwickler versucht Pieter Wuille, allzu hohe Erwartungen zu dämpfen. “Es ist einfach nur ein Entwurf einer Spezifizierung des Signatur-Verfahrens selbst. Es berührt keine Konsens-Regeln, Aggregierung oder irgendeine andere Integration in Bitcoin.” Wuille versucht lediglich, einen Standard des Signaturverfahrens zu etablieren, was ein erster Schritt für die Integration in Bitcoin selbst ist.

Die Inhalte des Vorschlags sind daher auch noch weit von der Anwendung entfernt und dürften für Nicht-Kryptographen relativ trocken und langweilig sein. Denn Schnorr ist weniger ein konkreter Algorithmus, als ein Bündel von Methoden. Es gibt verschiedene Varianten, das Verfahren einzusetzen, und nicht jede ist für jeden Zweck gleich gut geeignet. Wuille versucht daher, die Varianten zu finden, die für Bitcoin am besten geeignet sind. Dabei versucht er, künftige Anwendungen – etwa das “Batching” von Signaturen, die Implementierung geplanter Skriptbefehle – vorwegzunehmen und zwischen verschiedenen Tradeoffs (etwa zwischen Effizienz und Kompaktheit) die richtige Entscheidung zu treffen.

Wenn sich die technische Community auf einen solchen Standard einigt, erklärt Wuille Coindesk, kann man damit beginnen, an der Integration zu arbeiten. Diese wird dann vermutlich eine Änderung der Konsens-Regeln per Softfork beinhalten, welche Schnorr mehr oder weniger in SegWit integriert. Noch weiter wird der Weg dahin sein, Schnorr in die Wallets zu bringen und Signaturen zu batchen. Diesen Teil von Schnorr, der vielleicht am aufregendsten ist, will Wuille bewusst weiter nach hinten verzögern, weil es noch so viele spannende Ideen gibt, die Skripte von Bitcoin zu verbessern – etwa MAST, Taproot und mehr – welche alle die konkrete Implementierung des Batchings berühren.

Stepan Snigirev wendet noch ein, dass auch die Bildung von Multisig-Adressen mit den Schwellensignaturen von Schnorr mit einem Nachteil daher kommt. So gibt es zum einen einige Angriffe, die zwar verhindert werden können, was aber die Angelegenheit etwas verkompliziert. Zum anderen erfordern die Schwellensignaturen, dass sich alle Beteiligten bei der Zeichnung der Transaktion nicht nur einmal absprechen, wie bisher, sondern zweimal. Dies wäre vom Standpunkt der User-Experience ein ziemlich großer Rückschritt.

Allerdings schmälert dies nicht die vielen Vorteile, die Schnorr mit sich bringt. Es ist ein Baustein für zahlreiche weitere Verbesserungen von Bitcoin, die bisher noch nicht einmal vollständig erahnt werden können. Insbesondere für die Privatsphäre der User könnten Anwendungen auf Basis von Schnorr-Signaturen einen großen Beitrag leisten. Pieter Wuilles BIP stellt nun einen wichtigen Schritt hin, um diesen Baustein Wirklichkeit werden zu lassen.

About Christoph Bergmann (1309 Articles)
Das Bitcoinblog wird von Bitcoin.de gesponsort, ist inhaltlich aber unabhängig und gibt die Meinung des Redakteurs Christoph Bergmann wieder, es es seit Mitte 2013 führt. Christoph hat vor kurzem ein Buch geschrieben: Bitcoin: Die verrückte Geschichte vom Aufstieg eines neuen Geldes. Das Buch stellt Bitcoin in seiner ganzen Pracht dar. Ihr könnt es direkt auf der Webseite Bitcoin-Buch.org bestellen - natürlich auch mit Bitcoin - oder auch per Amazon. Natürlich freuen wir uns auch über Spenden in Bitcoin oder Bitcoin Cash an die folgende Adresse: 1BvayiASVCmGmg4WUJmyRHoNevWWo5snqC. Weitere Adressen (bech32, SegWit, Litecoin, Ethereum) finden Sie HIER. Tipps für Stories sind an christoph.bergmann@mailbox.org immer erwünscht. Wer dies privat machen möchte, sollte meinen PGP-Schlüssel verwenden.

10 Comments on Schnorr kommt näher

  1. Bin zwar aktuell im Urlaub, aber dennoch ein kurzer Kommentar:
    Das Cryptonote Protokoll hat Schnorr Signaturen seit Anfang an (2014) vorgesehen und bereits in der Referenzimplementierung integriert. Um dies für Ring Signaturen noch zu optimieren, nutzt Monero das Borromean Verfahren.

    Btw. Bulletproof Audits bei Monero wurden bereits von zwei der drei externen Dienstleister fertiggestellt und es wurden bisher keine gravierenden Schwächen gefunden. Höchstwahrscheinlich werden diese also im September/Oktober Netzwerk-Upgrade (Hardfork) live gehen und Monero Transaktionen um 85-90% schrumpfen lassen.

    Eine Dynamik, die ich von Bitcoin als ältestes und “stabilstes” Projekt nicht erwarte, aber über 6 Jahre lang darüber zu diskutieren, bis ein BIP kommt, welches vielleicht irgendwann mal umgesetzt wird (oder auch nicht), wäre selbst für Debian Verhältnisse äußerst träge. Nicht zuletzt schafft diese Trägheit viel Raum für die ganzen Scams, die alle möglichen Ideen, die für Bitcoin diskutiert wurden, aufgreifen können und als eigene vermeintliche “Vorteile” vermarkten können, auch wenn sie diese noch nichtmal selbst verstehen.

  2. Paul janowitz, ich folge schon lange deinen bereichernden Kommentaren hier im Blog, kann dich aber nicht zuordnen.. wer bist du eigentlich??;) Danke und Gruß

    • Freut mich, dass Du meine Kommentare bereichernd findest, danke für das Lob!

      Ich bin irgendwann 2012 auf Bitcoin aufmerksam geworden, nachdem mir ein Paypal Business Account zum zweiten Mal gekillt wurde, obwohl beide Male zuvor eine Prüfung des gesamten Business Modells durch PayPal erfolgt ist und genehmigt wurde. Das erste Mal war irgendwann 2005 oder 2006, als PayPal gemerkt hat, dass der Absinth, den ich vertrieben habe, in den USA illegal ist, in Europa dagegen komplett legal. Erst nach anwaltlicher Intervention haben wir einen 5-stelligen Betrag von PayPal zurückerstattet bekommen, dafür wurden wohl aus Rache allen Beteiligten (Gesellschafter, Geschäftsführer und alle, die auszumachen waren) selbst die privaten PayPal Accounts gekündigt. Damals konnte man lediglich auf E-Gold, Liberty Reserve, Perfect Money, Webmoney, OKPay oder ähnliche zentralisierte Dienste mit noch dubioseren Geschäftspraktiken als PP zurückgreifen und letztendlich mussten wir für deutsche Kunden Lastschriften implementieren, die ewig zurückbuchbar sind, auch wenn die Ware lange den Kunden erreicht hat.

      Das zweite Mal, als mir PayPal meinen Account gesperrt hat (neue Firma), war 2012, als ich gehostete ownCloud Instanzen vermietet habe und PayPal Admin-Zugriff auf alle User Files haben wollte, was ich natürlich datenschutzrechtlich und auch moralisch nicht vertreten konnte. Darauf wurde mir mein PP Account nicht wieder entsperrt und erneut das gleiche Spiel mit Anwalt. Allerdings gab es damals bereits eine dezentrale Alternative namens Bitcoin. Leider habe ich diesen Service letztendlich trotzdem schließen müssen, da Bitcoin damals für den normalen User nicht nutzbar war und meine Einbußen >90% im Vergleich zu PayPal lagen. Allerdings hat mich Bitcoin damals angesteckt und ich habe die Entwicklung stets mitverfolgt, wobei ich (fast) alle Projekte die damals aufkamen (Litecoin oder selbst Ethereum) für nicht sinnvoll erachtet habe, da die meisten keinerlei eigene Innovation eingebracht haben.

      Müde von der nie endenden Blocksize Debatte habe ich Mitte 2016 wieder Research betrieben, was sich in der Altcoin Szene getan hat und die meisten Projekte konnte ich direkt verwerfen wie ein paar Jahre zuvor, aber Monero hat es mir angetan und ich habe einen Haken gesucht… Bis heute übrigens! Bitcoin ist leider träge geworden und die Blocksize Debatte hätte in meinen Augen maximal 1 Jahr beanspruchen dürfen, denn es gibt viel gravierendere Probleme wie mangelnde Privatsphäre, die man längst hätte angehen sollen. Neue Technologien müssen agil bleiben, um zu überleben. Gelegentlich muss man leider auch alte Zöpfe abschneiden, um Raum für neue Entwicklungen zu schaffen…

      Mittlerweile versuche ich mich in der Monero Community einzubringen, wenn es meine Zeit zulässt, bin gelegentlich Speaker auf Konferenzen und biete auch Consulting für Unternehmen, die an Blockchains oder Cryptowährungen interessiert sind.

      Falls Du mich suchen solltest, wirst Du auf den gängigen Medien wie Twitter, Linkedin oder ähnlichen sicher fündig 😉

  3. Kartoffelkopf // 23. July 2018 at 8:25 // Reply

    Sind Schnorr-Signaturen quantencomputersicher? Wenn nicht, dann sollten die Entwickler sich mehr Zeit nehmen. Denn wenn Schnorr-Signaturen einen Hardfork benötigen, so sollte man diesen erst durchführen wenn auch quantencomputersichere Kryptographie in das Protokoll übernommen wird.

    • Schnorr Signaturen sind nicht “quanten-sicher” aber die Implementierung benötigt auch “nur” eine Soft-Fork ähnlich SegWit (und baut sogar darauf auf). Allerdings halte ich Quantensicherheit ähnlich wie Pieter Wuille derzeit für relativ irrelevant bei Bitcoin, da man noch nicht einmal abschätzen kann, ob diese mit einer relevanten Anzahl an QBits jemals erscheinen werden.

      Sollte Kryptographie auf Ellyptischen Kurven gebrochen sein, gibt es zudem größere Probleme als die paar Cryptocoinverrückte. IOTA “löst” mit ihrem QC-“sicheren” Algo ein nicht existentes Problem und schafft diverse neue… Unsere gesamte (Banken-)Infrastruktur basiert auf ECC, von Bankkarten über Online Banking bis hin zu Reisepässen. Quantencomputer würden diese Algorithmen und die damit verschlüsselten Daten auch nicht auf einen Schlag brechen nur womöglich den zeitlichen Aufwand dafür deutlich verringern…

      • Sollte Kryptographie auf Ellyptischen Kurven gebrochen sein, gibt es zudem größere Probleme als die paar Cryptocoinverrückte. IOTA „löst“ mit ihrem QC-„sicheren“ Algo ein nicht existentes Problem und schafft diverse neue… Unsere gesamte (Banken-)Infrastruktur basiert auf ECC, von Bankkarten über Online Banking bis hin zu Reisepässen. Quantencomputer würden diese Algorithmen und die damit verschlüsselten Daten auch nicht auf einen Schlag brechen nur womöglich den zeitlichen Aufwand dafür deutlich verringern…

        hehe, hier muss ich noch anbeissen 😉

        “Normale” Internetseiten haben das Glück, dass sie frühzeitig upgraden können. ECC wird ja nicht über Nacht von Quantencomputern gebrochen werden. Im Notfall können Banken eventuell Überweisungen blockieren.

        Bei Kryptowährungen ist das grundsätzlich schwieriger, und selbst wenn es klappt, heikler. Die derzeitigen Kandidaten für quantensichere Signaturen sind ja recht sperrig und skalieren schlecht. Bei manchen Kryptowährungen mit komplexeren Signaturverfahren (RingCT *wink*) könnte es sogar unmöglich sein (oder macht RingCT Monero quantensicher, weil der public key geheim bleibt?).

        Aber ich stimme dir beim ersten Teil zu: Das Problem ist nicht eilig. Es ist noch nicht klar, dass Quantencomputer überhaupt jemals ECC knacken, sogar eher unwahrscheinlich. Und selbst wenn sind Adressen ja nur die Hash des public keys (die verwendeten Hashfunktionen gelten als quantensicher). Wenn man eine Adresse nur einmal verwendet, kann ein Quantenhacker nur einen Double-Spend bis zum nächsten Block versuchen, wenn jemand den public key bei einer Transaktion verrät. Und es ist nochmal ein Riesenunterschied zwischen “Quantencomputer knackt ECC” und “Quantencomputer knackt ECC in weniger als 10 Min.”

        Ethereum steht da eher schlecht da, weil man dort Coins auf Accounts speichert, die man in der Regel wiederverwendet. Monero dürfte recht gut dastehen, weil die Blocktime geringer ist.

  4. Weder die aktuellen Range Proofs bei Monero noch die im September / Oktober kommenden Bulletproofs sind Quanten-Sicher: https://eprint.iacr.org/2017/1066.pdf
    4.6 des Papers erwägt allerdings bereits Quanten-sichere Algorithmen für Bulletproofs falls diese mal benötigt werden sollten, aktuell sind diese allerdings zu wenig getestet und somit potenziell unsicher und haben zu viel Overhead um ein “Problem” zu lösen, welches eventuell irgendwann Mal relevant werden sollte.

    Ich bin ja ein Fan von SE, hier gibts qualifizierte Antworten auf diverse Themen rund um QC: https://quantumcomputing.stackexchange.com/

    Monero ist ziemlich agil, wenn ein Thema Relevanz bekommt (siehe ASIC-Fork) und ich bin mir ziemlich sicher, dass eine Protokolländerung ziemlich zeitnah implementiert werden würde, sobald QC in eine relevante Sphäre vorrücken sollten. Derzeit kann man sich noch nichtmal sicher sein, ob die aktuellen QC mit 40 QBits nicht eher simulierte QBits haben. Vom brechen von ECC Verschlüsselungen wären diese allerdings eh um ca. Faktor 100 entfernt… Das mag nach wenig klingen, allerdings muss man sich vor Augen halten, dass 1 QBit trivial ist, der Fortschritt zu knapp 40 hat jetzt mehr als 10 Jahre gedauert…

    Ist aber ein spannendes Thema!

  5. Herzlichen Dank für die Infos Paul Janowitz!!

    GG

  6. Was meint Ihr mit ECC?
    Das wird mir nicht so ganz klar. Kenne nur die ECC Blockchain, ecc.network

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s