王子亭的博客

去中心化的零毫秒计划了很久，一直都没能开始，原因很简单，就是我无法想象这样一个项目应该如何设计，都有哪些部分，从哪开始。

即使这两年来我学习了不少有关公钥加密和证书体系，Bitcoin 的实现，一些 DHT 网络的实现等，但依旧如此。

这段时间有很多目标类似的项目出现，我所知道的就有 BitMessage, BitTorrent Chat, Tox.

所以我以为这个项目就要这么坑掉了。

但前一阵，我一直想着重写 ZeroMS-1x, 即两年前我初学 Qt 的时候，写的零毫秒的第一个版本，一个十分简易的中心化，C/S 结构的聊天工具。

重写的目的也很简单，只是希望当初花了好大功夫写的东西不至于不能运行——虽然重写的时间应该不会小于当初花费的时间。

于是我开始设想如何设计这个重写版本。

首先不能再使用之前那丑陋的通讯协议载体，转而使用 JSON.

然后就是之前那蛋疼的帐号机制。

之前的帐号机制是使用 PHPWind 论坛(后来是 esoTalk)系统的帐号系统，服务器会请求论坛上的一个 PHP API 来验证登录信息。

我决定使用公钥加密(RSA), 的密钥对代替帐号系统。

一对公私玥就是一个帐号，公钥是帐号的唯一 ID, 私钥是持有帐号的凭证。

登录时，客户端用私钥为登录信息签名，同时提供一个短的，不唯一，可变的昵称作为友好的显示名。

再进一步，可以让发信人对所有发出的消息进行签名，以认证身份。

再进一步，可以让发信人对所有签名过的消息，用收信人的公钥进行加密，使只有拥有私钥的收信人才能解密。

至此，我们惊奇地发现，虽然整体仍是 C/S 结构的网络，但是我们似乎已经剥夺了服务器的大部分权力——服务器无法查看消息的内容，也无法篡改或伪造消息。

于是，服务器似乎变成了一个非必须的部分，因为作为服务器，不需要什么资格，也没有什么权力，任何人都可以当服务器！

甚至可以让多个服务器接力地完成一个消息的送达过程。只需要送达就可以了！无论中间是谁来传递的，也无论中间有多少人经手，因为它们看不了消息也改不了消息，就算你写在纸上飞鸽传书也没有什么不可以。

这时的服务器已经不能叫做服务器了，应该叫网关或者路由，就像 IP 中的网关一样，工作是将 IP 数据包送达指定的地址。IP 网络的网关各自维护了自己的路由表，同时基于 IP 地址的 IP 网络也是一个结构化的网络，所以这很简单。

而在零毫秒的网关之间，可以维护一个分布式散列表(DHT), 如类似 Kademlia 协议的 DHT, 储存网络上每个用户(公钥)和所对应的地址。

这样一来，原来我想要的去中心化即时通讯就是这么简单！之前一直把它想得过于复杂了，原来就是这么简单的一个构造而已！

既然图景已经清晰，我们还可以讨论一些更为细节的话题。

首先是公钥交换，通过上面的设计，要与一个人通讯，必须知道他的公钥，当然，获取公钥的过程很简单，问题是如何保证这个过程的安全性呢？如果密钥在通信的途中被替换了怎么办？这在 HTTP 环境下很容易发生。

有人提出应成立一个证书颁发机构(CA), 对用户的公钥进行签名，但这似乎有悖于去中心化的精神。

我认为公钥交换应该由用户自行解决，用户可以自行选择渠道，如 HTTP, HTTPS, 其他 IM 如 QQ, 当面交换纸质(二维码)公钥。而事实上也有提供公钥交换服务的网站，如 pgp.mit.edu (我不得不吐槽一下这个网站居然只有 HTTP 版本), 这些望着本来是为了交换 PGP 公钥而设计的，不过对零毫秒也是适用的。

因为用户可以自行选择渠道，用户的选择越多样，「信任链」的构成就越分散，攻击者发起攻击的成本就越高，整个系统就越安全。

之前我们讨论过，网关无法阅读或修改流经它的消息，但是网关可以选择丢弃消息，不予转发，那么如何应对这种消息丢失的情况呢？

事实上 IP 的网关也有类似的特点，即它可以随意丢弃消息，IP 对此的解决方案就是不予考虑，将这个工作交由上层协议来实现，比如 TCP.

TCP 会在通讯的双方，也就是两个端点来进行一些操作，而中间的 IP 网关不必考虑，甚至不必知道这是一个承载 TCP 协议的包。

「在端点实现功能」也是 TCP/IP 网络体系的一大特点。

由此，零毫秒中的两个客户端之间，应该自行协商，防止消息丢失。

最简单的办法就是在每一条消息中，嵌入上一条消息的散列值(Hash), 当中间的某个消息丢失时，双方可以察觉到，自行协商，对丢失的消息进行重传。

这样一来，客户端需要自行维护很多状态，例如对于每个联系人的上一条消息，这导致用户在更换设备时需要一并携带这些信息，否则就会导致通讯不正常，这是目前很难解决的问题，最理想的就是使用同步盘服务(可以是自建的)来同步这些数据。

另一方面是接收离线消息，客户端可以指定一个长期在线的网关作为离线代理，由这个网关来代收离线消息，上线后再从这个网关抓取离线消息，这符合在端点实现功能的原则。

这个网关可以是用户自建的，也可以是公共的「离线代理网关」。

最后要讨论的一个话题就是组群。

建立一个组群就是生成一个新的密钥对，公钥即为该组群的ID, 私钥由管理员掌握，用于签发新成员加入和移除现有成员的通知。

然后组群的成员根据管理员签发的公告，计算出目前的成员列表，逐个发送消息。

这个实现似乎很不完善，既无法阻止成员把消息发到非组群成员那，也无法阻止成员忽略组群中的一些成员，全靠成员的自觉。

而且如果有其他 10 个成员，那么每条消息就需要发送 10 遍，因为要保证网关不能阅读消息的内容，每一条消息都需要用不同的，收信人的公钥来加密。

Kademlia协议(模型)是被电驴，BitTorrent所采用了的，基于异或距离算法的分布式散列表(DHT), 它实现了一个去中心化的信息储存与查询系统。

Kademlia将网络设计为一个具有160层的二叉树，树最末端的每个叶子便是一个节点，节点在树中的位置由同样是160bit的节点ID决定。

每个bit的两种可能值(0或1), 决定了节点在树中属于左面还是右面的子树，160层下来，每个节点ID便都有了一个确定的位置。

Kademlia使用独特的异或距离算法来计算节点间的距离，异或是一种简单的数学计算，它有很多独特的性质，这些性质在之后会为我们带来方便：

自己与自己的距离为0:
x ^ x = 0
不同的节点间必有距离:
x ^ y > 0
交换律，x到y的距离等于y到x的距离:
x ^ y = y ^ x
从a经b绕到c, 要比直接从a到c距离长:
a ^b + b ^ c >= a ^ c
下面两个是资料上提到的，似乎很重要，但我不大理解他们的含义:
a + b >= a ^ b
(a ^ b) ^ (b ^ c) = a ^ c

在Kademlia中，异或(距离)算法具有单向性(或者说一一对应关系)，即给定一个节点和一个距离，必定存在唯一一个相对应节点。包括距离算法在内的，Kademlia中大部分的概念，都既有算术上的意义，又可以在节点树上表现实际意义。

事实上，节点间距离反映的就是节点ID中比特的差异情况，而且越靠前的比特权值越大。或者说是反映节点在树中相隔了多少个分支，需要向上多少个树节点才能找到共同的祖先节点。

Kademlia中使用了名为K-桶的概念来储存其他(临近)节点的状态信息，这里的状态信息主要指的就是节点ID, IP, 和端口。

对于160bit的节点ID, 就有160个K-桶，对于每一个K-桶i, 它会储存与自己距离在区间 [2^i, 2^(i+1)) 范围内的节点的信息，每个K-桶中储存有k个其他节点的信息，在BitTorrent的实现中，k的取值为8.

下表反映了每个K-桶所储存的信息

放在节点树上，即每个节点都更倾向于储存与自己距离近的节点的信息，形成 储存的离自己近的节点多, 储存离自己远的节点少 的局面。

从上表可以看出，在1-15这个范围内的节点，只要发现，就会被100%地储存下来，而离自己距离在1000左右的节点，只会储存13%.

对于一个节点而言，K-桶就代表着节点树上那些未知的节点(其实除了自己都是未知的)构成的子树，160个K桶分别是具有1到160层的子树，由小至大。对于节点ID, 160个K-桶分别储存着节点ID前0到159个bit和自己一致的节点。

K-桶中的条目(其他临近节点的状态信息)排序的，每当收到一个消息(如查询)时，就要更新一次K桶。

首先计算自己与对方的距离，然后储存到对应的K-桶中，但如果K-桶已满(前面提到每个K-桶储存有k=8个条目), 则会倾向放弃储存，继续保持旧的节点信息(如果还有效的话). 除了距离外，Kademlia更倾向于与在线时间长，稳定的节点建立联系。

这是因为实践证明，累积在线时间越长的节点越稳定，越倾向于继续保持在线，即节点的失效概率和在线时长成反比。

这样还可以在一定程度上抵御攻击行为。因为当大量恶意的新节点涌入时，大家都会选择继续保持旧的节点信息，而不是接受新的。

除此之外，还需要定时检查K-桶中的节点是否任然在线，及时删去已失效节点。

Kademlia协议仅定义了四种操作：

• PING: 探测一个节点是否在线
• STORE: 令对方储存一份数据
• FIND NODE: 根据节点ID查找一个节点
• FIND VALUE: 根据键查找一个值(数据)

当查找一个节点时，首先计算自己与目标节点的距离d, 然后将 log₂d 向下取整，找到对应的K-桶，从这个K-桶中选取a个节点(在BitTorrent的实现中取值为3), 向它们发送查询。

收到查询的节点同样计算距离后从自己的对应K-桶中选取a个节点返回给查询者。查询者不断重复这个过程，知道找到目标节点，或无法再找到更近的结果。

很多资料将这个过程描述成是递归的，但我觉得这里认为它是迭代的更为恰当。

因为每个节点都更倾向于储存距自己近的节点的信息，而整个网络又是一个二叉树，因此每次查询都会至少取得距离减半的结果，对于有N个节点的网络，至多只需要 log₂N 次查询。

当进行 FIND VALUE 操作时，查询操作是类型的，每份数据都有一个同样是160bit的键，每份数据都倾向于储存在与键值距离较近的节点上。

当上传者上传一份数据时，上传者首先定位几个较为接近键值的节点，用STORE操作要求他们储存这份数据。

储存有数据的节点，每当发现比自己与键值距离更为接近的节点时，便将数据复制一份到这个节点上。

当一个新节点欲加入网络时，只需找到一个已在网络中的节点，借助它对自己的节点ID进行一次常规查询即可，这样便完成了对自己信息的广播，让距自己较近的节点获知自己的存在。而离开网络不必执行任何操作，一段时间后，你的信息会自动地从其他节点被删除。

毫无疑问，Kademlia要比我之前为零毫秒设想的网络模型优秀得多，更为彻底地实现了去中心化，弱化了关键节点失效对整个网络的影响。而电驴和BitTorrent的实践也证明了kademlia是具有相当的可行性的。

Kademlia的精妙之处在于它选择了异或运算作为计算距离的依据，异或运算不仅具有算术的意义，在二叉树式的网络模型中，同样具有实际意义，同时任何情况下都在强调距离的概念，让节点间通过距离来聚合起来。

在上一篇日志的末尾，我便在思考如何来聚合节点，现在通过Kademlia, 我算是找到了。下一步我想思考的是，既然以上是Kademlia的优势，那么它的弱势在哪？哪些地方存在不足？

零毫秒，计划已久，也拖了很久，其概念一直都在我的脑海中，这可能是第一篇正式的“讨论”。

之所以是讨论，是因为我对整个系统的架构依旧迷茫。而相比之下，RootPanel(RP主机面板), JyBBS(论坛系统), 的蓝图则非常清晰，实现起来不过是时间问题而已。

目前最大的困难是没人和我讨论，这个项目几乎走在了世界前列，没有多少资料可以借鉴，希望正在读的《计算机网络——自顶向下方法》能给我一些帮助。

然而当前几天我看到又一个类似项目，比特信(BitMessage)的时候，不能再忍了。

纵观现在的互联网，个人认为它具有以下几个特点：

面向信任模型

即默认假定网络中的节点都是受信任的，如：IP和TCP, UDP数据报均不加密不签名，传输过程中的任何路由节点均可修改数据报。IP不提供担保，能否无误送达取决于中间路由节点。发信人向收信人发送数据报完全不需要收信人的同意，收信人无法拒收。

分层架构，在端点实现功能

即大多数功能在通信的两端实现，中间的路由无需关心，只需转发。如TCP的面向连接，排序，错误重传，IP的分段等等。

同时协议分层，上层协议更新不影响底层协议。

天生去中心化

互联网从未依赖于一个中心节点，每个路由都是独立工作的，这使得没有人能控制整个网络，除非控制每一个路由器。同时即使一处网络断开，被分割的各个部分也可以单独工作。

IPv6一定程度上解决了IPv4在上述特点中暴露的问题，IPv6的普及工作已经进行了十几年，仍没有显著成效。零毫秒希望在应用层组建一个去中心化网络，为上层应用提供身份验证，名称注册，加密传输，节点查找，信息广播/查询，组群，离线储存等功能。作为一个示例，零毫秒会首先实现一个即时通讯软件。

可以预见，在应用层进行数据报转发是非常不明智的。零毫秒也分为多层架构，在核心(最底层)只转发控制指令，实现最为基本的组网和节点查找功能，毕竟只要找到目标节点，即可进行点对点通讯。通过组件树状的结构化网络，为上层应用提供方便，使网络流量最小化。

零毫秒分层：

• 核心层：组网，节点查找，身份验证，组群
• 服务层：名称注册(加强版DNS), 信息广播和查询，离线储存
• 应用层：应用自有协议，如即时通讯

零毫秒网络有树状的结构，每个树节点有30个子节点。最次一级叫NNode(Normal Node), 其余具有子节点的树节点叫MNode(Master Node). 由底向上，由多至少，按层级分别为M1Node, M2Node, M3Node, 可无限扩充。一个新节点接入网络时，只需知道网络中任意一个节点的地址(IP和端口), 即可通过它获取到M1Node列表，并逐个尝试接入。网络中第一个节点启动时，则直接默认自己是M1Node. MNode需要有公网IP, 或使用UPnP.

加入网络后，作为NNode, 可以向M1Node申请成为M1Node. 成为M1Node后可向M2Node申请成为M2Node, 如果没有M2Node, 则像其他M1Node申请成为第一个M2Node.

申请是否成功并非绝对，有多少节点通过了你的申请，你就成为了多少节点眼中的MNode. 处理申请时要考虑的因素包括：网络延迟，带宽，已有节点数量，历史信用等。

这可能让读者存在一些疑惑，最高级的MNode是否可以控制整个网络，进行破坏呢？事实上因为零毫秒会对每一个数据包进行加密和签名，所以即使是MNode也无法对数据包进行篡改。当然它可以选择不作为——不按约定转发数据包，但这种行为会很快地被发现，其他节点会很快自动地推选出另一个MNode. 同时可以在核心层实现一个简单的点对点信用系统(类似于电驴的积分系统), 每当上级MNode为自己提供服务时，即为对方增加一点信用值，当上级MNode出现丢包，网络中断时，即为对方减少信用值。一段时间后，该信用值将能够很好地评估对方是否适合成为一个MNode.

我们再来讨论该模型的负荷，很显然，整个网络的节点数量取决于MNode的层级，以30为底数呈指数关系，而整个网络的瓶颈在于最高级的MNode, 因为在接下来的设计中，MNode需要储存(缓存)其所有(直接或间接)子节点的信息。这些信息包括256 Byte的用户ID(公钥), 18 Byte的地址(兼容IPv6, 以及端口号), 可选的256 Byte的额外信息(如节点层级等等), 合集530 Byte.

下表是含有M1Node至M8Node的网络下，可容纳节点数与MNode所需储存的信息的表格：

以当前硬件水平而论，M1Node至M3Node, 甚至M4Node, 都可以运行于个人计算机。而M4Node和M5Node适合运行于服务器，M6Node可运行于高性能集群。至此，M6Node已可以容纳2.2亿个节点。至今内存的发展远未达到瓶颈，仍在以摩尔定律预测的速度更新，更何况MNode可通过散列表，数据库引擎等技术来降低内存占用，所以单就内存而言，我认为不存在瓶颈。

在这种树状结构下，节点查找显得十分有序：逐级向上查找即可。查询经过的节点数量在最不理想的情况下，和网络规模(节点数量)成对数关系。当然，前文只讨论了内存瓶颈，毫无疑问最顶层MNode会收到大量的查询请求。但我们可以非常简单地通过集群来处理查询。即使在极大规模的MNode, 如M7Node, 我们也可以通过两层集群轻松应对：路由将零毫秒的数据包(甚至可以不做区分，直接全部)随机发往第一个集群，读出被查询的ID, 进行散列后发往第二个集群中的散列值前缀指定的服务器。每个服务器只需处理指定散列前缀的查询。数据包加解密和序列化可由单独的服务器进行。

在具体实现方面，我选择了以RSA公私玥对作为用户标识，公钥为ID, 私钥为凭证，每个数据包均需签名，签名值同时可以作为一个数据包的编号。节点之间使用SSL连接，支持IPv6. 因为目前所讨论的内容只涉及控制指令，所有指令都无需加密，这样可以使节点列表等信息被中间节点所缓存。所以只需在节点之间加密即可，无需在端点之间进行加密。

我选择使用JSON来承载通讯协议，因为JSON应用广泛，被众多开发环境支持，易于调试，具有很好的扩展性，同时可作为流来使用。为提高传输性能，可以考虑使用其二进制版本BSON, 也可以JSON, BSON双支持，前者用于调试环境，后者用于生产环境。

我还需要指出目前设计存在的几个问题：

节点的聚合方式

30个节点依据什么聚合在一起？我更倾向于按网络情况聚合，这样可以保证在网络的任意部分都具有高速的连接。不过也可以考虑通过经常联系与否来进行聚合，毕竟在较低层级处理查询将显著减少顶级MNode的负荷。

单个节点如何估计网络规模，选择时机进行“升级”

时间校准

数据包中应当包含时间戳，以供今后查证，但很难找到一个去中心化的时间校准方式。