Research Summary: Ethereum Data Structures

Cryptography
1

TLDR

  • The paper’s main objective is to provide sufficient detail on the Ethereum data structures while retaining conciseness and enrichment with examples to improve clarity.
  • It illustrates the basic ideas and concepts behind Ethereum data structures and encodings.
  • It proceeds to an Ethereum data structure representation in diagram form with detailed explanations.

Core Research Question

What are the detailed Ethereum data structures and encodings like?

Citation

Jezek, K. (2021). Ethereum Data Structures. ArXiv [Cs.CL]. doi:10.48550/ARXIV.2108.05513

Background

  • Ethereum Yellow Paper: The paper that describes a protocol called Ethereum.
  • Parity Ethereum: An open-source software solution that allows an individual to run a node on the public Ethereum network, or any other blockchain network that uses the Ethereum protocol.
  • Geth Ethereum: The command-line interface for implementing an Ethereum node in Google’s Go programming language.
  • Search Tree: A tree data structure used for locating specific keys from within a set.
  • Binary Search Tree (BTS): A binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left subtree and smaller than the keys in all nodes in that node’s right subtree.
  • Patricia Trie (Radix Tree): A data structure, a more space-efficient trie in which each node that is a unique child is merged with its parent, and edges can be represented either as sequences of elements or as single elements.
  • Merkle Tree (Hash tree): a tree in which every “leaf” (node) is labeled with the cryptographic hash of a data block, and every node that is not a leaf (called a branch, inner node, or inode) is labeled with the cryptographic hash of the labels of its child nodes.
  • Merkle Patricia Trie: A data structure that combines and extends Patricia trie and Merkle tree.
  • RLP (Recursive Length Prefix): A function that serializes a set of input arrays into one array.
  • HP Encoding (Hex Prefix Encoding): A function whose purpose is to encode any sequence of nibbles into the binary stream so that two (4-bit) nibbles compose one (8-bit) byte.
  • Keccak: A hash function that Ethereum uses, which is an original implementation of SHA3 available before SHA3 became official.
  • Ethash: The protocol Ethereum uses for mining and validating that the mining work has been done.
  • Unspent transaction output (UTXO): A way that transactions transfer balances between addresses and the balance must be transferred as a whole.
  • Ommers: A list contained in Ethereum block, which consists of headers of blocks that were successfully mined, but eventually did not become part of the mainline.

Summary

  • The author highlights the importance of understanding Ethereum data structures because they are complex and specific only to the blockchain network.
  • They detail the basic algorithms and encodings for retrieval and cryptography.
  • The author subsequently developed the investigation into the general idea of blockchain, blocks, and transactions.
  • They further conducted Ethereum data structures and created different diagrams with detailed explanations.
  • This paper is structured as follows. Fundamental data structures are described first; an extension of these structures in the form of Merkle Patricia Trie is formulated then. After that, the structure of the block is provided, followed by details about the Trie structures used for Ethereum data representation.

Method

  • Tree and Tries
    • Search Trees
      • Nodes are assembled from the root down to children and represent all the keys stored in that tree. Each node branches left or right to encode binary one and zero for the current position of one of the keys.
      • This data structure has the advantage of saving storage for data whose keys often have the same prefix.
      • An obvious drawback of search trees is that they have to traverse multiple children if they don’t branch.
    • Patricia Trie
      • To overcome the shortcomings of the tree structure, Trie is proposed as a new structure in which the data representation is defined in the form of a table, with the columns of the table being nodes and the rows being branches.
      • The trie data structure can be expressed as a two-dimensional array, so it is also effective in terms of speed.
      • Tries have a large memory overhead, especially when the structures are sparse. This problem can be overcome by representing paths with linked lists such that all possible branches from a node are represented as trees, forming a forest of trials from all nodes.
      • Another drawback of the original Trie structure is that it only groups common suffixes of keys. This shortcoming can be fixed by Patricia Trie where each node contains a set of bits that can be skipped when matching keys since all keys in the dataset have the same path.
    • Merkle Trees
      • A Merkle tree is a data structure for digitally signing a data set for quickly checking data integrity.
      • The purpose of this data structure is to allow parties to check the consistency of records without the need to replace the dataset itself.
      • A Merkle tree prevents malicious or unintentional modification of data by providing a unique hash that identifies a record.
    • Merkle Patricia Trie
      • It is organized as a tree, with each node hashed in the Merkle proof sense and common paths grouped in the Patricia trie sense.
      • The design, which tightly couples data structures and database schemas, made it easy to store structured data in unstructured databases such as key-value databases.
      • This new structure allows the intersection of keys and suffixes to be grouped into one node, and nodes can be used for branching only when branching is required.
  • Data Structures Encoding
    • Hex Prefix Encoding
      • HP is a hexadecimal prefix encoding function that aims to encode an arbitrary sequence of nibbles into a binary stream such that two (4-bit) nibbles form one (8-bit) byte.
    • Recursive Length Prefix
      • RLP is a recursive length prefix function that serializes a set of input arrays into an array, allowing trie nodes to be converted into flat byte arrays.
    • Ethereum stores both hash values ​​and plain values ​​together in its database.
      • keccak(RLP(node)) \rightarrow RLP (node)
      • key \equiv keccak(RLP(node))
      • value \equiv RLP(node)
      • Extension value \equiv RLP(node)
      • Branch node \equiv [branches, value]
      • Leaf node \equiv [HP(prefix + path), value]
    • Node In-lining
      • If the child node’s RLP encoding is shorter than 32 bytes, no hash is computed and the node is stored directly within the parent node.
  • Ethereum data structures
    • Transactions Trie
      • A transaction is mapped in the trie to compose a key-value pair where both the index and the transaction are RLP encoded.
      RLP(index) \rightarrow RLP(T)
  • The structure T consists of nonce, gas price, gas limit, address to receive, value, EVM code, data, and so on.
  • Receipts Trie
    • The result of each transaction execution is captured in the Transaction Receipt Trie.
    • The Receipt Trie has the following structure. The key is a transaction index and the value is a receipt R. They compose a key-value pair:
      RLP(index) \rightarrow RLP(R)
  • The receipt R consists of cumulative gas, a set of logs, a bloom filter, and a status code of the transaction result.
  • World State Trie
    • The World State Trie is a mutable data structure that captures the latest blockchain state.
    • Every account A stored is mapped via an account address.
      keccak(address) \rightarrow RLP(A)
  • Structure A contains a nonce, balance, storage root, and code hash.
  • UTXO-Based and Account-Based blockchains
    • One of the advantages of UTXO is that transactions can operate in parallel since there is no dependence between them.
    • UTXO can also evolve better because no data must be sought to update the global balances of accounts. But it’s impossible to easily get user balances in account-based ones.
    • Ethereum transactions may deduct a certain amount from the account directly; Bitcoin and other UTXO-based systems can transfer only the entirety of the amount and receive an exchange.
  • Storage Trie
    • Storage Trie is directly modified by a Smart Contract byte code employing the SLOAD and SSTORE instructions.
    • The author gives an overall view of the variable format produced by the Solidity current:
      • Statically Sized Variables
      • Maps
      • Dynamic Arrays
      • Byte Arrays and String
  • Authenticated Storage
    • Merkle Patricia Tries are used across the blockchain among other reasons to provide authenticated storage.
  • Pseudo Structure: Secure Trie
    • Being a wrapper of another trie, Secure Trie is not an independent data structure, but generally describing keys or paths in the trie are hashed.
    • In Ethereum, World State Trie and Account Storage Trie are Secure Trie.

Results

Discussion and Key Takeaways

  • Patricia Trie was initially proposed for binary trees, but it is practically used for N-ary trees these days.
  • The hash representation for the key is calculated from the whole node as represented by the RLP.
  • Resource-intensive computing miners perform in exchange for an award is part of the consensus protocol.
  • Miners’ effort over the mining blocks outside of the mainline becomes pointless after the creation of a chain of 6 consecutive ommers as there is no reward for longer ommer chains.
  • The transaction must initially be validated by a miner and in an ad-hoc sequence synchronized by all nodes involved in the blockchain network.

Implications and Follow-ups

  • The general idea of blockchain is generic and special blockchain protocols can store data such as blocks and transactions differently.
  • Ethereum stores Smart Contracts as well as transactions.
  • UTXO-based and Account-based blockchains have their pros and cons and the interoperability of both systems is under analysis.
  • Ethereum suffers from memory bloat and performance issues due to the amplification of reads and writes caused by the continuous computation of hashes.
  • The scope of this work is limited to data structures used in Ethereum. The author does not discuss in detail areas such as block mining, verification, execution, and Smart Contract creation.

Applicability

  • The paper is particularly worth reading for researchers and practitioners interested in extending, modifying, building on, conducting research on, etc. on Ethereum.
4 Likes