Orbits网络

2019.09月报(Orbits网络)

目录

  1. 哈希图 (Hashgraph)的运行方式以及应用

  2. DAG 拓扑排序 (DAG Topological Ordering )

哈希图(Hashgraph)的运行方式以及应用

1. Swirlds 哈希图

哈希图(Hashgraph)是Swirlds公司为创建分布式账本(DLT)而开发程序。2016年中期,为了满足私人公司的需求而开发了哈希图,哈希图则是构建分布式账本的方法之一。(相关内容可在2019.08月报中Orbits网络DAG部分查看)

https://www.hedera.com/blog/the-evolution-of-possibilities‌

哈希图是Swirlds用于管理个人知识产权的分布式账本应用程序。被称之为Swirlds Hashgraph。

哈希图具有以下所述优点:

  • 高吞吐量:处理速度可达到每秒100,000 TPS

  • 不变性:交易历史是不会改变

  • 抗攻击:可抵抗DDoS攻击

  • 一次性:支持可一次性使用的分布式账本

哈希图是一款分布式账本程序,而不是区块链技术。因此,哈希图未被列入加密货币高收益投资项目行列之中。但是,在由CUNA(美国国家信用联盟协会)和 MWCUA(西部山区信用联盟协会)组成的北美各地6,000家银行联盟的关注下,Swirlds决定组建Hedera哈希图平台(Hedera Hashgraph Platform)。

事实上,哈希图并不包含区块链技术,这种管理模式类似于以太坊网络。哈希图平台高层则由Hedera理事会构成,理事会中有39名会员(个人和法人),项目的开发以及发展方向均由理事会来进行决策。 Swirlds由管理层选举执行理事, T-Labs,DLA Piper,野村证券,Swisscom Blockchain和Luiza杂志等五位理事会成员已经入选。

因此, Hedera哈希图平台的管理方式不同于比特币和以太坊,而是更类似于Visa等跨国公司(财团)的管理模式。知识产权方面也是如此, 由于该软件受版权保护,因此,Hedera哈希图在网络中无法进行硬分叉。

2. Hedera Gashgraph

https://tgraph.io/Hedera-Hashgraph-obzor-ICO-proekta-06-14‌

Hedera 哈希图平台并不是区块链,哈希图也并非区块链结构。它并不是由数据在区块中积累之后连接而成的链式结构。哈希图的数据则是存储在能够描述某个特定事件(事务)的哈希值中。

https://tgraph.io/Hedera-Hashgraph-obzor-ICO-proekta-06-14‌

平台的操作以及参与者之间的哈希交换都是通过Gossip协议进行的。 当有事务发生时,该节点将数据发送到其他两个任意节点,然后再将数据发送至另外两个任意节点。 (共4个)

通过这种方式信息呈指数型分布于整个网络中。

但是,仅凭信息在网络中传播并不能保证全网信息达成共识。 这要求系统的参与者要知晓所有的交易记录,即每笔交易的确切时间。

哈希图在 Gossip中负责Gossip共识算法。网络中的各个节点则是通过相关技术将全部的交易信息以哈希值方式共享给网络参与者。

最终来看,从该网络可知晓信息先后出现的顺序。

DAG拓扑排序 (DAG Topological Ordering)

拓扑排序是指列出有向图的顶点所排成的一个线性序列。

能够说明拓扑排序的最好例子就是大学的选修课(prerequisite) 。

如果在选定的课程当中包含有选修课程,那么在必修课与选修课的顺序选择中可通过拓扑排序的方式找出相应的排序。如同在已选定好的图表构造中使用拓扑排序来制定先后顺序。

排列的顺序可以根据有向图的结构而发生多种变化。 拓扑排序若要成立,图表则必须不可循环。 也就是说,该图表必须是有向无环图(directed acyclic graph)。

拓扑排序的一般应用于业务日程的顺序安排,自1960年代初开始就研究此算法,目的是将其用于项目管理技术应用以及 计划审评(PERT) 。

此时,任务可被表示为一个顶点,连接每个顶点的边代表了任务之间的先后关系。

例如,熨烫衣服的任务必须安排在衣服洗涤完后。这就如同拓扑排序提供的任务执行时顺序。

1. 深度优先搜索算法——Depth-First-Search(DFS)

深度优先搜索意味着熊一个顶点开始依次访问所有的点。

深度优先搜索(Depth-Frist-Search)首先会对深度进行确认,之后才会确认宽度,该搜索方式会先找到一个相对最深位置的点,如果它无法继续前进,则会返回到最近的分叉并继续向下直至无法向下搜索。

深度优先搜索的特点

  • 它具有递归算法的形式。

  • 深度优先搜索算法与其他树的先序遍历,都是DFS的一种。

  • 实施此算法时的主要区别在于,对于图表的搜索,必须去检查具体访问了哪个节点。

2. DAG 拓扑结构

未配置为DAG的图表无法进行拓扑排序。 仅在DAG情况下才可以进行拓扑排序,因为在循环结构中拓扑排序会进入死循环。

以下是用于拓扑结构排序的代码:

class Graph {
int V; // Number of vertices
List<Integer> adjListArray[];
public Graph(int v) {
V = v;
List<Integer> adjListArray[] = new LinkedList[V];
this.adjListArray = adjListArray;
for (int i = 0; i < V; i++) {
adjListArray[i] = new LinkedList<>();
}
}
public void addEdge(int src, int dest) {
this.adjListArray[src].add(dest);
}
public void printAdjList() {
for (int i = 0; i < this.adjListArray.length; i++) {
List<Integer> adj = this.adjListArray[i];
System.out.println(i + ":" + Arrays.toString(adj.toArray()));
}
}
private void allTopologicalSortsUtil(boolean[] visited, int[] inDegree, ArrayList<Integer> stack) {
boolean flag = false;
for (int i = 0; i < this.V; i++) {
if (!visited[i] && inDegree[i] == 0) {
visited[i] = true;
stack.add(i);
for (int adjacent : this.adjListArray[i]) {
inDegree[adjacent]--;
}
allTopologicalSortsUtil(visited, inDegree, stack);
visited[i] = false;
stack.remove(stack.size() - 1);
for (int adjacent : this.adjListArray[i]) {
inDegree[adjacent]++;
}
flag = true;
}
}
if (!flag) {
stack.forEach(i -> System.out.print(i + " "));
System.out.println();
}
}
public void allTopologicalSorts() {
boolean[] visited = new boolean[this.V];
int[] inDegree = new int[this.V];
for (int i = 0; i < this.V; i++) {
for (int var : this.adjListArray[i]) {
inDegree[var]++;
}
}
ArrayList<Integer> stack = new ArrayList<>();
allTopologicalSortsUtil(visited, inDegree, stack);
}
}

拓扑排序的节点配置如下所示:

Graph graph = new Graph(6);
graph.addEdge(5, 2);
graph.addEdge(5, 0);
graph.addEdge(4, 0);
graph.addEdge(4, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
graph.printAdjList();
graph.allTopologicalSorts();

相应拓扑结构的输出结果如下所示: