＃39　Understanding BitTorrent 1: A Deep Dive into Bencode

## Introduction:
BitTorrent is one of the pioneering and most popular peer-to-peer (P2P) file sharing protocols. In this blog, we'll explore the mechanics of BitTorrent and its unique encoding method, Bencode. Whether you're a tech enthusiast or just curious about how file sharing works, this post will provide you with a clear understanding of BitTorrent's functionality and its impact on the digital world.

## What is BitTorrent?
BitTorrent is a communication protocol for P2P file sharing, widely used to distribute data and electronic files over the internet. Unlike traditional file download methods, BitTorrent segments the content and downloads pieces from multiple sources simultaneously. This method, known as swarming, speeds up the download process and efficiently manages bandwidth.

### Key Features of BitTorrent:

- Decentralized Distribution: BitTorrent reduces reliance on a single server, distributing the load among multiple users.
- Scalability: The more users (peers) participate in sharing a file, the faster the download speed for everyone.
- Resilience: BitTorrent can resume downloads even after interruptions, making it robust against connection issues.


## Understanding Bencode
Bencode is the encoding method used by BitTorrent for storing and transmitting loosely structured data. It's a binary format that serializes data types like integers, strings, lists, and dictionaries (key-value pairs).

From spec, this is how Bencode Works:

- Integers are represented by an 'i' followed by the number in base 10 followed by an 'e'. For example i3e corresponds to 3 and i-3e corresponds to -3. Integers have no size limitation. i-0e is invalid. All encodings with a leading zero, such as i03e, are invalid, other than i0e, which of course corresponds to 0.
- Strings: Strings are length-prefixed base ten followed by a colon and the string. For example 4:spam corresponds to 'spam'.
- Lists: Lists are encoded as an 'l' followed by their elements (also bencoded) followed by an 'e'. For example l4:spam4:eggse corresponds to ['spam', 'eggs'].
- Dictionaries are encoded as a 'd' followed by a list of alternating keys and their corresponding values followed by an 'e'. For example, d3:cow3:moo4:spam4:eggse corresponds to {'cow': 'moo', 'spam': 'eggs'} and d4:spaml1:a1:bee corresponds to {'spam': ['a', 'b']}. Keys must be strings and appear in sorted order (sorted as raw strings, not alphanumerics).


### Decoding Bencode

I wrote a brief decoding Bencode in [Rust](https://www.rust-lang.org/). 

```rust
pub fn decode_bencode_value(encoded_value: &str) -> (serde_json::Value, &str) {
    match encoded_value.chars().next() {
        Some('i') => {
            if let Some((n, rest)) =
                encoded_value
                    .split_at(1)
                    .1
                    .split_once('e')
                    .and_then(|(digits, rest)| {
                        let n = digits.parse::<i64>().ok()?;
                        Some((n, rest))
                    })
            {
                return (n.into(), rest);
            }
        }
        Some('l') => {
            let mut values = Vec::new();
            let mut rest = encoded_value.split_at(1).1;
            while !rest.is_empty() && !rest.starts_with('e') {
                let (v, remainder) = decode_bencode_value(rest);
                values.push(v);
                rest = remainder;
            }
            return (values.into(), &rest[1..]);
        }
        Some('d') => {
            let mut dict = serde_json::Map::new();
            let mut values = Vec::new();
            let mut rest = encoded_value.split_at(1).1;
            while !rest.is_empty() && !rest.starts_with('e') {
                let (k, remainder) = decode_bencode_value(rest);
                let k = match k {
                    serde_json::Value::String(k) => k,
                    k => {
                        panic!("key must be strings, not {k:?}");
                    }
                };
                let (v, remainder) = decode_bencode_value(remainder);
                dict.insert(k, v.clone());
                values.push(v);
                rest = remainder;
            }
            return (dict.into(), &rest[1..]);
        }
        Some('0'..='9') => {
            if let Some((len, rest)) = encoded_value.split_once(':').and_then(|(len, rest)| {
                let len = len.parse::<usize>().ok()?;
                Some((len, rest))
            }) {
                return (rest[..len].to_string().into(), &rest[len..]);
            }
        }
        _ => {}
    }
    panic!("Unhandled encoded value: {}", encoded_value);
}
```

1. Function Signature

    ```rust
    pub fn decode_bencode_value(encoded_value: &str) -> (serde_json::Value, &str)
    ```
    This function takes a string slice (&str) representing the Bencode encoded value and returns a tuple containing a [serde_json::Value](https://docs.rs/serde_json/latest/serde_json/enum.Value.html) and a string slice. serde_json::Value represents any valid JSON value below.

    ```rust
    pub enum Value {
        Null,
        Bool(bool),
        Number(Number),
        String(String),
        Array(Vec<Value>),
        Object(Map<String, Value>),
    }
    ```

2. Matching the First Character

    ```rust
    match encoded_value.chars().next() { ... }
    ```

    The function begins by examining the first character of the input string to determine the type of the encoded data (integer, list, dictionary, or string):

3. Decoding an Integer

    ```rust
    Some('i') => { ... }
    ```

    If the first character is 'i', it indicates an integer. The function looks for the character 'e' that marks the end of the integer, parses the characters between 'i' and 'e' into an integer, and returns it.

4. Decoding a List

    ```rust
    Some('l') => { ... }
    ```

    If the first character is 'l', it represents a list. The function iteratively decodes each item in the list (also Bencode encoded) until it encounters the 'e' character, which marks the end of the list.

5. Decoding a Dictionary

    ```rust
    Some('d') => { ... }
    ```

    Dictionaries are indicated by the character 'd'. The function decodes each key-value pair (both Bencode encoded) until the 'e' character is reached. Keys must be strings; otherwise, the function panics.

6. Decoding a String

    ```rust
    Some('0'..='9') => { ... }
    ```

    Bencode strings are preceded by their length and a colon (:). The function parses the length, then returns the specified number of characters as the string.

7. Error Handling

    ```rust
    _ => {}
    panic!("Unhandled encoded value: {}", encoded_value);
    ```

    If the input does not conform to Bencode rules or an unsupported type is encountered, the function panics with an error message.
    

### Serde_bencode crate

There is a crate that supports serialize and deserialize bencode. If you want to know more, you can check [it](https://docs.rs/serde_bencode/latest/serde_bencode/).

```rust
use serde_derive::{Serialize, Deserialize};

#[derive(Serialize, Deserialize, PartialEq, Eq, Debug)]
struct Product {
    name: String,
    price: u32,
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let apple = Product {
        name: "Apple".to_string(),
        price: 130,
    };

    let serialized = serde_bencode::to_string(&apple)?;
     
    // cspell:disable-next-line
    assert_eq!(serialized, "d4:name5:Apple5:pricei130ee".to_string());

    let deserialized: Product = serde_bencode::from_str(&serialized)?;

    assert_eq!(
        deserialized,
        Product {
            name: "Apple".to_string(),
            price: 130,
        }
    );

    Ok(())
}
```

## Applications of Bencode in BitTorrent:
Bencode is primarily used in .torrent files and in the communication between peers and trackers. The .torrent files contain metadata about the files to be shared and the tracker, the server coordinating the distribution. 

## Conclusion:
BitTorrent has revolutionized the way we share and download files on the internet. Its efficient distribution mechanism, coupled with the simplicity of Bencode, makes it a powerful tool for handling large files. Understanding these technologies gives us insight into the complexities and innovations in the world of digital file sharing. Thank you for reading. See you in next blog.

## Resources:
For those interested in a deeper dive into the technical aspects of BitTorrent and Bencode, we recommend exploring the official BitTorrent specification and trying out creating your own .torrent files.

- [The BitTorrent Protocol Specification](https://www.bittorrent.org/beps/bep_0003.html)