北京大学学术 |以太坊p2p网络结构算法概述

Trias与“北京大学微软-八元协同创新实验室”定期举办技术沙龙。该实验室成立于去年9月，以可信计算和区块链为主要研究方向，致力于推动智能互联新时代人机互信问题的解决。关于沙龙的具体细节，我们将推出由实验室教授和博士生撰写的系列文章。本文由北京大学博士生张晓磊撰写。

最近很火的区块链技术大家应该都不陌生。但是，很多人只了解区块链技术的一些概念，可能并不了解一些底层技术实现原理。本文将为您介绍区块链底层使用的通信网络技术以及网络中节点之间的通信协议。

区块链底层网络技术采用点对点网络，简称P2P网络。这是一种分布式网络通信技术，也称为“点对点网络”。不同于传统的客户端/服务器（C/S）结构，P2P网络中的节点之间没有主从之分，地位平等，每个节点既可以是服务器，也可以是客户端。

P2P网络根据其路由查询结构可分为四种类型，即集中式、纯分布式、混合式和结构化模型。这四种类型也代表了P2P网络技术的四个发展阶段。

其中，比特币采用混合型的生活经验，而当今的大多数公链都采用结构化型。在结构化网络的具体实现中，大多采用DHT（Distributed HashTable，分布式哈希表）算法的思想。基于DHT算法思想的具体实现方案包括Chord、Pastry、CAN、Kademlia等算法。 Kademlia算法是以太坊网络使用的算法，我们将在本文中详细介绍。

比特币网络

区块链技术最早的应用是在比特币中。正如我们前面提到的，比特币网络的结构是一个混合网络。

比特币网络节点有四个功能：钱包、挖矿、区块链数据库、网络路由。这四个功能并非比特币的所有节点都包含。不同类型的节点只包含一些功能。只有比特币核心节点会包含所有这四个功能。

图1.全节点示意图，其中Wallet代表钱包功能，Miner代表挖矿功能比特币客户资源，FullBlockchain代表完整的区块链数据库，Network代表路由功能[1]

不同节点的类型根据其包含的功能不同，但所有节点都会包含路由功能，因为所有节点都必须参与校验和广播（传播交易和区块信息），并发现并保持与其他节点的连接。

另外，一些节点包含一个包含所有交易数据的完整区块链数据库，这样的节点被称为“FullBlockChainNode”。全节点可以独立验证所有交易。

还有一些节点只包含部分区块链数据，一般只有区块头。此类节点通过“简单支付验证（SPV）”的方式完成交易的验证。它被称为“SPV 节点”或“轻量级节点”。

矿工节点通过在特殊设备上运行工作量证明算法（挖矿）相互竞争生成新块。

部分矿工节点为全节点，称为“SoloMiners”，而其他矿工节点则需要依赖矿池服务器维护的全节点进行挖矿工作。称为“PoolMiner”，矿池矿工和矿池服务器组成一个矿池（MiningPool），是一个本地中心化网络。它们通过特殊的矿池协议相互通信。

目前主流的矿池协议是Stratum协议。钱包功能一般是帮助用户查询自己的余额、管理公私钥对和发起交易。在比特币网络中，除了比特币核心钱包是全节点外，大部分钱包都是轻量级节点。

一个比特币扩展网络，包括运行比特币主网络协议、Stratum网络协议和不同节点之间的其他矿池网络协议的各个节点，如下图所示：

图2.比特币扩展网络图[2]

以太坊网络

以太坊作为新一代以区块链为底层技术的平台在很多方面与比特币相似。其节点还具备钱包、挖矿、区块链数据库和路由四大功能。由于功能不同，它也被划分为节点。除了主网络之外，还有许多不同类型的扩展网络。然而，与比特币不同的是其底层网络结构。比特币主网的P2P网络是非结构化的，而以太坊使用的P2P网络是结构化的，其P2P网络是通过Kademlia（简称Kad）算法实现的。 Kad算法作为一种DHT（分布式哈希表）技术，可以在分布式环境中实现快速准确的路由和数据定位功能。接下来我们重点介绍Kad算法的基本内容。

Kad算法作为一种分布式数据存储和路由发现算法，因其简单、灵活、安全，被以太坊用作底层P2P网络的主要算法。下面我们将通过一个例子来说明Kad算法的主要内容及其操作过程。

问题描述和情景假设

我们假设这样一个场景：有几本书供学生分享比特币客户资源，为了公平起见，每个人都保留了几本书，如果您想阅读其他书，则需要向保留书的学生借。书。那么问题来了，我们如何才能找到保留这本书的学生呢？如果一一问，效率显然是极低的。把这个问题放到P2P网络中是，如果一个节点需要某种资源，它是如何获得这个资源的呢？如何快速找到存储资源的节点？

节点信息

就像我们对学校的每个学生都有一个唯一的标识符一样，Kad 算法中为每个节点设置了几个属性来唯一标识一个节点，分别为：节点 ID、IP 地址、端口号。在我们的示例中，节点ID对应学生的学生ID，IP地址和端口号对应学生的联系信息（电话号码或家庭地址）。

每个学生（节点）都有以下信息：

·分配给它的书信息（分配给节点的资源信息）。这里的信息是指书名和书内容的哈希值（对于被理解为节点资源中的资源的资源的索引和内容，它以of的形式存储在节点上）。

·一个地址簿，里面存储了几条记录，每条记录是一本书的书名的hash值和存放该书的学生的学号和联系方式（一个路由表，每个路由项存储一个索引资源和存储资源的节点信息。在Kad算法中，这个路由表称为“K-bucket”，后面我们会详细介绍“K-bucket”）。值得注意的是，这里的每个学生只存储了一部分同学的联系方式（节点的路由表只存储了一部分节点的信息）。

资源存储和搜索

那么问题来了，我们应该如何给每个学生分配书籍（给节点分配资源）？

在Kad算法中，它是这样做的：对每本书的书名进行hash计算，将书名的hash值作为书的索引，然后计算书的索引和索引之间的索引节点 ID。在它们之间创建映射。如果一本书的hash值为000110，那么这本书会分配给学号为000110的学生。（这要求hash算法的取值范围和节点ID的取值范围一致。在以太坊中，节点ID是256位二进制，因为以太坊使用的哈希算法是sha-3，所以结果长度是256位二进制）

那么这里就会有人问了，如果某个学生联系不上（节点下线或者退出网络），那么他保存的书（资源）就拿不到了。 为了解决这个问题，Kad算法采用的方法是在几位学号最接近000110的学生手中存一份书本，这样几位学号为00011的学生1、 000101等人手中也会有这本书的副本。这本书（在节点上就是把相同的资源存放在离目标节点ID最近的几个节点上）。

当你需要找这本书的时候，你只需要对书名进行hash就可以知道你要找的学生的联系方式（对于节点中的资源来说，我们只需要计算资源索引才能知道要查找哪个或哪些节点）。

节点位置

我们已经知道应该找到哪些学生来获取这本书，所以下一个问题是如何找到他们的联系信息。这里我们介绍一下Kad算法中的路由表——“K-bucket”。 K-bucket作为一个路由表，存储了节点的路由信息​​，但是和一般的路由表不同的是，在K-bucket-bucket中，节点是按照距离进行分类的，如图3所示。节点之间的距离问题是这里提到。我们先来看看kad算法中两个节点之间的距离是如何计算的。

Kad 算法中节点之间的距离是一个逻辑距离，它是通过对节点 ID 进行异或运算来计算的。当目标节点到该节点的距离在[2(i-1), 2i)的范围内时，该节点被分类为“K-bucketi”。例如，节点ID为000111的节点与节点ID为000110、000011的节点之间的距离计算为：000111 Å000110 =000001 (decimal1）, 000111 Å000011 =000100 (decimal< @4）。那么根据上面的算法，在节点ID为000111的K-bucket中，将节点ID为000110的节点分配给“K-bucket1”，将节点ID为000011的节点分配给“K-桶3"。

图3.K-bucket图

其实这种使用异或计算距离的方法相当于将整个网络拓扑组织成一棵二叉前缀树，如图4所示。这里的所有节点都分布在二叉前缀树的叶子节点上。这种组织形式就相当于按照节点ID的每一位来对节点距离进行分类。

以图中节点号110为例，因为节点000、001、010第三位（从右往左数）和110不同，所以这三个节点是分配给110的“K-bucket3”，而ID为100、101的节点第二位（从右往左数）与110不同，所以将这两个节点分配给“K-bucket2” ”的110，而ID为111的最后一个节点是第一个（从右往左数）和110不同，所以放在110的“K-bucket1”中。

图4.表示网络拓扑的二叉前缀树[3]

回到以太坊，如前所述，每个节点ID都是256位长，所以以太坊中节点的K-bucket大小被分配为256行，每行最多存储16个节点的路由信息​​。

通过前面的内容，我们已经知道了如何找到另一个学生的联系方式（节点之间的距离计算）以及每个学生存储的通讯录的结构是什么（节点中K-bucket的存储结构）。那我们找一本书，看看如何在Kad算法中找到某个节点。

一个学生ID为000111的学生想找一本叫《西游记》的书（ID为000111的节点想找一个特定的资源），他首先计算书名值的hash得到索引这本书的（获取资源的索引），经过计算，《西游记》的hash值为001011，那么他就知道这本书是保存在学生号001011的学生B手中。接下来，A同学计算距离该学生找到他的通讯录（节点计算目标节点与自身的距离，并检查K-bucket中是否有目标节点）。异或计算后：000111 Å001011 = 001100（十进制12），计算后发现距离12位于区间[23, 24)，所以A同学去第4行查看他的通讯录中是否有B同学的联系方式：

·如果有——直接联系B向他借书；

·如果没有--找一个也在4号线的同学C联系他，让C同学用同样的方法在他的通讯录中查找是否有同学的联系方式B. 原因是学生C的学号第四位（从右到左数）必须与学生B的学号相同。第四名也是一样，所以从逻辑上讲，C班和B班的距离肯定比A班和B班的距离更近。那么就会有两种情况：