Claire: 8月8日，我们做了一个题为『DAG 的前世今生(一)』的主题分享，得到很多朋友的热烈关注和讨论，不少同道中人也因此加入了【魔笛手社区】。今天，主讲嘉宾吴岷先生会继续『DAG 的前世今生(二)』的主题分享，进一步阐述BlockDAG的更多技术细节，难点，解决方法和工具，务求令大家对BlockDAG有更深入的了解，欢迎大家在稍后的Q&A 部分提出问题深入探讨。现在有请吴岷先生……
今天的分享是主要针对开发者的，有不少程序员才懂得俚语（黑话）哦。我尽量用通俗易懂的方式来分享，争取大家都能受益。
上一期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。
工程实现区块图（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/dagvizDagviz 是一个命令行工具，
它会开启几个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的）