Merkle Trees

Merkle Trees, Blockchain, and Cryptocurrency

In this article, we discuss Merkle Trees in the context of Blockchain and Cryptocurrency. Although Merkle Trees have many applications, it is predominantly used for blockchain. Since blockchain was first introduced through cryptocurrency, it is crucial that we first understand the concept and workings of blockchain technology and cryptocurrency. After that, we will dive into the details of a Merkle Tree and its salient features. The figure below shows how Merkle Trees, blockchain, and cryptocurrency relate to one another. We will proceed with explaining blockchain first since it is fundamental and relates to both cryptocurrency and Merkle Tree.

 

Merkle Trees

Blockchain

Blockchain is a specific implementation of a decentralized distributed network.. A decentralized network is one that can run without the intermediation of financial institutions, such as banks. A distributed network ensures that we have multiple nodes for data processing. However, distribution isn’t synonymous with decentralization. For example, Git offers a centralized distributed architecture. Essentially, Git is centralized because Git Remote Repository keeps every version of your software’s source code in a centralized server. This centralized server is publicly accessible for everyone on the network to track software changes in the source code throughout its development history. This is where blockchain truly distinguishes itself from other distributed networks because it is decentralized.  In other words, cryptocurrency is distinguishable from Git because it is not stored on a centralized server.

What is a decentralized network?

A decentralized network refers to a network that operates without the control of a principal entity, such as a financial intermediary. In other words, there is no single point of failure since there is no central node. Every node on the network contains the network’s entire configuration. Therefore, every node holds identical information, and all of them get updated whenever a transaction is processed. Since the network is updated automatically, a principal entity is not necessary for updating the network’s configuration. Furthermore, each node is capable of independent decision-making and has a particular authority on the network. Therefore, decentralized networks do not require an intermediary to control transactions. For these reasons, decentralized networks are arguably less vulnerable than centralized networks since there is no single point of failure and since it is not under a single entity’s control.

The Emergence of Blockchain Technology: A Historical Perspective

When the Internet first became available to the public in 1991, it altered the way people communicate with each other. With the development of the Internet of information, people started to exchange information freely and instantly without involving entities that charge intermediation fees. As of now, with Facebook, Twitter, Gmail, and other communication platforms, we can easily correspond and communicate with a person living at the other end of the world without paying any transaction costs. However, the internet does not permit people to exchange things of value freely and instantly, such as money, from our computers or smartphones. Although people can exchange information on Facebook, Twitter, or Gmail without paying any costs, people often cannot send money to other people without paying third-party fees. Specifically, transferring something of value over the Internet requires the involvement of a third party to verify the identity and the ownership of the sender of the valuable asset. Although there are some third parties, such as Venmo, that do not impose transaction costs, the majority of third parties charge heavy service fees.. Therefore, buyers and senders are often burdened with transaction costs whenever they transfer funds to someone else over the Internet or purchase something online.

However, blockchain provides people with the opportunity to send valuable assets online without paying any fees since the new technology is decentralized. With blockchain, an intermediary is no longer needed for authenticating transactions because blockchain technology has an innate trust mechanism built within the software. Because of the transparency and immutability blockchain offers, people can now send valuable assets to someone on the opposite side of the planet without paying any third-party fees. Therefore, blockchain permits people to exchange valuable assets over the internet with no transaction costs in the same way that social media has permitted people to exchange information without third-party fees. We will discuss the case study of a Bitcoin transaction to illustrate how blockchain ensures the transaction’s integrity. However, before, let’s formally discuss cryptocurrency and crypto assets with some examples.

Cryptocurrency

Cryptocurrency refers to a digital currency that is frequently used as a unit of exchange. Cryptocurrency is not an actual or physical currency, but a virtual currency that can be exchanged online. Currently, Bitcoin is the most valuable cryptocurrency, and as of now, the worth of a single Bitcoin is more than $33,000. However, cryptocurrency is not yet insured or backed by international governments because the value of cryptocurrency is not determined by any underlying physical assets such as gold or silver. Instead, cryptocurrency’s value is exclusively determined by economic principles of supply and demand. In other words, the value of cryptocurrency rises as its popularity increases.

Cryptographic techniques have been incorporated into the development and transaction of cryptocurrencies to make them secure and valuable. The increased security that cryptographic techniques provide has allowed certain forms of cryptocurrency to become popular worldwide. Currently, Bitcoin and Ethereum are the two most popular types of cryptocurrency. While Bitcoin is more valuable, Ethereum is more widely used. One reason Ethereum is more widely used is that it has faster transaction times than Bitcoin. A single Bitcoin transaction takes around 10 minutes; whereas an Ethereum transaction takes only 15 seconds. Accordingly, Ethereum transactions are forty times faster than Bitcoin transactions.

Below is a case study that demonstrates how a Bitcoin transaction is processed and what cryptographic techniques are involved in ensuring the security of the network that processes these transactions.

Case Study: A Transaction of Bitcoin Blockchain

Asymmetric cryptography is used to make Bitcoin transactions more secure by using a combination of Public and Private keys to ensure the integrity of each transaction. A private key is similar to the password you use to log in to your bank’s app. Like bank account passwords, private keys must not be shared with anyone. Otherwise, once lost, you cannot retrieve your private key and will never be able to reaccess your crypto funds (unless you find the key). In contrast, public keys are visible to everyone on the network. Public keys can be used by anyone to encrypt a transaction that can only be decrypted by your private key. Think of your public key as your account number that can be shared with anyone. Once you receive your funds, you have to use your password to log in to the app to spend those funds. By acting together, public and private keys make Bitcoin transactions more secure and valuable.

To initiate a Bitcoin transaction, you need a Bitcoin Wallet App on your smartphone or computer. To transfer Bitcoin, specify the number of Bitcoins you want to send and encrypt the message with the public key of the receiver to whom you are transferring the Bitcoins. After that, you will sign off the transaction with your private key to digitally timestamp the transaction and verify that you initiated the transaction.

Each node on the blockchain plays its role in the completion of a blockchain transaction. These nodes are machines offered by cryptocurrency miners to compute the hash of the chain’s next block. Miners refer to the people who authenticate cryptocurrency transactions by running complex algorithms on their computers. The miners offer their machines in return for a fixed number of Bitcoins associated with each transaction. A miner is a person just like you and me but has installed the required software on his/her system. Now let’s see what happens when we sign off the message and broadcast it over the network.

 

Once the message is broadcasted over the distributed network, the nodes verify each transaction’s legitimacy. This process includes the verification of sufficient funds in the Bitcoin wallet, the valid public key of the receiver, and the correct private key of the sender. After the verification phase is completed, the miners race among themselves to stumble upon the right nonce that will be combined with the hash of the previous block to generate the hash of a new block. Bitcoin uses SHA-256 to generate the hash of the new block. These calculations are done by Bitcoin’s software, and the calculation speed is directly proportional to the system’s efficiency. Once a miner finds the right hash, he/she shares that hash and all the associated calculations over the network. The new block is added to the chain once a consensus is established. After the specified Bitcoin transfer is complete, the miner who computed the hash is rewarded with cryptocurrency.

Notice that I haven’t gone into details concerning the consensus algorithm (proof-of-work) because it would then have to be explained in detail. Otherwise, it will be futile. Therefore, let’s leave it for another time.

Now that we have developed an understanding of blockchain and cryptocurrency, let’s move to Merkle Tree and see how it is used in blockchain.

What is a Merkle Tree?

Named after Randolph Merkle, a Merkle Tree is an information structure that encodes all of the data in the blockchain. In Bitcoin blockchain, a single block has the capacity to store around 1 MB of data. Therefore, a single block can store over a thousand transactions and even more. Each transaction has its own hash. The Bitcoin software links the hashes of all transactions from a single block until a single hash is generated for the entire block. Such a structure is represented in the below figure.

 

For the sake of simplicity, we have considered this case in which a single block contains only four transactions. However, recall that each block can store around a thousand transactions. The above diagram represents the Merkle root of the block, the Branches, and the Leaf nodes. The Merkle root of a block is used to generate a unique hash block by combining it with the hash of the previous block, the right nonce, the software version, timestamp, and other necessary information. Each transaction has a unique hash, and all the hashes of a single block combine to generate the hash of the entire block. Therefore, it becomes practically impossible to tamper with a Bitcoin transaction since we will have to alter all the hashes without being noticed.

Merkle Trees are efficient because they do not store complete files. Rather, they use hashes to encode the files into a smaller number, a 256-bit number in the case of Bitcoin transactions. These hashes are faster to compute compared to computing the whole database. Likewise, since a hash is unique for a single input, and no two inputs can have the same hash, we can easily identify if a transaction has been tampered with by checking its old hash. Since it is a distributed network, every node will have the same hash for a particular transaction or block. Therefore, it would be impossible to change the hash of a block on each node. In this way, Merkle Trees ensure the integrity of cryptocurrency transactions.

Merkle Tree offers a trust mechanism to verify the integrity of data. Therefore, blockchain technology provides an inherent trust mechanism through the utilization of Merkle Trees.