A. The generation of the block

DAG As in Bitcoin, participating nodes (called miners) create blocks of transactions by solving PoW puzzles. A block specifies its direct predecessors by referencing their ID in its header (a block’s ID is obtained by applying a collision resistant hash to its header); we will describe in the next subsection how these predecessors are chosen. This results in a structure of a direct acyclic graph (DAG) of blocks (as blocks can only reference blocks created before them), denoted typically G=(C,E). Here, C represents blocks and E represents the hash references. We will frequently write z ∈ G instead of z ∈ C. past(z,G) ⊂ C denotes the subset of blocks reachable from z, and similarly future(z,G) ⊂ C denotes the subset of blocks from which z is reachable; these are blocks that were provably created before and after z, correspondingly.

Note that an edge in the DAG points back in time, from the new block to previously created blocks which it extends. A node does not consider a block as valid until it receives its entire past set. We denote by cone(z,G) the set of blocks that the DAG directly orders with respect to z: cone(z,G) := past(z,G)∪{z}∪future(z,G), and by anticone(z) the complementary of cone(z,G). The set past(b,G) is fixed once and for all at the creation of b (in sharp contrast to future(z,G) and anticone(z,G) that may grow as blocks are added later to the DAG), hence we can simply write past(b) without noting the context.

The unique block genesis is the block created at the inception of the system, and every valid block must have it in its past set. In addition, we relate to a hypothetical block, virtual (G). This block satisfies past(virtual (G)) = G. While its role is merely methodological, virtual(G) can also be thought of as representing the next block that a node whose current observed DAG is G attempts to create. Gvt denotes the block DAG observed by node v ∈ N at time t. This DAG represents the history of all (valid) block-messages received by the node, instantiating the abstract data structure.

B. The mining protocol

SPECTRE’s instructions to miners are extremely simple:

  1. When creating or receiving a block, transmit the block to all peers.
  2. When creating a block, embed in its header a list containing the hash of all leaf-blocks (blocks with in-degree 0) in the locally-observed DAG.

Note that these instructions allow miners to operate concurrently irrespective of potential conflicts in the contents of their blocks.