A Simple Trie Pruning Algorithm

A very simplified trie structure: a top node and its descendants, with many levels. Only the leaf nodes has associated values (at least in Ethereum and in my personal project)
New value and nodes can be added without changing the original trie
A database with many tries, a bucket in this algorithm description
When the pruning algorithm starts, a new bucked is created. The new generated nodes are saved in that second bucket
Each selected trie will be copy to the new bucket

Attention: it is important that if a new trie is generated by a new block, DO NOT TRY to avoid saving one of your new nodes BECAUSE it is in the old bucket. All nodes must be recorded. Because if we do not save that node into the new bucket, trusting that it will go from the old bucket to the new one during the process of the selected top nodes, it may not be so because it may not be one of the nodes that are reached from the selected top nodes.

Extended Bucket

An account could have a pointer (a hash) to the top node of the trie that represents the contract storage associated with such account. So, there is a trie for accounts, and another trie for the storage (two key value database), but the concept of bucket is the same.

Stop and Resume

More than two buckets

Conclusion

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store