Claire: 8月8日，我们做了一个题为『DAG 的前世今生(一)』的主题分享，得到很多朋友的热烈关注和讨论，不少同道中人也因此加入了【魔笛手社区】。今天，主讲嘉宾吴岷先生会继续『DAG 的前世今生(二)』的主题分享，进一步阐述BlockDAG的更多技术细节，难点，解决方法和工具，务求令大家对BlockDAG有更深入的了解，欢迎大家在稍后的Q&A 部分提出问题深入探讨。现在有请吴岷先生……

min : 大家好，我是Min Wu，今天主题分享是解释如何从区块链扩展到区块图。 Github的链接是: https://github.com/soteria-dag/soterd

今天的分享是主要针对开发者的，有不少程序员才懂得俚语（黑话）哦。我尽量用通俗易懂的方式来分享，争取大家都能受益。

上一期Ming Guo讲过了“DAG的前世今生（一）“，链接在这里，https://news.huoxing24.com/20190812204900103888.html，我们快速的回顾一下。

1: Soteria 是“内生去中心化经济体”（SSDE – Self Sustainable Decentralized Economy）的基础设施技术。

2: Soteria正在开发一套整体解决方案，以解决当前一代区块链的一些紧迫问题，同时为其预想的去中心化经济体提供足够的功能集 – 例如基于区块图(blockDAG)的可扩展的吞吐量。

3: DAG 叫作有向无环图。

4: BlockDAG叫做区块图。BlockDAG和TransactionDAG有极大的区别，具体看上期分享中有关交易DAG的部分。

5: Soteria DAG 实际上是比特币中本聪共识算法的扩展，使其具有包容性，并在保证安全性的基础上提供了灵活弹性的可扩展特性。

区块图是长这个样子的：

在这个示例中。 最底部是创世（GENESIS）块，箭头是从一个区块指向它的父辈块（parent）。 如果一个区块不是任何其他的区块的父辈，它（们）就被称为当前区块图的tips。 比如上图中的tips就是M，J和L。Genesis、父辈块(parent)、tips都是很重要的概念，我们接下来会反复提到的。

在包容性的前提下，怎么保证安全性呢？比如恶意挖矿怎么办呢？这里我们就要讲到Phantom 和 Greedy Phantom。

Phantom 是什么？

Phantom 是染色/排序的协议，由Yonatan Sompolinsky 和 Aviv Zohar 发明。它的实现是如下三个主要步骤：

1： 识别出一组连接良好(well-connected)的区块。 这被称为蓝色集合(set)。 其他的区块，比如仅引用较旧的区块，或者自己私藏了一段时间的区块，在很大的概率情况下，会被排除在蓝色集合之外。

2：对区块图进行拓扑排序，优先蓝色集合的区块，滞后不在蓝色集合的区块。

3：在排序核对交易的时候，会使用区块图的排序，合法的交易将会被采用而恶意的交易将会被抛弃。

让我们看看使用Phantom或Greedy Phantom时这个图形的颜色可能是什么样子。

上图显示的是用 Phantom染色以后的结果（Greedy Phantom是类似的），我们是从区块M的角度来看如何染色的。在区块图的中间部分，有一个连接充分(well-connected)的区块集合；同时在区块图的边界处的一些区块(红色的)，它们的连接不是那么充分。

我们使用一个系统内部常量(k)来做这个决定的，k是如何选定的我们会在以后的技术分享中解释。这样就意味着，同样级别的红色集合的区块会排在蓝色集合区块的后面，注意，不是所以的红色的区块都排在所以蓝色的区块后面。没有颜色的区块(J 和 L）不属于M的“过去集合”，它们会被排序在M的后面。

排序结果（从M的角度看）就是：

GENESIS, C, D, E, H, B, I, K, F, M, J, L

在染色和排序的过程中，Phantom 需要：

1：通过分析一个区块的过去(past)和将来(future)来决定是不是充分连接(well-connected)。

2：遍历区块图，为每一个区块染色。

3：排序。

下面我们来看一看什么是Greedy Phantom，作者是Aviv Yaish:

1: 和Phantom的概念基本相同，Greedy Phantom的目标是更简单有效。

2: 染色部分是从最蓝色父辈(bluest parent)继承。

3: 染色和排序是递增模式。

染色部分是从最蓝色的父辈(bluest parent)继承来的，最蓝色的父辈又称为染色父辈(colouring parent)。染色父辈的集合会从当前的区块一直延续到创世块(genesis)，这又叫做当前区块的染色链(colouring chain)。

和Phantom 不同的部分就是，Greedy Phantom的染色是继承的，在一个最蓝色父辈之前的区块的排序是不变的，相反的，在Phantom算法中，由于每一个区块都需要考虑过去(past)和将来(future)，所以每一个区块的颜色在将来都还有可能改变，完全取决于该区块在未来的连接程度。

下面我们看一下在区块被加到区块图的过程中，Greedy Phantom的染色过程。

动图

在这个动画中，除了蓝色、红色、和透明的区块，还有绿色和虚线边界的区块。

绿色的：代表染色的tip

虚线的：当前区块的染色链。（最蓝色的父辈集合）

蓝色的：蓝色区块的集合，是指从最新的区块的角度来看（连接充分的，well-connected)

红色的：在蓝色区块集合以外的区块，从最新的区块的角度来看（连接不是很充分）

可以观察到的是，从最新的区块的角度来看，有一些区块的颜色会改变（在红蓝之间）。还可以观察到的是，当角度不同当时候，染色链也不同。

在DAG最开始当时候，当B、C、D、E被添加当时候，染色链并没有变成这些新的区块。这是因为一个打破平局的内部规则，当两个或两个以上的区块蓝色程度一样(equally blue)，哈希值低的区块胜出。在这个例子中，B是字母中最前（低）的，所以B胜出。

总结一下Phantom和Greedy Phantom之间的计算差异（影响到工程实践上）：

Phantom在染色时，会用到一个区块的过去（past) 和未来 (future)，随着区块图的增长，一个区块的未来会无限增长。

Greedy Phantom只会在染色时考虑一个区块的过去(past)，因为区块图不断的增长，使得Greedy Phantom成为染色/排序在工程实现上更好选择。

如果非要使用Phantom，可以通过设置节点过去和未来遍历的下限和上限来实现类似的效果

但限制节点的过去和未来可能会影响染色效果，所以不太理想。

我们的代码库中包含了两者的实现，目的是未来比较它们的差异，也为其他的开发人员提供更多的借鉴之处。

接下来我具体阐述我们如何对代码进行修改，以达到扩展区块链为区块图的目的。

项目开始以前，我们考察了不少已经开源的区块链项目，最终决定以btcd为基础，在上层做迭代。新的项目名称叫 soterd。Github的链接是: https://github.com/soteria-dag/soterd

工程实现区块图（BlockDAG）包括了如下内容：

修剪已有的代码，去掉只能服务于区块链场景下的代码，还包括不少会使得区块图（BlockDAG）开发复杂化同时又没有太多帮助的代码。

实现核心模块，代表区块图（旧的代码代表的是区块链），提供和区块链模块相同或者类似的服务功能，比如：

找寻tips的功能；

根据已有的区块，找寻父辈区块；

检索指定范围的区块图。

更新了区块的数据结构 （这可是所有区块链项目中最重要的数据结构哦） 。

增加了一个区域可以存储更多的父辈信息，因为在区块图里面，每一个区块可以有多个父辈（比特币只能又一个）。

更新了协议层的编码和解析的方法 (encoding/decoding)

更新及添加了测试(test)

更新了挖矿程序，还有其他有可能遍历区块链/区块图的地方:

增加了新的P2P 和 RPC 调用

getdagtips rpc call

renderdag rpc call

addrcache p2p call

更新了网络同步部分的代码

增加了系统集成测试，

生成区块图（原来是区块链），确认每个区块可以有多于一个父辈区块。

确认区块图可以在不同的全节点同步。

确认可以用挖矿出来的SOTO做交易。

（其实啰里八嗦这一大堆，不写程序的群友只要记住，改公链代码不是容易的事情，对程序员好一些。 :P……程序员朋友，details去看我们的github)

以上的改动是通过几个不同的阶段进行的，主要原因是一次改动量太大，风险太高。我们还开发量很多工具，来帮助理解+分析区块图和故障排除。工具会在后面的内容分享。

我知道大家看了这么久的文字直播，很辛苦，心中的一个大问题就是，"A picture is worth a thousand words"。 小编，你的图呢？？？

图马上就来。

好我们继续……

遇到的挑战：

在项目的开发过程中，需要更新很多的区块链的代码来支持区块图，大体上有三类不同的挑战：

区块链的假设。

已有的代码中，由于系统设计的不同，很多地方缺省假设了是区块链。

点对点 (p2p) 同步。

协议层的编码和解析。

区块链的假设:

部分代码需要重构， 例如，在区块链中，区块的高度(height)是当前区块距离创世区块(genesis)中间有多少个区块。在区块图中，一个区块可以有多个父辈区块，其中一些有可能比 其他人更直接地联系到Genesis。 所以在区块图中，区块的高度现在是父辈区块中的最大高度 + 1。

在上图中，K块的高度，如果通过B的路径，就是2；如果通过C、D、E就是3。 所以我们认为它的高度是3。

孤块 (Orphan block)的处理:

Z-shaped dag

一个孤块是这样的，当一个全节点收到了一个合理的区块，但是又找不到该区块的过去(past)，所以无法连接到现有的区块图上，这个区块就被称为孤块。

在区块链中，孤块是从上往下处理的，从孤块开始，然后是孤块的父辈。在区块图中，这种遍历方式就有问题了，尤其是区块图中有Z形状(Z-saped dag)，一些区块会被忽略掉。我们在这个算法上做了调整，利用深度优先的查找结果排序，从而包括了所有的区块。

（我知道这段话看起很烧脑，你就想，孤儿多可怜呢，当然要区别对待了）

在孤块处理中的重复问题 (knots)

对于区块之间具有高连接性的区块图部分，孤块处理将花费更长时间，因为每一条路径

连接都会被被重新遍历。 我们为此建立了缓存，记录已经处理完成的孤块及其过去(past)。

（也就是说，对孤儿太多的特殊待遇，也会对系统造成影响）

工具：

下面我们介绍一些开发工具，我们在soterd的代码中加入了染色功能，目的是：

1: 帮助检查区块图的实现或者同步问题，能直观的看到区块图，比只能看到日志文件中一组哈希值要有用的多。

2: 为上层应用（比如浏览器）提供接口。

dagviz:

Dagviz : https://github.com/soteria-dag/soterd/tree/master/cmd/dagviz

Dagviz 是一个命令行工具，

它会开启几个soterd的全节点（是的，是全节点），让它们挖矿并且交换区块，并且对结果进行一步一步的记录，你可以回放（通过浏览器）。每一个区块是按照它们的矿工区分颜色，这样很直观的可以看出每一个矿工对网络对贡献。 Dagviz 可以用于展示soterd和区块图，而且可以用来衡量算法的改变对于挖矿公平程度的影响。

min :

(记得哦，dagviz会让几个全节点在你的电脑上跑，所以对CPU的要求不低的）

dagparam 相关链接 dagparam https://github.com/soteria-dag/soterd/tree/master/cmd/dagparam Dagparam 是一个用来探索不同的点对点网络参数的工具。比如targetTimespan和targetTimePerBlock， 以及这些参数如何影响区块图的构成和传播。

Dagparam 是一个用来探索不同的点对点网络参数的工具。比如targetTimespan和targetTimePerBlock， 以及这些参数如何影响区块图的构成和传播。

比如当区块的生成速度超过 62.5blocks/second，就是每16毫秒一个区块的时候，同步的代码就会有不稳定的表现。

soterdash https://github.com/soteria-dag/soterdash Soterdash 是一个web UI, 用来浏览区块图和soterd网络中的全节点。它可以显示全部或者部分区块图，点击每个区块会提供更细节的信息，比如Header, MerkleRoot等等。我们的开发过程中，Soterdash给予了很多帮助，尤其是在问题排查的时候。

Soterdash 是一个web UI, 用来浏览区块图和soterd网络中的全节点。它可以显示全部或者部分区块图，点击每个区块会提供更细节的信息，比如Header, MerkleRoot等等。我们的开发过程中，Soterdash给予了很多帮助，尤其是在问题排查的时候。

最后一个工具了啊，最后的一定是最好的。

go repo sync

我们绝大部分的代码库都是用go写的。Go不允许relative import paths，这使得在不同的fork/copy的代码库之间共享代码变成一个非常复杂的过程。我们的开发过程涉及到多个版本及不同方向的代码共享，所以我们自己开发了这个工具来帮助在不同的代码库之间作同步。它把改变的部分自动转移到目标代码库，同时做必要的改动，比如原来引用旧的代码库的地方，会被替换成新的，其具体步骤如下：

-处理当前项目及其所依赖的前序项目。

-把当前项目及目标项目复制到临时区域。

-用git archive同步当前及目标项目。

-用git rm删除目标项目中不需要的文件。

-把引用文件和链接替换。

-更新go的模块名称。

-把需要的新的文件加入目标项目。

-提交到本地

-提交到目标git tree.

-这个工具现在是在私密的程序库(private repo)，但是我们可以按照需求提供开源。这个项目可以对广大的go 程序员都有帮助。

（重复一下，不光是区块链的程序员，所有go的程序员都有帮助的哦，当然，区块链程序员还有很多不用go的）

感谢大家参与我们今天的分享，技术就是在不断的讨论过程中成长的。今天的分享就到此，下面是问答环节，请提问。

以下是 Q&A 精华节选：

seabook: @min@soteria 今天分享很有深度，你们的经济模型是什么？

min : 哦，那是我们下一次分享的话题：

SSDE (SELF SUSTAINABLE DECENTRALIZED ECONOMY)…You read my mind.

seabook: 请简单提示一下。

min : https://www.ssde.io/ 现在是英文的，分享的内容会是中文的。我们还专门录制过两期podcast，谈论about UBI.

seabook: https://medium.com/bitcoin-is-alien-technology/https-medium-com-bitcoin-is-alien-technology-bitcoin-is-alien-technology-part-1-7c5c82faf552

@min@soteria i enjoy reading your article.

朱江²⁰¹⁹: seabook，你提到的经济模型是指的宏观模型还是微观模型 宏观上如@min@soteria 提到的我们的SSDE proposal 微观上是关于soteria dag本身的生态的 比如奖励机制 incentive design等等 这个我们会在后边的技术分享中涉及。

seabook: incentive design

朱江²⁰¹⁹: seabook， SSDE和soteria 不是UBI 也不是共产主义，仍然崇尚奋斗精神，按劳分配。只不过是对现有中心化的经济系统做了一些去中心化的增强：公平、包容、安全、隐私和可扩容。 incentive design，你也是博弈论的爱好者吧？ 请留意我们后边的分享。

seabook: 会关注的。

Claire: 非常感谢大家的关注，感谢所有转播的平台，欢迎大家稍后继续深入探讨Blockdag 的技术，这次主题分享到此结束。在进行了两个非常硬核的主题分享之后，我们会继续跟大家分享其他跟我们生活息息相关的话题，包括经济，金融，隐私保护，大数据分析，区块链项目的商业模式等等大家非常关心的内容，敬请继续关注后续的主题分享。。。 再次感谢主讲嘉宾吴岷先生的认真准备和细致分享！

特别鸣谢本次主题分享协办社群及媒体（排名不分先后）:

魔笛手技术开发社区

新通证经济无名高地

数字万物讨论群

国际社区&原子区块链ATOS

Metamask中文社区

盗火者区块链应用联盟

⑦月线下线上社群

算力社区1901

加密数字货币与区块链生态系统

清华校友区块链技术探索者

Defi 研究院 成都

散落在世界各地的龙珠们