COMP347 (Revision 10) | TrustOpen University
Upon completion of this expanded tutorial, students will be able to:
Peer-to-peer (P2P) systems represent a paradigm shift from the client-server model, leveraging the resources of end‑user hosts to achieve unprecedented scalability. This tutorial provides a rigorous, university‑level examination of P2P architectures, with BitTorrent as the primary case study.
We begin with formal models of P2P scalability, deriving the self‑scaling property mathematically. We then introduce game‑theoretic concepts—tit‑for‑tat as a cooperative equilibrium—to explain how BitTorrent mitigates free‑riding. The core of the tutorial dissects the BitTorrent wire protocol, detailing the binary format of each message type, the rarest‑first and endgame algorithms, and the choking/unchoking logic. We then explore the Kademlia DHT, explaining the XOR metric, k‑buckets, and the iterative lookup process. Finally, we discuss security threats unique to P2P systems: Sybil attacks, Eclipse attacks, content poisoning, and the countermeasures employed by modern clients.
Let a file of size \( F \) (bits) be distributed to \( N \) peers. The server upload rate is \( U_s \), and each peer \( i \) has upload rate \( u_i \) and download rate \( d_i \). The minimum distribution time is:
In client‑server, the term \( N \cdot F / U_s \) grows linearly with \( N \). In P2P, the denominator \( U_s + \sum u_i \) also grows with \( N \) (if each peer contributes non‑zero upload), making \( T_{p2p} \) asymptotically independent of \( N \). This is the fundamental self‑scaling property.
Churn is the continuous join/leave process. Let the average peer lifetime be \( 1/\mu \) (exponential distribution). The probability that a file piece replicated at \( k \) random peers is available at time \( t \) is:
For large \( k \) and short \( t \), availability approaches 1. This justifies replication and periodic repair in DHTs.
In any public good system, rational actors may choose to consume without contributing (free‑riding). In P2P, this manifests as leechers who download without uploading, degrading overall performance.
Tit‑for‑tat is a strategy where a peer cooperates (uploads) if the other peer cooperated in the previous round, and defects (chokes) otherwise. In the iterated prisoner's dilemma, tit‑for‑tat is a Nash equilibrium under certain conditions (Axelrod's tournament). It is robust, forgiving, and promotes reciprocal cooperation. BitTorrent's choking algorithm implements a form of tit‑for‑tat: peers upload to those who have recently uploaded to them.
To allow new peers to bootstrap and to discover better partners, BitTorrent periodically (every 30 seconds) unchokes a randomly chosen peer regardless of its upload contribution. This is essential for exploring the peer set and avoiding static oligopolies.
After establishing a TCP connection, peers exchange a handshake message:
pstr is the protocol string "BitTorrent protocol". info_hash is the SHA‑1 hash of the torrent's info dictionary (unique identifier). peer_id is a 20‑byte identifier generated by the client.
After the handshake, messages are length‑prefixed: `
| ID | Message | Payload | Description |
|---|---|---|---|
| 0 | choke | none | Stop uploading to this peer |
| 1 | unchoke | none | Start uploading to this peer |
| 2 | interested | none | Peer wants pieces from this peer |
| 3 | not interested | none | Peer doesn't want pieces |
| 4 | have | piece index (4 bytes) | Advertise that a piece is available |
| 5 | bitfield | bitfield | Initial set of available pieces |
| 6 | request | index, begin, length (4 bytes each) | Request a block of a piece |
| 7 | piece | index, begin, block data | Send a block |
| 8 | cancel | index, begin, length | Cancel a request |
The bitfield message is a variable‑length bit array, where bit i indicates whether piece i is available. It is sent immediately after the handshake to give the peer a complete picture of the remote peer's availability.
The client prioritises pieces that are least common among its connected peers. This improves global swarm health and ensures that rare pieces are replicated before peers with them depart. It is proven to be optimal for minimising the risk of deadlock (where a piece becomes unavailable).
For the first few pieces (typically the first piece), the client selects a random piece to complete quickly, enabling it to participate in the swarm (since it can now upload that piece).
When only a few pieces remain, the client sends requests for the same missing blocks to all peers simultaneously to avoid waiting for slow peers. This mode reduces completion time but generates redundant traffic. Duplicate responses are discarded.
Kademlia uses the XOR (bitwise exclusive OR) as a distance metric: \( d(x, y) = x \oplus y \). The distance is interpreted as an integer; the closer the value, the "closer" the nodes. Importantly, XOR satisfies the triangle inequality and allows for efficient routing.
Each node maintains a routing table of up to \( k \) entries per distance bucket (typically \( k = 20 \)). Buckets are organised by the most significant differing bit (i.e., logarithmic distance). When a bucket is full and a new node is discovered, the node pings the least‑recently‑seen entry; if it doesn't respond, the new node replaces it (bucket splitting).
The lookup converges in \( O(\log N) \) hops due to the XOR metric's consistent binary prefix property.
An attacker creates many identities (Sybils) to subvert the protocol, potentially gaining disproportionate influence. Mitigation: requiring computational puzzles, trusted identities, or using social trust networks (though these are challenging in open P2P).
An attacker surrounds a target node with malicious peers, so that all its routing table entries point to attacker‑controlled nodes. The target is then isolated from the honest network. Mitigation: random selection of peers, bucket splitting, and multiple parallel lookups.
An attacker injects corrupted or fake pieces into the swarm. BitTorrent mitigates this using SHA‑1 hashes of each piece (in the torrent file), so the client can verify every piece before accepting it. However, hash collisions are a theoretical risk (though impractical currently).
In a well‑behaved swarm, the number of seeders grows as peers complete the download. The system reaches a steady state where the rate of new completions balances the rate of departures.
High churn reduces the effective swarm size and increases the risk of piece loss. Replication (rarest first) and DHT redundancy are critical to maintaining availability. Studies show that BitTorrent remains efficient with churn rates up to 10% per minute.
Q1: In the P2P distribution time formula, why does the term \( N \cdot F / (U_s + \sum u_i) \) not grow with \( N \) in the ideal case?
Because \( \sum u_i \) grows proportionally to \( N \) (each peer adds upload capacity), so the denominator grows linearly with \( N \), cancelling the numerator.
Q2: What is the equilibrium strategy in the iterated prisoner's dilemma that BitTorrent's choking algorithm mimics?
Tit‑for‑tat.
Q3: What is the purpose of the optimistic unchoke in BitTorrent?
To allow new peers to bootstrap and to discover better uploading partners.
Q4: What is the message ID for a `have` message in the BitTorrent wire protocol?
ID 4.
Q5: What is the rarest‑first piece selection strategy?
It prioritises downloading pieces that are least common among the peers in the swarm.
Q6: What is the endgame mode in BitTorrent?
When only a few pieces remain, the client requests the same blocks from multiple peers to avoid waiting for slow ones.
Q7: What is the distance metric used by Kademlia?
XOR (bitwise exclusive OR).
Q8: What is a Sybil attack in a P2P network?
An attacker creates many fake identities to gain disproportionate influence.
Q9: How does BitTorrent protect against content poisoning?
Each piece is verified using a SHA‑1 hash from the torrent file; invalid pieces are rejected.
Q10: In Kademlia, how many parallel RPCs are typically used during a lookup?
\( \alpha \) (typically 3).
Q11: What is the purpose of the `bitfield` message in BitTorrent?
To advertise the complete set of pieces a peer has immediately after the handshake.
Q12: What is the effect of high churn on the availability of a file piece replicated at \( k \) peers?
High churn (large \( \mu \)) reduces availability; increasing \( k \) can compensate.
Exercise 1 – Distribution Time Calculation
Given: \( F = 10 \) GB, \( U_s = 100 \) Mbps, \( N = 1000 \) peers, each with \( u_i = 1 \) Mbps, \( d_i = 10 \) Mbps. Calculate \( T_{cs} \) and \( T_{p2p} \).
\( F = 10 \times 8 \times 1024 = 81920 \) Mb.
\( T_{cs} = \max(1000*81920/100, 81920/10) = \max(819200, 8192) = 819200 \) s ≈ 9.5 days.
\( T_{p2p} = \max(81920/100, 81920/10, 1000*81920/(100+1000)) = \max(819.2, 8192, 81920000/1100 ≈ 74472.7) ≈ 74473 \) s ≈ 20.7 hours.
P2P is much faster.
Exercise 2 – BitTorrent Message Analysis
Interpret a request message with length 13, ID 6, index=5, begin=1024, length=16384.
This is a request for block 1024–16384 of piece 5. The message length is 13 bytes (4+1+4+4+4). The peer is asking for a 16 KB block from that piece.
Exercise 3 – Kademlia Routing
Node A has ID 0101, Node B has ID 1001. What is their XOR distance?
0101 ⊕ 1001 = 1100 (binary) = 12 (decimal).
Exercise 4 – Tit‑for‑tat Strategy
Describe how a BitTorrent client decides which peers to unchoke in the next round based on current download rates.
The client ranks peers by their download rate (bytes per second) over the last 10 seconds. It unchokes the top 4 peers (default) and chokes the rest, then optimistically unchokes one random choked peer every 30 seconds.
Exercise 5 – Sybil Attack Mitigation
How could a P2P system mitigate Sybil attacks without central authority?
Use computational puzzles (proof‑of‑work), require each identity to have a small monetary stake (proof‑of‑stake), or rely on social trust networks (Web of Trust). Each has trade‑offs in terms of computational cost, centralisation, or adoption.
Exercise 6 – Endgame Mode Benefit
Explain how endgame mode reduces the completion time for a nearly‑finished download.
In endgame mode, the client sends duplicate requests for missing blocks to multiple peers. This reduces the probability that a slow peer (or one that leaves) delays the completion, as the first successful response is used and others are cancelled. This parallelisation reduces tail latency.
Homework 1 – BitTorrent Protocol Implementation
Design a minimal BitTorrent client in pseudocode that implements: handshake, bitfield exchange, rarest‑first selection, and choking. Outline the main event loop and state transitions.
Focus on the state machine for each peer: handshake → bitfield → interested/not interested → unchoke/choke → request/piece.
Homework 2 – Game Theory Analysis
Formalise the tit‑for‑tat strategy in BitTorrent as a repeated game. Show that it is a Nash equilibrium under the condition that the discount factor (probability of continuing) is sufficiently high.
Use the folk theorem for repeated games. Model each round as a prisoner's dilemma where cooperation is uploading.
Homework 3 – Kademlia Resilience
Analyse the resilience of Kademlia under a 30% node churn rate. Calculate the probability that a lookup fails (i.e., cannot find the target) if the bucket size \( k = 20 \). Simulate or derive using binomial distribution.
Assume node availability follows an exponential distribution; use the fact that the lookup contacts \( O(\log N) \) nodes.
Homework 4 – Content Poisoning Defence
Research and compare different defence mechanisms against content poisoning in P2P networks (e.g., hash verification, reputation systems, chunk‑based voting). Write a report evaluating their effectiveness and overhead.
Include both BitTorrent's SHA‑1 verification and academic proposals for reputation‑based voting.
Homework 5 – P2P Streaming Protocol Design
Design a P2P live streaming protocol (e.g., for a sports event). Consider the challenges of low latency, high churn, and the need for a continuous stream. Propose a piece‑selection strategy and a buffering algorithm.
Use a sliding window of segments; prioritise the most urgent (closest to playback time) pieces; use a mesh overlay with multiple parents.
This expanded tutorial has provided a deep, theoretically‑grounded examination of P2P architectures and BitTorrent. Key takeaways:
Understanding these concepts is essential for building scalable, resilient, and fair distributed applications beyond file sharing, including blockchain, decentralised storage, and real‑time streaming.