Fairness and Garbage Collection in DAG-Based BFT

A key fairness property in blockchain systems is ensuring that no validator is ignored, allowing even slow validators to contribute transactions to the total order. In the context of DAG-based Byzantine Fault Tolerance (BFT), it is essential that every validator can add vertices to the DAG.

Since up to f validators can be Byzantine and might never broadcast their vertices, it is challenging to distinguish between these and slow validators during asynchronous periods. Honest validators should not wait for more than n−f vertices to proceed to the next round. Consequently, a slow validator may always be late, unable to add its vertex to the DAG as other validators move to round i before receiving its vertex for round i−1.

To address this issue, DAG-Rider introduced weak edges that point to vertices from older rounds. These edges are ignored by the consensus mechanism and do not count as votes. Their sole purpose is to ensure that all vertices from all honest validators eventually get added to the DAG and become part of the total order in a future anchor's causal history.

Refer to the illustration below for a visual representation of this mechanism.

A challenge with DAG-based BFT systems is garbage collection. During asynchronous periods, it may take an indefinite amount of time for a vertex to be delivered, making it unsafe to garbage collect rounds that do not have all vertices in the DAG. This is impractical for real-world applications.

Bullshark strikes a balance between garbage collection and fairness. It ensures constant garbage collection while maintaining fairness during synchronous periods.

To achieve this, validators attach their local time to each vertex they broadcast. Once an anchor is committed and ready for ordering, the anchor’s timestamp is calculated as the median of the timestamps of its parent vertices. While traversing back through the anchor’s causal history to deterministically order it, the timestamp for each round is computed as the median of the timestamps in that round's vertices. When encountering a round r with a timestamp that is older than the anchor’s timestamp by more than a predefined Δ time, round r and all earlier rounds are garbage collected. Vertices not yet added to the DAG in these rounds will need to be re-broadcast in future rounds. However, it is guaranteed that if a slow validator can broadcast its vertex within the Δ time, the vertex will be added to the DAG and be totally ordered.

After ordering the anchor in the figure above, its timestamp is calculated as 5 based on its parent vertices' times. The timestamps for rounds i, i+1, i+2, and i+3 are computed from the times of the vertices in these rounds within the anchor’s causal history. In this example, with Δ=2, round i and all preceding rounds are garbage collected. Although Validator 4 is slow, it managed to broadcast its vertex in time, allowing the vertex to be ordered due to the weak links.