计算机网络-p2p

2.2. 片段优化的 BitTorrent

BT下载比特币每个区块大小是多少字节，首先需要一个torrent文件，其中包含以下数据：

announce - tracker 的 URL

info - 条目映射到一个字典，其键将取决于共享的一个或多个文件：

name - 建议的保存文件名（一个文件）和目录名（多个文件）

piece length - 每个文件块的字节数。 通常 256KB = 262144B

pieces - 每个文件块的 SHA-1 综合散列。 因为 SHA-1 返回一个 160 位哈希，所以 pieces 将得到一个字符串，它是 160 位的整数倍。

length - （当只有一个文件时）文件的大小

files - （对于多个文件）字典列表（每个文件一个）具有以下键：

path - 与子目录名称对应的字符串列表，最后一项是实际文件名

length - 文件的大小（以字节为单位）

上传

 如果一个Peer想要共享一个文件或目录，则为该文件或目录生成一个“种子”文件

 然后将“种子”上传到BT网站

下载

 将 Peer 下载到 BitTorrent 网站

根据种子信息找到需要的种子并下载

用户通过BT网站搜索文件，获得.torrent文件列表中的一项或多项。

每个选定的 .torrent 文件将开始下载任务

通常.torrent会指向该文件对应的Tracker，Tracker会根据Tracker用户信息将部分用户信息交给请求方用户

与其他用户建立连接，从他们那里下载文件碎片，也提供高速高效的分片

不总是和原来的邻居交换分片，而是每隔一段时间从Tracker那里获取新的邻居

采用“阻塞算法”主动阻止那些对自己没有贡献的邻居，寻找更好的邻居 2.2.1． BitTorrent 原理

协议

torrent文件的上传和下载，Peers和Tracker之间的通信都使用HTTP协议

点之间的通信使用 BitTorrent Peer 协议 (TCP)

问题

Tracker 的单点故障

同行未经过身份验证

发展

BitTorrent 协议是开放的，任何人都可以开发服务器或客户端

BitComet风靡国内，用Python语言开发

2.2.2. BitTorrent 的阻塞算法

防止邻居只下载不上传：每个用户保持4个邻居不被屏蔽。 每20秒轮询一次（10+10），每10s决定将上传数据速率最低的邻居设置为Choking状态，并保持此状态10s，10s足够TCP调整传输速率到最大限度。 如果您仍处于窒息状态，请更换邻居。

添加新邻居后，可能会增加下载带宽，找到更好的邻居。 那么新用户没有分片就无法上传，会不会一直卡住？

Optimistic unchoking：在任何时候，每个对等点都有一个称为“optimistic unchoking”的连接，无论其下载速率如何，它始终保持畅通。 每 30 秒，重新计算哪个连接应该是“乐观的畅通无阻”。 30秒足以相应地最大化下载容量，这样即使是新进入者也有机会下载碎片

2.3. 优缺点总结

拓扑结构：服务器仍然是网络的核心

底层协议：全部使用TCP，限制连接的peer数量

查询和路由简单高效：

Napster和BT用户访问服务器； 服务器返回文件索引或种子文件； 用户直接连接另一个Peer，所以路由跳数为O(1)，即恒定跳数

容错、自适应和匿名

服务器单点故障率高

自组织自适应主要靠服务器

服务器的存在使得匿名几乎不可能

无安全认证机制的用户接入

3.非结构化P2P网络（二代）

进程：泛洪请求模式

每个 Peer 的请求直接广播给连接的 Peer

每个对等点向其连接的对等点广播

直到收到回复或达到最大泛洪步骤数（通常为 5-9 步）

特征

智能发现节点，全分布式

大量请求占用网络带宽，扩展性不一定是最好的。

协议

Gnutella/KaZaA/eDonkey/Freenet 使用此模式

消息协议：用于节点间相互发现和资源搜索

下载协议：用于在两个节点之间传输文件（使用标准的HTTP协议：GET）

提升

Kazaa设置Super-Peer客户端软件集中处理大量请求

缓存最近的请求

什么是非结构化或结构化 P2P

根本区别在于是否可以全局组织每个peer维护的邻居，方便快速查找。

非结构化网络的优势

将覆盖网络视为一个完全随机的图，其中节点之间的链接不是按照某些预定义的拓扑结构构建的。

容错性好，支持复杂查询

节点加入退出频繁，但对系统影响不大。

3.1. 牛膝草

纯分布式节点

每个 Peer 甚至服务器也是客户端

每个Peer监听本地网络的状态信息，相互协作

工作过程

原始加入：首先要连接到一个几乎一直在线的“知名”节点[或中介、引导、入口]（功能与一般Peer相同），进入Gnutella网络

查询和响应消息采用广播或反向传播（Back-propagate）机制

每条消息都被一个全球唯一的 16 字节随机数编码为一个 GUID（128 位）

每个节点缓存最近路由的消息以支持播放或防止转播

每条消息都有一个TTL号，每跳一跳递减

3.1.1. Gnutella 问题和改进

由于 Gnutella 每个节点的链接数量有限：

 泛洪广播增加了网络带宽的负担。 受TTL限制，消息只能到达一定范围，进而导致部分文件查询不到

改进：Hierarchical P2P = 增加负责查询消息的超级节点的路由，形成P2P骨干网。 叶节点只能通过超级节点代理访问

3.2. 基于超级节点的 KaZaA

基于FastTrack协议，主要用于分享MP3音乐文件

比 Gnutella 更早引入 SuperNode

KaZaA是一种加密消息的专有协议，有两种类型的节点，超级节点和普通节点

Super：高带宽、高处理能力、大存储量、不受NAT限制

Normal：低带宽，低处理能力，小存储容量，受NAT限制

加入、上传、查询

普通节点选择一个超级节点作为父节点加入，维持半永久的TCP连接

将自己贡献的文件元数据和描述符上传给它，并生成一个Hash值

父超级节点根据文件描述符关键字查询，返回文件的IP地址+元数据

3.3. 电驴/电驴/Overnet

eDonKey，由 Jed McCaleb 于 2000 年创立，专注于文件下载

与BT类似，文件是分块下载的； 内容Hash用于完整性校验，服务器是核心

BT基于文件，Tracker服务器用于查询、搜索和跟踪用户； 但 eDonKey 是类似于 KaZaA 的基于用户的超级节点。

3.4. 非结构化网络P2P总结

容错和自适应

幂律属性对随机节点故障具有高度容忍度

自适应：检测邻居是否在线

超级节点列表定期更新

可扩展性

Retrofit Flooding 提高了可扩展性

安全和匿名

非结构化且难以跟踪

增强机制 - 复制

查询分布：Uniform、Zipf

副本数：统一，与查询概率成正比，平方根副本

长处和短处

高容错性和良好的适应性，高安全性和匿名性

路由效率低/扩展性差/定位精度差

4.结构化P2P网络（第三代）

所谓结构化P2P的核心就是使用DHT作为P2P节点和资源的组织方式：

分布式哈希表

在普通的Hash Table中，key和value存储在一台主机上，而DHT将key和value存储在分散的节点上，通过Hash Table的方式进行插入和查询。

DHT的特点

自适应节点动态加入/退出

具有良好的可扩展性和健壮性

节点ID分布的均匀性和自组织能力。

可以精确找到确定性拓扑

4.1. 分布式哈希表

1）一致性哈希

一致性哈希函数使用基本哈希函数（例如 SHA-1）为每个节点和资源分配一个 mbit 标识符。

假设资源以(ObjectID,Info)的形式保存，每个节点都有NodeID，那么NodeID和ObjectID在同一个空间

因此，一致性哈希可以很容易地建立节点和资源之间的关系，即哪些节点存储哪些资源可以很容易地查询到。

2）结构化路由

节点加入：一开始，获取一个NodeID，连接到一个“bootstrap”节点，加入P2P网络

发布资源：生成资源的ObjectID，找到距离ObjectID最近的N个节点，向这N个节点广播新的资源信息，告诉这些节点我有某个资源

资源搜索：找到距离资源最近的N个节点（使用NodeID和ObjectID计算距离），向这些节点发送资源查询信息，如果有关于该资源的详细信息，则返回给客户端，否则返回更接近的资源节点列表发送给客户端，直到查询到资源提供者信息。

资源下载：如果没有找到资源提供者信息，也没有更近的节点，说明该资源没有提供者。 如果找到资源提供者信息（NodeID、ip、端口），请求资源提供者

多个节点有相同的资源，则资源搜索可以得到资源提供者列表，可以开始P2P下载

结构化路由和泛洪路由的区别：有目的、有针对性的路由

4.2. 弦

环形P2P网络

Chord：优雅精准的P2P网络

在一个有 N 个节点的网络中，每个节点都持有关于 O(logN) 个其他节点的信息

可以在 O(logN) 跳内找到存储数据对象的节点

当节点离开或加入网络时，保持Chord自适应所需的消息数O(log2N)=O((logN)2)

提供数据对象的存储、查询、复制和缓冲

协作文件系统CFS（Cooperative File System）建立在其上

4.2.1. 工作原理 4.2.1.1。 ID的分配

通过散列函数（例如 SHA-1）（安全散列标准）

NodeID=H(节点属性)=H(IP地址/端口号/公钥/随机数/或其组合)

ObjectID=H(对象属性)=H(数据名称/内容/大小/发布者/或其组合)

SHA-1的长度值m=160 Bits，以保证其唯一性和几乎不可重复性，所以nodeID/objectID可以选择在[0...2^m)

4.2.1.2. 索引分配

NodeIDs从小到大顺时针排列在一个环上

数据对象k（即ObjectID=k）也在环上顺时针分布到节点k或第一个大于k的节点（因为有环，所以需要mod 2^m）。这个节点称为Successor（ k) 节点

形式化表达 Successor(objectk) = nodek or nodex，x为现有网络上第一个顺时针大于k的节点

4.2.1.3. 节点路由表的分配

Chord 显然适用于上述后继关系

但是查询效率低。 比如要找一个ObjectID=K的​​资源，就得先问K个节点是否存在，再找K+1个。 在最坏的情况下，您需要顺序查询 O(N) 个节点。

所以Chord引入finger table来优化，finger table其实类似于路由表：让每一步更接近目的节点更快

指向表：手指表

每个节点存储一个大小为m的路由表（finger table）以减少路由跳数

在节点n的路由表中，第i项指向节点s = Successor(n+2^i-1), 1≤i≤m

所以s是顺时针方向距离节点n至少2^(i-1)的第一个节点：表示为n.finger[i].node

除了对象 k 有 Successor，节点 n 也有 Successor 节点，即 n.finger[1].node

路由表条目还包括相关节点的 NodeID、IP 地址和端口号

特征

每个节点只保存很少的关于其他节点的信息，对离它越远的节点了解越少

一个节点不能直接从自己的路由表中看到对象k的后继节点

4.2.1.4。 查找资源（不修改手指）

通过指表，可以快速找到一个key的Successor：

假设k为ObjectID，要找到持有k的Succesor(k)节点，从节点n开始查找（n可以是任意节点）

节点n在自己的路由表中寻找k之前距离k最近的节点j，让j找到离k更近的节点，如此递归，j会越来越靠近k，最后找到 n'

n'是k之前最接近k的节点

那么n'的Successor就是要找的节点Successor(k)

4.2.1.5。 新节点加入（修改手指）

Chord中加入新节点后，为了更新finger表，每个节点除了Successor之外还有一个Predecessor节点

前驱节点：Predecessor(n)

在节点n之前，节点Predecessor(n)不等于n且最接近n

4.2.1.6. 离开 Chord 的节点

左图中，节点6加入了各节点路由表的变化（灰色为未变化）

右侧，Node 1留下了各节点路由表的变化（论文中错误标记为Node 3）

（还有：Node 1离开后，Node 0的finger表中的第一项应该是3）

4.2.2. 协作文件系统CFS简介

CFS是一个基于Chord的P2P只读文件存储系统

依靠 Chord 作为其分布式哈希表来提供高效、容错和负载均衡的文件存储和检索

系统由三层组成：文件系统FS、分布式哈希表DHash和底层位置哈希表Chord

每个节点既是服务器又是客户端

功能说明

FS：high-level，从DHash层获取数据块，将这些块转化为文件，与上层文件系统接口

DHash：中间层，分发和缓存数据块用于负载均衡，复制数据块用于容错，通过服务器选择减少延迟，使用Chord定位数据块

Chord：底层维护路由表，定位数据块所在服务器。每个服务器都是Chord的一个节点

4.2.3. 和弦：总结

简单、精确，但需要

每个节点的后继者总是准确的

每个对象k的后继节点总是带有k的索引

查询和维护成本

查询代价：m项的平均间隔delta = [2^0+ 2^1+... +2^m-1]/m； 假设J跳命中后覆盖节点数≤2^m； 所以 J*delta≤2 ^m ； 因此，J≤m = O(log N)； 查询路由的平均跳数为 O(logN)

维护成本：节点进入/退出的O(log2N)，适应最新状态

缺点：

没有实际用途（只是一个文件共享应用程序）

不支持不精确查找

手指表有冗余

维护手指表（加入/退出）相对昂贵

和弦的问题

(1): finger表有冗余

以2^i为跨度在路由表中寻找后继节点，会在finger中产生一定的冗余，即节点稀疏时，路由容易冗余

(2)：路由维护开销大

节点加入：Chord需要环形拓扑中的任一节点协助完成，加入过程包括两个阶段：新节点自身的Join操作和其他节点finger表的修改；

节点故障的处理：Chord需要周期性检测节点的前驱节点和后继节点，并在节点加入时根据算法重建Finger表；

节点退出的处理：Chord采用了将节点退出视为失败的处理方式。

4.3. Kademlia，一个结构化的 P2P 网络

Kademlia类似于Chord，属于恒度P2P网络

路由、定位、自组织方式与前四种没有太大区别

每个节点的“度”（连接数）是固定的，与规模无关

维护固定的路由表条目仍然可以达到O(logN)跳的索引定位效率

固定路由表可减少网络适配开销

更具容错性和实用性的结构化网络Kademlia

类似于Chord的路由方式

加入和离开节点更容易

4.3.1. 节点之间的异或距离

定义两个节点x、y（用ID值表示）之间的“异或”距离（非欧距离）

节点和数据对象都使用 SHA-1 分配 160 位 ID，

对象索引由最接近 objectID 的 nodeID 处理，“最接近”由 XOR 距离测量

d(x,y)=x⊕y，如1011⊕0010=1001=9 > 1011⊕1010=0001=1

XOR 距离的属性：

合理性：d(x,x) = 0

非负性：d(x,y) ≥ 0

对称性：对于任何 x,y 和 x≠y，d(x,y) = d(y,x)。 （和弦没有）

三角不等式：d(x,y)+d(y,z)≥ d(x,z)

因为 d(x,z) = d(x,y)⊕d(y,z)

对于任何 a≥0, b≥0 , a+b≥ a⊕b

单向：任意节点x距离d，系统中只有一个节点-y满足d(x,y)=d

单向性保证相同数据的位置最终会收敛在同一条路径上

传递性：显然如果 d1≥d2 且 d2≥d3 ，则 d1≥d3 成立

4.3.2. XOR 距离结构优势

根据当前节点ID与所有其他节点ID的异或距离进行排队。 知道目标节点ID后，就很容易计算出目标节点在这个队列中的位置；

如果给你一个异或距离，你也可以很容易地从这个队列中找到距离最近的节点

与自身前缀相似度较高的节点离自身较近（异或后高位为0）

4.3.3. K-bucket路由表

K-buckts：每个节点维护一个路由表，由logN（N为最大节点数）k个桶组成

本质是一个链表集合比特币每个区块大小是多少字节，每个节点0≤i<160个桶； 每个桶包含Max（10或20）条记录=（序号i，异或到自身的距离[2i—2i+1），节点信息）

节点信息 = 三元组

表条目按访问时间排序，最近最少访问的放在末尾，最近访问的放在最前面

4.4. 比特币和区块链 4.4.1。 非对称加密

比特币使用椭圆曲线算法，一个私钥可以导出一个唯一的公钥，反之亦然。

4.4.2. 交易

通过关联密钥将钱交给新所有者。

4.4.3. 比特币区块

多个比特币交易将被打包在一个区块中，每个区块大小为1Mbyte

每笔交易在区块的 tx 数组中都会有一个唯一的 ID

每笔交易vin中包含的比特币数量减去vout中的比特币数量即为交易手续费

4.4.4. 比特币区块链

比特一条区块链是一个单向链表

每个区块都保存了前一个区块的哈希值，因此任何人想要篡改链中的一个区块，都会破坏整个区块链，并被 P2P 网络中的其他节点发现。

在比特币网络中，矿工负责打包区块，任何人都可以成为矿工。

如右图所示，如果不同的矿工在不同的链上打包区块会怎样？ 全网识别最长链（工作量最大）

所有矿工都可以在打包过程中竞争。 关键是看谁先算出一个合法的nonce，让当前块的hash值前面有指定个数的0（比如5个）。

0的个数由全网哈希能力决定，每隔一段时间调整一次，大概十分钟左右就可以计算成功。

打包成功的矿工，交易手续费归他所有。

4.4.5. 区块链竞赛