Merklized Abstract Syntax Tree

Merklized Abstract Syntax Trees (MAST) is een voorgestelde toevoeging/verbetering voor Bitcoin die kleinere transactieformaten, meer privacy en grotere slimme contracten mogelijk maakt. Op deze pagina zullen we de basisprincipes van MAST in kaart brengen, de potentiële voordelen ervan beschrijven en een paar van de huidige voorstellen samenvatten om het aan het Bitcoin-protocol toe te voegen.

Het probleem: unused script data

Satoshi Nakamoto gaf Bitcoin een interessante functie die niet werd beschreven in de originele whitepaper. In plaats van te vereisen dat bitcoins worden ontvangen op een openbare sleutel en uitgegeven met een digitale handtekening, gaf Nakamoto gebruikers de mogelijkheid om programma’s (genaamd scripts) te schrijven die als dynamische openbare sleutels en handtekeningen zouden fungeren.

Wanneer je een script opgeeft – wat de standaard is in elke portemonnee – zal het door consensus afgedwongen Bitcoin-protocol niet toestaan dat iemand jouw bitcoins uitgeeft, tenzij het script True retourneert. Hiermee kun je beperkingen opgeven, zogenaamde encumbrances (bezwaren), zoals dat de uitgavenverrichting moet worden ondertekend door jouw privésleutel.

Complexere bezwaren zijn ook mogelijk, zoals het volgende voorbeeld dat we in dit artikel zullen gebruiken: Alice wil haar bitcoins op elk moment kunnen uitgeven, maar als haar bitcoins niet binnen drie maanden worden uitgegeven (misschien omdat ze dood of arbeidsongeschikt), wil ze dat haar broers en zussen, Bob en Charlie, haar bitcoins hebben, zolang ze het maar eens zijn over waar ze ze kunnen uitgeven.

Het bezwaringsscript hieronder geeft het beleid aan dat hierboven is beschreven en omvat niet alleen de openbare sleutel van Alice (nodig om een handtekening van haar privésleutel te verifiëren), maar ook een voorwaardelijke logica, een time-out en de openbare sleutels voor zowel Bob als Charlie.

In het huidige Bitcoin-protocol moeten alle bovenstaande gegevens aan de blockchain worden toegevoegd wanneer de bitcoins van Alice worden uitgegeven. Dat omvat de delen van het script die niet worden gebruikt in een bepaalde uitgave, zoals de openbare sleutels van Bob en Charlie, wanneer Alice haar eigen bitcoins uitgeeft.

Ongebruikte bezwaringsgegevens vergroten de omvang van transacties, verminderen de privacy door meer informatie openbaar te maken dan nodig is en beperken in de eerste plaats intelligente contracten naar hun grootte in plaats van naar hun validatiekosten. MAST probeert deze situatie te verbeteren door de noodzaak weg te nemen om ongebruikte delen van een script direct in de blockchain te registreren.

De oorsprong van MAST

Het idee achter MAST is afkomstig van twee reeds bestaande concepten, abstracte syntaxisbomen en merkle-bomen. (AST’s) zijn een manier om een programma te beschrijven door het op te splitsen in de afzonderlijke delen, waardoor het gemakkelijker te analyseren en optimaliseren is. Om een AST te genereren, verbindt je elke functie met zijn afhankelijkheden totdat alle afhankelijkheden zijn toegewezen. Hier is een AST voor de hierboven beschreven voorbeeldbelemmering:

Aan de andere kant kun je met Merkle-bomen controleren of een afzonderlijk element deel uitmaakt van een set zonder dat de hele set aanwezig is. Bitcoin SPV-portefeuilles maken bijvoorbeeld gebruik van merkle-trees om bandbreedte te besparen door te verifiëren dat individuele ontvangen transacties lid zijn van een blok zonder het volledige blok te downloaden.

Om een merkle-boom te genereren, wordt elk lid individueel gehasht, waardoor een korte unieke identificatie voor dat lid wordt geproduceerd. Elk van die identifiers wordt dan gepaard met een andere identifier en opnieuw gehashed, waardoor een andere korte unieke identifier voor dat paar wordt geproduceerd. Deze stap wordt herhaald totdat slechts één identifier overblijft, de merkle-root, die op unieke wijze de hele set identificeert in slechts een paar bytes aan gegevens.

Om te controleren of een bepaald lid deel uitmaakt van de set, geeft iemand met de hele set alleen de ID’s die je nodig hebt om dat specifieke lid te verbinden met de merkle-root van de hele set. Dit bewijs dat het lid tot de set behoort, wordt een merkle proof (merklebewijs) genoemd.

Kortom, de techniek achter AST’s stelt ons in staat een programma op te splitsen in zijn individuele delen, en merkle-trees laten ons toe om te verifiëren dat de afzonderlijke delen tot een compleet programma behoren zonder dat het volledige programma aanwezig is. Dit is de basis van MAST, waarmee verkopers de ongebruikte delen van bezwaringen kunnen vervangen door een merklebewijs, waardoor de transactiegrootte wordt verkleind, privacy wordt vergroot en grotere slimme contracten mogelijk worden gemaakt.

Een voorbeeld van MAST

Laten we ons voorbeeld van eerder nemen en deze opsplitsen in afzonderlijke subscripts voor elk van de twee mogelijke resultaten die we toestaan:

  1. Alice kan haar bitcoins op elk moment uitgeven (linksonder)
  2. Of, Alice haar bitcoins zijn drie maanden niet uitgegeven, Bob en Charlie kunnen afspreken waar ze de bitcoins van Alice aan kunnen uitgegeven (rechtsonder)

Laten we een maken op basis van deze twee onafhankelijke subscripts:

De merkle-root voor deze tree identificeert op unieke wijze Alice’s volledige bezwaring in slechts 32 bytes aan data. Alice gebruikt vervolgens een vervangende bezwaring die zegt dat een spender een merklebewijs moet leveren dat de merkle-root verbindt met een van de subscripts en dat het subscript True moet retourneren

Het merkle-bewijs met sub-script kan worden gevisualiseerd zoals een van de onderstaande voorbeelden, afhankelijk van welk subscript we wilden gebruiken:

Voordeel # 1 – kleinere transacties

Laten we beginnen met ons onderzoek naar de voordelen van MAST door na te gaan hoe het gebruikers van complexe bezwaren in staat stelt om kleinere transacties te creëren.

In het bovenstaande voorbeeld gebruikten we een bezwaring met twee subscripts: Alice besteedde haar geld, of Bob en Charlie wachtten drie maanden en gaven het geld zelf uit. Laten we ons een oneindig uitbreidbare versie hiervan voorstellen waarin een derde subscript zegt dat Dan en Edith na drie maanden en één dag de fondsen kunnen uitgeven; of een vierde deelschrift zegt dat Fred en George na drie maanden en twee dagen geld kunnen uitgeven; etc.

Dit geeft ons de mogelijkheid om de volgende eenvoudige plot te maken die het aantal sub-scripts laat zien en hoeveel bezwaring data moet worden toegevoegd aan de blockchain met en zonder MAST om dat mogelijk te maken.

Hier is dezelfde plot in logschaal:

Hoewel MAST iets duurder begint dan hetzelfde voorbeeldscript zonder MAST voor slechts twee subscripts, neemt niet-MAST lineair toe met de kosten, terwijl MAST alleen logaritmisch toeneemt.

Als het besparen van bytes het primaire doel is, kan dit verder worden geoptimaliseerd. Voor veel bezwaren is het waarschijnlijker dat uitgevers één voorwaarde gebruiken dan de anderen. Alice hoopt bijvoorbeeld heel lang te leven, dus bouwt ze haar merkle-boom, zodat haar bestedingsconditie altijd bovenaan staat en alle andere omstandigheden op de bodem liggen.

Dit geeft ons twee verschillende maten voor het MAST-merklebewijs, een voor het beste geval waarin Alice leeft en haar bitcoins uitgeeft, en een voor de andere gevallen waarin Alice dood is en haar begunstigden haar bitcoins uitgeven; laten we die maten op de vorige plot weergeven.

We kunnen zien dat Alice nu altijd hetzelfde aantal bytes gebruikt, ongeacht hoeveel potentiële begunstigden ze aan haar bezwaring toevoegt, en dat de andere potentiële spenders slechts een paar meer bytes gebruiken dan het vorige normale geval.

Welke regeling Alice ook kiest, we zien dat MAST bezuinigingen met meerdere sub-scripts veel kleiner kan maken, waardoor de transactiegrootte wordt verminderd, zodat gebruikers minder aan vergoedingen kunnen betalen en blokken een groter aantal geavanceerde transacties kunnen bevatten.

Voordeel # 2 – meer privacy

Omdat we het hele verhaal van Alice uitvoerig hebben behandeld in dit artikel, ken je alle details van de bezwaring, maar stel je voor dat je alleen de gegevens hebt gezien die daadwerkelijk aan de blokketting zijn toegevoegd toen Alice haar bitcoins gebruikte (hieronder, links voorbeeld):

Met alleen deze informatie zou je niet weten of iemand anders dan Alice toegang zou hebben tot het geld of welke voorwaarden hun uitgaven zouden kunnen beperken. Je zou kunnen raden aan de hand van MAST dat er andere omstandigheden waren, maar dat zou maar een gok zijn – Alice zou net kunnen doen alsof ze andere bestedbare delen van haar merkleboom had.

Als alternatief, als alles wat je zag de andere branche was (hierboven, het goede voorbeeld), zou je niet weten dat de fondsen vóór de time-out konden worden besteed of dat een enkele persoon (Alice) ze kon uitgeven. Nogmaals, je zou kunnen raden dat er andere omstandigheden waren, maar je kon niet zeker zijn alleen door naar de blokkeerketen te kijken.

Het vermogen om privé ongebruikte bezwaringsvoorwaarden te houden kan voor sommige gebruikers erg belangrijk zijn, zoals bedrijven die hun slimme contractafspraken zo vertrouwelijk mogelijk willen houden voor potentiële concurrenten. Dit staat in contrast met sommige altcoins die beweren dat ze specifiek zijn ontworpen voor slimme contracten, maar die geen privacy bieden voor welk deel van die contracten dan ook.

Privacy kan ook een ander voordeel bieden dat van toepassing is op alle Bitcoin-gebruikers, zelfs degenen die zich niet druk maken om de privacy van bezwaringen. Stel je voor dat Alice de enige persoon is die ooit het niet-MAST-bezettingssjabloon uit het eerste deel van dit artikel gebruikt. Omdat de volledige bezwaring openbaar is, kan iedereen alle uitgaven van Alice volgen door alleen te zoeken naar gevallen waarin die sjabloon wordt gebruikt, waardoor de privacy van Alice wordt vernietigd.

Alles wat het gemakkelijk maakt om bepaalde gebruikers te identificeren, maakt het ook gemakkelijk om hun bitcoins anders te behandelen dan de bitcoins van andere mensen, een gebrek aan fungibiliteit. Als iemand weet hoe Alice’s bezittingen eruit zien, kunnen ze miners omkopen of dwingen die transacties niet te delven om te voorkomen dat Alice haar bitcoins zou uitgeven.

MAST alleen kan dit niet volledig oplossen, omdat Alice (of Bob en Charlie) nog steeds een deel van de bezwaring moeten onthullen wanneer de bitcoins van Alice worden uitgegeven, maar het is mogelijk dat veel verschillende complexe bezwaren kunnen worden opgelost tot een kleiner aantal eenvoudige MAST -stijlen.

Bijvoorbeeld: de uitgaven van Alice zien eruit als de standaarduitgaven voor elke transactie waarvoor slechts één handtekening vereist is, zodat de op MAST gebaseerde transacties van Alice passen in andere op MAST gebaseerde transacties met één handtekening. Dit geeft de privacy van Alice terug en vergroot zowel haar fungibiliteit als de fungibiliteit van iedereen die MAST-gebaseerde bezwaren gebruikt die door een enkele handtekening kunnen worden voldaan.

Dit specifieke voordeel van MAST zal waarschijnlijk goed combineren met andere voorgestelde functies die de privacy en fungibiliteit voor Bitcoin-gebruikers verbeteren door bepaalde complexe bezwaren te laten voldoen aan een enkele digitale handtekening, bijvoorbeeld de generalized threshold trees van Pieter Wuille en Gregory Maxwell, scriptless scripts van Andrew Poelstra en de discrete log contracts van Thaddeus Dryja.

Maar zelfs als niets van die dingen ooit mogelijk wordt op Bitcoin, biedt MAST zelf gebruikers meer privacy en meer fungibiliteit voor geavanceerde bezwaren dan ze vandaag kunnen krijgen op elke altcoin die slimme contracten ondersteunt door middel van door de gebruiker gespecificeerde bezwaren.

Voordeel # 3 – grotere en slimme contracten

Bitcoin heeft drie verschillende bytegrootte limieten die van toepassing zijn op individuele scripts, afhankelijk van hoe de bezwaring is geconstrueerd: een limiet van 10.000 bytes toegevoegd in juli 2010 voor bare scripts, een 520-byte limiet voor P2SH en een limiet van 10.000 bytes voor segwit . Laten we deze drempels over elkaar leggen op de maattabel die we eerder hebben gebruikt.

We kunnen zien dat MAST, zelfs voor ons basale, oneindig uitbreidbare voorbeeld, het mogelijk maakt om veel meer voorwaardelijke vertakkingen te hebben dan zou worden toegestaan met behulp van enig ander huidig mechanisme. Inderdaad, MAST schalen zo goed dat als je tot je beschikking had alle energie geloofde te bestaan in het hele waarneembare universum, je alleen een gebalanceerde merkle boom kon creëren waarvan het merkle bewijs ongeveer 8.448 bytes groot zou zijn. Maar zelfs een merkle-bewijs van die omvang zou in minder dan een milliseconde gevalideerd kunnen worden door een volledig knooppunt op een moderne laptop.

Er zijn andere limieten die ook van toepassing zijn op Bitcoin-scripts die door MAST kunnen worden omzeild omdat niet-volledige knooppunten ongebruikte subscripts verwerken. In dit opzicht behoudt MAST op lovenswaardige wijze een lang gekoesterde ontwerpdoelstelling van slimme Bitcoin-contracten, wat inhoudt dat de contractbelasting zoveel mogelijk moet worden gelegd op de contractdeelnemers en dat netwerkknooppunten waarvan het gebruik van bandbreedte, geheugen en de verwerkingskracht die niet gecompenseerd wordt, moet zo min mogelijk belast worden.

De echte prestatie van MAST is dus niet dat het Bitcoin-gebruikers toestaat geavanceerdere slimme contracten te maken dan voorheen, maar dat het dit doet zonder nieuwe Bitcoin-knooppunten in het ergste geval te veroorzaken.

MAST mogelijk maken

Tot nu toe zijn er twee methoden voorgesteld op de bitcoin-dev mailinglijst voor het mogelijk maken van MAST in het Bitcoin Protocol, die beide nog steeds conceptvoorstellen zijn, onderhevig aan verandering.

Het eerste voorstel is BIP114 van Johnson Lau, dat gebruik maakt van een op SegWit gebaseerde uitbreidingsfunctie waarmee native segwit-adressen (bech32) zich kunnen binden aan de merkle-root van een MAST-bezwaring. Spenders kunnen vervolgens één enkel subscript uit de structuur selecteren.

Het tweede voorstel is twee nog niet genummerde BIP’s (1, 2) van Mark Friedenbach (maaku), die de flexibiliteit van de Script-taal op een zodanige manier vergroten dat programmeurs scripts kunnen schrijven die zelf MAST-gebaseerde bezwaren kunnen valideren. Indien geïmplementeerd op Friedenbachs voorkeursmanier, zou dit het mogelijk maken om merkle-proofs te gebruiken in alle drie soorten scripts die momenteel worden ondersteund door Bitcoin (bare, P2SH en SegWit).

Beide voorstellen kunnen worden geïmplementeerd in Bitcoin met een zogenaamde soft fork.

Conclusie: wanneer krijgen we MAST?

Na het beschrijven van de voordelen van MAST en het kort vermelden van twee voorstellen die het beschikbaar zouden maken op Bitcoin, vraag je jezelf waarschijnlijk af wanneer je het kunt gebruiken. Helaas weet ik het niet.

De weg van idee, naar voorstel, naar volledige implementatie, naar voorgestelde soft fork, naar geactiveerde soft fork is niet eenvoudig. Ik denk dat de twee jaren van drama rondom SegWit dat duidelijk maakten.

Maar het lijkt mij dat het basisidee achter MAST iets is dat sterke steun heeft van de Bitcoin technische gemeenschap, en dat de ontwikkelaars die het meest geïnteresseerd zijn in MAST eraan zullen blijven werken, tenzij is bewezen dat het volledig onhoudbaar is. Mochten die ontwikkelaars erin slagen peer-reviewed soft-fork-ready code te produceren, dan is het aan de lezers van dit artikel en andere Bitcoin-gebruikers om te beslissen of MAST deel gaat uitmaken van het Bitcoin-protocol.

Verder lezen

Bovenstaande tekst is een vertaling van het artikel “What is a Bitcoin Merklized Abstract Syntax Tree (MAST)?” geschreven door David A. Harding.