Cryptoeconomic Security for Data Availability Committees w/ Ertem Nusret Tas | a16z crypto research

Transcript

I'm very happy to introduce nisratas who's a PhD student at Stanford uh doing all kinds of great work on David Chase group um so very happy to have him here and Mr the floor is all yours okay let's get started then um yeah uh thank you for inviting and joining the seminar and I will be I am uh I am Nusrat Thai and um I will be talking about crypto economy security for a data availability committees that I will refer to as Dax for sure um and this is joined to work with Professor Dan Bonnet here at Stanford uh let's get started so I would like to start with a survey

of the data availability landscape on Layer Two so we here have a graph of a trust versus the cost for the layer 1 blockchain which many of these layer 2 systems depend on so the first solution that comes to mind in the data available the landscape is on chain data and this is a concept encapsulated by Roll-Ups and some examples include stock net and Z casing so in the solution the data is simply put on the layer 1 chain so as a result the cost for the layer 1 chain is high but the trust is also High because the layer of one chain is trusted for the security of the layer to the applications an alternative solution is to use an off-chain data availability committee or

DAC for short um to store the data so these dacs are used to um perhaps store the data for temporarily and to make it available if they are needed by the applications and this is a concept encapsulated by validiums such as stockx and ZK Porter there are new ones like eigen layer um so the cost for the layer one chain is much smaller as compared to the on-chain Data Solutions but the trust is also smaller because we now have to trust an external set of entities that we call the DAC um to persist the data uh by the way please interrupt whenever you have any questions or if anything is unclear and enable the emerging Paradigm in this

space is off-chain data with data available to sampling so in these Solutions the data is again uh I delegated to an external set of validators but these validators uh persist data in the form of a separate blockchain like uh like the Celestia blockchain or polygon male and these Solutions typically support our data availability sampling this datability sampling solution enables unlike clients to verify the availability of the data without downloading the full blocks in these uh of off-chain blockchains and here as this uh figure indicates there is an inherent sort of problem with the data availability committee

solution namely the low level of trust that we have on these Solutions as compared to the on-chain data at the point and this indeed constitutes the heart of this presentation ideally security of L1 architecture relies solely on the L1 blockchain this implies that we cannot simply trust the daily availability committees because that would mean that we would be introducing an extra trust assumption on the security of the L1 architecture and in particular abolitions that can promise to preserve the data but simply delete it because it's more profitable to not spend the effort on persisting the data luckily there are solutions like proofs

of custody through which these lazy DAC members can be slashed and they can be reliably punished and the key word here is reliable the other line of attack and militias that can do is to basically promise to reveal the data whenever the data is query but simply withhold it even though it has the data in its memory and it might do this because it might try to extract some Ransom out of the um querying clients unfortunately unlike the lazyback members um problem there is no solution to Reliable slash the data with the committee members in the case of such attacks and the reason why there is no reliable there is no solution to rival slash them is something called the

fisherman attack so fisherman attacks tells us that the lack of data cannot be provably punished in without the existence of a trusted third party by the way I took this term from a blog post by vitalik so I I don't know like what is the exact term for this this attack some people just call it the um non non-accountability of data available to attacks but let's go with the fisherman attack because it's much shorter and uh let's let's see why this is the case why we need to trust the third party and uh as almost all of the impossible results and consensus work this is a indistinguishability argument so we have two girls world one and world two that we will that will be indistinguishable in in our video

um if we assume that we are some late coming uh Watchtower to this system so in world one we have a malicious block producer that publishes a Blog but it holds some part of the data upon observing that some of the data is withheld uh an honest client raises an alarm at this point and watch tower intervenes and it starts inspecting the block however as soon as seeing the Watchtower intervene the malicious block producer can publish the missing data and make it look like the block is available or has been available since the beginning of the time so so the malicious block producer made the client look like as if it has a raised a false alarm in World 2 it's the exact opposite the

blog producer is honest and publishes a full blog but the client is malicious and it raises a false alarm and at the end of the day these two roles are indistinguishable in the view of a late coming Watchtower so in order to make them distinguishable we need a trusted party that we trust to have been observing this system since the beginning of the time and that will tell us which one is our honest and which one is adversary okay is it a clear so far why uh withholding data it cannot be uh accountably punished why can't he sign the block and then if they publish it with missing data you can you can prove it um oh so PX does sign the block so we

can think of the block as having a header and the header contains a commitment to the transaction data and then P size this header um but the transaction data itself it can withhold some part of the data um so the question is why doesn't it sign the whole transaction data um that is because then to verify the block everyone needs to download the full blog but we generally want to support like clients so that they don't have to download the full block to verify the block to verify the signature right so that's why what does publish mean here uh it means that it produces the block and let's say let's say we have a blockchain and there it's it's slaughtered and then each slot has a leader and a leader is supposed to

propose a block so it proposes a block um with some of the with some of the data missing and let's say the validators are also dishonest so they all vote for this block even though part of the data is missing and the block becomes finalized and then a client uh upon seeing this blog it cannot get part of the data perhaps part of the data it actually needs so it raises an alarm but at this point the block producer you can publish the missing data and because it doesn't sign the whole data it just signs the header it can always hold part of the data within the blog and publish it much later um is that part clear why size the header because we don't want the client

to have to download the whole block to verify the block yeah yeah um yeah so let's go forward I think that was also a question in the chat that was on the specific point so okay what if the header uses an accumulator that supports proofs of non-inclusion okay so let's say the header has an accumulator and well Miracle trees for instance okay let me think so so hmm I will address this question a little bit later

um I guess I can I will adjust towards the end of the Fall uh I'll just go forward quickly um [Music] yeah I would like to open up parenthesis here about a data availability sampling so a common misconception in the field is that um data available the sampling solves this fisherman attack well this is not correct so what datability sampling does is that it enables like clients to verify the availability of the data without downloading the whole data right it can send some repeated samples sampling requests to the blog producer and blog producer can reveal these uh requested parts of the block and then the client clients will rest assured that the rest of the block is also

available under certain assumptions like a mixed net however these data available sampling Solutions cannot prevent the fisherman attack and it does not make withholding data approvable offense and the reason is because the block producer can simply choose to not reply to any of these queries by the the sampling clients and then the client will conclude that the block is not available and it will complain to let's say a later Watchtower and then when the Watchtower intervenes um the block producer will again reveal their data so this means that does cannot make the withholding data approvable offense you cannot make attackers accountable for their actions and this is exactly where our work uh

comes into the steps in um we propose at that protocol that uses an on-chain contract and financial incentives to deter the dark notes from adversarial Behavior uh here are just the third party is the on-chain contract that lives on the layer one blockchain which we are allowed to trust for our layer 2 application and then we analyze the interaction of the diagnose clients in this contract as a dynamic game and most importantly we assume an adversity that can uh not only corrupt the nose but also bribe the nodes and we will see what what this extra power gives to the adversary um and then we also Define a notion of optimality for the contract and show the

optimality of the contract that we proposed forever foreign the interactions of the participants in our that protocol can be modeled as a dynamic game that involves uh three parties that I have previously alluded to so the first party is the DAC members or the shorts are called nodes for short and they are denoted by uh the notation P1 through p and where n is the number of nodes and then we have a client we that sends a sequence of data queries to the nodes and most importantly we have our contract that lives on the L1 chain and it's used to punish misbehaving notes such as the notes that we hope we hold

the data when the client has a query and uh let's uh make this a model more Concrete in a validium setting so here we have our validium chain that contains the transactions and state commitments to the blocks and we have our parent chain which is our L1 blockchain here so the validium posts the state commitments of its validium blocks under the parent chain along with that proof of validity for the state however it delegates the data or the responsibility of persisting and making sure that this data is available to a committee of uh diagnose and there are end diagonals here we typically assume this data is Erasure content and we will

see why this is a good solution later and these diagnos are responsible to reveal the data upon query and of course we have a client that might send a query to the doc nodes and in this example the query could be a short short request like a inclusion proof for its account within the latest valid State as recorded by the parent chain right we assume that if K or more out of these nodes respond to the client over the network the client using these responses can recover the answer to its query and and then the client is happy and the protocol terminate successfully so here this cape is a parameter of our model and this case determined by the

Erasure rate of the Eraser coding solution okay so this is the rosy setting uh it might as well be the case that there is an adversary that might corrupt some of the that nodes and then these corrupted diagonals might opt to not reveal the data to believe the client right so if there are less than K nodes that respond over the network to the client our on-chain contract steps into the game and our on-chain contract basically gives the client a venue to complain about this lack of data over the network so this complaint is simply the query is sent to the contract and to send the query to the to its contract the client

has to put up a base payment of PC coins so this could be either to cover the um the gas cost of complaining to the layer one blockchain or it could also be adjusted as a parameter to deter spanning clients and to have some leverage over the dark notes uh the complaint contract is assumed to hold a stake of PS coins from each of the dark members the diagnodes okay so upon receiving a complaint uh the complaint contract starts at timer and it waits for a timeout period so during this timeout period the diagonals are responsible to observe the contract

and put their send their responses to the contract uh to avoid perhaps getting punished so if the nodes reply we send their responses to the contract by the timeout period Then the client can simply observe the contract at the end of a timeout and retrieve the data from there and if there are enough responses sent to the contract the client can again combine them to recover the answer to this query and we assume that there is again a cost associated with sending a response to the contract and these cost is taken by the dark notes as denoted by PW and we assume that this PW is less than the collateral state by each node and in reality it could be much less than this

collateral and this could either be the call again the cost of covering the gas cost on the layer one blockchain or it could be it could also encapsulate the cost of generating the correct response to the client's query foreign are you going to go into more detail about sort of this challenge response part yes okay yes and uh if declined uh can get the response the protocol indeed terminate successfully okay so so far I have alluded to the existence of an adversary so let's make it concrete uh

um and let's see what the adversity can do so first of all it can corrupt F out of these nodes and these are Byzantine false it means that it under the control of the adversity is the end if that notes can deviate from any prescribed uh code arbitrarily like and here we assume that f is less than M minus K plus one this is to ensure that uh if the f is if the F parameter is too large then these uh corrupted diagonals can simply withhold their responses and grieve the client up perpetually so we don't want them to be too strong to have any meaningful security and another important observation is that the rest of the diagnose the ones that are not corrupted are rational

so this is the first Power of that verse the second power of the adversity is to offer bribes to these rational nodes so you can offer a total Vibe of P0 coins again P0 here is a parameter of the protocol so the rational loss and in return ask for a favor so these nodes who accept the bribe are not really corrupted so they accept the right only if they think let's say their payoff would be better in the future and uh they would they would um do do whatever whatever the adverse is asking to them and adversity basically tells them hey I'm offering you PC some some fraction of this P0 coins please do this action for me and the node looks into its payoff if it does this action accepts the drive and

then it makes a decision to either accept the bribe or reject that and the same goes for the client the adversity can offer a bribe of P1 coins to the client in return for a favor and we assume that the adversity can have a coordinated plan across this bribed and adversarial nodes and clients so it can make up a plan of let's say coordinating the nodes who accepted the bribe and then the nodes that are already corrupted by the adversary and we assume that each rational node aims to maximize its net utility which is denoted by this function and here x is the payoff at the end of the game and in this talk for Simplicity we consider uh some linear utility function and we

will see how much the results generalized to our discoveries nodes as well okay so what is this adversary doing in this system like what is the goal of the adversity so the goal of the adversary is to violate security that is defined as follows so we say that cheese security is satisfied if the client receives K or more correct responses from the nodes either over the network or through the contract by the beginning of some slot team so here T is the latest late is a parameter for our security and in other words we can express security as being satisfied if the client can recover the answer to its query which requires okay or more correct responses from the loads

okay is the adversary and security definitions clear um if so I would like to again uh briefly open up parenthesis on this K parameter so I have previously mentioned the data is typically erased recorded across these dark members and uh I would like to dwell on the reason why this is the case so the typical numbers for this K parameter are one or n so k equals one corresponds to data being replicated across the whole uh committee members and it means that this every node stores the whole beta but it also gives a higher notion of security because now the adversity has to corrupt or write all of the uh that members the diagnose

uh to violate security on the flip side if K is equal to n this this means data is just divided among the nodes the storage per node would be much smaller because the data is divided so it will scale as of 1 over n however now the security is much worse because it's sufficient for the adversary to corrupt a single node and anything in between these two numbers can be represented by a eraser rate and then in this case k can be denoted as some constant Alpha times n and this corresponds to the solution where the data is first Erasure coded and then divided that among the nodes and this makes the storage per node um a constant within a constant of the

previous one D Over N which is a very little amount and it also makes the system more robust because now the adversary has to corrupt that constant fraction of the loss okay so now that we have seen security we have seen the adversity the nodes and the client uh we need to characterize what this contract does and uh how to and we should we should we should examine how to uh design the best contract and for this purpose I would like to introduce a note sub game that will be a part of the final uh Dynamic game so in this notes of game we assume that the contract receives a query at some slot T So this query is a complaint

right uh suppose a client did not see its respond enough responses over the network so it sends its query to the contract at some slope team so this is exactly the point our nodes of game starts and then the Baseline payoffs at this point for each node is said to be zero and we introduced this indicator variable XJ and that would equal one if the node PJ sensor responds to the contract uh by the next slot or it will be zero otherwise so here I am normalizing the slot to be one and it is this slot the the length of this slot in and reality can be thought of as equaling the length of this timeout period

and it stays basically it encapsulates the um the response of the node to this query over the concept and at T at slope t plus one after a timeout period the game ends and the final payoffs of the nodes are realized now um Perfectly Natural question to ask is uh how should the contract behave if the nodes are responsive or if they are responsive and in general what would be a good notion of optimality for this contract we have a huge design space here how should we narrow down the space and find the best contract okay so here are the parameters we have seen so far to answer these questions we should put some structure on the contract and for

this purpose we will represent the contract by a slashing function so this flashing function is the contracts uh punishment or reward for a node Pi given the actions of all of the nodes including Pi's actions so at slot t plus one then the contract has the opportunity to observe the actions of every node and it basically gives a reward or punishment to each node and this reward of punishment paranoid is denoted by this function f i x and it takes value from minus PS to some positive real numbers so the reason the negative side is kept at PS is because each node has a collateral of PS state in the contract and the contract cannot take away more than PS as a result you're calling it a slashing function

it's really like a payment function right yes it is yeah but the payment can be negative because it can take away the collateral by each node okay um now the the name of the function is actually giving away what the function is going to be doing unfortunately um we will see that it will not actually give any reward um but here here's an example which there does not have to be and is not optimal um according to our future definition so this is in this example the contract simply takes away all of the collateral here minus PS if the node is unresponsive and it gives a reward of one coin whatever the denomination of

the coin is uh if the node is responsive so this is an example contract and um to further illustrate what happens at the end of the game the payoff realized for the note Pi in the absence of any bribe would be this expression basically the reward or the punishment of the contract minus PW times x i so PW times x i means that if the node sends a response the very x i is one then it basically needs to pay PW coins to send a response to the contract and if it doesn't it doesn't pay this okay now let's slowly build towards an uh notion of optimality for this

flashing function which represents the power of the contract so an optimal slashing function has three main features so the first feature is the compliance so compliance is a general set of um properties that we want any good contract to satisfy so it Narrows down our search space to a set of good contracts and amongst them we will find the optimal one later using the remaining two features so a compliant function satisfies these following basic properties so the first one uh is symmetry that is motivated by fairness it says that the function should not depend on the node's identities the second one is no rewards and this is

more contentious but it's this is for economic feasibility it says that the function should not pay out divorce it should only slice the nodes so the reason we impose this constraint is because we want to have a net flow of um money to towards the contract we don't want the contract to lose money second uh if the contract offers rewards to the responsive nodes this this opens up a different attack Vector so in this attack Vector the node can simply withhold its response over the network Force the client to go to the contract and only then it reveals the response over the contract so and this way it gets extra Rewards so we want to avoid this attack Vector as a result we don't want to offer any rewards

the third uh no feature for a compliant function is security under no attack this is a very basic one it says that when there is no bribe uh when P0 is equal to zero uh basically there should be K or more responses in the contract in the sub gain we have seen we will strengthen this uh to construct the optimal slashing function and the final one is B minimal punishment um again this is a this is a more contentious than the rest so this says that for every action where security is satisfied so when they're more okay or more responses are sent to the contract we should have that the contract should not punish the notes too much

uh where it should only punish them by some B coins MLB is a potentially much less than the total collateral so we the reason we impose this B minimal punishment requirement is we don't want to punish our benign errors too much so let's Suppose there is no adversary coordinating the nodes and then someone of the nodes cannot send a response due to some Network outage or downtime um which we have at Stanford of time to time uh uh yeah so in this case we don't want the note to lose all of this collateral or lose a large amount of money just because of some maintenance issue when there is no coordinated attack and security satisfied again in our optimal slashing function we will strengthen this fourth property just

like we will strengthen the third one okay let's strengthen the security so the second feature of an optimal slashing function is security optimality and it says that a compliance slashing function would be security optimal if for all bribes P0 that is greater than or equal to zero there exists a probability q0 that is a probability of failure such that security is satisfied in the north sub game with probability at this one minus q0 in all Nash equilibria of the sub game and furthermore they should not exist any other compliance slashing function with a larger probability of security or with a smaller probability of failure

so is this definition clear so here we are strengthening the third property what's the probability over here uh so the the so we have fixed the right P0 and then we are saying that for each P0 the probability is across we look at all Nash equilibrium of this top game uh given given our optimal contract in each NASA equivalent there is a probability of failure and then we pick the largest one amongst these probability of failures let's say this largest one is Q zero and then uh there should not and I'm saying that there should not be any other compliance slashing function with a larger largest probability of failure

amongst its own Nash equilibria okay is the randomness coming just from mixing over strategies okay yes so the adversity can uh adversely can propose mixed strategies to the knows in return as a in return for its bright for instance adversity can say I'm gonna offer you a bribe and then as a node you don't have to withhold your response but you should withhold your responsibility assertion probability so as an adversity I will just flip a Fair coin and then according to the result of the spare coin you will be told your response or not and the note can basically look at its expected reward and then uh at the end of this game if it accepts the bribe and then make a decision so this is uh

where the probabilities coming from so the probability is also coming from the node mixing across strategies um so these are the two two main vectors so the proof considers both of them um does that answer the question yes thanks so uh yes so Security optimality in layman terms basically means higher price possible security and the last feature of an optimal slashing function is punishment optimality and this is strengthening the fourth requirement this B minimal punishment requirement so a compliance slashing function is punishment optimal if the contract

satisfies B minimal punishment for some B and no other compliant contract can satisfy um B Prime minimal punishment for a smaller B Prime so it means that the com the replenishment optimal comp line slashing function imposes the minimum punishment when security is not violated so these are pretty strict requirements and it might actually turn out that there is no optimal slashing function that satisfies all three properties of security optimality punishment optimality and a compliance well luckily there is one and it is it's actually a very simple one the most most intuitive one given uh all we have seen so far

so this optimal slashing function um does not punish the node if it sends a response to the contract if slashes all of the stake from the node right the nodes all over the state if it does not send a response to the contract and the data cannot be recovered because uh very few notes send the response and in the case that the node does not send the response to the contract yet the data can be recovered from other nodes responses the punishment amount is much smaller it's only slightly larger than the cost of sending a response to the contract yeah so it's it's as simple as that and this function satisfies the our

optimality requirements and uh to state it more formally this slashing function is optimal for both risk neutral and risk-averse nodes and here there's asterisk or these covers because we have considered uh utility functions of the sort x to the new and new zero and one um I don't want to over promise but I have a feeling that it's generalized to a larger set of uh concave utility functions I have to do more work on that um and then the failure probability that we have seen uh the q0 P0 for risk neutral notes on this optimal contract

is this expression um first of all before we go into the expression I would like to remind what is this failure probability so we have our optimal slashing function and we have fixed the bribe amount P0 we know what this problem on P0 is and then uh the adversity can do a lot of different strategies and it can offer different price to different people and ask them to do different things and at the end of the sub game the look at all Nash equilibria and we find the one with the largest failure probability and given that versus Powers and it's this this value and this value is equal to the expression we see here and this expression increases linearly as total

bright goes up it decreases as the minimum number of rational nodes uh that the adversity must break to wireless security increases so this is the minimum number of rational nodes diversity should ask to withhold their data from the contract it can always ask its minions the adversarial ones the already corrupted ones to withhold the data and again this probability of failure decreases as a total collateral goes up because then it means there is more punishment for each node if it withholds its data okay I was I was planning to offer a proof sketch for optimality um but I will I will be a little bit more quick with the pro sketch so well let's cheat a little bit and say

are we already approved our slashing function is a compliant it satisfies these four natural properties and then uh but if we actually try to do this ourselves we will notice that for any compliance flashing function the punishment should be less than the cost of sending your data sending a response to the contract if if the um the node is unresponsive x i is zero and this is necessary for security to be satisfied with overwhelming probability and even when the prime amount is zero so we need this even when the bribe is zero if we have adversarial nodes and this level also implies a punishment optimality of our compliance slicing

function because it indeed uh punishes the non-responsive nodes and an amount that is just below PW and then uh after assuming away all of these properties we only have to prove security optimality of the contract and security to prove security optimality of the contract we first show an upper bound we show that the error probability for our optimal uh slashing function even a fixed P0 is upper bounded by this expression um because of time constraints I will quickly skip this and if we have time and then we will return and this flip side of proving the security optimality is to show that for

all compliant punishment optimal slashing functions this error probability is larger than this expression which this apply this also applies to the optimal flashing function that we have seen as a result it gives the type Bond and these results are purely for the risk and neutral nodes for risk-averse laws we can do the same proofs um but except for the fact that I I don't know how to characterize this expression I can do it for some expression here that will end up being the same but I don't know how to characterize that confused me yes

um this one or the previous one this one yeah um specifically the phrase asks them to collectively withhold their responses would probably cue not peanut so who's flipping the coin so I'll give them a little yes yes that's a very very good question so what the adversary is doing is it tells each of the nodes I'm gonna offer you a bribe and then if you accept the bride I will tell you to do the following thing it will it tells you know I will ask you to withhold your response with some probability but it's the adversity who is flipping the coin because adversity can coordinate across the favors uh that

it has asked from the bribe North and the adversary adversial notes actions so adversarial notes are purely corrupted by the adversity so there is no bribe associated with time they are adverses minions the rest are offered a bribe and adverse they can coordinate across the actions of the ones that accept the bride and the ones that are uh offered that are already corrupted so the adversity can flip a coin and ask all of the knows that accept the bribe to withhold their responses according to the outcome of coin so here there is a big assumption the Assumption being this actually these actions are Atomic right because flipping a coin offering a bribe and not taking the action are not necessarily Atomic so the question of

how we ensure automatically is another part of this Verge so there are two ways we can ensure it first of all we can assume a trust the third product that uh ensures the agreement or atomicity between the nodes uh that are alpha de bribe and adversary or we can assume repeated games and in the case of repeated games we can show that we can sustain an equilibrium where the actions end up looking like atomic interesting so for the first version of that I'd like I almost wonder if like this is more naturally phrased in terms of correlated equilibria as opposed to National equilibria um so that that might be worth thinking

about um and then the repeated game stuff is not just using the folk theorem or yes yes it's just using the fault theorem okay yeah the folk theorem is often viewed as more of a negative response than a positive result but you know what I mean because there's like so many equilibria so yes so the fault theorem is again here and more like a negative equilibrium because it gives the adversary the power uh to uh to to interact with these nodes in a more Atomic way so the reason we needed for the fault theorem is that because suppose that version offers a bribe and tells I will do some action for me when I flip a coin and then uh the note takes the bribe and then the coin ends up being uh the result that the node should

withhold its response and not just deviates right because it has already taken the drive I should just be told this response from the contract and potentially suffer some punishment so that is why the repeated games are needed to ensure this trust that when they promise to do some action they will do the action or another way we can ensure this is through a trusted third party okay yes and now let's go into the repeated game uh so we have seen a sub game uh we have seen how the optimal contract is struck contract is structured and over the notion of optimality for contracts and let's now bring all of this information together in a repeated game

so we assume that before the game starts the nodes and the client are input a query because without a query there is no game and at this point the game starts and the Baseline payouts are set to zero for both the node and decline and at any slot until T equals four and node can either send its response to the client or the network or send its response to the contract if there is a query on the contract if there is no then then the contract doesn't accept responses of course and at any slot the client can send the query to the contract so this is an important detail that the repeated game does not start with that query already sent to the contract it only starts with the node and the client knowing that

there is a query so nodes knowing that they should reply to the client and the client uh accepting a waiting for a reply but the the client does not necessarily have to send its uh query to the contract so this will be part of the game and if the client learns the response to it is query by slot T equals four then it gains a payoff of PF coins and here every smpf is a large number that is larger than the cost of complaining on the contract or the adverse is right to the client so for instance it could as well end up happening that the nodes send K or more responses over the network to the client

in this case the client need not complain on the contract and the client already learned the response the answer to its query so it can end the game right at this point the game uh the game could end and the payoff because the payoffs will be realized or if the client is malicious it can still send their query to the contract because the adversion asked it to do so then the game might continue but the game definitely Ends by T equals 4. so these are the parameters we have seen so far are lots of them I I just want to flash the screen for a second to remind people so we have two extra ones that we will see next at the bottom

okay so how do we now incorporate the client into this uh game right so far we have only had a sub game of interactions between the contract and the nodes now we have a client as a result the contract should have some reaction to the client and its reaction is structured as follows it says that the contract basically doesn't offer any reward or punishment to the client if the data can be recovered because well the contract knows that the um the client already earns their payoff of TF which is a large number on the other hand if the if there is a query on the contract and there are less than a k responses on the contract which

means that the now the contract thinks the client did not recover the data contract doesn't know if it recovered the data through the network or not it only knows how many nodes responded to the contract in this case the contract offers a compensation to the client that is some amount and it's assumed to be larger than the cost of complaining on the contract and there's and we need to have this uh this is necessary for security if P comp is less than or equal to PC then there are some equilibria that are very pathological very nodes can promise to not not ever reply to the contract or send their data to the client over the network and it

will be more profitable for the client to Simply remain silent and not complain on the contract so to avoid these kinds of pathological equilibria we need to have this compensation and what can we claim given our modified enhanced contract and the repeated game so we can claim the following Suppose there is an adversary that has some fixed rights P0 and P1 to the node and the client respectively and suppose these satisfy the following inequalities this first one is the one I already talked about uh where we need this P1 to be less than P comp minus PC so that the client sends a query to the contract if the nodes are unresponsible

with the network or even if they stick to being unresponsive over the contract and the second inequality comes from the expression we have seen so far I the expression for error probability had this value as its denominator and this value has its numerator if p 0 is equal or larger than this then the problem Security will be violated with probability with overwhelming probability in the sub game and uh if these are satisfied then given our optimal slashing function that we have seen in the previous slide for any adversary a that offers P0 and P1 price the maximum probability for security is violated in the previous Dynamic game in nns equilibria is upper bounded by the

same expression that we have seen for the sub game and moreover if K is equal to 1 greater than one when there are more than one diagram node for any other slashing function there is a sub game perfect equilibrium where the adversary with bright P0 violates four security with a larger or equal probability than this expression so in some sense our optimal contract is still optimal when we generalize the uh to uh rational clients and an adversion who can offer Brides to client foreign sort of users is that they may not they

may not do the challenge yes exactly imagine like the notes simply tell the user hey no matter what you do we will never reply to you in this case uh the issue is now the user it knows it won't get any responses over the network and it knows that if even if it sends a query to the contract it won't get any responses from the contract and like quoting the contract has a cost associated with it which is this PCM on so then the client the user simply thinks that I should better remain silent and this is an equilibrium where the client the security is not satisfied and adversity is successful so and and now even if this PP call

there's a compensation and there is a PC amount the same could happen if the adversary can offer a bribe to the client right now the adversary can cover the difference between these two and it can say to the client hey look like these nodes are pledging to never send their responses even to the contract or to the network you better remain silent and I will give you this P1 composition so it turns out that now the client would find it more profitable uh to not send their query to the contract so it's like a very pathological equilibrium and this is a theorem that is stated for these neutral nodes uh this expression in particular but the theorem holds for these covers nodes

with a different expression here that I could not uh find a closed one solution and the flip side of this theorem is if P0 is small right P1 was just like the cost of comp sending a response to the contract and P1 is also sufficiently small well here it's a much more complicated expression that I would rather avoid putting here and the unfortunate thing is if K is equal to one then four security can be satisfied in all Nash equilibrium without the client sending a query to the contract in this case the the single DAC node will realize that it's it maximizes its payoff or utility then it simply responds responds over the network

the problem with this expression is why it's unsatisfactory is well we have more take created amount most of the time and when K is greater than one if none of the nodes are sending a response over the network in the equilibrium then a single mode cannot increase its payoff by sending a response over the network right like this single node even even wants to be honest it it doesn't gain any reward from sending its response over the network because it knows that because other ones are not sending their responses the client will put a query to the contract no matter what and then uh as a result uh we need to assume that K is equal to one in which case the node has full agency over its

payoff given the client's actions other nodes cannot believe it and of course uh all of these results would remain uh theoretical if we do not put numbers to these broad amounts uh and uh failure probabilities so we calculate the bride that is needed to violate the security with this probability uh where we assume the value of it is just twelve hundred dollars and the number of diagnosis is 300 000 to match the the magnitude of the size of the validator set on proof of State ethereum we assume that the adversarial fraction and K is a one-third

if this is to match the resilience of a proof of stake ethereum again and each node States 32e the minimum amount a note can stake in proof of State ethereum we just use it as our benchmark and we said okay let's look at how much bribe the adversion should offer to violate uh security with probability 0.1 percent for a single query and let's focus on the bottom expression this basically tells us the drive needed to violate the security for a single query is a 3.9 million US dollars which is quite a large amount if we are talking about a single query and each time there's a new query adversity needs to spend the same amount on the contract

either in bribes or yeah in brights basically and uh well the rest of the table is for risk averse nodes and there is a the gap between the lower and upper bound characterization for this error probability because of uh the fact that there we could not find a closed form expression so the solution for this error probability comes from a problem statement and the problem statement is not convex as a result we could not uh solve it can you put that 4 million in context like it it sounds like a lot of money but if you could brick an entire roll-up server for four million dollars

and like yes that is true so the context is uh let's say there is a single client that wants to learn um that's also learning proof of inclusion for this account balance right and then it has a credit to the contract and this is the bribe amount that version needs to pay to the diagnose so that they don't reveal the proof of inclusion to the uh to the client for it to withdraw its money so well I it will probably be result in a loss of trust in this layer 2 system if a client cannot uh get this proof of inclusion but I don't know how this uh loss of trust will compare against four

million dollars so it's four million dollars when it's paid it does not necessarily break the whole system it just Grieves a single client but if this is an important client or an important transaction of course it could be more serious foreign we also consider in the paper uh what if the adversary like coordinates actions across multiple queries right uh across the responses of the bribed and adversial notes across multiple queries it turns out it does not give adversary extra power the the results end up being

the same meaning that in each query adversion needs to spend 3.9 million US Dollars um to grieve the client Whenever there is a query on the contract just curious did you get any feedback Pharmacy um we did not get any feedback as far as I know from them specifically we got some feedback from people who work on oracles or decentralized Oracle networks so they were they were thinking that this scheme of this this contract and as a query analysis uh it is useful for them because they there they have the problem of some of the people who are

supposed to reply to a contract we told in their responses let's say there's a lot going on and these people don't vote on it so they want to have some slashing mechanism on them so they they thought that this is this work is quite applicable to them so one issue one I guess so I problem with the applicability of this data available versus these decentralized Oracle networks is in the Oracle Network the response to the query by the node is very small right it's just a yes or no one let's say or like some small amount of information and in my example for the data that's been requested proof of inclusion that is also a small amount that you can put on on chain but what if the client's query is asking for a lot right let's say it's asking for the data in a thousand blocks now in a validium

setting you might not want to put a data for a thousand blocks onto the layer one blockchain so these kinds of like large queries uh will have a much larger cost PW like the cost of putting the response to the contract for the nodes then uh the other settings so the then the the analysis and the assumptions there's PW being a much smaller as compared to PS and this numerical side breaks down a little bit yeah so and let me just end with a small discussion points so our work um Can arguably uh discourage

centralization of storage um the reason for that is now when storage is centralized everyone delegates the storage is possible to try Central Mall so these DAC members they pretend as if they are storing the data but they don't but now if the Central Storage has a downtime it looks as if these DAC members are corrupted and they don't reply to the contract right and as a result and then they they they endure a large slashing cost so this our solution as a result might discourage them from uh centralizing their storage now the downtime of this uh storage um entity that they are centralizing towards is much more costly for the darknodes another uh discussion is on this value

of PC the cost of sending a query to the contract there is a trade-off here between preventing denial of service attacks by the clients and then making this PC higher to prevent these dos attacks and to make it lower so that the queries are much cheaper for the honest clients and finally I would like to end with an open problem about what would be the most realistic utility function I am I'm guessing it's not the linear one that I looked into and uh given this optimal slashing function would there be a closed form solution for the failure probability when the nodes are risk covers because even though we showed its optimality in the sub game for discover snows we couldn't characterize this solution because the problem ended up

being non-convex and if someone could solve it what would be the expression either numerically or um mathematically yeah thank you very much yeah I think there was a question on the chat that I did not reply at the beginning of the talk uh what if the headers uses an accumulator that supports proof of non-inclusion um so the proof of non-inclusion okay so it will be like suppose the header has a accumulator and it says that okay so these are the data that is accumulated and he's here are the proof of inclusions right so a client comes and asks for the data so the blog producer

gives the data and the proof of inclusion with it and it might perhaps give a proof of non-inclusion for some of the data right you can give a proof of non-inclusion for a data that's not there but it cannot give approval money inclusion for every data that is there so when the client receives the response uh it will be all right but if the blog producer is malicious it can basically just remain silent towards the client like just not say anything to the client at all so the client doesn't know what is inside that block and then as soon as the Watchtower comes in then the block producer gives all of the response right it gives all of the proof of inclusion or non-inclusion for the data that's not supposed to be there to the Watchtower so the issue with the um fisherman

attack is that the Watchtower does not have any way to monitor what happened between the client and the malicious block producer back in the time when the Watchtower was not available it was not in the system um I'm not sure if there's this yeah that that does answer my question thanks have you um have you talked to anyone uh in the lightning world because this seems like something that could be used to prevent the uh the griefing attacks that that they've been struggling with for a while oh that's yeah that's very good feedback thank you um I I wasn't aware this I did not look in the lightning Network that much myself so I was not aware that this

could have some use there but yeah I think we should we just strengthen because I had I had this sense that uh data availability might not always be the best application of this work because of this uh on chain cost being too high when the queries ask for a large amount of data unlike a single inclusion proof um but yeah it would be great if I can find more applications yeah because I mean you're kind of hitting like three birds with one stone here it's like um proof of data availability proof of non-censorship and proof of like non-griefing kind of thing and actually I think I think the proof of non-griefing is something that there are the fewest

uh potential solutions for out there so yeah it's interesting yes I would definitely take a look there thank you it was great talk um thanks so much for taking the time thanks for listening so much