Merkle Tree – Tamper-evident Binary Tree
Uncategorized

Merkle Tree – Tamper-evident Binary Tree

One can construct a binary tree similar to the blockchain that places hash pointers in the place of regular pointers, to obtain a Merkle Tree. The leaf nodes in a Merkle tree contain data blocks, while the intermediate nodes in a hierarchical fashion contain the cumulative hash pointers to the respective subtrees. The hash pointer to the root node acts as a constant size commitment for the whole tree on the Merkle Tree; this is similar to the case of blockchains.

Contrary to blockchains,it is possible to append or insert a node from the Merkle tree with operations of 0 (log x), where x is the total number of data blocks (nodes) in the tree, as one needs an alternation of the shortest path from to the root from the leaf node when appending a data block.

If a malicious error causes a change in the data in any node of the tree, it will be evident to all users holding the hash pointer to the root node. In the case of a network, the hash pointer may be stored as a commitment in the root node in a distributed fashion, having each entity, and in such a case, the Merkle Tree acting as a tamper-evident storage of data in a decentralized way.

Appending to a tree is similar to inserting a node, making this non-linear structure, to act as a generic set and not a list. To add onto that, Merkle Trees allow an 0(log x) proof of membership in all leaf nodes which are used for consistency in the data blocks. To prove membership in any leaf node in a Merkle Tree, one has to produce a 0(log x) size proof that is in the form of a sibling hash pointer along the shortest path to the root node from the leaf node. Similarly, tests may be provided to verify that data blocks are a certain subset of another collection of data blocks.

Patricia Tree: Tamper-evident Trie

In addition to the Merkle Tree and the blockchain, the Patricia Tree or Merkle Trie is a modified structure of the Trie data structure based on hash pointers and not regular pointers. A group of data blocks is stored in a format (key value) where the maximum length of the key values controls the tree’s depth. Therefore, in a Patricia Tree, operations like appending, insertion, proof of membership and others become 0(k), while commitments maintain to 0(1). This is the data structure used in the modern platform called Ethereum.

Blockchain Protocol

The success of blockchain technology is the flexibility and the wide range of protocols that data structures enable. To understand the protocols of the blockchain, we need to look at some functional components as below:

Network

The blockchain protocol establishes a consensus of members over a decentralized network in the respective protocol. Members who participate in the protocol may have different roles in the management of the authenticated data structure as is specified in the protocol.

Such roles may rely on a pre-specified set of permissions when they are needed to enable flexibility of the protocol. Consequently, the blockchain structure may be hierarchical or peer-to-peer, as and when required by the respective protocol.

Transactions

A transaction is a mutual contract between any entities in the blockchain network. However, a transaction can be coded as a Boolean logic in a complex multi-party contract, implemented as an executable script. This generic blockchain transaction is called a Smart Contract.

Transactions are the fundamental components of a blockchain protocol, while other components are built on top of the transactions. One may view a blockchain platform as a distributed ledger of transactions which are tamper-evident.

Ledger

This is a collection of transactions that are stored in a Merkle Tree form. To ensure tamper-evidence of the transactions using a constant size. Each transaction set recorded as a Merkle Tree is included in the block’s data segment, and they are stored chronologically in a blockchain ledger as per their time stamps.i.e., in the form of a linked list.

Verification

The blockchain is meant to be a ledger of transactions that are decentralized. Each transaction between to users in the network needs a verification by the network, without any independent arbitrator. This is done by the use of a verification scheme in the protocol.

Practically, the verification scheme is normally implemented as a part of a script that is executable resulting in either rejection or acceptance of the transaction specified.

In some practical applications of blockchain technology. The routine of verification also connects the current transaction to the previous transactions that still exist in the blockchain, which has already been verified as inputs. Depending on the application, the verification scheme may be created in such a way that there is public verification in the transactions, or it may be entirely permissible.

Consensus

In the Merkle Tree, the transactions are grouped together, and the block that contains the tree is recorded in the blockchain ledger. In a distributed network, creating a block and appending it to a ledger should also be decentralized. The blockchain technology is flexible enough to handle appending processes known as mining that is decentralized.

Irrespective of the mining process which updates the blockchain ledger, it is important to ensure that the ledger is accepted across the network anytime. This calls for a consensus scheme in the protocol.

This decentralized consensus makes sure that a consistent version of the blockchain ledger amongst all the users of the network, and provides the most important tamper-resilience and tamper-detection property to the blockchain. If any member brings into the equation an inconsistency in the ledger through mining, the other users have the power to negate the block that the user appended and rectify the ledger in the block by forking.

Depending on the applications nature and the network structure, specific consensus schemes that ensure tamper-resilience may be constructed for the blockchain. It is important to note that mining and consensus schemes constitute the core of the blockchain protocol, and should be chosen.