Introducing Immutable State — Part 2

This article will review the architecture proposed in the first Caasiope Improvement Proposal (CIP) : Immutable State

The architecture proposed by Immutable State consists in using immutable objects instead of mutable objects in the current implementation. The main benefit of immutable objects comes from the possibility to have multiple threads working in parallel on the same object. The representation in memory of the ledger state and of the account are heavily impacted. A new merkle tree structure that have the required behavior is part of the proposal .The main objectives of this architecture are performance and code simplicity.

Account

Accounts are now immutable and represent the state of the account at a given point of time (CurrentLedger).

Mutable accounts are used when we are updating the ledger and should be used only by a single thread.

When the ledger is finalized, the mutable account is also finalized and becomes immutable.

Merkle Tree

The proposal introduces a custom implementation of a merkle tree that can store the state of every account and give a consistent hash based on the included items. The tree is optimized for insert, update, lookup and clone operations. The tree can be read by several concurrent threads once its has been finalized.

Properties :

• The tree is using a radix trie where every node has up to 16 children.
• The position of an item in the tree in determined by its key.
• The key that identifies an item is a byte array with fixed length.
• Leaf can be found at fixed depth and contains an item.
• Each node hash is computed from the hash of its children .

Behavior :

• Finalize : The tree can be finalized, the hash is computed and the trie becomes immutable.
• Clone : The tree can be cloned after being finalized, the copy can modify the new tree with modifying the original one.
• Insert : The item will be inserted at the end of the associated branch, any node belonging to the original tree that need to be modified will be replaced by a new node.
• Update : The item with the associated key will be replaced in the tree, any node belonging to the original tree on the path to the item will be replaced by a new node.
• Lookup : The tree can be retrieve an item based on the associated key or prove there is no item associated to this key.
• Hash : When the tree is finalized, the hash from every item or node that were modified is computed .

Ledger State

The ledger state is containing the list of the state of every account at the given point of time.

The ledger state is finalized when a new block is produced, the state hash is computed and can be compared with the hash provided by other peers on the network.

The final ledger state is thread safe and can be safely explored by any thread.

The ledger post state is a temporary ledger state built on top of a previous ledger state.

The post state is using a cloned version on the previous state’s merkle tree and will update it everytime a transaction is included in the new block.

The post state will replace the immutable state of an account by a new mutable state of this account at the given height.

When a new ledger is received from the network because a new block was created, we check if it is valid then we update our own ledger state.

We create a temporary post state on which to execute all the transactions included in the new block.

If the merkle hash of the temporary ledger post state is different from the one validated by the network, we will reject the block. This can happen if the node is using a different software version, a bug happened, or the network has been compromised.

The post state can be finalized and become the (final) state of the last ledger.

Conclusion

The architecture proposed in this Caasiope Improvement Proposal will greatly improve the performances by enabling lock-free parallelization. By migrating from a global state to a state contained in a single object, the complexity of business logic has been drastically reduced. This feature will simplify the implementation of new features in the future.

Looking for an opensource blockchain community ? Join us on www.caasiope.net