树图区块链说明

背景

最近在寻找提高区块链交易TPS的方案。 我注意到目前有一种DAG结构可以实现并发出块来提高交易TPS。 这里发现Conflux项目的树图区块链采用的是DAG结构。 这里说明方案的出发点和解决方案。

为什么相关描述是完整的顺序？

所谓交易全序，是指所有节点上的交易顺序是确定的、一致的。 比如A有10个币，转7个币给B，转5个币给C，如果这两笔交易的顺序不确定，得到的结果也是不确定的，这在比特币上是不允许的。

比特币中的几种安全攻击双花问题

假设 A 想同时给 B 和 C 同一笔交易，即把同一枚币花两次，这称为双花问题。 双花有三种可能：

第一种可能是让 A 验证一个包含两笔相同交易的区块。 假设A有1%的算力，那么A可能有幸验证这个区块。 但是，这种双花会立即被其他节点发现并验证并拒绝。 A虽然解决了工作量证明的问题，但是区块无法在链上得到确认。

在第二种可能性中，A 试图分别公布两笔交易。 A可能向部分矿工发布一笔交易，向另一部分矿工发布另一笔交易，A希望两笔交易都得到验证。 在这种情况下，由于交易是有序的，一笔交易完成后，另一笔交易将被其他节点拒绝，网络最终只会确认其中一笔交易。 所以这不是问题。

第三种可能，A=B，也就是说A想给C一个币，同时A把那个币给A自己，因为A可以有多个账户。 在这种情况下，A的策略是等到C接受比特币，即交易在最长的区块链中被确认6次之后。 然后 A 尝试解析另一个区块分支，该分支有 A 发送给他的交易。但是，此时 A 落后于最长的区块链 6 步。 A 很难跟上最长的分支。 其他正常的挖矿节点不会帮助A，因为他们都需要在最长的分支上工作才能获得奖励。 除非 A 能够比网络上其他节点的组合更快地解决工作量证明（即 A 拥有全网 50% 以上的算力）。 当然，A可能运气好，可以用百分之一的算力解决一个块，但是如果他同时赶上6个块，就相当于1/100^6。 这种情况出现的概率可以说几乎为0。

分叉问题

两个矿工几乎同时挖出区块，此时区块链上会产生一个分支。 它们将同时向网络公布，一些节点在 A 分支上更新它们的区块链，而其他节点在 B 分支上更新它们的区块链。

在这种情况下，交易就会乱序，谁拥有哪个比特币就不清楚了。 比特币消除分支的规则是这样的：如果出现分支情况，那么网络上的节点继续维护两个分支。 无论如何，矿工只在最长的区块链上工作。

有些矿工先收到区块 A，有些矿工先收到区块 B。 那些收到区块 A 的矿工会继续沿着 A 的分支挖矿，而其​​他矿工则在 B 区块的分支上挖矿。假设 B 分支上的矿工先挖到下一个区块：

当矿工收到这个消息后，A分支的矿工会注意到B分支现在最长，所以他们会切换到B分支。 A 分支上的工作将很快停止，这样矿工们将在同一个顺序区块链上工作。 然后块 A 将被忽略。 当然，所有在A区块中的未决交易会继续保持pending状态比特币分叉最大的风险是双花，然后它们会被放到B分支上的一个新区块中，这样所有的交易最终都会被验证。

同理，如果A分支的矿工先挖出下一个区块，那么B分支的矿工就会停下来前往A分支。

这个过程保证了区块链有一个统一的顺序。 在比特币中比特币分叉最大的风险是双花，一笔交易只有在： a，它存在于最长分支的区块中； b、至少有5个验证块在它之后被验证。 在这种情况下，我们称此交易为“6 次确认”。

chained total order Blocks不能并发导致的问题

由于矿工同时挖出区块，一个分支区块会被丢弃，导致无法并发出块，进而导致比特币的TPS非常低，一般为每秒几笔交易。 比特币想要提高交易频率。 有两种方法： 增加每个区块包含的交易数量； b. 提高区块生成速度。

这两种方法将导致： a． 区块增加，网络传播时间变长； b. 区块生成时间变短。 这意味着一个新的区块产生后，来不及传播到全网，其他节点会产生另一个新的区块，于是区块链上产生了分叉。 虽然整个系统最终会收敛到某个最长的分叉，但是出块率和区块大小越大，分叉就会越严重，分叉会进一步出现在现有的分叉上，所以最后会有很多分叉.

这带来了两个问题。 首先，这些分叉浪费了网络和计算资源，因为只有最长链中的区块才被认为是有效的。 其次，它损害了安全性，因为整个区块链中最长的链变得更短，这使得攻击者可以生成恶意的最长链，其计算能力不足 50%。

树状图的解决方法

treemap区块链需要解决总交易顺序、安全性（50%算力攻击）、增加交易频率三个问题。

如何实现全序？

首先，让我们了解一下树图的结构。 树图的实现主要是通过父边和参考边来构造。 如上图所示，每个块都有一个指向其父块的父边，每个块也可以有多个参考边。 这个参考边主要是记录和表达块之间的顺序。 例如，当节点生成区块 E 时，区块 D 已经存在于链上，此时 D 没有任何其他区块引用它。 那么这个节点可以在E上添加一条引用D的边，表示D先于E生成。

首先，这些节点先在树图中确定一条一致的主链，然后根据这条主链确定一个一致区块的总序。

为了确定主链，使用了 Ghost 规则。 具体来说，从创世块开始，从子块中迭代选择主链上的下一个块。 选择规则是选择具有最大子树的子块。 例如，区块 A 和区块 B 是创世区块的两个子区块。 A的子树有6个块，B的子树有5个块。 所以我们选择区块A作为创世区块之后的主链区块。 相应地，我们按照相同的规则将区块C、E、H选入主链。 如下所示：

为了产生一个新的区块，一个机器节点首先选择主链上的最后一个区块作为新区块的父区块，然后新区块引用所有已经接收但还没有被其他区块引用的区块站起来。 这里之所以使用Ghost规则而不是最长链规则来选择主链，是因为Ghost规则中的所有区块，包括分叉上的区块，都会对主链的选择做出贡献。 这样就保证了只要攻击者的算力不超过50%，诚实节点确定的主链就不能被改变。

现在我们有了一个所有机器节点在主链上产生共识的机制。 那么，这些节点如何就区块的总顺序达成共识呢？ 为了做到这一点，引入了 Epoch 的概念。 主链上的每个区块决定一个 Epoch。 分叉上的区块属于哪个Epoch，由其之后生成的第一个主链区块所在的Epoch决定。 比如区块D属于Epoch E，因为D首先被E引用，所以它先于E生成，但D并没有先于C生成。

首先，按照 Epoch 的顺序对块进行排序。 然后在每个Epoch内，根据拓扑排序确定区块的顺序。 如果平局，则根据区块的哈希值打破平局。 然后在每个区块内，根据交易在区块中的位置对交易进行排序，从而实现交易的总排序。 如下所示：

如何确保安全？

双花问题

和比特币一样，双花也有三种可能。

第一种可能是将同一笔交易放入同一个区块。 这个区块会被其他节点验证，后面的重复交易将无效。

第二种可能是将同一笔交易放到不同的区块中，同一后面区块中的交易会被其他节点验证，如果不能通过则作废。

第三种可能就是我们提到的算力攻击。 具体来说，如果攻击者想要撤销账本中的一笔交易，比如交易 Tx4。 为此，攻击者需要生成一笔交易Tx4的双花交易，打包成一个区块，并将该区块插入到区块总序中的区块B的前面。 但是攻击者很难做到这一点，主要有两个原因：

分叉问题

树状图允许区块分叉，即允许区块并发产生，保证交易的总顺序。 在不影响安全性的情况下提高交易频率。

树形图如何提高交易速度？

区块可以并发产生，分叉区块不会被丢弃。 并保证交易的总秩序。 在不影响安全性的情况下提高交易频率。

树状图的缺点

每个节点维护图的信息比链式结构要复杂得多。

目前的联盟链PBFT共识是否可以借鉴？

比特币和Treemap都是公链，采用工作量证明机制，通过上述方式实现交易的完全有序和安全。 通过改变链的结构，树状图使得区块可以并发产生，提高了交易TPS。

POW共识可以让更多的节点参与进来，可以更好的实现去中心化，但问题是TPS上不去。 PBFT通过算法实现交易的全序和一致性，可以提高交易TPS，但一般只能在联盟链中使用，因为参与的节点太多，对P2P网络的压力会比较大。 Facebook 的 Libra 项目使用 BFT 共识算法来提高 TPS。 树状图也提供了提高TPS的解决方案。

PBFT采用三阶段的方式来保证交易的完整顺序。 最后的commit阶段保证所有非故障节点提交的数据一致，按照commit中的批量数据生成块，不产生块分叉。 PBFT 共识的性能瓶颈是三级网络通信和签名验证的压力。

通过以上分析可以看出，使用树状图并不能有效提高PBFT共识区块链网络的TPS。