Fast Confirmation of GhostDAG with SPECTRE
GhostDAG[1] protocol from DAGlabs[3] is an upgrade to SPECTRE[2] protocol, supporting transaction linear-ordering, which is the prerequisite of on-chain Smart Contracts. The trade-off is that GhostDAG’s confirmation time will be longer than SPECTRE ‘s. GhostDAG has been exploring how to maintain the GhostDAG transaction linear ordering capability while also having SPECTRE ‘s fast confirmation capability. The latest paper of GhostDAG[1] has provided a reference implementation. We may study together how it works.
GhostDAG’s confirmation is slower than SPECTRE ‘s because it has to estimate the maximum network delay, which is the maximum time it takes for a block to spread across the entire network. The delay time should be large enough for the vast majority of nodes to propagate throughout the network. The calculation of the confirmation time is based on the delay time so that the confirmation time will increase accordingly. The confirmation time of SPECTRE depends only on the propagation delay of the node itself and can be as close as possible to the limit of the confirmation speed.
According to the definition of the BlockDAG framework, for any block B, the whole ledger G is composed of the past set, future set, and anticone set. The Past Set and Future Set form a cone set, representing the set of B with the order determined. For any block b in the anticone set, we need to count those blocks before b by the SPECTRE ordering rule ≺G; we define this number as the gap.
If it is an honest block, the gap should be relatively small. Specifically, it is less than the k value of GhostDAG, which is the number of blocks generated by the whole network when a node is generating in a block. We could understand it as the degree of concurrency.
To quantify this gap, GhostDAG has proposed a pumping index; as the name implies, it extends, as if pumping out, blocks from B until B gets votes to surpass all the other blocks in the anticone. One thing needs to mention, according to SPECTRE’s rules, extending blocks will enlarge one block’s future set, and the block will get all votes from the future set. Since the extending blocks only affect the block’s future set, only the block will get additional votes while will not affect other blocks; therefore, it would be an effective metric of the gap.
Formally, if there are j blocks extension after block B, then b1 is the only child block of b, and all the original children nodes of B connect to bj. We define the modified ledger as <b, G, j> , then the formal definition of pumping index is as follows:
Now we may derive the blue set based on the pumping index. There is a Condorcet paradox regarding SPECTRE that it would happen that a < b, b < c, c < a, however, since SPECTRE only affects blue set generation, even if this paradox occurs, GhostDAG could get the linear order of transactions in the blue set. In addition, the calculation of SPECTRE does not take into account the maximum network delay so that the confirmation would be faster.
Pseudo code
References：
[1] Sompolinsky, Y. (2018). PHANTOM , GHOSTDAG : Two Scalable BlockDAG protocols.
[2] Sompolinsky, Yonatan et al. “SPECTRE: A Fast and Scalable Cryptocurrency Protocol.” IACR Cryptol. ePrint Arch. 2016 (2016): 1159.
