【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

时间：2024-03-13 13:40:19

【转载请标明出处】：https://blog.csdn.net/qq_25870633/article/details/81939101 

本文章参考自：

http://www.yeolar.com/note/2010/03/21/kademlia/#id13    Kademlia协议原理简介

https://keeganlee.me/post/blockchain/20180313               详解区块链P2P网络

  

大家好，今天我们来说一说以太坊的Kad网络；在此之前我们先来聊一聊少部分P2P方面的知识，P2P 主要存在四种不同的网络模型，也代表着 P2P 技术的四个发展阶段：集中式、纯分布式、混合式和结构化模型。

  • 集中式：即存在一个中心节点保存了其他所有节点的索引信息，索引信息一般包括节点 IP 地址、端口、节点资源等。

             优点：就是结构简单、实现容易。

             缺点：由于中心节点需要存储所有节点的路由信息，当节点规模扩展时，就很容易出现性能瓶颈；而且也存在单点故障问题。

  • 纯分布式：移除了中心节点，在 P2P 节点之间建立随机网络，就是在一个新加入节点和 P2P 网络中的某个节点间随机建立连接通道，从而形成一个随机拓扑结构。          

                     新节点加入该网络的实现方法也有很多种，最简单的就是随机选择一个已经存在的节点并建立邻居关系。像比特币的话，则是使用 DNS 的方式来查询其他节点，DNS 一般是硬编码到代码里的，这些 DNS 服务器就会提供比特币节点的 IP 地址列表，从而新节点就可以找到其他节点建立连接通道。新节点与邻居节点建立连接后，还需要进行全网广播，让整个网络知道该节点的存在。

                   全网广播的方式：该节点首先向邻居节点广播，邻居节点收到广播消息后，再继续向自己的邻居节点广播，以此类推，从而广播到整个网络。这种广播方法也称为泛洪机制。纯分布式结构不存在集中式结构的单点性能瓶颈问题和单点故障问题，具有较好的可扩展性，但泛洪机制引入了新的问题，主要是可控性差的问题：

                  【 一是】：容易形成泛洪循环，比如节点 A 发出的消息经过节点 B 到 节点 C，节点 C 再广播到节点 A，这就形成 了一个循环；

                  【二是】：响应消息风暴问题，如果节点 A 想请求的资源被很多节点所拥有，那么在很短时间内，会出现大量节点同时向节点 A 发送响应消息，这就可能会让节点 A 瞬间瘫痪。

  • 混合式：混合了集中式和分布式结构，如下图所示，网络中存在多个超级节点组成分布式网络，而每个超级节点则有多个普通节点与它组成局部的集中式网络。一个新的普通节点加入，则先选择一个超级节点进行通信，该超级节点再推送其他超级节点列表给新加入节点，加入节点再根据列表中的超级节点状态决定选择哪个具体的超级节点作为父节点。这种结构的泛洪广播就只是发生在超级节点之间，就可以避免大规模泛洪存在的问题。在实际应用中，混合式结构是相对灵活并且比较有效的组网架构，实现难度也相对较小，因此目前较多系统基于混合式结构进行开发实现。其实，比特币网络如今也是这种结构。

【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

 

  • 结构化 P2P 网络：它也是一种分布式网络结构，但与纯分布式结构不同。纯分布式网络就是一个随机网络，而结构化网络则将所有节点按照某种结构进行有序组织，比如形成一个环状网络或树状网络。而结构化网络的具体实现上，普遍都是基于 DHT(Distributed Hash Table，分布式哈希表) 算法思想。DHT 只是提出一种网络模型，并不涉及具体实现，主要想解决如何在分布式环境下快速而又准确地路由、定位数据的问题。具体的实现方案有 Chord、Pastry、CAN、Kademlia 等算法，其中 Kademlia 也是以太坊网络的实现算法，很多常用的 P2P 应用如 BitTorrent、电驴等也是使用 Kademlia。

 P2P 网络中，可以抽象出两种空间：资源空间和节点空间。资源空间就是所有节点保存的资源集合，节点空间就是所有节点的集合。对所有资源和节点分别进行编号，如把资源名称或内容用 Hash 函数变成一个数值（这也是 DHT 常用的一种方法），这样，每个资源就有对应的一个 ID，每个节点也有一个 ID，资源 ID 和节点 ID 之间建立起一种映射关系，比如，将资源 n数值 的所有索引信息存放到 n数值节点上，那要搜索资源 n 时，只要找到节点 n 即可，从而就可以避免泛洪广播，能更快速而又准确地路由和定位数据。【当然，在实际应用中，资源 ID 和节点 ID 之间是无法做到一一对应的（因为无法确保数值为100的资源ID可以在全网中找到数值也为100的节点ID），通常的解决方案是，但因为 ID 都是数字，就存在大小关系或偏序关系等来决定数值为 100 的资源ID应该存放到那些离数值 100 最近的k个节点上，基于这些关系就能建立两者的映射关系】。这就是 DHT 的核心思想。DHT 算法在资源编号和节点编号上就是使用了分布式哈希表，使得资源空间和节点空间的编号有唯一性、均匀分布式等较好的性质，能够适合结构化分布式网络的要求。

好了，废话逼逼了太多了（咳咳，应该是抄了人家的太多了），现在我们来说一说传统kad网络和以太坊的kad网络，【因为他咩的，以太坊是用来做节点发现的，而类似于Bittorrent之类的除了可能要做节点发现外还需要做资源发现的】

来，我们来看一看 Kad是个什么样的东东：

  1. 在kad网络中每一个节点都必须有自己的节点ID 【160 bit 的 ID 值作为标志符，Key 也是一个 160 bit 的标志符，每一个加入 Kad 网络的计算机都会在 160 bit 的 key 空间被分配一个节点 ID（node ID）值（可以认为 ID 是随机产生的）， <key,value> 对的数据就存放在 ID 值“最”接近 key 值的节点上】
  2. 在kad网络中，所有资源(条目)都是以<key, value>的形式存储在节点上的，其中key和节点的ID一样也是 160 bit，这显然是有目的的，因为希望“尽量”的把数值为 n 的key 对应的 <key, value> 资源存放到 同样数值为 n 的节点ID上，我们可以将满足(ID==key)这一条件的节点命名为目标节点N。这样纸 ，一个查找条目的问题便被简单地转化 成为了一个查找ID等于Key值的节点的问题（当然这是理想化的情况下，现实中，不一定存在 和key的数字一样的节点ID，所以我们说是 “尽量”把<key, value> 存储在和数值 n 相近的K个节点上，这里的k是个经验取值）。

  3. 在kad网络中我们是通过 两个节点ID的异或运算得出来的值来算节点间的距离的，而不是依靠物理距离、路由器跳数来衡量的（因为这样需要做很多的计算才可以知道对方的远近，效率相当的慢），而通过异或这类的计算可以快速的精准的定位到对方节点

节点的距离：

异或操作也是单向性的。对于任意给定的节点 x 和距离 Δ≥0 ，总会存在一个精确的节点 y ，使得 d(x,y)=Δ。

单向性也确保了对于同一个 key 值的所有查询都会逐步收敛到同一个路径上，而不管查询的起始节点位置如何。这样，只要沿着查询路径上的节点都缓存这个 <key,value> 对，就可以减轻存放热门 key 值节点的压力，同时也能够加快查询响应速度。【这句话的理解是：把<key, value> 均匀的放置到 和 key 的数值相近的 某一部分节点上，这样纸的话我们在查找key时，总能命中这些节点上，这样纸减轻了把 <key, value> 放置到 某单个节点上所造成的访问压力，及能够加快查询到 value 的速度】；所以，在Kad网络中ID越靠近key的节点区域，该条目保存的份数就越多，存储得也越集中；事实上，为了实现较短的查询响应 延迟，在条目查询的过程中，任一条目可被cache到任意节点之上；同时为了防止过度cache、保证信息足够新鲜，必须考虑条目在节点上存储的时效性： 越接近目标结点N，该条目保存的时间将越长，反之，其超时时间就越短；保存在目标节点之上的条目最多能够被保留24小时，如果在此期间该条目被其发布源重 新发布(每个节点都会把自身的资源每个固定时间重新发布给临近节点)的话，其保存时间还可以进一步延长。

节点的状态：

在 Kad 网络中，所有节点都被当作一颗二叉树的叶子【这个信息是以各个节点本地的k-bucket所记录的，可能每个节点的k-bucket所记录的内容不尽一样，但是大家所维护的k-bucket 组成的整网的节点状态既是这样】，并且每一个节点的位置都由其 ID 值的最短前缀唯一的确定。【这句话我们先记下，不明白也没关系，后面的内容会让我们明白】，对于任意一个节点，都可以把这颗二叉树分解为一系列连续的，不包含自己的子树。最高层的子树，由整颗树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的一半组成；依此类推，直到分割完整颗树。比如节点0011如何进行子树的划分，如图：

【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

其中，虚线包含的部分就是各子树，由上到下各层的前缀分别为 1，01，000，0010 。Kad 协议确保每个节点知道其各子树的至少一个节点。在这个前提下，每个节点都可以通过ID值来找到任何一个节点。这个路由的过程是通过所谓的 XOR（异或）距离得到的。

下面演示了节点0011如何通过连续查询来找到节点1110的。节点0011通过在逐步底层的子树间不断学习并查询最佳节点，获得了越来越接近的节点，最终收敛到目标节点上：

【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

由于网上很多说法都是互抄的，其实上光看这个图还是不能明白，如何的收敛到目标节点：是这样纸的，首先，需要知道请求发起节点 0011 和 目标节点 1110 的 距离 n ，然后从 请求节点 0011 的本地 k-bucket 的 n 桶中返回 k个 节点信息，然后 0011 再给这几个节点广播，如果 这几个节点中刚好有距离是 n 的节点，那么就会用 0011 ，否则，就从这些节点的bendi k-bucket 中继续上述操作，直到找到 1110 节点，所以这个过程是个递归的过程。

K桶：

Kad 的路由表是通过一些称之为 K 桶的表格构造起来的，传统的kad的k-bucket 的数目取值为  0≤i≤160 ；每个节点都保存有一些和自己距离范围在区间 [2i,2i+1) 内的一些节点信息，这些信息由一些 (IP address,UDP port,Node ID) 数据列表构成（Kad 网络是靠 UDP 协议交换信息的）。每一个这样的列表都称之为一个 K 桶，每一个list(k-桶)中最多存放k个对端节点信息；【注意】此处的k与上文所提到的条目被存放的最近节点数含义是一致的；每一个 list中的对端节点信息均按访问时间排序，最早访问的在list头部，而最近新访问的则放在list的尾部。

如图：

【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

表格形式如：

【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

 

不过通常来说当 i 值很小时，K 桶通常是空的（也就是说没有足够多的节点，比如当 i = 0 时，就最多可能只有1项）；而当 i 值很大时，其对应 K 桶的项数又很可能会超过 k 个（当然，覆盖距离范围越广，存在较多节点的可能性也就越大），这里 k 是为平衡系统性能和网络负载而设置的一个常数，是个经验取值，但必须是偶数，比如 k = 20。在 BitTorrent 的实现中，取值为 k = 8。

经过证明，对于一个有 N 个节点的 Kad 网络，最多只需要经过 logN 步查询，就可以准确定位到目标节点。

K-Bucket的更新机制：

当节点 x 收到一个 PRC 消息时，发送者 y 的 IP 地址就被用来更新对应的 K 桶，具体步骤如下：

  1. 计算自己和发送者的距离： d(x,y)=x⊕y ，注意：x 和 y 是 ID 值，不是 IP 地址
  2. 通过距离 d 选择对应的 K 桶进行更新操作
  3. 如果 y 的 IP 地址已经存在于这个 K 桶中，则把对应项移到该该 K 桶的尾部
  4. 如果 y 的 IP 地址没有记录在该 K 桶中
    1. 如果该 K 桶的记录项小于 k 个，则直接把 y 的 (IP address, UDP port, Node ID) 信息插入队列尾部
    2. 如果该 K 桶的记录项大于 k 个，则选择头部的记录项（假如是节点 z）进行 RPC_PING 操作
      1. 如果 z 没有响应，则从 K 桶中移除 z 的信息，并把 y 的信息插入队列尾部
      2. 如果 z 有响应，则把 z 的信息移到队列尾部，同时忽略 y 的信息

K 桶的更新机制非常高效的实现了一种把最近看到的节点更新的策略，除非在线节点一直未从 K 桶中移出过。也就是说在线时间长的节点具有较高的可能性继续保留在 K 桶列表中；这是有依据得的：在线时间长一点的节点更值得我们信任，因为它在下一个小时以内保持在线的可能性将比我们最新访问的节点更大 这对应 Kad 网络的稳定性和减少网络维护成本（不需要频繁构建节点的路由表）带来很大好处。

【好处】这种机制的另一个好处是能在一定程度上防御 DOS 攻击，因为只有当老节点失效后，Kad 才会更新 K 桶的信息，这就避免了通过新节点的加入来泛洪路由信息。

为了防止 K 桶老化，所有在一定时间之内无更新操作的 K 桶，都会分别从自己的 K 桶中随机选择一些节点执行 RPC_PING 操作。

上述这些 K 桶机制使 Kad 缓和了流量瓶颈（所有节点不会同时进行大量的更新操作），同时也能对节点的失效进行迅速响应。

Kademlia的协议操作类型：

Kademlia 协议包括四种远程 RPC 操作：PING、STORE、FIND_NODE、FIND_VALUE。

  1. PING 操作的作用是探测一个节点，用以判断其是否仍然在线。

  2. STORE 操作的作用是通知一个节点存储一个 <key,value> 对，以便以后查询需要。

  3. FIND_NODE 操作使用一个 160 bit 的 ID 作为参数。本操作的接受者返回它所知道的更接近目标 ID 的 K 个节点的 (IP address, UDP port, Node ID) 信息。

    这些节点的信息可以是从一个单独的 K 桶获得，也可以从多个 K 桶获得（如果最接近目标 ID 的 K 桶未满）。不管是哪种情况，接受者都将返回 K 个节点的信息给操作发起者。但如果接受者所有 K 桶的节点信息加起来也没有 K 个，则它会返回全部节点的信息给发起者。

  4. FIND_VALUE 操作和 FIND_NODE 操作类似，不同的是它只需要返回一个节点的 (IP address, UDP port, Node ID) 信息。如果本操作的接受者收到同一个 key 的 STORE 操作，则会直接返回存储的 value 值。

     

【注意】为了防止伪造地址，在所有 RPC 操作中，接受者都需要响应一个随机的 160 bit 的 ID 值 【及接受者自己的ID】。另外，为了确信发送者的网络地址，PING 操作还可以附带在接受者的 RPC 回复信息中。

 

路由查找机制：

Kad 技术的最大特点之一就是能够提供快速的节点查找机制，并且还可以通过参数进行查找速度的调节；

假如节点 x 要查找 ID 值为 t 的节点，Kad 按照如下递归操作步骤进行路由查找：

  1. 计算到 t 的距离： d(x,y)=x⊕y
  2. 从 x 的第 [logd] 个 K 桶中取出 α 个节点的信息（“[”“]”是取整符号），同时想这些节点进行 FIND_NODE 操作。如果这个 K 桶中的信息少于 α 个，则从附近多个桶中选择距离最接近 d 的总共 α 个节点。
  3. 对接受到查询操作的每个节点，如果发现自己就是 t，则回答自己是最接近 t 的；否则测量自己和 t 的距离，并从自己对应的 K 桶中选择 α 个节点的信息给 x。
  4. X 对新接受到的每个节点并从中中挑选出若干没有请求过的，再次执行 FIND_NODE 操作，此过程不断重复执行，直到每一个分支都有节点响应自己是最接近 t 的。【注意】在查询过程中，没有及时响应的节点将立即被排除；因为查询者必须保证最终获得的k个最近节点都是活动的。
  5. 通过上述查找操作，x 得到了 k 个最接近 t 的节点信息。

【注意】：这里用“最接近”这个说法，是因为 ID 值为 t 的节点不一定存在网络中，也就是说 t 没有分配给任何一台电脑。所以，Kad之所以没有把节点查询过程严格地定义成为仅仅只查询单个目标节点的过程，这主要是因为Kad网络并没有对节点的上线时间作出 任何前提假设，因此在多数情况下我们并不能肯定需要查找的目标节点一定在线或存在

这里 α 也是为系统优化而设立的一个参数，就像 K 一样。在 BitTorrent 实现中，取值为 α=3 。

当 α=1 时，查询过程就类似于 Chord 的逐跳查询过程，如图：

【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

 

整个路由查询过程是递归操作的，其过程可用数学公式表示为：

n0=x (即查询操作的发起者)

N1=find −noden0(t)

N2=find −noden1(t)

... ...

Nl=find −nodenl−1(t)

这个递归过程一直持续到 Nl=t ，或者 Nl 的路由表中没有任何关于 t 的信息，即查询失败。

由于每次查询都能从更接近 t 的 K 桶中获取信息，这样的机制保证了每一次递归操作都能够至少获得距离减半（或距离减少 1 bit）的效果，从而保证整个查询过程的收敛速度为 O(logN) ，这里 N 为网络全部节点的数量。【因为：对于一个有 N 个节点的 Kad 网络，最多只需要经过 logN 步查询】

<key, Value>的查找：

当节点 x 要查询 <key,value> 对时，和查找节点的操作类似，x 选择 k 个 ID 值最接近 key 值的节点，执行 FIND_VALUE 操作，并对每一个返回的新节点重复执行 FIND_VALUE 操作，直到某个节点返回 value 值。

一旦 FIND_VALUE 操作成功执行，则 <key,value> 对数据会缓存在没有返回 value 值的最接近的节点上。这样下一次查询相同的 key 时就会更加快速的得到结果。通过这样的方式，热门 <key,value> 对数据的缓存范围就逐步扩大，使系统具有极佳的响应速度。cache的超时时间为节点-key之间的距离越远则超时时间越短。(【因为】 cache 为存活24小时，但是目标节点上的内容时每1小时向其他最近节点重新发布<key, value>使得数据的超时时间得以刷新，而远离目标节点的节点的数据存活时间当然就可能不会被重新发布到，所以也就是数据缓存的超时时间和节点的距离成反比咯)

数据的存放：

存放 <key,value> 对数据的过程为：

  1. 发起者首先定位 k 个 ID 值最接近 key 的节点
  2. 发起者对这 k 个节点发起 STORE 操作
  3. 执行 STORE 操作的 k 个节点每小时重发布自己所有的 <key,value> 对数据
  4. 为了限制失效信息，所有 <key,value> 对数据在初始发布24小时后过期

另外，为了保证数据发布、搜寻的一致性，规定在任何时候，当节点 w 发现新节点 u 比 w 上的某些 <key,value> 对数据（即 对Key更接近）更接近，则 w 把这些 <key,value> 对数据复制到 u 上，但是并不会从 w 上删除(超时时间到了，且远离了key则后续会自动被删除)

节点加入和离开：

如果节点 u 要想加入 Kad 网络，它必须要和一个已经在 Kad 网络的节点，比如 w，取得联系。

u 首先把 w 插入自己适当的 K 桶中，然后对自己的节点 ID 执行一次 FIND_NODE 操作，然后根据接收到的信息更新自己的 K 桶内容。通过对自己邻近节点由近及远的逐步查询，u 完成了仍然是空的 K 桶信息的构建，同时也把自己的信息发布到其他节点的 K 桶中。

所以， 节点 u 必须做三件事，【其一】不管通过何种途径，获知一个已经加入Kad网络的节点信息(我们可以称之为节点 w)，并将其加入自己的k-buckets；【其二】向该节点发起一次针对自己ID的节点查询请求，从而通过节点I获取一系列与自己距离邻近的其他节点的信 息；【最后】刷新所有的k-bucket，保证自己所获得的节点信息全部都是新鲜的

k-bucket和二叉树：

还记得在 节点状态 那一小节中我们讲了，在 Kad 网络中，所有节点都被当作一颗二叉树的叶子，并且每一个节点的位置都由其 ID 值的最短前缀唯一的确定。那么我们下面就讲一讲这个是怎么个设计：

在 Kad 网络中，每个节点的路由表都表示为一颗二叉树，叶子节点为 K 桶 (因为k桶里面装的也是节点)，K 桶存放的是有相同 ID 前缀的节点信息，而这个前缀就是该 K 桶在二叉树中的位置【前缀值确定了节点应该放到 什么距离的k-桶中】。这样，每个 K 桶都覆盖了 ID 空间的一部分，全部 K 桶的信息加起来就覆盖了整个 160 bit 的 ID 空间，而且没有重叠。

如：0000111 和 0000001是属于同一个k-桶的两个节点，其中对于他们的前缀可能是 0000 ； 而对于 1111111 和 1011111 来说 他们所属于前缀为 1 的这个 k-桶，总之当前节点 N 来说，它本地的全部 k-桶 组成了 节点N 所感知的全网节点的拓扑，当然这肯定只是真实的全网节点拓扑的一部分而已，但是对于节点N来说却是他所认为的全网拓扑，这样纸的各个节点本地的k-桶所组成的各个节点所认为的全网拓扑组成了一张逻辑上的真实全网拓扑。

下面是对某节点本地的k-桶进行二叉树的分割原理，以节点 u 为例，其路由表的生成过程为：

  1. 最初，u 的路由表为一个单个的 K 桶，覆盖了整个 160 bit ID 空间
  2. 当学习到新的节点信息后，则 u 会尝试把新节点的信息，根据其前缀值插入到对应的 K 桶中：
    1. 如果该 K 桶没有满，则新节点直接插入到这个 K 桶中；
    2. 如果该 K 桶已经满了，
      1. 如果该 K 桶覆盖范围包含了节点 u 的 ID，则把该 K 桶分裂为两个大小相同的新 K 桶，并对原 K 桶内的节点信息按照新的 K 桶前缀值进行重新分配【这一步就是为了分出新的k-桶好让新加入的节点放置到k-桶中】
      2. 如果该 K 桶覆盖范围没有包节点 u 的 ID，则直接丢弃该新节点信息 【没有包含u说明，当前k-桶不可以再分裂了，由于k-已经满了，所以新节点就被抛弃】

【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

上述过程不断重复，最终会达到距离近的节点的信息多，距离远的节点的信息少的结果【因为随着新节点的加入需要对原有某包含了当前节点u的k-桶进行拆分，可知，图中越来越多的节点加入k-桶中，随着k-桶的拆分，我们知道离目标节点越近的二叉树(k-

桶)越多】，保证了路由查询过程能快速收敛。具体原理为图中所示：

当 K 桶 010 满了之后，由于其覆盖范围包含了节点 0100 的 ID，故该 K 桶分裂为两个新的 K 桶：0101 和 0100，原 K 桶 010 的信息会根据其其前缀值重新分布到这两个新的 K 桶中。注意，这里并没有使用 160 bit 的 ID 值表示法，只是为了方便原理的演示，实际 Kad 网络中的 ID 值都是 160 bit 的。

节点离开：

节点离开 Kad 网络不需要发布任何信息，Kademlia 协议的目标之一就是能够弹性工作在任意节点随时失效的情况下。为此，Kad 要求每个节点必须周期性的发布全部自己存放的 <key,value> 对数据，并把这些数据缓存在自己的 k 个最近邻居处，这样存放在失效节点的数据会很快被更新到其他新节点上。所以有节点离开了，那么就离开了，而且节点中的k-桶刷新机制也能保证会把已经不在线的节点信息从自己本地k-桶中移除。

以太坊的Kad网络：

我们知道常规的kad网络节点的本地维护者 最多 160 个k-桶的信息，每个桶中 最多有K个临近节点的信息 (K 为经验取值， K 取值的原则是 不管什么时刻都能确保这K个节点中有 一个节点在网络中是存活的，通常取值 k == 20 为最好)；以太坊的节点本地有 256 个k-bucket，每个里面最多 16 个临近节点的信息；

而且传统的kad网络除了需要节点发现外还需要资源发现；而以太坊中主要是主要节点发现，所以kad协议的操作类型和传统的不一样：

  1. Ping：用于探测一个节点是否在线
  2. Pong：用于响应 Ping 命令
  3. FindNode：用于查找与 Target 节点异或距离最近的其他节点
  4. Neighbours：用于响应 FindNode 命令，会返回一或多个节点

节点的发现：

【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

邻居节点发现流程说明：

  1. 系统第一次启动随机生成本机节点NodeId，记为LocalId,生成后将固定不变，本地节点记为local-eth。

  2. 系统读取公共节点信息，ping-pong握手完成后，将其写入K桶。

  3. 系统每隔7200ms刷新一次K桶。

刷新K桶流程如下：

a.      随机生成目标节点Id，记为TargetId，从1开始记录发现次数和刷新时间。

b.      计算TargetId与LocalId的距离，记为Dlt，然后从该距离的桶中取出所有kadId。

c.      K桶中节点的NodeId记为KadId，计算KadId与TargetId的距离，记为Dkt

d.      找出K桶中Dlt 【这里的Dlt 是 KadId 和 LocalId的距离，因为任何和LocalId的距离都叫做Dlt】大于Dkt的节点，记为k桶节点，向k桶节点发送FindNODE命令，FindNODE命令包含TargetId

e.      K桶节点收到FindNODE命令后，同样执行b-d的过程【这时候，上一个KadId成为了新的LocalId了】，将从K桶中找到的节点使用Neighbours命令发回给本机节点。

f.       本机节点收到Neighbours后，将收到的节点写入到K桶中。

g.      若搜索次数不超过8次，刷新时间不超过600ms，则返回到b步骤循环执行。

 

邻居节点网络拓扑及刷新机制：

【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

 

1 TargetId为随机生成的虚拟节点ID。

2 以太坊Kad网络与传统Kad网络的区别：

  1. 以太坊节点在发现邻居节点的8次循环中，所查找的节点均在距离上向随机生成的TargetId收敛。

  2. 传统Kad网络发现节点时，在距离上向目标节点本身收敛。

可能上面这种说法不是很明白，来，我们下面用另外一种说法来说一说，既然以太坊刷桶，是基于节点发现这个角度出发的，那么我们应该发现的是所有和目标节点相邻的节点集，基于上面的说法和下面这个图，我们应该会明白：

【我的区块链之路】- 理解传统Kademlia和以太坊Kademlia网络

即，每一次都用新的LocalId和返回的桶里面的KadId分别和targetId的距离做对比，符合：Dlt > Dkt 的kadId，然后继续发送 FindNODE命令。【假想： 如果用 Dlt < Dkt 的呢？自己画个图就知道了，这样纸获取的KadId 永远距离 targetId越来越远了】

至此，我们先告一段落，放心，后面发现有不足的我都会及时补充~

相关文章