Algorithmic Reputation and Sybil Prevention Using Onchain Pagerank | Scott Imig - Octan Network

[Music] on behalf of my company and myself we're really excited to be here at eth Denver and we'd like to thank the organizers the stewards the volunteers and the staff everybody who's come together to make this event so great let's give it up Octon network is a data intelligence company we do onchain algorithmic reputation and other analytics my name is Scott Emig I'm a principal scientist at Octon my background is from the web World web search paid search recommender systems personalization so you'll see that flavor in this talk the both the data science flavor and the web 2 flavor but I promise to bring everything together for something that's very relevant to blockchain so all right everyone let's get into it this is the Octon business model our stack is in the middle uh we have a distributed GPU compute protocol and a reputation ranking system we're a B2B company so other businesses pay us for services and analytics at different levels of the stack this talk is about onchain page Rank and it's related to a blog post from Brian Armstrong from August 2023 where he gave 10 ideas for startups that he would found today if he was starting a company today and they're very innovative ideas Network States flat coin and among these 10 very innovative ideas is onchain reputation and one of the points that is made in that blog post and the video that went with with it is that the web has exactly the same data structure as the blockchain on the web you have pages and hyperlinks between pages and on the blockchain you have addresses and transactions between addresses so anything that can run on the web graph can run one to one on the blockchain without modification in particular page range can run on the blockchain and provide a reputation score just like it does on internet so to give some credibility to this idea let's look at the sizes of these two graphs the web in 2024 has 202 million active websites ethereum in 2024 has 205 million active addresses those the sizes are not just the same order of magnitude they're almost the same number of course there are differences it would be nice to know more about the web topology but that's a very difficult research problem things like diameter and connected components because in order to know about the web you have to crawl it and the crawler is always behind reality because the web is always evolving contrast that with the blockchain at any given time we can know exactly the state of the blockchain and not only can we know exactly the state of the blockchain at that point in time but we can know the historical state of the blockchain at any historical point in time and there are other important differences in the blockchain for example the transactions which are playing the roles of hyperlinks have a lot more information they have amounts higher amounts are more important they have ages an old transaction may be less important than a newer transaction they have multiplicities two hyperlinks from the same web page to another web page doesn't carry the same importance as two transactions from the same address to another address so all this goes together to kind of demonstrate that page rank is not only applicable to the blockchain but page rank is more applicable to the blockchain and more powerful on the blockchain than it is on the web to let's just review and introduce the page rank into his it maybe one or the other page rank is based on a random Surfer model the idea in the internet is that the this random Surfer this hypothetical Surfer goes to a random web page and then on that web page they randomly select a hyperlink and they go to the Target page and on the target page they randomly select a hyperlink and go to the Target page of that and they go on forever and if they go on forever then at some level of approximation the page rank is the number of the percentage of visits that each page has there's some additional components to page rank one thing is there are dark corners of the internet where the random Surfer can get stuck they can get into that dark corner of the internet but they can't get out because there's no hyperlink getting out so in order to account for this page rank allow this random Surfer to jump with some probability usually it's set to 20% 20% of the time instead of following a random hyperlink they will choose a web page at random and then go to that web page and in the internet world this is done with a uniform random distribution usually so all the pages on the internet are equally likely to be chosen but it's not necessarily the case that it has to be a uniform distribution this random Surfer May 20% of the time jump to the same web page or to the same group of web pages or the random Surfer may prefer certain web pages over other Pages this is called personalization and Page Rank and so it's possible not only to weit transactions by their amounts and ages and multiplicities but it's possible to weight addresses by anything that you know about the address maybe the balance at that address this leads us to adapted page rank blockchain has these features and we want to incorporate that information into the algorithm so we can wait nodes and edges according to the um according to everything we know about the blockchain and this is not the first time it's been done applying this to blockchain adapting for blockchain it's not the first time for example in City networks for uh City Planning some applications want to find the important intersections between city streets but some intersections may have a big building on them or some intersections may have a vacant lot and some may have houses so the features of the intersection are actually possible to incorporate into page rank before page rank even runs and then let page rank do what it does this allows us to tune the page rank algorithm using all of the information that we've been discussing to be very specific to a scenario or to be very well tuned to the blockchain so let's suppose that we adapt page rank to the blockchain and we've used all the math and all the intuition and we've asked all the experts and we think that this ranking for reputation based on page Rank and all the waiting that we've assigned is a pretty good ranking how can we tell if it's really good well if there are data scientists here they'll tell you what you need is an independent truth set where you can take the reputation ranking and you can compare it against this independently generated truth truth set and see how the reputation ranking performs against the truth set fortunately the blockchain excels in this regard too for example the arbitrum airdrop did not go to Every address that met the criteria specified for the airdrop certain addresses were eliminated some of them were El eliminated because they were large publicly known addresses and they weren't qualified for the airdrop but some were eliminated because they were bad actors they were spamming the network and so they were disqualified from the airdrop so using the arbitrum airdrop we can say that anyone who received the airdrop is true true quality High reputation anyone who didn't receive the air drop is low low quality low reputation and false or we could look at ether scan ether scan actually has warnings for certain addresses such and such Authority has warned that this address may be associated with a Ponzi scheme so we could say that anything that has an ether scan warning is potentially low reputation we should trade it as false false reputation anything else we can treat as true reputation we don't really care where anything else falls in the ranking we just want to eliminate any of these ether scan addresses with warnings or the other way around maybe there's a large trusted entity let's say Unis swap Unis swap has many addresses and so we may think that we a lot of people trust Unis swop and let's say that we want to give High reputation to the Unis swop addresses so we could give a True Value to that we could say that's high reputation that's true reputation and everything else can be false it doesn't matter where anything else Falls we just want to be sure that the Unis swap addresses appear here near the top so let's look a little bit closer at the arbitrum airdrop how did AR arbitrum detect the sys anyway they use a clustering algorithm on the transaction graph clustering algorithms on large graphs can be very expensive and so we can take that the output of that very expensive operation and the existing reputation score and see how those two compare and we can actually measure this and assign numbers to it and use the number to improve it so the way that we can do that is rank all the addresses by the reputation score in descending order the very highest reputation is at the top of the list the very lowest reputation is at the bottom of the list everybody else is in order in between and then suppose you were going to launch another airdrop on arbitrum you might want to use the relevance score the reputation score to determine which ones would receive the air drop so we can set a threshold where you think that above the line those are pretty high reputation and those those should get the air drop anything that's above the line and got the arbitrum airdrop we treat as a true positive it's high reputation according to the reputation score and it's high reputation according to the arbit arbitrum airdrop anything above the line that did not get the airdrop it's a false positive it's ranked highly according to the reputation score but it did not get the air drop so it's a false positive and the true positive rate is the percentage of the true positives and the false positive rate is the percentage of the false positives you can see that for different business scenarios it could be very useful to adjust that threshold let's say that for your new airdrop you wanted to be sure that everybody who possibly qualified for the airdrop would get it and we don't really mind if a few bad actors also get it then you could set the threshold very low you could capture almost everybody who's a good actor and you also get a few bad actors and for certain scenarios that might be okay or the other way around let's say that we really want to eliminate any civil attackers we could set the threshold very high and then we would a lot of people who were were good actors would not get the airdrop but uh we would at least not be getting a lot of Bad actors with the airdrop so the threshold can be adjusted for different business scenarios and between any of these two addresses and this long long vertical list of millions of addresses there's actually a threshold and that threshold has a false positive rate and a true positive rate so being a data scientist I love charts and graphs and we can chart this the true positive rate on the Y AIS and the false positive rate on the x axis and this is known in in data science as the receiver operating characteristic curve you may have heard of it any data scientist will tell you this can be very useful for measuring the performance of a ranking and the way that you use it to measure the performance of the ranking is that the percentage of the rectangle that's underneath the line is your score so on the left we have a lower quality ranking and on the right we have a higher quality ranking there's 61% of the uh of the area is under um on the left and 84% is on the right now 84% is a very good number this is um this is real data against the arbitrum airdrop using arbitrum uh reputation scores computed from before the airdrop and if we were a pharmace tical company and we got an 84% area under the curve we would take that product to the next step and if we were a web search company and we got an 84% area under the curve we would take that model to The Next Step so 84% is a positive result it has a signal and we can not only do that we can not only do one experiment this is just one experiment we can do any number of experiments because we have transactions with amounts and ages and we can adjust how we're waiting those transactions according to their amounts and ages and we can also adjust how we're waiting nodes and improve on this score over and over and get that area under the curve higher and higher and higher in the case that I'm showing from the previous uh previous chart from the previous slide we were actually experimenting with waiting nodes according to either incoming or outgoing transactions and it turned out that one was much better the other one had a signal but this was much better so there are a lot of opportunities to adjust this so for future work for the reputation scoring algorithm we are comparing these scores against other truth sets other airdrops and some of the other truth sets that I mentioned there are also a lot of tools from the web that we can apply that are related to area under the curve but other other tools like Precision at in there are other uh analytics that are important maybe this High reputation address got the airdrop but did they just sell the arbitrum tokens when they got the airdrop and then stop using arbitrum or are they still users of the arbitrum and can that Rel can that reputation score predict that we're moving toward decentralized Compu for algorithms and uh visualization this is a deepin initiative and we're moving toward decentralized Oracle for reputation so this is my final slide and I have um an email address on here for inquiries we're very interested in connecting with you we're interested in connecting with Partners we're interested in connecting with customers we're interested in connecting with investors and we're interested in connecting ING with other engineers and data scientists who are interested in algorithmic reputation I also have a PO app up here and the PO app is on a piece of paper and the piece of paper is my business card and it has all my contact information along with this email address so if you see me after the talk or you see me anytime during the conference please say hi and I'll give you a PO app so thank you for everybody's attention and have a very prosperous and good and productive week this week and at eth Denver and I really appreciate your attention lfg