🧮BlockDAG Protocol

Before introducing the protocol specifics, it is essential to lay down some fundamental definitions to ensure clarity and understanding throughout this exposition.

Definition: Within a Directed Acyclic Graph (DAG) denoted as G = (C, E), where C represents a set of blocks and E symbolizes the hash references or edges between these blocks, a subset S of C is termed a k-cluster if for every block B within S, the size of the intersection between S and the anticone of B does not exceed k.

Here, the term "anticone" refers to the set of blocks in C that are not reachable from B and do not include B itself. It is common to denote the presence of a block within a DAG by B ∈ G, which simplifies to B ∈ C. The parameter k is predetermined and plays a crucial role in forming clusters within the DAG.

Maximum k-cluster SubDAG (MCSk) Problem:

Input: A DAG G = (C, E)

Output: A subset S ⊆ C of maximal size such that for every block B within S, the size of the intersection between S and the anticone of B is at most k.

To elucidate, consider identifying the largest 3-cluster within a specific DAG, comprising blocks denoted as A, B, C, D, F, G, I, J, and colour-coded in blue for visual clarity. It is verifiable that each block within this blue-coded set has a maximum of three other blue blocks in its anticone, underscoring that this set is the largest possible to adhere to the specified condition. By setting the PHANTOM protocol’s inter-connectivity parameter to k = 3, it is inferred that a maximum of four blocks can be produced within each unit of time delay.

As a result, the expected size of any anticone typically does not surpass three blocks. Blocks not included within the largest 3-cluster, specifically E, H, and K (marked in red), are presumed, with high probability, to be associated with adversarial actions.

For instance, block E has six blue blocks within its anticone (B, C, D, F, G, I), suggesting these blocks did not reference E, likely due to E being intentionally withheld from their miners. In a similar vein, block K has six blue blocks in its anticone (B, C, G, F, I, J), indicating that while its miner might have received some blocks from (B, C, D, G), it contravened the mining protocol by failing to reference them, thereby hinting at malicious intent.