Trying out MAST (Merkelized Abstract Syntax Trees)

2021–12–20 update: this code is obsolete in favor of https://github.com/bitcoin-core/btcdeb/blob/master/doc/tapscript-example-with-tap.md (etc).

MAST has been given a lot of attention recently, and pull requests (here and here) to the Bitcoin Core repository for implementing a version of MAST written by Mark Friedenbach were opened recently.

What is it?

MAST theory is explained in great detail elsewhere, such as this great post by Mark Friedenbach to the bitcoin mailing list or this post on hackernoon about using MAST in atomic swaps, but I’ll give a short primer here. This article focuses on hands-on testing of MAST, and the target audience is someone with a developer background.

When you write a program, you often check for, and react to, various conditions. In a regular situation, this might be something like:

if (logged_in) {
    render(dashboard_page);
} else {
    redirect(login_page);
}

In Bitcoin Script, it might be a timeout for a lightning channel:

OP_IF
144
OP_CHECKSEQUENCEVERIFY
OP_DROP
<PUBKEY-Bob>
OP_ELSE
<secret>
OP_ENDIF
OP_CHECKSIG

MAST lets you take a script like the one above, and converting it into a merkle tree, where each hash is the hash of the resulting script when taking one of the paths. For the above channel closure script, there are two possible paths:

144
OP_CHECKSEQUENCEVERIFY
OP_DROP
<PUBKEY-Bob>
OP_CHECKSIG

And:

<secret>
OP_CHECKSIG

We can turn the two paths above into two hashes and make a merkle tree out of them. That may not look very impressive, until you realize you can do this with arbitrarily large scripts, and it will always compress down to a single hash, plus the code for the path that was taken.

Generally speaking, we sometimes need to ensure that a path we entered was actually valid. Unnecessary in this case, because the signer provides the input to the IF conditional, but in cases where we care, we would sprinkle these at the path points in the “flattened” script versions:

OP_NOT
OP_0 (for OP_IF; OP_1 for OP_ELSE)
OP_EQUAL

Getting started

MAST is not in Bitcoin yet, but you can try it out using the Bitcoin Script debugger written by yours truly. From command line on a linux or mac machine, cd to some good place (like workspace or so) and:

git clone https://github.com/kallewoof/btcdeb.git
cd btcdeb
./autogen.sh
./configure
make

You can optionally do make install as well (may need to prepend with sudo) and use <command> for the tools, but I am skipping that here. Instead I am referring to the commands as ./<command>.

First example (no MAST)

Our first example doesn’t use MAST at all, but we build on it in the next sections.

Our script will take an input value, and then check if it equals to 1.

OP_1
OP_EQUAL

Note that this is completely unsafe in practice. Normally you would require signatures and such, but I am doing it this way to avoid having to juggle private and public keys and such. Do not use with actual bitcoins!

We can try this out:

./btcdeb '[01 OP_EQUAL]' 01
btcdeb -- type `./btcdeb -h` for start up options
valid script
2 op script loaded. type `help` for usage information
script   |  stack
---------+--------
1        |      01
OP_EQUAL |
#0001 1
btcdeb> step
  <> PUSH stack 01
script   |  stack
---------+--------
OP_EQUAL |      01
         |      01
#0002 OP_EQUAL
btcdeb>
  <> POP  stack
  <> POP  stack
  <> PUSH stack 01
script   |  stack
---------+--------
         |      01

Brief note on the syntax for btcdeb: you can pass in scripts by wrapping them in quotes and brackets, i.e. '[content]'. This is exactly the same as passing the script output from btcc, when passing content. In this case, 0x5187.

If you try it and change the last argument, 01, to something else, e.g. 02, you will get a zero after the OP_EQUAL execution.

From here on, think of this as a good old signature checking script like you see with normal transactions. This is a grave simplification, as stated above.

Second example (MAST, with a single node)

We’ll now stuff this script into a MAST-enabled version. It will not make much sense, yet, because we only have one script. In the third example, we will add more, so bear with me a bit.

Firstly, we need to add an extra step: any arguments into the script have to be temporarily pushed onto the altstack, and then popped out again. I explain why in the Gorey details section at the bottom. Our script becomes:

OP_FROMALTSTACK
OP_1
OP_EQUAL

Secondly, we need some stuff, such as the hash of this script (that’ll be our merkle root). btcdeb has a transform tool that we can use to get this:

btcdeb> tf hash256 FROMALTSTACK OP_1 OP_EQUAL
9e2232a0e2a41073464bdd218fa4ae9221b20ce93af704dceb0db1a0aa253fed

Next, we need a proof. Because this tree is the hash itself with no leaves, we actually end up with a proof that proves nothing — the verify code will simply check that the hash of the root is the hash of the script itself. The proof becomes 0000. (Four zeroes, in hexadecimal form.)

Finally, we need to take the hash we got, and wrap it into a script that does the merkle branch verify part. This script looks like this:

OP_TOALTSTACK
9e2232a0e2a41073464bdd218fa4ae9221b20ce93af704dceb0db1a0aa253fed
OP_2
OP_MERKLEBRANCHVERIFY
OP_2DROP
OP_DROP

• The first line matches the FROMALTSTACK in our new script above.
• The next line is the hash256 we generated with tf before.
• The next line is basically always OP_2 for now. (It describes the number of items being used in the merkle tree verification; this is our OP_FROMALTSTACK OP_1 OP_EQUAL script, and those will almost always just be one.)
• Next we perform the actual merkle branch verification, and after this we drop 3 items from the stack — the 3 items used in the verification itself.

You may wonder about that last part; it’s basically so that old nodes, that don’t know how to do merkle branch verification, will accept the script as valid. They won’t validate it, but they’ll accept it, which is all we need. This is also how OP_CHECKSEQUENCEVERIFY works.

Sidenote: if we had two inputs to our script (such as a signature and a pubkey), we would have two FROMALTSTACK entries and two corresponding TOALTSTACK entries. This would repeat for the number of arguments.

Let’s wrap this all up and try it in the debugger. To recap:

• Our input script is TOALTSTACK 9e2232a0e2a41073464bdd218fa4ae9221b20ce93af704dceb0db1a0aa253fed OP_2 MERKLEBRANCHVERIFY 2DROP DROP
• Our parameter (the signing part) is the script itself:FROMALTSTACK OP_1 EQUAL
• And our proof is 0000
• And our input (answer) to the actual inner script, which is 01

This converts into the following, rather longish call to btcdeb:

./btcdeb '[TOALTSTACK 9e2232a0e2a41073464bdd218fa4ae9221b20ce93af704dceb0db1a0aa253fed OP_2 MERKLEBRANCHVERIFY 2DROP DROP]' '[FROMALTSTACK OP_1 EQUAL]' 0000 01

We will get an initial state that looks like this:

script                           |  stack
---------------------------------+--------
OP_TOALTSTACK                    |      01
9e2232a0e2a41073464bdd218fa4a... |    0000
2                                |  6c5188
OP_MERKLEBRANCHVERIFY            |
OP_2DROP                         |
OP_DROP                          |
#0001 OP_TOALTSTACK

The step command lets us iterate down into the script. I will describe what happens at each step; run step each time and check that it matches what I’m describing:

• The stack has our “answer” (1) to the question (what is equal to 1) at the top. We start by putting that into the altstack. You can check the content of the altstack with the altstack command.
• Next up, we put the hash256 of the script (the merkle root) as well as the 2 above on the stack, for the merkle branch verify operation.
• Now we call OP_MERKLEBRANCHVERIFY. It will use the merkle root, and generate and compare a root based on the proof (0000) and input script (6c5187) with the given merkle root. In this case, that’s all it does.
• Next we drop the hash256, the 2, and the proof from the stack; we are left with the input script and nothing in the script side.

If you step again now, the tail eval functionality will be triggered; the input script (on the stack) will be transferred and be interpreted as a script (in the script side). It should look like this:

script                            |                            stack
----------------------------------+---------------------------------
                                  |                           6c5187
btcdeb> step
  <> POP  stack
script                            |                            stack
----------------------------------+---------------------------------
OP_FROMALTSTACK                   |
1                                 |
OP_EQUAL                          |

From here on, the script will execute as a regular script.

• It pulls the input (01) from the altstack back into the stack.
• It pushes the compared value (also 01) onto the stack.
• It calls OP_EQUAL, which pushes a 1 or 0 to the stack depending on whether the two values are the same or not. If you provided something other than 01 into the script, it would give a 0.

I recommend that you try to change the hash256 value, or the input script, or the proof, to see if the merkle branch verify call fails. If it does, it should convince you that the script is, indeed, locked to a subset of scripts (currently only 1), and that it won’t accept just any script you throw at it!

Third example (an actual merkle tree)

We’ll now expand to a set of scripts — I’ve arbitrarily opted for 5 scripts in this case, but you can do a hundred or ten thousand if you want.

My scripts are the same as above, except the second script does OP_2 OP_EQUAL, the third one does OP_3 OP_EQUAL, and so on. That is, my five scripts look like this:

OP_FROMALTSTACK OP_1 OP_EQUAL
OP_FROMALTSTACK OP_2 OP_EQUAL
OP_FROMALTSTACK OP_3 OP_EQUAL
OP_FROMALTSTACK OP_4 OP_EQUAL
OP_FROMALTSTACK OP_5 OP_EQUAL

To pull this off, we need to use a new tool that is in the btcdeb toolkit, called merklebranch. It lets us create merkle trees based on inputs, and it also lets us create proofs. We’ll begin by making a tree from the five scripts.

./merklebranch '[FROMALTSTACK OP_1 EQUAL]' '[FROMALTSTACK OP_2 EQUAL]' '[FROMALTSTACK OP_3 EQUAL]' '[FROMALTSTACK OP_4 EQUAL]' '[FROMALTSTACK OP_5 EQUAL]'
root: 4cae2f5573c5728f37f1a610ff01f8f4adba6474e71d5a50c1354292d04e74a4

We’ll now make the “funding” part, which only needs the merkle root. This looks very similar to what we had before, in fact, it is identical, except for the merkle root having changed.

TOALTSTACK
a4744ed0924235c1505a1de77464baadf4f801ff10a6f1378f72c573552fae4c
OP_2
MERKLEBRANCHVERIFY
2DROP
DROP

Now we’ll pick a script to use for redeeming. I’m going for number 4, but you go for a different one if you’d like. This is 0-index based, though, so you want to subtract 1 from your index (in my case, I want position 3):

./merklebranch --position=3 '[FROMALTSTACK OP_1 EQUAL]' '[FROMALTSTACK OP_2 EQUAL]' '[FROMALTSTACK OP_3 EQUAL]' '[FROMALTSTACK OP_4 EQUAL]' '[FROMALTSTACK OP_5 EQUAL]'
root: 4cae2f5573c5728f37f1a610ff01f8f4adba6474e71d5a50c1354292d04e74a4
branch: [
 1d3b5bad759a6eeeb8e48dfcfc1b7b802a7256ec87a7b2e2c04d54c56487a22a
 90658083c0751863dceb7f8874f170be082c70c8b282b7df2c0c56598885e64d
 256836c0cb68f9f3189cfff8e5f033ea7a5ee32148f377405e0971036c950f80
]
path: 3
proof: 037f000390658083c0751863dceb7f8874f170be082c70c8b282b7df2c0c56598885e64d1d3b5bad759a6eeeb8e48dfcfc1b7b802a7256ec87a7b2e2c04d54c56487a22a256836c0cb68f9f3189cfff8e5f033ea7a5ee32148f377405e0971036c950f80
unlocking proposal (1 parameter):
- script:       TOALTSTACK 4cae2f5573c5728f37f1a610ff01f8f4adba6474e71d5a50c1354292d04e74a4 OP_2 OP_MERKLEBRANCHVERIFY 2DROP DROP
- script (hex): 6b204cae2f5573c5728f37f1a610ff01f8f4adba6474e71d5a50c1354292d04e74a452b36d75
stack:
- item #1:       [FROMALTSTACK OP_4 EQUAL]
- item #1 (hex): 6c5487
- item #2:       037f000390658083c0751863dceb7f8874f170be082c70c8b282b7df2c0c56598885e64d1d3b5bad759a6eeeb8e48dfcfc1b7b802a7256ec87a7b2e2c04d54c56487a22a256836c0cb68f9f3189cfff8e5f033ea7a5ee32148f377405e0971036c950f80
- item #3+:      (argument to script at item #1)

We get some new stuff when we include a position. The thing we care about is the proof, the 100 byte (200 hex character) long blob at the end. We can now make the spending part. Our initial stack will consist of three parts: the script we decided to use, the proof showing that the script is in the merkle tree, and our argument (which is 04 here, because that is what equals to 4):

[FROMALTSTACK OP_4 EQUAL]
(proof)
04

Slapping it all together, we get the following btcdeb call:

./btcdeb '[TOALTSTACK 4cae2f5573c5728f37f1a610ff01f8f4adba6474e71d5a50c1354292d04e74a4 OP_2 MERKLEBRANCHVERIFY 2DROP DROP]' '[FROMALTSTACK OP_4 EQUAL]' 037f000390658083c0751863dceb7f8874f170be082c70c8b282b7df2c0c56598885e64d1d3b5bad759a6eeeb8e48dfcfc1b7b802a7256ec87a7b2e2c04d54c56487a22a256836c0cb68f9f3189cfff8e5f033ea7a5ee32148f377405e0971036c950f80 04

Run it through and make sure it runs through to the end, and try changing parameters and check that it fails, until you are convinced that it works as intended.

Using the mastify tool

There’s another tool in the btcdeb tool set called “mastify”. It lets you take a regular script as input, and it will convert it into a MAST version. Let’s see what the Lightning Network script mentioned at the beginning ends up as if we turn it into a MAST script. Since we can’t check signatures, we’ll tweak it so that the first case requires a 01 and the second case requires a 02.

OP_IF
144
OP_CHECKSEQUENCEVERIFY
OP_DROP
01
OP_ELSE
02
OP_ENDIF
OP_EQUAL

If we run this as normal, we can provide a 01 for the IF case, followed by a 01 for the equality check, or we can provide a 0x for the IF case and 02 for the equality check:

./btcdeb '[OP_IF 144 OP_CHECKSEQUENCEVERIFY OP_DROP 01 OP_ELSE 02 OP_ENDIF OP_EQUAL]' 01 01
# OR #
./btcdeb '[OP_IF 144 OP_CHECKSEQUENCEVERIFY OP_DROP 01 OP_ELSE 02 OP_ENDIF OP_EQUAL]' 02 0x

Let’s turn this into a MAST version. This is simply done by running mastify on the script itself, like so:

$ ./mastify '[OP_IF 144 OP_CHECKSEQUENCEVERIFY OP_DROP 01 OP_ELSE 02 OP_ENDIF OP_EQUAL]'
2 paths:
path #0 (2 arguments):
OP_FROMALTSTACK
OP_FROMALTSTACK
OP_VERIFY
9000
OP_CHECKSEQUENCEVERIFY
OP_DROP
1
OP_EQUAL
path #1 (2 arguments):
OP_FROMALTSTACK
OP_FROMALTSTACK
OP_NOT
OP_VERIFY
2
OP_EQUAL
path #0 proposal:
root: 7881572ae991d940eb786056331c1a5c987efb8720216ed1ebfc71863b755441
branch: [
 365f30a36fd9c447bb512a114c3f1b05a96c9221d596c93d09f096b34f452313
]
path: 0
proof: 010001365f30a36fd9c447bb512a114c3f1b05a96c9221d596c93d09f096b34f452313
unlocking script: TOALTSTACK TOALTSTACK 7881572ae991d940eb786056331c1a5c987efb8720216ed1ebfc71863b755441 OP_2 OP_MERKLEBRANCHVERIFY 2DROP DROP
- script (hex): 6b6b207881572ae991d940eb786056331c1a5c987efb8720216ed1ebfc71863b75544152b36d75
stack:
- item #1:  6c6c69029000b2755187
- item #2:  010001365f30a36fd9c447bb512a114c3f1b05a96c9221d596c93d09f096b34f452313
path #1 proposal:
root: 7881572ae991d940eb786056331c1a5c987efb8720216ed1ebfc71863b755441
branch: [
 9865a8e8b5a546d2c1e5ccb582b2a178e2ca9f39db089351a757db2cdb42fa36
]
path: 1
proof: 01c0019865a8e8b5a546d2c1e5ccb582b2a178e2ca9f39db089351a757db2cdb42fa36
unlocking script: TOALTSTACK TOALTSTACK 7881572ae991d940eb786056331c1a5c987efb8720216ed1ebfc71863b755441 OP_2 OP_MERKLEBRANCHVERIFY 2DROP DROP
- script (hex): 6b6b207881572ae991d940eb786056331c1a5c987efb8720216ed1ebfc71863b75544152b36d75
stack:
- item #1:  6c6c91695287
- item #2:  01c0019865a8e8b5a546d2c1e5ccb582b2a178e2ca9f39db089351a757db2cdb42fa36

It’s a bit verbose, but let’s break it down: first, we get a listing of the 2 possible paths that can be taken in this script. The OP_VERIFY replaces the OP_IF because we already know which case it is (this was selected from the tree, rather than at runtime). For the ELSE case, there’s an OP_NOT preceding the verify call, which turns a 1 into 0 and a 0 into 1 (it verifies that the top item on the stack is 0).

We then see two proposals for each path. Note that the root for both is the same, which it must be, as it is committed to before we spend it and we don’t pick a path until we spend.

If we call mastify with arguments, it will figure out the path, and will give us the spending parameters. Let’s try it with the second case (i.e. the else part, where the input is 2):

$ ./mastify '[OP_IF 144 OP_CHECKSEQUENCEVERIFY OP_DROP 01 OP_ELSE 02 OP_ENDIF OP_EQUAL]' 02 0x
switching to alternative path from idx=0 to idx=1
branch: [
 9865a8e8b5a546d2c1e5ccb582b2a178e2ca9f39db089351a757db2cdb42fa36
]
path: 1
proof: 01c0019865a8e8b5a546d2c1e5ccb582b2a178e2ca9f39db089351a757db2cdb42fa36
unlocking script: TOALTSTACK TOALTSTACK 7881572ae991d940eb786056331c1a5c987efb8720216ed1ebfc71863b755441 OP_2 OP_MERKLEBRANCHVERIFY 2DROP DROP
- script (hex): 6b6b207881572ae991d940eb786056331c1a5c987efb8720216ed1ebfc71863b75544152b36d75
- item #1:  6c6c91695287
- item #2:  01c0019865a8e8b5a546d2c1e5ccb582b2a178e2ca9f39db089351a757db2cdb42fa36
- argument: 0x02
- argument: 0x

The first line shows that the solution is using the second path (idx=1). The last portion shows the solution. We can pass this into btcdeb directly like this:

./btcdeb $(./mastify --btcdeb '[OP_IF 144 OP_CHECKSEQUENCEVERIFY OP_DROP 01 OP_ELSE 02 OP_ENDIF OP_EQUAL]' 02 0x)

Run that through to the end and see if it works. Also try changing the 02 0x to 01 01 (should use the first path and should succeed), and try combinations that should fail, such as 02 01 or 01 02 or anything else that you can come up with.

Multisig using MAST via mastify

Mastify also supports conversion of multisig into MAST. What it effectively does is take a k-of-n multisig and converting it into a series of k-of-k multisigs, for each possible combination. That is, if you have pubkeys abc in a 2-of-3 multisig, it will create combinations ab, ac, and bc. When we create the funding script, we use the --multisig=<k> parameter to tell mastify how many signatures are required (the k in k-of-n), followed by the pubkeys.

./mastify --multisig=2 \
0375e00eb72e29da82b89367947f29ef34afb75e8654f6ea368e0acdfd92976b7c \
03a1b26313f430c4b15bb1fdce663207659d8cac749a0e53d70eff01874496feff \
03c96d495bfdd5ba4145e3e046fee45e84a8a48ad05bd8dbb395c011a32cf9f880

It should give you 3 paths as described above.

When we want to spend the MAST multisig, we generate the signatures, and use = to tie each signature to its corresponding pubkey. E.g.

./mastify --multisig=2 \
0375e00eb72e29da82b89367947f29ef34afb75e8654f6ea368e0acdfd92976b7c \
03a1b26313f430c4b15bb1fdce663207659d8cac749a0e53d70eff01874496feff=3045022100c56ab2abb17fdf565417228763bc9f2940a6465042fd62fbd9f4c7406345d7f702201cb1a56b45181f8347713627b325ec5df48fc1aee6bdaf937cbb804d7409b10c01 \
03c96d495bfdd5ba4145e3e046fee45e84a8a48ad05bd8dbb395c011a32cf9f880=304402207f874ef00f11dcc9a621acad9354f3fca1bf90c43878f607b7e2d358088487e7022052a01b47b8eef5e1c96a6affdc3dac46fdc11b60612464dc8c5921a852090d2701

Gorey details — altstack use

There is a consensus rule called CLEANSTACK, which non-conforming nodes would consider violated if we used the regular stack directly. You can read more about this in BIP-117. To avoid having a “dirty” stack, we temporarily push stuff onto the altstack, and then pop them off right as we need them.

Alternatively we could have opted for increasing the script version in Segwit, removing the CLEANSTACK requirement for versions > 0, but this would add unnecessary complexity to the implementation process, so the current proposal opted to not go down this route (later, when version is actually bumped, this may be proposed as a part of it, though).