Transaction Merkle Trees

When generating a Merkle tree of Bitcoin transactions, the value of each leaf nodes is made up of a transaction ID (TXID). Transactions are typically ordered in the sequence they are observed arriving on the network; however, due to network latency, there can be no fixed topology rule applied. The 32-byte TXID is generated by passing the serialised string of the raw transaction data through the SHA256 function twice. These TXIDs then securely represent all the details of the transaction, and any Merkle tree constructed of these values can be used to successfully verify where funds came from, how much was transferred, the data which specifies the conditions of the locking script and any other detail encoded in the transaction. It should be noted that, unlike the Merkle trees that we observed in Chapter 1, in the case of the Bitcoin system, the leaf nodes, all interior node values and the Merkle root are generated using a double SHA256 (HASH256) hash of the raw transaction data or the concatenated string of the parent node values.

\

Bytes	Data Field	Hexadecimal String
4	Version	01000000
1-9	Number of Inputs	01
32	Previous TX hash (reversed)	f253cf794a7a0aff45144c8ea1fc4271be683952ae8241ee1524266b46375246	Inputs
4	Previous Output Index	00000000
<in-counter> qty with variable length per input	Script Length	6b
<in-script length>-many bytes	ScriptSig (Unlocking Script)	4830450221008f8c069a2e8aa0cce2455374916ff1dedc40da58680c7fab925b0d8206e d4e48022013bd576c0ed17448525d282ca4ddc55245c788da88eee7e35a2084b7bed78 caa01210302e3a61057a9c9616291b17085c16d9e1f22821395e3ba792f4492f61d57169b
4	nSequence	ffffffff
1-9	Number of Outputs	01
8	Value (reversed)	30c11d00000000	Outputs
1 - 9 bytes VI = VarInt	Script Length	19
<out-script length>-many bytes	ScriptPubKey (Locking Script)	76a914800311626c5e50a10ea7d84f42471c0e7c17a4a088ac
4	nLockTime	00000000
Serialised String of Raw Transaction Data
0100000001f253cf794a7a0aff45144c8ea1fc4271be683952ae8241ee1524266b46375246000000006b4830450221008f8c069a2e8aa0cce2455374916ff1d edc40da58680c7fab925b0d8206ed4e48022013bd576c0ed17448525d282ca4ddc55245c788da88eee7e35a2084b7bed78caa01210302e3a61057a9c96162 91b17085c16d9e1f22821395e3ba792f4492f61d57169bffffffff0130c11d00000000001976a914800311626c5e50a10ea7d84f42471c0e7c17a4a088ac00000000
TXID
0a2a20c62734f1963c99e29e4848e2472b7f15ecb8abf8f29eb290db363a4d4d

When a TXID is concatenated with the ID of the next transaction and hashed, the output will be dependent upon the order in which the transactions were concatenated. In this respect, by constructing a Merkle tree from these TXIDs, it can then be used to verify not only the specific details of a single transaction but also the relative ordering of transactions to one another. As more and more transactions occur on the network, the Merkle tree is appended to include the TXIDs of the new transactions as the leaf nodes and the 32-byte Merkle root of the transaction set is calculated anew. This Merkle root can then be used to verify any detail from within the transaction set.

A key feature of Bitcoin is its capability to manage transactions that evaluate a wide variety of conditions. In order to create the scripts used to manage these transactions, Bitcoin has an embedded scripting language that uses a fixed set of opcodes. Scripts built with these opcodes are inserted into the transaction outputs to generate the needed functionality. For example, this can include multi-signature unlocking, form entry and evaluation or complex contract-based transactions with detailed data entry and conditional requirements. There are a number of techniques that allow users to embed data into transactions and to perform conditional evaluations upon that data and other data that has been written to the Bitcoin database in earlier transactions.

In this way, not only are the transactions used to generate the TXIDs that make up the leaves of the Merkle trees verifiable using this data structure, but also the data embedded within these transactions. The ability to use the Bitcoin system to verify external data objects other than simply transactions is just one of the many innovative features of the protocol and the Merkle tree is essential to this capacity.

Records of Bitcoin transactions can be held by a multitude of different parties, each of whom can store each transaction with its accompanying Merkle proof. We call this type of transaction database a 'Working Blockchain' which can be described as a subset of the total blockchain, that maintains the security of the Merkle tree through the proof of work applied to the block it is in. The fact that all the transactions are recorded within a Merkle tree data structure allows for efficient verification of any individual set of records against those held by another entity with a simple check of the Merkle proof. The next chapters will discuss how, in the event of a conflict between two alternate transaction sets and their Merkle roots, the network comes to consensus as to which Merkle root is in fact the correct one, and subsequently which set of transaction ordering will be relied upon to check the validity of new transactions for double spends.