Steven's Blog

Appearance

On this page

使用拓扑排序管理比特币的Tx ​

比特币采用的是UTXO模型,对于那些未被打包的交易,需要不断的向临近节点进行广播. 那么广播这些交易的时候就需要有一定的顺序,当然最好的方式就是按照依赖顺序进行排序.

什么是拓扑排序 ​

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

每个顶点出现且只出现一次。 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。 有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

一个例子 ​

graph LR
TX1((TX1))
TX2((TX2))
TX3((TX3))
TX4((TX4))
TX5((TX5))
TX1 --> TX2
TX1 --> TX4
TX2 --> TX4
TX2 --> TX3
TX4 --> TX3
TX4 --> TX5
TX3 --> TX5

这里TxPool中我们有五个Tx, 其中Tx1有两个输出分别被TX2,TX4引用 而TX2有两个不同的输出,分别被TX4和TX3引用 TX4有两个输出,分别被TX3,TX5引用.

Tx1有两个输出分别被TX2,TX4引用 这句话啥意思呢? 就是TX1有两个outpoint,分别出现在Tx2和Tx4的TxIn中.

如果这时候要对外广播交易,那么最好的顺序显然应该是TX1,TX2,TX4,TX3,TX5

拓扑排序的过程 ​

  1. 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
  2. 从图中删除该顶点和所有以它为起点的有向边。
  3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

使用Golang实现对比特币交易的拓扑排序 ​

相关源码位于kahnsort.go,感兴趣的朋友可以查看源码.

  1. 首先将Tx组成图
  2. 分别对各个独立的图进行拓扑排序

数据结构 ​

go
type graphNode struct {
	value    *wire.MsgTx
	outEdges []*chainhash.Hash //指向将value作为TxIn的那些Tx
	inDegree int //value这个Tx依赖多少个Tx
}
type hashGraph map[chainhash.Hash]graphNod

graphNode表示图中的每个节点,其中inDegree保存自己有多少入度,如果入度为0表示没有任何依赖.入度为3则表示该Tx有多个输入,其中有三个都是未上链的交易. outEdges则表示哪些依赖自己的Tx的Hash值. 在区块链中广泛使用Hash值,大家需要习惯.

针对刚刚的例子,那么TX1这个节点应该是如下

go
{
    value:TX1,
    outEdges:{TX2_Hash,TX4_Hash},
    inDegeree:0,
}

而缓冲池中的所有Tx则用hashGraph来表示,为什么不用传统的Graph来表示呢,是因为考虑到缓冲池中的Tx很多时候没有依赖关系,这时候实际上不是一张图,而是多张图,也就是一个Graph的数组. 因此通过hashGraph这种map的形式表示更灵活.

创建hashGraph ​

首先要讲缓冲池中的Tx表达成图 makeGraph的输入就是所有Tx,其中map的key就是Tx的Hash.

go
func makeGraph(set map[chainhash.Hash]*wire.MsgTx) hashGraph {
	graph := make(hashGraph)

	for _, tx := range set {
        //首先遍历所有的交易
		txHash := tx.TxHash()
		if _, ok := graph[txHash]; !ok {
            //如果该交易没有对应的节点,就创建他.
			graph[txHash] = graphNode{value: tx}
		}

	inputLoop:
		for _, input := range tx.TxIn {
            //遍历该Tx的所有输入,找寻依赖
			if _, ok := set[input.PreviousOutPoint.Hash]; !ok {
                //如果依赖的Tx不在缓冲池中,有两种情况
                //1. 孤儿交易
                //2. 依赖的交易已经上链
				continue
			}
            //当前交易依赖的其中一个交易
			inputNode := graph[input.PreviousOutPoint.Hash]

			for _, outEdge := range inputNode.outEdges {
                //如果已经存在一条边,跳过
				if *outEdge == input.PreviousOutPoint.Hash {
					continue inputLoop
				}
			}

            /*
            在Input的outEdges中加入一条边,
            同时当前节点的入度要加1
            */
			inputTx := inputNode.value
			if inputTx == nil {
                //之所以存在inputTx为空的情况,是与交易的遍历顺序有关系
				inputTx = set[input.PreviousOutPoint.Hash]
			}
			graph[input.PreviousOutPoint.Hash] = graphNode{
				value:    inputTx,
				outEdges: append(inputNode.outEdges, &txHash),
				inDegree: inputNode.inDegree,
			}
			node := graph[txHash]
			graph[txHash] = graphNode{
				value:    tx,
				outEdges: node.outEdges,
				inDegree: node.inDegree + 1,
			}
		}
	}

	return graph
}

获取当前有多少张图 ​

graphRoots在hashGraph中找出所有入度为0的节点,这些节点分别就是每一个独立的图的入口.

go
func graphRoots(graph hashGraph) []*wire.MsgTx {
	roots := make([]*wire.MsgTx, 0, len(graph))
	for _, node := range graph {
		if node.inDegree == 0 {
			roots = append(roots, node.value)
		}
	}
	return roots
}

拓扑排序 ​

有了这些组件,再来看拓扑排序就会很简单,我在重复一下开始的思路:

  1. 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
  2. 从图中删除该顶点和所有以它为起点的有向边。
  3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
go
func DependencySort(txs map[chainhash.Hash]*wire.MsgTx) []*wire.MsgTx {
	graph := makeGraph(txs)
	s := graphRoots(graph)

    //一种特殊情况,就是所有的交易都是独立的,互相不依赖.
	if len(s) == len(txs) {
		return s
	}
    /*
    s中保存的全都是入度为0的节点,
    sorted中的是已经按照依赖排过序的Tx
    */
	sorted := make([]*wire.MsgTx, 0, len(txs))
	for len(s) != 0 {
        //步骤1,取一个入度为0的节点
		tx := s[0]
        s = s[1:]
		sorted = append(sorted, tx)

        n := graph[tx.TxHash()]
        //步骤2: 从图中删除该顶点和所有以它为起点的有向边。
		for _, mHash := range n.outEdges {
			m := graph[*mHash]
			if m.inDegree != 0 {
				m.inDegree--
                graph[*mHash] = m
                //入度为0的,加入s
				if m.inDegree == 0 {
					s = append(s, m.value)
				}
			}
		}
    }
    // 结束的时候所有的Tx已经按照依赖排好序了
	return sorted
}