Data Structure

Let’s start at the beginning. As with all other blockchains, the Ethereum blockchain begins life at its own genesis block. From this point (genesis state at block 0) onward, activities such as transactions, contracts, and mining will continually change the state of the Ethereum blockchain. In Ethereum, an example of this is an account balance (stored in the state trie, as shown in Figure 9.4), which changes every time a transaction, in relation to that account, takes place.

Importantly, data such as account balances is not stored directly in the blocks of the Ethereum blockchain. Only the root node hashes of the transaction trie, state trie, and receipts trie are stored directly in the blockchain.

You will also notice, from Figure 9.4, that the root node hash of the storage trie (where all of the smart contract data is kept) actually points to the state trie, which in turn points to the blockchain. I will zoom in and cover all of this in more detail soon.

There are two vastly different types of data in Ethereum: permanent data and ephemeral data. An example of permanent data is a transaction. Once a transaction has been fully confirmed, it is recorded in the transaction trie and never altered. An example of ephemeral data is the balance of a particular Ethereum account address. The balance of an account address is stored in the state trie and is altered whenever transactions against that particular account occur. It makes sense that permanent data, such as mined transactions, and ephemeral data, such as account balances, should be stored separately. Ethereum uses trie data structures (as broadly outlined earlier) to manage data. The next section will take a detour and provide a quick overview on tries.

Standard Trie

Figure 9.5 shows the structure of a standard trie that stores words. Each character in the word is a node in the tree, and each word is terminated by a special null pointer.

Patricia Trie

Figure 9.6 shows the structure of a Patricia trie that stores words. The storage is more compact than the standard trie. Each word is terminated by a special null pointer.

Rules for Adding a Word to the Patricia Trie

Patricia tries group all common characters into a single branch. Any unusual characters will constitute a new branch in the path. When adding a word to a Patricia trie, we exhaust all the characters and then add the null pointer (terminator), as shown in Figure 9.7.

Rules for Deleting a Word from the Patricia Trie

This is the same as with a traditional trie, except for when deleting nodes (from the leaf back to the root), we must ensure that all parent nodes must be in possession of at least two child nodes. It is okay for a single child node to just have characters and a null pointer (this occurs in Figure 9.7, at the end of every word). It is also okay for a single node to just have a null pointer (this occurs if a shorter word is contained in a longer word). See Figure 9.7, which illustrates how wood and wooden coexist in the same trie.

Importantly, when deleting from a trie, a path cannot be left with a parent node that connects to just a single child node. If this occurs (when deleting, we need to concatenate the appropriate characters to resolve this). This is illustrated in Figure 9.8 (where we delete the word from the trie).

Similarities between the Trie and Patricia Trie

The runtime “O” for adding is O(mN), where “m” is the length of the string we are adding and “N” is the size of the available alphabet.

The runtime for deleting is O(mN), where “m” is the length of the string we want to delete and “N” is again the size of the available alphabet.

The runtime for searching is O(m), where “m” is the length of the string we are searching for.

Main Difference between the Trie and Patricia Trie

The main advantage of using the Patricia trie is in relation to storage.

The storage requirement “O” for the standard trie is O(MN), where “M” is the total length of all strings in the trie and “N” is the size of the available alphabet.

The storage requirement “O” for the Patricia trie is O(nN+M), where “n” is the number of strings stored in the Patricia trie, “N” is the size of the available alphabet, and “M” is the total length of all strings in the trie.

In short, you will have noticed a marked difference in the depth of the tries. The Patricia trie is less deep (shallower). This is because of the Patricia trie’s ability to group common characters (and concatenate null pointers to leaves).

Modified Merkle Patricia Trie

In the Ethereum state database, the data is stored in a modified Merkle Patricia trie, which means the root node of the trie is a hash of the data in its leaves. This design makes the state database on each node resistant to tampering, just like the blockchain itself.

Every function (put, update, and delete) performed on a trie in Ethereum utilizes a deterministic cryptographic hash. Further, the unique cryptographic hash of a trie’s root node can be used as evidence that the trie has not been tampered with.

For example, any changes to a trie’s data, at any level (such as increasing an account’s balance), will completely change the root hash. This cryptographic feature provides an opportunity for light clients (devices that do not store the entire blockchain) to quickly and reliably query the blockchain; in other words, does account 0x…4857 have enough funds to complete this purchase at block height 5044866?

State Trie : The One and Only

There is one, and one only, global state trie in Ethereum. This global state trie is constantly updated. The state trie contains a key-value pair for every account that exists on the Ethereum network.

• The key is a single 160-bit identifier (the address of an Ethereum account).

• The value in the global state trie is created by encoding the following account details of an Ethereum account (using the recursive-length prefix [RLP] encoding method): nonce, balance, storageRoot, codeHash.

The state trie’s root node (a hash of the entire state trie at a given point in time) is used as a secure and unique identifier for the state trie; the state trie’s root node is cryptographically dependent on all internal state trie data. The state trie’s root node is stored in the Ethereum block header corresponding to the time when the state trie was updated (see Figure 9.9) and can be queried from the block (Figure 9.10).

Storage Trie : Where the Contract Data Lives

A storage trie is where all the contract data lives. Each Ethereum account has its own storage trie. A Keccak 256-bit hash of the storage trie’s root node is stored as the storageRoot value in the global state trie (Figure 9.11).

Transaction Trie : One per Block

Each Ethereum block has its own separate transaction trie. A block contains many transactions. The order of the transactions in a block is of course decided by the miner who assembles the block. The path to a specific transaction in the transaction trie is via the RLP encoding of the index of where the transaction sits in the block. Mined blocks are never updated; the position of the transaction in a block never changes. This means that once you locate a transaction in a block’s transaction trie, you can return to the same path over and over to retrieve the same result. Figure 9.12 shows how the transaction trie’s root hash is stored in an Ethereum block header.

Concrete Examples of Tries in Ethereum

The main Ethereum clients use two different database software solutions to store their tries. Ethereum’s Rust client, Parity, uses RocksDB. Ethereum’s Go, C++, and Python clients all use LevelDB.

RocksDB is out of scope for this book. Let’s explore how three out of the four major Ethereum clients utilize LevelDB.

LevelDB is an open source Google key-value storage library that provides, among other things, forward and backward iterations over data, ordered mapping from string keys to string values, custom comparison functions, and automatic compression. The data is automatically compressed using Snappy, an open source Google compression/decompression library. While Snappy does not aim for maximum compression, it aims for very high speeds. LevelDB is an important storage and retrieval mechanism that manages the state of the Ethereum network. As such, LevelDB is a dependency for the most popular Ethereum clients (nodes) such as go-ethereum, cpp-ethereum, and pyethereum.

To learn more, we have to access the data in LevelDB using the appropriate Patricia trie libraries. To do this, we will need an Ethereum installation (see Chapter 5). Once you have set up your Ethereum private network, you will be able to execute transactions and explore how Ethereum’s state responds to network activities such as transactions, contracts, and mining. In the next section, I will provide code examples and screen captures from an Ethereum private network.

Get the Data

From this point, running the following code will print a list of the Ethereum account keys (which are stored in the state root of your Ethereum private network). The code connects to Ethereum’s LevelDB database, enters Ethereum’s world state (using a stateRoot value from a block in the blockchain), and then accesses the keys to all accounts on the Ethereum private network (Figure 9.13).

Click here to view code image

//Just importing the requirements

var Trie = require('merkle-patricia-tree/secure');
var levelup = require('levelup');
var leveldown = require('leveldown');
var RLP = require('rlp');
var assert = require('assert');

//Connecting to the leveldb database
var db = levelup(leveldown(
    '/home/user/geth/chaindata'));

//Adding the "stateRoot" value from the block so that
//we can inspect the state root at that block height.
var root = '0x8c777…2976';

//Creating a trie object of the merkle-patricia-tree library
var trie = new Trie(db, root);

//Creating a nodejs stream object so that we can access the data
var stream = trie.createReadStream()

//Turning on the stream
stream.on('data', function (data){
  //printing out the keys of the "state trie"
  console.log(data.key);
});

Decoding the Data

You will have noticed that querying LevelDB returns encoded results. This is because Ethereum uses its own specially modified Merkle Patricia trie implementation when interacting with LevelDB. The Ethereum wiki provides information about the design and implementation of both Ethereum’s modified Merkle Patricia trie and RLP encoding. In short, Ethereum has extended the trie data structures described earlier. For example, the modified Merkle Patricia trie contains a method that can shortcut the descent (down the trie) through the use of an extension node.

In Ethereum, a single modified Merkle Patricia trie node is one of the following:

• An empty string (referred to as NULL)

• An array that contains 17 items (referred to as a branch)

• An array that contains two items (referred to as a leaf )

• An array that contains two items (referred to as an extension)

As Ethereum’s tries are designed and constructed with rigid rules, the best way to inspect them is through the use of computer code. The following example uses ethereum.js. The following code (when provided with a particular block’s stateRoot as well as an Ethereum account address) will return that account’s correct balance in a human-readable form (Figure 9.14):

Click here to view code image

//Mozilla Public License 2.0
//Getting the requirements
var Trie = require('merkle-patricia-tree/secure');
var levelup = require('levelup');
var leveldown = require('leveldown');
var utils = require('ethereumjs-util');
var BN = utils.BN;
var Account = require('ethereumjs-account');

//Connecting to the leveldb database
var db = levelup(leveldown('/home/user/geth/chaindata'));

//Adding the "stateRoot" value from the block
//so that we can inspect the state root at that block height.
var root = '0x9369577...73028';

//Creating a trie object of the merkle-patricia-tree library
var trie = new Trie(db, root);

var address = '0xccc6b46fa5606826ce8c18fece6f519064e6130b';
trie.get(address, function (err, raw) {
    if (err) return cb(err)
    //Create an instance of an account
    var account = new Account(raw)
    console.log('Account Address: ' + address);
    //Decode and present the account balance
    console.log('Balance: ' + (new BN(account.balance)).toString());
})

Read and Write the State LevelDB

So far, I have shown how to access the Ethereum state’s LevelDB database using JavaScript on a local node. If you are familiar with GO and can work with Ethereum source code, there is an easier way. You could just import the go-ethereum source code in GO and call its functions to read and even modify the LevelDB database. The write function will not only change the values in the nodes but also update the root hash to reflect the changes. Specifically, the functions are in the following source code file:

Click here to view code image

https://github.com/ethereum/go-ethereum/blob/master/core/state/statedb.go

It contains methods such as GetBalance, AddBalance, SubBalance, and SetBalance to operate on the account balances. However, changing the state LevelDB in this way will change the data on only one node and will likely cause this node to go out of sync with the rest of the nodes on the network. The right way to change the state is to follow how go-ethereum processes a transaction and records it on the blockchain. That is out of scope for this book.