125

Here's my interpretation, based on the yellow paper: ...the Tries should look more like this:


79

Trie (also called digital tree, prefix trie or radix trie) An ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings. A node's position in the tree defines the key with which it is associated. https://en.wikipedia.org/wiki/Trie A trie for keys "A","to", "tea", "ted", "ten", "i", "in", and "...


72

Lets first start with my adaptation of this figure illustrating the Bitcoin block structure: So far so good. All fairly basic. Enter Ethereum and things get a wee bit more complex. After reading through this and this, and as per @eth 's recommendation this, my best interpretation is the figure below: The header field definitions are available in section 4....


21

Here is a complete structure of a block and where it plays its role in Ethereum's blockchain. You asked for a diagram but i think this would be more explanatory.


20

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


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


13

Update: https://github.com/PISAresearch/event-proofs has some code. From its readme: Event proofs A POC to explore how Ethereum logs could be verified in a smart contract. Proofs are generated using eth-proof and verified using the Merkle Patricia Tree implementation from Peace Relay. If running the tests against Infura be patient with them as ...


11

The description can be found in the Yellow Paper which is the formal specification of the Ethereum protocol. Here are the main pieces of a block: 4.3. The Block. The block in Ethereum is the collection of relevant pieces of information (known as the block header), H, together with information corresponding to the comprised transactions, T, and a set ...


10

The Ethash DAG is not related to merkle trees (the word "merkle" does not appear on either wiki page). The Ethash DAG only serves as a big dataset (i.e. too big to fit in memory) for making Ethash mining be "memory-hard". Ethereum's merkle tree is what keeps track of the state of all accounts and contracts. The state of all accounts is not directly related ...


9

'Trie' comes from the word retrieval, since it only uses the prefix of a word to find it in a dictionary. It is an ordered tree where the keys are usually strings ending with a terminal symbol, and each vertex represents a prefix. The root of a trie is usually an empty string, as we can see in the diagram taken from wikipedia. For more information about the ...


8

This sounds correct to me. Referring to the graphical interpretation of the descriptions in the Yellow Paper, your 4 tries are shown in the "Information required to derive block header" section. The picture exactly matches your descriptions.


7

Here's a picture from V's article regarding data structures for light clients: https://blog.ethereum.org/2014/02/18/ethereum-scalability-and-decentralization-updates/


6

The trie can be up to 64 levels deep. 1 for each hex character of a bytes32 hash. To find a piece of data, one must traverse 1 level at a time picking out the nth index of a (usually) 17 element array. (source) However there is an optimization to shortcut this path when there are no other branches at a particular level. In practice I have found there to be ...


5

I think the below picture might be the closest you will get. It can be found in this answer to a previous question: Ethereum block architecture Note that the purpose of this diagram is to show how the state tries for different blocks are related. The transaction tries are rather more straightforward. (i.e. They're just standalone, non-interacting data ...


5

Vitalik Buterin gives a compact answer: Every block header in Ethereum contains 3 trees for three kinds of objects: Transactions, Receipts (essentially, pieces of data showing the effect of each transaction), State. You can read a longer version with pictures here.


5

Every Merkle is a directed acyclic graph (DAG) because each node is accessed by its name. Each branch of Merkle is the hash of its local data, because its fast to access instead of accessing by its original content. This will helps to prevents cycles (lets assuming there are no hash collisions), because one cannot link the first created node to the last node ...


5

About 1/2: from https://github.com/ethereum/wiki/wiki/Design-Rationale 32 byte word size - the alternative is 4 or 8 byte words, as in most other architectures, or unlimited, as in Bitcoin. 4 or 8 byte words are too restrictive to store addresses and big values for crypto computations, and unlimited values are too hard to make a secure gas model ...


4

The state trie contains the balance of each account. Even transactions that throw an exception result in a reduction in the sender's balance through gas costs, which means that the resulting state is different from the initial state. An interesting question would be to see if a transaction with a gas price of 0 can be excluded from a block without changing ...


4

Different computers store binary data differently. The purpose of the RLP as stated in the referenced document is to The purpose of RLP (Recursive Length Prefix) is to encode arbitrarily nested arrays of binary data, and RLP is the main encoding method used to serialize objects in Ethereum. In other words, it turns any binary data structure into a string ...


4

Whenever a new item is added to the trie the algorithm can decide whether to insert a branch, a leaf or an extension. Let's say you need to insert 3 key-value pairs: "0x01": 1 "0x01234": 2 "0x01235": 3 After "0x01" is inserted the trie will look like this (hash0 is root): <hash0> leaf ["0x01", 1] After "0x01234" is inserted (hash1 is root): <...


4

In the storage contents of the account what are these (k,v) i.e keys and values? The contract code is free to use these as it wishes. For example, in this Solidity code the compiler will take index 0 for var1 and index 1 for var2: pragma solidity 0.4.20; contract Test { uint public var1; address public var2; function test() public { var1 = 5; ...


4

It's done for DoS Protection, as explained in the Design Rationale wiki: Using sha3(k) as the key in the "secure tree" (used in the state and account storage tries): this makes it much more difficult to DoS the trie by setting up maximally unfavorable chains of diverge nodes 64 levels deep and repeatedly calling SLOAD and SSTORE on them. Note that this ...


4

I think, I have an idea. An important property of the Modified Merkle Patricia Tree is that it’s versioned. You can take a tree version 1 with root hash H1, insert new key-value pairs into the tree, and you will get a new tree version 2 with root hash H2. However, H1 will still be in the database, will still be accessible, and will still denote the complete ...


4

The number of transactions will always be even in a merkle tree (even number of leafs). If you happen to have an uneven number of transactions, the last transaction will be doubled for the construction of the merkle tree.


4

First, it should be noted that there is no such thing as a "plain Merkle Trie". The Merkle tree found in Bitcoin is not a radix tree (trie). The main reason Ethereum uses a Patricia Trie for transactions is simply uniformity. The current protocol specifies exactly one kind of tree-like data structure. Switching to a standard Merkle tree would require ...


3

Appendix D of the Yellow Paper, in defining the node types, states (italics mine): Leaf: A two-item structure whose first item corresponds to the nibbles in the key not already accounted for by the accumulation of keys and branches traversed from the root. The hex-prefix encoding method is used and the second parameter to the function is required ...


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


3

What exactly are the problems in bitcoin's idea of blockchain that this new data structure is solving? Bitcoin itself uses Merkle trees (and therefore Merkle proofs) - it's not a new concept. Ethereum had to introduce something more complex - the Merkle Patricia tree - to store its state data. In short, state data is updated often, and this doesn't fit ...


3

I believe that the hash of the empty string is the code hash only until the constructor returns the body code. I always find the yellow paper hard to read, but if you continue reading the Contract Creation section, there's an equation 98 which appears to show the code hash being stored with the code returned by the constructor. The text that follows that ...


3

Each node in the trie is identified by it's hash. Suppose there is a leaf with encodedPath 0x01 and a value 0x78 (I omit some things like even/odd coding for simplicity): leaf [0x01, 0x78] The hash of this node is calculated as hash1 = sha3(rlp([0x01, 0x78]). Suppose now there is a root, which is a branch node, where the 2nd nibble points to the leaf ...


Only top voted, non community-wiki answers of a minimum length are eligible