Decentralized workload distribution with VRFs and reputation systems

Transcript

Mario Karl I'm here with my friend Gorka Aki and we all represent the center eyes were closed distribution with lever 18 on cryptography sortition like with via left it later and algorithmic reputation systems so we will both work at the summary labs and we've been building for the last years with net which is a decentralized oracle network so during this talk we are gonna go through the problem statement then we're gonna try to discover what kind of challenge arise regarding this problem statement and then we are gonna design a genetic workload distribution system and finally we're gonna showcase an example of the

system which is with net and we're gonna have some kind of conclusions and takeaways so what's the problem before really going deep dive with the problem first we're gonna do some kind of taxonomy some classification about what kind of workload decisions they are out there and we make a really simple classification with for example full replication systems like Bitcoin or aetherium in which all the nodes they have to execute all the transactions in order to reconstruct the world state then we have Charlotte systems that are like sort of chains of chains they are really similar also they are anchor and

some kind of chain relay you name it and then in a different dimension we have a classification depending on the type of task one of them are for example systems that normally try to split the task into sub tasks that's the case for example from mining pools also they case the famous case of Boeing protocol that is using SETI at home or a set at home and even the torrent and then the nice ones and the one that we are going to focus during this talk at the the tasks that we call hardly probable this is the case of for example file coin and witness so what are highly probable task this task are a special kind of task that it

really doesn't make any sense for all the nodes to execute those types by the whole network it really doesn't make sense why for example they could be because they are not verifiable at all imagine doing a query to an open API they are not that monistic like for some random number or maybe they are just really computationally heavy so doing the verification of those transactions takes so much time that really doesn't make sense to be done by a whole entire network so having that in mind the problem would be like how to distribute hardly pro tasks in an efficient way among really important in order to be decent wise and trusted entities without

compromising the task integrity trying to be as as possible so having this problem statement in mind let's try to go to what kind of challenge challenges they are going in step by step let's start with this it was hardly hardly probable task so here the questions are like how should I assign those tasks among the entities should be the assigned really equally for example following a round robin scheme or how can we do this kind of assignments without having central coordinators there are normal questions in any disputed workload distribution system so later on we have the untrusted

entities challenged so how can we really be sure that those entities are executing those tasks how can we be sure that they didn't manipulated the outcome they did a tamper with the data outcome and finally how can we provide some kind of security to all these task execution like for example avoiding or deterring civil attacks and the last set of challenges they are regarding how to do this efficiently and really providing some kind of task integrity here the first question is obvious what does efficiently efficiently mean efficient mean does it mean to be also scalable or

not then the next questions we are about how can we really in a distributed world log system how can we really maximize the probabilities that the task outcome has some kind of in 30 have some kind of quality and finally it's the liveness property how can we be sure like after a certain period of time this task has been executed either successfully oh with rarer so after all these open questions we came with named the holy grail of workload efficient systems that are only a set of characteristics now we would like to have in a decentralized water

distribution system it's important to be decentralized in order to avoid having central coordinators to be a scaleable to have the property of lightness but at the same time we want to care about the security and there is also a nice feature also like which is the fairness now we're gonna explain the next slide thanks Mario one by one through the ingredients that we said a protocol that we imagined I should have and actually revised what we understand by all those

components right so for instance Central Station for us as mario said already we don't want a central coordinator to actually distribute the work among the nodes we have right that's the number one thing we want we also at the same time one no single point of failure so imagine that we distribute the work to one node only right so if this node is not available that work gets incomplete right so that's something we don't want either and also something very important we don't we don't want an entity to have enough power to actually be able to censor tamper with with word that we want to this to it so essentially what do we understand by a scalability so we

understand the fact that this work that can be more or less complicated or cost-efficient to perform so we imagine a system in which we allow a work champion so basically this means that the task can be chunked in several subtasks and each of those tasks can be independent and basically can be executed by several notes at the same time that's what we call parallelization and the last one it's very important because it's very natural to the kind of work we're trying to add distribute which is number if I all work or non-terminal stick work and it's a replication factor which means that we cannot ensure the integrity of the outcome of the work basically because it's not verifiable right so we need to

we need several notes to actually execute that task as mayor said liveness what we would like is that when we insert a work to a network we want event rate to receive a result we don't care if that result is work couldn't be the work can be completed or basically the work has been successfully completed with this result but eventually we want a result in terms of security of course what we imagine our our the network or reportable to look like it's basically that if we put a fully replicated protocol aside and basically we compare

them we insert the same inputs to both networks we want the result to be the same so basically we want our network to actually behave like a fully replicated Network that means of course that no task outcome should be possible and also very important we should deter field of initial attacks we will see later how how this can be done and lastly and this is kind of very nice to have which is fairness so we would like the world to be distributable to notes in an even manner that means that there's no note that actually gets to do all the all the jobs and also we would like to be we would like to assign works in a metric based

way so essentially that there is a metric that quantifies how honest or dishonest tasks how well or bad some nodes have completed the job additional considerations of course we would like people that join late in time in the network so we would like them to we'd like to send them a probability to actually perform those jobs as well so as to avoid until 14 so but we don't want this an illegal or a set of em oligarchies executing the jobs because that means that they would be bribable all right so with this we will present now what we came up with and ya later see an example of how we apply this kind

of protocol to so as we said it's very important that several notes actually execute the task because again we're dealing with number e file jobs and that means that we need some kind of community selection right so we're gonna leverage that with the usage of verifiable random functions of ers and then what we also ambition is a protocol that actually has some incentives to actually behave or complete the job in an honest manner but honest meaning that they complete the job as it should be and we imagine that been achieved with a reputation system so we're gonna build a

protocol that actually uses this two component so let's start with the first one whatever if il run on functions the first time I actually looked at them I found the first definition which essentially it gives little clarity of to what they are so I'd rather read the second one which is very crystal clear for me it's basically the public key version of a kid cryptographic hash so in a cryptographic hash we usually use a symmetric key so just change that with the public key and you have kind of the same properties how they work well we have a proven a verifier of course so the prover gets a message which we call

here input and also it has a secret key that only he knows and the output is a proof of this kind of execution and also a random value that I used for different reasons or for different uses cases as a swivel selector and essentially how does the very fire proof verify this so it takes the public key of the prover it takes a semi input and it takes the proof and basically is gonna say whether the proof was valid or not so why are we using verify all random functions because in the end again what we want to build is a system that is able to select committees right to perform jobs so um yeah what we would

like is a crypt a certain kind of scheme right in which every task is performed by us a few randomly selected selected people but we want some characteristics of descriptive sortition right so for instance what we want is that no one is able to compute the legibility or the yeah no one is able to compute whether someone else is in a committee or not that's what we call secret right so no one should be able to compute in another notes eligibility until this node publishes the proof right we want this looks is random the output of course we want we want to be probably sztyc so we want we don't want to assign all the jobs to a certain person or not sorry but rather we want

it to be probabilistic we also would like to be verifiable and we also want that each node has a single shot of becoming eligible to a certain job so essentially almost all those characteristics are given by the very fail random functions and that's why we will use them so as we said we have certain nodes executing a job number if firewall and non-deterministic and that means that they have to reach an agreement right so we ambition that being a shall in point game in which basically there are incentives to actually say truth because if you say truth you probably are gonna get a economic crew and economic reward if you don't or

meet the truth being both in any consensus with the others of course and if you don't you don't get the economic reward right so in this kind of scheme the most probable outcome is to execute the very most let's the outcome that guarantees the the the money is basically to actually execute the the job and report the correct result so up to now we didn't mention why we why would we use the reputation system right in this case so we could have this kind of a scheme just with brf's and everything would look sort of nice but the problem is that for every work or for every job that we want to do notes would be selected in a totally

random number and basically there wouldn't be any penalty aside from not winning the pot of correctly but it wouldn't be an infinity by saying by not complaining job correctly right so that's why we need the repetition system which means basically to count how well or bad a node has behaved over the past right our two goals are keep keep notes I all for any wrongdoing so if they so if they are both out of the consensus they will have less chances to actually take part of an in another job and it also as we said should condition influence on future rewards so the better you behave the more odds you have to actually perform jobs in the future

so how do we use this in combination with the BRS it exactly in the way the question is drives what we have is metrics so I have an influence my reputation divided by the total reputation of the network we also have a replication factor which is how many people do we want to execute the job we have a public randomness that's a must and of course we have a task ID identifying each of the jobs we insert in the network and basically what you do is kind of a prf with a randomness in the task ID with a secret key of course of the node that is computing the eligibility you divide that you divide that by the tutorial where L is the size of the of the proof and you basically

get a number between 0 and 1 that you compare it to the right term so again when you try to build a reputation system you have to be very careful with how you define rewards penalties issuance or distribution of course rewards and penalties we already mentioned while are very important because you're going to affect actually the way nodes are selected for future jobs so that's that should be and designed with take thinking that it will actually impact on how the nodes profitability Dacians is very important because so I don't know if you're

familiar with the time with the term whitewashing but basically a node if it starts with reputation that is above the minimum one so if it falls below that default reported that if a reputation they can open a new entity at zero cost right so basically it's important to think the issuance correctly I will see later how how we did it and of course there is the redistribution right so we don't want someone de that acquired repetition at some point in time to hold it forever right so that means that at some point that repetition needs to expire or be distributed over a network yeah and the last well actually one of the key components as well of a certain

scheme is that if we have a set of nodes executing a job and each of them comes with a result we don't want them to copy each other this is like in the school right so essentially what we mission is a commit reveal scheme in which they first put their with the result they got in in a sealed envelope which is just let's say in an encrypted manner they throw it to a network and once all the commitments are in the network they are allowed to rebuild their boats and actually reach a confirm on it which is exactly the last inside we will cover here reaching a consensus what does this mean well every node that executed the job had a different result and we need to define how these are reduced right

this can be done both at the protocol level so we could have in the protocol and specified how things should be reduced for instance we want them to be reduced by mode so that could be built in protocol and and be fixed but the other the other ways since jobs can look very different from each other we could say it said the parametric that means that we could said we could so basically the work submitter could decide how the results can be reduced and now Maria will explain how so what design decisions we made for the case of witness okay let's go so right now we showcase witness which

is just an example of a decentralized workload distribution and I already mention about whether these are the centralized or a good Network and in realizing kill traffic sortition and reputation system obviously our main goal is to bring external data into other block chains so for that we build our own block chain and we can interact with our block chains through bridges yeah let's go and follow a little bit their structure of what work explained so let's start with the test definition in our case the task is just a data request and as I already mentioned these are hardly probable tasks which because they are non verifiable imagine query in open URLs okay you don't have any proof like it serve to onenote the same as to

the other and they may be also non-deterministic imagine query not temperature in our open weather API for example so it's really important for witness that these test definitions are really well defined it means it should say how many sources they should be used to query the data so it should also mention and define formally how these data should be aggregated and then how their reports or the results from different workers witnesses whatever you call it how they should be also aggregated on that in mind okay and this way we define this with three stages the source scripts that are four different

your data sources the aggregation to convert different sources results into one single at a point and the tally function with which I uses all the research from different reporters into one single data point so I think it's better to see the diagram because it's easier to understand so imagine we have a data request that is gonna be reported by two workers Alice and Bob so the data request defines that there are going to be dead data queried to three different URLs and each of them they will query the data and apply an aggregation function after that they

will have each of them a different result so following the committee level scheme that got convention they will first a committee result into a transaction into a blog later on they will reveal their results and finally another a third party in this case a minor node will take all the results from other reporters and will aggregate it and reduce it into one single data point so following this the structure what about the committee selection we call it proof of eligibility because as Gorka said it's not come privately compute if they are eligible or not it means if they are part of the committee for a certain task so it's really

important to say it's weighted by the reputation it means the more you contributed to the system are not convinced to the system it means been behaving honestly whatever you want to call it it means trying always to contribute to the quality of the data extracted the more chances they will get to become a part of the man of a committee the formula is the same as god convention it's important to say this random SS worker said the same I'm regarding reputation system here gets a little bit more interesting we said the following incentives regarding rewards and penalties if group battery do we think it will continue so

if if I behave honestly in all the tasks he was part of he will get some some reputation points but if he misbehave at one task so he will lose a 50% of the reputation points for each dishonest participation regarding the issuance a new reputation points will be minted for each data request that is sent to the system and there gonna be a limit that is gonna be proportionally set to the total token supply in our case they with tokens and the most simple interesting part is the registration so the reputation points they will expire with with time or based

on the net velocity it means the more data requests they have to be executed the quicker and not will lose its reputation points this is really important because it's an anti hoarding mechanism it also discourage inactivity it means they note they will want to be online to keep earning reputation points and obviously trading reputation doesn't make sense because it's expressed with time and the last part the last piece is regarding the protocol it's really similar to the Alice and Bob diagram in witness we have four different stages the first one is the data request stage in which developer or somebody sends a

lot a request with all the definition how the data should require a tax aggregated and determind then we have the committee stage in which all the nodes of the system of witness compute if they are eligible or not based on the using also the reputation as an input and if they are they will send these committee transactions and in the next block they will send a rebel transaction with the results of the data request and finally as I mentioned before the miner will get all the results and will execute a tally function and we will have a single data point so we kind of convert and determinism into the termism in some way so and the last part which

is really really important in a permissionless system it's trying to the turing severe attacks for that because it's a big problem we thought about 200 measures the first one is having collaterals for each data request commitment this makes like if there is an attacker that once really to attack some data request first of all she it should have enough funds in many identities at the same time because he may lose some stake so there is some skin in the game and the big problem here perhaps could be the low barriers to entry because if you are requesting collateral maybe a newcomer most

probably who it will not have enough funds yet still that's the one of the trade-off that can be said having for example setting not too high collateral for all the data requests and the second condom measure is the mature collateral I don't know if the name is the best one we also call it coin age and it's just like in order to put some stake so to join a committee and put some stakes tanka some collateral these funds has to be at rest at least for a certain period of time this makes orchestrating an attack for malicious issue a user really really difficult imagine not only having all the funds but the same in many

distributed identities but also having those utx holes these funds being completely at rest it means not participating in witness therefore most probably losing reputation so they will have less chances to really perform the attack and to conclude some takeaways we discover in the process of building witness so we present you a different distant ice water distribution that is alternative that is different it was highly inspired by Al grant file coin they mean there are two main takeaways the first one is like obviously when you

are designing such a system they test make sure effects completely your entire system design has to be taken the first thing of all and the second one is like perhaps the the the most important one is like we saw like during the process of defining building with net we have to make a lot of it to find the sweet spot or finding the right violence from different trade-offs I give you some examples for example the more parameters you allow in a lot of requests most probably the more difficult it is for a newcomer to build it at the same time I already mentioned the low values to entry and similar attacks which if you allow or make it facilitate that

newcomers can join the system really quick most probably you are also not deterring enough see us on civil attacks and at the same time its simplicity versus attack surface let's say during the process we saw we wanted to cover some edge cases and at some point we also always wanted to keep it simple as much as possible in order to avoid to really increase in the tax surface it means the more complex your system the more you have to be really cautious so and that's all thank you very much for listening and just a quick reminder we have all the talks in the incoming days when it's about s DX the other ones

about bridging unknown poem post side chains with etherion and the last one is radon which is a domain-specific language in order to define those data requests thank you very much if there is any question hi this is really interesting one question that I have is that you mentioned that each node privately calculates its own reputation and it seems to me that you're kind of using a work token model where people are staking and I was just wondering why not something like chain link which has a reputation contract

built-in that automates this what is the distinction they you draw there and why did you make the decision to put the work onto the individual node so I'm not entirely aware of what kind of reputation system training has built in but the reason we decided to do that is that you know every node we ambition a system in which every node should secretly like it's not that every node secretly computes the reputation because like everybody knows everybody else's reputation with not what it computes secretly is the eligibility so basically where it has to actually insert the

private key in that case so that's the part that is secretly computed by the node so no one knows the eligibility of a node before that node publishes the proof can you use witness you you know in some way collect trust word for information from Oracle's like can you be more specific nowadays everybody uses in the file right so I want important relationship would be

nowadays for dyes or sizes what's the what's the price of the ether against dollar it's as important information so do you think I can use something in with net to in order to then collective trust worth information absolutely so right now anything that is available available in public ap is like the ether to use the price for instance that you mentioned you can retrieve through witness but I think the good part of a system that is that you don't even have to trust one single API but rather you can fit several EPS and then you can decide how the result that each API gives should be aggregated so in our way

what when we designed with net we actually foresee that yeah we don't want any single point of failure not even the API in this case yeah so if you're curious we have also a prizefight example that really showcase exactly this specific use case experience the rhythm is just the language in order to really specify the different stages I mentioned like how to retrieve the data from different URLs how to aggregate them for example filtering out those that fall out of the division a standard deviation for examples and then how to aggregated the same function of similar function to aggregated result from

different reporters so here the URLs could be like open api's providing the price feed bitcoin against USD whatever yeah that's it I really encourage you to take a look to the price feed example which is really showcase super good how Twitter works and where we why we design with it like that well could I find it the presentation I will tell you about these dogs I thought we'd not to tell you I think in the web in the repo that you see over there in the sliders there's a really nice example in truffle books that you can actually take a look at and that should

serve as a starting point for that thank you