Protocol Berg v2: Nikita Polianskii - Starfish: push based dissemination can be efficient

Yeah, it's working. Thank you for the introduction. So now I'm going to talk about some uh high performance uh consensus protocol and it's good that we have a talk at in the evening because we already touched so many topics starting with uh the consensus workshop in the morning about multi proposal protocols and data availability layers just by early. 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 the magic of eraser codes to amortize the communication complex complexity of the of the whole protocol. Okay, let's start from the just general picture.

So we consider a typical blockchain uh 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 first came to one of the validators and when it gets sequenced in the lock by all correct validators. So we are focusing on so-called like ordinary task or just consensus task. We consider a bizantine environment meaning that some nodes some meditators can be faulty.

It means that they can deviate from the behavior arbitrarily but there is at least quorum of correct nodes and typically to many protocols we look at partially synchronous model mean that until some moment called global stabilization time the communication is completely asynchronous and then this moment is unknown and after that moment the communication finally gets synchronous with the predicted delay delta which is usually a protocol parameter that is used for timeouts. So in the solutions that I will describe, we will use direct cyclic graph as a communication and logical layer and basically we'll come to the decision how to sequence all the transactions using one data structure. So and typically inside one block we have several fields like which round which who is the author of this block who are ancestors who are parents probably transactions probably transaction commitments and we also have signature. So in here we have uh several rules on how we construct the duck. So 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 lastly, as I said, we will use only the duck structure for sequencing.

And typical for this area, and it's like in spirit of PBFT style protocols, we choose some nodes to be leaders in certain rounds. And these nodes will create blocks. And if you'll find in the duck a special structure then we'll say okay this leader block is committed and then I can slice the duck using this leader block using all the references and I can then segments all the transactions in all these slices that I'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 uh some references included in the block and we need to have this links to the leader from the previous round. One thing that I probably didn't mention is that uh 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 say 100 maybe up to 200 but it's the system just that optimize for low latency. Okay. And next thing is that there are typically just two types of ducks that considered in the literature.

The first one is like certified ducks where each block is can be seen as certificate meaning that uh before adding this such a block into your local duck you need to ensure that this block is already well dissipated and uh the block creator is basically responsible for providing such a certificate. So first it send the block then collect the signatures and then send back the certificate. So here here usually in production we use consistent broadcast for theory you need to use reliable broadcast 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, all 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 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 this transaction is included in some block on 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 dark.

We will need to maybe exclude equations when we'll just do sequencing. But in general, this method allows for equocations. 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 uh creates a new block A6. And now just thinking okay what shall 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 lightness of the protocol I need to send this potentially missing blocks to validator D. This is okay just but the the problem of course is in the communication complexity. So you need to send basically every block between every pair of peers. It's too much expensive for us at the practical solution.

So if you look so at the M city protocol what is was suggested is just okay let's just stream or broadcast our own blocks and if the peer doesn't know some of 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 the perspective you cannot do this and here is the issue which happens not only in theory but it al 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 like the rules.

But for some reason the slowly later just got connected only to one pier. And then it sent 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 uh validator A is just thinking okay if we I use pool based dissemination then I going to send only my own block to all others and this block is sent to predator C and D but let's look just what happens on the from the perspective of data 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 uh pooling strategy takes a lot of time to collect all the missing ancestors and that's exactly the issues that we going to solve. So on one hand we don't like podatic complexity on the other hand we don't like poolbased 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 pushbased dissemination and here just uh two ideas that we use here. The first one is we want to decouple the block structure and we want to have separately transaction data in the block header. So it's usually how it's done in many protocols because in my city transaction 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 size.

It's probably of size 3 kilobytes or something. And the headers are sufficient to drive the consensus. It's sufficient just to continue progress of the D 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 acknowledgements 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 in block header we need to also include acknowledgements. This like a new field that we need to have.

The second idea just because the 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 going to encode transaction data using uh say relevant codes. So let's say that we have information. So we have transaction data we divide into information shards and it coded into parity charts. So altogether we have n charts and basically each validator is then responsible for its own chart for broadcasting its own chart.

So when you are block creator then you definitely need to share what you are aware of pull transaction data to every other validator. But if you are not a block creator then responsible for only one chart. And of course you need to have some kind of proof just to show that it's uh part of the full encoded code word. Then when you just uh want to have access to the data then you either receive this full data from the block creator or you can decode from any f plus one shots here for sequencing already we need to have two f+1 no acknowledge in this data is available because previously I told that it's sufficient to have f+ one but for this solution we have two f+ acknowledgements because f nodes could lie Okay. And we have at least F+1 nodes.

They will share these shards and we can decode the data from F+1 charts. That's the reason. And let's uh 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 with our block.

We going to send the block headers and we also will include the shard corresponding to our index. So in this case we'll send the charts for blocks P5 and C5 if we have the data a locally available. So let's take a look then how we going to when we 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 bit later validators just say okay 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 going to send my encoded chart to everybody else or maybe I can send it later if you will pull it from me. The next step we have again leader block. So the leader block needs to rep observe at least two f+1 acknowledgements and uh the rest is basically what we have in uncertified duck approach in cordial miners in mystic set. We 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 is behaves dishonestly and does not provide the data to the validator B then B if it knows it sees that from the D structure that transaction from the block C1 should be sequenced then it should have at least two shards sent by correct gradators. That means that letter 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 uh a G distributed network. We have 100 validators, 10 regions and half of kilabyte transactions. So first you can see certified duck selffish. It's like the state-of-the-art protocol which provides the lowest latency cross certified ducks.

And you can see that as I said before when we we look at the end to end latency then certified ducks they grow slowly and the transaction is getting included in the block much slowly than in uncertified ducks. We also have here uh a red curve and it basically responds to the protocol called corial miners the first in this class and it use really a pushbased uncoded dissimination 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 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 mist setting which is which uses pullbased strategy. As I said for starfish we need so-cal acknowledgement steps that the nodes say okay I have this data and this is the reason why for low load we have uh better performance for mystic set but interestingly enough for large load we have better performance for starfish and primarily the reason for this is because in such In network when we deal with large transaction data we don't necessarily have this triangle inequality and the data sent by with A to B and C can be achieved by C faster as a block header when B receive 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 just were thinking about this problem is from practical perspective because it gives much more robustness against some misbehavior or when the some validators have bad connection and for instance if we have just one Byzantine validator and we have some specific uh behavior then we can increase the enter latency for Mr. protocol whereas it become whereas it's quite stable for any number of validators in starfish and finally just if you look at the all the recent protocols that's proposed in the last say four years we can just see here then starfish achieves linear amortized communication complexity and the end to latency is like 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 uh uncertified duck based protocol. It has quite low latency. It uses pushb based block dissemination and we incorporate rich slammon encoding in this dissimmination process. It achieves lowest latency in the class of duckbased protocols with linear amortized communication complexity and it has much better robustness against some bizantine attacks than other uncertified duck protocols. Yeah, thank you.