Learn the Linked List Data Structure by Building a Blockchain in JavaScript

Overview

Building a blockchain from scratch is an excellent way to understand both the intricacies of blockchain technology and fundamental data structures like linked lists. In this article, we’ll explore how to create a simple blockchain using JavaScript, highlighting how the blockchain resembles a singly linked list.

Now the question is what is a Blockchain?

A blockchain is a decentralized digital ledger. What that means? You can say it's a database that records transactions. Now what is transaction here? You can say it's data. That's mean blockchain store the data across many computers in a way that ensures security, transparency, and immutability means can't manipulate the data. Each block in a blockchain contains a cryptographic hash of the previous block, a timestamp, and transaction data. Still don't understand what is blockchain? Learn more

How it's related to Linked Lists?

A linked list is a linear data structure where each element, known as a node, points to the next element in the sequence. In a singly linked list, each node contains data and a reference (or pointer) to the next node in the list.

In blockchain, each block is like a node in a linked list:

Data: Contains transaction details.
Pointer: Holds the hash of the previous block.

This creates a chain of blocks, where each block points to its previous block, forming a linked list.

Let's build a Blockchain in JavaScript

You need nodejs latest version in your pc. So Download it.

Step 1: Program setup

Now create a file name blockchain.js. Our code will be here.

We need a cryptographic library that called crypto-js. This library is for generating hash. So hash means, You can give a data and a secret key to an algorithm and it will encrypt it. The encrypted result will be long form of string so that nobody can understand what is the data. Meaning we can abstract our data by encrypting it. And when we need to see the data we will decrypt it using the same algorithm with a secret key we provided on encryption time.

Now open the terminal and install it by this command:

npm install crypto-js

Step 2: Setting Up the Block Class

First, we need a Block class that will represent each block in our blockchain.

const SHA256 = require("crypto-js/sha256");

class Block {
  constructor(index, timestamp, data, previousHash = "") {
    this.index = index;
    this.timestamp = timestamp;
    this.data = data;
    this.previousHash = previousHash;
    this.hash = this.calculateHash();
  }

  calculateHash() {
    return SHA256(
      this.index +
        this.previousHash +
        this.timestamp +
        JSON.stringify(this.data)
    ).toString();
  }
}

SHA-256: We are using this algorithm
Block Class: Each block has an index, timestamp, data, the hash of the previous block, and its own hash. You can say it's the node of the linked lists.
calculateHash(): Generates a SHA-256 hash based on the block’s properties.

Step 2: Creating the Blockchain Class

Next, we need a Blockchain class to manage the chain of blocks.

class Blockchain {
  constructor() {
    this.chain = [this.createGenesisBlock()];
  }

  createGenesisBlock() {
    return new Block(0, "10/06/2024", "Genesis Block", "0");
  }

  getLatestBlock() {
    return this.chain[this.chain.length - 1];
  }

  addBlock(newBlock) {
    newBlock.previousHash = this.getLatestBlock().hash;
    newBlock.hash = newBlock.calculateHash();
    this.chain.push(newBlock);
  }

  isChainValid() {
    for (let i = 1; i < this.chain.length; i++) {
      const currentBlock = this.chain[i];
      const previousBlock = this.chain[i - 1];

      if (currentBlock.hash !== currentBlock.calculateHash()) {
        return false;
      }

      if (currentBlock.previousHash !== previousBlock.hash) {
        return false;
      }
    }
    return true;
  }
}

Blockchain Class: Manages the chain of blocks means the list.
createGenesisBlock(): Creates the first block in the blockchain.
getLatestBlock(): Retrieves the latest block in the chain.
addBlock(newBlock): Adds a new block to the chain, setting its previous hash to the hash of the current latest block, then recalculates its own hash.
isChainValid(): Validates the integrity of the blockchain by checking hashes.

Now what is validation means here: Let's suppose we have a database and we want to add some data into it, so before that what we do? we prepare and validate the data. So same situation here. We must have to validate our block before it insert to the blockchain. Here isChainValid() function actually validate our block.

Step 3: Adding and Validating Blocks

In this step, we will create an instance of our Blockchain class, add some blocks to it, and then validate the chain to ensure its integrity.

Let's break down the code and explain each part in detail.

Creating a Blockchain Instance First, we create a new instance of our Blockchain class. This instance will start with a single block, the genesis block, which is automatically created by the constructor of the Blockchain class

let myBlockchain = new Blockchain();

Adding Blocks Next, we add new blocks to our blockchain. Each block contains an index, a timestamp, and some data. When a new block is added, its previousHash property is set to the hash of the latest block in the chain, and its own hash is calculated using the calculateHash method.

myBlockchain.addBlock(new Block(1, "11/06/2024", { amount: 4 }));
myBlockchain.addBlock(new Block(2, "12/06/2024", { amount: 8 }));

Validating the Blockchain After adding blocks, we can validate the entire blockchain to ensure its integrity. The isChainValid method checks if all the blocks in the chain are valid by comparing their hashes and the previousHash values.

console.log("Blockchain valid?", myBlockchain.isChainValid());

Displaying the Blockchain
Finally, we can display the blockchain by converting it to a JSON string and logging it to the console.

console.log(JSON.stringify(myBlockchain, null, 4));

Now open the terminal and run the program:

node blockchain.js

This will output a neatly formatted representation of the entire blockchain, showing all the blocks and their properties.

Now let's understand how this blockchain relates to linked lists

This blockchain can be thought of as a specialized type of linked list. Both data structures store a sequence of elements (blocks in blockchain, nodes in linked list) where each element contains a reference to the next (and in some cases, the previous) element. Let's explore how the concepts align and then illustrate this with some examples.

Similarities Between Blockchain and Linked Lists

Sequential Storage:

Linked List: Each node points to the next node in the sequence.
Blockchain: Each block points to the next block through the previousHash property, forming a chain.

References:

Linked List: Nodes have pointers or references to the next node.
Blockchain: Blocks have a previousHash that references the hash of the previous block.

Addition:

Linked List: New nodes are added by adjusting the pointers of the existing and new nodes.
Blockchain: New blocks are added by setting the previousHash of the new block to the hash of the latest block, then appending it to the chain.

Traversal:

Linked List: You can traverse from the head (or any starting node) to the end by following the next pointers.
Blockchain: You can traverse from the genesis block to the latest block by following the previousHash references.

Differences Between Blockchain and Linked Lists

Immutability:

Linked List: Nodes can be changed freely.
Blockchain: Once a block is added, it is immutable; any change to a block would invalidate the entire chain from that block onwards.

Data Security:

Linked List: No inherent security features.
Blockchain: Each block contains a cryptographic hash that ensures data integrity and security.

Consensus Mechanisms:

Linked List: No need for consensus; nodes are managed centrally.
Blockchain: Often part of a decentralized system requiring consensus mechanisms (like Proof of Work or Proof of Stake) to validate new blocks.

Example: Linked List Implementation

Let's see a simple linked list implementation in JavaScript:

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  add(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  print() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }
}

// Usage
let list = new LinkedList();
list.add(1);
list.add(2);
list.add(3);
list.print();

This structure is consisting of a sequence of elements called nodes. Each node contains two parts:

Data: The value stored in the node.
Next: A reference (or pointer) to the next node in the sequence.

Here’s a simple visual representation of a linked list:

[Data|Next] -> [Data|Next] -> [Data|Next] -> null

In this structure, the first node is called the head, and the last node points to null, indicating the end of the list. Linked lists are dynamic, meaning they can grow and shrink in size as elements are added or removed.

Our blockchain:

const crypto = require("crypto-js");

class Block {
  constructor(index, timestamp, data, previousHash = "") {
    this.index = index;
    this.timestamp = timestamp;
    this.data = data;
    this.previousHash = previousHash;
    this.hash = this.calculateHash();
  }

  calculateHash() {
    return crypto
      .SHA256(
        this.index +
          this.previousHash +
          this.timestamp +
          JSON.stringify(this.data)
      )
      .toString();
  }
}

class Blockchain {
  constructor() {
    this.chain = [this.createGenesisBlock()];
  }

  createGenesisBlock() {
    return new Block(0, "10/06/2024", "Genesis Block", "0");
  }

  getLatestBlock() {
    return this.chain[this.chain.length - 1];
  }

  addBlock(newBlock) {
    newBlock.previousHash = this.getLatestBlock().hash;
    newBlock.hash = newBlock.calculateHash();
    this.chain.push(newBlock);
  }

  isChainValid() {
    for (let i = 1; i < this.chain.length; i++) {
      const currentBlock = this.chain[i];
      const previousBlock = this.chain[i - 1];

      if (currentBlock.hash !== currentBlock.calculateHash()) {
        return false;
      }

      if (currentBlock.previousHash !== previousBlock.hash) {
        return false;
      }
    }
    return true;
  }
}

// Usage
let myBlockchain = new Blockchain();
myBlockchain.addBlock(new Block(1, "11/06/2024", { amount: 4 }));
myBlockchain.addBlock(new Block(2, "12/06/2024", { amount: 8 }));
console.log(JSON.stringify(myBlockchain, null, 4));

Now what's happening blockchain as a linked list here:

Genesis Block: The genesis block is analogous to the head node of a linked list. It’s the first block (node) and does not reference any previous block.
Adding Blocks: Similar to adding nodes to a linked list, new blocks are linked to the chain by referencing the hash of the previous block (node).
Traversal and Validation: Just like traversing a linked list to perform operations, we traverse the blockchain to validate the integrity of the chain.

Conclusion

By building a blockchain from scratch, we can see how its underlying structure is similar to a linked list. Each block in the blockchain contains a reference to the previous block, forming a chain of blocks similar to nodes in a linked list. However, the blockchain adds layers of security and immutability through cryptographic hashing, making it a robust structure for maintaining an immutable ledger of transactions. And there are also some others linked list as well as.

Blog