原理篇 理解IPFS
第2章 IPFS底层基础
欢迎来到第2章。这一章的内容相对较多，也相对独立。你可以选择先阅读这一章，了解这几个基础性系统的设计思路和算法细节；或者暂时跳过这一章，直接去了解IPFS系统设计。在这一章中，我们会着重介绍IPFS的几个基础性的子系统和数据结构，包括DHT、BitTorrent、Git和自验证文件系统，以及Merkle结构。
2.1 分布式哈希表（DHT）
第1代P2P文件网络需要中央数据库协调，例如在2000年前后风靡一时的音乐文件分享系统Napster。在Napster中，使用一个中心服务器接收所有的查询，服务器会向客户端返回其所需要的数据地址列表。这样的设计容易导致单点失效，甚至导致整个网络瘫痪。在第2代分布式文件系统中，Gnutella使用消息洪泛方法（message flooding）来定位数据。查询消息会公布给全网所有的节点，直到找到这个信息，然后返回给查询者。当然，由于网络承载力有限，这种盲目的请求会导致网络快速耗尽，因此需要设置请求的生存时间以控制网络内请求的数量。但无论如何，这种方式所需的网络请求量非常大，很容易造成拥堵。到了第3代分布式文件系统中，DHT的创新提供了新的解决方案。DHT（Distributed Hash Table）主要思想如下：全网维护一个巨大的文件索引哈希表，这个哈希表的条目形如<Key, Value>。这里Key通常是文件的某个哈希算法下的哈希值（也可以是文件名或者文件内容描述），而Value则是存储文件的IP地址。查询时，仅需要提供Key，就能从表中查询到存储节点的地址并返回给查询节点。当然，这个哈希表会被分割成小块，按照一定的算法和规则分布到全网各个节点上。每个节点仅需要维护一小块哈希表。这样，节点查询文件时，只要把查询报文路由到相应的节点即可。下面介绍3种IPFS引用过的有代表性的分区表类型，分别是Kademlia DHT、Coral DHT和S/Kademlia。
2.1.1 Kademlia DHT
Kademlia DHT是分布式哈希表的一种实现，它的发明人是Petar Maymounkov和David Mazières。Kademlia DHT拥有一些很好的特性，如下：
❑ 节点ID与关键字是同样的值域，都是使用SHA-1算法生成的160位摘要，这样大大简化了查询时的信息量，更便于查询。
❑ 可以使用XOR，计算任意两个节点的距离或节点和关键字的距离。
❑ 查找一条请求路径的时候，每个节点的信息是完备的，只需要进行Log(n)量级次跳转。
❑ 可根据查询速度和存储量的需求调整每个节点需要维护的DHT大小。
KAD网络对之前我们说的DHT有较大的改进，一个新来的网络节点在初次连接网络时会被分配一个ID；每个节点自身维护一个路由表和一个DHT，这个路由表保存网络中一部分节点的连接信息，DHT用于存放文件信息；每个节点优先保存距离自己更近的节点信息，但一定确保距离在[2n,2(n+1)-1]的全部节点至少保存k个（k是常数），我们称作K-Bucket；每个网络节点需要优先存储与自己的ID距离较小的文件；每次检索时，计算查询文件的哈希值与自己的ID的距离，然后找到与这个距离对应的K-Bucket，向K-Bucket中的节点查询，接受查询的节点也做同样的检查，如果发现自己存有这个数据，便将其返回给查询的节点。
下面我们详细说明一下KAD网络算法细节。
1．Kademlia二叉状态树
Kademlia网络的节点ID是由一棵二叉树维护的，最终生成的二叉树的特点如下：
❑ 每个网络节点从根节点出发，沿着它的最短唯一前缀到达。
❑ 每个网络节点是叶子节点。图2-1表示了二叉树的形成过程，例如这里黑色的节点ID拥有一个唯一的前缀0011。对于任意的一个树的节点，我们可以沿着它的前缀作为路径，向下分解成一系列不包含自己的子树。Kademlia二叉树的建立，需要确保每个网络的节点都能从树根沿着它的最短唯一前缀的路径到达。
图2-1 Kademlia ID二叉树结构
下面我们介绍一下节点哈希是0011….（一共160位）的子树划分方法。
现在我们的网络上有18个节点，如图2-1所示。从树根开始，树根的前缀是空。左子树和右子树的编号分别是1和0。因为还存在其他10个节点都有共同的前缀0，那么我们继续划分成00和01两棵子树，我们的目标节点（哈希值0011…）显然属于00这棵子树。我们继续检查，发现还有3个节点是00前缀，那么继续划分子树001、000。哈希位00100…和00101…两个节点与0011依旧是共有001前缀，所以001还不是最短唯一前缀，我们再继续划分子树，到0011，那么不再有其他节点有相同的前缀，这条路径0011就是到树根最短的路径，同时0011是最短唯一前缀，0011就成为它的网络ID。
在Kademlia中，每个DHT条目包含<key, value>对。key是文件的哈希值，value是节点ID。key和value有相同的值域，都是160位。每一个新加入网络的计算机都会被随机分配一个节点ID值。数据存放在key值与ID值最接近key值的节点上。这样，我们就需要定义它们的远近了。XOR运算可以解决这个问题。<key, Value>在160位Hash上，判断两个节点x、y的距离远近的方法是进行二进制运算异或，d(x, y)=x⊕y。两个二进制位结果相同，它们的异或值是0；如不同，值为1。例如，我们将111010和101011取XOR。
111010 XOR 101011 ---------------- 010001
对于异或操作，有如下一些数学性质：
❑ d(x, x)=0
❑ d(x, y)>0, iff x≠y
❑ x, y:d(x, y)=d(y, x)
❑ d(x, y)+d(y, z)≧d(x, z)
❑ d(x, y)⊕d(y, z)=d(x, z)
❑ 存在一对x≧0, y≧0，使得x+y≧x⊕y
我们很自然地发现，如果给定了x，任意一个a(a≧0)会唯一确定另一个节点y，满足d(x, y)=a。假设这里的x是我们需要查询的文件key，我们只需要不断更新y，使得y沿着d(x, y)下降的方向找下去，那么一定能收敛到距离x最近的点。前面我们提到，文件就是存放在网络编号与文件哈希的XOR最近的几个节点上。那么换句话说，只要沿着XOR距离降低的方向查找，从任意一个网络节点开始查询，我们总能找到这个存放文件的地址。而且每次更新总能筛选掉一半的节点，那么最多只需Log N步即可到达。
2．节点路由表K-Bucket
节点路由表用于保存每个节点与自己一定距离范围内其他节点的连接信息。每一条路由信息由如下3部分组成：IP Address、UDP Port、Node ID。KAD路由表将距离分成160个K桶（存放K个数据的桶），分开存储。编号为i的路由表，存放着距离为[2i,2(i+1)-1]的K条路由信息。并且每个K桶内部信息存放位置是根据上次看到的时间顺序排列的，最早看到的放在头部，最后看到的放在尾部。因为网络中节点可能处于在线或者离线状态，而在之前经常在线的节点，我们需要访问的时候在线的概率更大，那么我们会优先访问它（尾部的节点）。
通常来说当i值很小时，K桶通常是空的（以0为例，距离为0自然只有1个节点，就是自己）；而当i值很大时，其对应K桶的项数又很可能特别多（因为范围很大）。这时，我们只选择存储其中的K个。在这里k的选择需要以系统性能和网络负载来权衡它的数量。比如，在BitTorrent的实现中，取值为k=8。因为每个K-Bucket覆盖距离范围呈指数增长，那么只需要保存至多160K个路由信息就足以覆盖全部的节点范围了。在查询时使用递归方式，我们能证明，对于一个有N个节点的KAD网络，最多只需要经过log N步查询，就可以准确定位到目标节点。
当节点x收到一个消息时，发送者y的IP地址就被用来更新对应的K桶，具体步骤如下。
1）计算自己和发送者的ID距离：d(x, y)=x⊕y。
2）通过距离d选择对应的K桶进行更新操作。
3）如果y的IP地址已经存在于这个K桶中，则把对应项移到该K桶的尾部；如果y的IP地址没有记录在该K桶中，则：
①如果该K桶的记录项小于k个，则直接把y的(IP address, UDP port, Node ID)信息插入队列尾部。
②如果该K桶的记录项大于k个，则选择头部的记录项（假如是节点z）进行RPC_PING操作。
❑ 如果z没有响应，则从K桶中移除z的信息，并把y的信息插入队列尾部。
❑ 如果z有响应，则把z的信息移到队列尾部，同时忽略y的信息。
K桶的更新机制非常高效地实现了一种把最近看到的节点更新的策略，除非在线节点一直未从K桶中移出过。也就是说，在线时间长的节点具有较高的可能性继续保留在K桶列表中。采用这种机制是基于对Gnutella网络上大量用户行为习惯的研究结果，即节点的在线概率与在线时长为正比关系，如图2-2所示。
图2-2 网络中在线时长和继续在线的概率关系
可以明显看出，用户在线时间越长，他在下一时段继续在线的可能性就越高。所以，通过把在线时间长的节点留在K桶里，可以明显增加K桶中的节点在下一时间段仍然在线的概率，这利于保持KAD网络的稳定性和减少网络维护成本（不需要频繁构建节点的路由表）。
（1）路由查询机制
KAD技术最大特点之一就是能够提供高效的节点查找机制，并且还可以通过参数调节查找的速度。假如节点x要查找ID值为t的节点，Kad按照如下递归操作步骤进行路由查找：
1）计算到t的距离：d(x, t)=x⊕t。
2）从x的第log(d)个K桶中取出α个节点的信息，同时进行FIND_NODE操作。如果这个K桶中的信息少于α个，则从附近多个桶中选择距离最接近d的总共α个节点。
3）对接受到查询操作的每个节点，如果发现自己就是t，则回答自己是最接近t的；否则测量自己和t的距离，并从自己对应的K桶中选择α个节点的信息给x。
4）x对新接收到的每个节点都再次执行FIND_NODE操作，此过程不断重复执行，直到每一个分支都有节点响应自己是最接近t的。
5）通过上述查找操作，x得到了k个最接近t的节点信息。
这里强调，是k个最接近t的节点信息，而不是完全信息相等，因为网络中可能根本不存在ID为t的节点。α也是为权衡性能而设立的一个参数，就像K一样。在BitTorrent实现中，取值为α=3。这个递归过程一直持续到x=t，或者路由表中没有任何关于t的信息。由于每次查询都能从更接近t的K桶中获取信息，这样的机制保证了每一次递归操作都能够至少获得距离减半（或距离减少1bit）的效果，从而保证整个查询过程的收敛速度为O(logN)，这里N为网络全部节点的数量。
上述是查询节点ID的方法，对于文件查询也是一样的方法。区别仅在于进行FIND_Value操作，查找自己是否保存ID为t的文件。文件查询过程的收敛速度同样是O(LogN)。
（2）节点加入和离开
如果节点u要加入KAD网络，它必须和一个已经在KAD网络中的节点，比如w，取得联系。u首先把w插入自己适当的K桶中，对自己的节点ID执行一次FIND_NODE操作，然后根据接收到的信息更新自己的K桶内容。通过对自己邻近节点由近及远的逐步查询，u完成了仍然是空的K桶信息的构建，同时也把自己的信息发布到其他节点的K桶中。在KAD网络中，每个节点的路由表都表示为一棵二叉树，叶子节点为K桶，K桶存放的是有相同ID前缀的节点信息，而这个前缀就是该K桶在二叉树中的位置。这样，每个K桶都覆盖了ID空间的一部分，全部K桶的信息加起来就覆盖了整个160bit的ID空间，而且没有重叠。
以节点u为例，其路由表的生成过程如下：
1）最初，u的路由表为一个单个的K桶，覆盖了整个160bit ID空间。
2）当学习到新的节点信息后，则u会尝试把新节点的信息，根据其前缀值插入对应的K桶中。
①该K桶没有满，则新节点直接插入这个K桶中；
②该K桶已经满了：如果该K桶覆盖范围包含了节点u的ID，则把该K桶分裂为两个大小相同的新K桶，并对原K桶内的节点信息按照新的K桶前缀值进行重新分配；如果该K桶覆盖范围没有包含节点u的ID，则直接丢弃该新节点信息。
3）上述过程不断重复，直到满足路由表的要求。达到距离近的节点的信息多、距离远的节点的信息少的结果，这样就保证了路由查询过程能快速收敛。
节点离开KAD网络不需要发布任何信息，等待节点离线的时间足够长，其他网络节点访问它失效后，便会自动将其移出各自的路由表，那么这一节点也就离开了。
2.1.2 Coral DSHT
Coral协议是在2004年，由纽约大学的Michael Freedman、Eric Freudenthal和David Nazieres发明的一套内容分发网络系统（Content Delivery Network）。CDN的设计是为了避开互联网传输瓶颈，并且降低内容供应服务器的网络压力，使得内容能更快速、更稳定地传递给客户端。CDN的基本思想是在网络部署一些节点服务器，并且建立一套虚拟网络。网络中节点服务器之间实时更新连接信息、延时信息、用户距离参数等，然后将用户的请求重定向到最适合的节点服务器上。这样做有诸多好处，首先，通过节点服务器中转，用户访问网页的速度大大提高了；其次，节点服务器会缓存内容服务器的查询信息，那么也降低了内容服务器的网络负载；最后，内容服务器有可能出现暂时的离线，那么用户同样能通过节点服务器中的缓存读取。
Coral DSHT则是Coral CDN最核心的部件之一。我们在2.1.1节中阐述过，Kademlia协议使用的是XOR距离，即信息永远是存储在XOR距离最近的节点中。而这并没有考虑实际网络的情况，例如节点之间的延时、数据的位置。这样会浪费大量网络带宽和存储空间。Coral解决了这个问题，不同于经典的DHT方式，Coral首先对所有的节点评估连接情况，然后根据循环时间（Round-Trip Time）划分为几个等级（Coral中是3层），L2(<20ms)、L1(<60ms)、L0（其他）。Coral还提供了两个操作接口，put和get，用于添加和查找一个键值对，以确定从哪一个等级的DSHT中查询。后面我们会详细描述它是如何实现的。
Coral DSHT（Distributed Sloppy hash table）适用于软状态的键值对检索，也就是同一个Key可能会保存多个Value。这种机制能把给定的Key映射到网络中的Coral服务器地址。比如，使用DSHT来查询距离用户较近的域名服务器；查询拥有特定网站缓存信息的服务器；定位周围的节点来最小化请求延时。
1．索引机制和分层
Coral对路由表的处理也比较特殊，每一个Coral节点根据它们的延时特性放在不同的DSHT中。同一个DSHT的节点被称为一个集群（Cluster），每个集群有一个最大延时时间，称为集群直径（Diameter）。而整个系统会预先设定一个直径，称为等级（Level）。在每个等级划分下，每个节点都会是某一个DSHT的成员。一组节点只有满足两两直径小于第i个等级的极限时，它们才能成为一个集群。在Coral中，将DSHT分成了三层，Level-2对应两两延时小于20毫秒，Level-1对应两两延时小于60毫秒，Level-0对应其他的全部节点。Coral在询问时，也会优先请求等级更高、相应时间更短的节点。如果失败了，才会在下一级节点中请求。这样的设计不但降低了查询的延时，也更可能优先获得临近节点的返回数据。
2．基于键值对的路由层
Coral的键值对与Kademlia一样，都是由SHA-1哈希计算得来的，有160bit。每个节点的ID是由它的IP地址通过SHA-1运算出来的。我们在此可以通过Put指令保存一个<Key, Value>对，用来表明Key和Value是接近的；也可以通过Get指令，来查询对于同一个Key，节点的远近顺序如何。具体的计算方法和路由方法与在2.1.1节中讲的Kademlia协议是一样的。
3．Sloppy存储
在Kademlia协议中，数据会直接保存到XOR更近的节点。但实际情况是，如果某些数据非常热门，其他节点也会大量查询，会因此造成拥塞，我们称作Hot-Spot；同时，一个缓存键值对存储了过多的值，我们称其为Tree-saturation。Sloppy存储就是希望规避这两种情况发生。
每一个Coral节点定义有两种异常状态，Full和Loaded。Full状态定义为：在当前节点R，已经存在L个<Key, Value>对使得Key=k，并且这L个键值对的生存周期都大于新值的1/2。Loaded状态定义为：对于给定的Key=k，在过去的一分钟里已经收到超过特定次请求。
那么Coral在执行存储操作的时候分为两步进行。
第1步为前向查询，Coral会持续迭代查找距离Key更近的节点ID，这一点和Kademlia协议完全一样。每一个节点返回两个信息，其一，该节点是否加载，其二，对于该Key，这一节点存储有几个Value，每一个Value的实效时间是多长。客户端根据接收到的这些信息决定这些节点是否可以存储新的值。前向查询的过程会一直继续，直到客户端找到一个距离Key值最近的可连接节点。如果对某个节点查询异常，这一节点将不再继续迭代查询。可连接节点将被逐一压进堆栈里。
第2步为反向查询，客户端从第1步中得到了可以存放的节点列表。那么按照距离Key从近到远的顺序，依次尝试添加<Key, Value>对到这些节点。如果操作失败，比如在此时有其他节点也进行了插入，这一节点成为FULL状态，那么客户端将放弃存储这一节点，将其从堆栈内弹出，并尝试下一个节点，直到被成功存储。
取回的操作其实是存放操作的逆过程，在此不赘述。
2.1.3 S/Kademlia DHT
Kademlia用于完全开放的P2P网络，如果不提供任何安全措施，它很容易受到来自恶意节点发动的各类攻击。由此Ingmar Baumgart和Sebastian Mies二人设计了一种更安全的S/Kademlia（S/K）协议。基于Kademlia协议，S/K协议在节点ID中加入隐式身份认证和兄弟广播（sibling Broadcast）。这样，S/K就有能力抵御常见的日蚀攻击（eclipse attack）和女巫攻击（Sybil attack）了。
1．Kademlia面临的攻击
按照受到攻击的结构来看，攻击主要分为两类，第1类攻击是针对路由表控制网络中部分节点；第2类则是恶意消耗占用节点的资源。前者包括日蚀攻击、女巫攻击、流失攻击（Churn attack）和对抗路由攻击。
（1）日蚀攻击
如果一个节点在网络中能够自由选择它的ID，攻击者可以在网络中安放一些恶意节点，使得信息都必须经由恶意节点传递。那么这样一来，恶意节点就能够在网络中将一个或几个节点从网络中隐藏掉。只要恶意节点不能自由选择ID或者很难通过策略修改其他节点的K-Bucket，这一攻击就能避免了。我们从2.1.1节得知，KAD会优先请求K-Bucket中的长时间在线的节点，一旦被攻击节点的K-Bucket是非满的，恶意节点就有机会加入攻击节点的K-Bucket，那么攻击者只要拥有足够长的在线时间就能实现攻击了。
（2）女巫攻击
在开放的对等网络里，攻击者可以假冒多个ID，用少数网络节点控制多个虚假身份。KAD网络难以控制节点的数量，那么攻击者伪造大量虚假节点身份，就能控制部分网络。通常情况下可以通过消耗一定的系统和计算资源提高女巫攻击者的成本。当然，这也只能改善并不能杜绝。
（3）流失攻击
攻击者拥有网络的一些节点，即恶意节点，这可能会在网络中引发大量流量流失，从而导致网络稳定性降低。
（4）对抗路由攻击
恶意节点在收到查询指令后，不是按照KAD的要求返回距离Key最接近的网络节点，而是转移给同伙节点。同伙节点也做同样的操作，而不返回给查询节点所需要的信息，那么这样一来查询就会失效。我们发现，整个过程中必须将查询信息传递给恶意节点，这一攻击才能发动。那么我们可以在查询时，设计算法并行地查询，并且每一条查询路径不相交。这样一来，只要并行查询的路径中有一条不碰到恶意节点，查询就能成功了。
2．S/K防护方式
S/K协议就是做出了上述的几个改进：为了避免日蚀攻击和女巫攻击，S/K需要节点不能自由选择节点ID，不能大批量生成ID，同时不能窃取和伪装其他节点的ID。这一方法可以通过非对称加密确保节点身份不被窃取，我们可以设置一定的计算量障碍，强迫节点进行一定的哈希运算来确保不能自由选择和批量生产ID。
为了避免对抗路由攻击，我们需要并行查找不相交的路径。
（1）安全的节点分配策略
S/K节点ID分配策略方案有3个要求：节点不能自由选择其ID；不能生成多个ID；不能伪装和窃取其他节点的ID。
为了实现这些要求，S/K设置了如下方法增加攻击的难度。每个节点在接入前必须解决两个密码学问题，静态问题是：产生一对公钥和私钥，并且将公钥做两次哈希运算后，具有c1个前导零。那么公钥的一次哈希值，就是这个节点的NodeID。动态问题是：不断生成一个随机数X，将X与NodeID求XOR后再求哈希，哈希值要求有c2个前导零。静态问题保证节点不再能自由选择节点ID了，而动态问题则提高了大量生成ID的成本。那么女巫攻击和日蚀攻击将难以进行。
为确保节点身份不被窃取，节点需要对发出的消息进行签名。考虑安全性，可以选择只对IP地址和端口进行弱签名；或者对整个消息进行签名，以保证消息的完整性。在其他节点接收到消息时，首先验证签名的合法性，然后检查节点ID是否满足上述两个难题的要求。我们发现，对于网络其他节点验证信息的合法性，它的时间复杂度仅有(1)；但是对于攻击者，为了生成这样一个合法的攻击信息，其时间复杂度是（2c1+2c2）。合理选取c1和c2，就能有效避免这3种攻击方式了。
（2）不相交路径查找算法
在KAD协议中，我们进行一次查询时，会访问节点中的α个K-Bucket中的节点，这个K-Bucket是距离我们需要查询的Key最近的。收到回复后，我们再进一步对返回的节点信息排序，选择前α个节点继续迭代进行请求。很明显，这样做的缺点是，一旦返回的其他节点信息是一组恶意节点，那么这个查询很可能就会失败了。
为解决这个问题，S/K提出的方案如下：每次查询选择k个节点，放入d个不同的Bucket中。这d个Bucket并行查找，Bucket内部查找方式和KAD协议完全相同。这样一来，d条查找路径就能做到不相交。对于任意一个Bucket，有失效的可能，但是只要d个Bucket中有一条查询到了所需要的信息，这个过程就完成了。
通过不相交路径查找，能解决对抗路由攻击。S/K协议将Kademlia协议改进后，针对常见的攻击，其安全性能大大提高了。
2.2 块交换协议（BitTorrent）
BitTorrent是一种内容分发协议，它的开创者是美国程序员Bram Cohen（也是著名游戏平台Steam的设计者）。BitTorrent采用内容分发和点对点技术，帮助用户相互更高效地共享大文件，减轻中心化服务器的负载。BitTorrent网络里，每个用户需要同时上传和下载数据。文件的持有者将文件发送给其中一个或多个用户，再由这些用户转发给其他用户，用户之间相互转发自己所拥有的文件部分，直到每个用户的下载全部完成。这种方法可以减轻下载服务器的负载，下载者也是上传者，平摊带宽资源，从而大大加快文件的平均下载速度。
2.2.1 BitTorrent术语含义
以下是BitTorrent中涉及的术语。
❑ torrent：它是服务器接收的元数据文件（通常结尾是．Torrent）。这个文件记录了下载数据的信息（但不包括文件自身），例如文件名、文件大小、文件的哈希值，以及Tracker的URL地址。
❑ tracker：是指互联网上负责协调BitTorrent客户端行动的服务器。当你打开一个torrent时，你的机器连接tracker，并且请求一个可以接触的peers列表。在传输过程中，客户端将会定期向tracker提交自己的状态。tracker的作用仅是帮助peers相互达成连接，而不参与文件本身的传输。
❑ peer:peer是互联网上的另一台可以连接并传输数据的计算机。通常情况下，peer没有完整的文件。peer之间相互下载、上传。
❑ seed：有一个特定torrent完整拷贝的计算机称为seed。文件初次发布时，需要一个seed进行初次共享。
❑ swarm：连接一个torrent的所有设备群组。
❑ Chocking:Chocking阻塞是一种临时的拒绝上传策略，虽然上传停止了，但是下载仍然继续。BitTorrent网络下载需要每个peer相互上传，对于不合作的peer，会采取临时的阻断策略。
❑ Pareto效率：帕累托效率（Pareto efficiency）是指资源分配已经到了物尽其用的阶段，对任意一个个体进一步提升效率只会导致其他个体效率下降。此时说明系统已经达到最优状态了。
❑ 针锋相对（Tit-fot-Tat）：又叫一报还一报，是博弈论中一个最简单的策略。以合作开局，此后就采取以其人之道还治其人之身的策略。它强调的是永远不先背叛对方，除非自己被背叛。在BitTorrent中表现为，Peer给自己贡献多少下载速度，那么也就贡献多少上传速度给他。
2.2.2 P2P块交换协议
1．内容的发布
现在我们从流程上解释，一个新文件是如何在BitTorrent网络上传播的。新的文件发行，需要从seed开始进行初次分享。首先，seed会生成一个扩展名为．torrent的文件，它包含如下信息：文件名、大小、tracker的URL。一次内容发布至少需要一个tracker和一个seed, tracker保存文件信息和seed的连接信息，而seed保存文件本身。一旦seed向tracker注册，它就开始等待为需要这个torrent的peer上传相关信息。通过．torrent文件，peer会访问tracker，获取其他peer/seed的连接信息，例如IP和端口。tracker和peer之间只需要通过简单的远程通信，peer就能使用连接信息，与其他peer/seed沟通，并建立连接下载文件。
2．分块交换
前面我们提到，peer大多是没有完整的拷贝节点的。为了跟踪每个节点已经下载的信息有哪些，BitTorrent把文件切割成大小为256KB的小片。每一个下载者需要向他的peer提供其拥有的片。为了确保文件完整传输，这些已经下载的片段必须通过SHA-1算法验证。只有当片段被验证是完整的时，才会通知其他peer自己拥有这个片段，可以提供上传。
3．片段选择算法
上面我们发现，BitTorrent内容分享的方式非常简单实用。但是，直觉上我们会发现如何合理地选择下载片段的顺序，对提高整体的速度和性能非常重要。如果某片段仅在极少数peer上有备份，则这些peer下线了，网络上就不能找到备份了，所有peer都不能完成下载。针对这样的问题，BitTorrent提供了一系列片段选择的策略。
❑ 优先完成单一片段：如果请求了某一片段的子片段，那么本片段会优先被请求。这样做是为了尽可能先完成一个完整的片段，避免出现每一个片段都请求了同一个子片段，但是都没有完成的情况。
❑ 优先选择稀缺片段：选择新的片段时，优先选择下载全部peer中拥有者最少的片段。拥有者最少的片段意味着是大多数peer最希望得到的片段。这样也就降低了两种风险，其一，某个peer正在提供上传，但是没有人下载（因为大家都有了这一片段）；其二，拥有稀缺片段的peer停止上传，所有peer都不能得到完整的文件。
❑ 第一个片段随机选择：下载刚开始进行的时候，并不需要优先最稀缺的。此时，下载者没有任何片断可供上传，所以，需要尽快获取一个完整的片断。而最少的片断通常只有某一个peer拥有，所以，它可能比多个peer都拥有的那些片断下载得慢。因此，第一个片断是随机选择的，直到第一个片断下载完成，才切换到“优先选择稀缺片段”的策略。
❑ 结束时取消子片段请求：有时候，遇到从一个速率很慢的peer请求一个片断的情况，在最后阶段，peer向它的所有的peer都发送对某片断的子片断的请求，一旦某些子片断到了，那么就会向其他peer发送取消消息，取消对这些子片断的请求，以避免浪费带宽。
2.2.3 阻塞策略
不同于HTTP协议，BitTorrent中文件分享完全依赖每个peer，因此每个peer都有义务来共同提高共享的效率。对于合作者，会根据对方提供的下载速率给予同等的上传速率回报。对于不合作者，就会临时拒绝对它的上传，但是下载依然继续。阻塞算法虽不在P2P协议的范畴，但是对提高性能是必要的。一个好的阻塞算法应该利用所有可用的资源，为所有下载者提供一致可靠的下载速率，并适当惩罚那些只下载而不上传的peer，以此来达到帕累托最优。
1．BitTorrent的阻塞算法
某个peer不可能与无限个peer进行连接，通常情况只能连接4个peer。那么怎么控制才能决定选择哪些peer连接使得下载速度达到最优？我们知道，计算当前下载速度其实很难，比如使用20秒轮询方式来估计，或者从长时间网络流量来估计，但是这些方法都不太可行，因为流量随着时间产生的变化太快了。频繁切换阻塞/连接的操作本身就会带来很大的资源浪费。BitTorrent网络每10秒重新计算一次，然后维持连接状态到下一个10秒才会计算下一次。
2．最优阻塞
如果我们只考虑下载速度，就不能从目前还没有使用的链接中去发现可能存在的更好的选择。那么，除了提供给peer上传的链接，还有一个始终畅通的链接叫最优阻塞。不论目前的下载情况如何，它每间隔30秒就会重新计算一次哪一个链接应该是最优阻塞。30秒的周期足够达到最大上传和下载速率了。
3．反对歧视
在特殊情况下，某个peer可能被全部的peer阻塞了，那么很显然，通过上面的方法，它会一直保持很低的下载速度，直到经历下一次最优阻塞。为了减少这种问题，如果一段时间过后，从某个peer那里一个片断也没有得到，那么这个peer会认为自己被对方“怠慢”了，于是不再为对方提供上传。
4．完成后的上传
一旦某个peer完成下载任务了，就不再以它的下载速率决定为哪些peer提供上传服务。至此开始，该peer优先选择网络环境更好、连接速度更快的其他peer，这样能更充分地利用上传带宽。
2.3 版本控制（Git）
1．版本控制类型
版本控制系统是用于记录一个或若干文件内容变化，以便将来查阅特定版本修订情况的系统。例如我们在做开发时，版本控制系统会帮我们实现对每一次修改的备份，可以方便地回到之前的任意一个版本。实现版本控制的软件有很多种类，大致可以分为三类：本地版本控制系统、中心化版本控制系统、分布式版本控制系统。
（1）本地版本控制系统
许多人习惯用复制整个项目目录的方式来保存不同的版本，或许还会改名加上备份时间以示区别。这么做唯一的好处就是简单，但是特别容易犯错。有时候会混淆所在的工作目录，一不小心会写错文件或者覆盖其他文件。为了解决这个问题，人们很久以前就开发了许多种本地版本控制系统，大多都是采用某种简单的数据库来记录文件的历次更新差异。
其中最流行的一种称为RCS，现今许多计算机系统上都还能看到它的踪影。甚至在流行的Mac OS X系统上安装了开发者工具包之后，也可以使用RCS命令。它的工作原理是在硬盘上保存补丁集（补丁是指文件修订前后的变化）；通过应用所有的补丁，可以重新计算出各个版本的文件内容。
（2）中心化版本控制系统
接下来人们又遇到一个问题：如何让不同系统上的开发者协同工作？于是，中心化版本控制系统（Centralized Version Control Systems, CVCS）应运而生，如图2-3所示。这类系统，诸如CVS、Subversion及Perforce等，都有一个单一的集中管理的服务器，保存所有文件的修订版本，而协同工作的人们都通过客户端连到这台服务器，取出最新的文件或者提交更新。多年以来，这已成为版本控制系统的标准做法。
图2-3 中心化版本控制系统
这种做法带来了许多好处，特别是相较于老式的本地VCS有优势。每个人都可以在一定程度上看到项目中的其他人正在做些什么，而管理员也可以轻松掌控每个开发者的权限。并且管理一个CVCS要远比在各个客户端上维护本地数据库来得轻松容易。这种方案最显而易见的缺点是中央服务器的单点故障。如果中央服务器宕机1小时，那么在这1小时内，谁都无法提交更新，也就无法协同工作。如果中心数据库所在的磁盘发生损坏，又没有及时做备份，毫无疑问你将丢失所有数据，包括项目的整个变更历史，只剩下人们在各自机器上保留的单独快照。本地版本控制系统也存在类似问题，只要整个项目的历史记录被保存在单一位置，就有丢失所有历史更新记录的风险。
（3）分布式版本控制系统
为了避免中心化版本控制系统单点故障的风险，分布式版本控制系统（Distributed Version Control System, DVCS）面世了。这类系统有Git、Mercurial、Bazaar及Darcs等，客户端并不只提取最新版本的文件快照，而是把代码仓库完整地镜像下来。它的系统架构如图2-4所示。这么一来，任何一处协同工作用的服务器发生故障，事后都可以用任何一个镜像出来的本地仓库恢复。因为每一次的克隆操作，实际上都是一次对代码仓库的完整备份。
图2-4 分布式版本控制
更进一步，许多这类系统都可以指定与若干不同的远端代码仓库进行交互。借此，你就可以在同一个项目中，分别和不同工作小组的人相互协作。你可以根据需要设定不同的协作流程，比如层次模型式的工作流，而这在以前的集中式系统中是无法实现的。
2．快照流
Git和其他版本控制系统的主要差别在于Git保存数据的方法。从概念上来区分，其他大部分系统以文件变更列表的方式存储信息，这类系统（CVS、Subversion、Perforce、Bazaar等）将它们保存的信息看作一组随时间逐步累积的文件差异关系，如图2-5所示。
图2-5 每个文件与初始版本的差异
Git不按照以上方式保存数据。反之，Git更像把数据看作对小型文件系统的一组快照，如用2-6所示。每次你提交更新或在Git中保存项目状态时，它将为全部文件生成一个快照并保存这个快照的索引。为了效率，如果文件没有修改，Git不再重新存储该文件，而是只保留一个链接指向之前存储的文件。Git保存数据的方式更像是一个快照流。
Git存储的是数据随时间改变的快照。
这是Git与其他版本控制系统的重要区别。因此Git综合考虑了以前每一代版本控制系统延续下来的问题。Git更像一个小型的文件系统，提供了许多以此为基础构建的优秀工具，而不只是一个简单的版本控制系统。稍后我们在讨论Git分支管理时，将探究这种方式带来的好处。
图2-6 文件快照存储
3．本地执行操作
在Git中的绝大多数操作都只需要访问本地文件和资源，一般不需要来自网络上其他计算机的信息。相比于中心化版本控制系统严重的网络延时，在本地加载Git要快许多。因为你在本地磁盘上就有项目的完整历史，所以大部分操作看起来瞬间就完成了。
举个例子，要浏览项目的历史，Git不需外连到服务器去获取历史，然后再显示出来，它只需直接从本地数据库中读取，你就能立即看到项目历史。如果你想查看当前版本与一个月前的版本之间引入的修改，Git会查找到一个月前的文件做一次本地的差异计算，而不是由远程服务器处理或从远程服务器拉回旧版本文件再在本地处理。
这也意味着当你处于离线状态时，也可以进行几乎所有的操作。比如：在飞机或火车上想做些工作，你能愉快地提交，直到有网络连接时再上传；回家后VPN客户端不正常，你仍能工作。而使用其他系统，做到如此是不可能的或很费力的。比如，用Perforce，你没有连接服务器时几乎不能做任何事；用Subversion和CVS，你能修改文件，但不能向数据库提交修改（因为你的本地数据库离线了）。这看起来不是大问题，但是你可能会惊喜地发现它带来的巨大的不同。
4．只添加数据
我们所执行的Git操作，本质都是在Git数据库中增加操作数据。Git上的操作几乎都是可逆的。同其他VCS一样，未提交更新将有可能丢失或弄乱修改的内容；一旦你将修改快照提交到Git系统中，就难再丢失数据。这使得Git在版本控制领域成为一个非常优秀的工具，因为我们可以尽情做各种修改尝试，而仍有回流的机会。
5．完整性校验
Git中所有数据在存储前都会计算校验和，然后以校验和来引用。这意味着不可能在Git不知情时更改任何文件内容或目录内容。这个功能由Git在底层实现。若你在编辑过程中丢失信息或损坏文件，Git就能发现。
Git用以计算校验的哈希算法是SHA-1。Git会将文件的内容或目录结构一同计算，得出它们的哈希值，确保文件和路径的完整性。Git中使用这种哈希值的情况很多，你将经常看到这种哈希值。实际上，Git数据库中保存的信息都是以文件内容的哈希值来索引的，而不是文件名。
6．工作区与工作状态
Git有3种状态，你的文件可能处于其中之一：已提交（committed）、已修改（modified）和已暂存（staged）。已提交表示数据已经安全地保存在本地数据库中；已修改表示修改了文件，但还没保存到数据库中；已暂存表示对一个已修改文件的当前版本做了标记，使之包含在下次提交的快照中。
由此引入Git项目的3个工作区域的概念：工作目录、Git仓库及暂存区域。Git仓库包括本地仓库和远程仓库。
1）工作目录：直接编辑修改的目录。工作目录是将项目中某个版本独立提取出来的内容放在磁盘上供你使用或修改。
2）Git仓库：保存项目的元数据和对象数据库。这是Git中最重要的部分，从其他计算机复制仓库时，复制的就是这里的数据。
3）暂存区域：是一个文件，保存了下次将提交的文件列表信息，一般在Git仓库中。有时候也被称作“索引”，不过一般还是叫暂存区域。
定义了这3个工作区域，工作流程就很清晰了。基本的Git工作流程如下：
1）在工作目录中修改文件。
2）暂存文件，将文件的快照放入暂存区域。
3）提交更新，找到暂存区域的文件，将快照永久性存储到Git仓库。
如果Git仓库中保存着的特定版本文件，就属于已提交状态。如果做了修改并已放入暂存区域，就属于已暂存状态。如果自上次取出后，做了修改但还没有放到暂存区域，就是已修改状态。
7．分支
为了理解Git分支的实现方式，我们需要回顾一下Git是如何储存数据的。Git保存的不是文件差异或者变化量，而是一系列文件快照。在Git中提交时，会保存一个提交（commit）对象，该对象包含一个指向暂存内容快照的指针，包含本次提交的作者等相关附属信息，包含零个或多个指向该提交对象的父对象指针：首次提交是没有直接祖先的，普通提交有一个祖先，由两个或多个分支合并产生的提交则有多个祖先。
为直观起见，我们假设在工作目录中有3个文件，准备将它们暂存后提交。暂存操作会对每一个文件计算校验和，然后把当前版本的文件快照保存到Git仓库中（Git使用blob类型的对象存储这些快照），并将校验和加入暂存区域。
$ git add README test.rb LICENSE
$ git commit -m 'initial commit of my project'
当使用git commit新建一个提交对象前，Git会先计算每一个子目录（本例中就是项目根目录）的校验和，然后在Git仓库中将这些目录保存为树（tree）对象。之后Git创建的提交对象，除了包含相关提交信息以外，还包含着指向这个树对象（项目根目录）的指针，如此它就可以在将来需要的时候，重现此次快照的内容了。
现在，Git仓库中有5个对象：3个表示文件快照内容的blob对象；1个记录着目录树内容及其中各个文件对应blob对象索引的tree对象；以及1个包含指向tree对象（根目录）的索引和其他提交信息元数据的commit对象。概念上来说，仓库中的各个对象保存的数据和相互关系看起来如图2-7所示。
图2-7 单一提交对象的数据结构
做些修改后再次提交，那么这次的提交对象会包含一个指向上次提交对象的指针。两次提交后，仓库历史会变成图2-8所示的样子。
图2-8 多个提交对象之间的链接关系
现在来谈分支。Git中的分支本质上仅是个指向commit对象的可变指针。Git使用master作为分支的默认名字。第一个分支也常被称为主干。主干可被克隆为其他分支，每条分支的可变指针在每次提交时都会自动向前移动，如图2-9所示。
图2-9 分支中的历史提交
2.4 自验证文件系统（SFS）
自验证文件系统（Self-Certifying File System, SFS）是由David Mazieres和他的导师M. Frans Kaashoek在其博士论文中提出的。SFS是为了设计一套整个互联网共用的文件系统，全球的SFS系统都在同一个命名空间下。在SFS中，分享文件会变得十分简单，只需要提供文件名就行了。任何人都能像Web一样，搭建起SFS服务器，同时任意一个客户端都能连接网络中任意一个服务器。
直觉上，我们可以感受到，要实现一个全球共享的文件系统，最大的障碍莫过于如何让服务端为客户端提供认证。一个我们能想到的思路就是每个服务器都使用非对称加密，生成一对私钥和公钥。客户端使用服务器的公钥来验证服务器的安全连接。那么这样又有一个新问题，如何让客户端在最初获得服务器的公钥呢？在不同的需求场景下，用户对密钥管理的要求是不同的，又如何实现密钥管理的可扩展性呢？
SFS则使用了一种解决方案，一种新的方式，它将公钥信息嵌入文件名中，这个做法命名为“自验证文件名”。那么显然，这样做以后我们就无须在文件系统内部实现密钥管理了。这部分密钥管理的功能可以加入用户对文件命名的规则中。这样一来给用户的加密方式带来很多便利，用户可以根据需求，自行选择需要的加密方式。
SFS核心思想有如下几点：
❑ SFS文件系统具备自验证路径名称，不需要在文件系统内部实现密钥管理。
❑ 在SFS上易于架设各种密钥管理机制，包括各类组合机制。
❑ SFS将密钥管理与密钥分发解耦。
❑ 实现全球范围的文件系统。
2.4.1 SFS设计
1．安全性
SFS系统的安全性可以由两部分定义：文件系统本身的安全性和密钥管理的安全性。换句话说，安全性意味着攻击者未经许可不能读取或者修改文件系统；而对于用户的请求，文件系统一定会给用户返回正确的文件。
❑ 文件系统本身的安全性：SFS除非明确指明允许匿名访问，否则用户如果需要读取、修改、删除或者对文件进行任何篡改，都需要提供正确的密钥。客户端与服务器始终在加密的安全通道中进行通信，通道需要确保双方的身份，以及数据完整性和实时性（避免攻击者截获数据包，并将其重新发送，欺骗系统，这称为重放攻击）。
❑ 密钥管理的安全性：仅仅依靠文件系统的安全保护并不能满足用户的各类需求，用户可以使用密钥管理来达到更高级别的安全性。用户可以使用预先设置的私钥，或使用多重加密，再或者使用由第三方公司提供的文件系统来访问经过认证的文件服务器。用户可以从中灵活、轻松地构建各种密钥管理机制。
2．可扩展性
因为SFS定位是全球范围共享的文件系统，所以SFS应该具有良好的可扩展性能。无论用户是希望以密码认证方式读取个人文件，还是浏览公共服务器上的内容，SFS都应该能很好地兼容。
在SFS系统的设计中，任何在Internet网络内拥有域名或IP地址的服务器，都能部署为SFS服务器，并且过程十分简单，甚至无须请求注册权限。SFS通过3个属性实现它的扩展：全网共享的命名空间，用于实现密钥管理的原语集，以及模块化设计。
❑ 全局命名空间：在任意一个客户端登录的SFS都具有相同的命名空间。虽然SFS中在每个客户端都会共享相同的文件，但是没有任何人能控制全局的命名空间；每个人都能添加新的服务器到这个命名空间里。
❑ 密钥管理的原语集：SFS还允许用户在文件名解析期间使用任意算法来查找和验证公钥。不同的用户可以采用不同的技术认证相同的服务器；SFS允许他们安全地共享文件缓存。
❑ 模块化设计：客户端和服务器在设计时就大量使用了模块化设计，程序之间大多使用设计好的接口进行通信。这样，更新迭代系统各个部分，或者添加新的功能特性会非常简单。
2.4.2 自验证文件路径
自验证文件系统的一个重要的特性，就是在不依赖任何外部信息的条件下，利用加解密来控制权限。这是因为，如果SFS使用本地配置文件，那么显然这与全局文件系统的设计相悖；如果使用一个中心化服务器来辅助连接，用户可能产生不信任。那么，如何在不依赖外部信息的情况下，来安全地获取文件数据呢？SFS提出了一种新的方式，即通过可以自我证明身份的路径名实现。
SFS路径中包含了构成与指定服务器构建连接的需要的全部信息，例如网络地址和公钥。SFS文件路径包含3部分：
（1）服务器位置
告知SFS客户端文件系统服务器的地址，它可以是IP地址或者DNS主机名。
（2）HostID
告知SFS如何与服务器构建安全的连接通道。为了确保连接的安全性，每个SFS客户端都有一个公钥，而Host ID通常设置为主机名与公钥的哈希。通常情况下，SFS会按照SHA-1函数计算。
HostID = SHA-1 (“HostInfo”, Location, PublicKey, “HostInfo”,
Location, PublicKey)
使用SHA-1主要考虑了计算的简易性，以及一个能接受的安全等级。SHA-1的输出是固定的20字节，它比公钥短得多。同时SHA-1能为SFS提供足够的密码学保护，找到一对合法的服务器位置与公钥对来满足要求，它的构造难度非常大。
（3）在远程服务器上文件的地址
前面两个信息是为了找到目标服务器并构建安全连接，最后只需要提供文件的位置、定位需求的文件即可。整个自验证文件路径的形式如下：
即给定一个IP地址或域名作为位置，给定一个公钥/私钥对，确定相应的Host ID，运行SFS服务器软件，任何一个服务器都能通过客户端将自己加入SFS中，而无须进行任何的注册过程。
2.4.3 用户验证
自验证的路径名能帮助用户验证服务器的身份，而用户验证模块则是帮助服务器验证哪些用户是合法的。与服务器身份验证一样，找到一种能用于所有用户身份验证的方法同样是很难达到的。因此SFS把用户身份验证与文件系统分开。外部软件可以根据服务器的需求来设计协议验证用户。
SFS引入了Agent客户端模块来负责用户认证工作。当用户第一次访问SFS文件系统时，客户端会加载访问并通知Agent这一事件。然后，Agent会向远程服务器认证这个用户。从服务器角度来看，这部分功能从服务器搬到了一个外部认证的通道。Agent和认证服务器之间通过SFS传递信息。如果验证者拒绝了验证请求，Agent可以改变认证协议再次请求。如此一来，可以实现添加新的用户验证信息却不需要修改实际的真实文件系统。如果用户在文件服务器上没有注册过，Agent在尝试一定次数以后拒绝用户的身份验证，并且将授权用户以匿名方式文件系统。另外，一个Agent也能方便地通过多种协议连接任意给定的服务器，这些设计都会非常方便、快捷和灵活。
2.4.4 密钥撤销机制
有些时候服务器的私钥可能会被泄露，那么原有的自验证文件路径可能会错误地定位到恶意攻击者设置的服务器。为了避免这种情况发生，SFS提供了两种机制来控制：密钥撤销指令和Host ID阻塞。密钥撤销指令只能由文件服务器的拥有者发送，它的发送目标是全部的用户。这一指令本身是自验证的。而Host ID阻塞是由其他节点发送的，可能与文件服务器拥有者冲突，每一个验证的Agent可以选择服从或者不服从Host ID阻塞的指令。如果选择服从，对应的Host ID就不能被访问了。
密钥撤销指令的形式如下：
Revokemessage={"PathRevoke" , Location, Public_Key, NULL}||Secret_Key
在这里PathRevoke字段是一个常量；Location是需要撤销密钥的自验证路径名称；NULL是为了保持转发指针指令的统一性，在这里将转发指针指向一个空路径，意味着原有指针失效了；这里Public_Key是失效前的公钥；Secret_Key是私钥。这一条信息能够确保撤销指令是由服务器所有者签发的。
当SFS客户端软件看到吊销证书时，任何要求访问撤销地址的请求都会被禁止。服务端会通过两种方式获取密钥撤销指令：SFS连接到服务器的时候，如果访问到已经撤销的地址或路径，它会收到由服务器返回的密钥撤销指令；用户初次进行自认证路径名时，客户端会要求Agent检查其是否已经被撤销，Agent会返回相应的结果。撤销指令是自验证的，因此分发撤销指令并不是那么重要，我们可以很方便地请求其他源头发送的撤销指令。
2.5 Merkle DAG和Merkle Tree
对于IPFS, Merkle DAG和Merkle Tree是两个很重要的概念。Merkle DAG是IPFS的存储对象的数据结构，Merkle Tree则用于区块链交易的验证。Merkle Tree通常也被称为哈希树（Hash Tree），顾名思义，就是存储哈希值的一棵树；而Merkle DAG是默克尔有向无环图的简称。二者有相似之处，也有一些区别。
从对象格式上，Merkle Tree的叶子是数据块（例如，文件、交易）的哈希值。非叶节点是其对应子节点串联字符串的哈希。Merkle DAG的节点包括两个部分，Data和Link; Data为二进制数据，Link包含Name、Hash和Size这3个部分。从数据结构上看，Merkle DAG是Merkle Tree更普适的情况，换句话说，Merkle Tree是特殊的Merkle DAG。从功能上看，后者通常用于验证数据完整性，而前者大多用于文件系统。
下面我们对这两种数据结构和用法详细解释。
2.5.1 Merkle Tree
1．Hash
Hash是一个把任意长度的数据映射成固定长度数据的函数。例如，对于数据完整性校验，最简单的方法是对整个数据做Hash运算，得到固定长度的Hash值，然后把得到的Hash值公布在网上，这样用户下载到数据之后，对数据再次进行Hash运算，将运算结果与网上公布的Hash值进行比较，如果两个Hash值相等，说明下载的数据没有损坏。可以这样做是因为输入数据的任何改变都会引起Hash运算结果的变化，而且根据Hash值反推原始输入数据是非常困难的。如果从稳定的服务器进行数据下载，采用单一Hash进行验证是可取的。但现实中数据的下载会发生各种意外，如链接中断。一旦数据损坏，就需要重新下载，这种下载方式的效率低下。
2．Hash List
在点对点网络中做数据传输的时候，会同时从多个机器上下载数据，而且可以认为很多机器是不稳定或者不可信的。为了校验数据的完整性，更好的办法是把大的文件分割成小的数据块（例如，分割成2KB为单位的数据块）。这样的好处是，如果小块数据在传输过程中损坏了，那么只要重新下载这一块数据即可，不需要重新下载整个文件。那么，如何确定数据块的完整性呢？只需要为每个数据块计算Hash值。BT下载的时候，在下载到真正数据之前，我们会先下载一个Hash列表。那么问题又来了，怎么确定这个Hash列表本身是正确的呢？答案是把每个小块数据的Hash值拼到一起，然后对这个长字符串再做一次Hash运算，这样就得到Hash列表的根Hash（Top Hash或Root Hash）。下载数据的时候，首先从可信的数据源得到正确的根Hash，就可以用它来校验Hash列表了，然后即可通过校验后的Hash列表校验数据块的完整性。
3．Merkle Tree
Merkle Tree可以看作Hash List的泛化（Hash List可以看作一种特殊的Merkle Tree，即树高为2的多叉Merkle Tree）。
在最底层，和Hash列表一样，把数据分成小的数据块，有相应的Hash与它对应。但是往上走，并不是直接去运算根Hash，而是把相邻的两个Hash合并成一个字符串，然后运算这个字符串的Hash。这样每两个Hash就“结婚生子”，得到了一个“子Hash”。如果最底层的Hash总数是单数，那到最后必然出现一个“单身Hash”，这种情况就直接对它进行Hash运算，所以也能得到它的“子Hash”。于是往上推，依然是一样的方式，可以得到数目更少的新一级Hash，最终形成一棵倒挂的树，树根位置就是树的根Hash，我们把它称为Merkle Root。
在P2P网络下载之前，先从可信的源获得文件的Merkle Tree树根。一旦获得了树根，就可以从其他从不可信的源获取Merkle Tree。通过可信的树根来检查接收到的Merkle Tree。如果Merkle Tree是损坏的或者是虚假的，就从其他源获得另一个Merkle Tree，直到获得一个与可信树根匹配的Merkle Tree。
4．Merkle Tree的特点
Merkle Tree是一种树，大多数是二叉树，也可以是多叉树。无论是几叉树，它都具有树结构的所有特点。
1）Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据Hash。
2）非叶子节点的value是根据它下面所有的叶子节点值，按照哈希算法计算而得出的。
通常，使用哈希算法（例如：SHA-2和MD5）来生成数据的Hash值。但如果目的仅仅是防止数据不被蓄意的损坏或篡改，可以使用安全性低但效率高的校验算法，如CRC。
Merkle Tree和Hash List的主要区别是，可以直接下载并立即验证Merkle Tree的一个分支。因为可以将文件切分成小的数据块，这样如果有一块数据损坏，仅仅重新下载这个数据块就行了。如果文件非常大，那么Merkle Tree和Hash List都很大，但是Merkle Tree可以一次下载一个分支，然后立即验证这个分支，如果分支验证通过，就可以下载数据了；而Hash List只有下载整个Hash List才能验证。
5．Merkle Tree的应用
❑ 数字签名：最初Merkle Tree的目的是高效处理Lamport单次签名。每一个Lamport密钥只能被用来签名一个消息，但是与Merkle Tree结合起来可以签名多个消息。这种方法成为一种高效的数字签名框架，即Merkle签名方法。
❑ P2P网络：在P2P网络中，Merkle Tree用来确保从其他节点接收的数据块没有损坏且没有被替换，甚至检查其他节点不会欺骗或者发布虚假的块。在2.2节中，我们提到了BitTorrent使用P2P技术来让客户端之间进行数据传输，一来可以加快数据下载速度，二来减轻下载服务器的负担。一个相关的问题是大数据块的使用，因为为了保持torrent文件非常小，那么数据块Hash的数量也得很小，这就意味着每个数据块相对较大。大数据块影响节点之间进行交易的效率，因为只有当大数据块全部下载下来并通过校验后，才能与其他节点进行交易。为解决上面两个问题：用一个简单的Merkle Tree代替Hash List。设计一个层数足够多的满二叉树，叶节点是数据块的Hash，不足的叶节点用0来代替。上层的节点是其对应孩子节点串联的Hash。Hash算法和普通torrent一样采用SHA-1。
❑ 比特币：Merkle Proof最早的应用是Bitcoin（比特币），它是由中本聪在2009年描述并创建的。Bitcoin的Blockchain利用Merkle proofs来存储每个区块的交易。而这样做的好处也就是中本聪描述到的“简化支付验证”（Simplified Payment Verification, SPV）的概念：一个“轻客户端”（light client）可以仅下载链的区块头，即每个区块中的80字节的数据块，仅包含5个元素，而不是下载每一笔交易以及每一个区块。5个元素为上一区块头的Hash值、时间戳、挖矿难度值、工作量证明随机数（nonce）以及包含该区块交易的Merkle Tree的根Hash。
如果客户端想要确认一个交易的状态，它只需简单地发起一个Merkle Proof请求，这个请求显示出这个特定的交易在Merkle Tree的一个叶子节点之中，而且这个Merkle Tree的树根在主链的一个区块头中。但是Bitcoin的轻客户端有它的局限。一个局限是，尽管它可以证明包含的交易，但是它不能进行涉及当前状态的证明（如数字资产的持有、名称注册、金融合约的状态等）。Bitcoin如何查询你当前有多少币？一个比特币轻客户端可以使用一种协议，它涉及查询多个节点，并相信其中至少会有一个节点会通知你关于你的地址中任何特定的交易支出，而这可以让你实现更多的应用。但对于其他更为复杂的应用而言，这些是远远不够的。影响一笔交易的确切性质（precise nature），取决于此前的几笔交易，而这些交易本身则依赖于更为前面的交易，所以最终你可以验证整个链上的每一笔交易。
2.5.2 Merkle DAG
Merkle DAG的全称是Merkle Directed Acyclic Graph（默克有向无环图）。它是在Merkle Tree的基础上构建的，Merkle Tree由美国计算机学家Merkle于1979年申请了专利。Merkle DAG跟Merkle tree很相似，但不完全一样，比如Merkle DAG不需要进行树的平衡操作、非叶子节点允许包含数据等。Merkle DAG是IPFS的核心概念。Merkle DAG也是Git、Bitcoin和dat等技术的核心。散列树由内容块组成，每个内容块由其加密散列标识。你可以使用其散列引用这些块中的任何一个，这允许你构建使用这些子块的散列引用其“子块”的块树。ipfs add命令将从你指定的文件的数据中创建Merkle DAG。执行此操作时，它遵循unixfs数据格式。这意味着你的文件被分解成块，然后使用“链接节点”以树状结构排列，以将它们连接在一起。给定文件的“散列”实际上是DAG中根节点（最上层）的散列。
1．Merkle DAG的功能
Merkle DAG在功能上与Merkle Tree有很大不同，上面我们提到Merkle Tree主要是为了验证，例如验证数字签名，以及比特币Merkle Proof。而对于Merkle DAG，它的目的有如下3个。
❑ 内容寻址：使用多重Hash来唯一识别一个数据块的内容。
❑ 防篡改：可以方便地检查Hash值来确认数据是否被篡改。
❑ 去重：由于内容相同的数据块Hash值是相同的，很容易去掉重复的数据，节省存储空间。
其中第3条是IPFS系统最为重要的一个特性，在IPFS系统中，每个Blob的大小限制在256KB（暂定为256KB，这个值可以根据实际的性能需求进行修改）以内，那些相同的数据就能通过Merkle DAG过滤掉，只需增加一个文件引用，而不需要占据存储空间。
2．数据对象格式
在IPFS中定义了Merkle DAG的对象格式。IPFS Object是存储结构，我们前面提到IPFS会限制每个数据大小在256KB以内。在IPFS Object对象里，我们保存有两个部分，一个是Link，用于保存其他的分块数据的引用；另一个是data，为本对象内容。Link主要包括3个部分，分别是Link的名字、Hash和Size，如以下代码所示。在这里Link只是对一个IPFS Object的引用，它不再重复存储一个IPFS对象了。
type IPFSObject struct {
links []IPFSLink // link数组
data []byte // 数据内容
}
type IPFSLink struct {
Name string // link的名字
Hash Multihash // 数据的加密哈希值
Size int // 数据大小
}
使用Git和Merkle DAG的集合会极大减少存储空间消耗。这是因为，对源文件的修改如果使用Merkle DAG来存储，那么修改的内容可能只是很少的一部分。我们不再需要将整个修改后的文件再做一次备份了。这也就是IPFS节省存储空间的原因。
2.6 本章小结
在这一章里，我们详细讨论了IPFS的几个基础性系统和数据结构，包括DHT、BitTorrent、Git和SFS，以及Merkle结构。DHT是本章的重点和难点，我们学习了3种著名的DHT设计，分别是Kademlia、Coral DSHT和S/K Kademlia。读者重点关注三者各自的侧重点和实现的区别。DHT是分布式存储的基本方式，Kademlia使得其完全去中心化，Coral提升了DHT的效率，而S/K Kademlia则大大提升了系统的安全性。BitTorrent协议应当重点关注其块交换协议的优化和经济学策略，对于不合作的节点，通过信用机制给出相应的惩罚，例如流量限制或者网络阻塞；在Filecoin的设计中，系统会没收它们的担保品。在Git版本控制系统中，只储存每个版本与原始版本的差异，而不做全部的拷贝。IPFS也是基于此原理，与现有文件系统相比，存储方式更节省空间。自验证文件系统的核心思想是在文件路径中隐含验证身份的密钥，IPFS系统也利用了这一方式，确保所有文件在同一命名空间下，同时不牺牲安全性。最后我们学习了Merkle数据结构，读者应重点关注Merkle Tree和Merkle DAG的区别和用途。