How to run a conspiracy

It seems like the holy grail of social networking is the "only Cool people" security level.  Whoever figures out how to do that and have it really work properly will make a huge amount of money; but since it's probably not actually possible, that's going to be difficult.

Here's what I mean:  you have something you want to publish.  You don't just want to distribute it to people you already know - you want members of the general public you don't already know to be able to read it - but they have to be Cool people.  You don't want it to be available to a few fairly well-defined Uncool people.  Music sharing would be one good example:  you want random Net users to be able to download your files but not the representatives of the RIAA. We saw something similar on Facebook a couple years ago when people were posting photos of themselves doing undignified, or occasionally illegal, things and then being unhappily surprised when, for instance, employers, or the police, saw and acted on the photos.  Something similar is often desired on Livejournal - they've even got an FAQ entry explaining why it's not possible to implement an "everybody except" security level for postings, but users still want it.  I'm going to generalize all these kinds of things as distinguishing Cool people from Uncool people.

This is a very old kind of problem.  The Mafia supposedly has a protocol for introducing members who don't already know each other:  if you say "This is my friend, Joe Bloggs," then it's not safe to discuss this thing of ours with Joe, but if you say "This is our friend, Joe Bloggs," then you're vouching for him as being Cool.  Secret societies are popularly imagined to have all kinds of code words and secret handshakes and stuff.  There's an instance of this problem in the Bible (Judges 12) where the Gileadites wanted to permit only Gileadite refugees to cross a river, and block out the Ephraimites - they demanded that would-be river crossers pronounce the word "shibboleth," which the Ephraimites couldn't pronounce properly.  (A "shibboleth" now means a password or group recognition sign, in reference to this passage.) Similarly, the protocol for hiring a prostitute or buying drugs may involve requiring the customer to do something that it's widely believed the police aren't allowed to do, in order to prove that the customer isn't an undercover police officer.  I've occasionally faced some interesting demands from witches and neopagans who weren't willing to accept me as a legitimate member of their community without proof.  Letters of introduction from known Cool members of the community are accepted or required in many different kinds of communities.

You can automatically administer a Coolness test, like a password or secret handshake or "knowledge of the ways of our community" questionnaire or something.  Many years ago I wrote something like that for a dialup BBS I ran at the time.  Those kinds of things have very limited utility, though.  All it takes is for one infiltrator to figure out the Cool answers to the test and publish that information to other Uncool people, and your system is blown wide open.  It's very hard for a computer to really evaluate this kind of thing in a sustainable way. 

Strong anonymity also seems to be aimed in this direction - that's what Freenet attempts.  Instead of preventing the Uncool from reading the secrets, Freenet generally allows everyone to read, but prevents that from being damaging by strongly hiding the identities of the participants.  That works for the kind of thing that goes on Freenet, but it's a problem for the more personal material that goes on systems like Facebook and Livejournal, because it's hard to separate that stuff from the identities of the persons posting it.  Also, people want their identities associated with their postings - that's often the purpose of posting at all.  We do see people using pseudonyms on these systems pretty often.  All too often they have exaggerated ideas of how secure their pseudonyms really are, and they wind up unhappy when they learn the hard way that the Uncool people actually can trace back from a pseudonym to the "real" identity that was supposedly protected.  One reason I almost always use my real name is to prevent myself from falling into that complacency trap.

So, one thing you can do is require individuals to make their own Cool/Uncool determinations individually.  Web sites that depend on "friends only" security are doing that.  Then if an infiltrator fools one member, it sucks for that member but they haven't violated the entire network.  It's a big sacrifice, though, because users really want to permit Cool strangers; they don't want to have to authorize everybody and be limited to the people they already know.  So either they approve "friends" who aren't really, on little or no authentication, or they make things public that they don't really want to be public, because that's the best compromise.  Either of those depends on some amount of security by obscurity - sure, the Uncool people are out there, but they probably won't read your profile.

Another thing you can do is provide some kind of default Cool/Uncool filter.  Some of the file sharing systems do that - you have to go to some lengths to become accepted into the net, but once you're in, there's little further authentication.  These kinds of things are often called "reputation systems." I think that's probably the better solution, but it means the default Cool/Uncool filter had better really work properly.  Here's my proposal for one I think might work well.  I don't know if someone else has thought of this before, but if not, maybe my posting it here will inspire someone to try it and/or prevent someone from patenting it.

The key idea is that everyone who joins has some "sponsors" who vouch for them.  Lots of sites have done things like that before with "invite codes" and similar; the new wrinkle is that sponsorship is a basically permanent, long-term relationship.  If you sponsor someone you are taking personal responsibility for their being Cool, and promising to the community that the person you sponsor really is Cool and won't betray the community.  Because it's a real commitment, I'd expect sponsorship to be a lot harder to come by than the "friendship" other social networking systems implement.  Being accepted in the network would then be based on having enough currently-accepted sponsors.

Inevitably, someone will end up getting accepted into the community who shouldn't have been.  If it's something like a file sharing network, then it's reasonable to suppose that the Uncool people are organized and actively hostile, so once a few get in, they'll cooperate to bring in more and to destroy the network.  It's important to be able to withstand such an attack as far as possible.

What I imagine is that the network would start with a few "founders" who are declared to be Cool by fiat.  Anybody could create an account, but your account wouldn't be good for anything when initially created.  To participate in the system, you'd have to attract sponsors from among people who were already Cool.  To be Cool yourself, you must have some number (k) of sponsors who are themselves Cool.  I'd suggest k=2 as a reasonable number.  If k=1 it's much like what many existing systems do with requiring an invitation from an existing member.  If k is more than 2, the system becomes progressively more paranoid, with the paranoia level increasing significantly with each additional sponsor required.

The "you must have k sponsors who are Cool" rule is not the real, strictly defined, version of that rule; in the normal case it reduces to that, but the real rule is "There must be at least k vertex-disjoint directed paths of sponsorship from the founders to you." In other words, the flow of sponsorship from the founders to you must not pass through any bottlenecks consisting of fewer than k people.  That allows for a group of k or fewer infiltrators, and their descendants, to be cut off as soon as one is exposed - but someone who managed to attract sponsors from outside the infiltrator group could still be Cool even if they had originally come in innocently through sponsorship by infiltrators.

It's assumed that there exists some out-of-band mechanism for detecting and punishing infiltrators.  If one of your ancestors becomes Uncool and causes you to lose Coolness under this rule, you lose access to the system too, but (if you really are Cool) you can still hope for a Cool person elsewhere in the network to sponsor you, at which point that restores not only your Coolness, but also the Coolness of your descendants.

You are considered responsible for the people you sponsor, and their behaviour.  Your sponsors are shown clearly and frequently; when you post a message or whatever, your identity is not just "John Doe," but "John Doe sponsored by Mary Roe and William Woe." It's an ongoing visible relationship with consequences.  The exact meaning of "you are responsible for the people you sponsor" depends on what the standards of the particular group are and what Coolness actually means, but it could mean for instance that if you sponsored someone who had to be expelled, then you'd get expelled too.  It would probably only propagate backward one generation.  The details of that aren't critical to my idea; the critical part is just that sponsorship is a promise from the sponsor to the entire community that the person being sponsored really is entitled to be there.  One of my assumptions is that we deal with Uncool people primarily by not allowing them in in the first place.  If they have to be expelled, that's the exceptional case and means the system has already malfunctioned.

Except as provided by the other rules, you may sponsor as many people as you want to and be sponsored by as many people as you can convince to do it.  However, because of the consequences of sponsorship and the other rules that do limit it, I'd expect that most people wouldn't have many more sponsors than the minimum needed, and wouldn't choose to sponsor many others.  I'd also allow sponsorship to be revoked at any time, though there might have to be some kind of timeout or something to prevent people granting and revoking sponsorship willy-nilly to avoid the "take responsibility for people you sponsor" rule.

There are a few more rules needed to keep the system functional in the face of infiltration attempts, allow for proper healing when a traitor is discovered, and prevent excessive sponsorship.  First, you're not allowed to sponsor anybody in a way that would create a directed cycle in the sponsorship graph.  That means, for instance, that if Alice sponsors Bob and Bob sponsors Carol, then Carol is not allowed to sponsor Alice, or more generally any of her ancestors.  A very simple way to enforce this would be to impose an ordering on sponsorships, such as "you may only sponsor people who joined after you did," but I'd rather not do that.  I'd rather only enforce the "no cycles" rule directly.  The purpose of this rule is to prevent a situation where a group of infiltrators gets a few people in, then they sponsor the rest of their group who in turn all sponsor each other.  If cycles were allowed, then most of the group could remain Cool as long as even a few of their incoming links remained live.  Without cycles, it's a lot harder for them to stay in once a few of the original infiltrators are expelled.  The next rule ties into that - it prevents a small untrustworthy group from protecting themselves too well with redundant incoming links.

Excessive sponsorships are also a problem because a group (even of legitimate Cool people) could decide that it's socially necessary for everyone to sponsor everyone else to the extent possible, and then, as above, if one does turn out to be a traitor and is expelled, people can end up being punished for sponsorships they should never have made in the first place.  Sponsorship ought to be a Big Deal, not something you hand out to everybody.  To limit it a bit I propose the rule that no pair of sponsors can sponsor more than one member.  For instance, if Alice and Bob both sponsor Carol, and Alice sponsors Dave, then Bob is not allowed to sponsor Dave, because if he did then the pair of Alice and Bob would be sponsoring both Carol and Dave, which is more than one member.  Resolving this rule (i.e.  which of Alice and Bob get to sponsor Dave) would be under first-come first-serve.

Under the "no pairs may sponsor more than one person" rule, the cost (to the network) of a person's sponsors increases with the square of the number of sponsors they have.  If you have 10 sponsors, then there are 45 (roughly half of 10 squared) pairs among those sponsors, who won't be able to collaborate with each other on sponsoring anyone else.  The number of pairs among all the people in the system increases with the square of the number of members overall (i.e.  very fast) in theory, but not really, because pairs of people who don't have close friends in common are not likely to really occur anyway.  So I'd expect the number of pairs who really would collaborate to actually be pretty much linear in the number of members.  Thus the typical number of sponsors per person should tend to a small constant.  The net effect is that I'd expect a few people who really are well-trusted by the community to have large numbers of sponsors, but most people would have close to the minimum number because there wouldn't be enough sponsorship to go around to support too many extra sponsors.  Thus the extra sponsorships, which allow for healing of the network when a traitor is expelled, would stay at a reasonable level.

A system that implemented this could allow for several semi-independent communities of Coolness by designating different subsets of members as "founders" for different kinds of Coolness.  I could see that getting complicated, especially because you might not want to sponsor someone across the board into all your own Coolness networks, as in "This is our friend Joe Bloggs - he's cool for drug deals but it's probably better not to mention that other thing of ours." It's something to think about in more detail, though.  There might have to be rules about labelling the graph edges for different Coolness types, allowing cycles (but maybe pruning them on the fly) and so on.  One nice thing is that the underlying graph algorithms tend to be pretty easy; even quite complicated rules can be computed quite efficiently.  It might be a problem explaining complicated rules to the users, though.  Users want simple rules.

One serious "gotcha" is that Coolness is not really transitive.  Very often the few people I consider Uncool are friends of my friends.  I've seen that with things like that Livejournal toy that analyses your friend network to find people who are friends of many of your friends but not friends of you - the people at the top of that list for me are people I deliberately didn't list as friends, for important reasons, and I've heard similar comments from other people who've tried it.  That's to be expected because my enemies would tend to be people I know - I'm less likely to care about people I don't know.  So just the fact that many people I like have vouched for someone doesn't necessarily mean I trust the person; but at the same time, what else can the system use?  This kind of scheme would probably work well for something like an illegal conspiracy where everyone's in it together and everyone who is Cool has some duty to the organization; it may be less useful for the kinds of personal things that people put on some social networking sites.

That's the idea in a nutshell.  As we continue to see semi-underground use of social networking sites (like the "It's not fair for the police to read Facebook!" thing), it'll be interesting to see if the social networking sites adapt to it and what techniques they use to adapt.  Of course very few sites will be willing to openly advertise their anti-police measures as such, but there are plenty of more openly acceptable reasons for a social networking site to try to be "exclusive" in some way, and I think there's a clear user demand for it.  What users really want is a "Cool people only" security level - and we can't hope to actually provide that, but I anticipate that there'll be more serious efforts toward it in the future.