GrapeRank
At the time of this writing, over 45 million nostr pubkeys are known to have been created. But how many of those pubkeys can we say with some degree of confidence are probably what most of us would consider “real” users? Not bots, not scammers, not impersonators, not mass produced by some script? Of the tens of millions of known pubkeys, probably no more than a few hundred thousand max should be considered real users, based on a cursory overview [1] of the follows network.
There are many applications of web of trust, but the first and foremost application is to find a suitable method to identify the pubkeys that are likely to be real users, while weeding out the obviously bad actors – impersonators, malware, spam, etc. Outside the world of nostr, one of the most famous such metrics is PageRank, which was introduced by Google in 1998 to weed out spam from website keyword search. Although the global version of PageRank is what we tend to find in the fiat world, the version most compatible with the ethos of nostr is personalized PageRank. The most natural way to implement personalized PageRank in nostr is to use the kind 3 follow list.
Using follows, PageRank can be quite effective at identifying pubkeys that are probably not bad actors, even the ones that are more than just one or two hops away. However, PageRank suffers from several well known methods of attack, most notably the link farm. The basic idea of a link farm is that a bad actor spins up a large number of nodes (URLs in the case of web search, pubkeys in the case of nostr) that all link to each other, boosting each other’s scores. This attack is particularly worrisome in nostr, given the relatively low cost to create bots and issue kind 3 events. All it takes is a small handful of pubkeys to entice a small number of real users to follow them – not hard to do using AI – and we are left with a swarm of high-scoring pubkeys that the bad actor is free to use for impersonation or some other nefarious purpose.
Although some methods exist to mitigate the link farm attack, none are fully satisfactory. Once utilization of centrality algorithms like PageRank becomes widespread in the nostr ecosystem, we can expect link attacks to intensify dramatically.
PageRank has several other problems in addition to the link farm attack. A second problem with PageRank is that it yields a single score, sometimes referred to as the “importance” score, and there is no immediately obvious way to create different scores that have meanings and can be used for different applications. And a third problem of PageRank is that it is well suited for sorting, but not well suitable to be used as the weight for weighted averages or weighted sums.
The first and most obvious way to improve PageRank would be to incorporate additional data beyond just follows, such as kind 10000 mutes and kind 1984 reports, that can be used to weed out whatever bad actors become problematic. The cost of identifying and tagging a bad actor that has gained traction is arguably less than the cost of spinning up the attack in the first place. So if we can incorporate these and other forms of flagging, we will have a highly effective mitigation scheme.
Unfortunately, there is no immediately obvious way to incorporate mutes, reports, or other arbitrary sources of data into the PageRank algorithm. When you sit down and try to work out the details of some method, it turns out to be more complicated than one might expect.
But the problem is not intractable. If you think about it long enough, if you try to modify PageRank to design a centrality algorithm to address its shortcomings and to implement a certain set of desired characteristics, you’ll eventually hit upon something more or less like GrapeRank. These desired characteristics include the following:
-
There needs to be a generalizable, clearly defined protocol to incorporate any source of data, not just follows, mutes and reports. For GrapeRank, that method is called intepretation [2].
-
There needs to be a clearly defined protocol to design different metrics with different meanings. One metric to identify health care workers, another metric to rate skill level in some particular activity, etc.
The GrapeRank algorithm was designed specifically with these considerations in mind. Although GrapeRank is designed to produce a variety of metrics, the prototype Brainstorm instance produces only one metric for each pubkey, the goal of which is verification: pubkeys that are probably “real” users, probably not bots or bad actors. This metric, the baseline GrapeRank score, is a number between 0 and 1, with a score of 1 meaning verified, a score of 0 meaning not verified, and a score between 0 and 1 indicating a pubkey that is probably not a bad actor, but there is insufficient data to say that with confidence. Indeed, the best way to interpret the baseline GrapeRank score is to multiply it by 100 and think of it as the degree of confidence with which your community says to you that this pubkey is probably not a bot or bad actor.
Here we will review the basic principles of GrapeRank which we will assume to be personalized to Alice’s pubkey:
-
The default score of all pubkeys (except Alice’s) is zero.
-
Alice’s pubkey has a fixed score of 1. (She knows with 100% certainty she is not a bot.)
-
The only way to boost a score is to be followed by someone whose score is nonzero.
-
The amount of the boost is directly proportional to the GrapeRank score of the follower.
-
Mutes and reports decrease a score, with the amount of the decrease being proportional to the GrapeRank score of the muter or reporter.
-
A single mute has more effect on the score than a follow, and a report has more effect on the score than a mute. It therefore takes only a small handful of reports authored by trusted users to counteract a large number of follows.
Under the hood, the GrapeRank algorithm tracks not just one number for each pubkey, but several numbers, one of which is the degree of confidence that your trust network has in the assessment of that pubkey, with more information yielding a higher confidence in the assessment. For more details of the math behind the algorithm, see this article [3].
Consider what happens when an established nsec is compromised or a bad actor manages to achieve a high score, either PageRank or GrapeRank. What is the remedy? For PageRank, the remedy requires all (or most) verified users following the pubkey in question to unfollow – something that is simply unlikely to happen in most cases. For GrapeRank, the remedy requires only a small handful of trusted pubkeys to identify and flag the bad actor, a remedy that is quite feasible in most cases.
This prototype of a Brainstorm instance shows that empirically, GrapeRank is quite effective at sorting the wheat from the chaff for a basic application such as profile keyword search. Impersonator accounts that use the link farm approach to fool PageRank are more effectively screened out by GrapeRank. (Please forgive the slow performance of this particular keyword search implementation - work in progress.)
Through the process of interpretation [2], additional sources of data (zaps, content interaction scores, badges, etc) will in the future be utilized to create more varied GrapeRank metrics with different meanings and for different applications. For now, work is focused on building more performant Brainstorm instances and on methods of delivery of personalized trust metrics throughout nostr, such as NIP-85: Trusted Assertions.
Notes
[1] This prototype of a Brainstorm instance shows that the set of all known pubkeys that I follow, plus the ones they follow, plus the ones they follow, ad infinitum until there are no more known pubkeys to add, yields less than 300 thousand pubkeys, with the highest degree of separation by follows being 10 hops away.
[2]
[3]
