Progress Metrics in DAG-based Consensus

Quan Nguyen FANTOM James Henderson FANTOM Egor Lysenko FANTOM

Abstract

Lachesis protocol [2] leverages a DAG of events to allow nodes to reach fast consensus of events. This work introduces DAG progress metrics to drive the nodes to emit new events more effectively. With these metrics, nodes can select event timing and can choose previous events as parents for their own new events. Our results show that our event timing and parent selection methods can help reaching consensus quicker and thus can reduce lower time to finality significantly.

Keywords event timing, parent selection, OPERA, directed-acyclic-graph, DAG progress, metrics, Lachesis, consensus protocol

1 Introduction

Lachesis protocol [2, 1] is a BFT consensus protocol that reduces communications overhead as events can be reused in the form of event DAG. Nodes participating in Lachesis consensus produce events asynchronously. Nodes generate event blocks to form a DAG of events, each of which contains transactions. Each event block has references to parent event blocks. For an event block $e$ and it’s parents $e_{p}$ , there is no restriction about the creator nodes of $e$ and that of $e_{p}$ . Each node computes Roots to find Atroposes in order to reach consensus on finalized event blocks.

Each node can generate new own event block and can choose which previous events as the parents for this new event. Throughout this paper, the terms ‘event block‘ and ‘event‘ are used interchangeably. Event generation involves two steps Event Timing and Parent Selection.

•

Event Timing: node can decide by itself when it can generate a new own event block.
•

Parent Selection: this is the process of select a suitable set of previous event blocks and use them as parents (aka. $e_{p}$ ) for the new event.

For the network to perform efficiently, nodes need a set of criteria so as to produce a new event in an effective manner. If nodes produced too many events, it could increase communication overheads as peers will need to handle those events. At the same time, many of such events are possibly abundant in the sense that they do not necessarily contribute to reach a new root. Thus, it is important to know whether a node should emit a new event and whether they should choose certain events as the parents for this new event.

In this work, we introduce two new metrics, which measure the DAG progress of an event and can be used to optimize the way that a node emits a new event. The two metrics are Quorum Indexer (QI) metric and Root Knowledge (RK) metric. The metrics enable nodes to determine whether a proposed new event block will have a positive contribution towards reaching a new root.

Based on the two metrics, we have defined new criteria for event timing and parent selection for nodes. In event timing, node can decide itself whether creating a new event will be beneficial. Leveraging the metrics ensures that nodes attempt to create events only if they can produce substantial DAG progress toward finality. The metrics can also improve parent selection, in which nodes can select previous events as candidate parents for its new event, and thus it can improve the contribution of each event toward reaching finality.

We compare the two metrics in a set of experiments. Our experimental results show that RK metric outperformed QI metric. Our results also show that event timing and parent selection based on the RK metric have significantly reduced the node overheads (i.e. avoid generate excessive events and handle them) and time-to-finality (TTF). Efficiency is achieved as nodes will create events when they are able to make substantial DAG progress, reducing the computational time and resources used for processing and transmitting events.

2 DAG Progress Metrics

This section describes two new DAG progress metrics. These metrics are used in event timing and parent selection.

2.1 Quorum Indexer Metric

Quorum Indexer (QI) is a measure of DAG progress. QI metric is based on the sequence numbers of HighestBefore events.

Let $v$ be a node. For a local DAG of $v$ , we determine each highest (latest) event $e_{i}$ for each node $i$ . HighestBefore calculations are performed for each node $v$ as follows.

•

Median: Each node $v$ computes the highest events $e_{i}$ for each node $i$ in a local DAG of $v$ . For each $e_{i}$ , it then finds the sequence number of $e_{i}$ in the subgraph. Then it calculates the median sequence number weighted by the stake of each highest event creator’s stake. Intuitively, this gives an estimate of the median highest event created by $i$ in all nodes.
•

Current Self: A node $v$ finds the sequence number of highest event created by $v$ in the subgraph of its own.
•

New Self: A node pre-computes the sequence number of highest event created by $v$ that would be in the subgraph if it created such a new event.

The above three sub-metrics for node $v$ are combined into a single QI metric of DAG progress produced by a new event. To do so, the three metrics are compared and transformed using a piecewise linear function into a metric in the range $[0,w_{i}/W]$ , where $w_{i}$ is the stake of node $v$ and $W$ is the total stake of all nodes.

The QI metric $h^{(e)}$ is defined as summation across all nodes $i$ to give a final metric of DAG progress for a new event $e$ . The metric is in the range [0,1], with 0 indicating little DAG progress, and 1 indicating significant DAG progress.

2.2 Root Knowledge Metric

Progress in Lachesis consensus is achieved via the production of new roots and frames. Root Knowledge (RK) metric is a more effective metric as it is built on the knowledge of previous roots.

An event $e$ is a root when in $e$ ’s subgraph quorum roots of the previous frame forkless-cause $e$ . This means that within $e$ ’s subgraph quorum roots of the previous frame are each in the subgraph of events created by quorum nodes, potentially with different sets of quorum nodes for each previous root. Further, there can be no forks detected for any of the nodes involved in confirming the forkless-cause condition.

2.2.1 Notations

The progress of an event $e$ toward meeting the required conditions for the next root can be described via a root knowledge matrix $\mathbf{K}^{(e)}$ (or simply $\mathbf{K}$ ).

We write knowledge of previous roots among $n$ nodes in an event $e$ ’s subgraph as an $n\times n$ matrix $\mathbf{K}$ , with entries

\mathbf{K}^{(e)}_{ij}=\begin{cases}1,&\text{if the subgraph of node $i$ contains a root created by node $j$ and no forks are observed for $i$ or $j$.}\\ 0,&\text{otherwise.}\end{cases}

(1)

Let $k^{(e)}$ be the sum of all elements in matrix $\mathbf{K}^{(e)}$ . The metric $k^{(e)}$ is in the range $[0,1]$ .

k^{(e)}=\frac{1}{n^{2}}\sum_{i}\sum_{j}\mathbf{K}^{(e)}_{ij}.

(2)

where the numerator is a count of the number of nodes observing each known root in the subgraph. The denominator $n^{2}$ normalises $k^{(e)}$ to the range [0,1], where $k^{(e)}=1$ if all nodes know all roots.

We define the progress of an event $e$ as a scalar metric of DAG progress, $k^{(e)}$ . This scalar metric will enable a comparison the progress of two events. Figures 1(a) and 1(b) show $\mathbf{K}$ and $k$ examples for simple DAGs.

Refer to caption — (a) Root knowledge of event $e$ on the left is $k^{(e)}$ = 1/9.

A new root will typically be produced before $k^{(e)}$ because producing a new root only requires quorum prior roots to forkless cause the new root.

2.2.2 Pseudo-code

The rootProgress function in calculates the root knowledge $k^{(e)}$ of an input event $e$ . The function rootProgress does not explicitly construct the $n\times n$ matrix $\mathbf{K}^{(e)}$ in memory. Instead, $k^{(e)}$ can be calculated by looping over the indexes of $\mathbf{K}^{(e)}$ without storing the matrix’s elements in memory. The implementation uses function ForklessCauseProgress to calculate each column of $\mathbf{K}^{(e)}$ .

Algorithm 1 rootProgress

k^{(e)}

calculation

function rootProgress(

e

)

\leftarrow

roots in

e

’s subgraph

\leftarrow

for r in range(R) do

c

= ForklessCauseProgress(e, r)

s

s

+ sum(

c

)

return s

In Alg. 1, ForklessCauseProgress returns a column of $\mathbf{K}^{(e)}$ , corresponding to the number of nodes that have an event whose subgraph contains root, without forks.

3 Parent Selection and Event Timing

Based on the metrics, a node can rank candidate events for its new event. For each QI metric and RK metric, a parent selection method is defined to rank candidate parents into a sorted list. Parents are selected from the list if they provide the greatest progress toward producing the next root.

Based on the two metrics, we also define two different event timing strategies. We define new event timing metrics $t$ for a node $v$ based on DAG progress metric (e.g., either QI metric $h^{(e)}$ or RK metric $k^{(e)}$ ).

We describe the timing metric $t$ based on RK metric $k^{(e)}$ in more details as follows. The timing metric $t$ can be defined base on QI metric $h^{(e)}$ in a similar way.

Let $v$ be a node, and let $e_{v}$ be the latest event of $v$ . Within node $v$ ’s local DAG, for a node $i$ , let $e_{i}$ be the latest event of $i$ . The new metric $t$ counts the number of nodes $i$ , whose highest event has metric $k^{(e_{i})}$ that exceeds that of $e_{v}$ . $t=\sum_{i}H(k^{(e_{i})}-k^{(e_{v})})s_{i}$ , where $s_{i}$ is the stake of node $i$ and $H(x)$ is the step function. $H(x)$ = 1 if $x>0$ ; 0, otherwise.

The event timing metric is used to order nodes and is a direct measure of the progress a node has made toward producing a new root and progressing toward the next frame. Nodes emit an event when they fall below a threshold level in an ordering of nodes, and new emission is to help increase their DAG progress metric.

4 Simulation Results

Figures 2(a), 2(b), and 2(c) compare the performance in simulation between parent selection and event timing methods using QI metric and RK metric.

The experiments were made on a simulation of a network consisting of 30 nodes, with the stake of each node randomly sampled. A dataset of real world internet latencies between cities is used to model latencies between pairs of nodes. It randomly allocated each node to a city in the dataset. Each of the 100 simulations shown are simulations of 100 seconds of network activity.

On average, the new RK metric is more efficient, producing each frame using fewer events compared to the QI metric. The new RK metric produces more frames per second on average compared to QI metric, and thus, the new methods will lower TTF.

Figure 3 compares frame rate. The experiments were made with a simulation of 40 nodes, each event has 3 parents. Latency was set around 100ms.

5 Conclusion

In this work, we introduce two new metrics to measure the DAG progress of a new event. By comparing between different possible new event blocks it can generate, a node can determine which new event block is the most effective to be made in order to progress toward achieving a new root.

Based on the metrics, we presented new methods for event timing and parent selection. These methods will give several advantages. First, they can reduce the number of generated events and can avoid generating many excessive events and hence can reduce communication overheads. Second, using these methods, it can achieve faster finality as it can compute roots and Atroposes quicker. Third, it can reduce events per frame and increase frame rate, as more events are generated only if they help achieve roots quicker. As such, it improves the number of frames per second (frame rate).

6 Reference

[1] Q. Nguyen, A. Cronje, M. Kong, A. Kampa, and G. Samman. Stairdag: Cross-dag validation for scalable BFT consensus. CoRR, abs/1908.11810, 2019.
[2] Q. H. Nguyen, A. Cronje, M. Kong, E. Lysenko, and A. Guzev. Lachesis: Scalable asynchronous BFT on DAG streams. CoRR, abs/2108.01900, 2021.