Example of data that is hashed in the merkle tree for a transaction

Question

So I am reading this (excellent resource) on the Bitcoin merkle tree for a transaction.

The merkle tree is constructed bottom-up. In the following example, we start with four transactions, A, B, C, and D, which form the leaves of the merkle tree, as shown in Calculating the nodes in a merkle tree. The transactions are not stored in the merkle tree; rather, their data is hashed and the resulting hash is stored in each leaf node as HA, HB, HC, and HD:

HA = SHA256(SHA256(Transaction A))

Consecutive pairs of leaf nodes are then summarized in a parent node, by concatenating the two hashes and hashing them together. For example, to construct the parent node HAB, the two 32-byte hashes of the children are concatenated to create a 64-byte string. That string is then double-hashed to produce the parent node’s hash:

HAB = SHA256(SHA256(HA + HB))

The process continues until there is only one node at the top, the node known as the merkle root. That 32-byte hash is stored in the block header and summarizes all the data in all four transactions.

That makes sense, but I have a few questions. First is how the Transaction like Transaction A is hashed, and what is included in a transaction in practice. For example, if it's a JSON object stringified, or a byteArray in JavaScript, or if data must be in a specific format, etc.. I would like to see for example how a record would be hashed, like { a: 'foo', b: 'bar', c: 123, ... } or something like that.

Second is, if this is where the idea of the Patricia Merkle Tree (or perhaps even Merkle DAG, which I have seen somewhere) comes in, to shorten the amount of stuff you have to store in memory because the hashes don't completely overlap and so would have a lot of empty tree nodes.

Finally, what an example set of transactions would look like in a single block where they say on average they have 1900 transactions. This would be a pretty deep merkle tree, and I would like to see what the transactions are actually called and some more info on their data structure. For example, if they go all the way down to the ISA (Instruction Set Architecture) operations, or they are much higher level. That's basically all I'd like to know. I didn't see that in the book linked to above yet, but will take a closer look.

Answer 1

The leaves in the merkle tree are the transaction ids (txid) of the transaction, which in turn is the double-SHA256 of the full serialized transaction in its binary (little-endian) form, which is the same format it is received over the network.

Ch06 of the same book describes the serialization of the txin and txout structures. I'm not sure why the transaction format itself seems to be absent from the book. A transaction is a serialization of the sequence of txin and txout structures with an additional version and a locktime.

tx {
    version : int32
    txin_count : VarInt
    txins : txin[]
    txout_count : VarInt
    txouts : txout[]
    nLockTime : uint32
}

The VarInt is the same one used in the book. In the Bitcoin core source code it is called CompactSize.

There is an alternative format for witness transactions which are used by clients supporting the format, which uses a trick that the txin_count must usually be >= 1 because all transactions must spend an existing input (except the coinbase tx). Thus, if the byte where txin_count is expected above has the value 0, this indicates the presence of a witness transaction, where there are some additional fields.

witness_tx {
    version : int32
    witness_marker : byte //always 0
    witness_flag : byte
    txin_count : VarInt
    txins : txin[]
    txout_count : VarInt
    txouts : txout[]
    witnesses : witness[] //list always has the same length of txin_count
    nLockTime : uint32
}

Even when a transaction is a witness transaction, the tx format is used to generate the txid for that transaction to be used in the calculation of the merkle root. This is to ensure that witness transactions are backward compatible with the older transaction format. A client supporting SegWit which is communicating with a client which does not support it will send the tx format to his peer for witness transactions, rather than the witness_tx format.

Answer 2

1) Transactions don't contain merkle hashes. Pre-SegWit transactions' hashes are calculated by serializing the transaction (you can search for "the hex format"), and then hashing the byte array. After SegWit, signatures are excluded from transaction hashes.

2) (I can't understand what you're asking for)

3) 1900 transactions is not so deep. The height can be calculated by ceil(log_2(number_of_tx))+1. Plug in 1900, and the height is 12. If you want to learn how merkle trees could be used for ISA, I'd suggest searching for MAST. It allows hiding the unexecuted parts of Script.