Sunday, November 1, 2020

A breakdown of Bitcoin "standard" script types (crazy long)

When challenged recently to provide an little known bitcoin fact, I presented that "Addresses are not stored anywhere in the blockchain". This got me thinking a bit more about the bitcoin op-codes and the scripting language they describe. There is a good wiki article on it all as a refresher. It's basically a stack based language similar to Forth or RPL language. Here's an example of a Mancala game I wrote in RPL to show more complex code.

So below I will set out to try to explain the seven most easily identifiable bitcoin transaction types and how the script assembly for them works. Originally the script assembly was basically just <scriptSig> <scriptPubKey>, but with BIP16 and BIP141 the concept of deserializing either the redeemScript or the witnessScript were introduced. Most of this is done outside the scripting engine by the bitcoin client, but here I image a new op-code called OP_DESERIALIZE for the task. I realize it's fictional, but felt it was easier to present the material with this small imaginary op-code.

This makes our complete script assemble a bit more than just <scriptSig> <scriptPubKey> in most cases. I'll go through what that assembly looks like as well as how block explorers or client software identify the seven major transaction types, and how the address is parsed and assembled. I've also written a sample script that will decode these by walking through testnet blocks.


Pay to Pubkey

The original bitcoin client defined two fields scriptSig and scriptPubKey which each contained half of the script needed to validate a transaction. The two scripts were concatenated together to create a complete script. Here's an example of a Pay to Pubkey script

P2PK size script
scriptSig 72 <sig>
scriptPubKey 35 <pubkey> OP_CHECKSIG
assembled <scriptSig> <scriptPubKey>
btc_address b58_encode(pfx + hash160(spk[1:34]))
Test len(spk)==35 and (spk[0:1] + spk[34:35]).hex()=='21ac'
Total vB 107 72 + 35

Since the OP_CHECKSIG operation takes two arguments, this can be interpreted as txin.OP_CHECKSIG(<pubkey>, <sig>) from a non-stack based language perspective. In regards to TXN size, the total size of one of these assembled scripts is 107 vB (bytes). In regards to bitcoin addresses, the address is derived by chopping off the first and last bytes (op codes) from the scriptPubKey (spk) then performing a Hash160 operation on the data. The script is recognized by it's length and the first and last op codes (OP_PUSH, OP_CHECKSIG).

In the original client P2PK was used for what was termed "Pay to IP". In this process, you would enter an IP address in the PayTo field, and the client would connect to the remote node to receive a scriptPubKey from them.


Pay to Public Key Hash

Along with P2PK, the original client also supported P2PKH termed "Pay to address". Since addresses were always stored as the Hash160 of the pubkey, this format had the advantage of requiring no secondary piece of information. All the sender need was the bitcoin address, where as in P2PK the sender needed the pubkey and could derive the address. But pubkeys are long and generally not checksumed like bitcoin address notation is. Having the sender only need a small checksumed hash was simpler and became much more widely used, although it does require a larger scriptSig making it more expensive to spend

P2PKH size script
scriptSig 106 <sig> <pubkey>
scriptPubKey 25 OP_DUP OP_HASH160 <pkHash> OP_EQUALVERIFY OP_CHECKSIG
assembled <scriptSig> <scriptPubKey>
btc_address b58_encode(pfx + spk[3:23])
Test len(spk)==25 and (spk[0:3] + spk[23:25]).hex()=='76a91488ac'
Total vB 131 106 + 25

the total size of one of these assembled scripts is 131 vB (bytes). In regards to bitcoin addresses, the address is derived by chopping off the first 3 and last 2 bytes (op codes) from the scriptPubKey (spk). The script is recognized by it's length and the first 3 and last 2 bytes (OP_DUP, OP_HASH160, OP_PUSH, OP_EQUALVERIFY, OP_CHECKSIG).


Pay to Script Hash

So this simple script concatenation worked well for the first three years, but then, eventually more flexibility was desired and BIP-16 was introduced. It was a simple enough concept, but if you're looking at a TXN validation completely within the scripting engine then the simple concatenation is not enough. You will need to invent a new op code OP_DESERIALIZE and then insert some op-codes to glue it together to exist purely in this scripting engine. The concept of OP_DESERIALIZE, introduced here, is to take the top data element (redeemScript) and reinterpret it as code instead of data.

P2SH size script
scriptSig ?? <sigData> <<redeemScript>>
scriptPubKey 23 OP_HASH160 <rsHash> OP_EQUAL
assembled <scriptSig> OP_DUP <scriptPubKey> OP_VERIFY OP_DESERIALIZE
btc_address b58_encode(pfx + spk[3:23])
Test len(spk) == 23 and (spk[0:2] + spk[22:23]).hex() == 'a91487'
Total vB 96+ 73 + len(redeemScript) + 23

The total size on the blockchain for a P2SH spent output will be at least 97 bytes. The actual size will be dependent upon the size of redeemScript. The majority of non-segwit P2SH transactions are multisig related. At the time of BIP-16, multisig (P2MS) was already widely adopted, though it was mostly done in the scriptPubKey element. As before, this put the burden on the sender to maintain an intricate scriptPubKey instead of a simple bitcoin address. P2SH allows complex scripts to be used while still providing basic pay to address type semantics. The address is derived like most pay-to-address outputs, though a different prefix (pfx) is used. The script is recognized by its length and by clipping the first and last two bytes.

One thing to note with P2SH is that the scriptSig can only support OP_PUSH up to 520 bytes. This puts a hard cap at the size of redeemScript and the flexibility of P2SH in general.


Pay to Witness Public Key Hash

The last four script types were all introduced with Segregated Witness (BIP-141). In order for Segwit to allow backward compatibility, the scriptSig and scriptPubKey elements are either empty or consist of nothing more than data elements (OP_PUSH). Since non-zero data will always pass validation, this makes all segwit TXNs default to valid if witness data is not included. Like P2SH a lot of the op-codes are implied and to make the point I'll artificially insert glue-code here as we did with P2SH.

The P2WPKH is modeled after the P2PKH, but the scriptSig is moved to the witness program and most of the op-codes are implied. Scripts are generally prefixed with OP_0 to signify segwit enablement. The goal of segwit was to allow blocks to expand to something approaching 4MiB while not breaking older implementations. So you can still only have 1MiB of "legacy" block data, but you can have up to 3MiB of witness data... well kinda... The real WU math is a bit more complex, but I'll defer to the wiki for that.

P2WPKH size script
witness 107 <sig> <pubkey>
scriptPubKey 22 OP_0 <pkHash>
assembled <witness> OP_DUP OP_HASH160 <scriptPubKey> OP_SWAP OP_DROP OP_EQUALVERIFY OP_CHECKSIG
btc_address b32_encode(pfx + spk[2:22])
Test len(spk) == 22 and (spk[0:2]).hex() == '0014'
Total vB 48.75 22 + 107/4

For those keeping score, you'll notice that the witness program is 107, yet the same scriptSig elsewhere is 106. This is because the witness program has to push an element count (0x02) so it can be deserialized. I won't get into those specifics since I think we are already getting off in the weeds. You'll also notice with the WU math, we get to apply a 75% discount to the witness program. This gives our "virtual size" in the block at 48.75, making P2WPKH far and away the least expensive script type. The address is derived from the last 20 bytes of scriptPubKey but by identifying the scriptPubKey as a P2WPKH type, the address will use bech32 encoding instead of base58 encoding.


Pay to Witness Script Hash

As part of segwit P2WSH was introduced as a complement to the BIP-16 P2SH standard script. But because the witness program is constructed and not pushed, it does not have the 520 byte push limit that P2SH has. This means you can construct arbitrarily large M of N multisig scripts in the same way as P2MS worked, but at a greatly reduced WU size. Just like P2SH, the script itself (witnessScript) is hashed and that hash is used to construct the address. But unlike P2SH, the witnessScript hash uses a 32 byte SHA256 hash not a 20 byte HASH160 hash. This makes P2WSH addresses uniquely long. As before, there is a lot of implied op-codes used in the imagined script assembly.

P2WSH size script
witness ?? <sigData> <<witnessScript>>
scriptPubKey 34 OP_0 <wsHash>
assembled <witness> OP_DUP OP_SHA256 <scriptPubKey> OP_SWAP OP_DROP OP_EQUALVERIFY OP_DESERIALIZE
btc_address b32_encode(pfx + spk[2:34])
Test len(spk) == 34 and (spk[0:2]).hex() == '0020'
Total vB 52+ 34 + (74 + len(witnessScript))/4

Looking at the size calculation, the minimum overhead for P2WSH is 53 vBytes which is significantly smaller than P2SH. It also does not fall victim to the size limitation of the BIP16. The witness program can support OP_PUSH operations up to 10,000 bytes. You will also notice that the address construction is 32 bytes. This script type is easily identified by its scriptPubKey length and the specific pattern of the first two bytes.


P2SH Encapsulating Pay to Witness Public Key Hash

The next two script formats are clever bridge formats that were popular during the transition to segwit while not all wallets supported it. The receiving side (scriptPubKey) is P2SH, but the spending side (scriptSig) is segwit. This works because BIP16 simply needs a hash, any hash. Normally a P2SH would receive a redeemScript hash, but in this case, what it receives is a scriptSig hash, which in turn contains the pubkey hash.

P2SH-P2WPKH size script
witness 107 <sig> <pubkey>
scriptSig 23 <OP_0 <pkHash>>
scriptPubKey 23 OP_HASH160 <ssHash> OP_EQUAL
assembled <witness> OP_DUP OP_HASH160 <scriptSig> OP_DUP <scriptPubKey> OP_VERIFY OP_DESERIALIZE OP_SWAP OP_DROP OP_EQUALVERIFY OP_CHECKSIG
btc_address b58_encode(pfx + spk[2:22])
Test is_p2sh() and len(ss) == 23 and (ss[0:3]).hex() == '160014'
Total vB 72.75 23 + 23 + 107/4

Since the scriptPubKey is BIP16, the address is computed just like any BIP16 scriptPubKey. The fact that this encapsulates a segwit transaction is not known until the scriptSig is revealed. Only then is the serialized OP_0 and OP_PUSH interpreted as a P2SH-P2WPKH transaction. Due to the encapsulation, the imagined script assembly is a bit harder to understand, but it carries the same format as we'd expect, { witness + glue + scriptSig + glue + scriptPubKey + glue }. The "glue code" just has more work to do since it must verify both the scriptSig hash and the pubkey hash. Although this format is more portable, it does take up 24 more vBytes than the native format.


P2SH Encapsulating Pay to Witness Script Hash

Just like P2SH-P2WPKH, P2SH-P2WSH is simply a way to contain a P2WSH in a BIP16 address. Again, this works exactly like a BIP16 address until the scriptSig is exposed. Only then does it become clear that this is a P2WSH script. Just like the native P2WSH scripts, this format fixes the 520 byte script limitation that was previously imposed on the BIP16 redeemScript. The new P2WSH witnessScript is not capped until it reaches 10,000 bytes.

P2SH-P2WSH size script
witness ?? <sigData> <<witnessScript>>
scriptSig 35 <OP_0 <wsHash>>
scriptPubKey 23 OP_HASH160 <ssHash> OP_EQUAL
assembled <witness> OP_DUP OP_SHA256 <scriptSig> OP_DUP <scriptPubKey> OP_VERIFY OP_DESERIALIZE OP_SWAP OP_DROP OP_EQUALVERIFY OP_DESERIALIZE
btc_address b58_encode(pfx + spk[2:22])
Test is_p2sh() and len(ss) == 35 and (ss[0:3]).hex() == '220020'
Total vB 76+ 23 + 35 + (74 + len(witnessScript))/4

Again, the imagined assembly of this seems to be a lot to take in, but simply seeing it as { witness + glue + scriptSig + glue + scriptPubKey + glue } may help to make it a bit easier to comprehend. This format is recognizable by the longer scriptSig with the serialized OP_0 prepended to it, and the address is computed as any BIP16 scriptSig is. Even though this more portable, it is 24 bytes larger than the native form.


Other formats

The two major forms not discussed here are OP_RETURN transactions and P2MS (Pay to Multisig). OP_RETURN is simply a unspendable UTXO that can encode some data into the public ledger. P2MS is the legacy form of multisig before P2SH was more commonly used. P2MS avoids some of the limitations of BIP16. As a general rule, if a TXN is not one of these recognized forms, it can be assumed to be of the form <scriptSig> <scriptPubKey>. If that execution fails, then the transaction is invalid. There is also some debate as to whether or not miners will include these arbitrary transaction types. One thing for certain is that there is no convention for displaying any type of address for these UTXOs, since there is no convention for creating one.

References



No comments:

Post a Comment