29

Here is my basic understanding about how Ethereum stores transactions

  1. A hash is generated for each transaction
  2. Then pairs are selected and a hash is generated for each pair
  3. This way the last remaining hash becomes the root
  4. Block header contains three Merkle trees
    • To maintain the state
    • To maintain the transactions
    • To maintain the receipts
  5. Each block refers to its previous block's hash
  6. I am attaching the very common diagram showing this structure

enter image description here

Questions:
1. The state root of Block 180994 is pointing to Block 180993's first left child of the state root. What does it mean and why is it needed?
2. Lets take an example
- First block 180993 is having a transaction where Account 98 is passing 30 ethers ether to Account 100
- Second block 180994 is having a transaction where Account 99 is passing 20 ethers to Account 100

How this will be reflected in the tree? Will there be similar kind of cross mapping of Merkle trees like shown in the diagram? Please explain

Added more Detail

enter image description here

18

The state has the information of all accounts in the blockchain, it is not stored in each block. The state is generated processing each block since the genesis block. Each block will only modify parts of the state.

How to generate the state is defined in the yellow paper (pdf). It is defined in such a way that it can be implemented in any programming language, and all such implementations will generate the same representation.

  1. It means the left side was not modified in block 180994. It is only a representation, remember the whole state is not stored, only the root hash.

  2. There's an article about Merkle Trees in Ethereum, I probably can't do better. The basic idea of merkle trees is that for a single operation it will only modify the minimum amount of nodes to recalculate the root hash.

  • thanks for your answer! Here is my understand please share your views. 1. Each node is maintaining in total three trees. Each block is referring to one of the roots in that whole tree. 2. Based on the mapped root the state could be found at that stage. – Susmit Apr 19 '17 at 6:07
  • 3. Lets say 180994 is having the transaction (A->B 50 eth). So it means if I refer to block 180994 then based on state root hash I can find Account A's state is 50 eth and B's account state is 150 eth (as B's initial state was 100). 4. If I refer to 180993 having a transaction where A's total is becoming 100 eth then based on state root hash I can find Account A's state is 100 eth – Susmit Apr 19 '17 at 6:08
  • 2
    1) Only the state tree is required. The transaction and receipts trees are to build from the block data. It is only used to validate the block. It is necesary to store them, because they will not be used again. 2. Yes, if your node store the whole state history you could retrieve the state in any point in the history. But some nodes can prune old history. 4) y 5) The state will only show the final balance. For block 180993 A: 100, B: 100 and for block 180994 A: 50, B: 150. – Ismael Apr 19 '17 at 16:29
  • Thanks for your reply! Are you saying all the transaction and receipt trees are stored in the block itself and not just their root hash? Can you also have a look at my other question i.e. "How Ethereum transaction tree is formed" and share your views as it is in same lines – Susmit Apr 19 '17 at 17:25
  • 1
    Yes, each block has the complete transactions. The txs root hash is to quickly validate the transactions within the block were not modified. – Ismael Apr 19 '17 at 19:03
14

Ethereum is said to have an account-based blockchain. The state isn't directly stored in each the block.

To build a better conceptual understanding, we can say that all account states reside locally on the Ethereum node in the form of “state data”. This is common for performance reasons and is assumed that it will be stored in a Merkle Patricia tree, but the protocol specification doesn’t require it. Yellow paper states,

The world state (state), is a mapping between addresses (160-bit identifiers) and account states (a data structure serialised as RLP, see Appendix B). Though not stored on the blockchain, it is assumed that the implementation will maintain this mapping in a modified Merkle Patricia tree

So, in addition to the blockchain itself, we find ourselves dealing with a "second state". State data can be described as implicit, meaning it can be calculated from the actual blockchain data. Transactions contain all the appropriate fields to determine new state data. Unlike Bitcoin, Ethereum blocks contain a copy of both the transaction list and the Merkle root hash of the entire state tree.

Taken from the Yellow Paper by Dr. Gavin Wood:

Ethereum Runtime Environment: (aka ERE) The environment which is provided to an Autonomous Object executing in the EVM. Includes the EVM but also the structure of the world state on which the EVM relies for certain I/O instructions including CALL & CREATE.

To conclude, the storage of the state is managed by the client implementation of the Ethereum protocol. I've attached an (overly simplified) image I created which aims to show the state transition before and after a transaction is sent between two parties.

Image I've created to help understand the conceptual model of state transition As far as understanding the Merkle Patricia tree, I'd point you in the direction of any article covering Radix Trees

  • First of all thanks for your detailed answer! Have just restructured my diagram a bit. Listing my understanding and queries. Please share your views on them. Q1. What I am getting is the block header is only storing the root hashes for each tree i.e. state/transaction/receipt. The actual tree is a single tree with various roots as it grows up. Q2. The state root of that block is pointing to a root which can give you the state (i.e. at that point) of all the accounts involved in those transactions present in the block. – Susmit Apr 19 '17 at 5:53
  • Q3. So based on the newly added image, if I refer to block 180993 (assuming A's account is getting ether making it total of 100) then using state root hash I can find Account A's state is 100 specific to that block. Q4. Lets say 180994 is having the transaction (A to B 50 eth). So it means if I refer to block 180994 then based on state root hash I can find Account A's state is 50 eth and B's account state is 150 eth specific to that block. Q5. Hoping the state/transaction/receipt trees are maintained by each client on their respective nodes – Susmit Apr 19 '17 at 5:54
  • Q6. But lets say Node A (i.e. having account A) is down, still a call from Node B can figure out A's balance, possibly by using the transaction tree and summing up all the account transfers from/to A's account. Q7. If lets say Node A was active then if there was a call to find A's balance will it query Node A directly. Believe that never happens it only tries to figure out using the state root hash from the latest block and then finding A's state which here is 50 eth? – Susmit Apr 19 '17 at 5:56
0

Steal this diagram from Badr in this fantastic answer Where is the state data stored?

"Block 180994 is pointing to Block 180993's first left child" simply means that the first left child has been mutated. So we could simply refer to the same hash. Note that this approach is applied recursively. And that's why we see many references to the previous block.

enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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