Bare multisig was the first attempt at creating transaction outputs that require signatures from multiple parties. The idea is to change from a single point of failure to something a little more resilient to hacks. To understand bare multisig, one must first understand the OP_CHECKMULTISIG opcode. As discussed in Chapter 6, Script has a lot of different opcodes. OP_CHECKMULTISIG is one of them, at 0xae. The opcode consumes a lot of elements from the stack and returns whether or not the required number of signatures are valid for a transaction input.

The transaction output is called “bare” multisig because it’s a long ScriptPubKey. Figure 8-1 shows what a ScriptPubKey for a 1-of-2 multisig looks like.

Figure 8-1. Bare multisig ScriptPubKey

Among bare multisig ScriptPubKeys, this one is on the small end, and we can already see that it’s long. The ScriptPubKey for p2pkh is only 25 bytes, whereas this bare multisig is 101 bytes (though obviously, compressed SEC format would reduce it some), and this is a 1-of-2! Figure 8-2 shows what the ScriptSig looks like.

Figure 8-2. Bare multisig ScriptSig

We only need 1 signature for this 1-of-2 multisig, so this is relatively short; something like a 5-of-7 would require 5 DER signatures and would be a lot longer (360 bytes or so). Figure 8-3 shows how the ScriptSig and ScriptPubKey combine.

Figure 8-3. Bare multisig combined script

I’ve generalized here to show what an m-of-n bare multisig would look like (m and n can be anything from 1 to 20 inclusive, though the numerical opcodes only go up to OP_16; values of 17 to 20 would require 0112 to push a number like 18 to the stack). The starting state looks like Figure 8-4.

Figure 8-4. Bare multisig start

OP_0 will push the number 0 to the stack (Figure 8-5).

Figure 8-5. Bare multisig step 1

The signatures are elements, so they’ll be pushed directly to the stack (Figure 8-6).

Figure 8-6. Bare multisig step 2

OP_m will push the number m to the stack, the public keys will be pushed to the stack, and OP_n will push the number n to the stack (Figure 8-7).

Figure 8-7. Bare multisig step 3

At this point, OP_CHECKMULTISIG will consume m + n + 3 elements (see OP_CHECKMULTISIG Off-by-One Bug) and push a 1 to the stack if m of the signatures are valid for m distinct public keys from the list of n public keys; otherwise, it pushes a 0. Assuming that the signatures are valid, the stack has a single 1, which validates the combined script (Figure 8-8).

Figure 8-8. Bare multisig end

Coding OP_CHECKMULTISIG

In an m-of-n bare multisig, the stack contains n as the top element, then n pubkeys, then m, then m signatures, and finally a filler item due to the off-by-one bug. The code for OP_CHECKMULTISIG in op.py is mostly written here:

def op_checkmultisig(stack, z):
    if len(stack) < 1:
        return False
    n = decode_num(stack.pop())
    if len(stack) < n + 1:
        return False
    sec_pubkeys = []
    for _ in range(n):
        sec_pubkeys.append(stack.pop())
    m = decode_num(stack.pop())
    if len(stack) < m + 1:
        return False
    der_signatures = []
    for _ in range(m):
        der_signatures.append(stack.pop()[:-1])  
    stack.pop()  
    try:
        raise NotImplementedError  
    except (ValueError, SyntaxError):
        return False
    return True

Each DER signature is assumed to be signed with SIGHASH_ALL.

We take care of the off-by-one error by consuming the top element of the stack and not doing anything with the element.

This is the part that you will need to code for the next exercise.

To mitigate these problems, pay-to-script-hash (p2sh) was born.

Pay-to-script-hash (p2sh) is a general solution to the long address/ScriptPubKey problem. More complicated ScriptPubKeys than bare multisig can easily be made, and they have the same problems as bare multisig.

In p2sh, a special rule gets executed only when the pattern shown in Figure 8-9 is encountered.

Figure 8-9. Pay-to-script-hash pattern (p2sh) that executes the special rule

If this exact command set ends with a 1 on the stack, then the RedeemScript (the top item in Figure 8-9) is parsed and then added to the Script command set. This special pattern was introduced in BIP0016, and Bitcoin software that implements BIP0016 (anything post 2011) checks for the pattern. The RedeemScript does not add new Script commands for processing unless this exact sequence is encountered and ends with a 1.

Let’s say we have a 2-of-2 multisig ScriptPubKey (Figure 8-10).

Figure 8-10. Pay-to-script-hash (p2sh) RedeemScript

This is a ScriptPubKey for a bare multisig. What we need to do to convert this to p2sh is to take a hash of this script and keep the script handy for when we want to redeem it. We call this the RedeemScript, because the script is only revealed during redemption. We put the hash of the RedeemScript as the ScriptPubKey (Figure 8-11).

Figure 8-11. Pay-to-script-hash (p2sh) ScriptPubKey

The hash digest here is the hash160 of the RedeemScript, or what was previously the ScriptPubKey. We’re locking the funds to the hash of the RedeemScript, which needs to be revealed at unlock time.

Creating the ScriptSig for a p2sh script involves not only revealing the RedeemScript, but also unlocking the RedeemScript. At this point, you might be wondering where the RedeemScript is stored. It’s not on the blockchain until actual redemption, so it must be stored by the creator of the p2sh address. If the RedeemScript is lost and cannot be reconstructed, the funds are lost, so it’s very important to keep track of it!

The ScriptSig for the 2-of-2 multisig looks like Figure 8-12.

Figure 8-12. Pay-to-script-hash (p2sh) ScriptSig

This produces the combined script in Figure 8-13.

Figure 8-13. p2sh combined script

As before, OP_0 is there because of the OP_CHECKMULTISIG bug. The key to understanding p2sh is the execution of the exact sequence shown in Figure 8-14.

Figure 8-14. p2sh pattern that executes the special rule

Upon execution of this sequence, if the stack is left with a 1, the RedeemScript is inserted into the Script command set. In other words, if we reveal a RedeemScript whose hash160 is the same as the hash160 in the ScriptPubKey, that RedeemScript acts like the ScriptPubKey instead. We hash the script that locks the funds and put that into the blockchain instead of the script itself. This is why we call this ScriptPubKey pay-to-script-hash.

Let’s go through exactly how this works. We start with the Script commands (Figure 8-15).

Figure 8-15. p2sh start

OP_0 will push a 0 to the stack, and the two signatures and the RedeemScript will be pushed to the stack directly, leading to Figure 8-16.

Figure 8-16. p2sh step 1

OP_HASH160 will hash the RedeemScript, which will make the stack look like Figure 8-17.

Figure 8-17. p2sh step 2

The 20-byte hash will be pushed to the stack (Figure 8-18).

Figure 8-18. p2sh step 3

And finally, OP_EQUAL will compare the top two elements. If the software checking this transaction is pre-BIP0016, we will end up with Figure 8-19.

Figure 8-19. p2sh end if evaluating with pre-BIP0016 software

This would end evaluation for pre-BIP0016 nodes and the result would be valid, assuming the hashes are equal.

On the other hand, BIP0016 nodes, which as of this writing are the vast majority, will parse the RedeemScript as Script commands (Figure 8-20).

Figure 8-20. p2sh RedeemScript

These go into the Script column as commands (Figure 8-21).

Figure 8-21. p2sh step 4

OP_2 pushes a 2 to the stack, the pubkeys are also pushed, and a final OP_2 pushes another 2 to the stack (Figure 8-22).

Figure 8-22. p2sh step 5

OP_CHECKMULTISIG consumes m + n + 3 elements, which is the entire stack, and we end the same way we did for bare multisig (Figure 8-23).

Figure 8-23. p2sh end for post-BIP0016 software

The RedeemScript substitution is a bit hacky, and there’s special-cased code in Bitcoin software to handle this. Why wasn’t something a lot less hacky and more intuitive chosen? BIP0012 was a competing proposal at the time that used OP_EVAL and was considered more elegant. A ScriptPubKey like Figure 8-24 would have worked with BIP0012.

Figure 8-24. OP_EVAL would have been a command that adds additional commands based on the top element

OP_EVAL would have consumed the top element of the stack and interpreted that as Script commands to be put into the Script column.

Unfortunately, this more elegant solution comes with an unwanted side effect, namely Turing completeness. Turing completeness is undesirable as it makes the security of a smart contract much harder to guarantee (see Chapter 6). Thus, the more hacky but more secure option of special-casing was chosen in BIP0016. BIP0016 (or p2sh) was implemented in 2011 and continues to be a part of the network today.

The special pattern of RedeemScript, OP_HASH160, hash160, and OP_EQUAL needs handling. The evaluate method in script.py is where we handle the special case:

class Script:
...
    def evaluate(self, z):
...
        while len(commands) > 0:
            command = commands.pop(0)
            if type(command) == int:
...
            else:
                stack.append(cmd)
                if len(cmds) == 3 and cmds[0] == 0xa9 \
                    and type(cmds[1]) == bytes and len(cmds[1]) == 20 \
                    and cmds[2] == 0x87:  
                    cmds.pop()  
                    h160 = cmds.pop()
                    cmds.pop()
                    if not op_hash160(stack):  
                        return False
                    stack.append(h160)
                    if not op_equal(stack):
                        return False
                    if not op_verify(stack):  
                        LOGGER.info('bad p2sh h160')
                        return False
                    redeem_script = encode_varint(len(cmd)) + cmd  
                    stream = BytesIO(redeem_script)
                    cmds.extend(Script.parse(stream).cmds)  

0xa9 is OP_HASH160, 0x87 is OP_EQUAL. We’re checking that the next three commands conform to the BIP0016 special pattern.

We know that this is OP_HASH160, so we just pop it off. Similarly, we know the next command is the 20-byte hash value and the third command is OP_EQUAL, which is what we tested for in the if statement above it.

We run the OP_HASH160, 20-byte hash push to the stack, and OP_EQUAL as normal.

There should be a 1 remaining, which is what op_verify checks for (OP_VERIFY consumes one element and does not put anything back).

Because we want to parse the RedeemScript, we need to prepend the length.

We extend the command set with the parsed commands from the RedeemScript.

>>> from helper import encode_base58_checksum
>>> h160 = bytes.fromhex('74d691da1574e6b3c192ecfb52cc8984ee7b6c56')
>>> print(encode_base58_checksum(b'\x05' + h160))
3CLoMMyuoDQTPRD3XYZtCvgvkadrAdvdXh

p2sh Signature Verification

As with p2pkh, one of the tricky aspects of p2sh is verifying the signatures. p2sh signature verification is different from the p2pkh process covered in Chapter 7.

Unlike with p2pkh, where there’s only one signature and one public key, we have some number of pubkeys (in SEC format in the RedeemScript) and some equal or smaller number of signatures (in DER format in the ScriptSig). Thankfully, the signatures have to be in the same order as the pubkeys or the signatures are not considered valid.

Once we have a particular signature and public key, we only need the signature hash, or z, to figure out whether the signature is valid (Figure 8-25).

Figure 8-25. Validation of p2sh inputs

As with p2pkh, finding the signature hash is the most difficult part of the p2sh signature validation process. We’ll now proceed to cover this in detail.

Step 1: Empty all the ScriptSigs

The first step is to empty all the ScriptSigs when checking the signature (Figure 8-26). The same procedure is used for creating the signature.

Figure 8-26. Empty each input’s ScriptSig

Step 2: Replace the ScriptSig of the p2sh input being signed with the RedeemScript

Each p2sh input has a RedeemScript. We take the RedeemScript and put that in place of the empty ScriptSig (Figure 8-27). This is different from p2pkh in that it’s not the ScriptPubKey.

Figure 8-27. Replace the ScriptSig of the input we’re checking with the RedeemScript

Step 3: Append the hash type

Last, we add a 4-byte hash type to the end. This is the same as in p2pkh. The integer corresponding to SIGHASH_ALL is 1 and this has to be encoded in little-endian over 4 bytes, which makes the transaction look like Figure 8-28.

Figure 8-28. Append the hash type (SIGHASH_ALL), 01000000

The hash256 of this interpreted as a big-endian integer is our z. The code for getting our signature hash looks like this:

>>> from helper import hash256
>>> modified_tx = bytes.fromhex('0100000001868278ed6ddfb6c1ed3ad5f8181eb0c7a38\
5aa0836f01d5e4789e6bd304d87221a000000475221022626e955ea6ea6d98850c994f9107b036\
b1334f18ca8830bfff1295d21cfdb702103b287eaf122eea69030a0e9feed096bed8045c8b98be\
c453e1ffac7fbdbd4bb7152aeffffffff04d3b11400000000001976a914904a49878c0adfc3aa0\
5de7afad2cc15f483a56a88ac7f400900000000001976a914418327e3f3dda4cf5b9089325a4b9\
5abdfa0334088ac722c0c00000000001976a914ba35042cfe9fc66fd35ac2224eebdafd1028ad2\
788acdc4ace020000000017a91474d691da1574e6b3c192ecfb52cc8984ee7b6c5687000000000\
1000000')
>>> s256 = hash256(modified_tx)
>>> z = int.from_bytes(s256, 'big')
>>> print(hex(z))
0xe71bfa115715d6fd33796948126f40a8cdd39f187e4afb03896795189fe1423c

Now that we have our z, we can grab the SEC public key and DER signature from the ScriptSig and RedeemScript (Figure 8-29).

Figure 8-29. DER signature and SEC pubkey within the p2sh ScriptSig and RedeemScript

We can now validate the signature:

>>> from ecc import S256Point, Signature
>>> from helper import hash256
>>> modified_tx = bytes.fromhex('0100000001868278ed6ddfb6c1ed3ad5f8181eb0c7a38\
5aa0836f01d5e4789e6bd304d87221a000000475221022626e955ea6ea6d98850c994f9107b036\
b1334f18ca8830bfff1295d21cfdb702103b287eaf122eea69030a0e9feed096bed8045c8b98be\
c453e1ffac7fbdbd4bb7152aeffffffff04d3b11400000000001976a914904a49878c0adfc3aa0\
5de7afad2cc15f483a56a88ac7f400900000000001976a914418327e3f3dda4cf5b9089325a4b9\
5abdfa0334088ac722c0c00000000001976a914ba35042cfe9fc66fd35ac2224eebdafd1028ad2\
788acdc4ace020000000017a91474d691da1574e6b3c192ecfb52cc8984ee7b6c5687000000000\
1000000')
>>> h256 = hash256(modified_tx)
>>> z = int.from_bytes(h256, 'big')  
>>> sec = bytes.fromhex('022626e955ea6ea6d98850c994f9107b036b1334f18ca8830bfff\
1295d21cfdb70')
>>> der = bytes.fromhex('3045022100dc92655fe37036f47756db8102e0d7d5e28b3beb83a\
8fef4f5dc0559bddfb94e02205a36d4e4e6c7fcd16658c50783e00c341609977aed3ad00937bf4\
ee942a89937')
>>> point = S256Point.parse(sec)
>>> sig = Signature.parse(der)
>>> print(point.verify(z, sig))
True

z is from the code on page 185.

We’ve verified one of the two signatures that are required to unlock this p2sh multisig.