📌Algorithm 2

Algorithm 2: Structuring the DAG with PHANTOM

Within the innovative framework of PHANTOM, the Directed Acyclic Graph (DAG) introduces a revolutionary approach to transaction ordering through the Greedy Heaviest Observed Sub-DAG (GHOSTDAG) algorithm. This algorithm stands as a cornerstone in the architecture, skillfully managing the complexities introduced by parallel block creation—a notable deviation from the linear progression seen in traditional blockchain technologies. Below is a detailed exploration of the GHOSTDAG algorithm, emphasizing its methodology and execution.

Core Principle

The DAG structure of PHANTOM allows for the simultaneous generation of blocks, a feature that significantly diverges from the sequential block creation in classic blockchains. This architectural choice necessitates a sophisticated mechanism to establish a definitive sequence for processing and validating transactions housed within these concurrent blocks. The GHOSTDAG algorithm emerges as this critical mechanism, ensuring coherent transaction ordering within the DAG.

Initial Process

The operational phase begins with the formation of an empty queue and list. This foundational step is followed by introducing the genesis block—the inaugural block of the DAG—into the queue, setting the stage for the following iterative processing.

Iterative Processing

The essence of the GHOSTDAG algorithm unfolds through its iterative processing phase. In this stage, the algorithm methodically selects a block (denoted as B) from the queue and integrates it into the list. The process extends by examining all selected block B's validated child blocks (C).

For each child block C, the algorithm comprehensively evaluates all blocks (D) residing "in the past" of child C, including blocks referenced directly by C or through its ancestral lineage. Importantly, these past blocks (D) are distinct from the "anticone" of block B, referring to blocks that are not reachable from B.

These past blocks (D) are crucial as they potentially influence the positioning of C within the overall order. Subsequently, every past block (D) identified in this evaluation is queued for processing, alongside the child block (C) 's re-inclusion into the queue.

Final Output

The algorithm reaches its culmination when the queue is exhausted, leaving behind a list that meticulously arranges the blocks in their definitive transactional sequence within the DAG.

Algorithm 2-DAG Ordering Procedure

Input: G – a block DAG, k – the propagation parameter

Output: ord(G) – an ordered list containing all of G’s blocks function ORDER(G, k)

initialise empty queue topo queue

initialise empty ordered list L

BLUEk (G) ←CALC-BLUE(G, k) topo queue.push (genesis)

while topo queue 6= ∅ do

B ← topo queue.pop()

L.add(B) (B is added to the end of the list)

for all C ∈ childrenB ∩ BLUEk (G) do

for all D ∈ past(C) ∩ anticone (b) \ L do

topo queue.push(D)

topo queue.push(C)

ord(G) ← L

return ord(G)

Through meticulous design and strategic execution, the GHOSTDAG algorithm elegantly addresses the inherent challenges of DAG-based transaction ordering, underscoring PHANTOM's innovative contribution to the field of blockchain technology.