Blockchains : A sneak peek into the DS
The brainchild of Satoshi Nakamoto , Blockchains is a concept which was initially proposed with a cryptocurrency, but has now grown leaps and bounds. The fact that “Satoshi Nakamoto” till date remains a pseudonym , depicts the power of blockchains.
The main concept of blockchains is it keeps information distributed. There is no concept of a central database in this technology. Everyone knows everything, and each monitors that others don’t manipulate the data, thus ensuring data integrity.
Please make a note that cryptocurrency use Blockchains (they are an application), but they are not the concept. Blockchain is an independent concept which has many many applications.
I would like to give an example of Google Docs here.
What happens when people write on the same doc?
With traditional text editors users need to transfer the documents back and forth, losing time, energy and likely losing track of the versions.
With Google Docs, instead, all the users involved have access to the same document at the same time, and that document together with the updates are always visible real-time to each of them.
The same thing happens with the Blockchain compared to traditional databases. There is a ledger, everyone in network pushes it’s changes to the ledger. Miners verify the data and a block is appended to the chain of previous blocks (BlockChain).
Before adding more to the concept let’s build some basic data structures which we need for implementing Blockchains.
Hash Pointers:
Simply, a hash pointer is a kind of data structure that contains two parts
- pointer to where some info is stored
- (cryptographic) hash of the info
(Smells like a node of Linked List) .
Ok so why hash? For those who still are wondering what a hash is, it is a simple and one way encryption of a text of variable size to a fixed size encrypted code calles Hash. Let’s examine the terms I used here :
One-way hash : Given text you can encrypt to find the hash, but you can’t do the reverse of it, given hash you can’t decrypt it to get back text.
Fixed Size: No matter the input size of text is, output remains of fixed size. The size of Hash is fixed.
How does hash pointer helps us? We can verify easily if the data a pointer points to has changed or not. Just hash the data and check if it is the same as the hash in pointer.
Now let’s build some data structures using hash pointer:
Linked List with Hash Pointer (Blockchain)
Yes this very Data Structure is called Blockchain.
A simple linked list is a data structure in which the objects are arranged in a linear order. One node holds some data and address of next node.
In a blockchain, the pointer is replaced by hash pointer. So along with address you also maintain the hash of the data of node current node is pointing to.
Advantage blockchain has over has simple linked lists ? Answer is Temper Evidence.
Now since you have hash of all the nodes, any changes made to the nodes can easily be detected by comparing original hashes and computing new hashes.
Suppose an adversary tries to mess up with data of block one shown in figure.
Hash of Block 2 can be used to verify the data of block 1. Now let us suppose he also changes the hash of Block 2 (figure below). In that case, since contents of Block 2 have been changed Hash of Block 3 shall work as counter check. Now one question that arises here is, what id he changes all the hashes throughout the blockchain ?? He can definitely get a blockchain in the very form he wants. Please ponder over it, and we shall discuss more about it in comment section.
One more very powerful data structures we make using nodes is Binary Tree. We just replace normal nodes with has pointers and get a Merkle Tree.
This data structure does all things that a blockchain can do, but considerably reduces the complexity from linear to log . Every node now has two hasp pointers, pointing to left and right child.
To verify data integrity we just have to match the hash data of a node with it’s parent’s hash. Thus at max it takes O(Log n) time.
Conclusion
The images i have used have been shamelessly copied from google. ( I was not going to make them, anyways i suck at it :p ).
For any queries mail me at unishubh1@gmail.com. You can read more articles on my personal blog www.smartscribs.com
