Bitcoin, en gerelateerde blockchains zoals Liquid van Blockstream, maken gebruik van het ECDSA-algorithme voor signatures om het bezit en overdracht van bitcoins in het systeem te verifiëren. Dit was een technisch besluit dat vermoedelijk in 2008 is genomen op basis van de veelgebruikte en ongepatenteerde systemen voor digitale signatures die toentertijd beschikbaar waren. ECDSA heeft echter een aantal flinke technische beperkingen. Vooral multisignatures en threshold signatures – signatures die zijn gemaakt door verschillende onafhankelijke partijen en niet slechts één persoon – zijn lastig te produceren met ECDSA. Met ECDSA hebben signatures een complexe algebraïsche structuur die het inflexibel en ingewikkeld maakt. Hierdoor moeten bitcoin-ontwikkelaars gebruikmaken van Bitcoin Script voor applicaties zoals cross-chain atomic swaps of Lightning, terwijl dit met flexibelere signatures op compactere wijze en met meer privacy zou kunnen worden geïmplementeerd.
Hoewel er veel is veranderd in de wereld van digitale signatures sinds 2008, zijn de alternatieven die in de literatuur staan beschreven vaak niet praktisch voor echt gebruik. Vaak wordt ervan uitgegaan dat de maker van de signature volledige controle heeft over hoe en wanneer de sleutels worden aangemaakt: er moet toegang zijn tot getallen die volledig random (willekeurig) zijn, en het geheugen moet persistent, betrouwbaar en veilig zijn. In de praktijk hebben gebruikers in bitcoin slechts beperkte toegang tot hun sleutels, weinig controle over het mechanisme voor het genereren van sleutels, en geen controle over hoe externe partijen de adressen gebruiken die ze genereren. Om deze problemen aan te pakken, zijn we een initiatief gestart om een nieuw signature-ontwerp te ontwerpen. Tevens hebben we flink veel werk gedaan om het te implementeren op een manier die robuust en antifragiel is.
Introductie
In de eerste helft van het afgelopen jaar hebben Blockstreams cryptografie-expert Pieter Wuille en ik in samenwerking met Yannick Seurin en Gregory Maxwell een nieuw signature-ontwerp genaamd MuSig gepubliceerd. Dit multisignature-ontwerp was aantoonbaar veilig, zelfs bij samenwerking met kwaadaardige partijen, en produceert een signature die niet te onderscheiden is van een gewone Schnorr-signature van een enkele gebruiker.
Sindsdien zijn we aan de slag gegaan om de academische paper van MuSig om te zetten in bruikbare code. Deze week hebben we de code toegevoegd aan secp256k1-zkp, een fork van secp256k1 (de high-assurance cryptografische library van Bitcoin Core), die we hebben uitgebreid met ondersteuning voor Confidential Transactions voor Elements en Liquid.
De bitcoin-community is momenteel het gebruik van Schnorr-signatures aan het onderzoeken. Wij hopen dat onze code uiteindelijk in de secp256k1 library van Bitcoin Core en vele andere projecten zal verschijnen.
Onze code produceert signatures in navolging van BIP-schnorr en kan tevens adaptor signatures produceren, wat Lightning in scriptless scripts mogelijk maakt.
Waarom MuSig?
Zoals we vorig jaar hebben besproken, bestaan er in de literatuur van de cryptografie veel multisignature-ontwerpen. Je zou je dus kunnen afvragen waarom het nodig was om een eigen ontwerp te maken. De reden daarvoor is dat we twee vereisten hadden waar niet aan werd voldaan in bestaande ontwerpen:
- Korte signatures van constante grootte die er ongeacht de hoeveelheid participanten hetzelfde uitzien. In een blockchain-systeem is de efficiëntie van verificatie van essentieel belang. Het is niet logisch om de verificateurs te belasten met details over de hoeveelheid participanten. Bovendien verbeteren MuSig-signatures tevens de privacy, gezien ze de informatie over de hoeveelheid participanten geheel verbergen.
- Aantoonbare veiligheid voor zichtbare publieke sleutels. Dit houdt in dat participanten volledige flexibiliteit hebben om mee te doen aan een multisignature met gewone sleutels, zonder dat extra informatie moeten meegeven over hoe de sleutels zijn geproduceerd of worden bewaard. Informatie over het genereren van sleutels is moeilijk over te dragen in de context van bitcoin, omdat individuele participanten op gevarieerde en restrictieve manieren hun sleutels beheren. Daarnaast kan de afhankelijkheid van details over het genereren van de sleutel problemen veroorzaken met Taproot, een extensie van bitcoin waarin publieke sleutels mogelijk aanvullende informatie in zich verborgen houden.
Bovendien hebben we sinds de aankondiging van MuSig geleerd dat een hoop van de gepubliceerde signature-ontwerpen, en ook een voorheen ongepubliceerde versie van MuSig, niet veilig blijken te zijn! We bespreken dit in de toekomst verder, maar hopelijk is het in elk geval duidelijk dat het niet makkelijk was om een multisignature-ontwerp te ontwikkelen dat geschikt is voor bitcoin en Liquid.
Gevaren en veilige API-ontwikkeling
Onze gepubliceerde versie van MuSig gaat er net als andere multisignature-protocollen vanuit dat participanten toegang hebben tot het geheugen tijdens het maken van de signature, en dat dit geheugen persistent, makkelijk te updaten, en niet terug naar voorgaande staten te zetten is door aanvallers. Het gaat er ook vanuit dat participanten toegang hebben tot een bron van randomness (willekeurigheid) die niet van uniform is te onderscheiden. Helaas is dit in de praktijk niet zo makkelijk, en we hebben een hoop tijd gestoken in het ontwerpen van een API die kan worden gebruikt in verschillende scenario’s, zonder dat mogelijk gelimiteerde hardware of ongenoemde aannames kunnen leiden tot het lekken van een privésleutel.
MuSig-signatures maken net als Schnorr-signatures en ECDSA gebruik van een geheime “nonce” die geheel random moet worden gegenereerd. Als er zelfs een enkele bit niet uniform is, kan dit leiden tot het lekken van de privésleutel en gestolen bitcoins.
Ons primaire doel was om een API te creëren die niet door verkeerd gebruik tot problemen kan leiden, en die geen problematische gebruikspatronen aanmoedigt, zelfs in gevallen waar er veel beperkingen zijn.
Uniform random
Voor individuele signatures is het creëren van uniform random getallen makkelijk: neem wat geheime informatie en het bericht waar de signature voor wordt gemaakt, en voer deze in bij een cryptografische hash-functie dat een uniform random en geheel onafhankelijk getal produceert voor elk mogelijk bericht.
Voor multisignatures is deze makkelijke en betrouwbare oplossing niet veilig. Een kwaadaardige participant kan twee multisignatures verzoeken voor hetzelfde bericht, en hun eigen contributie aanpassen voor de tweede signature. Als het slachtoffer een nonce kiest door een geheim en het bericht te hashen, wordt dezelfde nonce gebruikt in twee verschillende signatures. Dit is precies hetzelfde probleem dat ervoor zorgde dat de PS3 werd gehackt. Helaas is er geen makkelijke oplossing zoals het geval is voor een signature van een enkele participant, want elke participant moet zijn nonce kiezen voor de details van de signature bekend zijn.
De traditionele oplossing voor dit probleem, en tevens de oplossing die werd gebruikt voordat hashen populair werd, is om een hardware random number generator te gebruiken. Helaas zijn deze vaak duur, beïnvloedbaar van buitenaf en door de omgeving, en is er bovendien geen manier om te verifiëren of ze correct werken.
Het laatste punt, over of ze correct werken, heeft een aantal creatieve oplossingen die we in een toekomstig artikel zullen verkennen. We hebben er voorlopig voor gekozen om de API een unieke “sessie-ID” te laten aanmaken voor elke signature. Nonces worden geproduceerd door het geheim van de gebruiker, alle participanten van de signature, het bericht, en een unieke input voor de sessie te hashen. Gebruikers die toegang hebben tot een random number generator, kunnen daar gebruik van maken om een sessie-ID aan te maken. Gebruikers met persistent geheugen kunnen simpelweg een teller bijhouden.
We zijn niet tevreden met de noodzaak voor willekeurige getallen of persistent geheugen, en verwachten dat we daar met ons huidige onderzoek binnenkort een echt betrouwbare oplossing voor vinden.
Replay attacks
Zelfs met een goede random bron is het mogelijk om privésleutels van een participant in een multisignature te achterhalen als het mogelijk is om het protocol voor de signature opnieuw af te spelen vanaf een dieper punt in het proces. Deze aanval heet een “replay attack” en kan worden uitgevoerd tegen een gebruiker die een signature probeert te maken binnen een herstartbare virtuele machine, of als het mogelijk is om het proces te onderbreken en terug te gaan naar een voorgaande staat. Het kan zelfs per ongeluk voorkomen zonder een actieve aanval, als er bijvoorbeeld twee virtuele machines worden gecloond vanaf dezelfde staat, of door code uit te voeren op een gedistribueerde database die niet goed is gesynchroniseerd.
Als een participant bijdraagt aan een multisignature en het proces opnieuw wordt gestart vanaf het punt waarop de nonce wordt gekozen, is het zelfs mogelijk om de bijdrage van andere participanten aan te passen en dezelfde aanval uit te voeren als werd omschreven in de vorige sectie.
Dit soort aanvallen kunnen niet voorkomen met signatures voor enkele gebruikers, want deze worden geproduceerd in één stap, zonder onafgemaakte staat om naar terug te keren. Deze aanvullende uitdagingen zijn dus uniek voor cryptografische protocollen met meerdere rondes.
Zonder nieuwe mechanismes (die momenteel door ons worden onderzocht) kunnen we niets doen om gebruikers die een signature maken in een virtuele machine, te beschermen. Wel maken we de observatie dat het gebruik van een virtuele machine sowieso de beveiliging verlaagt, want een machine die een aanvaller kan resetten, is waarschijnlijk ook een machine waar de geheimen direct uit vallen te extraheren.
Om gebruikers te beschermen die misschien hun oude staat in volgorde bijhouden en erin herstarten, ondersteunt onze API simpelweg niet de serialisatie van signature-sessies.
In de praktijk betekent dit dat gebruikers van onze code die hun sessie willen kunnen voortzetten na interruptie (een redelijk doel voor een hardware wallet), gebruik moeten maken van veilig, persistent geheugen. Als zulke wallets meerdere signatures in parallel willen kunnen uitvoeren, moeten ze voor elke sessie apart persistent geheugen hebben.
Zoals eerder vermeld, is dit een probleem dat we vermoedelijk kunnen verhelpen met methodes waar we momenteel onderzoek naar doen.
Conclusies en wat de toekomst brengt
Uit de bovenstaande discussie blijkt dat protocollen met meerdere participanten nieuwe, lastige uitdagingen creëren die niet voorkomen bij een enkele participant. Wiskundig gezien is MuSig veel simpeler dan iets als bijvoorbeeld Bulletproofs. Maar qua implementatie heeft MuSig meer moeite gekost en waren er meer afwegingen tussen antifragiliteit en flexibiliteit van de API.
Dit artikel heeft alleen multisignatures omschreven: signatures waarin meerdere participanten samenwerken om samen een enkele signature te vormen. In een toekomstig artikel beschrijven we ook threshold signatures, een gerelateerd concept waarin een subgroep van de participanten, als het er maar genoeg zijn, een geldige signature kunnen produceren zonder contributie van de gehele groep.
Ook gaan we in de toekomst technieken bespreken die random nonces veiliger maken om te produceren, en makkelijker verifieerbaar maken. Door gebruik te maken van een techniek genaamd sign-to-contract is het mogelijk voor de host-computer om onbetrouwbaarheid van de random number generator van een hardware wallet tegen te gaan.
We kunnen nog verdergaan door gebruik te maken van zero knowledge proofs. Hiermee wordt het mogelijk om de risico’s van getallen die niet geheel random zijn en replay attacks te elimineren. Persistent geheugen is dan niet meer nodig, en het MuSig-protocol gaat van drie rondes naar twee. We zijn enthousiast over deze mogelijkheid, en kijken ernaar uit om onze resultaten te delen zodra we verder zijn in de ontwikkeling.
Onze code is publiekelijk in te zien op GitHub en we hopen dat mensen ermee aan de haal gaan en feedback geven!