Release of Kelvin — Dusk Network’s Merkle-Tree toolkit, Library and Backend
Kelvin is designed to combine the advantages of immutable data-structures, on-disk persistence, and content-addressed trees (aka Merkle trees).
Kelvin is created by Dusk Network, and has been an indispensable tool for modeling truly blockchain-optimized data-structures that are used by the transaction model and the smart contract engine.
Furthermore, Kelvin reduces the overhead caused by database structures that are designed for mutable data (as opposed to the immutable data / append-only data we need for the blockchain use case).
Kelvin on Github (click!)
Why Kelvin? Some database education!
A data structure (DS) is a way to organize data and a database (DB) is a way to store data structures on disk or on memory. We all know that blockchains are immutable and thus that they deal with append-only data since we do not want to ever remove confirmed (i.e. mined) transactions. Because of these properties, it is desirable to organize transactions in data structures that work well for fast insertion (append) and retrieval operations (lookup), and are easy to keep consistent (i.e. alike) even across distributed network nodes.
Merkle Trees (we’ll explain what these are later) are commonly used as a data structure (DS) that makes sure that the data is consistently stored across all nodes in the network. Since these nodes need to store the DS on a disk or memory, they use a DB backend (for example, Ethereum uses LevelDB by Google). However, these DB’s were created to store mutable data, and not immutable data, which means that additional logic is needed to prevent cached values from going stale.
Furthermore, accessing a DB on file is ‘expensive’, therefore DBs are cached. Managing this cache introduces even more overhead/complexity as it needs to be kept in sync with what is stored on file. Hence it needs to be invalidated/refreshed regularly.
Kelvin introduces a layer that separates Merkle tree data structures from the DB backend. It hides all the complexity of having to deal with the overhead above (cache invalidation, data mutability, interconnectedness with a single DB, etc), introduces optimizations for append-only operations and makes it easy to swap between various types of DS and DBs at will.
So what are Merkle Trees?
Merkle trees are one of many tools used by cryptographers to guarantee that in distributed networks (such as Blockchains) each and every single node — wherever they may be — is aware of the current state of the entire network. It is one of the vital components of the blockchain’s “database” .
A Merkle Tree looks like this
In this picture you can see that 4 transactions are made, transaction A, B, C and D. And their respective hashes are stored in the Merkle Tree (we call these leafs) of which further combinations are also hashed until only a Root Hash remains. Note: Hashing produces a shorter hashed key that is quicker and easier to find than the original value.
In the blockchain, only the Root Hash is stored. Every node that connects to the blockchain needs to reconstruct everything that has happened (we call that reconstructing the state). The Root Hash can be used by these nodes to check that their state has been correctly calculated.
Applicability in practice
Through Merkle Trees we can efficiently share which transaction outputs are unspent, the chain history, and even the account state and smart contract storage.
Kelvin is a layer that separates Merkle tree data structures from the DB backend. We have created Kelvin to reduce a lot of the overhead caused by DBs that are designed for mutable data structures. Kelvin introduces optimizations for append-only operations and makes it easy to swap between various types of DS and DBs at will. The latter is useful since traditionally the type of Merkle Tree / DS used creates inflexibility in regards to which DBs you could choose from.
You can read more about Kelvin on our Github (click!)
About Dusk Network
Dusk Network is an open-source and privacy-oriented blockchain based on years of academic research. You can use Dusk Network to create smart contracts that control digital assets and securities.
Release of Kelvin — Dusk Network’s Merkle-Tree toolkit, Library and Backend was originally published in Dusk Network on Medium, where people are continuing the conversation by highlighting and responding to this story.