Im Jahr 2015 kündigten wir Confidential Transactions (CT) als Highlight von Elements an. Diese Funktion ersetzte Transaktionsbeträge mit Pedersen Commitments, einem kryptografischen Tool zum Verbergen der Beträge, wobei die Fähigkeit bestehen bleibt, dass jedermann verifizieren kann, ob die Beträge in einer bestimmten Transaktion ausgeglichen sind.
Ein großes Problem bei CT bestand darin, dass die Transaktionen dadurch sehr umfangreich wurden und die Verifikation langsam vonstatten ging, da jeder Transaktions-Output einen Rangeproof enthalten musste, also eine Art Zero-Knowledge-Beweis, der beweist, dass die Beträge zu klein sind um überzulaufen. Während eine herkömmliche digitale Signatur weniger als 100 Bytes groß ist und ihre Verifikation weniger als 10 Mikrosekunden erfordert, waren diese Rangeproofs mehrere Kilobytes groß und die Verifikation dauerte mehrere Millisekunden. In Transaktionen, die Rangeproofs benutzten, machten diese in der Praxis den Großteil der Transaktionsdaten aus.
Obwohl unsere, auf Borromean Ring Signatures basierenden Rangeproofs in der Literatur die schnellsten und kleinsten waren – für die Range-Größen, die wir brauchten, und ohne vertrauenswürdiges Setup – waren sie dennoch ziemlich groß.
Seit 2015 gibt es Anstrengungen, die Effizienz von Rangeproofs zu verbessern. Anfang 2017 gelang Adam Back eine 24%ige Reduzierung der Rangeproof-Größe, allerdings ohne Verbesserung der Verifikationsgeschwindigkeit. Damals hatten wir das Problem gegenüber unseren Freunden und Kryptographie-Kollegen Dan Boneh und Benedikt Bünz an der Stanford-Universität erwähnt, die sich ziemlich sicher waren, dass es noch Raum für Verbesserungen gibt.
Was sie sich schließlich einfallen ließen, hat uns erstaunt.
Kleiner, schneller, stärker
Eine von Bootle et al vorgenommene Verbesserung der Effizienz von Zero-Knowledge-Beweisen auf der Basis von diskreten Logarithmen führte zu Bulletproofs, eine noch effizientere Form von Zero-Knowledge-Beweisen. Wichtig für unsere Zwecke ist, dass diese Beweise auch eine native Unterstützung von Committed Values wie Pedersen Commitments und Public Keys bieten. Somit können wir Dinge wie Rangeproofs in diesem allgemeinen Zero-Knowledge-System nutzen, ohne die aufwändige Kurvenarithmetik innerhalb eines Zero-Knowledge-Beweises implementieren zu müssen.
Stärker. Zur Begrenzung der Transaktionsgröße wurden die Outputs in unseren alten Rangeproofs auf einen Größenbereich von 2^32 beschränkt. Dadurch waren die Outputs auf etwa 43 BTC beschränkt, obgleich wir dies erhöhen konnten, indem wir die Granularität der Beweise von 1 Satoshi auf 10 oder 100 reduzieren oder den Mindestbetrag von Null erhöhen. Diese Anpassungen waren möglich, verwendeten jedoch explizite Beträge, wodurch die Vertraulichkeit eingeschränkt wurde.
Diese 32-Bit-Rangeproofs waren ungefähr 2,5 KiB groß. Dank der Optimierung von Adam wären sie 2 KiB, mit Bulletproofs 610 Bytes groß gewesen. Bei so kleinen Größen lohnt es sich, den Bereich auf 64 Bit zu verdoppeln, was die nichtvertraulichen Anpassungen unnötig macht. Dies würde die geringe Menge von 610 Bytes auf 1220 erhöhen, müsste man meinen. Aber nein, ein 64-Bit-Rangeproof in Bulletproof-Form ist nur 674 Byte groß.
Kleiner. Wir können die Range-Größe verdoppeln und der Beweis-Größe nur 64 Byte hinzufügen, weil die letztere logarithmisch zunimmt. Dies geschieht anhand einer Variante des Skalarproduktarguments von Bootle et al aus dem Jahr 2016. (Jonathan Bootle half auch Benedikt und Dan bei der Entwicklung von Bulletproofs). Das in dieser Arbeitbeschriebene logarithmisch aufgebaute Skalarproduktargument wurde in den Bulletproofs noch weiter reduziert, nämlich von 6log(N) Kurvenpunkten auf 2log(N).
Der gleiche Trick ermöglicht die Aggregation mehrerer Rangeproofs in einer einzigen Transaktion, wobei die Größe nur geringfügig ansteigt. Zwei aggregierte Rangeproofs sind 738 Bytes groß, bei vier sind es 802 Bytes, bei acht sind es 866 Bytes. Ein klassischer 64-Bit-Rangeproof wäre über 40000 Bytes groß!
Schneller. Diese Größenersparnisse sind gut, aber unsere erste Analyse der Methode zeigte, dass die Verifikation länger dauern würde als bei den alten Rangeproofs. So würde die Verifikation eines einzigen 64-Bit-Beweises über 200 Skalarprodukt-Multiplikationen erfordern, wobei jede mit 50 Mikrosekunden kräftig zu Buche schlägt, während die alten Rangeproofs nur 128 erforderten.
Nach weiterer Prüfung konnten wir jedoch viele Multiplikationen kombinieren und auf insgesamt 147 reduzieren. Mehr noch: Wir erkannten, dass keine dieser Multiplikationen, im Gegensatz zu den alten Rangeproofs, voneinander abhingen und wir sie alle in einem Durchlauf ausführen konnten. Aufgrund unserer Arbeit an aggregierten Signaturen wussten wir, wie man sehr schnell in einem Durchlauf multipliziert. Pieter Wuille, Greg Maxwell, Jonas Nick, Peter Dettman und ich hatten mehrere Monate an diesem Problem gearbeitet und die Geschwindigkeit von 147 Multiplikationen auf jeweils 15,5 Mikrosekunden verringert, wodurch sich die gesamte Verifikationszeit eines Bulletproofs auf 2,3 ms im Gegensatz zu 5,8 ms für die alten Beweise reduzierte.
Damit wird die Geschwindigkeit bereits mehr als verdoppelt, und da unsere Batch-Multiplikation schneller wird, je mehr Punkte man hinzufügt, ist die Leistung für aggregierte Rangeproofs noch beeindruckender. Ein acht aggegierte 64-Bit Bulletproofs könnenschon in 10,7 ms verifiziert werden, im Gegensatz zu 46,5 ms bei den alten Beweisen. Somit wird die Geschwindigkeit mehr als vervierfacht.
Es kommt noch besser: Bulletproofs unterstützen eine äußerst wirksame Form der Batch-Verifikation. Von den erforderlichen 147 Verifikationen verwenden 130 die gleichen Punkte in jedem Bulletproof. Das bedeutet, dass diese 130 Multiplikationen bei der Batch-Verifikation kombiniert werden können, wobei nur 17 neue verbleiben. Diese marginalen Kosten steigen nur logarithmisch: Für aggregierte Beweise von zwei Bereichen Bereichen erfordert jeder zusätzliche Beweis 19 Extrapunkte und für vier Bereiche sind es 21..
Zu beachten ist, dass wir zwei ähnliche, aber separate Konzepte eingeführt haben: Aggregation bedeutet, dass ein Beweiser mehrere Rangeproofs in einem zusammenfasst, Batching bedeutet, dass ein Verifizierer mehrere separate Beweise gleichzeitig prüft.
Das heißt, dass zwei 64-Bit Rangeproofs in weniger als 2,7 ms bzw. 1,3 ms pro Bereich validiert werden können. Tausend Rangeproofs können in 239 ms bzw. 0,24 ms pro Bereich validiert werden, eine 23-fache Verbesserung im Vergleich zu den alten Beweisen. Aufgrund der Aggregation wird es noch besser: Tausend 8-fache (also 8000 Bereiche insgesamt) aggregierte Rangeproofs können in 588 ms oder 74 Mikrosekunden pro Bereich validiert werden, eine 78-fache Verbesserung im Vergleich zu den alten Rangeproofs.
Dieser Effekt ist bei 64 Beweisen ausgereizt, da die zunehmend effizienten Skalarprodukt-Multiplikationen kein dominanter Effekt mehr sind. An diesem Punkt können wir die Batch-Validierung in unter 49 Mikrosekunden pro Bereich durchführen, eine 120-fache Verbesserung. Um einen Bezug zu geben, eine Elliptic Curve Digital Signature Algorithm (ECDSA)-Signatur erfordert etwa 49 Mikrosekunden, somit ist der Rangeproof auf dieser Ebene der Aggregation nicht einmal der dominante Teil der Transaktionsvalidierung. Es ist zwar unwahrscheinlich, dass wir auf der Blockchain viele 64-Output-Transaktionen sehen werden, aber diese Geschwindigkeit ist in Situationen außerhalb der Blockchain, wie z. B. Provisions sicherlich möglich.
Diese Verifikation ist auch speichereffizient, da es weniger als 100 KiB erfordert, um einen einzigen Rangeproof zu validieren, und lässt sich linear mit der Größe skalieren.
Man kann alles beweisen (sofern es wahr ist)
Bulletproofs sind viel allgemeiner als Rangeproofs. Sie können verwendet werden, um im Zero Knowledge-Verfahren beliebige Aussagen zu beweisen. Sie sind ähnlich leistungsfähig wie SNARKs oder STARKs, haben aber native Unterstützung für Elliptic Curve (EC) Public Keys sowie Pedersen Commitments (somit ist es in der Regel nicht notwendig, EC-Berechnungen innerhalb eines zu beweisenden Programms umzusetzen). Zudem haben Bulletproofs, im Gegensatz zu SNARKs, vollständige 128-Bit Sicherheit unter Standardannahmen ohne vertrauenswürdiges Setup. Im Gegensatz zu STARKs sind sie schnell genug, um Probleme einer angemessenen Größe auf typischer Computer-Hardware zu beweisen und zu verifizieren.
Ein spezifisches Beispiel wäre ein einzelner Durchlauf einer SHA2-Komprimierungsfunktion. Unser Beweiser erfordert weniger als 30 MiB Speicher und etwa 13 Sekunden, um die Kenntnis eines SHA2-Urbildes zu beweisen. Die Verifizierung erfordert etwa 23 MiB Speicher und 435 ms, aber wir können zusätzliche Beweise in etwa jeweils 28 ms und 13,4 KiB stapelweise verarbeiten. Der resultierende Beweis hat nur 1379 Bytes.
Unser Beweiser ist speicher-effizienter als der für SNARKs: Auf dem gleichen System erfordert ein SNARK-Beweisfür SHA2 nur 4 Sekunden, aber 75 MiB Speicher. Die Verifizierung erfordert zwar eine große einmalige Vorberechnung für jeden Schaltkreis (Beschreibung der zu beweisenden Aussage), aber nur 3–5 ms und sehr wenig Speicher. Diese Zahlen steigen nicht mit der Größe des Schaltkreises, daher sind SNARKs bei mehreren Tausend Gates der deutliche Sieger verglichen mit unserer Batch-Validierung. Dies geht leider auf Kosten eines vertrauenswürdigen Setups und neuer kryptographischer Annahmen.
Es bleibt noch viel Raum für eine weiterführende Optimierung der Bulletproofs, sowohl beim Beweiser als auch beim Verifizierer.
Diese Fähigkeit zum Beweisen von beliebigen Aussagen — sei es durch Bulletproofs, SNARKs oder STARKs — bietet viele Anwendungen. Sie kann zur Ausführung von herkömmlichen digitalen Signaturen, einschließlich (nachvollziehbarer) Ringsignaturen und Schwellensignaturen verwendet werden, was für umfangreiche Ringe wahrscheinlich effizienter ist als traditionelle Schemata, sowohl im Hinblick auf die Verifizierungszeit als auch die Beweis-Größe, ist allerdings nicht darauf beschränkt. Sie kann verwendet werden, um vertrauenslos Sudoku-Probleme zu verkaufen. Sie kann in Mehrparteien-Berechnungen verwendet werden, um zu beweisen, dass sich jede Partei ehrlich verhalten hat, sogar mit geheimen Daten. (Insbesondere bei Methoden zur Multisignaturen wie MuSig ermöglicht dies die deterministische Nonce-Erzeugung, ohne dass die Unterzeichner einen Zustand halten müssen oder für Nonce-Reuse-Angriffe anfällig sind.) Sie kann für den Beweis von Hash-Urbildern verwendet werden.
Diese letzte Anwendung, Hash-Urbilder, ist besonders interessant, da sie zur Erzeugung von Zero-Knowledge Merkle Proofs, effizienten Mengenzugehörigkeitsbeweisen (Proof of Inclusion) in riesigen Mengen (mit Millionen oder sogar Milliarden von Elementen), genutzt werden kann. Wir werden in zukünftigen Beiträgen näher darauf eingehen.
Fazit
● Bulletproofs sind allgemeine Zero-Knowledge-Beweise (wie SNARKs)
● Sie können zur Erweiterung von Mehrpartei-Protokollen wie Multisignaturen oder Zero-Knowledge Contingent-Zahlungen verwendet werden
● Bulletproofs bieten eine viel effizientere Version der CT-Rangeproofs (über 23-fache Steigerung der Geschwindigkeit bei der Batch-Verifikation)
● Diese Rangeproofs können innerhalb von Transaktionen aggregiert werden, wobei sich die Größe lediglich logarithmisch erhöht.
● Bei hinreichender Aggregation, wie bei Provisions, wird die Batch-Verifikation über 120-mal schneller als die alten Beweise.
Wir danken Bootle et al. für die Entwicklung des Skalarproduktarguments, das hierzu geführt hat. Darüberhinaus danken wir Benedikt Bünz und Dan Boneh, unseren Mitverfassern, die den größten Teil der Erfindungsarbeit geleistet haben. Schließlich danken wir Sean Bowe und Daira Hopwood für ihre Forschung zur Optimierung von arithmetischen Schaltkreisen.
Alle Berechnungen wurden auf einem Einzelkernprozessor eines Intel i7-6820HQ CPU mit 2,70 GHz ausgeführt.
Links
● Bulletproofs – Stanford Applied Crypography
● Vortrag von Benedikt Bünz anlässlich der BPASE ‘18
● Vortrag von Andrew Poelstra anlässlich des Milano Bitcoin Meetup (Folien)