In 2015 hebben we Confidential Transactions (CT) aangekondigd als een van de voornaamste functies van Elements. Deze functie verving bedragen in transacties met zogenaamde Pedersen commitments, een cryptografische truc waarmee bedragen kunnen worden verborgen zonder de mogelijkheid te verliezen om te controleren of de bedragen binnen een transactie gebalanceerd zijn.
Een van de problemen met CT was dat de transacties erg groot en langzaam te verifiëren zijn, want elke transactie bevat een rangeproof, een zero-knowledge proof dat bewijst dat de bedragen binnen een bepaald bereik vallen. Een gewone digitale signature is minder dan 100 bytes groot en is te verifiëren in 100 microseconden, maar rangeproofs zijn meerdere kilobytes en zijn te verifiëren in een aantal milliseconden. In de praktijk waren de rangeproofs het merendeel van de gegevens in een transactie die er gebruik van maakte.
Onze rangeproofs, gebaseerd op Borromean ring signatures, waren de snelste en kleinste optie binnen de literatuur voor het voor ons benodigde bereik en zonder zogenaamde 'trusted setup', maar waren alsnog best groot.
Sinds 2015 is er veel voortgang geboekt in het verbeteren van de efficiëntie van rangeproofs. Aan het begin van 2017 kwam Adam Back met een reductie van 24% voor de grootte van de rangeproofs maar zonder verbetering in de verificatiesnelheid. Rond die tijd introduceerden we het probleem aan onze vrienden en mede-cryptografen Dan Boneh en Benedikt Bünz van de Universiteit van Stanford, en zij dachten dat er ruimte was voor verbetering.
Hun uiteindelijke voorstel was indrukwekkend.
Kleiner, sneller, beter
Bulletproofs zijn gebaseerd op een verbetering uit 2016 voor discrete-log zero knowledge proofs van Bootle et al, en zijn een nog efficiëntere versie van zero-knowledge proofs. Wat belangrijk was voor onze doeleinden is dat deze proofs publieke sleutels met bedragen in Pedersen commitments ondersteunden. Hierdoor is het voor ons mogelijk om rangeproofs met deze methode voor zero-knowledge proofs te implementeren zonder dat er ingewikkelde constructies nodig zijn om elliptic curve cryptography te implementeren.
Beter. Om de grootte van de transacties te minimaliseren, hadden onze oude rangeproofs een limiet van 2^32 voor het bedrag. Dit betekende dat een output ongeveer 43 BTC groot kon zijn, al kon dit worden vergroot door de granulairiteit van de proofs te verkleinen van 1 satoshi naar 10 of 100, of door het minimum te vergroten voorbij nul. Deze aanpassingen waren mogelijk maar maakten gebruik van expliciete waarden, waardoor het ten kost zou gaan van de privacy.
Deze 32-bit rangeproofs waren ongeveer 2,5 KiB groot. Met de optimalisatie van Adam zouden ze ongeveer 2 KiB groot zijn. Met Bulletproofs zijn ze slechts 610 bytes groot. Omdat Bulletproofs zo klein zijn, kunnen we makkelijk het bereik verdubbelen naar 64 bits, om zo ook van het privacyprobleem af te zijn. Verdubbelt nu de grootte van slechts 610 bytes naar 1220 bytes? Nee. Een 64-bit rangeproof is met Bulletproofs slechts 674 bytes.
Kleiner. De reden dat we het bereik kunnen verdubbelen met slechts 64 bytes extra is omdat de proofs logaritmisch in grootte toenemen. Dit wordt bereikt met een variant van het 'inner product argument' uit de publicatie van Bootle et al 2016. (Jonathan Bootle heeft Benedikt en Dan ook geholpen tijdens de ontwikkeling van Bulletproofs). Het logaritmische 'inner product argument' was zelfs nog verder verbeterd voor Bulletproofs van 6log(N) curve points naar 2log(N).
Dezelfde truc kan worden gebruikt om meerdere rangeproofs samen te brengen binnen één transactie, waardoor de grootte slechts een klein beetje toeneemt. Het samenbrengen van twee rangeproofs is 738 bytes, vier rangeproofs 802, en acht 866. Voorheen zouden acht 64-bit rangeproofs meer dan 40000 bytes groot zijn!
Sneller. Het reduceren van de grootte is erg positief, maar onze eerste analyse van de techniek gaf aan dat verificatie langzamer zou zijn dan de voormalige rangeproofs. Het leek erop dat de verificatie van een enkele 64-bit proof 200 scalar-point-vermenigvuldigingen zou vereisen, wat per vermenigvuldiging 50 microseconden zou kosten, terwijl dit met de oude rangeproofs slechts 128 keer hoefde.
Maar na het verder te analyseren, bleek dat we een hoop van de vermenigvuldigingen konden samenbrengen, wat het aantal naar 147 bracht. Maar het belangrijkste is dat deze vermenigvuldigingen, in tegenstelling tot de oude methode, niet van elkaar afhankelijk waren, waardoor we ze gelijktijdig konden uitvoeren. Dankzij ons onderzoek naar aggregate signatures, wisten we hoe we gelijktijdige vermenigvuldigingen konden versnellen. Pieter Wuille, Greg Maxwell, Jonas Nick, Peter Dettman en ik hebben meerdere maanden besteed aan dit probleem en hebben de snelheid van 147 vermenigvuldigingen teruggebracht naar 15.5 microseconden per stuk, wat de verificatietijd van Bulletproofs verlaagt naar 2,3 ms in tegenstelling tot 5,8 ms voor de oude proofs.
Dit is al meer dan een verdubbeling in de snelheid, maar omdat het samenbrengen van vermenigvuldigingen sneller wordt met meer berekeningen, is de efficiëntie nog indrukwekkender als je meerdere proofs tegelijk verifieert. Acht 64-bit Bulletproofs kunnen worden geverifieerd in slechts 10,7 ms in tegenstelling tot 46,5 ms voor de oude proofs. Dat is meer dan 4x sneller.
Maar dat is nog niet alles. Bulletproofs ondersteunen een extreem efficiënte vorm van gelijktijdige verificatie (batch validation). We moeten 147 vermenigvuldigingen uitvoeren, maar 130 ervan maken gebruik van dezelfde curve points voor elke Bulletproof, wat betekent dat deze kunnen worden gecombineerd tijdens gelijktijdige verificatie, waardoor er slechts 17 nieuwe vermenigvuldigingen overblijven. En deze nieuwe vermenigvuldigingen nemen slechts logaritmisch toe: voor 2 gelijktijdige rangeproofs zijn er 19 extra curve points, en voor 4 rangeproofs 21.
Let op dat we twee soortgelijke maar aparte technieken hebben geïntroduceerd. Het samenbrengen van meerdere rangeproofs binnen één proof, en het gelijktijdig verifiëren van meerdere rangeproofs.
Dit betekent dat twee 64-bit rangeproofs kunnen worden geverifieerd binnen 2,7 ms, of 1,3 ms per stuk. Duizend rangeproofs kunnen worden geverifieerd in 239 ms, of 0,24 ms per stuk, wat 23x beter is dan de oude proofs. Met het samenbrengen van meerdere rangeproofs wordt het resultaat nog beter. Duizend rangeproofs waarin er acht zijn samengebracht (dus 8000 in totaal) kunnen worden geverifieerd in 588 ms, of 74 microseconden per stuk, dat is 78x sneller dan de oude rangeproofs.
Dit resultaat bereikt zijn maximum bij het samenbrengen van 64 proofs, want dan is de efficiëntie van het vermenigvuldigen van curve points niet langer het dominante effect. De optimale gelijktijdige verificatie haalt 49 microseconden per stuk, een verbetering van 120x. Ter vergelijking, een signature voor Elliptic Curve Digital Signature Algorithm (ECDSA) duurt ongeveer 49 microseconds, dus op dit niveau is de rangeproof niet meer het dominante onderdeel van transactieverificatie. Het is natuurlijk onwaarschijnlijk dat we veel transacties met 64 outputs op de blockchain gaan zien, maar deze snelheid is ook te halen in gebruik buiten de blockchain, zoals Provisions.
Deze verificatie is ook geheugen-efficiënt. Er is minder dan 100 KiB nodig om een enkele rangeproof te verifiëren, en dit schaalt lineair.
Alles is te bewijzen (als het waar is)
Bulletproofs zijn veel veelzijdiger dan rangeproofs. Ze kunnen worden gebruikt om elke berekening te bewijzen in zero knowledge. Ze zijn equivalent in kracht met SNARKs of STARKs, maar ondersteunen van nature elliptic curve (EC) publieke sleutels en Pedersen commitments (dus het is niet nodig om EC-berekeningen te implementeren binnen de berekening die je wilt bewijzen). En in tegenstelling tot SNARKs hebben Bulletproofs volledige 128-bit beveiliging onder standaard veronderstellingen zonder 'trusted setup'. In tegenstelling tot STARKs zijn ze snel genoeg om simpele problemen te bewijzen en verifiëren op typische hardware.
Een specifiek voorbeeld is het gebruik van een SHA2-compressiefunctie. We kunnen kennis van een SHA2-preimage bewijzen in minder dan 30 MiB geheugen en 13 seconden. Verificatie verbruikt 23 MiB geheugen en 435 ms, maar met gelijktijdige verificatie kunnen we meerdere proofs verifiëren in 28 ms en 13,4 KiB per stuk. Het resultaat is slechts 1379 bytes.
Onze bewijsmethode is efficiënter in geheugengebruik dan een SNARK. Op hetzelfde systeem verbruikt een SNARK-bewijs 75 MiB geheugen, maar ook slechts 4 seconden. Verificatie vereist een flinke pre-computatie voor elk circuit (de omschrijving van de berekening die je wilt bewijzen), en vergt vervolgens slechts 3-5 ms en weinig geheugen om te verifiëren. Deze getallen stijgen niet met de grootte van het circuit, dus voor meer dan een paar duizend gates zijn SNARKs sneller dan zelfs onze gelijktijdige verificatiemethode. Helaas vereist dit wel een trusted setup en nieuwe cryptografische assumpties.
Er blijft nog steeds veel ruimte over voor aanvullende optimalisaties voor Bulletproofs, bij zowel het bewijzen als de verificatie.
De mogelijkheid om willekeurige berekeningen te bewijzen (via Bulletproofs, SNARKs of STARKs) heeft vele toepassingen. Het kan worden gebruikt voor de implementatie van gewone digitale signatures, waaronder (traceable) ring signatures en threshold signatures, wat voor grote ringen waarschijnlijk efficiënter is dan traditionele methodes, zowel in verificatietijd als bewijsgrootte, maar er is nog meer mogelijk. Het kan worden gebruikt om sudoku-oplossingen zonder risico te verkopen. Je kan voor multiparty computations bewijzen dat elke partij eerlijk handelde, zelfs zonder geheimen prijs te geven. (Dit kan van pas komen bij multisignature-methodes zoals MuSig om de nonce deterministisch te genereren zonder dat de deelnemers de staat bij moeten houden of vatbaar zijn voor aanvallen waarin de nonce wordt hergebruikt.) Het kan worden gebruikt om kennis van hash-preimages te bewijzen.
Deze laatste toepassing, hash-preimages, is vooral interessant omdat het kan worden gebruikt voor zero-knowledge Merkle-proofs, waardoor het bewijzen van inclusie binnen een gigantische set (met miljoenen of zelfs biljoenen elementen) mogelijk wordt. Dit verkennen we later meer in een toekomstig artikel.
Conclusie
● Bulletproofs zijn algemene zero-knowledge proof (zoals SNARKs)
● Ze kunnen worden gebruikt om multiparty-protocols zoals multisignatures of Zero-knowledge Contingent Payments uit te breiden
● Bulletproofs maken een veel efficiëntere versie van CT-rangeproofs mogelijk (met gelijktijdige verificatie is het meer dan 23x sneller)
● Deze rangeproofs kunnen worden samengevoegd binnen transacties met slechts een logaritmische toename in grootte.
● Door alles samen te brengen, zoals in Provisions, wordt gelijktijdige verificatie meer dan 120x sneller dan de voormalige proofs.
We willen Bootle et al. graag bedanken voor de ontwikkeling van het 'inner product argument' dat hiertoe heeft geleid, alsmede Benedikt Bünz en Dan Boneh, onze medeauteurs, die het grootste deel van het uitvindwerk voor hun rekening namen. Ook willen we Sean Bowe en Daira Hopwood bedanken voor hun omtrent het optimaliseren van aritmetische circuits.
Alle berekeningen zijn uitgevoerd op een enkele core van een Intel i7-6820HQ CPU op 2,70GHz.
Links
● Bulletproofs - Stanford Applied Cryptography
● Presentatie Benedikt Bünz BPASE ‘18
● Presentatie Andrew Poelstra Milano Bitcoin meetup (slides)