Sparse Merkle Tree Introduction

Introduction

The goal of this post is to provide an introduction to Merkle Tree and its especial instance Sparse Merkle Tree. Key building block of blockchain technology is Merkle Tree. Invented by Ralp Merkle, a hash pointer of group of transactions stored in binary tree is a powerful concept. It enables the nodes to run on any type of hardware including IOTs.

So what is Merkle Tree? It is data structure of hashed transnational data. Merkle tree are recursively constructed, starting in the leaves where the hash of the associated data is computed. The most common tree structure is binary tree. The figure below shows the data and hashing structure.

This structure enables the data validation, called Merkle proofs without reviling or re-hashing a complete dataset.

Merkle Proof Explained

There are two types of proofs that can be performed: Proof of Membership and Proof of Non-membership. So, how does it works? If we want to verify that value X1 really exists, we need to provide the following information: data set in question, hashed root and hashed leave. All intermediate nodes concatenate the hash from its children and uses it as the input to the hash function. Hashing is one way encryption function, and it is intended to be collision free, so no two plaintext hashes should be the same.

So in order to find proof of membership, X1 doesn’t need to be revealed but the hash of the X1 should be provided. Also the rest of the data that we need are just parts of the tree (grayed boxes), and this will allow us to be able to calculate the hash value of the tree root and compare it with the provided one.

Ethereum Example

In each block Ethereum is using three different Merkle Roots, and they are:

1. Transactions in the block

2. The state — addresses status

3. Transaction fulfillment data and receipts

Ethereum uses a special type of Merkle tree called the ‘Merkle Patricia Tree’. By using such protocol in the network, it allows users to get answers to the following financial related questions:

  1. Does the specified transaction exist in the block?
  2. Does the specified account exist?
  3. What is the current balance of the specified account?
  4. How many events of the certain type have been performed by the specified address for n number of blocks?
  5. What result will be obtained after the transaction fulfillment for the specified smart-contract?

The following image shows the Ethreum block header information including the three hash roots that we mentioned earlier in this section:

The header field definitions are available in section 4.3 of the yellow paper.

For more information go to:

https://github.com/ethereum/wiki/wiki/Patricia-Tree

Sparse Merkle Tree

Sparse Merkle Tree is a variation off the standard Merkle Tree, where contained data is indexed and each data point is placed in the leaf that corresponds to its index. Sparse Merkle Tree has been first proposed by Laurie and Kasper. It is based on the idea of a complete Merkle tree of an intractable size.

The key observation here is that such a tree contains many empty leaves and is therefore sparse. Sparse Merkle Tree found a use in Plasma Cash implementation where it is used to store information about deposited assets. Every Plasma Cash asset has a unique ID. Whenever an asset is transferred to a new user, a transaction is included in the sparse Merkle tree at the asset’s index. Proof of inclusion is used to prove that a given transaction history is valid.

The real use of Spare Merkle Tree is when proof of non-inclusion is performed as we know the exact position of the asset index.

The advantages of Spare Merkle Tree vs. Binary Merkle Tree are as follows:

  1. As we have seen, each asset gets a unique ID and that ID has exactly one transaction in the block.
  2. When a unique ID is not assigned to an asset, you can proof that with the same mechanism as the assigned one.

References

Laurie, B., Kasper, E.: Revocation transparency. Google Research (2012), http: //www.links.org/files/RevocationTransparency.pdf

_________________________________________________________________

NewCryptoBlock consists of a team of engineers with extensive technology and business backgrounds, united by a passion for innovation, professional development and building high-quality software products. Innovative technologies have the capacity of bringing to life revolutionary ideas that can change and better the world compared to the way we know it.

info@newcryptoblock.io