🗒️BitTorrent 原理与去中心化下载
type
status
date
slug
summary
tags
category
icon
password
不谈在 BitTorrent 上下载东西。或最好的客户端。
只是深入探讨其技术层面。
任何人都可以阅读本文。阅读本文无需任何网络或 BitTorrent 知识。
BitTorrent 是传输大文件最常用的协议之一。2013 年 2 月，BitTorrent 的带宽占全球总带宽的 3.35%，超过文件共享总带宽 6% 的一半。
让我们直接进入主题。
谁创建了 BitTorrent？
Bram Cohen 于 2001 年发明了 BitTorrent 协议。Cohen 用 Python 编写了第一个客户端实现。
2002 年夏天，Cohen 收集了免费色情内容，以吸引一堆Linux 极客等测试人员使用 BitTorrent。结果不出意外的策略奏效了，同时说明他的代码也奏效了。
BitTorrent 与客户端-服务器下载的比较
在传统下载中，服务器上传文件，客户端下载文件。
对于流行的文件，这种方式并不十分有效。
500 人下载同一个文件会给服务器带来压力。这种压力会限制上传速度，使客户端无法快速下载文件。
其次，客户端-服务器的成本很高。我们支付的费用会随着文件的受欢迎程度而增加。
第三，它是集中式的。如果系统死机，文件不复存在，任何人都无法下载。
BitTorrent 旨在解决这些问题。
客户端-服务器模式 | BitTorrent |
中心化的 | 去中心化的 |
受欢迎的文件会对服务器造成很大压力 | 即使文件很受欢迎，也不会影响任何人 |
成本高昂。成本与文件的受欢迎程度成正比 | 成本不会随着文件的受欢迎程度而增加 |
在点对点网络中，每个点对点都与网络中的其他点对点相连。
半中心化的点对点网络拥有一个或多个比大多数对等节点更高权限的节点。
📑 高层次表述
BitTorrent 是一种共享文件的方式。它通常用于大文件。BitTorrent 是服务器等单一来源共享文件的替代方式。BitTorrent 可在带宽较低的情况下有效工作。
当用户想要共享文件时，他们就会将自己的文件播种。该用户被称为播种者（seeder）。他们将torrent描述符文件上传到交换中心（exchange，我们稍后会讨论）。任何想要下载该文件的人都将下载此 torrent 描述符。
第一个版本的 BitTorrent 客户端没有搜索引擎，也没有点对点交换，想要上传文件的用户必须创建一个小的 torrent 描述文件，然后上传到 torrent 索引网站。
我们称这些下载者为对等节点（peer）。他们的 torrent 客户端将连接到跟踪器（tracker，稍后讨论），跟踪器将向他们发送一个列表，其中包含群中其他种子和对等节点的 IP 地址。群体（swarm）是与某个 torrent 相关的所有 PC。
torrent描述符文件包含跟踪器列表和我们正在下载的文件的元数据。
对等节点会连接到一个播种者并下载文件的一部分。
一旦对等节点完成下载，他们可以作为播种者。虽然，也可以在下载的同时作为播种者（这是很常见的）。
一旦播种者与对等节点分享了文件，该对等节点将作为播种者。与仅有一个服务器上传文件的客户端-服务器模式不同，在 BitTorrent 中，多个人可以上传同一个文件。
BitTorrent 将文件分成称为片段的块，每块具有一定的大小。有时是 256 KB，有时是 1 MB。每个对等节点收到一个片段后，他们就成为该片段的播种者，可以提供给其他对等节点。
使用 BitTorrent，我们没有单一的下载来源。我们可以从你的本国下载一些片段，然后从一个遥远的国家下载你本国没有的片段。
该协议对片段进行哈希处理，以确保没有种子篡改原始文件。然后将哈希存储在跟踪器上的种子描述文件中。
这就是 BitTorrent 的高层次工作原理。现在我们将详细探讨。我们旨在回答以下问题：
- 如果同伴只下载而从不上传怎么办？
- 我们从谁那里下载或上传给谁？
- 什么是磁力链接（magnet link）？
- 什么是 torrent 描述文件？
- 使用什么散列算法？
- BitTorrent 如何选择要下载的文件？
还有更多。
📁 Torrent 描述符文件中到底有什么？
这是一个字典（或哈希图）文件。
bencode（pronounced like B encode）是BitTorrent用于存储和传输数据的编码方法。bencode支持四种不同的数据类型：字节字符串，整数，列表和字典。
以下是这四种数据类型的bencode表示：
- 字节字符串：由一个整数（表示字节的长度），后跟一个冒号和字符串本身组成。例如，字符串 "spam" 将被编码为 "4:spam"。
- 整数：由'i'开始，后跟数值，然后是'e'。例如，整数 42 将被编码为 "i42e"。
- 列表：由'l'开始，后跟列表中的元素（按bencode格式编码），然后是'e'。例如，列表 ["spam", 42] 将被编码为 "l4:spami42ee"。
- 字典：由'd'开始，后跟字典中的键值对（键和值都按bencode格式编码，键必须为字节字符串，并按字典序排序），然后是'e'。例如，字典 {"bar": "spam", "foo": 42} 将被编码为 "d3:bar4:spam3:fooi42ee"。
bencode格式是BitTorrent协议的基础，用于创建.torrent文件和传输peer和tracker之间的消息。它的设计目标是简单和易于实现，而不是高效或灵活。
文件描述如下
- Announce（公告）
跟踪器（tracker）的 URL。还记得我们之前联系跟踪器服务器以查找使用相同文件的其他对等吗？我们是通过使用 torrent 描述符文件中的公告密钥找到跟踪器的。
- Info（信息）
这映射到一个字典（key-value 表），其key取决于是否共享一个或多个文件。key包括
Files（文件，属于 info 的子文件，是一个列表）
Files 仅在共享多个文件时存在。Files 是一个字典列表。每个字典对应一个文件。每个字典都有 2 个键。
长度 - 文件的大小（以字节为单位）。
路径 - 与子目录名称相对应的字符串列表，最后一个字符串是实际文件名称。
- Length（长度）
文件的大小（以字节为单位）（仅在共享一个文件时）。
- Name（文件名）
建议的文件名。或建议的目录名。
- Pieces length（片长）
每个片段的字节数。
片段长度必须是 2 的幂，并且至少为 16 KiB。
即
- Pieces
散列列表。
对不同数据块计算的散列列表。我们把数据分成若干块。计算这些片段的哈希值，并将其存储在列表中。
BitTorrent 使用 SHA-1，可返回 160 位的散列值。片段将是长度为 20 字节倍数的字符串。
如果 torrent 包含多个文件，则会按照文件在文件目录中出现的顺序串联形成片段。
除了最后一个片段可能较短外，torrent中的所有片段都是完整片段长度。
现在，我能猜到你在想什么。
"SHA-1？这是什么？2000年代的东西吗？"
我同意。BitTorrent 正在从 SHA-1 转向 SHA256。
还在困惑吗？不用担心！我设计了这个 JSON 文件，它描述了 torrent 文件的样子。
注意：我合并了一些内容。这使得阅读和理解整体布局更加容易。数字是我编造的，遵循了BitTorrent种子描述符的规则。
BitTorrent 的片段选择算法
BitTorrent 中最大的问题之一是 "我应该选择下载哪些片段？
在传统的客户端-服务器模式下，我们下载的是整个文件。但现在，我们可以选择下载哪些片段。
我们的想法是下载别人没有的文件--稀有文件。通过下载稀有片段，我们上传它们，使它们不再稀有。
🌆 什么是子片段和片段选择算法？
BitTorrent 使用 TCP，这是一种数据包传输协议。TCP 有一种称为慢启动的机制。
慢启动是一种平衡 TCP 网络连接速度的机制。它会不断增加传输的数据量，直至达到网络的最大承载能力。cwdn 代表拥塞窗口（Congestion Window）。
TCP 这样做是因为如果我们一次发送 16 个连接，服务器可能不习惯这种流量，网络会发生拥塞。
如果我们不定期发送数据，TCP 可能会将我们的网络连接速度限制在低于正常速度的范围内。
BitTorrent 确保通过将数据块拆分成更小的子块来始终发送数据。
每个子块大约有 16 KB 大小。一个数据块的大小并不固定，但大约在 1 MB 左右。
该协议总是有一定数量的子块请求（五个）在流水线中。当下载一个新子块时，客户端会发送一个新请求。这有助于加快速度。
子块可以从其他对等节点下载。
两个核心策略支配数据块选择算法。
1️⃣严格策略
一旦 BitTorrent 客户端请求一个数据块的子块，任何剩余的子块都会在请求其他数据块的子块之前被请求。
在此图中，首先下载该数据块的所有子块比开始下载另一个数据块更合理。
2️⃣最稀有优先
BitTorrent 的主要策略是选择最稀有的优先。我们希望下载其他对等节点拥有最少的那个数据块。
这是为了使其不再稀有。如果只有一个对等节点有一个数据块并且它下线了，没人能获得完整的文件。
这个策略有很多好处。
增加种子
最稀有优先确保我们只从种子下载新的数据块。
种子一开始会成为瓶颈。种子是唯一拥有完整文件的对等节点。
下载者可以看到其他对等节点拥有哪些数据块，而最稀有优先策略会使我们从种子获取那些其他对等节点尚未上传的数据块。
让我们来可视化一下。
每个对等点都与其他对等点相连。
每个对等节点都连接到其他对等节点。
节点（对等节点）列表是互连的。我无法绘制出这个不利的图示。
每个箭头指向对等节点下载的子块。我们下载了一个除了种子外没有其他对等节点拥有的子块。这意味着这个子块是稀有的。
我们的上传速度比种子快，所以所有对等节点都会想从我们这里下载。而且，他们会想先下载最稀有的子块，因为我们是稀有子块的两个持有者之一。
当每个人从我们这里下载时，我们可以更快地从他们那里下载。这是“以牙还牙”算法（稍后讨论）。
提高下载速度
拥有数据块的对等节点越多，下载速度就越快。这是因为我们可以从其他对等节点下载子块。
启用上传
稀有数据块是其他对等节点最想要的，获得稀有数据块意味着对等节点会对从我们这里上传感兴趣。正如我们稍后会看到的，我们上传得越多，我们下载得越多。
最后下载最常见的数据块
把最常见的数据块留到最后下载是合理的。因为很多对等节点拥有常见的数据块，所以能够下载它们的概率要大于稀有数据块。
防止最稀有数据块丢失
当种子消失时，文件的所有不同数据块应该分布在剩余的对等节点中。
3️⃣随机第一个数据块
一旦我们开始下载，我们没有可以上传的东西。我们需要尽快获得第一个数据块。最稀有优先策略较慢。稀有数据块下载较慢，因为我们只能从少数对等节点下载它的子块。
4️⃣终局模式
有时，一个传输速度较慢的对等节点会尝试向我们提供一个子块，导致下载延迟。为了防止这种情况，有“终局模式”。
记得流水线原则吗？总是有几个子块请求处于待处理状态。
我们的计算机缺少一个子块，所以我们进入终局模式。
我们正在从 2 个对等节点下载，有 1 个对等节点我们没有从其下载。
当对等节点缺少的所有子块都被请求时，他们会向所有对等节点广播这个请求。这有助于我们获得文件的最后一块。
我们找到一个拥有我们需要的子块的对等节点，所以我们从他们那里获取。
如果一个对等节点有我们缺少的子块，他们会将其发送回我们的计算机。
一旦子块到达，我们发送一个取消消息，告诉其他对等节点忽略我们的请求。
我们取消对所有其他对等网络的请求
🌱 使用以牙还牙（tit-for-tat）策略进行资源分配
在 BitTorrent 中，没有集中式的资源分配。相反，每个对等节点都最大化其下载速度。
一个对等节点会从任何可以下载的人那里下载。为了决定向谁上传，他们将使用一种“以牙还牙”算法的变体。
以牙还牙策略来自博弈论。其精髓是：
"以其人之道还治其人之身"
- 第一步，合作
- 每一步都做对方上一步做的事，也即以其人之道还治其人之身
- 在实施一次报复行为后，做好原谅的准备
🎐 阻塞算法
阻塞是暂时拒绝向另一个对等节点上传，但我们仍然可以从他们那里下载。
为了合作，对等节点上传；不合作时，他们“阻塞”与对等节点的连接。原则是向那些向我们上传的对等节点上传。
在合作期间，我们可以从对等节点下载数据块。当其他对等节点不合作时，他们不会告诉我们无法下载数据块。
我们希望同时有几个双向连接以实现帕累托效率。
给定固有的一群人和可分配的资源，如果从一种分配状态到另一种状态的变化中，在没有使任何人情况变坏的前提下，使得至少一个人变得更好，我们就认为这种分配是帕累托效率的。
因此，关键问题是如何确定要阻塞哪些对等节点以及要解除阻塞哪些对等节点？
一个对等节点总是解除阻塞其固定数量的对等节点（默认是4个）。
当前的下载速度决定了解除阻塞哪些对等节点。我们使用20秒的平均值来决定这一点。由于使用了 TCP（慢启动），快速阻塞和解除阻塞是不好的。因此，每10秒计算一次。
如果我们的上传速度很高，更多的对等节点会允许我们从他们那里下载。这意味着如果我们是一个好的上传者，我们可以获得更高的下载速度。这是 BitTorrent 协议中最重要的特性。
该协议禁止许多“白嫖者”，即只下载而不上传的对等节点。
对于一个对等网络来说，要高效，所有对等节点都需要为网络做出贡献。
😎 乐观解除阻塞
BitTorrent 还允许一个额外的解除阻塞的对等节点，这个节点不使用下载速度标准。
我们称之为乐观解除阻塞。检查一个未使用的连接是否优于当前使用的连接。
我们每30秒切换一次乐观解除阻塞。这段时间足够上传速度达到最大。同样对于上传。如果这个新连接被证明优于现有的解除阻塞连接之一，它将取代它。
乐观解除阻塞是随机选择的。
这也允许那些不上传且只下载的对等节点下载文件，即使他们拒绝合作。尽管如此，他们的下载速度会非常慢。
🤕 反阻塞
如果所有向另一个对等节点上传的对等节点都决定阻塞它，会发生什么？我们必须找到新的对等节点，但乐观解除阻塞机制每30秒只检查一个未使用的连接。为了帮助下载速度恢复，BitTorrent 有反阻塞。
如果客户端在60秒内没有从某个特定对等节点收到任何东西，它将认为它已经被“阻塞”了。
按照以牙还牙的思路，我们报复并拒绝向那个对等节点上传（除非它成为乐观解除阻塞）。
然后对等节点会增加乐观解除阻塞的数量，以更快地找到新连接。
🤔 如果我们只上传怎么办？
我们看到，通过使用 BitTorrent 中实现的阻塞算法，我们优先考虑那些对我们友好的对等节点。如果我能从他们那里快速下载，我们允许他们从我这里快速上传。
没有下载怎么办？那么就不可能用这个阻塞算法知道该解除阻塞哪些对等节点。当下载完成时，我们使用一个新的阻塞算法。
这个新的阻塞算法解除阻塞上传速度最快的对等节点。这确保了数据块被更快上传，并且它们更快被复制。
上传速度好的对等节点也不会被其他人服务。
🐝 什么是跟踪器？
跟踪器是帮助对等节点之间通信的特殊类型服务器。
在 BitTorrent 中，通信非常重要。我们如何知道其他对等节点存在？
跟踪器知道谁拥有文件，以及多少。
一旦对等下载开始，通信可以在没有跟踪器的情况下继续。
自从创建了用于无跟踪器种子的分布式哈希表方法以来，BitTorrent 跟踪器基本上已经过时了。
🗼 公共跟踪器
这些是任何人都可以使用的跟踪器。
海盗湾曾经运营一个最受欢迎的公共跟踪器，直到2009年禁用它，只使用磁力链接（稍后讨论）。
🔐 私人跟踪器
私人跟踪器是私人的。它们通过要求用户注册来限制使用。控制注册的方法通常是邀请制。要使用这个跟踪器，我们需要一个邀请。
🔢 多跟踪器种子
多跟踪器种子包含在一个种子文件中的多个跟踪器。这提供了冗余，如果一个跟踪器失败，其他跟踪器可以继续维持种子的群体。
通过这种配置，可能会有多个不连接的种子群 - 这是不好的。有些用户可以连接到一个特定的跟踪器，而无法连接到另一个。这会创建一个分离的集合，阻碍种子传输其描述文件的效率。
🧲 磁力链接 - 无跟踪器种子
前面，我谈到了海盗湾如何摆脱跟踪器并开始使用无跟踪器种子。
当我们下载一个种子时，我们会得到一个种子的哈希值。要在没有跟踪器的情况下下载种子，我们需要找到也在下载种子的其他对等节点。为此，我们需要使用分布式哈希表。
让我们来探索分布式哈希表。
🐍 分布式哈希表
分布式哈希表（DHT）为我们提供了类似字典的接口，但节点分布在网络上。DHT 的技巧在于，存储特定键的节点是通过哈希该键找到的。
大部分 BitTorrent 客户端（例如 μTorrent、qBittorrent 等）内置了 DHT 功能。当客户端启动时，它会初始化自己的 DHT 模块。
为了加入 DHT 网络，客户端需要知道至少一个已经在网络中的节点。这些初始节点称为“引导节点”（Bootstrap Nodes）。客户端可以从几种方式获取这些引导节点的信息：
- 内置引导节点列表：客户端通常包含一组预配置的引导节点 IP 地址。
- DNS 引导：客户端可以通过查询特定的 DNS 记录来获取引导节点的 IP 地址。
- 本地持久存储：客户端可能会从上次会话中保存并恢复已知的 DHT 节点信息。
引导节点会回复一些它们已知的节点信息。客户端将联系这些节点，逐步扩展自己的节点列表。这个过程称为“路由表构建”（Routing Table Construction），目的是找到更多活跃的 DHT 节点。这样在实际上，每个对等节点都变成了一个小型跟踪器。
每个节点（实现 DHT 协议的客户端/服务器）都有一个称为“节点 ID”的唯一标识符。我们从与 BitTorrent 信息哈希相同的160位空间中随机选择节点 ID。
信息哈希是以下内容的 SHA-1 哈希：
- ITEM：长度（大小）和路径（包含文件名的路径）
- Name：要搜索的名称
- Piece length：单个数据块的长度（大小）
- Pieces：此种子的每个数据块的 SHA-1 哈希
- Private：限制访问的标志
我们使用距离度量来比较两个节点 ID 或一个节点 ID 和一个信息哈希的“接近度”。
节点必须有一个路由表，包含其他一些节点的联系信息。
节点在 DHT 中彼此了解。他们知道许多与自己的 ID 接近的节点，但很少有远离的节点。
距离度量是异或（XOR），并被解释为一个整数。
较小的值表示较近。
当一个节点想要查找种子的对等节点时，它使用距离度量来比较种子的哈希与其路由表中的节点 ID 或一个节点的 ID 与另一个节点的 ID。
然后他们联系路由表中离信息哈希最近的节点，并询问他们下载种子的对等节点的联系信息。
如果被联系的节点知道种子的对等节点，他们会在响应中返回对等节点的联系信息。否则，被联系的节点必须响应其路由表中离种子信息哈希最近的节点的联系信息。
原始节点查询更接近目标信息哈希的节点，直到找不到更近的节点。节点耗尽搜索后，客户端会将其自身的对等节点联系信息插入到响应节点的 ID 最接近种子信息哈希的节点中。将来，其他节点可以轻松找到我们。
查询对等节点的返回值包括一个称为“令牌”的不透明值。节点要宣布其控制的对等节点正在下载种子，必须出示在最近的对等节点查询中从同一被查询节点收到的令牌。
当一个节点试图“宣布”一个种子时，被查询节点会根据查询节点的 IP 地址检查令牌。这是为了防止恶意主机将其他主机签入种子。
查询节点将令牌返回给他们从中收到令牌的同一节点。我们必须在合理的时间内接受分发的令牌。BitTorrent 实现使用 IP 地址的 SHA-1 哈希与每五分钟变化一次的秘密拼接，最多接受十分钟内的令牌。
📌 路由表
每个节点都维护一个已知的良好节点的路由表。我们使用路由表作为在 DHT 中查询的起点。我们从路由表中返回节点来响应其他节点的查询。
并非所有我们了解到的节点都是平等的。有些是“好的”，有些则不是。许多使用 DHT 的节点可以发送查询并接收响应，但不能响应其他节点的查询。每个节点的路由表必须仅包含已知的良好节点。
一个良好节点是在过去15分钟内对我们的查询做出响应的节点。如果某个节点曾经对我们的查询做出响应，并且在过去15分钟内向我们发送了查询，它也是一个良好节点。在15分钟不活动后，节点变为可疑。当多个查询连续失败时，节点变为坏节点。我们优先考虑我们认为好的节点，而不是状态未知的节点。
路由表覆盖从0到的整个节点 ID 空间。我们将路由表划分为覆盖该空间一部分的“桶”。
一个空的表有一个 ID 空间范围为 的桶。
一个空的表只有一个桶，因此任何节点都必须适合它。每个桶只能容纳 K 个节点，目前是8个，才能变得“满”。
当一个桶装满已知的良好节点时，除非我们的节点 ID 落在该桶的范围内，否则我们不能再添加节点。该桶被两个覆盖旧桶一半范围的新桶取代。旧桶中的节点分布在新桶中。
对于只有一个桶的新表，我们总是将满桶拆分成两个新的桶，覆盖范围为 和 。
当桶中充满良好节点时，我们简单地丢弃新节点。当桶中的节点变坏（如果它们变坏）时，我们用一个新节点替换它们。
当节点被认为是可疑的并且在过去15分钟内没有被看到时，最久未被看到的节点将被 ping。一旦节点响应或不响应，我们就移动到下一个节点。我们这样做直到找到一个未响应的节点。如果没有找到，则认为该桶是好的。
当我们找到一个未响应的节点时，我们再试一次，然后丢弃该节点并用一个新的良好节点替换它。
每个桶应该维护一个“最后更改”属性，以显示内容的“新鲜度”。
当 ping 一个桶中的节点并响应时，或者向桶中添加一个节点或用另一个节点替换一个节点时，桶的最后更改属性会更新。
如果最后更改属性在过去15分钟内未更新，桶会被刷新。
🤺 对 BitTorrent 的攻击
对 BitTorrent 网络的攻击很少。所有内容都是公开的。我们的 IP 地址，我们正在下载的内容——一切。为什么要攻击一个开放的网络？
为什么要攻击一个完全开放的网络？
在 Exploit-DB（一个针对服务的已知漏洞数据库）中只列出了7个条目。而且大多数与特定的客户端有关。
对 BitTorrent 网络的主要攻击是停止盗版。我们已经谈了这么多，却没有谈到盗版，但它通常与 BitTorrent 同义。
对 BitTorrent 的主要攻击是种子中毒。
种子中毒
这种攻击旨在获取盗版内容的对等节点的 IP 地址或以某种方式毒害内容。
麦当娜的《American Life》专辑发布就是一个内容中毒的例子。在发布之前，发布了相似长度和文件大小的曲目。这些曲目包含麦当娜的一段音频：
“你以为你在做什么？”
然后是几分钟的静默。
以下是一些毒害种子的方法。
索引中毒
索引允许用户定位具有所需内容的对等节点的 IP 地址。这种攻击方法使得寻找对等节点变得困难。
攻击者向索引中插入大量无效信息，阻止用户找到正确的信息。
其目的是通过让对等节点尝试从无效对等节点下载数据块来减慢下载速度。
诱饵插入
他们向网络插入损坏的文件版本。
想象一下500个文件副本中只有2个是真实文件，这会阻止盗版者找到真实文件。
大多数列出种子的网站都有投票系统。这种方式能阻止这种攻击，因为搜索的顶部充满了未损坏的文件。
在 GameDevTycoon 中，该文件在首次上传到盗版网站之前被发布。盗版者不知道的是，该文件已被损坏。盗版版本中无法赢得比赛。其他一切都很完美。
🧙🏼♂️ 防御 BitTorrent 攻击
大多数流行的种子是由建立了多年信誉的个人或团体发布的。在私人跟踪器上，可以指向个人。被毒害的种子会迅速被标记，发布者会被禁止。
或者，在公共跟踪器上，下载受信任团体发布的种子是可取的。毕竟，你是愿意从 Ubuntu 团队下载 Ubuntu，还是从用户 xxx-HACKER-ELITE-GHOST-PROTOCOL-xxx 下载？
在公共跟踪器上，如果种子被毒害，会被举报和删除。
防御 BitTorrent 攻击的最简单方法是使用一个与你无关的 IP 地址。无论是通过 VPN 还是其他服务。
👋🏻 结论
以下是我们学到的内容：
- 种子描述文件是什么
- BitTorrent 如何选择对等节点
- BitTorrent 如何选择数据块
- 以牙还牙算法
- 跟踪器
- 对 BitTorrent 网络的攻击
Kademlia 算法
Kademlia 算法Magnet 嗅探
‣
原理
前言
之前看到 lantern 这个十分火的翻墙工具，其利用了P2P的思想，就想了解一下P2P相关的协议。看了下最流行的BT协议官方文档，就产生了实现BT协议的想法，顺便根据协议实现了一个BT种子嗅探器。
也有人将BT种子嗅探器称为BT种子爬虫，个人觉得其行为特性和传统的web爬虫相差较大，反而和嗅探器很类似，因此暂且称之为BT种子嗅探器吧。
接下来将写一系列文章来介绍其原理和具体实现方式。这篇文章先提纲挈领，介绍其工作原理，以对全局有一个把握。后序的文章再介绍具体细节。
背景知识
在讲原理之前首先你得具备BitTorrent(简称BT)协议的一些基本知识，以便于理解接下来要讲的嗅探器。BT协议其实是一个协议簇，BEP-3 是其基本协议内容，其他的大部分都是围绕这个来进行扩展或补充。要想从BT网络中下载一个资源，必须具备以下部分：
- 种子文件（也就是我们常说的种子，后缀是 .torrent，本质上是一个由bencode编码的文本文件，其把资源分成很多虚拟块，并记录每个块的hash值，另外上面还记录着其他信息，比如文件大小、名字、Tracker服务器等）
- BT客户端（需要有专门解析BT协议的程序，这样才能下载，比如迅雷，电驴）
- Tracker服务器 （记录着peer和种子相关信息，起着中心调控的作用）
下载资源的时候，客户端首先根据bencode（bencode是BT协议中的编码方式）解码种子文件，得到Tracker服务器的地址和资源信息，通过和Tracker服务器沟通得到其他已经下载该资源的peers信息（其他已经拥有该资源的客户端或者发布该资源的人），然后再和这些peers沟通得到自己想要的部分，即互通有无。由于把文件分成很多块来同时从不同的地方下载，这也就是为什么BT通常下载快的原因。
DHT协议
通过上面我们知道，Tracker服务器在资源下载的过程中起着至关重要的作用，只有通过它我们才能得到其他peers的信息，才能够下载，但这同时也成了BT协议的一个弱点，如果Tracker服务器挂掉了或者被封被屏蔽，整个网络也就瘫痪了。由于一些资源都是有版权的，还有一些资源是限制级的，比如色情资源，Tracker服务器很容易被迫关闭或被墙。后来聪明的人类发明了另外一种协议，就是 Distributed hash table, 简称DHT，这个协议就是用来弥补这个弱点的。
BT协议簇中的DHT协议 是基于 Kademlia协议 建立的，其基本思想很好理解。DHT 由很多节点组成，每个节点保存一张表，表里边记录着自己的好友节点。当你向一个节点A查询另外一个节点B的信息的时候，A就会查询自己的好友表，如果里边包含B，那么A就返回B的信息，否则A就返回距离B距离最近的k个节点。然后你再向这k个节点再次查询B的信息，这样循环一直到查询到B的信息，查询到B的信息后你应该向之前所有查询过的节点发个通知，告诉他们，你有B的信息。
举个例子，比如我现在想要Angelababy的微信号（额…我要干嘛），我就从自己的微信好友中挑出k个最可能认识她的人，然后依次问他们有没有Angelababy的微信号，假如其中一个认识，那么他就会给我Angelababy的微信号，我也就不继续问其他人了。假如他不认识，他就给我推荐k个他微信好友中最有可能认识Angelababy的k个人，然后我再继续这k个人，就这样循环一直到我问到为止。OK，现在我已经得到了Angelababy的微信号，我就会告诉之前所有我问过的人，我有Angelababy的微信号。
当客户端下载资源的时候，他会利用上述方式查找peers信息，这样每个人都充当了Tracker的作用，也就解决了上面那个问题。
嗅探器原理
终于到核心部分了。
BT种子嗅探器就是利用了DHT协议得到peer信息后会向他之前查询过的节点发送通知这一点，这就是嗅探器的核心。
剩下的工作就是我们要让更多的节点发给我们通知。那么如何让更多的节点发给我们通知呢？
- 我们要不断的查询自己的好友节点表，并对返回回来的节点进行查询，这样才会有更多的人认识我们
- 别人向我们查询Target的时候，我们要伪装成Target的好友，返回结果里边包括自己，这样会有更多被查询、收到通知的机会
这就是BT种子嗅探器的原理，简单吧 :)
种子下载器
在BT网络中，通过上述原理收到信息并不是种子，而是发送消息者的ip和port、种子infohash（可以理解为种子的id）。我们如果想要得到种子的话，还需要做一番工作。这里涉及到另外一个非常重要的协议 BEP-09，BEP-09规定了如何通过种子infohash得到种子。
这里不铺开讲，仅说下大致过程。首先同我们收到的消息里边的 ip:port 建立TCP连接，然后发送握手消息，并告知对方自己支持BEP-09协议，然后向对方请求种子的信息，收到对方返回的种子信息后，依次或同时请求每一个块。最有所有块收集完后，对其进行拼接并通过sha1算法计算其infohash，如果和我们请求的infohash值相同则保存起来，否则丢掉。
应用
这样你可以得到非常多的种子信息，你可以对其进行索引建立自己的BT种子搜索引擎，建立自己的海盗湾。但你需要注意版权问题和色情资源问题。
DHT
背景知识
DHT全称 Distributed Hash Table，中文翻译过来就是分布式哈希表。它是一种去中心化的分布式系统，特点主要有自动去中心化，强大的容错能力，支持扩展。另外它规定了自己的架构，包括keyspace和overlay network（覆盖网络）两部分。但是他没有规定具体的算法细节，所以出现了很多不同的实现方式，比如Chord，Pastry，Kademlia等。BitTorrent中的DHT是基于Kademlia的一种变形，它的官方名称叫做 Mainline DHT。
DHT人如其名，把它看成一个整体，从远处看它，它就是一张哈希表，只不过这张表是分布式的，存在于很多机器上。它同时支持set(key, val)，get(key)操作。DHT可以用于很多方面，比如分布式文件系统，DNS，即时消息(IM)，以及我们最熟悉的点对点文件共享（比如BT协议）等。
下面我们提到的DHT默认都是Mainline DHT，例子都是用伪代码来表示。读下面段落的时候要时刻记着，DHT是一个哈希表。
Mainline DHT
Mainline DHT遵循DHT的架构，下面我们分别从Keyspace和Overlay network两方面具体说明。
Keyspace
keyspace主要是关于key的一些规定。
Mainline dht里边的key长度为160bit，注意是bit，不是byte。在常见的编译型编程语言中，最长的整型也才是64bit，所以用整型是表示不了key的，我们得想其他的方式。我们可以用数组方式表示它，数组类型你可以选用长度不同的整型，比如int8，int16，int32等。这里为了下边方便计算，我们采用长度为20的byte数组来表示。
在mainline dht中，key之间唯一的一种计算是xor，即异或（还记得异或的知识吧？）。我们的key是用长度为20的byte数组来表示，因此我们应该从前往后依次计算两个key的相对应的byte的异或值，最终结果得到的是另外一个长度为20的byte数组。算法如下：
读到这里，你是不是要问xor有啥用？还记得原理篇中DHT的工作方式吗？
xor是为了找到好友表中离key最近的k个节点，什么样的节点最近？就是好友中每个节点和key相异或，得到的结果越小就越近。这里又衍生另外一个问题，byte数组之间怎么比较大小？很简单，从前往后，依次比较每一个byte的大小即可。
在Mainline DHT中，我们用160bit的key来代表每个节点和每个资源的ID，我们查找节点或者查找资源的时候实际上就是查找他们的ID。回想一下，这是不是很哈希表? :)
另外聪明的你可能又该问了，我们怎么样知道每个节点或者每个资源的ID是多少？在Mainline DHT中，节点的ID一般是随机生成的，而资源的ID是用sha1算法加密资源的内容后得到的。
OK，关于key就这么多，代码实现你可以查考这里。
Overlay network
Overlay network主要是关于DHT内部节点是怎么存储数据的，不同节点之间又是怎样通信的。
首先我们回顾一下原理篇中DHT的工作方式:
DHT 由很多节点组成，每个节点保存一张表，表里边记录着自己的好友节点。当你向一个节点A查询另外一个节点B的信息的时候，A就会查询自己的好友表，如果里边包含B，那么A就返回B的信息，否则A就返回距离B距离最近的k个节点。然后你再向这k个节点再次查询B的信息，这样循环一直到查询到B的信息，查询到B的信息后你应该向之前所有查询过的节点发个通知，告诉他们，你有B的信息。
整个DHT是一个哈希表，它把自己的数据化整为零分散在不同的节点里。OK，现在我们看下，一个节点内部是用什么样的数据结构存储数据的。
节点内部数据存储 - Routing Table
用什么样的数据结构得看支持什么样的操作，还得看各种操作的频繁程度。从上面工作方式我们知道，操作主要有两个：
- 在我（注意：“我”是一个节点）的好友节点中查询离一个key最近的k个节点（在Mainline DHT中，k=8），程度为频繁
- 把一个节点保存起来，也就是插入操作，程度为频繁
首先看到“最近”、“k”，我们会联想到top k问题。一个很straightforward的做法是，用一个数组保存节点。这样的话，我们看下算法复杂度。top k问题用堆解决，查询复杂度为O(k + (n-k)*log(k))，当k=8时，接近于O(n)；插入操作为O(1)。注：n为一个节点的好友节点总数。
当n很大的时候，操作时间可能会很长。那么有没有O(log(n))的算法呢？
联想到上面堆的算法，你可能说，我们可以维护一个堆啊，插入和查询的时候都是O(log(n))。这种做法堆是根据堆中元素与某一个固定不变的key的距离来维护的，但是通常情况下，我们查询的key都是变化的，因此这种做法不可行。
那还有其他O(log(n))的算法吗？
经验告诉我们，很多O(log(n))的问题都和二叉树相关，比如各种平衡二叉树，我们能不能用二叉树来解决呢？联想到每个ID都是一个160bit的值，而且我们知道key之间的距离是通过异或来计算的，并且两个key的异或结果大小和他们的共同前缀无关，我们应该想到用Trie树（或者叫前缀树）来解决。事实上，Mainline DHT协议中用的就是Trie树，但是与Trie树又稍微有所不同。在Trie树里边，插入一个key时，我们要比对key的每一个char和Trie里边路径，当不一致时，会立刻分裂成一个子树。但是在这里，当不一致时，不会立刻分裂，而是有一个长度为k的buffer（在Mainline DHT中叫bucket）。分两种情况讨论：
- 如果bucket长度小于k，那么直接插入bucket就行了。
- 如果bucket长度大于或等于k，又要分两种情况讨论：
- 第一种情况是当前的路径是该节点ID（注意不是要插入的key，是“我”自己的ID）的前缀，那么就分裂，左右子树的key分别是0和1，并且把当前bucket中的节点根据他们的当前char值分到相应的子树的bucket里边。
- 第二种情况是当前路径不是该节点ID的前缀，这种情况下，直接把这个key丢掉。
如果还没有理解，你可以参照Kademlia这篇论文上面的图。
插入的时候，复杂度为O(log(n))。查询离key最近的k个节点时，我们可以先找到当前key对应的bucket，如果bucket里边不够k个，那么我们再查找该节点前驱和后继，最后根据他们与key的距离拍一下序即可，平均复杂度也为O(log(n))。这样插入和查询都是O(log(n))。
代码实现你可以查考这里。
节点之间的通信 - KRPC
KRPC比较简单，它是一个简单的rpc结构，其是通过UDP传送消息的，报文是由bencode编码的字典。它包含3种消息类型，request、response和error。请求又分为四种：ping，find_node, get_peers, announce_peer。
- ping 用来侦探对方是否在线
- find_node 用来查找某一个节点ID为Key的具体信息，信息里包括ip，port，ID
- get_peers 用来查找某一个资源ID为Key的具体信息，信息里包含可提供下载该资源的ip:port列表
- announce_peer 用来告诉别人自己可提供某一个资源的下载，让别人把这个消息保存起来。还记得Angelababy那个例子吗？在我得到她的微信号后，我会通知所有我之前问过的人，他们就会把我有Angelababy微信号这个信息保存起来，以后如果有人再问他们有没有Angelababy微信号的话，他们就会告诉那个人我有。BT种子嗅探器就是根据这个来得到消息的，不过得到消息后我们还需要进一步下载。
跳出节点，整体看DHT这个哈希表，find_node和get_peers就是我们之前说的get(key)，announce_peer就是set(ke, val)。
剩下的就是具体的消息格式，你可以在官方文档上看到，这里就不搬砖了。
实现KRPC时，需要注意的有以下几点：
- 每次收到请求或者回复你都需要根据情况更新你的Routing Table，或保存或丢掉。
- 你需要实现transaction，transaction里边要包含你的请求信息以及被请求的ip及端口，只有这样当你收到回复消息时，你才能根据消息的transaction id做出正确的处理。Mainline DHT对于如何实现transaction没有做具体规定。
- 一开始你是不在DHT网络中的，你需要别人把你介绍进去，任何一个在DHT中的人都可以。一般我们可以向 router.bittorrent.com:6881、 dht.transmissionbt.com:6881 等发送find_node请求，然后我们的DHT就可以开始工作了。
KRPC的实现你可以参考这里。
总结
DHT整体就是一张哈希表，首先我们本身是里边的一个节点，我们向别人发送krpc find_node或get_peers消息，就是在对这个哈希表执行get(key)操作。向别人发送announce_peer消息，就是在对这个哈希表执行set(key, val)操作。
OK，今天就说到这里，关于怎么样下载，我们下篇再说。