6

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 enter image description here

Transaction Tree enter image description here

3

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.

  1. 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(logxn) 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.

  • Thanks for your clarification! Hoping in that case the flow of the diagram is correct. – Susmit Jun 28 '17 at 6:35
  • All the trees in ethereum are patricia tries (agree there might be limited benefit to this). Most nodes are branch node which have 17 children (although there are also optimized 'extension nodes'). The TXs are input in their trie by the rlp of their txIndex within each block (chosen by miner) – ZMitton Jul 27 '17 at 18:37
1

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.

  • Thanks for your reply! But from the basic structure listed in my example if you could highlight where I am right or wrong will be of great help. So that at-least I can get the basic correct flow direction. – Susmit Apr 24 '17 at 4:58
  • I guess I would say that the transactions do not form a tree. The transactions form more of a list. The blocks form a basic linked list (linked by block hashes), and in each block is simply a list of transactions. There's no real tree for the transactions. I think that's your basic disconnect. – Thomas Jay Rush Apr 24 '17 at 5:10
  • In that case why its said that Ethereum block consists of not one but three Merkle tree root hash references (i.e. state, transaction and receipt)? – Susmit Apr 24 '17 at 5:35
  • Don't know. A list can be considered a tree with one branch at each node. – Thomas Jay Rush Apr 24 '17 at 5:38
  • Is there any specific sequence in which the transactions are referenced in this link list or its just in which order it was picked? – Susmit Apr 24 '17 at 5:50
0

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

  • Thanks for the answer! Good to know that was in right path. So I guess from the flow diagram perspective don't have to make any changes. – Susmit Jun 28 '17 at 6:34
  • @susmit i think the state trie stuff you wrote is a bit off. The stateRoot encodes the entire state, not just what changed during the last block. Luckily, the way this tree is designed (patricia trie), only requires a few branches to be re-hashed in order to recompute the new root – ZMitton Jun 28 '17 at 18:52
  • @ZMitton Request you to please update the diagram and post it here – Susmit Jun 29 '17 at 9:26
  • @susmit actually the way you have it might be correct, but to be clear (and what confused me about your drawing), the old state of AccountA(from 180993) would not be included in the construction of the stateRoot for block 180994 – ZMitton Jun 29 '17 at 18:53
  • All trees in Ethereum are Patricia trees for consistency – k26dr Jan 24 '18 at 16:43
0

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)

enter image description here

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.