【论文阅读·BlockChain】Information Propagation in the Bitcoin Network

以下解读均为本人个人见解，如有曲解或造成不必要的麻烦，欢迎联系我 nexisato0810@gmail.com 进行修改。正文内容中的“作者”均为paper作者本人，我的观点会由“我”或在括号“()”内显式注明。

【Paper作者】：Christian Decker, Roger Wattenhofer

【一句话总结】：从网络角度分析了比特币的消息传播流程和它的局限性，并提出了加速传播方法.

【Introduction】

**比特币(Bitcoin)**是全球真正意义上的第一个全球性的去中心化数字货币系统，它承载着与其他货币一样作为一般等价物的本质，但不由任何机构颁发. 自从2008年末期诞生以来，其交易值和交易数量越来越大. 由于在比特币发行以前，交易系统的研究更关注于构建可信任的中心化发行人，或创建用户与用户之间的信赖关系，仍由发行人对交易进行清算.

比特币通常被视为现金，但其实功能已经超越了现金的范畴. 比特币的所有交易历史公开，并且在全球范围内的交易速度都非常快，提供了智能财产、小额支付、合同、托管交易等功能用于调解交易纠纷. 目前已有部分公司允许使用比特币进行交易.

尽管如此，比特币的基本规则没有什么问题，但是仍然有一些提升空间，比特币解决的问题是交易的分布式追踪和验证，每个用户都可以有一份交易历史的副本，这些副本可能并不完全一致，但比特币的最终一致性会确保这些副本分支达到同步. 交易的验证是根据副本的状态进行验证的，如果一条交易记录在不同副本上不一致的话，这条交易就是不确定的，这种情况就会导致危及到比特币交易共识本身的安全性，对那些试图重写交易历史的攻击者而言是很有帮助的.

这篇paper从网络的角度对比特币进行了分析，如：消息是如何在比特币网络之间进行传播的，并找到这种传播机制的关键弱点，以及分析它可能引发的各种交易问题. 此外，作者分析了比特币的交易同步机制，并针对这些同步协议的弱点提出修改建议.

【比特币概述】

比特币网络中传播两种类型的信息：交易和区块. 交易代表着价值（或财产）的转移，而区块用于同步网络中所有结点的状态. 不同于传统货币，比特币依赖分布式的 “志愿者网络” 共同复制分类账本. 分类帐本用于追踪所有账户的余额，记录了比特币交易记录而非余额，网络中的每个结点保留一个完整的账本副本，交易的有效性是针对这些副本进行验证的，因此这些副本需要保持一致.

交易

在上层抽象层而言，一笔交易，就是从一个或多个源账户，转移到多个目标账户的过程. 一个账户，本质上是一个公钥/私钥对，公钥派生的地址用于识别账户，私钥用于对发送方账户的发起的交易进行签名加密. 交易由一条序列化的消息的哈希值表示，通过提供交易发起方的归属证明来声明输出，而对这些输出的引用和所有权的证明构成了交易的输入.

输出是交易信息的基本单元，由于在副本中要保持一致性，所以声明和创建要遵循如下准则：一个输出仅可以声明一次、仅作为交易的结果创建、声明的输出值总和必须大于等于新分配的输出值的总和. 当交易通过网络传播时，接收结点收到交易消息后，账本的副本状态会随之发生变化，经过验证后，这条交易记录就被上传到本地交易副本. 随着时间的推移，各结点的交易副本可能会变得不一致.

如果有不同的交易尝试转移统一部分比特币，这种现象称为 “双重花费攻击”. 这对分类帐本会产生直接影响. 假设有一个结点收到交易信息，并经过验证将其提交到本地账本副本，但是当其他结点收到这条交易消息时，交易会失败，因为币已经花出去了，所以这里就有一个交易冲突.

区块

比特币使用区块技术同步交易记录. 具体来说，在某个结点完成交易后，会创建一个区块，并向网络中其他结点广播这个区块. 这个区块包含了自上一个区块被广播出来后，该结点的交易记录. 接收这个区块的结点将交易记录回滚到上一次广播区块的记录，并用新区块的交易记录进行合并 (类似于 git 的分支同步)，这样冲突的交易就无法进行合并，这些冲突的交易因为失效而被丢弃.

不过，区块的创建结点只能决定交易什么时候到达对方结点，或者在创建的区块中是否写入该交易记录，因此，只要区块链系统底层的公钥/私钥对是安全的，就不能伪造任何交易.

决定能否创建区块的机制称为 “工作量证明机制”，这个机制很简单，就是通过计算找到一个随机字符串，我们称为 “nonce”，这个字符串与区块头部进行结合，生成一个哈希值，这个哈希值也是区块自身的身份标识. 加密哈希是单向函数，因此如果想通过哈希值反解字符串，只能通过暴力枚举的方法找到一个有效的随机数. nonce 被视为区块的一部分，所以接收结点可以直接验证创建者的工作量. 想通过暴力计算得到这个随机数的结点，就称为“矿工”，为了奖励矿工的工作量，算出这个随机数的矿工，会被奖励一部分新的比特币，即一笔没有输入但可以指定输出的交易.

区块链

区块以有向树的形式连接在一起，构成区块链. 每个块包含对先前块的引用，如区块 $b$ 引用区块 $b_0$ ， $b_0$ 就是区块 $b$ 的父块，父区块的哈希值必须是已知的. 树中的根块称为 创世区块 ，它是所有区块的祖先，被硬编码到客户端中. 区块链被定义为从任何块到创世区块的最长路径，它们之间的距离称为区块高度. 低高度的区块中交易验证要先于高度较高的区块. 不过，只有出现在区块链中的区块，才会被所有用户结点承认，因而这个区块奖励的比特币才会有效，所以矿工通常是去尝试寻找能连接到当前区块链头的区块.

区块链分叉

在这样的规则下，区块链的头部可以是多个，这样的情况称为 区块链分叉，这会导致系统的不一致性. 如果在区块 $b_h$ 和新发现的区块 $b_{h'}$ 处于同一分支，那么它将检查这个分支上的所有中间区块，并逐步更改交易；若处在不同分支，则依照较长的区块的交易规则，回退到它们的共同祖先区块，并按这这个规则对交易记录进行修改. 区块链网络经过分区如果可以找到不同的分支，那么总会有一条分支是最长的，如果没有采用这个分支的分区，就切换到这个分支上，其他分支就被丢弃，并且保证各结点的账本副本要和这个区块链头一致.

区块链分叉导致任何交易都不能被明确提交，因为都有可能会失效，且如果某个结点控制了全网上的大部分算力，那么它就可以比其他结点更快找到新的区块，从而改写交易记录，恢复先前的交易，并在此基础上创建新的区块，直到形成一条比原始长度更长的区块链.

【消息传播】

加入区块链的结点需要先查询一组DNS服务器，由志愿网络运行. 结点通过向邻居
查询已知结点的地址. 如果要离开网络的话，其地址还会在其他结点中保留几个小时. 每个结点会打开至少 $p$ 个连接，如果没有的话就从已知的结点中随机选取一个建立连接. 对于那些接收传入连接的结点，连接数会更高.

区块链网络中存在着分区的现象，各分区之间的交易是独立运行的，但是交易记录会随着时间的推移而发散增加，并且这些交易记录可能是互相冲突的. 一般在区块查找效率下降时，可能表明发生了分区. 但是分区一般不会被主动检测到，我们可以通过观察网络的聚合计算能力得到.

在区块链中，只有交易信息和区块信息具有相关性. 一般对于这种消息要避免直接转发的，如果接收到交易和区块信息，并经过验证之后，就要向它们的邻居结点发送inv信息，表示当前结点可以被请求. 接收到inv消息的结点，会向发送该消息的结点请求获取数据. 如下图所示

区块链中每一发送消息的原结点，都要通过上述这一跳，通过网络向其他结点广播传播消息. 消息的验证和在网络中传播的时间开销，统称为传播延迟. 我们定义从网络中的源结点第一次发出传播公告时，到结点 $j$ 收到数据消息 $i$ 的时间为 $t_{i,j}$ ，遵循“双指数规律”. 这个规律分为两个阶段：初始的指数增长阶段，大多数收到inv消息的结点会向数据项 item 发送请求；后续的指数衰减阶段，这是因为大多数结点都以应请求到了这个数据项.

作者在区块链网络中引入了测量结点，进行了一次实验测量了区块链中的消息传播时延，通过监听inv消息的形式进行测量. 测量结点不负责转发消息，收集区块哈希、广播结点的IP和接收结点的时间戳. 下图展示了所有区块接收到inv消息的时间延迟分布的规范化直方图：

统计得到，结点接收一个区块的时间间隔中位数为6.5s，平均值为12.6s，且在40s后仍有5%的结点收不到区块.

传播消息的大小和传播时延之间的关系非常大. 定义 延迟代价 为每KB区块大小导致的延迟时间. 如下图展示了延迟代价的影响随区块大小变化的曲线

可以看到，小于20kB的区块受到延迟传播的影响是很大的，由于inv和getdata消息的往返延迟，这对小区块是非常大的时间开销. 由此可见，对于小区块而言，直接转发交易消息是一个明智的选择，避免了消息往返带来的传播延迟，但是对于较大的区块则需要进行多跳转发.

当两条使用同一笔输出的交易在网络中传输时，先被某个结点接收到的交易才被视为有效，因为它经过验证传播后达到了同步，第二个到达结点的交易被视为无效而丢弃. 这种设计使得恶意结点很难通过发送数百个矛盾的消息记录淹没网络，但也使得双重花费攻击难以被检测到. 对于这种交易记录，停止传播即可，但是对于传播的区块而言是不可取的，因为存在着某些有效但有潜在的冲突性的区块，不能以任意的速率创建，不会产生攻击的可能性.

【区块链分叉】

根据作者在之前实验中的设计，收集了在180000~190000的区块高度中传播的统计分布直方图，如下所示：

区块的工作量证明机制导致有效的区块可以被独立随机发现，因此在网络中就有可能存在一些交易记录冲突的块被传播. 作者宣称区块链的分叉是由于区块在网络中的传播延迟造成的. 区块 $b$ 在网络中传播的过程中如果找到一个冲突的区块 $b_0$ ，就会发生区块链分叉， $b_0$ 只能被网络中还不知道区块 $b$ 的部分找到.

假设指示函数 $I_j(t)$ 表示结点 $j$ 在时间 $t$ 是否得知区块 $b$ ，则知情结点可定义为

$I(t) = \sum_{j \in V}I_j(t) \\ f(t) = E[I(t)] · n^{-1}$

其中， $f(t)$ 定义为累积分布函数(CDF), 这些结点称为 知情结点，而只有未知情结点才会产生冲突的区块. 综合发现新区块的概率和未知情区块的比例（即网络中的区块分布），我们可以得到区块链分叉的概率.

$Pr[F \geq 1] = (1 - P_b)^{\int_{0}^{\infty} (1-f(t))dt}$

其中， $F$ 是一个随机变量，表示在传播一个区块时，发现冲突区块的数量.

通过提取时间戳，得到区块的发现概率随时间变化的函数呈指数分布规律：

从前文 Figure 3 中得到的直方图，在时刻 t 的知情结点比例即这个直方图曲线到 t 时刻的积分. 从而得到区块链分叉概率：

该模型略高于观测到的的分叉概率 $1.69\%$ ，原因在于我们假设了所有的结点在消息传播过程中呈现出指数分布规律. 随着区块链网络规模的扩大，交易的数量也会随之增加，区块的大小和区块链分叉的概率也随之增大，从而传播延迟也会随之增大. 目前网络中的有效计算能力为 $1-(1 - \frac{11.37}{633.68}) = 98.2\%$ ，如果一个攻击者可以拿到全网络 $49.1\%$ 的算力，就可以修改任意修改交易，这在当前形势下已经几乎不可能达到.

【消息传播加速】

验证过程最简化

传播缓慢的一个原因，在于结点向网络宣布新发现的区块前，需要经过一段时间的验证，这与区块的大小有关. 目前coind协议限制了每个区块大小不超过500kB，但随着时间的推移，交易量会越来越大，这个限制会越来越松.

目前的验证过程分为两个阶段：困难度检查+交易验证. 困难度检查会对接收的区块进行哈希，并将哈希值与当前目标难度进行比较，验证工作量. 此外，还需要对当前区块的交易进行逐条验证. 大部分验证时间在交易验证中，因此，可以考虑在困难度检查完毕之后，就像邻居结点发送inv信息.

如果要伪造一个可以通过困难度验证的区块，难度与发现一个新的区块相当. 因此并不会有遭受DDoS攻击的风险，但这种验证简化过程只对单个路径上的消息传播进行了加速，并不会对网络整体的传播延迟造成很大的影响.

区块传播流水线化

此外，还可以通过将收集到的inv消息立即转发给邻居结点进行消息传播加速，过程如下.

但是这种方法仍是加速了单跳的传播，如果只对一个结点采取进行直接转发inv消息的策略，对于网络整体传播性能的提升也不会有太大的影响.

增大连通性

最有效的方法还是缩短发送交易或区块消息的源结点和其他结点之间的距离，尽可能将网络中任意两个结点进行连接，增大网络的连通性.

测量

通过对结点本身的修改，可以看到区块链分叉的比例下降了非常多，相比于对结点本身不做修改的情况有了一半的提升. 实验结果显示了最后一种方法的加速效果远好于前两种加速方法，但同时对于网络带宽的要求也非常高.

【总结】

本paper分析了比特币网络中消息是如何传播来同步分布式的账本副本. 提出对区块本身的依赖而造成的传播延迟，不仅导致区块链分叉，延迟交易清算，还有利于攻击者. 对此作者提出了一个模型来解释区块链的分叉，并指出它是导致分布账本不一致的问题，但由于信息遮蔽，大多数结点无法检测到分叉的区块. 最后，作者给出了一些结点本身的改进以加速消息的传播，降低区块链分叉的风险，并在实验中验证了这种改进的有效性，但这种方法也不能从根本上解决问题，分叉是比特币的底层原理决定的潜在隐患.

【后记】

这篇paper是目前看的最难的一篇，一方面我对于区块链的了解并不深，因此还需要边读边查，另一方面对相关原理的分析验证十分透彻，公式难度特别大，因此有一些证明推导过程选择了直接跳过. 总的来说，这篇paper的逻辑性十分紧密，对于消息传播、区块链分叉的建模都有严谨的推理过程，因此后续值得重刷精读，对于区块链本身原理的理解十分有帮助. 但是paper提出的改进方案可以看到，并没有对区块链本身做一些很大程度的修改，对于分叉的改进效果也并没有持久性.