DAG Blockchain之Byteball原理解析（一）

DAG数学基础

 

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

 

 

在图论中，相比于一般图，DAG的很多问题可以在多项式级甚至线性复杂度条件下得到求解。DAG具有以下几条数学性质：

 

DAG具有拓扑顺序，即DAG的所有节点可以转换为节点序列（线性化），使得每条边的起始节点位于终止节点之前，且该过程可以在线性复杂度条件下完成；

DAG中相互连通的节点可以进行排序，如果从节点u出发可到达节点v，则可称为u≤v；

DAG具有唯一的传递闭包；

DAG具有唯一的传递规约，传递规约的边数最大不超过V−1条，V是DAG的节点数；

DAG中给定两个节点，其最短路径和最长路径可以在线性时间内求解。

 

DAG常用来做任务的调度规划，比如Spark在做并行处理时使用DAG来任务规划，Git采用DAG来做版本管理。DAG在区块链上的应用可以参考 《DAG也许是真正的区块链3.0》，下面将对使用DAG作为区块链的Byteball原理进行详细的解析。

 

Byteball的区块链结构

 

Byteball区块链如上图所示，其基本组成为单元(unit)，所有单元共同构成DAG。其中，单元G为创世交易，它与所有单元连通，且是从所有单元出发到达的终点。

 

父单元与子单元：从单元A出发可直接到达单元B，即单元A到单元B的路径长度为1，则单元B称为单元A的父单元，单元A称为单元B的子单元。

 

直接包含：如果单元A为单位B的子单元，则单元A直接包含或者验证了单元B。

 

间接包含：如果从单元A出发到达单元B的路径长度大于1，则单元A间接包含或者验证了单元B。

 

顶端单元：不具有任何子单元的单元，也可称为无子单元或未经验证的单元。

 

创世单元：由创世交易构成的单元，不具有任何父单元。

 

相比于Bitcoin中一对一的链式区块结构，Byteball中单元在发出时，可以同时包含多个父单元，因此可以容纳更多的交易并获得更快的确认。由于进入DAG的单元将被所有与其连通的单元直接或间接地验证，如果要修改该单元的内容，则需要相应地修改验证了它的所有单元。直观上来讲，将要修改的单元数量（归属于不同的用户）像滚雪球一样急速增加，从而使得修改无法实现，这也是DAG可以作为区块链的重要基础。

 

单元的结构如下所示，其主要由三部分组成：

 

1、单元数据：数据以message的形式构成；

2、地址签名：输入所需的相应地址签名；

3、父单元：当前单元的父单元列表。

 

从中可以看出Byteball采用的交易模型是UTXO，即当前交易输出作为后续交易的输入。所有bytes是在创世交易中发出，因此Byteball本质上就是一种完全预挖的币。bytes可用于支付手续费，或在地址之间相互传输。

 

 

当某个单元达到稳定之后，就可以生成球(ball)，此时它的状态（是否有效）将确定性的固定下来，球的结构如下所示：

 

 

单元的结构中还包括见证人列表单元，这是为了节省存储空间，表示当前单元的见证人列表与其相同。关于球、见证人我们再后续解析共识算法时会详细讨论到。

坚持原创技术分享，您的支持将鼓励我继续创作！

来源：

来源：中币网  https://www.zhongbi.net/news/blocknews/25405.html
声明：登载此文仅出于分享区块链知识，并不意味着赞同其观点或证实其描述。文章内容仅供参考，不构成投资建议。投资者据此操作，风险自担。 此文如侵犯到您的合法权益，请联系我们3111859717@qq.com，我们将第一时间处理。