What is a Linked List?

A linked list is a linear data structure where elements (called nodes) are stored in a sequence, but unlike arrays, they are not stored in contiguous memory locations. Each node contains two parts: the data and a pointer (or reference) to the next node in the sequence.

Types of Linked Lists

• Singly Linked List: Each node points only to the next node
• Doubly Linked List: Each node points to both next and previous nodes
• Circular Linked List: The last node points back to the first node

Why Blockchain Uses Linked Lists

Blockchain is essentially a specialized singly linked list where each block contains a cryptographic hash of the previous block instead of a simple pointer. This creates an immutable chain - if any block is modified, all subsequent hashes become invalid.

Key Operations

• Insert at Head: O(1) - Add a new node at the beginning
• Insert at Tail: O(n) - Add a new node at the end
• Delete: O(n) - Remove a node by finding it first
• Search: O(n) - Find a node with specific data

What is a Hash Function?

A hash function takes an input (or 'message') of any size and produces a fixed-size output called a hash value, hash code, digest, or simply hash. The same input always produces the same output, but even a tiny change in input produces a completely different hash.

Properties of Cryptographic Hash Functions

• Deterministic: Same input always yields the same output
• Fast Computation: Quick to compute the hash for any given input
• Pre-image Resistance: Infeasible to reverse the hash to find the original input
• Collision Resistance: Extremely unlikely for two different inputs to produce the same hash
• Avalanche Effect: A small change in input drastically changes the output

Common Hash Functions

• SHA-256: Used in Bitcoin, produces 256-bit (64 hex characters) output
• SHA-3: Latest SHA standard with different internal structure
• RIPEMD-160: Used in Bitcoin for address generation
• CRC32: Simple checksum (shown in demo), not cryptographically secure

Hashing in Blockchain

Blockchain uses hashing to: (1) Create unique block identifiers, (2) Link blocks together by including the previous block's hash, (3) Verify data integrity, and (4) Support the mining process through proof-of-work.

What is a Merkle Tree?

A Merkle tree (named after Ralph Merkle) is a binary tree where every leaf node contains the hash of a data block, and every non-leaf node contains the hash of its child nodes. The root of the tree, called the Merkle root, represents a single hash that summarizes all the data.

How Merkle Trees Work

• Step 1: Hash each piece of data (e.g., transaction) to create leaf nodes
• Step 2: Pair adjacent hashes and hash them together
• Step 3: Repeat until only one hash remains (the Merkle root)
• Step 4: If odd number of nodes, duplicate the last one

Benefits of Merkle Trees

• Efficient Verification: Verify any single piece of data with O(log n) hashes
• Space Efficient: Only store the root to verify large datasets
• Tamper Detection: Any change propagates up, changing the root
• SPV Proofs: Light clients can verify transactions without downloading entire blocks

Merkle Trees in Bitcoin

Every Bitcoin block contains a Merkle root in its header, summarizing all transactions in that block. This allows lightweight wallets to verify if a transaction is included in a block by downloading only a small 'Merkle proof' instead of the entire block.

Binary (Base-2)

The fundamental language of computers. Uses only 0 and 1. Every piece of data, from text to images, is ultimately stored and processed as binary. Each binary digit is called a 'bit', and 8 bits make a 'byte'.

Hexadecimal (Base-16)

• Uses digits 0-9 and letters A-F (representing 10-15)
• More compact than binary: 1 hex digit = 4 binary bits
• Common in blockchain: hashes, addresses, transaction IDs
• Example: Binary 11111111 = Hex FF = Decimal 255

Base58 Encoding

• Used for Bitcoin addresses and private keys (WIF format)
• Similar to Base64 but removes confusing characters: 0, O, I, l
• Designed to be human-readable and avoid transcription errors
• Base58Check adds a checksum for error detection

Little Endian vs Big Endian

These describe the byte order when storing multi-byte values. Big Endian stores the most significant byte first (like reading left to right). Little Endian stores the least significant byte first. Bitcoin uses Little Endian for many internal values.

What is Symmetric Encryption?

Symmetric encryption uses the same secret key for both encryption (converting plaintext to ciphertext) and decryption (converting ciphertext back to plaintext). Both parties must have the same key and keep it secret.

AES (Advanced Encryption Standard)

• Most widely used symmetric encryption algorithm
• Adopted by U.S. government as standard in 2001
• Key sizes: 128, 192, or 256 bits
• Block cipher: encrypts data in 128-bit blocks
• Considered secure against all known practical attacks

The Key Distribution Problem

The main challenge with symmetric encryption is securely sharing the key. If an attacker intercepts the key during transmission, they can decrypt all messages. This problem led to the development of asymmetric encryption.

Symmetric Encryption in Blockchain

While blockchain transactions use asymmetric cryptography, symmetric encryption is still used for: encrypting wallet files, securing communication channels, and protecting sensitive metadata.