# Part 3 : Why share ? Understanding the BitTorrent economics .

All the peer connections are symmetric i.e data flow is not one way and each peer can download and upload data simultaneously .
But why should I contribute in the swarm and increase my data usage ? Why should't I just maintain a faster download speed ?
*Womp, Womp* . If you won't share data chunks , you won't receive any. BitTorrent uses a **tit for tat exchange scheme** .
Peers chose those peers to share data with who reciprocate the same . As a BitTorrent peer you will only have limited number of upload slots to allocate to other peers . So if you are uploading data to a peer who in return is not uploading any data to network then the BitTorrent will choke connection with this peer and try to alocate this upload slot to a more coorperative peer .
## 3.1 How can I participate in swarm when I have no pieces to trade ?
When a new peer joins the network it doesn't have pieces to participate in trade and hence this **tic to tac exchange scheme** will prevent it from participating. To avoid and counter such effects a mechanism called "optimistic unchoking" is used.
Periodically , the upload slot will be randomly allocated to an uncooperative peer . This gives chance to new peers to join in , and second chance to previously non-coorperating peers.

---------------------------------
## 3.2 But how do I discover and connect to a peer ?
Although the BitTorrent creates a decentralised file-sharing system there still exists a crucial centralised point(i.e. _tracker_) for maintaining the list of peers.
The tracker acts as an intermediary that helps all the peers discover each other and also maintains the number of seeders and leechers available for a particular torrent.
But the need for a tracker is only limited to the discovery of peers and once connection between peers is established , the need for trackers is not significant and P2P communication can go on without its need.

### 3.2.1 Promblems with trackers :
If the trackers goes down for maintainance or due to technical issues then the updated lists of peers couldn't be fetched making it difficult to share files.
Trackers handle a large number of requests from peers creating significant bandwidth demand on the tracker's server .Hence if the publishers is seeding some popular content they need to invest more in the infrastructure which might be very costly.

Seems like bit of a problem to me.

#### So, Any Solution ?
**_YUP_** . A _trackerless torrent_ solves the problem. A _trackerless_ refers to a BitTorrent download that operates without relying on a central tracker server for peer discovery.
One common method for such decentralised peer discovery is Distributed Hash Table(DHT).

## 3.3 Distributed Hash Tables
To eliminate the need of a central tracker , each peer must themselves hold a list similar to that of the tracker. But the list of tracker is too large to be stored individually with each peer. Hecne each peer maintains a partial list of other peers and the pieces of files they possess.
The DHT works with _info-hash(i.e. hash of metadata)_ as the key and peer-information(IP addresses and ports) as the value. Hence the data of the peer swarm is stored in the DHT . The BitTorrent uses Kademlia as it's DHT.

Now let's try to understand what Kademlia is ?
_~~I have tried my best to simpify it as much as possible T-T.~~_

### Kademlia DHT

#### A Neighbourhood Analogy
To understand how the Kademlia works , I have a small analogy to present .
Imagine there are 128($2^7$) houses in a neighbourhood ,not neccessarily all occupied . Each house with a family in it is assigned with a pencil , eraser and a copy with 7 pages (chosen as 128= $2^7$) and space for 2 entries per page .

These pages are used to write the phone number of the houses(occupied) in the neighbourhood with some rules. The rules are stated below :

* Each page say page number `i`(`i` from `0` to `6`) can only have the phone number of houses at a distance from $2^i$ and $2^{i+1}$ - 1
* Each page can atmost have 2 phone numbers, no limit on minimum.

Now suppose I want to know details about a household at a distance of 78 units from my house . Hence I must try to call the house which is as close as to the target house.
So now i will dial a number from page no.6 as it contains phone number of houses with distance of 64 to 127.
Now I dial up one of the numbers out of the two written on the list. It appears that the house I called is at a distance of 14 from the target house . So it will in turn again follow a similar procedure , turn up to page 3 of it's own list (contains phone number of houses with distance between 8 and 15) and call a house . And this process continues untill I get closest to/reach the target .

But this is just not it yet . There are some more aspects missing in this analogy.

This distance of ours is assumed to be special. Special in what sense might be the question in your mind . First , The distance of the two houses whose phone number are written on page `i` are always at distance less than $2^i$ . How is this possible might be a question in your head .
So consider 7 circles with their diameters as 1,2,4,8,16,32 and 64 .
You can see if 2 points lie in a circle the maximum distance they can be at is the diameter of that circle . Hence you can imagine the neighbourhood to look like this from each house . Second , no 2 houses can be equidistant to the same house , i.e. if house A and B are at a distance of 2 units then House A and C or B and C can not be at a distance of 2 units.Don't worry too much about thinking about implementing this condition geometrically.

What purpose this special distacne serve . It ensures that it takes at max 7 calls to reach the desired node (distance reduces geometrically).

Another advantage of it is that our target can uniquely identified by distance from current house as no other house is at same distance from the current one.

Now there is one last aspect of the algorithm analogy is to make use of our limited copy space to full extent .

If initially when I called the house of page no `6` , as this house is at distance of greater than 64 from my house hence my house is also at distance greater than 64 from this house(obvious actually) , so if this house were to store my number it would store it in the page `6` of it's notebook. Now considering you can only store 2 phone numbers on each page so it is in best interest to store the phone numbers of houses that are active(actively pick up your call). So now if this house which I initially called had less than 2 numbers written on it's page `6` , it will note my number with the time of contact .
If it already has 2 contacts it will now contact the phone which was least recently called . Now there are two possibilities :
1) This least recently contacted house doesn't pick up the call, hence proving to have become inactive . In this case this house will save my number .
2) This least recently contacted house picks up the call proving that it is still active . In this case my number will not be saved and the time of contact of this least recently contacted house will be updated to most recently contacted .

Now in the actual Kademlia DHT these houses are basically the hash-value and instead of 128($2^7$) possibilities we have $2^160$ possibilites as we use 160-bit space. The distance between the hashes is calculated by xoring them and it follows the properties said above . The 7 pages of the above the above notebook in actual are 160 different lists called K-buckets where K corresponds to the maximum number of entries in each list(in above analogy it was 2). Now let's formally define the Kademlia DHT .

#### Kademlia DHT

The Kademlia DHT uses a 160-bit space i.e. hashes of metadata will have 160-bits in it ( _e.g.,SHA-1_ ).Let us call this 160-bits space as **key space**.
Each participating computer is called a _node_ and is assigned an ID(called _node ID_) in the **key space**.

The <key,value> pairs are stored on nodes that are close to the key values. This closeness is defined by the XOR Distance.
| Term | Definition |
|--------------|----------------------------------------------------------------------------|
| Xor Distance | The distance between node and the key is defined as their **bitwise exclusive or (XOR)**. |

---------------------
Why XOR distance though?
Well,consider a 4 bit-binary number 1001.If this is the target is to be reached what is the most natural way to select from all 4-bit binary numbers ($2^4$ numbers) .
Start from the left-most bit and drop the numbers from consideration if their bit doesn't match.
So all numbers with 0xxx will be dropped and 1xxx will only be considered, so in one go we dropped 8 numbers. Now again we repeat this process for second left-most bit and drop the numbers with bits as 01xx, hence again droppin 4 numbers from consideration. Now repeating the same process again ,2 more times,we will reach the target. So it can be said that for a n-bit number in n steps we can reach the target by comparing if the left-most bit at each step matches our target or not .
Now how does XOR distance facilitate us in this comparision. Here is the XOR table before I exlain further :

| A | B | A ⊕ B |
|---|---|-------|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

Now as we can say for same bit in two numbers A & B the XOR operator results in 0. So we can clearly state that the more the bits(from the left-most end) of node match with the target the lesser the value of XOR distance it will assume .

--------------------------------

Kademlia stores data about nodes in the lists called _$k$-Buckets_. Each bucket ,indexed with i : 0 $\leq i <$ 160 , stores triples ==<IP Address , Port Number and Node ID>== for nodes of distance between $2^i$ and $2^{i+1}$ . For closer buckets , i.e. smaller $i$ , the bucket can sometimes be empty. And for large values of $i$ the bucket might contain upto $k$ number of triples.

What $k$ signifies is the maximum numbers of numbers triples stored in a bucket. The number $k$ is chosen such that any given $k$ nodes are very unlikely to fail (stop replying to requests) within an hour .
Generally the $k$ is taken to be 20 .

##### Now we have information stored on the nodes, let's understand how does the lookup takes place .
The lookup starts from the the very first _$k$-bucket_ for the node closest to the key(called target.) . If the target node is not found in the closest $k$-bucket, the initiating node queries nodes in the next closest $k$-bucket.
As the distance used is the ==XOR Distance== each step increases the common prefix between the node and the key by atleast one . Hence this process continues untill the initiating node reaches closest node to the target .

Each node has a <key,value> pair list for the closest keys and it is stored in it's **local storage** (different from DHT). The value for the key from the closest node to the target is hence fetched from this list .

This is how the trackerless torrent is able to share data chunks without a central system .