# Starfish: push-based dissemination can be efficient on uncertified DAG

- Channel: [ETHBerlin](https://streameth.org/ethberlin)
- Date: 2025-06-19
- Duration: 21:57
- Watch: https://streameth.org/watch/685422a390bd41297b663967

## Description

Current DAG-based BFT protocols face a critical trade-off: certified DAGs provide strong security guarantees but require additional rounds of communication to progress the DAG construction, while uncertified DAGs achieve lower latency at the cost of either reduced resistance to adversarial behaviour or higher communication costs.

## Transcript

It's working. Thank you for the introduction. So now I'm going to talk about some high performance consensus protocol. And it's good that we have to talk in the evening because we already have multi-proposal protocols and data availability layers. So what I'm going to talk about some high performance BFT protocol in which we integrate some data availability solution and we also make use of the magic of arranger codes to amortize the complexity of the whole protocol. Okay, let's start from the general picture. So we consider a typical blockchain scenario where we have clients, they are connected to some validators, they create and submit transactions. And the goal of validators is to sequence, execute transactions and then send the result of the execution back to the client. And for this talk, we will mostly focus at the moment when the transaction source came to one of the validators and when it gets sequenced in the log by all correct validators. So we are focusing on so-called like ordering task or just consensus task. We consider a Byzantine environment, meaning that some nodes, some validators can be faulty. It means that they can deviate from the behavior arbitrarily, but there is quorum of correct nodes. And typically, to many protocols, we look at partially synchronous model in that until some moment of globalization time, the communication is completely asynchronous. And then this moment is unknown. And after that moment, the communication finally gets synchronous with predicted delay delta, which is usually a protocol parameters that is used for timeouts. So in the solution that I will describe, we will use direct cyclic graph as a communication and logical layer. And basically, we will come to the decision how to sequence all the transactions using one data structure. So typically, inside one block, we have several fields like which round, who is the author of this block, who are the ancestors, who are parents, probably transactions, probably transaction commitments, and we also have signature. So in here, we have several rules on how we construct the data. The first rule is basically we try to create a block in each round. And all honest, all correct nodes should create the block in each round. The second rule is that we shouldn't progress ahead of the network. So we need to wait until a quorum of the network already created blocks from the previous round. This means that we have kind of like cordial progression of the whole duck, we just respect the network. Otherwise, our blocks will not be considered as valid. And typical for this area. And it's like, in spirit of pbt style protocols, we choose some nodes to be leaders in certain rounds. And this nodes will create blocks. And if you'll find in the dark special structure, then we'll say, okay, this block is committed. And then I can slice the duck using the leader block using all the references. And I can then segment all the transactions in all the slices that they'll have after cutting the duck. So and what's important is that we wait not only for the quorum of blocks from the previous round, but we also wait for the leader block in the previous round, because in our duck interpretation, we'll use some kind of like virtual votes, some references included in the block. And we need to have this link to the leader from the previous round. One thing that I probably didn't mention is that we want to have a really low latency protocol. And all the validators will be connected with each other. So meaning that we need only one hope just to send a block from one validator to another validator. That means that our network is not just huge, it's of size 300, maybe up to 200. But the system just optimized for low latency. Okay, next thing is that there are typically just two types of ducks that can fit in the literature. The first one is like certified ducks, where each block can be seen as a certificate. Meaning that before adding such a block into your local duck, you need to ensure that this block is already well designated. And the block creator is basically responsible for providing such a certificate. So first it sends a block, then collects the signatures, and then sends back the certificate. So here, usually in production, we use consistent broadcasts. For theory, you need to use reliable broadcasts for block dissemination. But as you can see, it requires much more rounds to construct such a certificate. So usually you need two, three rounds to construct a certificate. And that results in higher latency compared to so-called uncertified ducks. In uncertified ducks, we basically receive a block from some peer, and we check that we have all the parents of the ancestors of this block. And we know all the causal history of this block. And after that, we optimistically include such a block in our local duck. This allows us to progress the duck construction much faster. And eventually, it results in lower end-to-end latency. Because if we just receive a transaction at some point, then the transaction is included in some block on a much shorter time in uncertified ducks rather than certified ducks. But what is the caveat of uncertified ducks? Definitely, we could have equivocation blocks. So for instance, here, the node D created two blocks and sent one block to validator A and one block to validator C. And since we include blocks optimistically, both blocks will survive in the duck. We will need to maybe extrude equivocations when we'll just do sequencing. But in general, this method allows for equivocations. But this is not the only problem. The other one is related just to how we broadcast the blocks. In theory, if you want to prove things, then let's look from the perspective of node of validator A on top. It creates a new block, A6. And now just thinking, okay, what should I send to validator D? Because validator D, from my current perspective, validator D doesn't know block B5 and C5. And then to ensure just liveness of the protocol, I need to send this potentially missing blocks to validator D. This is okay, but the problem, of course, is in the communication complexity. So you need to send basically every block within every pair of peers. It's too much expensive for us. The practical solution, so if you look at the Misty City protocol, what is suggested is just, okay, let's just stream or broadcast our own blocks. And if the ancestors, then it should pull it, and we will send them. It looks fine. I mean, on the practical terms, it looks fine. From theoretical perspective, you cannot do this. And here is the issue, which happens not only in theory, but it actually happens quite often in practice. Suppose that we have a slow validator, say here validator B is slow, and it creates its own chain of blocks. They all valid, they all satisfy the rules. But for some reason, this slow validator just got connected only to one peer. And then it sends this chain of blocks to only one peer, who created a block in the next round, and reference this hidden chain, orange chain of blocks. And then this validator A is just thinking, okay, if we are useful based dissemination, then I'm going to send only my own blocks to all others. And this block is sent to validator C and D. But let's look at what happens from the perspective of validator C. It just receives this block from guy A, and it understands, okay, there is a missing ancestor, I need to request it. Then I need to request another ancestor. So and this pooling strategy takes a lot of time to collect all the missing ancestors. And that's exactly the issue that we're going to solve. So on one hand, we don't like quadratic complexity. On the other hand, we don't like pool-based dissemination. So one thing is good, probably in theory. Another thing is good, probably in practice, and we want to achieve linear amortized communication complexity. And we want to use pool-based dissemination. And here are just two ideas that we use here. The first one is we want to decouple the block structure. And we want to have separately conduction data and the block header. So it's usually how it's done in many protocols, because in MistyCity, conduction data was included, it was part of the blocks. And it's helpful because then pushing the block headers is much simpler, they are not of great types, it's probably of size three kilobytes or something. And the headers are sufficient to drive the consensus. It's sufficient just to continue progress of the DAG to sequence blocks, sequence transactions. And if, say, we don't have some data, then we can pull it. But what's important here, since we separate these two things, transactions from the block header, we need to ensure that the data was well disseminated. And since we could have up to F faulty nodes, we need to have some kind of acknowledgments from the nodes that the data is locally available to them, and then we can at least pull the data from them. So it means that the block header, we need to also include acknowledgments, like a new field that we need to have. The second idea, just because the first idea is enough to make pushing strategy in practice, but the second idea is needed to improve, to amortize the communication complexity. So now what we are going to do, we are going to encode transaction data using the Ritz-Salomon codes. So let's say that we have information, so we have transaction data, we divide it into information shards, and it's coded into parity shards. So altogether we have n shards, and basically each validator is then responsible for its own shard, for broadcasting its own shard. So when you are a block creator, then you definitely need to share what you are aware of, full transaction data to every other validator. But if you are not a block creator, then you are responsible for only one shard. And of course, you need to have some kind of proof just to show that it's part of the full encoded codeword. Then when you just want to have access to the data, then you either receive the full data from the block creator, or you can decode from any other function. Here, for sequencing, already we need to have two F plus one nodes acknowledging this data is available, because previously I told that it's sufficient to have F plus one, but for this solution we have two F plus one acknowledgements, because F nodes could lie, and we have at least F plus one nodes. They will share the shards, and we can decode the data from F plus one shards. That's the reason. And let's look on how we broadcast in this case. So let's say again we just created a block, A6. What we are going to broadcast together is our block. We're going to send the block headers, and we also will include the shards corresponding to our index. So in this case, we'll send the shards for blocks B5 and C5 if we have the data locally available. So let's take a look then how we're going to, when we're going to sequence transaction data. We're going to sequence it in the following case. So let's say that we have this block C1 with some transaction data inside. Then this block is broadcasted to other validators, and in the next round, or maybe a little later, validators just say, okay, hey, I know this data from this block, and I acknowledge it. So it will be part of the block header, and it means that I'm going to send my encoded shard to everybody else, or maybe I can send it later if you put it from me. The next step, we have again a leader block. So the leader block needs to observe at least two F plus one acknowledgements, and the rest is basically what we have in unsatisfied DAC approach, in Cordial Minus, in Insta Safety. We have some virtual votes, which is part of the block headers, and we construct, we treat some blocks as certificates for the leader. So in total, we need to have like five rounds to sequence the transaction data in block C1. And in case like C behaves dishonestly and does not provide the data to the validator B, then B, if it knows, it sees that from the DAC structure that transaction from the block C1 should be sequenced, then it should have at least two shards sent by correct validators. That means that the leader B, in this case, will be able to reconstruct the data. Okay, and let's go finally to the results that we have. So let's look first at this picture, and here we have a GAO distributed network. We have hundreds validators, ten regions, and half of kilobytes transactions. So first, you can see certified DAC, Tailfish, it's like the state-of-the-art protocol, which provides the lowest latency across certified DACs. And you can see that, as I said before, when we look at the end-to-end latency, then certified DACs, they grow slowly, and the transaction is getting included in the block much slowly than in uncertified DACs. We also have here a red curve, and it basically corresponds to the protocol called Corel Miners, the first in this class, and it uses really a push-based uncoded destination strategy. And it's very expensive. You can see that basically we can hit the bandwidth limit immediately, even at 10k transactions per second. It's too much expensive. So again, on the x-axis, we have the throughput. For y-axis, we have end-to-end latency. And if you look at the two other protocols, so green one is Starfish that I presented, and the blue one is just the best in the class for especially low-load nifty setting, which uses pull-based transition. As I said, for Starfish, we need so-called acknowledgment steps that the nodes say, okay, I have this data, and this is the reason why for low-load, we have better performance for nifty setting. But interestingly enough, for large load, we have better performance for Starfish. And finally, the reason for this is because in such a network, when we deal with large transaction data, we don't necessarily have this triangle inequality. And the data sent by visitor A to B and C can be achieved by C faster as a block header. When B receives a block from A, then B can send the block header much faster than the block sent by A arrives to C. But the reason why we're thinking about this protocol is from a practical perspective, because it gives much more robustness against some misbehavior or when some validators have bad connection. And for instance, if we have just one Byzantine validator, and we have some specific Byzantine behavior, then we can increase the latency for the protocol, whereas it's quite stable for any number of validators in Starfish. And finally, if you look at all the recent protocols that's proposed in the last, say, four years, you can just see here that Starfish achieves linear amortized communication complexity, and the latency is significantly lower than all other protocols can achieve in this class, which has linear amortized communication complexity. Okay, that's the summary of my talk. So today I just talked about unspecified DAG-based protocol. It has quite low latency. It uses proof-based block dissemination, and we integrate RISC-LMON encoding in this dissemination process. It achieves lower frequency in the class of DAG-based protocols with linear amortized communication complexity, and it has much better robustness against some Byzantine attacks than other unspecified DAG protocols. Yeah, thank you.