UNIT 2: BLOCKCHAIN TECHNOLOGY & PARALLEL COMPUTING

I. BLOCKCHAIN TECHNOLOGY

A. Fundamental Cryptography

Cryptographic Hash Functions

A deterministic algorithm that maps data of arbitrary size to a fixed-size string (hash/digest). Essential for blockchain integrity.

Properties:

1. Deterministic: Same input → same output.

2. Quick Computation: Fast to generate for any input.

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

4. Small Change → Big Difference: Avalanche effect; minor input change drastically alters output.

5. Collision Resistant: Hard to find two different inputs with same output.

6. Puzzle-friendly: Hard to find an input that hashes to a desired output (crucial for PoW).

[!TIP] Exam Focus: Properties are frequently asked. Link each property to its blockchain use (e.g., collision resistance prevents block tampering).

Public Key Cryptography (Asymmetric)

Uses a key pair: Public Key (shared) and Private Key (secret).

• Encryption: Encrypt(Public Key, Message) → Only Private Key can decrypt.

• Digital Signature: Sign(Private Key, Message) → Anyone with Public Key can verify signature and message integrity.

• Application in Blockchain: Creates Bitcoin addresses (hashed public keys) and signs transactions to prove ownership without revealing the private key.

Merkle Trees

A binary hash tree where leaves are hashes of data blocks (e.g., transaction hashes). Non-leaf nodes are hashes of their children.

DiagramCANVAS: A binary tree. Leaf nodes L1, L2, L3, L4 are hashes of transactions. Parent nodes H12 = Hash(H1+H2), H34 = Hash(H3+H4). Root = Hash(H12+H34).

Importance in Blockchain:

1. Efficient Verification: Allows Merkle Proof to verify a single transaction's inclusion in a block without downloading the entire block (lightweight clients/SPV).

2. Data Integrity: Any change in a leaf transaction changes all ancestor hashes up to the root. Root hash is stored in block header; tampering is easily detectable.

3. Scalability: Enables pruning of old transactions while maintaining proof of their existence.

[!TIP] Common Pitfall: Don't just state "used for efficiency." Explicitly mention Merkle Proof and SPV (Simplified Payment Verification).

B. Blockchain Structure and Operation

Block Structure

DiagramCANVAS: A block diagram with two main sections: Block Header and Block Body. Header contains: Version, Previous Block Hash, Merkle Root, Timestamp, Difficulty Target, Nonce. Body contains: Transaction Counter & List of Transactions.

• Block Header: Contains metadata. Previous Block Hash creates the immutable chain.

• Block Body: Contains the list of transactions. In Bitcoin, the first is the Coinbase transaction (miner reward).

Bitcoin P2P Network

A decentralized, unstructured overlay network. Nodes (full nodes, miners, SPV clients) connect to a few random peers.

• Transaction Propagation: A node broadcasts a new transaction to its peers, who validate and rebroadcast (flooding protocol).

• Block Propagation: A miner that finds a valid block broadcasts it. Nodes validate the block (transactions, PoW) and adopt it if valid, extending the chain.

Transaction Processing in Bitcoin

1. Creation: User A signs a transaction (inputs = UTXOs from previous tx, outputs = amount to B + change).

2. Broadcast: Sent to P2P network.

3. Validation by Nodes: Checks digital signature, UTXO existence, no double-spend, valid script.

4. Mempool: Valid transactions wait in the memory pool (mempool) to be included in a block.

5. Mining: Miners select transactions from mempool, create a candidate block, and solve PoW.

6. Confirmation: Once block is mined and accepted, transaction gets 1 confirmation. Each subsequent block adds another confirmation.

Double Spending Problem & Prevention

• Problem: Malicious user spends the same digital token (UTXO) twice by broadcasting two conflicting transactions.

• Prevention in Blockchain:

  1. Global Consensus: The network agrees on a single, canonical history of transactions (the longest valid chain).

  2. Confirmation Depth: A transaction in a block is "final" only after several subsequent blocks are added (typically 6 in Bitcoin). The probability of an attacker rewriting history decreases exponentially with confirmations.

  3. Timestamp & Ordering: Transactions are ordered in blocks. The first transaction to be included in a block that gets accepted by the network is the valid one.

C. Consensus Mechanisms

Overview of Distributed Consensus

Agreement among distributed nodes on the state of the ledger (which block is next) without a central authority. Must handle node failures and malicious actors (Byzantine faults).

Proof of Work (PoW)

• Concept: Miners compete to solve a computationally intensive but easily verifiable puzzle: find a nonce such that Hash(Block Header) < Target.

• HashCash PoW: Original idea (anti-spam). Puzzle: find x such that Hash(Email + x) has n leading zeros.

• Bitcoin PoW: Puzzle: Hash(Version | Prev_Hash | Merkle_Root | Timestamp | Bits | Nonce) < Target. Difficulty adjusts to maintain ~10 min block time.

• Attacks on PoW:

  • 51% Attack: If an attacker controls >50% hash power, they can exclude/alter transactions and double-spend.

  • Monopoly Problem: Mining power centralizes in large pools due to economies of scale, defeating decentralization.

Proof of Elapsed Time (PoET)

• Concept: Uses a trusted execution environment (TEE, e.g., Intel SGX) to randomly elect a leader.

• Process:

  1. Each validator requests a random wait time from the TEE.

  2. TEE confidentially returns a random wait time.

  3. Validator with the shortest wait time wakes up first and proposes the next block.

  4. Others verify the TEE attestation and the block.

• Advantage: Low energy consumption vs PoW. Disadvantage: Relies on trusted hardware vendor.

Byzantine Fault Tolerance (BFT)

Tolerates up to f Byzantine (malicious/faulty) nodes in a system of 3f+1 nodes.

• Lamport-Shostak-Pease (Practical BFT) Algorithm:

  1. Primary (Leader) broadcasts a value (proposal).

  2. Replicas broadcast PRE-PREPARE message with proposal to all.

  3. Replicas collect PREPARE messages from 2f others. On receiving 2f+1 PREPAREs, they enter prepared state and broadcast COMMIT.

  4. On receiving 2f+1 COMMITs, they enter committed state and execute the value.

  Key: Requires 3f+1 nodes to tolerate f faults. Communication-heavy (O(n²)).

Raft Consensus Algorithm

• Concept: A leader-based consensus for non-Byzantine (crash-fault) environments. Prioritizes understandability.

• Roles: Leader, Follower, Candidate.

• Process:

  1. Leader Election: Timeout → Candidate requests votes. Wins with majority → becomes Leader.

  2. Log Replication: Leader appends entries to its log and replicates to Followers. When majority replicate, entry is committed.

• Difference from BFT: Simpler, but assumes nodes are only faulty (crash), not malicious.

Consensus in Permissioned Blockchains

• Design Issues: Identity management, membership service, performance vs. decentralization trade-off, regulatory compliance.

• Types of Consensus Protocols:

  • Crash-Fault Tolerant (CFT): Raft, Paxos. For trusted environments.

  • Byzantine-Fault Tolerant (BFT): PBFT, Tendermint. For hostile environments with known identities.

  • Hybrid: e.g., HoneyBadgerBFT (BFT, asynchronous).

[!TIP] Exam Distinction: Permissionless (Bitcoin, Ethereum) → PoW/PoS, anonymous, Sybil-resistant. Permissioned (Fabric, Corda) → Known identities, BFT/RAFT, higher throughput.

D. Smart Contracts

Definition & Essential Characteristics

A self-executing contract with terms written in code, deployed on a blockchain. Characteristics:

1. Self-Executing: Automatically executes when predefined conditions are met.

2. Immutable: Once deployed, code cannot be changed (unless designed with upgradeability).

3. Decentralized: Runs on all nodes in the network.

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

5. Trustless: No need for trusted intermediary.

6. Transparent: Code is visible to all.

Bitcoin Script

• A stack-based, non-Turing-complete language (no loops).

• Purpose: Simple transaction validation logic (e.g., Pay-to-Public-Key-Hash - P2PKH).

• Limitation: Cannot express complex logic (e.g., multi-step agreements). Not a "smart contract" platform in the modern sense.

Ethereum Smart Contracts

• Written in Solidity (Turing-complete, high-level).

• Compiled to EVM bytecode and deployed to an Ethereum address.

• Gas: Execution fee paid in ETH to prevent infinite loops/spam.

• Features: Can store state, call other contracts, handle complex logic (DeFi, NFTs, DAOs).

Hyperledger Fabric Smart Contracts (Chaincode)

• Written in Go, Java, or JavaScript.

• Execution: Runs in a separate Docker container (chaincode container) from the peer process.

• Key Difference: Execute-Order-Validate architecture. Transactions are executed (simulated) by endorsing peers, then ordered, then validated by all peers. This allows for private data and confidentiality.

• Access Control: Managed by Membership Service Provider (MSP).

[!TIP] Key Contrast: Ethereum = Order-Execute (global state, all nodes execute all). Fabric = Execute-Order-Validate (private data, selective execution).

E. Blockchain Platforms

Bitcoin

• Purpose: Decentralized digital currency (peer-to-peer electronic cash).

• Consensus: Proof of Work (SHA-256).

• Smart Contracts: Limited (Bitcoin Script).

• Token: BTC (native currency, used for fees & rewards).

Ethereum

• Purpose: Decentralized platform for applications (world computer).

• Consensus: PoW (Eth1) → PoS (Eth2/Casper).

• Smart Contracts: Full-featured (Solidity, Vyper).

• Token: ETH (native currency for gas).

• Key Feature: EVM (Ethereum Virtual Machine).

Hyperledger Fabric

• Purpose: Permissioned enterprise blockchain framework for confidential transactions.

• Architecture:

  • Peers: Host ledgers & chaincode. Endorsing Peers simulate transactions.

  • Ordering Service: Orders transactions into blocks (Raft, Kafka, BFT-SMaRt). Separate from peers.

  • Membership Service: Manages identities (MSP).

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

  
  DiagramCANVAS: Fabric Architecture. Client App -> Peers (Endorsing, Committing) & Ordering Service. Peers connected via Channels. MSP box managing identities.
  
  

• Identities & Policies:

  • Identities: X.509 certificates issued by a CA, managed by MSP.

  • Policies: Define who can read/write (e.g., AND('Org1.member', 'Org2.member')). Policies for endorsement, validation, channel creation.

• Use Cases: Supply chain traceability, trade finance, healthcare records, inter-bank settlements.

Ripple & Corda

F. Blockchain Identity Management Systems

• Problem: Centralized identity providers (Google, Facebook) control user data → single point of failure, privacy loss.

• Blockchain Solution: Self-Sovereign Identity (SSI).

  • User controls their identity (private keys).

  • Identity is a set of verifiable credentials (VCs) issued by authorities (e.g., university degree, passport).

  • VCs are cryptographically signed and stored in a digital wallet.

  • Decentralized Identifiers (DIDs): Unique IDs anchored on-chain that point to DID documents (public keys, service endpoints).

  • Verification: Relying party verifies VC signature & issuer's DID without contacting the issuer directly.

• Benefit: Privacy, user control, reduced fraud, interoperability.

G. Mining

Block Mining Process (Bitcoin)

1. Collect pending transactions from mempool.

2. Create candidate block header (Prev_hash, Merkle_root, Timestamp, Bits, Nonce).

3. Start PoW: Iterate Nonce (and extra nonce) to find Hash(Header) < Target.

4. On success: Broadcast block to network.

5. On acceptance: Receive block reward (new BTC) + transaction fees.

Types of Mining

• Solo Mining: Individual miner. Very low probability of finding a block with small hash power.

• Pool Mining: Miners combine hash power. Pool operator finds block, rewards split proportionally. Reduces variance.

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

• Staking (for PoS): "Minting" by locking up coins as collateral (e.g., Ethereum 2.0).

H. Applications and Use Cases

Mortgage Process: Traditional vs Blockchain

Supply Chain Finance

• Problem: SMEs face cash flow gaps due to long payment cycles. Banks rely on manual, slow invoice verification.

• Blockchain Solution:

  • Immutable record of invoice creation → approval → payment on a shared ledger.

  • Smart contracts automatically release payment upon delivery confirmation (IoT sensor data).

  • Invoice financing: Banks can instantly verify invoice authenticity on-chain, reducing risk and enabling faster lending to SMEs.

  • Improvement: Transparency, reduced fraud, faster settlements, lower costs.

Cross-Border Payments

• Problem: Traditional (SWIFT) is slow (2-5 days), expensive (multiple fees), lacks transparency.

• Blockchain Solution (e.g., RippleNet):

  • Use a digital asset (XRP) as a bridge currency for instant liquidity.

  • Transactions settle in seconds on a distributed ledger.

  • Lower costs, end-to-end tracking, 24/7 operation.

Blockchain-Enabled Trade (Trade Finance)

• Process: Letters of Credit (LC), bills of lading, invoices.

• Blockchain Solution (e.g., we.trade, Marco Polo):

  • All trade documents (LC, bill of lading) digitized as tokens on a permissioned ledger.

  • Smart contracts automate LC issuance, amendment, and payment upon document presentation.

  • Benefit: Reduces processing from 5-10 days to <24 hours, cuts fraud, improves trust among unknown trading partners.

II. PARALLEL COMPUTING

A. Basic Terminology and Concepts

B. Parallel Architectures

Characteristics of MIMD Multiprocessors

(Multiple Instruction streams, Multiple Data streams)

1. Independent Execution: Each processor has its own control unit, executes its own instruction stream.

2. Shared Memory: Processors communicate via a shared global memory (UMA or NUMA).

3. Asynchronous Operation: Processors run asynchronously; need synchronization (locks, barriers).

4. Heterogeneity Possible: Can have different processor types (CPU+GPU).

5. Programming Model: Shared-memory programming (threads, OpenMP).

Distinction from: Multiple Computer Systems (distributed memory, networked, OS per node) & Computer Networks (loosely coupled, geographically dispersed).

Pipeline Speedup Proof (k-stage linear pipeline)

• Non-pipelined (Serial) Processor: Time for one instruction = k * t (where t = stage delay). Time for n instructions = n * k * t.

• Pipelined Processor:

  • First instruction finishes at k * t.

  • Each subsequent instruction finishes every t (steady state).

  • Time for n instructions = (k * t) + (n - 1) * t.

• Speedup (S):

$$ S = \frac{\text{Time}_{\text{serial}}}{\text{Time}_{\text{pipeline}}} = \frac{n * k * t}{k * t + (n - 1) * t} $$

For large `n` (steady state), `S ≈ \frac{n * k * t}{n * t} = k`.

\boxed{S_{\text{max}} = k}

• Ideal Speedup equals number of stages. Real Speedup < k due to pipeline hazards (structural, data, control).

C. Memory Systems and Cache Coherence

Disadvantages of Caches using Virtual Addresses

1. Cache Flush on Context Switch: Different processes use same virtual addresses but different physical pages. Cache must be flushed (or tagged with ASID) on every context switch → high overhead.

2. Coherence Complexity: Multiple virtual addresses (from different processes) may map to same physical address. Cache coherence protocols must handle this aliasing → more complex tags (need physical address or process ID).

3. I/O & DMA Issues: Direct Memory Access (DMA) uses physical addresses. Cache with virtual addresses must handle I/O coherence (maintaining consistency between cache and I/O-modified memory).

Solution: Physically Addressed Caches (PAC). Tags store physical addresses. Requires MMU lookup before cache access (adds latency) but solves above problems.

Centralized vs Distributed Shared Caches

Snooping-based vs Directory-based Cache Coherence

Multicache Coherence Problem & Solutions

• Problem: In a system with multiple caches, a memory location cached in two places may be modified by one CPU, leaving the other with a stale value.

• Solutions:

  1. Snooping Protocols (Bus-based):

     • Write-Invalidate: On write, broadcast invalidate. Other caches invalidate line.

     • Write-Update (Write-Broadcast): On write, broadcast new data. Other caches update line.

     • States: MSI (Modified, Shared, Invalid) → MESI (adds Exclusive).

  2. Directory Protocols (Scalable):

     • A directory (central or distributed) tracks sharers.

     • On read/write, processor queries directory. Directory coordinates invalidations/updates.

  3. Timestamp-based: Use timestamps to order accesses (rare).

  4. Hardware Solutions: Memory Order Buffers (MOB), store buffers to manage ordering within a core.

D. Specialized Architectures

GPU Architecture and Applications

• Architecture (SIMT - Single Instruction, Multiple Thread):

  • Many-core: Hundreds to thousands of smaller, efficient CUDA Cores / Stream Processors.

  • Grouped into Streaming Multiprocessors (SMs). Each SM has:

    • Warp Schedulers (32 threads = 1 warp).

    • Registers, shared memory (scratchpad), texture units.

  • High Memory Bandwidth: GDDR/HBM.

  • Design Goal: Throughput over latency. Hide memory latency with massive thread switching.

  
  DiagramCANVAS: GPU Block Diagram. Host (CPU) connected via PCIe to GPU DRAM. GPU contains multiple SMs. Each SM has warp schedulers, registers, shared memory, cores. Warp = 32 threads.
  
  

• Applications:

  • Graphics Rendering: Pixel/vertex shading (highly parallel).

  • General-Purpose GPU (GPGPU): Scientific computing, AI/Deep Learning (matrix ops), molecular dynamics, financial modeling, video encoding.

  • Key: Problems with high data parallelism and high arithmetic intensity.

E. Parallel Programming

Transaction vs Transactional Memory

Categories of Parallelism

1. Data Parallelism: Same operation on different data elements (SIMD, GPU kernels, #pragma omp parallel for).

2. Task Parallelism: Different tasks (functions) run concurrently (thread pool, std::async).

3. Pipeline Parallelism: Task broken into stages; different data items in different stages (assembly line). Common in streaming apps.

4. Implicit Parallelism: Compiler/Runtime extracts parallelism automatically (auto-parallelizing compilers, OpenMP #pragma).

Steps to Design Parallel Programs

1. Decomposition: Break problem into concurrent tasks (data/task/pipeline).

2. Assignment: Map tasks to processes/threads (static/dynamic).

3. Orchestration: Manage interactions (synchronization: locks, barriers; communication: message passing, shared memory).

4. Mapping: Bind processes/threads to physical processors (affinity) for performance.

5. Testing & Debugging: Race conditions, deadlocks. Use tools (Helgrind, ThreadSanitizer).

Distributed-Memory Programming with MPI

• Model: Processes with private address spaces. Communicate via explicit messages.

• Key MPI Concepts:

  • MPI_Init / MPI_Finalize

  • Communicator: MPI_COMM_WORLD (all processes).

  • Rank: Process ID in communicator.

  • Size: Total processes.

  • Point-to-Point: MPI_Send, MPI_Recv (blocking/non-blocking).

  • Collective: MPI_Bcast (broadcast), MPI_Scatter/Gather, MPI_Reduce.

• Typical Pattern:

  
  MPI_Init(...);
  
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  
  MPI_Comm_size(MPI_COMM_WORLD, &size);
  
  if(rank == 0) { data = ...; MPI_Scatter(data, ...); }
  
  else { MPI_Scatter(NULL, ...); }
  
  local_compute();
  
  MPI_Reduce(&local_result, &global_result, ...);
  
  MPI_Finalize();
  
  

I/O Handling in Parallel Programming Languages

• Challenge: Multiple processes/threads writing to same file → race conditions, interleaved output.

• Solutions:

  1. Independent Files: Each process writes to its own file (output.rank0, output.rank1). Post-process to combine.

  2. Collective I/O: Processes cooperate to read/write a shared file in disjoint regions (MPI-IO MPI_File_read_at). OS/parallel filesystem ( Lustre, GPFS) optimizes.

  3. Synchronized I/O: Use a lock (e.g., #pragma omp critical for OpenMP) so only one thread writes at a time. Slow.

  4. Log-Structured: Each process writes to a private buffer; a dedicated I/O process collects and writes sequentially.

Thread Management

• Creation/Joining: pthread_create, pthread_join (POSIX); std::thread (C++11).

• Thread Pool: Pre-create a fixed number of worker threads. Submit tasks (work queues). Reduces creation overhead, controls concurrency.

• Thread-Local Storage (TLS): __thread (C), thread_local (C++). Each thread has its own copy of a variable.

• Affinity: Bind thread to specific CPU core (pthread_setaffinity_np) to reduce cache misses and context switches.

Parallel Data Management

• Partitioning: Distribute data structures (arrays, graphs) across processors.

  • Block: Contiguous chunks.

  • Cyclic: Round-robin assignment (good for load balancing).

  • Block-Cyclic: Hybrid.

• Replication: Copy read-only data on all processors.

• Redistribution: Moving data between partitions (expensive). Needed for algorithm phases with different access patterns.

• Load Balancing: Dynamic scheduling (#pragma omp for schedule(dynamic)), work-stealing.

Fusing Map and Scan Operations

• Map: Apply function f to each element: [a,b,c] → [f(a), f(b), f(c)]. Embarrassingly parallel.

• Scan (Prefix Sum): Compute all intermediate sums: [a,b,c] → [a, a+b, a+b+c]. Has data dependency.

• Fusing: Combining map and scan into a single pass to reduce memory traffic.

  • Example: Compute scan(f(x)) without creating intermediate array.

  • Algorithm: Each thread computes local f(x) and local scan. Then a global scan on the partial sums. Finally, adjust each local scan by adding the global prefix sum of its partition.

  • Benefit: O(n) work, O(log n) span (parallel time), half the memory reads/writes vs separate map+scan.

F. Performance and Future Trends

Performance Metrics of Parallel Systems

1. Speedup (S): S = T_serial / T_parallel.

2. Efficiency (E): E = S / p (p = processors). Measures resource utilization.

3. Scalability: Ability to maintain efficiency as p increases. Strong scaling: Fixed problem size, increase p. Weak scaling: Increase problem size with p.

4. Amdahl's Law: S_max = 1 / ( (1 - P) + P/p ) where P = parallel fraction. Serial portion limits speedup.

5. Gustafson's Law: S = p - (1 - P)*(p - 1). Assumes problem size scales with p. More optimistic.

6. Cost-Effectiveness: S / cost(p).

Architectural Characteristics of Future Systems

1. Heterogeneity: Integration of CPU + GPU + FPGA + AI Accelerators (TPU, NPU) on package/chip.

2. Memory Hierarchy Deepening: More levels (HBM, MCDRAM), non-uniform access (NUMA) dominant.

3. Interconnect Evolution: From buses → rings → meshes → chiplet-based interconnects (UCIe) with high bandwidth, low latency.

4. Power & Thermal Limits: Dark Silicon - not all transistors can be powered simultaneously. Requires specialized accelerators for efficiency.

5. Approximate Computing: Trading precision for energy/performance (e.g., AI inference).

6. In-Memory/Processing-in-Memory (PIM): Reducing data movement by placing compute near memory (HBM with logic layer).

7. Quantum-Classical Hybrid: Quantum accelerators for specific problems (optimization, simulation) coupled with classical HPC systems.

8. Security & Reliability: Hardware support for confidential computing (TEEs like Intel SGX, AMD SEV), memory safety (CHERI), and resilience (fault-tolerant designs).

[!TIP] Exam Focus: Amdahl vs Gustafson is a classic distinction. Future trends emphasize specialization over generalization due to power constraints.