大部分DAG论文都会提到可以选择最长链作为自己的主链,但Inclusive论文提到除了最长链以外,还可以选择GHOST作为主链。可见GHOST选择主链的规则并不是以链的长度为依据。
先给出GHOST选择主链的算法。
============================
输入:一个区块图
输出:一条区块链(作为主链)
步骤:
- 定义一个区块指针B,指向创世区块,并构造一个只有B组成的区块链。
- 如果B是叶子区块(即没有孩子),则输出区块链并退出。
- 否则遍历B的每一个孩子区块C,考察以C为根区块的区块子树(即C的所有后裔)所需要的工作量证明。挑选工作量证明难度最大的那棵子树的根区块。将挑选出的那个区块C附加到区块链中,然后让B指向C。
- 跳转到第2步。
============================
下面结合GHOST论文中的例子来讲解上面的算法。
GHOST算法从创世区块开始往叶子方向推进,并在推进的每一步中以工作量证明难度为依据挑选“最重”(也可以说是“最难”)的子树。为了便于说明,在这个例子中我们假设每个区块的工作量证明难度都一样。因此最重的子树也就是区块数量最多的子树。
在图中,区块1B的子树含有12个区块,而1A的子树只有6个。因此算法会选择1B作为主链的一环,进而挑选1B子树中的分叉。以此类推,最终输出的主链是区块0、1B、2C、3D、4B。而不是以5B结尾的1B子树中的最长链。
这样的好处在于,即便有攻击者的算力够强,其秘密构造的链(如图中1A至6A组成的链)长度超过了诚实矿工构造的最长链,系统也未必会采用攻击者的链作为主链。