GHOST选择主链的规则

大部分DAG论文都会提到可以选择最长链作为自己的主链,但Inclusive论文提到除了最长链以外,还可以选择GHOST作为主链。可见GHOST选择主链的规则并不是以链的长度为依据。

先给出GHOST选择主链的算法。

============================

输入:一个区块图

输出:一条区块链(作为主链)

步骤:

  1. 定义一个区块指针B,指向创世区块,并构造一个只有B组成的区块链。
  2. 如果B是叶子区块(即没有孩子),则输出区块链并退出。
  3. 否则遍历B的每一个孩子区块C,考察以C为根区块的区块子树(即C的所有后裔)所需要的工作量证明。挑选工作量证明难度最大的那棵子树的根区块。将挑选出的那个区块C附加到区块链中,然后让B指向C。
  4. 跳转到第2步。

============================

下面结合GHOST论文中的例子来讲解上面的算法。

GHOST算法从创世区块开始往叶子方向推进,并在推进的每一步中以工作量证明难度为依据挑选“最重”(也可以说是“最难”)的子树。为了便于说明,在这个例子中我们假设每个区块的工作量证明难度都一样。因此最重的子树也就是区块数量最多的子树。

在图中,区块1B的子树含有12个区块,而1A的子树只有6个。因此算法会选择1B作为主链的一环,进而挑选1B子树中的分叉。以此类推,最终输出的主链是区块0、1B、2C、3D、4B。而不是以5B结尾的1B子树中的最长链。

这样的好处在于,即便有攻击者的算力够强,其秘密构造的链(如图中1A至6A组成的链)长度超过了诚实矿工构造的最长链,系统也未必会采用攻击者的链作为主链。

1赞

附上GHOST原文地址:

https://www.cs.huji.ac.il/~yoni_sompo/pubs/15/btc_scalability.pdf

1赞