UNIT 1: Foundations of Blockchain Technology and Parallel Computing

1.0 Blockchain Technology Core Concepts

1.1 Blockchain Structure and Components

A blockchain is a growing list of records (blocks) linked via cryptographic hash pointers.

• Block Anatomy:

  • Block Header: Contains metadata:

    • Previous Block Hash: Hash of the preceding block (creates the chain).

    • Merkle Root: Hash of the root of the Merkle tree of all transactions in this block.

    • Timestamp: Time of block creation.

    • Nonce: Number used once in the mining Proof-of-Work.

    • Difficulty Target: The current mining difficulty.

  • Transaction Counter & Transactions: List of transactions included in the block.

• Genesis Block: The first block in the chain. Its Previous Block Hash is 0 (or a predefined value).

• Chain Formation: Each new block references the hash of its predecessor. Any alteration to a past block changes its hash, breaking all subsequent links, ensuring immutability.

[!TIP] Exam Focus: Be prepared to draw a labeled diagram of a block, showing the header fields and transaction list, and explain the role of the hash pointer in creating an immutable ledger.

1.2 Cryptographic Foundations

Cryptography provides the security foundation for blockchain.

• Cryptographic Hash Function (e.g., SHA-256):

  • Properties:

    1. Deterministic: Same input → same output.

    2. Quick to Compute: Fast for any input size.

    3. Pre-image Resistant: Hard to reverse (find input from hash).

    4. Avalanche Effect: Tiny input change → drastic output change.

    5. Collision Resistant: Extremely hard to find two inputs with same hash.

  • Purpose: Creates unique, fixed-size identifiers (hashes) for data (blocks, transactions).

• Public Key Cryptography (Asymmetric):

  • Key Pair: Each user has a private key (secret) and a public key (shared).

  • Digital Signature:

    • Signing: Signature = Sign(Private_Key, Transaction_Data)

    • Verification: Verify(Public_Key, Transaction_Data, Signature) returns true/false.

  • Purpose: Provides authentication (proves ownership) and non-repudiation (sender cannot deny).

• Merkle Trees (Hash Trees):

  • Construction: Transactions are hashed. Hashes are paired and hashed again recursively until a single root hash (Merkle Root) remains.

  • Usage:

    1. Efficiency: Allows lightweight clients (SPV nodes) to verify a transaction's inclusion without downloading the entire block. They only need the block header and a small subset of hashes (Merkle Proof).

    2. Data Integrity: Any change to a single transaction changes its hash, altering all parent hashes up to the Merkle Root, which is stored in the block header. This change would be detected.

  • Key Formula: Merkle_Root = Hash(Hash(Tx1) + Hash(Tx2)) (simplified for two transactions).

[!TIP] Exam Focus: Merkle Trees are a high-frequency question. Explain both construction (pairing, hashing) and usage (SPV, integrity). Always link the Merkle Root back to the block header.

1.3 Bitcoin Protocol Deep Dive

• P2P Network Architecture: Decentralized, peer-to-peer network. Nodes (full nodes, miners) propagate transactions and blocks via a gossip protocol.

• Transaction Propagation: A node broadcasts a new transaction to its peers. Each peer validates it (signature, UTXO check) and rebroadcasts. Valid transactions enter the mempool.

• Mining Process (Proof-of-Work):

  1. Miners collect pending transactions from the mempool.

  2. They construct a candidate block (header + transactions).

  3. They repeatedly change the Nonce and compute the double SHA-256 hash of the block header.

  4. Goal: Find a hash H such that H < Target (a very small number). This is computationally intensive ("work").

  5. First miner to find a valid nonce broadcasts the new block.

  6. Other nodes verify the PoW and all transactions, then add the block to their chain.

• Difficulty Adjustment: Every 2016 blocks (~2 weeks), the network recalculates the Target to maintain an average block time of 10 minutes, regardless of total hash power.

• Bitcoin Script: A simple, stack-based, non-Turing-complete language for locking/unlocking UTXOs.

  • Stack-Based: Operations pop arguments from, push results to a stack.

  • Smart Contract Capabilities: Enables basic logic (e.g., P2SH - Pay-to-Script-Hash, multisig M-of-N). It is not for complex applications.

• Double-Spending Problem & Prevention: Spending the same UTXO twice.

  • Prevention: Achieved through global consensus on the transaction order in the blockchain. The first transaction to get enough confirmations (blocks built on top) is considered valid; subsequent spends are rejected as they reference already-spent UTXOs.

• Types of Mining:

  • Solo Mining: Individual miner with own hardware. Very low probability of reward.

  • Pool Mining: Miners combine hash power. Rewards are shared proportionally. Most common.

  • Cloud Mining: Renting hash power from a remote facility. Often associated with scams.

[!TIP] Exam Focus: Be able to describe the full mining lifecycle. Distinguish Bitcoin Script (simple, locking) from Ethereum's Solidity (complex, stateful). For double-spending, emphasize the role of consensus and confirmations.

1.4 Consensus Mechanisms

Consensus is agreement among distributed nodes on the state of the ledger.

• Proof-of-Work (PoW):

  • Mechanism: Solve a cryptographic puzzle (find nonce). Requires significant computational power (energy).

  • HashCash: Early PoW algorithm for spam prevention. Bitcoin adapted it.

  • Attacks:

    • 51% Attack: If an entity controls >50% of network hash power, it can double-spend and censor transactions (but cannot steal funds).

    • Selfish Mining: Miner withholds a found block to create a private fork, eventually overtaking the public chain, reducing honest miners' revenue.

• Proof-of-Elapsed-Time (PoET):

  • Mechanism: Uses a trusted execution environment (TEE, e.g., Intel SGX). Each validator randomly waits for a randomly chosen time. The first validator to finish waiting (proves elapsed time) gets to propose the next block.

  • Goal: Achieve consensus with minimal resource consumption compared to PoW. Used in Hyperledger Sawtooth.

• Byzantine Fault Tolerance (BFT): Tolerates arbitrary/malicious faults (Byzantine generals problem).

  • Lamport-Shostak-Pease (Practical BFT - PBFT): State machine replication. Requires 3f+1 nodes to tolerate f faulty nodes. Involves pre-prepare, prepare, and commit phases for each block. Communication-heavy, used in permissioned chains.

• Raft Consensus Algorithm:

  • Mechanism: Leader-based consensus for non-Byzantine (crash-fault) environments.

  • Roles: One Leader (handles all client requests, replicates log to followers), Followers (passive, vote for leader), Candidate (in election).

  • Process: Leader appends log entry, sends AppendEntries to followers. Entry is committed when majority replicate it. Simple, efficient, used in permissioned systems (e.g., etcd, Consul, Hyperledger Fabric's ordering service can use Raft).

• Comparison: Permissioned vs. Permissionless:

[!TIP] Exam Focus: Contrast PoW (resource-heavy, permissionless) with BFT/Raft (efficient, permissioned). Know the core steps of PBFT and Raft. Understand the 3f+1 rule for BFT.

1.5 Smart Contracts

• Definition: Self-executing contracts with the terms of the agreement directly written into lines of code. They automatically enforce and execute when predefined conditions are met.

• Essential Characteristics:

  1. Self-Executing: Run automatically on the blockchain.

  2. Immutable: Deployed code cannot be changed (unless built with upgradeability).

  3. Deterministic: Same input → same output on all nodes.

  4. Trustless: No need for trusted third party; execution is guaranteed by the network.

  5. Stateful: Can store and modify state on the blockchain.

• Ethereum Smart Contracts:

  • Language: Solidity (statically-typed, JavaScript-like).

  • Runtime: Ethereum Virtual Machine (EVM). Every node runs the EVM to execute contract bytecode.

  • Process: Write .sol file → compile to EVM bytecode (.bin) & ABI → deploy to Ethereum network (paying gas) → interact via transactions.

• Hyperledger Fabric Smart Contracts (Chaincode):

  • Concept: Business logic that defines assets and transactions. Can be written in Go, Java, JavaScript.

  • Writing Process:

    1. Define asset data structure (e.g., in Go as a struct).

    2. Write transaction functions (e.g., CreateAsset, TransferAsset). These functions interact with the world state (key-value store).

    3. Package chaincode (code + dependencies).

    4. Install on peers, define and commit on a channel.

  • Execution: Transactions are sent to endorsing peers, who simulate execution and produce read-write sets. Ordering service orders transactions, committing peers validate and update world state.

• Use Cases & Limitations:

  • Use Cases: Automated payments (insurance), supply chain tracking, decentralized finance (DeFi), tokenization.

  • Limitations: "Garbage in, garbage out" (code bugs are permanent), scalability, legal enforceability in traditional courts, oracle problem (need external data).

[!TIP] Exam Focus: Contrast Ethereum (global, Turing-complete, gas) vs. Fabric (permissioned, channel-based, private data, no gas). Smart contract characteristics are a common 7-mark question.

1.6 Blockchain Types and Design Issues

• Public vs Private Blockchain:

• Permissioned Blockchain Design Considerations:

  • Membership Service Provider (MSP): Manages identities (X.509 certificates).

  • Channels: Private subnets for confidential transactions between specific peers.

  • Policies: Define rules for endorsement (who must sign), validation, and admin actions (e.g., AND('Org1.peer', 'Org2.peer')).

• Hyperledger Fabric Architecture:

  • Peers: Host chaincode & ledger. Endorsing Peers simulate transactions. Committing Peers update ledger.

  • Ordering Service (Orderers): Consensus service. Orders transactions into blocks (does not execute them). Can use Raft, Kafka, BFT-SMaRt.

  • Channels: Ledger & chaincode instances are isolated per channel. Allows multi-lateral transactions without global broadcast.

  • Membership Services: Handles identity management via MSPs.

• Identities and Policies in Fabric:

  • Identities: Based on X.509 certificates issued by a Certificate Authority (CA). Each peer, orderer, client, and admin has a cryptographically verifiable identity.

  • Policies: Defined in the channel configuration. Key policies:

    • Endorsement Policy: Which peers must endorse a transaction.

    • Channel Creation Policy: Who can create a channel.

    • Lifecycle Endorsement Policy: For chaincode definition/commit.

    • Application Policies: For reading/writing private data collections.

[!TIP] Exam Focus: Fabric's 3-tier architecture (Peers, Orderers, Channels) and the separation of execution (endorsement) from ordering are critical differentiators from Bitcoin/Ethereum. Know the role of MSPs and policies.

1.7 Blockchain Applications and Case Studies

• Mortgage Process Transformation:

  • Traditional: Paper-heavy, multiple intermediaries (lender, broker, title company, appraiser, insurer), slow (45-60 days), prone to fraud.

  • Blockchain-Based: Shared, immutable ledger. All parties (borrower, lender, title, etc.) access same verified data (income, appraisal, title). Smart contracts automate steps (release funds upon condition fulfillment). Result: Faster (days), reduced cost, increased transparency, reduced fraud.

• Supply Chain Finance Improvements:

  • Problem: SMEs face cash flow gaps due to long payment cycles. Invoices are paper-based, hard to verify, leading to high financing costs.

  • Blockchain Solution: Immutable record of goods movement and invoice creation on a permissioned network. Financiers can verify invoice authenticity and goods receipt in real-time. Enables invoice discounting and dynamic discounting with lower risk and interest rates.

• Cross-Border Payments (Ripple Case Study):

  • Problem: Traditional SWIFT is slow (2-5 days), expensive, opaque, requires multiple correspondent banks.

  • Ripple Solution: Uses XRP Ledger (consensus ledger, not blockchain) and XRP cryptocurrency as a bridge currency.

  • Mechanism: Banks connect to RippleNet. Payment is sent as a message (IOU). XRP is used for instant settlement between banks, avoiding nostro accounts. Result: Near-instant (3-5 sec), low-cost, transparent tracking.

• Identity Management Systems:

  • Problem: Centralized identity providers (Facebook, Google) are honeypots for hackers. Users have no control.

  • Blockchain Solution: Self-Sovereign Identity (SSI). User controls their identity data (stored in a digital wallet). Verifiable Credentials (VCs) issued by authorities (e.g., university degree) are cryptographically signed and stored on-chain/off-chain. User shares only necessary data with verifiers via zero-knowledge proofs. Examples: uPort, Sovrin.

• Ripple vs Corda Comparison:

• Hyperledger Fabric Industry Use Cases:

  • TradeLens (Maersk & IBM): Global shipping supply chain digitization. Tracks container events, automates documentation.

  • We.Trade (Banks): Trade finance platform for SMEs. Digitizes letters of credit.

  • Food Safety (Walmart, Nestlé): Trace food origin (e.g., mangoes, pork) from farm to store in seconds.

  • Digital Identity: Secure, shared identity verification for KYC/AML.

[!TIP] Exam Focus: For case studies, focus on the problem → blockchain solution → specific outcome structure. For platform comparisons (Ripple vs Corda), highlight the fundamental architectural difference (global ledger vs. point-to-point).

2.0 Parallel Computing Fundamentals

2.1 Parallelism Concepts and Classifications

• Four Categories of Parallelism (Flynn's Taxonomy):

• Distinctions:

  • Parallelism vs Pipelining: Pipelining overlaps execution of sequential instructions in a single processor (instruction-level parallelism). Parallelism uses multiple processors/cores to solve a larger problem concurrently.

  • Serial vs Parallel Processing: Serial executes one task at a time. Parallel divides a task into subtasks executed simultaneously on multiple resources.

  • Control Flow vs Data Flow Computers:

    • Control Flow: Execution driven by program counter (PC). Traditional von Neumann architecture.

    • Data Flow: Execution driven by availability of data. Instructions fire when their input data tokens are ready. No PC.

  • Uniprocessor vs Multiprocessor Systems:

    • Uniprocessor: Single CPU. Uses pipelining, superscalar, multithreading for ILP.

    • Multiprocessor: Two or more CPUs/cores sharing memory and/or bus. Enables true task-level parallelism.

2.2 Multiprocessor Architectures

• MIMD Multiprocessors vs Computer Networks:

  • Multiprocessors: Tightly-coupled. Share physical memory (UMA/NUMA). Low-latency, high-bandwidth interconnect (bus, crossbar). Single OS image. Used for parallel programming (OpenMP).

  • Computer Networks: Loosely-coupled. Each node has private memory. Communication via message passing (MPI) over network (Ethernet, InfiniBand). Higher latency. Each node runs its own OS.

• Pipeline Speedup Theory:

  • Theorem: A k-stage linear pipeline can be at most k times faster than a non-pipelined processor.

  • Proof:

    Let t_s = time for a non-pipelined instruction (sum of all stage times).

    Let t_p = clock cycle time of pipeline (determined by slowest stage).

    For a pipeline to work, t_p >= max(stage_time_i).

    Speedup S for executing n instructions:

$$S = \frac{n \cdot t_s}{[k + (n-1)] \cdot t_p}$$

    As `n → ∞` (large number of instructions):

$$S_{max} = \frac{t_s}{t_p}$$

    Since `t_s = \sum_{i=1}^{k} t_i` and `t_p >= max(t_i)`, the maximum possible `t_s / t_p` occurs when all stages are perfectly balanced (`t_i = t_p` for all i), giving:

$$S_{max} = \frac{k \cdot t_p}{t_p} = k$$

    \boxed{S_{max} = k}

*   **Note:** Real speedup is less due to pipeline hazards (structural, data, control).

• Modern GPU Architecture & Applications:

  • Architecture: Thousands of smaller, simpler cores organized in Streaming Multiprocessors (SMs). Designed for massive data parallelism (SIMT - Single Instruction, Multiple Threads). High memory bandwidth (GDDR/HBM). Separate VRAM.

  • Applications: Graphics rendering, scientific computing (matrix ops), AI/ML training (CNNs, Transformers), crypto mining, video encoding.

• Future System Architectural Trends:

  • Heterogeneous Computing: CPU + GPU + FPGA + AI accelerators (TPU, NPU).

  • Chiplet Design: Multiple smaller dies (chiplets) connected via high-speed interconnects (e.g., AMD Infinity Fabric, Intel Foveros).

  • Near-Memory/Processing-in-Memory (PIM): Reduce data movement by placing compute near memory (HBM with compute layers).

  • Domain-Specific Architectures (DSA): Optimized for specific workloads (e.g., Google TPU for ML).

  • Optical Interconnects: Using light for faster, lower-power chip-to-chip communication.

2.3 Memory Systems and Cache Coherence

• Cache Issues with Virtual Addresses:

  • Problem: Virtual addresses are process-specific. The same virtual address in different processes maps to different physical addresses.

  • Issue 1 (Alias Problem): Two different virtual addresses (from same or different processes) can map to the same physical address. If caches use virtual tags, two cache lines could hold the same physical data, causing coherence issues.

  • Issue 2 (TLB Miss Handling): On a TLB miss, the page table walk must complete before the cache access can proceed (if using virtual addresses), increasing latency.

  • Solution: Virtually Indexed, Physically Tagged (VIPT) caches. Index cache using virtual address bits, compare tags using physical address (after TLB lookup). Requires careful design to avoid aliasing within the cache index bits.

• Centralized vs Distributed Shared Caches:

  • Centralized Shared Cache (e.g., L3): Single, large cache chip shared by all cores. Simpler coherence (snooping on a single bus). Potential bottleneck, single point of failure.

  • Distributed Shared Cache (e.g., AMD's Infinity Fabric): Cache memory physically distributed across cores/chiplets. Each core has local cache, but can access remote caches. Lower latency for local access, higher for remote. Complex coherence (directory-based often needed). Better scalability.

• Cache Coherence Problem (Multicache Coherence):

  • Problem: In a system with multiple private caches, a single memory location can be cached in multiple places. If one core writes to its cached copy, other caches must be invalidated or updated to see the latest value. Without coherence, programs exhibit incorrect behavior.

  • Goal: Ensure all caches have a consistent view of memory.

• Snooping-Based vs Directory-Based Coherence Protocols:

  • Snooping (Bus-Based):

    • Mechanism: All cache controllers monitor (snoop) a shared broadcast medium (bus). Every memory transaction is visible on the bus.

    • Types:

      • Write-Invalidate: On a write, the writer broadcasts an invalidate message. Other caches discard their copy.

      • Write-Update (Write-Broadcast): On a write, the writer broadcasts the new data. All caches update their copy.

    • Pros: Simple, fast for small systems (few cores).

    • Cons: Bus traffic scales poorly with core count. Not suitable for distributed caches.

  • Directory-Based:

    • Mechanism: A central or distributed directory tracks the state (Shared, Modified, Invalid) of each cache line and which caches hold it.

    • Process: On a read/write, the request is sent to the directory. The directory coordinates invalidations/updates only to caches that have the line.

    • Pros: Scales to many cores (NUMA, clusters). Less traffic than snooping.

    • Cons: Directory lookup is an extra memory access (latency). Directory storage overhead.

2.4 Parallel Programming Models

• Distributed-Memory Programming with MPI:

  • Model: Processes have private address spaces. Communication via explicit message passing (MPI_Send, MPI_Recv).

  • Key Concepts: Communicators, ranks, tags, collective operations (MPI_Bcast, MPI_Reduce).

  • Process: Programmer decomposes data and computation, explicitly manages data distribution and communication. Used for clusters, supercomputers.

• Thread Management Models:

  • Many-to-One: Many user-level threads mapped to one kernel thread. Inefficient (kernel blocks all on one). Rare.

  • One-to-One: Each user thread maps to a unique kernel thread. True parallelism, but high overhead. Used by Linux Pthreads.

  • Many-to-Many (Hybrid): Many user threads multiplexed over a pool of kernel threads. Balances flexibility and performance. Used by modern thread libraries (Go goroutines, Java thread pools).

• Transaction vs Transactional Memory:

  • Transaction (DB): ACID (Atomicity, Consistency, Isolation, Durability) operations on a database.

  • Transactional Memory (TM): Hardware/software mechanism to simplify parallel programming. A transaction is a block of code that executes atomically and in isolation on shared memory. Conflicts are detected and resolved (retry) at commit time. Aims to replace locks.

• Parallel Data Management Strategies:

  • Partitioning (Decomposition): Divide data among threads/processes.

    • Block: Contiguous chunks.

    • Cyclic: Round-robin assignment.

    • Block-Cyclic: Hybrid.

  • Replication: Copy read-only data to all processing elements to avoid communication.

  • Striding: For regular access patterns (e.g., matrices).

• Map and Scan (Fusing) Operations:

  • Map: Applies a function to each element of a collection independently. f(x_i) → y_i. (Embarrassingly parallel).

  • Scan (Prefix Sum): Produces cumulative results. y_i = f(x_0, x_1, ..., x_i). (e.g., sum, max). Has dependencies.

  • Fusing: Combining map and scan operations into a single pass to reduce memory traffic and improve cache locality. Common optimization in parallel libraries (e.g., Thrust, CUB).

2.5 Performance and I/O in Parallel Systems

• Performance Metrics:

  • Speedup (S): S = T_serial / T_parallel. Measures how much faster parallel version is.

  • Efficiency (E): E = S / p (where p = number of processors). Measures resource utilization. E <= 1.

  • Scalability: How speedup improves as p increases. Strong scaling: Fixed problem size, increase p. Weak scaling: Increase problem size proportionally with p.

  • Amdahl's Law: S_max = 1 / ( (1 - P) + P/p ), where P is parallelizable fraction. Shows speedup limited by sequential part.

  • Gustafson's Law (Scaled Speedup): S(p) = p - α(p-1), where α is sequential fraction of scaled problem. More optimistic for weak scaling.

• I/O Handling in Parallel Programming Languages:

  • Challenge: Multiple processes/threads accessing shared filesystems can cause contention, race conditions, and non-determinism.

  • Strategies:

    1. Independent I/O: Each process writes to its own file (e.g., output.000, output.001). Simple, no contention.

    2. Collective I/O: Processes cooperate to perform a single large I/O operation (e.g., using MPI_File_read_all). Optimizes for parallel filesystems ( Lustre, GPFS).

    3. Two-Phase I/O: Aggregation phase (processes send data to designated I/O processes), then I/O phase (those processes write). Reduces number of I/O requests.

    4. Log-Structured I/O: Append-only writes to minimize seeks.

• Architectural Characteristics for Performance:

  • Latency Hiding: Use concurrency (multithreading, prefetching) to keep pipeline/network busy while waiting for memory.

  • Bandwidth Maximization: Use wider buses, higher clock rates, multiple memory channels (e.g., DDR4/5).

  • Locality Exploitation: Maximize temporal locality (reuse data) and spatial locality (access adjacent data) to leverage cache hierarchies.

  • Load Balancing: Distribute work evenly to avoid idle processors (static/dynamic scheduling).

  • Minimizing Synchronization: Reduce barriers, locks, and atomic operations which cause stalls.

[!TIP] Exam Focus: Amdahl's Law vs. Gustafson's Law is a classic distinction. For I/O, know the collective and two-phase strategies. For cache coherence, be able to contrast snooping (simple, bus-based) and directory-based (scalable, complex).