L9 - Algorithms for Transaction Ordering | by Prabhat | BlocSoc Lecture Series

Transcript

so today's lecture is on transaction ordering algorithms and me so basically with transaction or ordering algorithms is used in sequences where sequencer node uh like orders the transaction to get the maximum economic benefit and there are many algorithms that we can use for all ordering the transactions and we will be discussing here some of the most known or most used algorithm that are currently being used in this area so uh first of all yeah we will be

starting with transaction ordering and the first one is first come first serve algorithm so as the name just uh the first uh it is like ordering a transaction in in the way where when uh suppose trans uh transaction sorry in suppose transaction a came and that way let's say after came transaction b c and d so in the block

when the sequencer is mining the node uh it it will be uh the first transaction that will be included will be transaction a then transaction B and C and D so there is no like uh the first of all the selection of the algorithms is based on the priority order of uh High fees or high gas price that the like transaction the that the person who uh like submitted the transaction is paying and after the transaction are selected uh they are ordered in this first first ter algorithm and this just

is like the main here is to like tag the transactions as much as they can and also like do it in a most efficient way possible the so second transaction second ordering mechanism that we'll be learning is like permited graphical Arrangement so here the transactions are treated in a way uh where like yeah first of like the transaction are treated like a graph structure so they are like some kind of relationships uh in the transactions for example some transaction maybe the

parent transaction of some other transaction that is included right now in the mol and and uh so this in this way we are like establishing a graph like relation in between them and then then we order order them in a like some fashion most of like most popularly known as nested dissection where they are dissected or like arranged in a recursive fa fashion like there are three algorithms that are particularly used in like executed pgaas so first is cilmi algorithm second is

nest dsection and third is vierse Cil Mei so I'll be talking about nested dsection here uh uh I can use see this screen like I'll I'll share the wait I'll share the entire screen like can you see this desktop like the Whiteboard yes okay

so in PDA like suppose the transactions are in this manner it's say a b c and there are like suppose end transactions in this way what what happens is uh now I have first selected end transactions on the basis of the priority gas fee that the person is paying me and now what I'll do is after I've selected these M transactions I'll like order them in recursively for like for most bandwidth efficiency and

like uh I just break it into two parts and by two and by two transactions so this is kind of like a divide and conquer algorithm that is like you will be most known with so now the this bigger problem of ordering these end transactions is now broken down into uh like solving two sub problems with then n by two and n by2 and now recursively this will be called here same function and after that this again will be broker into pieces of n

by4 n by4 and n by4 both of these as well so this goes on as n by 2 whatever becomes K one and on this is the like base level where the transaction is sorted in itself and then it like goes back again and recursively computes the answer and so this is how it works first and transactions are there they have broken down into n by two and N by two now this goes

on this is kind of like a binary tree and after the execution is completed at leave nodes they come back and then we get a ordered transaction this here is the answer this is how like nction is working yeah yeah this is about pgs and then comes transaction naral and bull chart this is uh recent Al transaction algorithm with the new

like analysis cons bft consensus that is is like introduced in a recent paper in 2022 I think Aptos is the one that came up with this and it is currently being used in stocket so here we are like considering the meol as a like direct cyclic graph based C structure a dag based structure uh and the transaction ordering here is kind of complicated so I like break it down it in more easier fashion so what happens is now

that uh there is a new vft consens consensus mechanism here so what happens is like consider these as nodes these nodes as validators and this is one particular round so this is R round r+ 1 round r+ 2 round R three and so on so what happens here is they are connected like in any manner this is a like dag so there won't be Cycles in

it so like I'll just be I'll be connecting this one now this one only for demonstration purposes yeah so right now we have four of these node nodes or validators that we have so there is an execution that happens in like odd Round And even rounds so the transaction ordering happens based on an anchor the anchor is the leader LOE that is selected uh just in

uh like the leader note is selected in the even rounds and from the even rounds when the leader nodes are selected in the odd round their transaction inclusion or transaction ordering happens in this round so I just say like this is my leader node for this let's say r+ 1 is like E1 and here I'm picking this as my leader node this is known as an anchor node where I'll be anchoring my transactions off

so what happens in bft is you need to have Suppose there are F by generals so you need to have f+ one support to like execute something in a P2P or P2P Network or decentralized network so this is common knowledge in uh like blockchain so now we know there we need two nodes here to select like validate that we will be interacting or will be included this Noe so this is the odd

round and here I'll be like uh connecting these nodes for itself okay so I can see that there is one node that is connected with the leader here this node is counted as a vote so in the odd round these nodes will vote uh for the like this leader note if they have a connection with them so since this node has a connection with this node it will vote for it but since

this is not enough because we need two votes we will not include any transactions in it whatsoever for now so a new leader will be selected here suppose this is the new leader and I'll assume that this God support from the next two notes and it got two vs what will happen is now this will look first of all if uh there is uh this condition which happened here that it did not get full node like full support

of f+ one participant nothing will execute and it will like execute it in the next OD round if the condition meets so now now that the condition has met it will look for uh uh like a path so that this leader node leader two is connected with leader one in some manner so this path uh like right here and I'll suppose that it is also connected with this this path right here this is a path that we can connect with this leader node and L1 node so what will happen is uh this leader node

was let's say connect uh is connected with this mode so all the transactions that happen here all the batch of transactions that happened in the like interaction between these nodes will be in included in the block that will be mined by L1 or by L2 in this OD round and after like suppose r+ 4 andr plus fifth round when there is another L3 and this is connected with L2 all these transactions that are there like all

these will be included because I can trace back these nodes uh with this node here uh and I'm I'm supposing here that this is the only uh connection that I'm that I have for this L2 node here uh and after this execution all these transactions all these uh batches here batches of transactions will be included in the block and this will go on and on and on uh for forever and this is how like the uh transactions will be selected for

ordering and after that it is just high pce and high gas prices that uh will be like the factor where uh we will see that which of these notes that which of these transactions that we have in the mol will be included in the BL so this is all for narval chart now we will go into Ms yeah so initially it was known as minor extractable value because only the minor were able to extract this uh but now since we have PA like to host

network uh it is now known as maximal extractable value which means that the maximum amount of profit the maximum amount of financial profit that the block producer can get by manipulating or ordering and arrangement of transactions in a block so we can the validator can include or exclude any amount of transactions from the M Pool and like he can he or she or the validator can choose where he's getting the most profit from so now uh this is M and these generally are the transactions that have high fees

because these will be the one uh transaction these will be the transactions where the validator will be getting the most uh benefit from so there are also the participants in the network Searchers so what Searchers do is they are like always looking into the mol and they have the BS and algorithm to detect these high juicy transactions for high MV opportunities and like they extract uh like they have an extraction process automated for this and these that is why they are known for they are

known as searches because they are always searching for these transactions in the m and once a Searcher like has seen uh transaction where there is high me opportunity but that Meb bot will do is included include a similar transaction with higher fees and uh then since the fees are higher there is a higher chance that the that that the MB Bots transaction will be included and that original transaction will be excluded from the Block so this is how

they play and uh there are a lot of M BS so what happens is uh suppose bot is getting a $100 of benefit from the uh MV opportunity the bought will uh like uh give off approximately 90% of its profit uh to the validator because uh of the the competition from other Bots if like it goes for a 10% uh benefit to validators and 90% to itself but the bot

will come with the 20280 ratio this like percentage is included in the fees itself or like the gas price that we have uh so this is how like they distribute the uh they distribute the profit uh every time the anyways the validator will be getting 100% of its profit because it doesn't mind just that the me will try to like uh gain of the uh Financial benefit that the uh bought can gain from this that

transaction so there are many examples that the that these MB BS do they do what they do is Dex Arbitrage so in Dex Arbitrage what happens is suppose there is a transaction in un app and there is uh suppose uh person willing to give one e for let's say usdc what will happen is the bot will

come and PR turn and transaction let's say transaction X and also will give a transaction that will be included after this transaction uh transaction y let's say this will be with higher fees higher gas price and this will be with lower gas price and what will the do is change this ratio so there is always a slippage tolerance uh in uh like this swaps that happen so it will the BS will try to uh push of

the uh like trans transaction to the maximum slipage that can go and like take all the uh this uh uh difference in price that is created and then they like uh take the advantage of this and make profit with it also there is liquidation so some let's say that someone some person's position got liquidated so their uh assets are now up for sale for like really low prices the BS will come up and will give like high gas

prices to buy off these assets uh that are like there for very low prices and this like helps in very fast liquidation uh by the these M wats uh also there are sandwich attacks like this is also kind of a sandwich attack that I uh explained this Dex arbitary attack and also there is front running so if there is a transaction that is happening like that is like not happening like that is included in the M Pool and the this bot sees the opportunity of like exploiting this transaction B will do is create a

similar clone of this transaction with the higher gas price and since this is higher gas price and they are similar this will be executed and this will be not so this is how TR ring happens yeah the good and bad so m is both good and bad in itself so good is uh like this Dex Arbitrage ensures that they get correct prices for their token so like in this way if this happens like constantly and even the M BS are being M some sometimes so this problems is kind of mitigated always because if there is

some M Bard that that is trying to push this slipage tolerance to the right there there will always be a another board that will like push it to the opposite end and this kind of maintains the price at the middle this is like some kind of basic and basics of how this goes then and this Landing protocol as I explained liquidations happen very fast so there is a uh position with has gone the gone below the liquidation ratio uh this will be liquidated very fast and will not that position will not be there for too long

and will not be like in a worse situation forther the bad of me is uh like this sandwich attacks uh at the time of sandwiching even if the other users are getting a fair price the person who got sandwiched will get a like increased slippage and like you will be in a net negative position with this trade and this is kind of bad and uh this generalized gas uh gas like this frers uh that like are in that scenario generally generally increase

the gas price uh of the trans to execute the transactions because there there is always a of like getting front Rend by an M bought so this like is a net negative for the ethereum ecosystem and like they because of M me Bots there will always be uh like scenario we have to pay higher gas gas prices and uh one instance with this is that when the M boost was introduced the there was like 50% reduction in gas prices and maybe boost

and and maybe auctions when were introduced 50% of the gas prices were like reduced at the time now that the solution for this is like using flash BS and maybe boost and there is a proposal Builder architecture uh in the in ethereum you can like uh search for it these are the current solution that we have for like for the mebs and yeah these are the references for it and this is all about the presentation yeah if anybody has any

questions