Merkalized Abstract Syntax Tree (MAST, deel 1)

Wat is een Merkalized Abstract Syntax Tree (MAST)?

Merkalized Abstract Syntax Tree (MAST) is een geopperde toevoeging aan het bitcoinprotocol welke zorgt voor een kleinere transactiegrootte, verbeterde privacy en de mogelijkheid tot grotere smart contracts. In dit artikel zal de basis van MAST worden uitgelegd.

Het probleem: ongebruikte script data

Satoshi Nakamoto gaf Bitcoin een interessante mogelijkheid mee die niet werd beschreven in de oorspronkelijke whitepaper. In plaats van alleen de mogelijkheid om bitcoins te ontvangen op een public key en vervolgens weer te verzenden op basis van een digitale handtekening, heeft Satoshi ook de mogelijkheid gecreëerd om programmaÂs te schrijven (scripts) die als dynamische public keys en handtekeningen zouden kunnen dienen.

Wanneer binnen een transactie zo'n script gebruikt wordt, laat het Bitcoinprotocol de bitcoins niet verzenden totdat de waarde van het script als 'correct' gezien wordt. Er kunnen in het script bijvoorbeeld bepaalde restricties worden opgelegd voor het verzenden van bitcoins. Wanneer aan alle restricties is voldaan, wordt het script gezien als 'correct' en kunnen de bitcoins verzonden worden. Zulke restricties worden encumbrances genoemd. Een voorbeeld hiervan is het onderschrijven van een transactie met de private key; het ondertekenen met een digitale handtekening om de bitcoins te mogen verzenden.

Doordat deze restricties, de encumbrances, zelf te programmeren zijn, is het ook mogelijk om meer complexe voorwaarden te creëeren. Een voorbeeld hiervan wordt middels een casus met Alice, Bob en Charlie in dit artikel uitgelegd.

De casus

Alice wil haar bitcoins op elk moment kunnen besteden. Wanneer er gedurende drie maanden niets met haar bitcoins gebeurt, om wat voor reden dan ook, dat de bitcoins dan naar haar broers Bob en Charlie gaan. Dit met de voorwaarden dat beide broers samen overeenstemmen waar de bitcoins aan besteed worden.

In het onderstaande encumbrances script wordt het hiervoor genoemde scenario toegepast. Hierin staat de public key van Alice opgenomen om de handtekening, gemaakt met een private key, te verifiëren. Ook de conditionele logica, een time-out en de public keys van Bob en Charlie, staan hierin vermeld.

In het huidige bitcoinprotocol wordt alle bovenstaande data toegevoegd aan de blockchain wanneer de bitcoins van Alice worden verzonden. Dit is dus inclusief de public keys van Bob en Charlie, die bij het verzenden van de bitcoins door Alice helemaal niet relevant zijn. Dit is dus extra en onnodige data die wereldwijd wordt opgeslagen.Deze ongebruikte encumbrance data zorgt ervoor dat de transactiegrootte zelf ook hoger uitvalt.

Ook de privacy van anderen loopt een deuk op; de publieke keys van Bob en Charlie worden immers bij elke transactie van Alice onnodig kenbaar gemaakt. Doordat er niet oneindig data aan de scriptfunctie van Bitcoin kan worden toegevoegd, zorgt dit ervoor dat er minder ruimte overblijft voor andere scriptfunctionaliteiten binnen de transactie.

Hier komt MAST om de hoek kijken. MAST zorgt ervoor dat de ongebruikte delen van het script niet in de blockchain opgenomen hoeven te worden.

Oorsprong MAST

Het idee achter MAST komt voort uit twee losstaande concepten, namelijk abstract syntax trees (ASTs) en merkle trees. AST is een manier waarop een programma beschreven kan worden door het in stukken te hakken. Elk los onderdeel kan zo eenvoudiger geanalyseerd of aangepast worden, zonder dat het hele programma daarvoor op de schop hoeft. Om een AST te generen dien je in het programmeren bekende functies en dependencies aan elkaar te verbinden, totdat alle dependencies in kaart zijn gebracht.

Hier volgt de AST op basis van de casus:

Merkle trees zorgen er aan de andere kant voor dat een deel van een geheel te verifiëren is zonder dat het geheel zelf aanwezig is. Zo maken SPV bitcoinwallets gebruik van merkle trees zodat deze niet de gehele blockchain met bijbehorende blocks hoeven te downloaden, maar slechts controleren of transacties daadwerkelijk in een block zijn opgenomen.

Om een merkle tree te genereren, dient elk deel van het geheel gehasht te worden, waardoor elk deel afzonderlijk te identificeren is aan de hand van een unieke reeks karakters. Deze identificatiereeksen worden vervolgens samengevoegd en weer gehasht, waardoor er een kortere hash ontstaat voor de twee aparte reeksen samen. Dit wordt gedaan totdat er nog maar één identificatiereeks is voor alle voorgaande delen; de merkle root. Er is dus slechts een kleine hoeveelheid data nodig (de identificatiereeks is slechts een paar bytes groot) om het geheel te verifiëren.

Doordat dus niet de gehele blockchain gecontroleerd wordt, moet er vertrouwd worden op een externe partij die jou de juiste identificatiereeksen kan overhandigen. Zonder die reeksen kan er namelijk niet gecontroleerd worden of een deel daadwerkelijk onderdeel is van het geheel. Met de identificatiereeksen kun je namelijk weer uitkomen bij de merkle root van het geheel. Het aantonen dat een deel onderdeel is van een geheel wordt merkle proof genoemd.

In het kort kan de techniek achter AST ervoor zorgen dat een programma in individuele delen gesplitst kan worden. De merkle tree maakt het mogelijk om individuele delen van een compleet programma te verifiëren zonder dat het gehele programma aanwezig hoeft te zijn. Dit is het idee achter MAST; een zender van een transactie kan de ongebruikte delen van een encumbrance vervangen door een merkle proof die de transactiegrootte verkleint wordt, de privacy verhoogt en grotere smart contracts mogelijk maakt.

Voorbeeld en voordelen

In een tweede artikel zal MAST aan de hand van een voorbeeld worden toegelicht en zullen er een aantal voordelen van de upgrade worden besproken. Dit artikel is geschreven op basis van een artikel gepubliceerd door David A. Harding. David publiceert documentatie van gratis software en is sinds 2014 gefocust op Bitcoin.