Adaptive State Trie Pruning in Blockchains
Internship Topic
Context
Since its genesis in late 2008[¹], Bitcoin had a rapid growth in terms of participation, number of transactions and market value. This success is mostly due to innovative use of existing technologies for building a trusted ledger called blockchain. In this system, user participants sign transactions with their private keys and broadcast them on an open peer-to-peer network. These transactions are then confirmed (i.e., totally ordered and cryptographically linked to the blockchain) by miner participants and broadcast across the network. Moreover, both transactions and blocks that are broadcast are validated (applying the predefined rules) and diffused by each peer (i.e., participant) in the network, and invalid ones are discarded. This way, the participants collectively build a trusted ledger of transactions where they are confident about the balances of each other.
Ethereum[²] took this vision one-step ahead and introduced a blockchain that allows users to develop, run and use smart contracts³. A smart contract is a collection of code (its functions) and data (its state) that resides at a specific address on the Ethereum blockchain. For efficiency, in Ethereum[⁴], unlike in Bitcoin, every block contains a state root (the root hash of a Merkle Patricia tree, i.e. state trie) which stores the entire state of the system: all account balances, smart contract storage, smart contract code and account nonces are inside. However, one of the important issues about state tries is the large amount of data that users are required to store[⁵]; over little more than three months of operation, the amount of data in each Ethereum client’s blockchain folder can be ballooned to an impressive 10–40 gigabytes.
To tackle this problem, a state tree pruning approach has been proposed³. The idea is to count the references to track when nodes drop out of the state trie, and at that point put remove them: unless the same node somehow becomes used again within the next X blocks. The nodes that pass X number of blocks should be permanently deleted from the state trie. Essentially, only the trie nodes that are part of the current state are stored (recent history), but the history older than X blocks is not stored. However, finding the right X value is not trivial and depends on the number and type of the transactions issued at that time. Moreover, X may evolve during the time since the overall state of the blockchain network is dynamic.
Objective
Based on this observation, the objective of this internship is to develop an adaptive approach for making state trie pruning efficient and to study the implications of the developed approach. To this end, an adaptive parameter tuning approach will be used in order to find the dynamic X value. The approach will be first tested on a simulator and then on a private Ethereum network.
The successful candidate will join the Laboratory for Trustworthy, Smart and Self-Organizing Information Systems⁷ (LICIA) at CEA LIST.
The developed approach will be the base for a future PhD study focusing on a new scalable blockchain protocol.
Methodology
The intern will have the following responsibilities:
Preparing a state-of-the art about state tries in blockchain systems,
Preparing a state-of-the art about adaptive parameter tuning approaches,
Developing a simulation model (together with its automated tests) running on a single node on one computer,
Developing the final design of the approach on Ethereum and testing it on a private Ethereum network.
Competences
Being Master 2 in Computer Science/Engineering.
Knowledge about distributed systems and/or multi-agent systems in general.
Knowledge about the blockchain technology and smart contracts is a plus.
Good experience in programming in any language (but we will use Java)
Means used: distributed systems, distributed computation, multi-agent systems
Languages: Solidity, Java, etc.
Software: Ethereum, Geth, Eclipse.
Level required: Bac + 4/5
Duration: 6 months
Formation required: Engineering / Masters
Possibility of pursuing a thesis: Yes
Venue of the internship: CEA, Centre de Saclay Nano-Innov, 91191 Gif-sur-Yvette, France
Contacts
- Önder Gürcan: onder.gurcan@cea.fr 01 69 08 00 07
References
[¹]: S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. https://bitcoin.org/bitcoin.pdf, last access on 20/04/2018.
[²]: Ethereum Project, https://www.ethereum.org/, last access on 20/04/2018.
[⁴]: Ethereum yellow paper: Ethereum: A Secure Decentralised Generalised Transaction Ledger, EIP-150 Revision, https://ethereum.github.io/yellowpaper/paper.pdf, last access on 20/04/2018.
[⁵]: Vitalik Buterin, State Tree Pruning, https://blog.ethereum.org/2015/06/26/state-tree-pruning/, last access on 20/04/2018.