Ethereum state trie format change using an overlay

This is a proposal by @gballet, articles and resources collected here for convenience.

“During the 1.x workshop in Paris last weekend, a couple ideas have been discussed for the transition from hexary tries to binary tries. It has been agreed that each proposal should be published on ethresearch for comparison and further discussion.”

Overview article

“The proposed process introduces a transition period during which two trees are maintained. This has the advantage that the main chain can keep operating while the tree is being converted, and it also ensures that all accounts will be translated to a binary format.”

The main discussion for @gballet’s proposed is on ethresear.ch

“A hexary to binary conversion method in which new values are stored directly in a binary tree sitting ‘on top’ of the hexary, while the ‘historical’ hexary tree is converted in the background. When the process is finished, both layers are merged.”

"Quick and Dirty" prototype implementation in geth (a pull request)


Background

Understanding Trie Databases in Ethereum

Modified Merkle Patricia Trie Specification