The Ontology Team

All of it begins with somewhat tree sapling. The sapling slowly grows a trunk, which then develops branches that finally sprout leaves, and earlier than you already know it the entire thing turns into a giant, lush inexperienced tree.
Now within the digital world additionally exists a tree, which works by the title of Merkle Tree. This tree is primarily composed of a root node, a gaggle of center nodes, and leaf nodes. The time period root node denotes the singular remaining node of a Merkle tree. A tree may very nicely have numerous leaf nodes, however leaf nodes can not have additional baby nodes. What objective does a Merkle tree serve? Allow us to discover out.

A Merkle tree is a non-linear, binary, hash tree-like knowledge construction. Every leaf node of the tree shops the hash worth of a knowledge factor, whereas a center node shops the hash of the hashes of it’s two corresponding baby nodes. The primary benefit of utilizing a Merkle tree is that a number of necessary items of knowledge will be verified relating to a specific knowledge factor or the info set as a complete with out the necessity to have entry to the total knowledge set. For instance, it’s doable to confirm whether or not a specific knowledge factor is part of a given knowledge set, or to show {that a} knowledge factor is definitely part of a bigger knowledge set with out having to retailer and parse the total knowledge set. It is because of these sensible functions that Merkle timber are generally utilized in industries reminiscent of Blockchain which can be basically based mostly on P2P networks that often contain eventualities the place knowledge is fetched from a supply whose credibility shouldn’t be assured, and thus the info is fetched and verified concurrently. Introducing Merkle timber to the equation might help stop points reminiscent of synchronizing a full knowledge set solely to comprehend it’s not verifiable, thus saving loads of time and bandwidth.

Within the case of blockchain platforms, typically talking, customers solely have to synchronize knowledge and transaction data that’s associated to their very own accounts. If the person have been to synchronize all the knowledge, effectivity will surely take a success. Thus, blockchains implement one thing generally known as the Easy Pay Verification (SPV) approach. Utilizing this verification approach, customers can construct and confirm Merkle proofs that solely require a small portion of the info to be synchronized to hold out the required verification course of. This immediately leads to decrease storage and community bandwidth necessities for the end-user.

With respect to the Ontology framework, Merkle proofs have varied software eventualities. One of many important functions is the era of a block Merkle tree with the transactions of the block appearing because the leaf nodes. These information function verifiable proof {that a} transaction has taken place on the chain. This text primarily goals at describing how Ontology carries out sure optimizations when implementing Merkle timber.

Most blockchains implement Merkle timber for particular person blocks with the transaction hashes appearing because the leaf nodes. Nevertheless, within the case of the Ontology blockchain, with rising block peak the block Merkle tree is dynamically up to date with the brand new block knowledge, resulting in a mechanism that’s barely extra sophisticated than the normal scheme. This provides rise to a pure concern: How do you retailer this Merkle tree? Allow us to check out three completely different solutions to that query.

This resolution entails caching the Merkle tree. However there are two shortcomings right here. First, as a result of caching would imply that the tree is saved in unstable reminiscence, when the machine is turned off or restarted, all the chain would must be traversed to be able to generate the entire Merkle tree, a comparatively time-consuming course of. Additionally, because the block peak will increase the tree could be up to date. Thus, the reminiscence requirement would additionally develop linearly, critically affecting scalability. So we are able to safely say that caching shouldn’t be an optimum long run resolution.

This resolution entails storing the Merkle tree in a Okay-V database (reminiscent of LevelDB). Because of the simplicity of a Okay-V pair relationship, it will be essential to specifically encode the important thing and worth to characterize a tree-like construction. Additionally, the retrieval operation for a specific node of the tree would require a number of learn operations, thereby lowering the general effectivity of the method.

For the reason that nodes of a Merkle tree are all hash values of a hard and fast size, if we have been to map each hash worth to an integer to type a 1–1 relationship, it will be doable to compress all the tree right into a one-dimensional integer array. The corresponding integer worth may first be calculated and the node knowledge will be saved on the corresponding indices. When accessing a specific node this integer worth will be calculated after which used to immediately entry a node factor’s knowledge bypassing utilizing it because the index. Storing this array in a file may clear up the issue of the linear development of the Merkle tree.

There are numerous alternative ways to map the tree nodes to an integer, with probably the most direct and intuitive one being layer by layer serialization based mostly on the depth of the tree. However there’s an issue with this technique of serialization. Each time the scale of the tree adjustments, the serial variety of a specific node will even change. Thus, all the knowledge must be parsed, serialized, and saved once more. This might tremendously have an effect on the effectivity of the system. Therefore, the steadiness of the file storage resolution depends tremendously on discovering an environment friendly serialization technique.

Other than node serialization, utilizing the file storage technique presents different points as nicely. As new blocks are consistently inserted and the block peak constantly will increase, the Merkle tree nodes are often up to date, and thus the file additionally must be up to date and consistently overwritten. That is one other issue that will trigger the effectivity to go down considerably.

To additional add to the complexity of this course of, it requires a knowledge consistency processing mechanism in place. Contemplating a hypothetical case that very nicely could happen, let’s say that the node components are being up to date and the method is about half full, and all of the sudden a brand new block is generated. This might lead to an inconsistency within the Merkle tree knowledge file.

In the event you carefully observe the Merkle tree node insertion course of, there are two kinds of nodes current within the Merkle tree: non permanent nodes, whose node hash is prone to vary as new nodes are inserted, and fixed nodes that don’t change with the insertion of recent nodes. It’s straightforward to display that the pre-condition required for a node to develop into a relentless node is for it, together with its baby nodes, to type a full binary tree. Additionally, it’s clear that the variety of non permanent nodes could be very restricted (simply log(n)). The variety of non permanent nodes will be decided from the fixed nodes, and after persisting within the reminiscence, will probably be modified as quickly as new nodes are inserted.

Subsequently, in Ontology’s resolution to the issue, solely fixed nodes are added to the file. One other attention-grabbing coincidence is that the sequence during which fixed nodes are shaped is a steady serialization sequence. Contemplating the above-stated details, there is just one motion carried out on the file, and that’s to append. And this solves the info inconsistency drawback that will come up on account of overwriting the file as nicely.

Because of the particular property of fixed nodes, it turns into evident that the kid nodes of a relentless node will make no contribution to the Merkle tree’s replace course of. Thus, those that will not be going to deploy nodes that present verification companies and are solely fascinated about calculating the most recent Merkle root’s hash worth can merely retailer the basis nodes of log(n) variety of full Merkle timber. This is sufficient to characterize all the Merkle tree standing, thereby decreasing the variety of nodes that must be saved to log(n) which is much more handy to retailer utilizing one key within the LevelDB. Updating the Merkle tree would then require just one learn and write operation. The info construction definition is as follows:

It’s clear from the compact Merkle tree’s definition that to be able to acquire the basis hash of the Merkle tree the hashes array must be parsed from proper to left successively.
The algorithm is as follows:

Herein, the hash_empty operate returns empty hashes and the hash_children operate returns the hash worth of the father or mother node that the 2 baby nodes’ hashes correspond to.

When new leaf nodes are inserted, dynamic updation is carried out based mostly on the present standing of the Merkle tree. The algorithm used so as to add new leaf nodes is as follows:

The adjustments that happen within the hash values and compact illustration knowledge within the storage file from the method of Merkle tree development are illustrated right here.

The primary determine is the Merkle tree’s single node standing:

When a brand new node b is inserted into the Merkle tree, it’s dimension will increase by 1. The brand new node b will be paired with node a to compute the hash worth c.

When a brand new node d is inserted, since an already full binary tree exists, the brand new node d is added individually in the interim. The tree dimension will increase by 1.

At this level, each time a brand new node is inserted into the tree, we are able to decide the positioning and hash values based mostly on the algorithm mentioned above.

Merkle tree has a variety of functions throughout completely different eventualities. Within the context of Ontology, one of many functions of Merkle tree is to report each new block within the type of leaf nodes and supply existential proof for the transactions that happen on-chain and are part of these blocks.

To be used instances the place the aim shouldn’t be offering a verification service, Merkle timber can considerably enhance the efficiency and storage capability of consensus nodes. Ontology information and shops solely the important thing nodes when implementing block Merkle timber. Because of this technique, we are able to replace the Merkle tree utilizing only one learn and write operation on LevelDB. The time complexity is lowered to O(log(n)).

Furthermore, when offering a verification service, the answer supplied by Ontology can tremendously simplify the frequent storage file overwriting concern and assist keep knowledge consistency by decreasing the operation to simply appending the file.

So, do you see and respect the magic of Merkle timber now?

Are you a developer? Ensure you have joined our tech group on Discord. Additionally, check out the Developer Heart on our web site, there you’ll find developer instruments, documentation, and extra.

Supply hyperlink