<p>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.</p>

<p>2) (I can't understand what you're asking for)</p>

<p>3) 1900 transactions is not so deep. The height can be calculated by <code>ceil(log_2(number_of_tx))+1</code>. Plug in 1900, and the height is <code>12</code>. If you want to learn how merkle trees could be used for ISA, I'd suggest searching for <a href="https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki" rel="nofollow noreferrer">MAST</a>. It allows hiding the unexecuted parts of Script.</p>

CC BY-SA 4.0
2019-02-17T09:17:02.170Z
2019-02-17T09:17:02.170Z
MCCCS
<p>The leaves in the merkle tree are the transaction ids (<code>txid</code>) 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.</p>

<p>Ch06 of the same book describes the serialization of the <code>txin</code> and <code>txout</code> 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 <code>txin</code> and <code>txout</code> structures with an additional version and a locktime.</p>

<pre><code>tx {
    version : int32
    txin_count : VarInt
    txins : txin[]
    txout_count : VarInt
    txouts : txout[]
    nLockTime : uint32
}
</code></pre>

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

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

<pre><code>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
}
</code></pre>

<p>Even when a transaction is a witness transaction, the <code>tx</code> format is used to generate the <code>txid</code> 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 <code>tx</code> format to his peer for witness transactions, rather than the <code>witness_tx</code> format.</p>

CC BY-SA 4.0
2021-07-17T13:31:51.407Z
don't non-segwit txid's contain the witness[] as [0x00] and now use the same format? Great explanation.
Joe
CC BY-SA 4.0
2021-07-18T17:16:31.650Z
No. The 0x00 flag is used where the `txin_count` normally appears in the legacy tx format, and simply indicates that the transaction is a witness transaction so that the remaining bytes are parsed with the second witness format.
Mark H
CC BY-SA 4.0
2019-02-17T09:27:15.490Z
2019-02-17T09:27:15.490Z
Mark H
<p>So I am reading <a href="https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch09.asciidoc" rel="nofollow noreferrer">this</a> (excellent resource) on the Bitcoin merkle tree for a transaction.</p>

<blockquote>
  <p>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:</p>

<pre><code>HA = SHA256(SHA256(Transaction A))
</code></pre>
  
  <p>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:</p>

<pre><code>HAB = SHA256(SHA256(HA + HB))
</code></pre>
  
  <p>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.</p>
</blockquote>

<p>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 <em>record</em> would be hashed, like <code>{ a: 'foo', b: 'bar', c: 123, ... }</code> or something like that.</p>

<p>Second is, if this is where the idea of the <a href="https://github.com/ethereum/wiki/wiki/Patricia-Tree#main-specification-merkle-patricia-trie" rel="nofollow noreferrer">Patricia Merkle Tree</a> (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.</p>

<p>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 <a href="https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch06.asciidoc" rel="nofollow noreferrer">closer look</a>.</p>

<transactions><blockchain><merkle-tree>
Example of data that is hashed in the merkle tree for a transaction
Lance Pollard
# Example of data that is hashed in the merkle tree for a transaction

(Asked by: username_0 on 2019-02-17)

So I am reading [this](https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch09.asciidoc) (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](https://github.com/ethereum/wiki/wiki/Patricia-Tree#main-specification-merkle-patricia-trie) (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](https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch06.asciidoc).

**Tags:** transactions, blockchain, merkle-tree


---

## 2 answers

### Answer by username_2 on 2019-02-17. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_3**: don't non-segwit txid's contain the witness[] as [0x00] and now use the same format? Great explanation.  
> **username_2**: No. The 0x00 flag is used where the `txin_count` normally appears in the legacy tx format, and simply indicates that the transaction is a witness transaction so that the remaining bytes are parsed with the second witness format.  

---

### Answer by username_1 on 2019-02-17. Score: 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](https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki). It allows hiding the unexecuted parts of Script.


---

