How Ethereum transaction tree is formed

Question

I am looking for clarity on transaction tree structure. Below I have listed my understanding

1. If I am not wrong the state changes are tracked in a single state tree.
2. Each block has a state root hash pointing to the root having the state of the accounts taking part in the set of transactions to that block
3. So as the blocks keep on adding (i.e. there are changes in state of accounts) this state tree grows
4. But how about the transaction tree
5. Are the transaction root hash present in a block pointing to individual tree roots or again its a single tree like state tree (i.e. it points to various root levels)
6. To highlight this difference I have created two diagrams for state and transaction trees.
7. So what I am trying to say is all the blocks refer to a common state tree. But each block is having its own transaction tree
8. Please share your views and correct me where you feel I am wrong

State Tree

Transaction Tree

Answer 1

I'm going to disagree with the conversation in the comments to the other answer. (Apologies in advance!)

I think what's being outlined in the question is generally correct, at least from the way I'd understood things.

5. Are the transaction root hash present in a block pointing to individual tree roots or again its a single tree like state tree (i.e. it points to various root levels)

An individual tree/trie root. The state tree/trie is different because we're often updating existing state from a previous block, whereas with transactions no such thing can happen.

I don't think the tree/trie is actually just a list (i.e. single branching all the way down). Firstly, we'd lose the advantages of using a tree/trie at all. A tree/trie gives us O(log_xn) traversal, access, etc., whereas a list would be O(n). Secondly, in a Merkle tree it's the leaves that hold the actual data, with the parent nodes holding intermediate hashes all the way up to the root. A "Merkle list" would therefore only be able to hold one transaction, that being the final node or tail. (But then the tail would be the same as the root... so such a thing makes no sense anyway.)

Secondly, from the Geth code [1, 2, 3], and I think from the Yellow Paper [equation (176), although it's difficult to tell... ], the order of the transaction tree is 16 - that is, each node has 16 child nodes. Similarly, the picture here also has a label of "16" for each of the trees/tries.

I'm unsure how the order of the transactions is maintained or translated into the tree.

Disclaimer: If I'm conflating order with degree when describing the number of children per node in the above tree/trie, then apologies.

Answer 2

Absolutely the best way to figure this out that I've found is the Ethereum Ontology here: https://github.com/ConsenSys/EthOn.

I don't know if you're allowed to simply link to answers, but if you're not you should be. Duplicating this work on StackExchange would be a mistake.

Answer 3

Almost correct.

The Transaction and Receipts trees are only Merkle Trees, whereas the State Trie is a Merkle Patricia Trie. Since every Ethereum Block contains a list of transactions, and this list is "frozen solid" (Buterin - https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/) there would be no use to make it so you get O(log(n)) read, writes or deletes. What matters is that you can give a Merkle Proof of inclusivity. Furthermore, neither the Transaction nor the Receipts trees are persisted, they are recreated as needed (as opposed to the state trie, of course).

** Let me clarify something

You do not need a Merkle Patricia Trie for the txn root and receipts root, but at least in pyethereum that is how they create both tries. My guess is to stay consistent, one function for all tries. In common.py

def mk_receipt_sha(receipts): t = trie.Trie(EphemDB()) for i, receipt in enumerate(receipts): t.update(rlp.encode(i), rlp.encode(receipt)) return t.root_hash

Answer 4

Here is an example of how the state trie looks like (for transactions just replace Simplified World State on the top-right with Simplified Transactions where Keys are transaction_index and Values are transaction_content. It's simplified since some details are omitted such as RLP encoding)

If I am not wrong the state changes are tracked in a single state tree.

The Merkle Patricia Trie is an immutable data structure. Whenever you make any changes to any part of the trie it will result in a new trie with a different root with a different hash. However, the new trie might have pointers to subtrees from the previous state trie. Let's say you had a trie with 3 levels. If you want to change something on the lowest level you need to create a new node on the 2nd level, and a new node on the 1st level (the root) which will be recorded to the blockchain.

Each block has a state root hash pointing to the root having the state of the accounts taking part in the set of transactions to that block

Each block has the state root hash pointing to the root of the state trie having the state of all the accounts not only the ones taking part in the set of transactions to that block. As I mentioned above whenever the state of any account is changed the root of entire tree is changed.

Are the transaction root hash present in a block pointing to individual tree roots or again its a single tree like state tree (i.e. it points to various root levels)

Every block has its own transaction trie where keys are RLP encoded transaction indexes within the block and values are RLP encoded transactions.

To highlight this difference I have created two diagrams for state and transaction trees.

In your first image where the state trie is depicted you point the state root of block 180994 to the root of the previous state trie as its left child. This normally shouldn't happen. I think what you meant is the new root should point to the left child of the previous root.

Answer 5

I believe your diagram is correct. Finding a transaction should be as easy as doing a binary search on the blocks. Consider the function:

find block where: someBlockT1 <= timestamp(tx) <= someBlockT2

Then search through the Tx merkle trie that is contained in the returned block.