[00:03.900 --> 00:10.000] The problem that I think we're all seeing, and certainly that we've kind of been growing [00:10.000 --> 00:20.080] increasingly concerned about for some time, is that it's not enough anymore that you can [00:21.000 --> 00:28.520] participate in a peer-to-peer network and nobody can tell what you are doing. Increasingly [00:28.520 --> 00:34.340] it's the case in this country and elsewhere that simply the act of participating in a [00:34.340 --> 00:42.940] peer-to-peer network is in itself a pretty risky thing to do. As a result, we believe [00:42.940 --> 00:50.440] that future anonymous peer-to-peer networks will need to limit who your peer connects [00:50.440 --> 00:57.320] to to a group of trusted friends, people that you have decided you don't mind that they [00:57.320 --> 01:04.500] know that you're a part of this peer-to-peer network. The big question is, is it possible? [01:04.500 --> 01:13.880] And if it's possible, will it be useful? Just for those, quickly to clarify the term peer-to-peer, [01:13.880 --> 01:18.340] because if you ask 10 people what peer-to-peer means, you'll get 10 different answers. [01:19.160 --> 01:26.920] From our point of view, a peer-to-peer network is designed to help people find information. [01:27.320 --> 01:32.720] Specifically, it's designed to help people find information that is widely distributed [01:32.720 --> 01:40.620] across a large number of computers which are connected through some network, in practice [01:40.620 --> 01:46.760] typically the internet. Users of this system want to find information. They need to know [01:48.880 --> 01:53.220] where the information is so that they can go out and retrieve it. [01:53.220 --> 02:00.700] There are different approaches to this. The first peer-to-peer network in many ways was a piece of [02:00.700 --> 02:05.920] software called Napster, and its approach was pretty simple. Every peer in the network simply [02:05.920 --> 02:14.380] reported to a central server or eventually one of several central servers what data was being [02:14.380 --> 02:19.780] stored on that computer. And so if you wanted to find some data, you'd go to the central server [02:19.780 --> 02:23.500] and say, you know, where's this thing, and it would give you a list of computers where [02:23.500 --> 02:28.820] you could find it, and you would then connect to those computers directly and retrieve it. [02:31.120 --> 02:35.960] Subsequent to that, when Napster and similar systems were being shut down, because of course [02:36.140 --> 02:42.120] a centralized system is very easy to shut down, people started working on what we call [02:42.120 --> 02:47.760] semi-centralized peer-to-peer networks, where it's essentially the same idea but instead of [02:47.760 --> 02:57.620] one centrally administered index of data, you have a large number of decentralized indexes. So [02:57.620 --> 03:02.640] when you connect to the network, you're allocated one or more of these indexes, and you use that [03:02.640 --> 03:09.960] pretty much like a mini-Napster. Kazaz is probably the archetypal example of that approach. [03:11.140 --> 03:17.320] Well, other peer-to-peer networks strive to be completely decentralized, such that in essence [03:17.320 --> 03:23.060] each peer in the network does pretty much the same job and has loosely the same degree of [03:23.060 --> 03:28.620] responsibility as every other peer in the network, and Freenet is one of several examples of [03:28.620 --> 03:38.090] peer-to-peer networks like that. Another way that you can classify peer-to-peer networks, and it's [03:38.090 --> 03:44.810] particularly useful for the purposes of our talk, is into light and dark. Examples of light [03:44.810 --> 03:50.410] peer-to-peer networks, or you could also call them promiscuous peer-to-peer networks, include [03:50.410 --> 03:55.670] Nutella, Freenet, distributed hash tables, indeed the vast majority of peer-to-peer networks that [03:55.670 --> 04:04.310] you've probably heard of. In essence, a light peer-to-peer network is defined by the fact that [04:04.890 --> 04:10.650] your computer will willingly connect to strangers, which means that strangers, people you don't know [04:10.650 --> 04:19.410] or trust, can discover that you are running the software. The advantage of this is that if you do [04:19.410 --> 04:27.550] it right, it can be globally scalable, which essentially means whether you have 100,000 users [04:27.550 --> 04:35.250] or 100 million users, you can still find information pretty efficiently. The disadvantage is it's [04:35.250 --> 04:42.830] vulnerable to harvesting. If, for example, the Chinese government wanted to get a nice, convenient [04:42.830 --> 04:49.050] list of all of the people in China that were running Freenet, they could do that. It wouldn't [04:49.050 --> 04:56.090] necessarily be easy, but it would certainly be possible. When we first came up with the idea, [04:56.090 --> 05:03.170] we didn't really see this as... well, this wasn't really on our radar, but over the past few years [05:03.170 --> 05:08.730] we've realized that it's not only in increasing threatened countries like China, but also in this [05:08.730 --> 05:16.310] country. I think most people here are probably familiar with recent court decisions which have [05:16.310 --> 05:24.790] further rolled back the freedom of people to share information in the ways that they might want to do. [05:25.310 --> 05:31.990] The alternative to this are dark, or you can also call them friend-to-friend, peer-to-peer networks. [05:31.990 --> 05:38.530] These networks are characterized by the fact that peers in this network only talk to other peers [05:38.530 --> 05:44.450] directly, only establish a direct line of communication with other peers that they trust, [05:44.450 --> 05:50.510] that their user trusts. So the user is saying, I don't mind that these people know that I'm part of [05:50.510 --> 05:58.510] this network. An example of this is a piece of software called Waste. The advantage of this, [05:58.510 --> 06:03.810] as I said, is that only your friends know that you're part of the network. The disadvantage is [06:03.810 --> 06:10.830] that until now this type of network really doesn't scale. Typically you might have 10... [06:10.830 --> 06:17.890] you have isolated pockets of perhaps 5 to 10 people. And while some people have found that [06:17.890 --> 06:22.690] to be a useful thing, clearly there's a big difference between that and being part of a [06:22.690 --> 06:30.710] global network with millions of users. Shifting gears a little bit, [06:31.250 --> 06:38.610] networks like Freenet and completely decentralized networks rely on something called the small world [06:38.610 --> 06:44.490] phenomenon in order to find information in this completely decentralized way. [06:44.990 --> 06:49.970] Some of you, I'm sure most of you are familiar with the small world concept, [06:49.970 --> 06:54.810] or you may also be familiar with the game of Kevin Bacon where you try to [06:54.810 --> 07:02.690] get from Kevin Bacon to any one actor just by going through movies they've been in. [07:05.290 --> 07:14.130] So a guy called Stanley Milgram in the 1960s did a very interesting sociological experiment [07:14.650 --> 07:20.410] where he wrote the names of two people, of a number of people actually in Cambridge, [07:20.410 --> 07:25.430] Massachusetts on some letters and gave them just to random people spread throughout the United [07:25.430 --> 07:31.810] States with the instructions that they were to try to get these letters to the intended recipients [07:31.810 --> 07:37.890] but only by giving them to someone they personally knew who themselves would give it to someone else [07:37.890 --> 07:44.830] they personally knew. And very interestingly he found that when those letters arrived [07:44.830 --> 07:51.070] they did so in perhaps they went through just five or six people. So that's five or six people [07:51.070 --> 08:00.170] in a country of 270 million odd people. Clearly a very scalable way to get something from where [08:00.170 --> 08:06.650] it is to where you want it to be and interestingly also completely decentralized. These people were [08:06.650 --> 08:12.590] not relying on any central phone directory in order to figure out where they should route this [08:12.590 --> 08:19.870] information. They were doing it purely on the basis of their friends. So what characterizes [08:20.690 --> 08:25.830] a small world network? Well typically in small world networks [08:28.030 --> 08:37.650] in small in small world networks what you find is is that you have short paths exist between any [08:37.650 --> 08:43.070] two people. You can, if you know how, you can get from any one person to any other person [08:43.070 --> 08:49.170] in a short number of steps even if there are millions of people in the network. The challenge [08:49.170 --> 08:56.410] is that these short paths aren't necessarily easy to find. In the in the case of [08:56.410 --> 09:05.090] in the case of Milgram's experiment people were able to use information that they had [09:05.090 --> 09:11.670] about their friends in effect as signposts as to which of their friends they should send [09:11.670 --> 09:17.730] the letter to next. They knew that if one of their friends perhaps lived near Massachusetts [09:17.730 --> 09:22.870] that they would be a good choice to forward the letter to if having reached that person [09:22.870 --> 09:28.310] that person knew somebody who was close to the street or perhaps went to the same university [09:28.850 --> 09:35.430] as the intended recipient they could send it on. So in in social networks people are able to use [09:35.430 --> 09:42.110] their knowledge of their friends as signposts for route it for finding these short paths. [09:42.730 --> 09:48.430] Well the reason this works is that there is people have a concept of similarity [09:49.150 --> 09:55.790] between other people. You know that if two guys live on the same street they're likely to be more [09:55.790 --> 10:01.970] similar to each other and therefore more likely to to be connected to each other than someone living [10:01.970 --> 10:11.580] out in Zimbabwe. So so the the algorithm is simple once you've got this concept of similarity [10:11.580 --> 10:17.040] you simply route to the person that you know of that is closest to where you want to be [10:17.040 --> 10:24.400] at each step. We call this greedy routing. Freenet and distributed hash tables rely on [10:24.400 --> 10:35.520] this principle to find data in a scalable decentralized way. So so Ian just started [10:35.520 --> 10:39.960] by talking about the these peer-to-peer networks and essentially the problem the dark peer-to-peer [10:39.960 --> 10:43.600] networks that we want to address and then he talks about the small worlds and social [10:43.600 --> 10:49.040] networks forming small worlds. So what we want to talk about here today and what we what we're [10:49.040 --> 10:55.700] interested in is how can we apply this knowledge about small world and about these social networks [10:55.700 --> 10:59.780] to deal with these dark peer-to-peer networks and try to make them more useful. [11:00.280 --> 11:06.080] And essentially this starts with the realization that the darknet is just a social network. [11:06.080 --> 11:10.580] This darknet the peer-to-peer network that's formed when people connect only to people they trust [11:10.580 --> 11:17.700] will be just this big encrypted network of people's relationships just like the social [11:17.700 --> 11:23.620] networks that sociologists and people work with. So the environment that we're trying to deal with [11:23.620 --> 11:29.520] in our peer-to-peer networks is just this social network that Milgram's experiment took place in [11:29.520 --> 11:35.140] and that we want to find a way to deal with. And we're interested of course always when we're [11:35.140 --> 11:39.800] trying to search and being able to find a way from one point to another in the network. We have [11:39.800 --> 11:44.960] this network that's large network connections going all over the place and we need to find a [11:44.960 --> 11:49.940] way from one point to another. Well we know that in the social network and the darknet is like a [11:49.940 --> 11:55.840] social network, is a social network, we people can find a way from go from one place to another. [11:55.840 --> 12:01.940] Milgram's experiment showed people can root in social networks and they can do it well. He took [12:01.940 --> 12:06.240] only five or six steps to go from one side of this country to another to a complete stranger [12:06.810 --> 12:12.680] and people can do that. So if people can do it then well so should computers. I mean computers [12:12.680 --> 12:22.240] are much smarter than people right? So to try to do this somehow, make computers do this, we need [12:22.240 --> 12:27.700] some sort of mathematical understanding for what's going on in the small world network. [12:27.740 --> 12:32.820] And this mathematical understanding has is something rather recent but a Cornell professor [12:32.820 --> 12:38.920] named John Kleinberg provided a model about five years ago that explains how these networks can [12:38.920 --> 12:44.580] look in order to be navigable. In order for it to be possible as Ian said to find signposts in the [12:44.580 --> 12:49.700] network that will take you where you want to go, it needs to have a certain configuration. [12:51.160 --> 12:57.520] And this configuration is that the possibility of being able to find routes efficiently from [12:57.520 --> 13:03.620] one point to another rests on the fact that you have people who have similarity to one another [13:03.620 --> 13:09.240] and as Ian said are more likely to be connected and then you have a certain proportion of connections [13:09.780 --> 13:16.120] of different lengths with respect to some sort of position. And in the simplest model position can [13:16.120 --> 13:20.760] just be where people live. And you say that people are more likely to be connected if they live close [13:20.760 --> 13:27.880] to one another. And as we get further away we need this to be the probability that people know [13:27.880 --> 13:32.540] each other that they are connected needs to decrease. And when this happens that's when you [13:32.540 --> 13:38.880] can find an easy way to route in the network. So for our talk we're actually going to allow people's [13:38.880 --> 13:43.860] positions to just be in a ring. And that doesn't mean that we think that people exist on a ring [13:43.860 --> 13:49.000] but this is the very simplest model. We allow each person to just get a position on the ring [13:49.000 --> 13:55.680] and then we see people knowing each other as these chords in the circle that skip over the people. [13:55.680 --> 14:00.740] So here I have two examples. We've placed these positions in a ring in the mathematical idealized [14:00.740 --> 14:05.080] model and we say that there are two green people who know each other and two red people who know [14:05.080 --> 14:11.060] each other. But if you can see the red one covers more of the circle. It's a longer link therefore [14:11.060 --> 14:15.920] it needs to be less common. And according to Kleinberg's model it needs to be these long [14:15.920 --> 14:20.340] links which this one covers double as many steps along the edge here so it needs to be [14:20.340 --> 14:28.620] half as common as the green one does. And if this is the case, if you have these connections, [14:28.620 --> 14:35.220] if we can put people into this base model with a circle or just a... and we have connections [14:35.220 --> 14:40.380] that agree with Kleinberg's model. We have some... every once in a while we run into a long connection. [14:40.460 --> 14:45.540] Somebody happens to know somebody who lives way on the other side of the world but that's rather [14:45.540 --> 14:50.340] rare. More commonly people know lots of people who live close to them who are close to them who [14:50.340 --> 14:56.180] are similar to them. If this is the case and you have this model then we can do this greedy routing [14:56.180 --> 15:01.660] that Ian describes which just says I'll always go to the... if I'm going to some destination I always [15:01.660 --> 15:07.780] just step to the neighbor who's closest to my destination. And if I can do that in... if the [15:07.780 --> 15:12.280] configuration of these friends is correct then the greedy routing can be mathematically proved [15:12.280 --> 15:17.840] to perform in something on the order of log squared n steps. And when something is log that's [15:17.840 --> 15:22.960] good. If it's not log it's bad. But we have log here so that's going to help us. That means that [15:22.960 --> 15:27.920] we have an efficient way of finding steps from one way to another which is exactly what we want [15:27.920 --> 15:34.980] if we want to be able to search and route in our dark peer-to-peer network. So this is an example, [15:35.040 --> 15:39.440] a simulated example of how such a network would look. Now I've imagined again I've just placed [15:39.440 --> 15:44.440] people's positions on a circle like this. All around there are people placed on the circle. [15:44.440 --> 15:48.760] We have two red people who are circled at the end. And if you want to do a greedy route from [15:48.760 --> 15:54.100] one to the other you simply follow these cords which represent the friendships and you try to [15:54.100 --> 15:58.860] get from one place to another by always choosing the friend who is closest to the destination. [15:59.100 --> 16:03.660] And so a route would look something like that. In the beginning, in the very first step we can [16:03.660 --> 16:08.360] take a very long step because that takes us a lot closer to our destination. As we get closer [16:08.360 --> 16:13.400] it becomes harder and harder to find steps that take us a long way. But eventually you do reach [16:13.400 --> 16:20.660] the destination and you do so in a bounded number of steps. But this is greedy routing and this is [16:20.660 --> 16:25.580] on a circle and I placed everyone on a circle in this imaginary world where it is extremely easy [16:25.580 --> 16:30.500] to find to say if you're closer to somebody than somebody else because you have a circle [16:30.500 --> 16:35.800] and you can say how many steps is it to him. But if we're trying to do greedy routing in a real [16:35.800 --> 16:40.560] social network, in the kind of social network that our darknet is going to form, we don't have [16:40.560 --> 16:45.600] an easy way of saying is one person closer to another. We end up having to answer questions [16:45.600 --> 16:51.240] like this. Is Alice closer to Harry than Bob? I'm trying to route in a social network. I'm this [16:51.240 --> 16:55.840] person in the Milgram experiment with the letter and the letter is going to Harry. [16:56.880 --> 17:02.480] And I have to ask myself should I send it to Alice or Bob? The letter has to go to Harry. [17:02.480 --> 17:07.480] I have to make a decision. Should I send it to Alice or should I send it to Bob? Well, as a person [17:07.480 --> 17:13.500] I make some sort of a judgment and in Milgram's experiment people have to make this judgment [17:13.500 --> 17:19.040] based on some idea of who of closeness between people. The most basic form would then be where [17:19.040 --> 17:24.520] do they live. If Alice happens to be Harry's neighbor then she is probably closer. [17:24.520 --> 17:29.720] There's a greater chance that they know each other than that Bob would know Harry. But you could also [17:29.720 --> 17:34.340] go on, for example, what their occupations are. People who are all hackers are more likely to have [17:34.340 --> 17:42.220] met at Defcon than somebody who's an ice dancer or something. But you could go, you know, [17:42.220 --> 17:48.580] jobs, interests. As a person, we do these kind of judgments all the time and it's not that [17:48.580 --> 17:53.980] hard for us to say what would be closer to one person than another. But now what we want to do [17:53.980 --> 17:58.340] is we have this dark net which is this social network. We want to find a way to route and we [17:58.340 --> 18:04.460] want a computer to do it. And in practice we can't really ask the computer to make these decisions [18:04.460 --> 18:10.740] based on what people live, what they do, etc. I mean actually this isn't as insane as it may sound [18:10.740 --> 18:16.420] because people have actually tried this and one can try to put into the computer as much [18:16.420 --> 18:21.460] personal information as the people as possible. Then you try to do some sort of closeness algorithm [18:21.460 --> 18:25.860] based on people's personal information trying to match it so that you can make these routing [18:25.860 --> 18:32.560] decisions. But the fact is that what it has shown, even if you try to use a large [18:32.560 --> 18:37.180] number of criteria, computers are not good at making these sort of value judgments. And even [18:37.180 --> 18:41.800] more than that what we're trying to build are anonymous file sharing networks and they will [18:41.800 --> 18:46.020] not be a big hit if the first thing we do is ask everyone to put in all their personal information [18:46.020 --> 18:51.580] so that we can route. It just doesn't go over well with our target audience. So we have to find a [18:51.580 --> 18:57.500] different way to answer these things with Alice, Harry, and Bob. Who is closer to who? [18:57.620 --> 19:03.320] And so the thing is, and this is what's extremely important, is the information is there in the [19:03.320 --> 19:09.700] network. We can let the network itself tell us who is closer to who and we don't need to know [19:09.700 --> 19:15.340] anything about them except the network itself. We don't need to know where they live, we don't [19:15.340 --> 19:21.320] need to know what they do, all we need to have is this network and we work based on that. [19:22.460 --> 19:28.200] So how would we do this? Well, we have this model of John Kleinberg that tells us what should the [19:28.200 --> 19:33.420] world look like for it to be possible to greet a route efficiently. Well, what the world should [19:33.420 --> 19:38.260] look like is that there should be few long connections and many short ones. Most people [19:38.260 --> 19:43.620] should be... most friends that you have should be close to one another, whereas you should once in [19:43.720 --> 19:49.860] a while have a long connection out to somebody who doesn't. And then, knowing this and having this [19:49.860 --> 19:56.600] graph, all we need to do is basically give people positions in a way so that this becomes true. [19:56.780 --> 20:02.380] We just say, forget about the world, forget about where you live, forget about what you do, [20:02.380 --> 20:05.760] I don't care any about that, we're going to make believe, we're going to make positions for you [20:05.760 --> 20:12.540] based on the network and make it so that the properties that we are looking for are fulfilled. [20:12.820 --> 20:18.180] So what you can say is in a way, rather than taking the positions and trying to root on people's real [20:18.180 --> 20:23.560] positions in this sort of social space, we reverse engineer the positions of the people [20:23.560 --> 20:31.260] based on how the social network looks. And that is what allows us to give people new positions [20:31.260 --> 20:36.520] that we then can use to root. And once we have these positions, we can then do the simple greedy [20:36.520 --> 20:42.740] rooting of always trying to go to the closest point and we get what we want. And the method [20:42.740 --> 20:47.780] to do this is actually surprisingly simple. There's some deep mathematical magic involved, [20:47.780 --> 20:52.940] but it actually turns out to be extremely simple. When people join the network, they simply choose [20:53.080 --> 20:57.800] a position that would be a position on this circle, and they do so in a random fashion. [20:57.800 --> 21:03.140] Everyone just decides, okay, do a random number generator, give yourself a position. [21:03.640 --> 21:06.980] And when you do that, of course, this is not going to be true, because two people who could be [21:06.980 --> 21:12.420] very close in some sense in the social network, of course, could have chosen positions at opposite [21:12.420 --> 21:16.660] ends, because it's completely random. In fact, they will choose positions at opposite ends. [21:16.660 --> 21:22.740] But then we have an algorithm where people get together, and then they swap their positions [21:22.740 --> 21:30.060] with one another, so as to minimize the product of the distances to their friends. And this is [21:30.060 --> 21:34.420] extremely important, and it has to do with the math. But they get together, they contact each [21:34.420 --> 21:38.060] other over the network, and they say, I have positioned this, you have positioned that, [21:38.060 --> 21:43.720] maybe we'll just switch and we'll be better off. And this is an example of that sort of switch. [21:43.720 --> 21:48.280] These two people have chosen their positions randomly, and so have their friends. And you [21:48.280 --> 21:52.840] have a green person who's got three green friends marked by these cords in the circle, [21:52.840 --> 21:57.760] and you have a red person who's got three red friends. But as it has been, since they chose [21:57.760 --> 22:02.960] their positions randomly, they happen to choose them on opposite sides of the network from their [22:02.960 --> 22:06.980] friends. And this is not what we're looking for. We're looking for something that fulfills this [22:06.980 --> 22:12.800] model, that people who have lots of friends on one side, they should be on one side. Well, [22:12.800 --> 22:16.480] what if red and green were to swap positions with one another? Then we get something that [22:16.480 --> 22:21.220] looks like this. And this is much more in line with what we are looking for in our model. We [22:21.220 --> 22:26.220] have one or two long connections, we need some long connections, but mostly we have these short [22:26.220 --> 22:30.560] local connections, so the people are close to the people that they are connected to. [22:31.880 --> 22:37.500] And so this is essentially the algorithm as it goes. I mean, there's some math involved, [22:37.500 --> 22:41.760] and some formulas and stuff that I can give to the interested people. But essentially, [22:41.760 --> 22:46.920] choose positions randomly, and then they switch when it looks like switching will make this [22:46.920 --> 22:53.620] network more like what we're looking for. And some things to note is that this switching step [22:53.620 --> 22:59.520] is essential. We couldn't say, for instance, let's just have everyone choose a position, [22:59.520 --> 23:04.200] and just take a position that's close to their neighbors. Because what happens if you do that, [23:04.200 --> 23:08.140] is everyone ends up choosing the same position in the end. Once you've done it enough times, [23:08.140 --> 23:10.860] everyone's like, oh, I want to be closer to my neighbors, and they want to be closer, [23:10.860 --> 23:14.380] and it just converges on the same point. You get a bunch of people who are all saying that [23:14.380 --> 23:17.760] they're at the same point, and I promise you, you can't root based on that. [23:17.920 --> 23:22.060] So you need this random choice, and then the switching back and forth. [23:23.820 --> 23:28.280] And one problem with this technique, of course, is that these identities that we use to root [23:28.280 --> 23:32.280] are going to be changing as people switch. And that's something that has to be dealt with at [23:32.280 --> 23:37.220] the application level, because people do not have a permanent identity. But there are ways of going [23:37.220 --> 23:41.140] around this. As long as we have one way of finding path from one path to another, [23:41.140 --> 23:45.460] one place to another, we can deal with the fact that people's identities may change. [23:46.220 --> 23:52.140] Okay, so now for the simulations, always a necessity to show that we've done some simulator [23:52.140 --> 23:58.620] data, to show that this can actually work. And so what we have is three different modes here, [23:58.620 --> 24:03.500] which are essentially two controls and one good, and one sort of where we have applied our [24:03.500 --> 24:08.160] algorithm. The first control is the random route. If you start with a network, we have [24:08.160 --> 24:13.540] no positions whatsoever, and we're just looking to find a way of looking for data in this network. [24:13.540 --> 24:17.980] With no positions, no knowledge about anything, we can't do any form of greedy routing. All we [24:17.980 --> 24:22.940] can do is stumble around randomly and hope that we find our destination. So this is sort of the [24:22.940 --> 24:28.620] control of where you start out, the random network, the random search. That's all you can do. [24:29.660 --> 24:35.000] And the other control is going to be the completely idealized situation, where we have created a [24:35.000 --> 24:40.840] network that agrees with this model according to some position scheme, and we have this good [24:41.380 --> 24:46.880] network that's known to perform in log squared time. This is where everything is good, but that's [24:46.880 --> 24:50.960] not the situation that we actually have. The situation that we actually have is something [24:50.960 --> 24:55.480] where we have a network just like this good one, but we don't know anything about the positions, [24:55.480 --> 25:00.180] and we have to use our algorithm to try to restore the positions. And that's what I have [25:00.180 --> 25:04.860] as the third data set will be the restored data. That will be our algorithm applied. [25:05.620 --> 25:09.360] So the first thing I'm going to do is show the success rate within these log n squared [25:09.360 --> 25:14.600] number of steps, where n is the network size. You can see the size grows logarithmically [25:14.600 --> 25:19.320] there at the bottom, up to about 256,000, I think, for this data set. [25:21.220 --> 25:26.780] And you can see that the random one falls off very fast. Random routing simply cannot perform [25:26.780 --> 25:33.380] in this number of steps. It fails to find data as the network grows, whereas the good line [25:33.380 --> 25:38.200] will stay at the top. It always succeeds. The math tells us that it must, so it would only be a bug [25:38.200 --> 25:45.120] in my simulator if it wasn't. But this... and we can see that restoring, applying our algorithm, [25:45.120 --> 25:50.520] doing these switches, actually brings the success rate all the way up from the red line [25:50.520 --> 25:55.840] almost to the green line. And only at the very largest size do we see some significant deviation. [25:55.880 --> 26:01.080] But even at that level, we're talking about 96% success rate for the restored network. [26:02.400 --> 26:05.960] And the other thing one's interested in, of course, is the number of steps that it takes [26:05.960 --> 26:10.620] on average. And now we can see that even with the falling success rate, the successful queries [26:10.620 --> 26:16.460] in the random walk will increase as the size of the network grows dramatically. The good ones [26:16.460 --> 26:22.220] will stay low, just like the math tells us, and the restored one can bring us almost all the way down [26:22.220 --> 26:30.800] to an acceptable number of steps. But of course, that's simulated data, and we started with the [26:30.800 --> 26:36.460] model that we're applying, and that's always a little suspect. I'm basically doing, making, [26:36.460 --> 26:41.380] giving myself an idealized situation. So a more interesting question is, how do we do this if we [26:41.380 --> 26:46.820] have real-world stuff? Well, so to get some real-world stuff, rather than asking for permission, [26:46.820 --> 26:53.180] we simply borrowed some, and we went and grabbed 2,200 people from orkut.com, which is this social [26:53.180 --> 26:59.640] networking site that Google started, I think, about a year and a half ago. Everyone ran there [26:59.640 --> 27:04.060] because it was a fad or something, and put in all their friends, and then no one's done anything [27:04.060 --> 27:10.360] with it. So I think, because as far as I know, it's rather useless, but it does provide a very good [27:10.360 --> 27:16.220] data on social networks and how they look. So we grabbed some data from this, and we spidered a [27:16.220 --> 27:23.940] set of people, starting with our friend Ian here, and going and taking people so as to create a [27:23.940 --> 27:32.040] rather dense social network. And as it happened, this was done rather randomly, but as it happened, [27:32.040 --> 27:38.740] I guess that's not too surprisingly, given maybe Ian's... starting with Ian, but most of the people [27:38.740 --> 27:45.620] were programmers, techies, people in the technology community, and mostly Americans, very few non-Americans [27:45.620 --> 27:52.240] in the set. And I think that I would imagine that, say, maybe some of the people who are in this set [27:52.240 --> 27:58.320] are actually here today. Not just Ian, but somebody who was in it. And just as a note, we got no [27:58.320 --> 28:02.800] Brazilians. If someone has logged in to Orkut recently, you know that it's been overrun with [28:02.800 --> 28:11.720] Brazilians, because apparently in Brazil it's useful for something. So there are like 70 or 80% [28:11.720 --> 28:16.320] Brazilians there, but this set, apparently that social network is rather disconnected from this [28:16.320 --> 28:21.340] one. So our set contains programmers, Americans. There weren't a lot of these Brazilians who do [28:21.340 --> 28:26.840] whatever they do on Orkut. And just as a note, because when people talk about small worlds, [28:26.840 --> 28:32.040] they often talk about degree distributions and power laws. And we did have a power law degree [28:32.040 --> 28:37.040] distribution here, in the sense that there were a couple of people. When you talk about a degree [28:37.040 --> 28:42.340] in a network, you mean the number of people that somebody knows. So the most popular person here, [28:42.340 --> 28:47.240] and I think the most popular person in the set was Orkut Bukhokan himself, the guy who founded [28:47.240 --> 28:53.660] the site. He had 289 friends in the set. So out of 2000, he knew a hell of a lot of those people. [28:53.660 --> 29:00.080] And whereas most people had only around like 18-20 neighbors there, as you can see. [29:00.200 --> 29:05.660] So this is the sort of power law degree distribution that can affect the network. [29:06.300 --> 29:10.380] So dealing with this data set now, we want to apply this switching algorithm, [29:10.380 --> 29:15.060] and hope that this will do something good. Something that can beat just a random search. [29:15.240 --> 29:19.200] And a random search performs rather well on this data. And the reason that a random search [29:19.200 --> 29:23.960] performs well is that it will... is because of this degree distribution. Because you run into [29:23.960 --> 29:29.340] people who know so many people, it's easy to run into the person that you're looking for. [29:29.340 --> 29:34.500] So with power laws, it tends to perform rather well. So in this log n squared steps, and [29:35.440 --> 29:40.560] you should all be able to do that in your head, but 2000 log n squared, that's about 120 something, [29:40.560 --> 29:46.800] right? So in about 120 steps, the success rate was 72. And of the successful ones, it was about [29:46.800 --> 29:51.820] 43. So for randomly searching a network of 2000, this is rather good. [29:51.900 --> 29:55.720] So the question of course is, if we run the switching, try to apply this. This is a real [29:55.720 --> 30:02.060] social network. Can we just get somewhere with this greedy routing by assigning identities? And [30:02.060 --> 30:08.580] the answer is yes. So with our algorithm, we can search with a 97% success rate in this data, [30:08.580 --> 30:14.100] and on the mean number of steps is only about 7.7. So we are rather happy with that result, [30:14.100 --> 30:19.940] because it really shows that we can massacre the random search by performing this ordering, [30:19.940 --> 30:24.040] and we can get something that actually seems, it actually looks like the social network [30:24.040 --> 30:30.120] lives up to the model and what we were looking for. And one thing one can see is that this [30:30.120 --> 30:33.800] degree distribution, the fact that there are people who knows many people, can affect the [30:33.800 --> 30:38.520] results. So if we clip the degree distribution, meaning I don't allow anybody to have more than [30:38.520 --> 30:43.680] 40 friends, I just throw away everybody's friends after 40, we can look, was this what was actually [30:43.680 --> 30:48.360] going on? And in the random search, you can see that yes, in this case, success rate falls [30:48.360 --> 30:53.200] dramatically, because you don't have these people who know tons of people. But in the case of our [30:53.200 --> 30:57.600] thing, it adds a couple of steps, but the success rate is still good, and it's still dramatically [30:57.600 --> 31:03.520] better than the random search. So we can say that our algorithm can take advantage of this [31:04.620 --> 31:09.340] degree distribution, but it was not use it. And it seems like it actually does work. Starting [31:09.340 --> 31:15.580] with a social network, you can reverse engineer positions, so as to make it possible for a [31:15.580 --> 31:20.940] computer to do what people will do when they're trying to pass a letter along, based purely on [31:20.940 --> 31:29.560] this stuff. Are we going to go with the demo? So to demonstrate this, we were going to show [31:29.560 --> 31:39.320] routing in this, between some people in this data set from Orkut. So one thing to start with, [31:42.740 --> 31:48.880] is starting from Ian himself, who was of course the start of our set, and going to for instance [31:48.880 --> 31:53.560] Sergey Brin, who I think we all know. Ian wants to know how many steps does Sergey bring, because [31:53.560 --> 31:59.440] I want to borrow some money or something. And they will actually search the set, and you can see that [31:59.440 --> 32:06.700] it skips from friend to friend, and finds a path from Ian to James in four steps. And what needs [32:06.700 --> 32:11.640] to be noted about this, is that when this does the search, it does it in a decentralized fashion. [32:11.640 --> 32:17.020] It never looks at anything at any step, except who your friends are, and it decides which of Ian's [32:17.020 --> 32:21.760] friends was closest to Sergey Brin, which of Sean Parker's friends was closest to Sergey Brin, and [32:21.760 --> 32:26.640] then when it gets to James Joachim, it finds that he knows Sergey Brin. So the search is completed. [32:28.080 --> 32:36.660] Another example, we could do person in the set number 1708, which is Fyodor, [32:36.660 --> 32:41.980] who I think is at the conference somewhere. And we could go from him, to now somebody else who's [32:41.980 --> 32:55.020] in the set, like Lawrence Lessig. And that one also succeeds, and you can see how we are honing in [32:55.020 --> 33:00.560] in these positions in the circle, always choosing the friend of Fyodor who was closest, and then [33:00.560 --> 33:06.460] the closest, and it actually has managed to assign these positions in a way that it can find this [33:06.460 --> 33:16.940] path going in. So one other interesting thing, just while we have this tool that we discovered, [33:17.340 --> 33:23.180] is that there are certain people in this data set who aren't... well, they are real people, [33:23.180 --> 33:28.440] but it's kind of an abuse of the system. So for example, you get celebrities or politicians, [33:28.440 --> 33:34.760] one example being John Kerry, who someone signed up as John Kerry, and then people will connect [33:34.760 --> 33:41.540] to that person, I guess to show that they're going to vote for him or something. But the [33:41.540 --> 33:51.160] interesting thing about people like John Kerry in this data set, is that they don't fit into this [33:52.640 --> 33:58.760] small world model. If you've just got random people connecting to you, then it doesn't [33:58.760 --> 34:06.240] fulfill this criteria for a small world, whereby if you know somebody and you know somebody else, [34:06.240 --> 34:14.420] then they're more likely to know each other. So let's say we try to route from Sergey Brin to [34:16.100 --> 34:25.040] the fake John Kerry, the results are kind of interesting, and what you actually find is that [34:25.040 --> 34:34.540] this will keep going for 200 steps and never actually succeed in finding John Kerry. And again, [34:34.540 --> 34:41.840] the reason for that is very simply that this John Kerry user does not fit into the social network [34:41.840 --> 34:51.320] model that we assume. Yeah, because he doesn't actually know the people that are connected to [34:51.320 --> 35:06.820] him. Indeed, they don't know him either. So that's kind of the theory, and I hope we've [35:06.820 --> 35:14.800] demonstrated through simulation, including a simulation on real world data, that this idea [35:14.800 --> 35:24.040] can actually work. So just real quick, I should talk about some of the practical concerns. We're [35:24.040 --> 35:30.840] actually implementing this right now. We're about three weeks into coding, and we hope to have a [35:30.840 --> 35:43.890] prototype of it in the next couple of weeks. Hang on, this has gone mad. Okay. So theory works. [35:43.890 --> 35:49.610] What are the concerns in practice? Well, preventing malicious behavior, obviously. [35:49.810 --> 35:55.030] Freenet is the type of peer-to-peer software that expects to be attacked, [35:55.030 --> 36:03.770] and therefore it's essential that one person cannot easily take down the network or otherwise [36:04.550 --> 36:12.430] make themselves a nuisance. It's essential that it's easy to use. This is a problem that Freenet [36:12.430 --> 36:19.610] has certainly experienced. But right back for the past two decades of security software, [36:19.610 --> 36:25.550] including, for example, PGP, people have always found that when you create a really cool piece [36:25.550 --> 36:33.530] of software that does something really cool in terms of anonymity, privacy, or other kind of [36:33.530 --> 36:39.570] crypto stuff, people just don't use it, or at least it doesn't achieve wide adoption because [36:39.570 --> 36:47.370] it's just too difficult to use. With this next iteration of Freenet, we really want to tackle [36:47.370 --> 36:56.050] that head on. So we need to think about how do we actually make this thing usable? Additionally, [36:56.050 --> 37:01.570] how is data going to be stored in this architecture? And perhaps maybe it can do [37:01.570 --> 37:07.490] other things other than just storing and retrieving data as Freenet currently does. [37:08.790 --> 37:16.450] So, preventing malicious behavior. What are the threats? Well, somebody could potentially select [37:16.450 --> 37:24.650] an identity to attract certain types of data or otherwise act maliciously. They could potentially, [37:24.650 --> 37:30.750] through a similar means, manipulate the identities of other nodes for some nefarious purpose. [37:31.370 --> 37:36.390] How do we ensure ease of use? Well, one requirement is that peers will need to be, [37:36.390 --> 37:41.090] or at least most peers will need to be always on. That's not so much of an issue now that [37:42.610 --> 37:50.550] broadband is better deployed and is being deployed so quickly. How do we introduce peers? [37:51.270 --> 37:58.170] Can we do it by email? Kind of a PGP style thing where you have a block of data that you can cut [37:58.170 --> 38:03.670] and paste into Freenet and that can facilitate introduction. Maybe you can do it by phone, [38:03.670 --> 38:08.270] verbally phoning up your friend and saying, hey, let's do this. Here's the kind of code number [38:09.090 --> 38:14.010] to allow us to connect to each other securely. Or maybe you're willing, maybe you've got a lower [38:15.330 --> 38:21.670] threshold and you're willing to trust some third party to negotiate this introduction. [38:21.770 --> 38:26.350] What about NATs and firewalls? One of the big problems that peer-to-peer has experienced over [38:26.350 --> 38:31.930] the past few years is that with peer-to-peer, it's essential that people can make incoming [38:31.930 --> 38:39.030] connections to your peer and NATs and firewalls make that a lot more difficult. Fortunately, [38:39.030 --> 38:44.110] people have developed techniques to get around that, but that adds challenges in terms of peer [38:44.110 --> 38:49.470] introduction. So we can use UDP hole punching as kind of an increasingly standardized way to [38:49.470 --> 38:56.390] achieve that. It's used by Digger, another one of my projects, and Skype. But that would require [38:56.510 --> 39:05.350] a third party for negotiation. So in conclusion, real quick, so we have time for a few questions. [39:05.770 --> 39:11.530] We believe that this is not only possible, we're going to do it and we are doing it. There's still [39:11.710 --> 39:17.810] a lot of work to do on the theory. In other words, can other models work better? In particular, [39:17.810 --> 39:25.630] right now, when nodes choose each other to decide whether swapping would be advantageous, [39:25.630 --> 39:32.070] they do so at random. That's kind of nice for some of the mathematics that we haven't really [39:32.070 --> 39:40.250] discussed for lack of time, but it may mean that it doesn't converge to a good [39:40.250 --> 39:45.610] network as quickly as it could. So we need to explore perhaps a more directed search for peers [39:45.610 --> 39:53.790] to swap with. And it needs, like everything, it needs to be tested on more data. [39:54.410 --> 39:59.550] We've learned the hard way that practice is more difficult than theory, particularly with [39:59.550 --> 40:06.850] Freenet. Security issues clearly are critical. That's one of our our major focuses. And [40:06.850 --> 40:11.250] deployment of the network, you know, we could come up with the coolest thing in the world that's [40:11.250 --> 40:17.570] ultra secure. If it's not easy to use, we'll get 10 users and it won't be useful to anyone. [40:18.440 --> 40:24.550] So if you're interested in participating, helping Freenet, if you don't know, it's an open source [40:24.550 --> 40:32.210] project where we try to be very open to people who are willing and able to make a contribution. [40:32.210 --> 40:41.750] So if this interests you, our website is freenetproject.org. And Oscar insists that I [40:41.750 --> 40:51.270] show you this slide. So I guess we have about five minutes for some questions. [40:51.770 --> 41:14.650] So the question was, what is the incentive for people to acquire a lot of neighbors? Well, [41:14.650 --> 41:20.510] the incentive is actually quite simple. The more neighbors you have, the better connected to the [41:20.510 --> 41:26.090] network you are, and therefore you'll be able to find and retrieve data more quickly. If you, [41:26.090 --> 41:31.490] let's say you've only got one connection to the network, chances are they're on a ADSL broadband [41:31.490 --> 41:37.750] line. They've got perhaps 10 or 20 kilobytes per second upstream. If you want to download [41:37.750 --> 41:42.690] something and you're just relying on one person, that's going to place a serious limit on the [41:42.690 --> 41:46.990] speed with which you can do that. So do you want to comment? No, I just wanted to say it is an [41:46.990 --> 41:51.210] extremely important question that needs to be addressed because you really do need people to [41:51.210 --> 41:55.430] have a lot of friends. If everyone just connects to one person, you get a network that's one long [41:55.430 --> 42:00.090] string and you're not going to get anywhere. So you're right, and that has to do with this when [42:00.090 --> 42:04.430] we're talking about ease of use, that how we deploy this, how we get people to install it, [42:04.430 --> 42:08.870] and what they do right afterwards is really going to affect whether it can work or not. [42:08.870 --> 42:14.090] So it's something that one needs to be very careful with. And this is the insane part about [42:14.090 --> 42:19.830] trying to write these networks which rely on these emergent effects, that some of it is out of our [42:19.830 --> 42:24.710] hands. It's not like deploying normal software. We just write software that works. We actually [42:24.710 --> 42:41.700] need people to use it in the right way. But, you know, I don't think we've gotten there. [42:43.760 --> 42:55.620] Yeah, you basically, you would just disconnect from them at that point. I mean, you can, [42:55.620 --> 43:03.020] as you can start them up. And also, I mean, there are lots of these trust issues. Like, [43:03.020 --> 43:07.580] for instance, you could want to deal with, people who are less paranoid might want to [43:07.580 --> 43:12.520] allow for a friend of a friend connection so as to speed the network up and stuff like that. [43:56.650 --> 44:04.850] So if I can kind of address your core point, because no one else can hear you. So [44:04.850 --> 44:11.290] I think your core question was, we make the assumption that shorter paths are almost always [44:11.290 --> 44:16.470] better. And in this, we've ignored the fact that some people are on modems, some people are on [44:16.470 --> 44:21.670] fast ADSL connections, etc, etc. And that's a good point. We haven't discussed that. But we [44:21.670 --> 44:29.790] have actually considered that. The approach that we're considering in order to address that issue [44:30.210 --> 44:39.230] is, in effect, you split up the friends that you're connected to into several groups. Let's [44:39.230 --> 44:43.850] say it's two groups for simplicity. You have your fast friends and your slow friends. So [44:43.850 --> 45:02.430] the top 50% who's faster, the bottom 50% who's slower. Yeah, yeah. So you don't slot them into [45:02.430 --> 45:09.290] fixed categories. You can adapt that as time goes on. And then when you start out routing, [45:09.710 --> 45:17.890] you want to try and find it from your fast friends first. So when you initiate a request, [45:17.890 --> 45:24.970] you will send it to your faster friends. And if that fails to find it, then you resort to [45:24.970 --> 45:29.830] your slower friends. I'm sorry, I don't really have time to give a more in-depth explanation. [45:46.130 --> 45:52.410] Well, well, I mean, that is one of the dangers. People trying to manipulate the network with [45:52.410 --> 45:58.070] fraudulent swap requests. And there are a variety of ways that you can mitigate. There are a variety [45:58.070 --> 46:03.670] of ways you can mitigate it. One example would be, well, I don't really have time to go into it, [46:03.670 --> 46:11.690] but we have thought about a technique that's a variation on how you can do secure group random [46:11.690 --> 46:17.870] number generation. So basically get someone to cryptographically commit to a certain rate. Well, [46:17.870 --> 46:21.950] I can't really explain it in the time available, but we'll talk later. [46:26.490 --> 46:48.270] We're just done. One more question. Right. Well, I mean, that is in effect up to [46:48.270 --> 46:54.950] users' self-interest. It is in users' self-interest to trust the people that they're connecting to [46:54.950 --> 47:05.610] and as such, our hypothesis is that they will tend to form a social network. It so happens that the [47:05.610 --> 47:16.770] criteria for a structured network to work here are actually pretty robust. It doesn't demand that you [47:16.770 --> 47:23.670] have exactly the one over distance distribution that Kleinberg suggested. It's actually very, [47:24.230 --> 47:31.310] and beyond that, addressing the issue while you're saying the John Kerry problem, in many ways, [47:31.310 --> 47:37.870] that's kind of a usability issue, steering people towards a certain model of usage of the software, [47:37.870 --> 47:42.490] just in terms of how it interacts with users. I'm afraid we're going to have to end it there. [47:42.490 --> 47:43.210] Thank you. [47:51.400 --> 47:52.600] We'll talk about that.