DAG原理解析

DAG数学基础
定义：在有向图G=(V,E)中，对于任意一个顶点v∈V，都不存在一条路径p=(e1,e2,…),ei∈E，使得从v开始出发到v终止，则G称为有向无环图（DAG, Directed Acyclic Graph）

在图论中，相比于一般图，DAG的很多问题可以在多项式级甚至线性复杂度条件下得到求解。DAG具有以下几条数学性质：
l DAG具有拓扑顺序，即DAG的所有节点可以转换为节点序列（线性化），使得每条边的起始节点位于终止节点之前，且该过程可以在线性复杂度条件下完成；
l DAG中相互连通的节点可以进行排序，如果从节点u出发可到达节点v，则可称为u≤v；
l DAG具有唯一的传递闭包；
l DAG具有唯一的传递规约，传递规约的边数最大不超过V−1条，V是DAG的节点数；
l DAG中给定两个节点，其最短路径和最长路径可以在线性时间内求解。
DAG常用来做任务的调度规划，比如Spark在做并行处理时使用DAG来任务规划，Git采用DAG来做版本管理。DAG在区块链上的应用可以参考《DAG也许是真正的区块链3.0》，下面将对使用DAG作为区块链的Dagx原理进行详细的解析。
Dagx的区块链结构
DagX的产品原型是Byteball，此处对dagx的阐述同样适用byteball，Dagx区块链如上图所示，其基本组成为单元(unit)，所有单元共同构成DAG。其中，单元G为创世交易，它与所有单元连通，且是从所有单元出发到达的终点。
l 父单元与子单元：从单元A出发可直接到达单元B，即单元A到单元B的路径长度为1，则单元B称为单元A的父单元，单元A称为单元B的子单元。
l 直接包含：如果单元A为单位B的子单元，则单元A直接包含或者验证了单元B。
l 间接包含：如果从单元A出发到达单元B的路径长度大于1，则单元A间接包含或者验证了单元B。
l 顶端单元：不具有任何子单元的单元，也可称为无子单元或未经验证的单元。
l 创世单元：由创世交易构成的单元，不具有任何父单元。
相比于Bitcoin中一对一的链式区块结构，Dagx中单元在发出时，可以同时包含多个父单元，因此可以容纳更多的交易并获得更快的确认。由于进入DAG的单元将被所有与其连通的单元直接或间接地验证，如果要修改该单元的内容，则需要相应地修改验证了它的所有单元。直观上来讲，将要修改的单元数量（归属于不同的用户）像滚雪球一样急速增加，从而使得修改无法实现，这也是DAG可以作为区块链的重要基础。
单元的结构如下所示，其主要由三部分组成：

[*]
单元数据：数据以message的形式构成；

[*]
地址签名：输入所需的相应地址签名；

[*]
父单元：当前单元的父单元列表。

从中可以看出Dagx采用的交易模型是UTXO，即当前交易输出作为后续交易的输入。所有bytes是在创世交易中发出，因此Dagx本质上就是一种完全预挖的币。bytes可用于支付手续费，或在地址之间相互传输。
{
version: ‘1.0’,
alt: ‘1’,
messages: [ {
app: ‘payment’,
payload_location: ‘inline’,
payload_hash: ‘AegecfpDzh8xvdyIABdynrcP6CTd4Pt42gvRiv0Ftjg=’,
payload: {
inputs: [{
unit: ‘7yctnKyuAk5P+mFgFQDdDLza88nkceXYjsTs4e3doQA=’,
message_index: 0,
output_index: 1
} ],
outputs: [
{ address: ‘DJ6LV5GPCLMGRW7ZB55IVGJRPDJPOQU6’, amount: 208 },
{ address: ‘Z36JFFX2AH7X5JQ2V2C6AQUUOWFESKZ2’, amount: 3505 }
] }
} ],
authors: [ {
address: ‘DJ6LV5GPCLMGRW7ZB55IVGJRPDJPOQU6’,
authentifiers: {
r: ‘3eQPIFiPVLRwBwEzxUR5thqn+zlFfLXUrzAmgemAqOk35UvDpa4h79Fd6TbPbGfb8VMiJzqdNGHCKyAjl786mw==’
}
} ],
parent_units: [
‘B63mnJ4yNNAE+6J+L6AhQ3EY7EO1Lj7QmAM9PS8X0pg=’,
‘D6O1/D9L8vCMhv+8f70JecF93UoLKDp3e2+b92Yh2mI=’,
‘ZxqzWP6q6hDNF50Wax8HUK212lH/KSIRdW5a6T9h3DM=’
],
last_ball: ‘8S2ya9lULt5abF1Z4lIJ4x5zYY9MtEALCl+jPDLsnsw=’,
last_ball_unit: ‘bhdxFqVUut6V3N2D6Tyt+/YD6X0W+QnC95dMcJJWdtw=’,
witness_list_unit: ‘f252ZI2MN3xu8wFJ+LktVDGsay2Udzi/AUauE9ZaifY=’
}
当某个单元达到稳定之后，就可以生成球(ball)，此时它的状态（是否有效）将确定性的固定下来，球的结构如下所示：
{
unit: “hash of unit”,
parent_balls: [array of hashes of balls based on parent units],
is_nonserial: true, // this field included only if the unit is nonserial
skiplist_balls: [array of earlier balls used to build skiplist]
}
单元的结构中还包括见证人列表单元，这是为了节省存储空间，表示当前单元的见证人列表与其相同。关于球、见证人我们再后续解析共识算法时会详细讨论到。
Dagx的共识算法
主链
在Dagx中，从任何一个顶端单元出发到达创世单元的最优路径称为候选主链（Candidate Mainchain）。最优路径通过选择最优父单元产生，选择策略用于保证整个网络的安全性。不同的候选主链会在某个单元位置交叉（最差的情况是在创世单元交叉），该交叉点称为稳定点（Stable Point）。对于所有候选主链，从稳定点到创世单元的路径完全相同，该路径称为稳定主链（Stable Mainchain）。稳定主链是一条确定的路径，从候选路径变为稳定主链是一个从不确定逐渐变成确定的过程。后续讨论中，如果没有明确区分，主链一般指的是候选主链。

DAG中的每个单元要么直接位于主链上，要么经过较短的路径就能到达主链，主链可以形象地看作是一条连接着许多侧面道路的高速公路。一个单元一旦进入DAG中，它所在的主链也相应确定，因为后续单元只能作为其子单元，而无法更改其父单元。
给定一条主链，与之相关的所有单元均可以在此基础上进行排序，其序号称为主链序号（MCI, Main Chain Index）。创世单元的MCI为0，依次加1直到链尾。对于不在主链上的单元，其MCI等于主链上最先包含（直接或者间接）该单元的那个单元的MCI。MCI代表了从主链视角来看单元在DAG中的总序，对于发生冲突的双花交易，MCI较小的单元为有效单元。
最优父单元的选择策略
• 单元级别：由当前单元出发至创世单元的最长路径长度定义为单元级别（unit level）
• 见证级别：从当前单元开始沿主链回溯，并对路径中不同见证人进行计数（相同见证人只计数1次），当遇到的见证人数足够多时（超过大多数的已知见证人）停止回溯；然后计算停止位置的单元级别，将其称作当前单元的见证级别（witnessed level）。
最优父单元的选择策略由以下三部分组成：

[*]
在选择最优父单元时，见证级别最高的父单元为最优父单元；

[*]
如果见证级别相同，则单元级别最低的作为最优父单元；

[*]
如果两者都相同，则选择单元哈希值（base64编码）更小的作为最优父单元。

那么，从顶端单元出发，只需要递归地在其父单元中选取最优父单元即可形成主链。在上述选择策略中，见证人成为了某个单元看待历史的视角，每个单元可以维护自己的见证人列表，也可以通过witness_list_unit引用其它单元的见证人列表。
• 单元兼容：如果两个单元的见证人列表差别最多一项，则称这两个单元兼容
在选择最优父单元时，仅可以从与当前单元兼容的父单元中进行选择，以保证看待历史视角的连续性。不兼容的父单元仍然被承认，但是他们不能成为最优父单元。特别地，在发出新单元时，如果与所有顶端单元都不兼容，则应从上一级别的父单元中进行选择。
双花问题
在用户地址发出新单元时，要求相同地址发布的所有单元应当直接或间接包含该地址之前所有的单元，即相同地址的所有单元连通（有序或连续）。
双花交易：相同地址发出的任何无序的交易都视为双花交易，即使它们没有使用相同的输出，也可称为冲突交易或者矛盾交易。
因此，在相同地址的所有单元都连通的情况下，在路径上出现较早的交易为有效交易。如果有攻击者特意制造出双花交易，那么可以通过主链序号来解决，主链序号较小的交易为有效交易。

上图给出了一种攻击场景，攻击者制造出一条影子链，并在上面发布双花交易。当影子链接入到真实的DAG中时，根据最优父单元选择策略，影子链上的见证人个数少，因此它不会成为主链的一部分，从而解决了这种场景下的双花问题。值得注意的是，如果大多数见证人与攻击者合谋，并在其影子链上发布单元，则攻击者有可能攻击成功。
单元成为稳定点的条件
根据上面的分析可知，所有候选主链在稳定点之后到达创世单元的路径完全相同，即稳定主链成为最终状态。这也意味着，从稳定主链上单元直接或间接包含的那些单元也将无法再被篡改。因此，只要随着新单元的不断加入，稳定点可以不断地向后扩展，且不同的用户节点的稳定点扩展方式保持一致，则全网的所有用户节点可以实现共识。
对于所有单元，如果只保留其与其最优父单元的连接，则DAG将退化为一棵树T，所有的候选主链只可能从这棵树中产生。下面根据稳定点是否具有多个子单元分两种情况对稳定点的扩展方式进行讨论。
当前主链：在DAG中，从不同顶端单元出发具有不同的候选主链，从见证级别最高的顶端节点出发的候选主链称为当前主链（Current Mainchain）。

假设当前稳定点的见证人列表为W，单元级别为l，它只有一个子单元，如上图所示。以W作为见证人列表，从当前主链的顶端节点进行回溯，直到遇见W中的大部分见证人，记录这些见证人发出的单元中的最小见证级别，记作minwl。如果minwl>l，则扩展当前稳定点至其子单元，否则不进行扩展。由于大部分见证人已经在当前主链上了，后续这些见证人发布的单元将继续支持当前路径，从而使得稳定点可以向前扩展。

假设当前稳定点具有多个子单元，如上图所示。在当前稳定点的所有子单元中（除了位于当前主链的子单元），找出见证级别大于当前稳定点的子单元，并将其中最大的单元级别记为maxl。也就是说，除了当前主链外，当前稳定点其它分支上的单元见证级别将不超过maxl。如果minwl>maxl，那么稳定点可以沿当前主链向前扩展。
随着稳定点的不断前进，稳定主链及其相关单元的状态被最终确定下来。只要DAG中的单元相同，其形成的主链和稳定点也是相同的。因此，不同的用户节点，只要最终收到相同的单元，它们最终将达到一致的状态。
Dagx的地址、脚本及合约
地址的定义
Dagx中用户使用地址进行收发交易。地址本质上对应的是一段具有特定含义的脚本，该脚本称为地址的定义。任何能够使地址定义脚本输出为真（也称作解锁该脚本）的人具有使用该地址资产的权限。与Bitcoin类似，最常用的地址定义脚本是公钥（采用BASE64编码），即具有相应私钥的人可以使用该地址的资产，比如
[“sig”,{“pubkey”:“Ald9tkgiUZQQ1djpZgv2ez7xf1ZvYAsTLhudhvn0931w”}]
对于地址定义脚本进行哈希，再加上校验位就得到了地址，Dagx的地址采用BASE32编码。Dagx地址的校验位并不是全部放在尾部，而是穿插着放在哈希值中间，防止有攻击者在地址中间进行恶意修改。

按照此流程，上面公钥脚本对应的地址为：
A2WWHN7755YZVMXCBLMFWRSLKSZJN3FU
如果地址仅用于接收交易，其定义脚本可以不对外公布。但是当用户首次使用该地址进行发送交易时，他需要在发送的单元中声明该地址的定义脚本，比如
unit: {
…
authors: [ {
address: ‘DJ6LV5GPCLMGRW7ZB55IVGJRPDJPOQU6’,
definition: [
“sig”, {“pubkey”:“AsnvZ3w7N1lZGJ+P+bDZU0DgOwJcGJ51bjsWpEqfqBg6”}
],
authentifiers: {
r: ‘3eQPIFiPVLRwBwEzxUR5thqn+zlFfLXUrzAmgemAqOk35UvDpa4h79Fd6TbPbGfb8VMiJzqdNGHCKyAjl786mw==’
}
} ],
…
}
其中，authentifiers是用户采用私钥对除authentifiers之外的数据进行的签名。在用户使用该地址首次发送单元之后，它不允许再发送地址的定义。当然，只有在该地址的第一个单元到达稳定后，用户才可以发送后续单元。
用户可以在保持地址不变的条件下修改地址的定义脚本，用户需要发送消息
unit: {
…
messages: [
…
{
app: “address_definition_change”,
definition_chash: “I4Z7KFNIYTPHPJ5CA5OFC273JQFSZPOX”
},
…
],
…
}
definition_chash为新的地址定义脚本生成的地址。那么，下一个从原地址发出的单元有以下两条要求：

[*]
必须把address_definition_change这个单元作为其last_ball；

[*]
在修改地址定义脚本后发出第一个单元时，需要把新的定义脚本作为第一条message。

显然，新的地址定义脚本生成的地址跟原地址是不相同的。当用户迁移到新的设备上，同时想保持地址不变时，可以使用这种方式来修改地址定义脚本。
地址定义脚本中必须显式地（使用sig）或隐式地（使用address）包含至少一个sig。为了防止消耗过量的资源，脚本的操作总数限制在100以内，包括授权地址及脚本模板中的所有操作。
相比于Ethereum，Dagx的脚本语言的解释能力有限，它定义的几乎都是逻辑判断语句。但是，Dagx本身是为了提供给那些并不太懂编程的人群使用的，其语言必须便于理解且不容易出错。
逻辑运算脚本
与运算：当多个条件同时满足时，脚本输出为真。比如，同时需要两个私钥签名的脚本
[“and”, [
[“sig”, {pubkey: “one pubkey in base64”}],
[“sig”, {pubkey: “another pubkey in base64”}]
]]
或运算：多个条件中有一个满足时，脚本输出为真。比如，仅需要laptop、smartphone或者talet中某一个私钥就可以解锁的脚本
[“or”, [
[“sig”, {pubkey: “laptop pubkey”}],
[“sig”, {pubkey: “smartphone pubkey”}],
[“sig”, {pubkey: “tablet pubkey”}]
]]
非运算：脚本中不含sig、hash、address、cosigned by或者in merkle的条件可以进行非运算，比如
[“not”, [
“in data feed”,
[[“NOAA ADDRESS”], “wind_speed”, “>”, “200”]
]]
逻辑嵌套：逻辑运算可以嵌套使用。比如，必须同时拥有smartphone私钥以及laptop或者tablet中某一个私钥就可以解锁的脚本
[“and”, [
[“or”, [
[“sig”, {pubkey: “laptop pubkey”}],
[“sig”, {pubkey: “tablet pubkey”}]
]],
[“sig”, {pubkey: “smartphone pubkey”}]
]]
最小数量运算：当满足条件的个数超过门限时，脚本输出为真。比如，具有2个以上私钥就可以解锁的脚本
[“r of set”, {
required: 2,
set: [
[“sig”, {pubkey: “laptop pubkey”}],
[“sig”, {pubkey: “smartphone pubkey”}],
[“sig”, {pubkey: “tablet pubkey”}]
]
}]
最低权重运算：当满足条件的权重值超过门限时，脚本输出为真。比如，当几个私钥签名的权重之和大于50时可以解锁的脚本
[“weighted and”, {
required: 50,
set: [
{weight: 40, value: [“sig”, {pubkey: “CEO pubkey”}] },
{weight: 20, value: [“sig”, {pubkey: “COO pubkey”}] },
{weight: 20, value: [“sig”, {pubkey: “CFO pubkey”}] },
{weight: 20, value: [“sig”, {pubkey: “CTO pubkey”}] }
]
}]
地址授权脚本
授权使用其它地址来解锁脚本，其定义的语法为
[“and”, [
[“address”, “ADDRESS 1 IN BASE32”],
[“address”, “ADDRESS 2 IN BASE32”]
]]
这可以很方便地用来构造共享控制的地址。比如，上面给出的地址定义脚本生成的地址将由ADDRESS1和ADDRESS2共同控制。
共同签名脚本
要求与另一个地址共同签名才可以解锁脚本
[“cosigned by”, “ANOTHER ADDRESS IN BASE32”]
地址已用脚本
要求由某个地址发出的单元至少有一个成为last_ball_unit
[“seen address”, “ANOTHER ADDRESS IN BASE32”]
数据订阅脚本
通过订阅的数据是否符合条件来解锁脚本，其语法格式为
[“in data feed”, [
[“ADDRESS1”, “ADDRESS2”, …],
“data feed name”,
“=”,
“expected value”
]]
上述脚本表示：当数据源地址ADDRESS1、ADDRESS2等中某个地址发出的消息中订阅数据data feed name等于expected value时，脚本输出为真。
地址发出的数据订阅消息格式为
unit: {
…
messages: [
…
{
app: “data_feed”,
payload_location: “inline”,
payload_hash: “hash of payload”,
payload: {
“data feed name”: “value”,
“another data feed name”: “value2”,
…
}
},
…
],
…
}
对赌合约
当某个地址可以作为可靠的数据订阅源时，用户可以使用其作为外部数据条件来构造合约。比如，
[“or”, [
[“and”, [
[“address”, “ADDRESS 1”],
[“in data feed”, [[“EXCHANGE ADDRESS”], “EURUSD”, “>”, “1.1500”]]
]],
[“and”, [
[“address”, “ADDRESS 2”],
[“in data feed”, [[“TIMESTAMPER ADDRESS”], “datetime”, “>”, “2016-10-01 00:00:00”]]
]]
]]
上述脚本给出了ADDRESS 1和ADDRESS 2之间的一个简单合约，假设其对应的地址为ADDRESS X。当EXCHANGE ADDRESS发布的汇率数据EURUSD大于1.1500时，仅使用ADDRESS 1的私钥就可以取走ADDRESS X中的资产。而当TIMESTAMPER ADDRESS发布的时间数据datetime大于2016-10-01 00:00:00时，仅使用ADDRESS 2的私钥就可以取走ADDRESS X中的资产。也就是说，上述脚本定义的是对赌合约：如果2016-10-01 00:00:00之前EURUSD汇率超过1.1500，地址ADDRESS 1获胜，否则地址ADDRESS 2获胜。
商品合约
当顾客购买商品时，也可以使用上述方式来制定合约，比如
[“or”, [
[“and”, [
[“address”, “MERCHANT ADDRESS”],
[“in data feed”, [[“FEDEX ADDRESS”], “tracking”, “=”, “123456”]]
]],
[“and”, [
[“address”, “BUYER ADDRESS”],
[“in data feed”, [[“TIMESTAMPER ADDRESS”], “datetime”, “>”, “2016-10-01 00:00:00”]]
]]
]]
上述脚本给出了顾客BUYER ADDRESS和商户MERCHANT ADDRESS之间的合约，假设其对应的地址为ADDRESS Y。顾客在购买商品时，将款项打入地址ADDRESS Y。如果快递公司FEDEX ADDRESS发布数据表明相应的快递已签收，则商户MERCHANT ADDRESS可以从ADDRESS Y中取走货款；如果TIMERSTAMPER ADDRESS发布的时间数据datetime大于2016-10-01 00:00:00时，则顾客BUYER ADDRESS可以从ADDRESS Y中取回货款。
上述场景中，快递公司需要对每一个快递都发布其签收状态数据，这将需要发布大量的数据。Merkle数据订阅可以降低需要发布的数据量。只需要核实关心的hash值出现在数据源地址发布的Merkle树中时，即可证明该事件已发生。其定义语法如下：
[“in merkle”, [
[“ADDRESS1”, “ADDRESS2”, …],
“data feed name”,
“hash of expected value”
]]
此时，快递公司只需要定期将一大批快递状态构造Merkle树，并发布Merkle根即可。商户可以通过相应快递的Merkle路径来解锁Merkle数据订阅的脚本。
单元约束脚本
脚本可以对相应地址发出的单元数据进行约束，其定义格式为：
[‘has’, {
what: ‘input’|‘output’,
asset: ‘assetID in base64 or “base” for bytes’,
type: ‘transfer’|‘issue’,
own_funds: true,
amount_at_least: 123,
amount_at_most: 123,
amount: 123,
address: ‘INPUT OR OUTPUT ADDRESS IN BASE32’
}]
上述脚本要求单元至少有一个输入/输出满足后续定义所有的条件。特别地，可以使用has one来强制要求有且仅有一个输入/输出满足后续所有条件。
其它类似的约束还有求和约束，要求输入/输出之和满足特定条件，其格式为
[‘sum’, {
filter: {
what: ‘input’|‘output’,
asset: ‘asset or base’,
type: ‘transfer’|‘issue’,
own_funds: true,
address: ‘ADDRESS IN BASE32’
},
at_least: 120,
at_most: 130,
equals: 123
}]
交易合约
单元约束脚本可以用来实现去中心化交易。假设用户USER ADDRESS希望使用不高于1000bytes的价格购买1200units的其它资产。用户可以发送1000bytes至如下脚本定义的地址上：
[“or”, [
[“address”, “USER ADDRESS”],
[“and”, [
[“address”, “EXCHANGE ADDRESS”],
[“has”, {
what: “output”,
asset: “ID of alternative asset”,
amount_at_least: 1200,
address: “USER ADDRESS”
}]
]]
]]
或逻辑or的第一个条件表明，在未成交之前，用户可以随时取回他的1000bytes。或逻辑or的第二个条件表明，其他用户可以使用EXCHANGE ADDRESS地址私钥来取走着1000bytes，只要他同时在同一单元中将1200units其它资产输出到USER ADDRESS。通过这种方式，用户之间可以实现不同资产之间的交易。
借贷合约
单元约束脚本还可以用来实现抵押借贷。假设借款人抵押某种资产借贷10000bytes，那么借款人和借贷人可以共同签名一笔交易，其中借贷人将bytes发送给借款人，同时借款人将抵押资产转入以下脚本定义的地址上：
[“or”, [
[“and”, [
[“address”, “LENDER ADDRESS”],
[“in data feed”, [[“TIMESTAMPER ADDRESS”], “datetime”, “>”, “2017-06-01 00:00:00”]]
]],
[“and”, [
[“address”, “BORROWER ADDRESS”],
[“has”, {
what: “output”,
asset: “base”,
amount: 10000,
address: “LENDER ADDRESS”
}]
]],
[“and”, [
[“address”, “LENDER ADDRESS”],
[“address”, “BORROWER ADDRESS”]
]]
]]
上述脚本包括了三层含义：

[*]
当时间超过2017-06-01 00:00:00时，借贷人可以取走抵押资产；

[*]
当借款人归还10000bytes至借贷人地址LENDER ADDRESS时，借款人可以取回抵押资产；

[*]
借贷人和借款人可以协商解除合约。

脚本模板
通过预先设定的脚本模板可以很方便地定义脚本，只需要对模板中的参数进行修改即可
[“definition template”, [
“hash of unit where the template was defined”,
{param1: “value1”, param2: “value2”}
]]
脚本模板需要在单元中发送app=’definition_template’的消息，并且需要单元到达稳定状态后，脚本模板才可以使用。消息内容与普通的地址定义脚本相同，参数使用@param1及@param2表示。
Dagx的网络结构
从节点功能角度来讲，Dagx网络节点可以分为中继节点（Relay）、中枢节点（Hub）、播报节点（Oracle）、见证人节点（Witness）、钱包节点（Wallet）：
中继节点（Relay）：负责向与其连接的节点转发单元，存储整个Dagx区块链数据库，但它本身不保存任何私钥，也不发送任何单元；
Hub节点（Hub）：负责为连接到它的设备提供端到端的加密消息传输通道，用于比如收发私密资产、多签名交易、聊天信息等，其它功能与中继节点相同，默认的Hub地址为wss://Dagx.org/bb；
播报节点（Oracle）：负责不间断地向Dagx网络播报数据，数据可以是时间、价格、甚至是Bitcoin交易；
见证人节点（Witness）：负责不间断地以固定地址发送单元，任何满足该条件的节点都有可能成为见证人；
钱包节点（Wallet）：负责与用户交互，收发交易、消息等。
下图给出了Dagx网络结构的示意图：

轻节点及其验证过程
从是否存储了完整的区块链数据角度来讲，节点也可以分为全节点和轻节点，全节点保存了完整的区块链数据，而轻节点没有。用户在安装钱包时可以选择是使用全节点还是轻节点。轻节点仅存储与其地址相关的那些单元，它需要从全节点上下载所需要的数据，请求条件包括它信任的见证人列表以及它关注的地址。
跳跃列表：假设直接位于主链上的球的MCI为i，如果imod10=0，则该球具有跳跃列表（skiplist_balls），跳跃列表中的值指向之前的球；对于i尾数具有的每一个0，跳跃列表中都有一个MCI值与之对应；跳跃列表中的MCI值等于在保持尾数0个数相同的情况下最接近i的MCI，比如i=3000时，对应的跳跃列表为[2990,2900,2000]。
跳跃距离：对于跳跃列表中的MCI值，它与当前球的MCI值的差值称为跳跃距离。
最近的球：当前节点已知的距离当前时刻最近的球（last_ball），每个单元在发送时必须包含其已知的最近的球。
全节点接收到轻节点发送的见证人列表和关注地址，在其存储单元的数据库中搜索与轻节点关注地址相关的单元。同时，对于每一个相关的单元，全节点构造一条证据链，构造方法如下：

[*]
沿着主链回溯，当已收集到轻节点给定见证人列表中的绝大部分见证人时停止（这是寻找见证人的过程），记录这些主链上的单元，记作单元集合C；

[*]
选择单元集合C中时间最早的单元（也是MCI最小的单元），获取其last_ball；

[*]
从last_ball这个单元开始沿着主链回溯，直至遇见包含skiplist_balls的球停止，记录这些主链上的球，记作球集合B；

[*]
使用skiplist_balls继续沿主链回溯，跳转到skiplist_balls中跳跃距离最大的球（这是不断加速跳跃的过程）；

[*]
重复步骤4，当下一次跳跃超过目标单元时，减小跳跃距离（这是降速跳跃的过程，极限情况下，不使用skiplist_balls回溯，只利用父单元进行回溯），直到目标单元停止。

对于轻节点而言，全节点给出的证据链是可信的，主要有以下两个原因：

[*]
证据链开始的那些单元包含了轻节点信任的见证人发出的单元；

[*]
证据链中的连接使用的是parent_units（寻找见证人过程）、last_ball、skiplist_balls、parent_balls。

因此，通过证据链的方式，轻节点可以判断某个单元是否有效。
端到端加密通道
中枢节点Hub用于为不同的用户设备之间提供可靠的端到端加密数据通道，有点类似邮件服务器。Hub为用户设备提供存储转发服务，用户设备可以选择连接到不同的Hub。用户设备使用websocket连接到到Hub，并采用TLS加密。Hub一旦收到发往某个设备地址的消息，它就会立即转发，转发成功后删除消息。
设备地址是用于标识用户设备的，从而接收其它设备发送的消息，类似于邮件地址。设备地址与钱包地址不同，可以在不同的设备上使用相同的钱包地址。每个设备保存一把永久性的私钥，其对应的公钥做Hash后进行BASE32编码得到设备地址。为了和钱包地址区分开来，设备地址在其开始位置添加0作为标识（0本身并不是BASE32字符）。完整的设备地址还要包括Hub名称，比如DEVICEADDRESS@hubname.com。当切换到不同的Hub是，@之间的地址是保持不变的。
假设发送消息的设备记作sender，接收消息的设备记作receiver，receiver所连接的Hub为hub。那么，当sender想要与receiver进行通信时，它需要进行以下操作：

[*]
sender修改其Hub地址为hub，默认情况下所有设备连接的都是wss://Dagx.org/bb；

[*]
sender与receiver进行配对，可以使用扫描二维码、配对字符串、或者使用Dagx://起始的链接。

所有设备之间的通信均采用了端到端加密（ECDH+AES）和数字签名（ECDSA）。作为通信的唯一中间人，Hub也无法查看或者修改消息内容，为了提高转发的安全性，设备会生成一个临时私钥，并将对应的公钥上传至它连接的Hub上。同时，设备可以定时地更换临时私钥和公钥。
因此，sender在向receiver发送消息时，它需要完成以下步骤：

[*]
与hub连接；

[*]
从hub获取receiver的临时公钥；

[*]
生成一次性的密钥对；

[*]
根据一次性私钥和receiver的临时公钥生成ECDH密钥；

[*]
使用ECDH密钥对消息进行AES加密；

[*]
添加一次性公钥；

[*]
使用设备私钥对整个消息进行签名；

[*]
将消息发送给hub

对于receiver，它首先需要验证消息的签名，然后使用sender的一次性公钥和本地的临时私钥解密消息，从而获得消息的内容。
基于Hub的设备端到端加密消息通道可以用于设备之间通信，设备之间相互发送的消息不存入Dagx数据库中。用户可以利用该通道来发送加密文本消息、多签名交易、隐私资产（比如blackbytes）等。
Dagx的应用
数字资产
Dagx本质上是基于DAG的分布式数据库，数据状态一旦确定则不可逆转。在各种类型的数据中，具有社会普遍意义的数据是比较有价值的，比如个人资产数据。在Dagx中，资产可以发布、转移以及交换，类似于Dagx的基本货币bytes。资产可以代表任何有价值的东西，比如债务、股票、会员积分、通话时间、商品、其它加密货币等。
定义新资产的消息格式为：
unit: {
…
messages: [
…
{
app: “asset”,
payload_location: “inline”,
payload_hash: “hash of payload”,
payload: {
cap: 1000000,
is_private: false,
is_transferrable: true,
auto_destroy: false,
fixed_denominations: false,
issued_by_definer_only: true,
cosigned_by_definer: false,
spender_name_attested: true,
attestors: [
“2QLYLKHMUG237QG36Z6AWLVH4KQ4MEY6”,
“X5ZHWBYBF4TUYS35HU3ROVDQJC772ZMG”
]
}
},
…
],
…
}
在定义新资产时，可以设置以下属性：
cap：资产总量，比如bytes的总量为1015
is_private：资产转移是否公开，比如bytes为公开
is_transferrable：资产是否可以在无发行方允许的条件下进行流通，如果不可流通，则资产的收发方中必须有发行方，比如bytes为可流通
auto_destroy：资产在发送回发行方时是否自动销毁，比如bytes为不自动销毁
fixed_denominations：资产是否以固定面额进行流通（类似纸币），比如bytes可以以任意金额流通
issued_by_definer_only：资产是否仅由发行方发布，比如bytes均在创世单元中发布
cosigned_by_definer：资产在每次转移时是否必须由发行方共同签名，比如bytes是不需要的
spender_attested：资产在使用时用户是否需要通过认证，比如bytes是不需要的
attestors：受资产发行方认可的认证地址，可以在后续过程中修改
denominations：如果资产具有固定面额，定义面额种类以及各类别总量
transfer_condition：资产转移需要的额外条件，语法与地址定义脚本相同（除了不使用sig之外）
issue_condition：资产发布需要的额外条件
在定义资产时，每个单元中最多只能有一条asset消息。当资产定义单元发布后，后续都通过引用该单元的hash来引用该资产。资产只能定义一次，除了attestors之外均不能进行修改。资产定义的解释权在发行方，其具体含义由其进行解释。资产定义中的不同属性的组合可以适用不同的场景。
发布资产的消息格式为：
unit: {
…
messages: [
…
{
app: “payment”,
payload_location: “inline”,
payload_hash: “hash of payload”,
payload: {
asset: “hash of unit where the asset was defined”,
inputs: [
{
type: “issue”,
amount: 1000000,
serial_number: 1,
address: “ISSUER ADDRESS” // only when multi-authored
},
…
],
outputs: [
{
address: “BENEFICIARY ADDRESS”,
amount: 12345
},
…
]
}
},
…
],
…
}
总量有限的资产必须在一个交易中全部发布，比如，所有的bytes都是在创世单元中发布的。如果资产总量有限，发布时serial_number必须为1；如果资产总量不受限，每次发布时serial_number必须保证不同。
转移资产与bytes类似，只是需要加上资产的ID，其消息格式为：
unit: {
…
messages: [
…
{
app: “payment”,
payload_location: “inline”,
payload_hash: “hash of payload”,
payload: {
asset: “hash of unit where the asset was defined”,
inputs: [
{
unit: “hash of source unit”,
message_index: 0,
output_index: 1
},
…
],
outputs: [
{
address: “BENEFICIARY ADDRESS”,
amount: 12345
},
…
]
}
},
…
],
…
}
隐私资产
公开资产在转移过程中，其内容在交易中是完全公开的。而对于隐私财产，在转移时，仅发送特定时间点资产转移的证据；同时，发送者通过私有通道把资产发送给接收者；接收者可以通过区块链上的资产转移证据来验证是否得到该笔资产。
为了解决双花问题，需要在单元增加新的字段spend_proof，要求：
它仅依赖于其所花费的输出，相同的输出将产生相同的spend_proof
无法通过它逆向推断出所花费输出的任何信息
例如采用如下方式生成spend_proof：
spend_proof = hash({
asset: payload.asset,
unit: input.unit,
message_index: input.message_index,
output_index: input.output_index,
address: src_output.address,
amount: src_output.amount,
blinding: src_output.blinding
})
其中，payload.asset表示需要转移的资产，input则表示花费输出src_output的输入。隐私资产的输出必须包含扰乱因子blinding，它使得无法通过spend_proof来逆向推到出其使用了哪个输出。
对于隐私资产的发行来讲，其spend_proof为：
spend_proof = hash({
asset: payload.asset,
address: “ISSUER ADDRESS”,
serial_number: input.serial_number, // always 1 for capped assets
amount: input.amount, // issue amount
denomination: 1 // always 1 for arbitrary-amounts payments
})
在发行隐私资产时，由于需要公开表明已发行该资产，因此不需要添加扰乱因子。在资产传递过程中，发送者已知扰乱因子，虽然他可以知道接收者是否花费了这笔资产，但是他无法知道这笔资产的下一个接收者是谁，也就无法继续跟踪该笔资产的进一步流向了。
spend_proof需要添加到区块链单元中，其格式为：
unit: {
…
spend_proofs: [
{
spend_proof: “the above hash in base64”,
address: “SPENDING ADDRESS” // only if multi-authored
},
…
],
…
}
在发送隐私资产时，发送者需要完成以下几件事情：
• 对每个输出添加扰乱因子
• 将隐私资产通过私有通道发送给接收者，以及该资产传递所在的区块链单元
• 对于单元中每个输入，计算相应的spend_proof并加入单元中
接收者需要检查两件事情：
• 检查收到的隐私资产的hash值是否与区块链单元中的payload_hash相同
• 检查通过收到的隐私资产计算得到的spend_proof是否与区块链单元中的匹配
接收者可以验证整个资产转移的过程，并能够回溯到该资产的发布单元。
Dagx中提供了一种隐私数字资产blackbytes，其定义如下所示：
{
cap: 2,111,100,000,000,000,
is_private: true,
is_transferrable: true,
auto_destroy: false,
fixed_denominations: true,
issued_by_definer_only: true,
cosigned_by_definer: false,
spender_name_attested: false,
denominations: [
{denomination: 1, count_coins: 10,000,000,000},
{denomination: 2, count_coins: 20,000,000,000},
{denomination: 5, count_coins: 10,000,000,000},
{denomination: 10, count_coins: 10,000,000,000},
{denomination: 20, count_coins: 20,000,000,000},
{denomination: 50, count_coins: 10,000,000,000},
{denomination: 100, count_coins: 10,000,000,000},
{denomination: 200, count_coins: 20,000,000,000},
{denomination: 500, count_coins: 10,000,000,000},
{denomination: 1000, count_coins: 10,000,000,000},
{denomination: 2000, count_coins: 20,000,000,000},
{denomination: 5000, count_coins: 10,000,000,000},
{denomination: 10000, count_coins: 10,000,000,000},
{denomination: 20000, count_coins: 20,000,000,000},
{denomination: 50000, count_coins: 10,000,000,000},
{denomination: 100000, count_coins: 10,000,000,000}
]
}
数据
非结构化数据（文本）
用户可以在Dagx中存储文本信息，消息格式为：
unit: {
…
messages: [
…
{
app: “text”,
payload_location: “inline”,
payload_hash: “hash of payload”,
payload: “any text”
},
…
],
…
}
文本可以是任意内容：用户可以利用这个发布不能被篡改的公告、微博等等；也可以存储一些非明文的内容，比如合约的hash值之类的。
结构化数据
用户也可以使用Dagx存储任意的结构化数据，消息格式为：
unit: {
…
messages: [
…
{
app: “data”,
payload_location: “inline”,
payload_hash: “hash of payload”,
payload: {
key: “value”,
another_key: {
subkey: “other value”,
another_subkey: 232
}
}
},
…
],
…
}
投票
用户可以使用Dagx发起投票，消息格式为：
unit: {
…
messages: [
…
{
app: “poll”,
payload_location: “inline”,
payload_hash: “hash of payload”,
payload: {
question: “Should the United Kingdom remain a member of the European Union or leave the European Union?”,
choices: [“Leave”, “Remain”]
}
},
…
],
…
}
同时，用户可以响应投票，其消息格式为：
unit: {
…
messages: [
…
{
app: “vote”,
payload_location: “inline”,
payload_hash: “hash of payload”,
payload: {
unit: “hash of the unit where the poll was defined”,
choice: “Leave”
}
},
…
],
…
}
投票的有效性需要由发起投票方来决定，Dagx仅仅检查投票选项是否在给定集合内。比如，如果发起投票方要求只允许经过认证的或在白名单上的用户进行投票，那些无效的投票也会被Dagx记录，需要由发起方自行判别。
认证
用户可以通过Dagx发布和存储个人信息，消息格式为
unit: {
…
messages: [
…
{
app: “profile”,
payload_location: “inline”,
payload_hash: “hash of payload”,
payload: {
name: “Joe Average”,
emails: [“joe@example.com”, “joe@domain.com”],
twitter: “joe”
}
},
…
],
…
}
用户可以发布任意的个人信息，但是其真实性是无法保证的，只有通过认证的信息才是可信的。
认证消息用于确定用户发布的个人信息的真实性，其消息格式为
unit: {
…
messages: [
…
{
app: “attestation”,
payload_location: “inline”,
payload_hash: “hash of payload”,
payload: {
address: “ADDRESS OF THE SUBJECT”
profile: {
name: “Joe Average”,
emails: [“joe@example.com”]
}
}
},
…
],
…
}
认证消息中的个人信息不一定与用户自己发布的信息一致，事实上，用户甚至没有自己发布过个人信息。
Dagx中的认证者类似于现实世界中的实名认证，认证某个地址是归属于某个个人或组织。认证方可以向被认证方收取少量费用。一般来讲，见证人节点是需要通过认证的，这样可以提高手信任度。被认证方可以选择不公布认证信息，而只在Dagx中保存认证证据，并在合适的时机公布。
总结
Dagx是一种基于DAG结构的不可逆分布式数据库，它可以存储任何有价值的数据。Dagx中每一个新的数据单元都间接地确认了之前所有数据单元的存在性。对已达到稳定状态的数据单元的修改将变得不可实现。
相比于BTC和ETH，Dagx使用了DAG结构作为底层，并使用见证人作为共识机制，从而具有以下特点：
没有区块，只有交易单元，确认速度快
极少的手续费
交易单元具有最终状态
Dagx中发行了一种用于支付存储的货币bytes，支付费用与所需要存储的数据大小相关。自由开发者可以在Dagx平台上自由开发各种应用，根据不同的应用场景发布相应的数字资产。在Dagx上面可以轻松地实现去中心化交易所、互助保险、赌球、彩票、投票、认证等等功能。Dagx还提供了类似telegram的加密端到端通道，可以实现用户之间的隐私通信。Dagx最与众不同的是，它提供了一种隐私数字资产blackbytes，可以完整地保护使用者的隐私信息。
总的来说，不管从使用技术的先进性，还是其提供功能的多样性，DAG都是区块链领域中的佼佼者。

浏览过的版块