Preliminaries on GHOSTDAG
- Kaspa utilizes GHOSTDAG to select a chain in the DAG.
- Blocks whose weight counted into the selection of the GHOSTDAG chain are called blue blocks.
- A necessary condition for a block B to become a blue block is that its distance from the GHOSTDAG chain is at most k, where k is a controlled parameter in the protocol.
- For any block B in the DAG, the earliest chain block C that has B as an ancestor is called B’s merging block.
- Similarly to Bitcoin, which considers the accumulated work in the chain below a block (rather than its length), GHOSTDAG considers the (blue) accumulated work in the DAG below a block. Formally, the block’s blue accumulated work (BAW) is the work accumulated by blue blocks of its chain, i.e., blocks that are part of the GHOSTDAG chain of its past DAG.
Preliminaries on FlyClient
FlyClient, by Benedikt Bünz, Lucianna Kiffer, Loi Luu, and Mahdi Zamani, is “a novel transaction verification light client for chains of variable difficulty. Flyclient is efficient both asymptotically and practically and requires downloading only a logarithmic number of block headers while storing only a single block header between executions. Using an optimal probabilistic block sampling protocol and Merkle Mountain Range (MMR) commitments, Flyclient overcomes the limitations of NIPoPoWs and generates shorter proofs over all measured parameters.”
The protocol requires each block header to commit to the MMR of all blocks in its chain. The protocol receives the FlyClient commitment from the syncer peer whose chain is claimed to have highest accumulated work, and verifies this claim as follows: It samples blocks in the committed set, verifies their inclusion in the set (via an MMR inclusion proof, which is similar to a Merkle branch), and checks that the MMR of the tip of the chain is indeed an extension of the MMR committed in the sampled block. This guarantees that, if an honest block was sampled, an attacker will not be able to utilize honest blocks to increase its (claimed) accumulated work, unless these blocks are indeed legitimate members of its chain. By resampling multiple rounds, the probability that the proof is fraudulent decreases exponentially.
FlyDAG
Rationale
The strawman approach for adapting FlyClient to a DAG/GHOSTDAG would be to sample the (claimed) set of blue blocks, thereby generalizing over the notion of sampling the (claimed) set of longest chain blocks; and to have an MMR commitment to each block’s blue past, rather than to its (longest) chain. However, this is problematic. FlyClient relies on the fact that every block’s MMR is a subtree of the MMR of the last block in the chain, which holds true since the chain of the former is a subchain of the latter. Albeit, with blue blocks in GHOSTDAG, this property does not hold: the blue past of a blue block B need not be contained in the blue past of the last blue block. Therefore, its MMR commitment may not be a subtree of the T’s MMR.
To circumvent this, we check the MMR commitments against C, the nearest chain block to B. The blue past size of C is guaranteed to be very similar to that of B. With chains blocks, GHOSTDAG too satisfies the property that the MMR of a higher block is an extension of that of a lower one, which recovers the ability of the verifier to check that the inclusion proof of the lower block contains the MMR commitment of the lower one.
Protocol:
We now formalize this solution.
- Every block contains an MMR of all blue blocks in its past (i.e., the output of GHOSTDAG on its past DAG).
- Prover claims that block T has a blue-accumulated-work of W.
- When sampling blocks, we sample out of the blue blocks.
- For each sampled block B, the prover sends an inclusion proof to the block T.
- The prover sends the path to the highest chain block C in B.past. The verifier validates that the path from B to C is not longer than k (which is a necessary condition to become blue).
- The prover sends an inclusion proof for C, and shows that it’s included in T.MMR.
Preliminaries on GHOSTDAG
Preliminaries on FlyClient
FlyClient, by Benedikt Bünz, Lucianna Kiffer, Loi Luu, and Mahdi Zamani, is “a novel transaction verification light client for chains of variable difficulty. Flyclient is efficient both asymptotically and practically and requires downloading only a logarithmic number of block headers while storing only a single block header between executions. Using an optimal probabilistic block sampling protocol and Merkle Mountain Range (MMR) commitments, Flyclient overcomes the limitations of NIPoPoWs and generates shorter proofs over all measured parameters.”
The protocol requires each block header to commit to the MMR of all blocks in its chain. The protocol receives the FlyClient commitment from the syncer peer whose chain is claimed to have highest accumulated work, and verifies this claim as follows: It samples blocks in the committed set, verifies their inclusion in the set (via an MMR inclusion proof, which is similar to a Merkle branch), and checks that the MMR of the tip of the chain is indeed an extension of the MMR committed in the sampled block. This guarantees that, if an honest block was sampled, an attacker will not be able to utilize honest blocks to increase its (claimed) accumulated work, unless these blocks are indeed legitimate members of its chain. By resampling multiple rounds, the probability that the proof is fraudulent decreases exponentially.
FlyDAG
Rationale
The strawman approach for adapting FlyClient to a DAG/GHOSTDAG would be to sample the (claimed) set of blue blocks, thereby generalizing over the notion of sampling the (claimed) set of longest chain blocks; and to have an MMR commitment to each block’s blue past, rather than to its (longest) chain. However, this is problematic. FlyClient relies on the fact that every block’s MMR is a subtree of the MMR of the last block in the chain, which holds true since the chain of the former is a subchain of the latter. Albeit, with blue blocks in GHOSTDAG, this property does not hold: the blue past of a blue block B need not be contained in the blue past of the last blue block. Therefore, its MMR commitment may not be a subtree of the T’s MMR.
To circumvent this, we check the MMR commitments against C, the nearest chain block to B. The blue past size of C is guaranteed to be very similar to that of B. With chains blocks, GHOSTDAG too satisfies the property that the MMR of a higher block is an extension of that of a lower one, which recovers the ability of the verifier to check that the inclusion proof of the lower block contains the MMR commitment of the lower one.
Protocol:
We now formalize this solution.