Hello everybody hope you all had a great New Year eve. Since last week I promised focusing on cryptography and consensus we now see cryptography in detail.

We must have seen a lot of people associating the name blockchain with the word trust.

This is because that it creates a layer of trust to make transactions possible between two different parties. If not blockchains a third party is generally required to establish a layer of trust between them.

Cryptography in Blockchains

All the information that is stored in the ledger in a blockchain uses cryptography mechanisms. Later which the information can be accessed using cryptographic hash keys and digital signatures. Before we go into further details let me try to associate you people with fundamentals of cryptography.

Public Key cryptography : It is a cryptography mechanism by which a pair of keys : public and private keys are used to encrypt and decrypt the messages respectively. The public key is distributed widely to every user in the ecosystem whereas the private key is specific only to one user trying to decrypt the message. So with this mechanism any third person within or outside the ecosystem trying to eavesdrop into the particular channel of communication will only end up having the encrypted message.

Public key Cryptography

Credits : wikipedia

Digital Signature : Theoretically digital signature is a scheme for verifying the authenticity of digital messages or other documents using mathematical functions. But in implementation this is an exact opposite of Public Key cryptography where Private key is used to sign and encrypt (sign) the message and is decrypted (verify) using the public key. Though we say encrypt and decrypt just to understand it has got to do nothing with message security rather it verifies the authenticity of a particular message.

Digital Signature

Credits : wikipedia

Both Public Key cryptography and Digital Signature are asymmetric key cryptography methods since they use two different keys one for encryption and the other for decryption

Hashing : It is a one-way cryptography method by which message of any size can be transformed into a hash of fixed size. It is mathematically impossible to decipher the hash. There are several hashing mechanisms such as MD5,SHA-1,SHA-256 etc., One advantage with hashing is that no two different messages are found to have the same hash. There is this attack called as birthday paradox by which attackers potentially exploit this common key for two messages and predict the message easily. You may ask if it cant be deciphered where do we use this now. This mechanism is particularly used in password verification systems. It is not a exaggerated fact to state that it is even a standard for authentication systems. You may ask Sir since it applies to authentication only how do we use it in blockchains. Each and every block is hashed and added a reference to the next block. So this way to reverse any transaction is mathematically impossible. (remember immutability!)

Difference between hashing and encryption

Credits : ssl2buy

There is also another method of cryptography which is very least popular called Zero knowledge Proof. This is a method by which the very existence proves the message and no additional information about the message is revealed. There is a famous cave door analogy that helps understand this scheme better. Lets say that a cave has a front door that everybody knows and a backdoor that nobody knows. Let me say that I know there is a backdoor. I don't have to show whether the door is instead I can prove it by just entering at one end of the cave and exiting the other end. But for blockchains we only use cryptographic hashing now.

So now we are going to clearly see how every block in a blockchain is comprised actually. The data structure that powers blockchain is Merkle Tree. I know most of you wouldn't have heard this word at all. If you actually know how this works then this whole blog is a cakewalk for all of you. Before we see what is a merkle tree lets get clear of its origin. The purpose that merkle trees are used in databases is to verify individual records without the necessity to compare and review the databases in entirety. This is made possible with the help of hashing technique that forms a merkle tree. It was patented in 1979 by Ralph Merkle for the very first time. Following is the implementation of a Merkle tree based blockchain,

Merkle Tree

The term that is denoted by T is the individual blocks or transactions that happen in a blockchain. H denotes the hash of each block which is nothing but the Transaction details given as a input to the SHA-512 encryption system that generates a unique 512 bit hash output. The hash of the siblings are added and the hash of that sum is stored in the parent. In this way the tree is constructed until its root is achieved with only one ultimate hash that describes the entire blockchain. Now you understand why blockchains are no way linked lists. The Merkle root summarizes all the transaction details of a block in its header. This hash helps in maintaining the integrity of the data. If there is a slight change in any of the transaction details then the hash also changes. Any new entry to the blockchain will have the previous root meaning that it represents the entire existing transaction details in a blockchain. This way the new users in the blockchain will have the existing information in an ecnrypted form so that the data integrity is maintained in blockchains.

Simplified Payment Verification (SPV) is the method by which details of a block can be verified without downloading the entire chain which is a primary application of Merkle trees.

Instead of entire block information only headers are downloaded. Each block will have SPV nodes that are left to check whether the miners have verified the transactions within the block. This SPV method is utilized by some lightweight bitcoin clients.

Ethereum the most common blockchain framework used these days has a different data structure powering it called as a Merkle Patricia Tree. Before we see more about ethereum lets explore a little about Patricia trees.

Patricia Trees also known as the radix trees are space optimized tries meaning that each of the children have their common origin in their parent node. For looking up a string in a patricia tree almost all the operations should be same as that of a trie but differ in the fact some edges may consume multiple elements. One such example for a patricia tree is as follows where the way to lookup the word 'toasting' is self explanatory from the image.

Searching the word 'toasting' in a Patricia trees

Credits : wikipedia

Ethereum uses a modified trie namely the Merkle Patricia Tree an advancement to the tries. Each node in the trie is referenced by its cryptographic hash value which is a characteristic of Merkle trees. Also in a Merkle Patricia Tree there are three types of nodes namely : blank node, an empty node ; standard leaf node having the value and its hashkey ; extension node having the value and hashkey of some other leaf node. For more information on Ethereum and Merkle Patricia trees follow this link .

So that's all for the cryptography in the blockchains. Next week I will be writing about consensus in blockchains until then Happy Pongal holidays ! everybody.