Brief Announcement: DAGs for the Masses

We use the standard BFT system model. For simplicity, we assume $n=3f+1$ participants $\mathrm{\Pi }=\{p_1,\mathrm{\dots },p_n\}$ (or validators), up to $f$ of which might be Byzantine faulty. We assume partial synchrony with a known upper bound $\mathrm{\Delta }$ on the network delays after GST and a (polynomially) computationally bound adaptive adversary.

We implement the Byzantine Atomic Broadcast [14] (BAB) abstraction satisfying the standard properties: Validity, Agreement, Integrity, Total order.

Our protocol is based on the partially synchronous version of Bullshark [16, 17].

Pseudocodes of both Bullshark and Sparse Bullshark with highlighted modifications can be found in the full version of this paper[2].

During periods of synchrony, all blocks created by correct validators in odd rounds will link to the anchor of the previous round because of the additional timer delay before creating a new vertex. Therefore, all anchor nodes by correct validators will be committed. The frequency of anchors being committed in Sparse Bullshark is the same as in the original Bullshark.

However, as the anchor node in Sparse Bullshark only references D nodes from the previous round instead of $n-f$, the protocol incurs additional inclusion latency: the delay between a vertex being broadcast and being included in some anchor’s causal history. Assuming that each node has its parents selected at random from the previous round, the exact delay will follow the rumor-spreading pattern.

We provide a simulation of the inclusion delay (in terms of DAG rounds) in Figures 1(a) and 1(b) for 1000 and 10 000 users respectively. For example, selecting $\text{D}=70$ for 1000 users or $\text{D}=190$ for 10 000 users is enough to ensure that 95% of nodes will have inclusion latency of at most 2, i.e., will be referenced by some node referenced directly by the anchor. In contrast, Bullshark has inclusion latency of $1$ for the $n-1$ nodes referenced directly by the leader and $2$ (assuming random message ordering, with high probability) for the rest of the nodes.

We estimate the per-node metadata communication complexity. In Sparse Bullshark, each DAG node contains up to $\text{D}+2=\mathrm{\Theta }(\lambda )$ references to other nodes compared to $\mathrm{\Theta }(n)$ references in Bullshark. Each reference is a certificate for the corresponding DAG node and its size is:

• $\mathrm{■}$

  $\mathrm{\Theta }(\lambda )$ in case threshold signatures are available;

• $\mathrm{■}$

  $\mathrm{\Theta }(n+\lambda )=\mathrm{\Theta }(n)$ in case multi-signatures are available;

• $\mathrm{■}$

  $\mathrm{\Theta }(n\lambda )$ otherwise.

We will denote the size of a certificate by $C$.

In Sparse Bullshark, the metadata of a node consists of $\mathrm{\Theta }(\lambda )$ references and a bitmask of collected quorum (sampleProof), so metadata size for each node is $\mathrm{\Theta }(n+\lambda C)$. In contrast, in Bullshark, the metadata consists of $\mathrm{\Theta }(n)$ references, so the size of a node is $\mathrm{\Theta }(nC)$.

Practical implementations rely on a combination of Signed Echo Consistent Broadcast [7] with randomized pulling[10, Section 4.1]. This approach allows us to surpass the theoretical bound on deterministic Reliable Broadcast communication complexity [12] and achieve linear expected communication complexity. With this approach, the expected communication complexity is $\mathrm{\Theta }(n^{2}C)$ for Bullshark and $\mathrm{\Theta }(n^2+n\lambda C)$ for Sparse Bullshark. Refer to Table 1 for the exact complexity and example DAG node sizes depending on the choice of cryptographic tools.

We evaluated our Sparse Bullshark protocol using a simple simulator implemented in Python. We used emulated message delays with ($50$, $10$)-normal distribution for $99\%$ of messages and ($500$, $10$)-normal distribution for a randomly selected 1% of the messages. We limited the network bandwidth of each simulated validator to emulate real life limitations of network bandwidth. Our goal was to evaluate the resources consumed by our protocol on the metadata exchange, compared to Bullshark [17].

Figure 2(a) shows the throughput of the protocol in blocks committed per second depending on the sample size for various per-node network bandwidth limits. We can observe that small sample sizes dramatically increase the throughput, allowing the protocol to be scalable when, under the same conditions, Bullshark saturates the network and does not scale.

Figure 2(b) shows the change in latency depending on the sample size for various per-node network bandwidth limits. Despite the theoretical result of increased latency in terms of message delays, we can see that in many cases under limited network bandwidth, commit latency actually decreases significantly due to sampling.

Evaluations confirm that while the sampling significantly decreases the amount of metadata transmitted through the network, which also leads to a decrease in latency when the bandwidth restriction is below a certain threshold.

Due to the limitations of the simulator implementation, we only tested a relatively small system size of 100 nodes with small sample sizes. However, the same trends will apply to larger systems, with proportionally larger sample sizes as well.