WEBVTT 00:03.900 --> 00:27.600 The problem that I think we're all seeing, and certainly that we've kind of been growing increasingly concerned about for some time, is that it's not enough anymore that you can participate in a peer-to-peer network and nobody can tell what you are doing. 00:27.760 --> 00:39.960 Increasingly it's the case in this country and elsewhere that simply the act of participating in a peer -to-peer network is in itself a pretty risky thing to do. 00:40.780 --> 01:00.900 As a result, we believe that future anonymous peer-to-peer networks will need to limit who your peer connects to to a group of trusted friends, people that you have decided you don't mind that they know that you're a part of this peer-to-peer network. 01:01.300 --> 01:04.500 The big question is, is it possible? 01:04.500 --> 01:07.500 And if it's possible, will it be useful? 01:09.300 --> 01:18.340 Just for those, quickly to clarify the term peer-to-peer, 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:42.820 Specifically, it's designed to help people find information that is widely distributed across a large number of computers which are connected through some network, in practice typically the internet. 01:43.000 --> 01:46.000 Users of this system want to find information. 01:46.000 --> 01:53.220 They need to know where the information is so that they can go out and retrieve it. 01:53.220 --> 01:55.740 There are different approaches to this. 01:55.740 --> 02:03.900 The first peer-to-peer network in many ways was a piece of software called Napster, and its approach was pretty simple. 02:04.060 --> 02:16.200 Every peer in the network simply reported to a central server or eventually one of several central servers what data was being stored on that computer. 02:16.600 --> 02:28.820 And so if you wanted to find some data, you'd go to the central server and say, you know, where's this thing, and it would give you a list of computers where you could find it, and you would then connect to those computers directly and retrieve it. 02:31.120 --> 02:51.720 Subsequent to that, when Napster and similar systems were being shut down, because of course a centralized system is very easy to shut down, people started working on what we call semi-centralized peer-to-peer networks, where it's essentially the same idea but instead of one centrally administered index of data, 02:51.720 --> 02:57.520 you have a large number of decentralized indexes. 02:57.520 --> 03:05.200 So when you connect to the network, you're allocated one or more of these indexes, and you use that pretty much like a mini-Napster. 03:05.440 --> 03:09.960 Kazaz is probably the archetypal example of that approach. 03:11.140 --> 03:31.240 Well, other peer-to-peer networks strive to be completely decentralized, such that in essence each peer in the network does pretty much the same job and has loosely the same degree of responsibility as every other peer in the network, and Freenet is one of several examples of peer-to-peer networks like that. 03:33.510 --> 03:43.570 Another way that you can classify peer-to-peer networks, and it's particularly useful for the purposes of our talk, is into light and dark. 03:43.570 --> 03:57.470 Examples of light peer-to-peer networks, or you could also call them promiscuous peer-to-peer networks, include Nutella, Freenet, distributed hash tables, indeed the vast majority of peer-to-peer networks that you've probably heard of. 03:59.610 --> 04:16.750 In essence, a light peer-to-peer network is defined by the fact that your computer will willingly connect to strangers, which means that strangers, people you don't know or trust, can discover that you are running the software. 04:17.070 --> 04:33.090 The advantage of this is that if you do it right, it can be globally scalable, which essentially means whether you have 100,000 users or 100 million users, you can still find information pretty efficiently. 04:33.390 --> 04:37.030 The disadvantage is it's vulnerable to harvesting. 04:37.290 --> 04:48.810 If, for example, the Chinese government wanted to get a nice, convenient list of all of the people in China that were running Freenet, they could do that. 04:48.810 --> 04:52.370 It wouldn't necessarily be easy, but it would certainly be possible. 04:53.270 --> 05:09.210 When we first came up with the idea, we didn't really see this as... well, this wasn't really on our radar, but over the past few years we've realized that it's not only in increasing threatened countries like China, but also in this country. 05:09.210 --> 05:24.790 I think most people here are probably familiar with recent court decisions which have 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:45.990 These networks are characterized by the fact that peers in this network only talk to other peers directly, only establish a direct line of communication with other peers that they trust, that their user trusts. 05:45.990 --> 05:51.770 So the user is saying, I don't mind that these people know that I'm part of this network. 05:52.350 --> 05:55.990 An example of this is a piece of software called Waste. 05:56.830 --> 06:02.530 The advantage of this, as I said, is that only your friends know that you're part of the network. 06:02.530 --> 06:09.150 The disadvantage is that until now this type of network really doesn't scale. 06:09.150 --> 06:10.830 Typically you might have 10... 06:10.830 --> 06:15.650 you have isolated pockets of perhaps 5 to 10 people. 06:15.950 --> 06:25.730 And while some people have found that to be a useful thing, clearly there's a big difference between that and being part of a global network with millions of users. 06:27.270 --> 06:44.490 Shifting gears a little bit, networks like Freenet and completely decentralized networks rely on something called the small world phenomenon in order to find information in this completely decentralized way. 06:44.990 --> 07:02.690 Some of you, I'm sure most of you are familiar with the small world concept, or you may also be familiar with the game of Kevin Bacon where you try to get from Kevin Bacon to any one actor just by going through movies they've been in. 07:05.290 --> 07:39.390 So a guy called Stanley Milgram in the 1960s did a very interesting sociological experiment where he wrote the names of two people, of a number of people actually in Cambridge, Massachusetts on some letters and gave them just to random people spread throughout the United States with the instructions that they were to try to get these letters to the intended recipients but only by giving them to someone they personally knew who themselves would give it to someone else they personally knew. 07:39.390 --> 07:49.650 And very interestingly he found that when those letters arrived they did so in perhaps they went through just five or six people. 07:49.650 --> 07:55.270 So that's five or six people in a country of 270 million odd people. 07:55.590 --> 08:06.130 Clearly a very scalable way to get something from where it is to where you want it to be and interestingly also completely decentralized. 08:06.130 --> 08:13.210 These people were not relying on any central phone directory in order to figure out where they should route this information. 08:13.210 --> 08:17.250 They were doing it purely on the basis of their friends. 08:18.070 --> 08:22.150 So what characterizes a small world network? 08:22.150 --> 08:39.050 Well typically in small world networks in small in small world networks what you find is is that you have short paths exist between any two people. 08:39.050 --> 08:48.230 You can, if you know how, you can get from any one person to any other person in a short number of steps even if there are millions of people in the network. 08:48.230 --> 08:54.410 The challenge is that these short paths aren't necessarily easy to find. 08:55.350 --> 09:13.410 In the in the case of in the case of Milgram's experiment people were able to use information that they had about their friends in effect as signposts as to which of their friends they should send the letter to next. 09:13.410 --> 09:31.670 They knew that if one of their friends perhaps lived near Massachusetts that they would be a good choice to forward the letter to if having reached that person that person knew somebody who was close to the street or perhaps went to the same university as the intended recipient they could send it on. 09:31.670 --> 09:42.110 So in in social networks people are able to use their knowledge of their friends as signposts for route it for finding these short paths. 09:42.730 --> 09:51.610 Well the reason this works is that there is people have a concept of similarity between other people. 09:51.610 --> 10:03.990 You know that if two guys live on the same street they're likely to be more similar to each other and therefore more likely to to be connected to each other than someone living out in Zimbabwe. 10:06.760 --> 10:18.500 So so the the algorithm is simple once you've got this concept of similarity you simply route to the person that you know of that is closest to where you want to be at each step. 10:19.060 --> 10:20.960 We call this greedy routing. 10:21.380 --> 10:29.040 Freenet and distributed hash tables rely on this principle to find data in a scalable decentralized way. 10:33.400 --> 10:45.440 So so Ian just started by talking about the these peer-to-peer networks and essentially the problem the dark peer-to-peer networks that we want to address and then he talks about the small worlds and social networks forming small worlds. 10:45.440 --> 10:59.780 So what we want to talk about here today and what we what we're interested in is how can we apply this knowledge about small world and about these social networks 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:20.720 This darknet the peer-to-peer network that's formed when people connect only to people they trust will be just this big encrypted network of people's relationships just like the social networks that sociologists and people work with. 11:20.720 --> 11:32.560 So the environment that we're trying to deal with in our peer-to-peer networks is just this social network that Milgram's experiment took place in and that we want to find a way to deal with. 11:32.660 --> 11:39.460 And we're interested of course always when we're trying to search and being able to find a way from one point to another in the network. 11:39.460 --> 11:46.400 We have this network that's large network connections going all over the place and we need to find a way from one point to another. 11:46.400 --> 11:55.360 Well we know that in the social network and the darknet is like a social network, is a social network, we people can find a way from go from one place to another. 11:55.520 --> 12:00.420 Milgram's experiment showed people can root in social networks and they can do it well. 12:00.420 --> 12:08.720 He took only five or six steps to go from one side of this country to another to a complete stranger and people can do that. 12:08.720 --> 12:12.200 So if people can do it then well so should computers. 12:12.200 --> 12:14.440 I mean computers are much smarter than people right? 12:15.220 --> 12:27.700 So to try to do this somehow, make computers do this, we need some sort of mathematical understanding for what's going on in the small world network. 12:27.740 --> 12:40.880 And this mathematical understanding has is something rather recent but a Cornell professor named John Kleinberg provided a model about five years ago that explains how these networks can look in order to be navigable. 12:40.880 --> 12:49.700 In order for it to be possible as Ian said to find signposts in the network that will take you where you want to go, it needs to have a certain configuration. 12:51.160 --> 13:14.500 And this configuration is that the possibility of being able to find routes efficiently from one point to another rests on the fact that you have people who have similarity to one another and as Ian said are more likely to be connected and then you have a certain proportion of connections of different lengths with respect to some sort of position. 13:14.540 --> 13:17.780 And in the simplest model position can just be where people live. 13:17.780 --> 13:21.800 And you say that people are more likely to be connected if they live close to one another. 13:21.840 --> 13:30.580 And as we get further away we need this to be the probability that people know each other that they are connected needs to decrease. 13:30.580 --> 13:35.480 And when this happens that's when you can find an easy way to route in the network. 13:35.740 --> 13:41.180 So for our talk we're actually going to allow people's positions to just be in a ring. 13:41.180 --> 13:46.400 And that doesn't mean that we think that people exist on a ring but this is the very simplest model. 13:46.400 --> 13:55.680 We allow each person to just get a position on the ring and then we see people knowing each other as these chords in the circle that skip over the people. 13:55.680 --> 13:57.240 So here I have two examples. 13:57.360 --> 14:05.960 We've placed these positions in a ring in the mathematical idealized model and we say that there are two green people who know each other and two red people who know each other. 14:05.960 --> 14:09.340 But if you can see the red one covers more of the circle. 14:09.480 --> 14:12.420 It's a longer link therefore it needs to be less common. 14:12.420 --> 14:23.140 And according to Kleinberg's model it needs to be these long links which this one covers double as many steps along the edge here so it needs to be half as common as the green one does. 14:25.260 --> 14:36.940 And if this is the case, if you have these connections, if we can put people into this base model with a circle or just a... and we have connections that agree with Kleinberg's model. 14:36.940 --> 14:40.380 We have some... every once in a while we run into a long connection. 14:40.460 --> 14:46.300 Somebody happens to know somebody who lives way on the other side of the world but that's rather rare. 14:46.300 --> 14:51.460 More commonly people know lots of people who live close to them who are close to them who are similar to them. 14:51.460 --> 15:04.420 If this is the case and you have this model then we can do this greedy routing that Ian describes which just says I'll always go to the... if I'm going to some destination I always just step to the neighbor who's closest to my destination. 15:04.460 --> 15:16.200 And if I can do that in... if the configuration of these friends is correct then the greedy routing can be mathematically proved to perform in something on the order of log squared n steps. 15:16.220 --> 15:18.460 And when something is log that's good. 15:18.460 --> 15:19.700 If it's not log it's bad. 15:19.700 --> 15:22.260 But we have log here so that's going to help us. 15:22.300 --> 15:32.140 That means that we have an efficient way of finding steps from one way to another which is exactly what we want if we want to be able to search and route in our dark peer-to-peer network. 15:33.240 --> 15:37.620 So this is an example, a simulated example of how such a network would look. 15:37.620 --> 15:42.320 Now I've imagined again I've just placed people's positions on a circle like this. 15:42.320 --> 15:44.440 All around there are people placed on the circle. 15:44.440 --> 15:47.320 We have two red people who are circled at the end. 15:47.320 --> 15:58.860 And if you want to do a greedy route from one to the other you simply follow these cords which represent the friendships and you try to get from one place to another by always choosing the friend who is closest to the destination. 15:59.100 --> 16:01.300 And so a route would look something like that. 16:01.420 --> 16:07.580 In the beginning, in the very first step we can take a very long step because that takes us a lot closer to our destination. 16:07.600 --> 16:12.060 As we get closer it becomes harder and harder to find steps that take us a long way. 16:12.060 --> 16:17.220 But eventually you do reach the destination and you do so in a bounded number of steps. 16:18.520 --> 16:33.180 But this is greedy routing and this is on a circle and I placed everyone on a circle in this imaginary world where it is extremely easy to find to say if you're closer to somebody than somebody else because you have a circle and you can say how many steps is it to him. 16:33.200 --> 16:44.060 But if we're trying to do greedy routing in a real social network, in the kind of social network that our darknet is going to form, we don't have an easy way of saying is one person closer to another. 16:44.060 --> 16:46.420 We end up having to answer questions like this. 16:46.420 --> 16:48.860 Is Alice closer to Harry than Bob? 16:49.000 --> 16:50.880 I'm trying to route in a social network. 16:50.880 --> 16:55.840 I'm this person in the Milgram experiment with the letter and the letter is going to Harry. 16:56.880 --> 17:00.040 And I have to ask myself should I send it to Alice or Bob? 17:00.960 --> 17:02.480 The letter has to go to Harry. 17:02.480 --> 17:03.480 I have to make a decision. 17:03.480 --> 17:05.920 Should I send it to Alice or should I send it to Bob? 17:05.920 --> 17:17.460 Well, as a person I make some sort of a judgment and in Milgram's experiment people have to make this judgment based on some idea of who of closeness between people. 17:17.500 --> 17:19.980 The most basic form would then be where do they live. 17:20.280 --> 17:24.520 If Alice happens to be Harry's neighbor then she is probably closer. 17:24.520 --> 17:29.140 There's a greater chance that they know each other than that Bob would know Harry. 17:29.140 --> 17:32.240 But you could also go on, for example, what their occupations are. 17:32.240 --> 17:38.640 People who are all hackers are more likely to have met at Defcon than somebody who's an ice dancer or something. 17:40.880 --> 17:43.540 But you could go, you know, jobs, interests. 17:43.540 --> 17:52.180 As a person, we do these kind of judgments all the time and it's not that hard for us to say what would be closer to one person than another. 17:52.300 --> 17:56.800 But now what we want to do is we have this dark net which is this social network. 17:56.800 --> 18:00.220 We want to find a way to route and we want a computer to do it. 18:00.220 --> 18:07.080 And in practice we can't really ask the computer to make these decisions based on what people live, what they do, etc. 18:07.200 --> 18:19.060 I mean actually this isn't as insane as it may sound because people have actually tried this and one can try to put into the computer as much personal information as the people as possible. 18:19.120 --> 18:26.700 Then you try to do some sort of closeness algorithm based on people's personal information trying to match it so that you can make these routing decisions. 18:28.020 --> 18:36.720 But the fact is that what it has shown, even if you try to use a large number of criteria, computers are not good at making these sort of value judgments. 18:36.900 --> 18:47.480 And even more than that what we're trying to build are anonymous file sharing networks and they will not be a big hit if the first thing we do is ask everyone to put in all their personal information so that we can route. 18:47.920 --> 18:50.700 It just doesn't go over well with our target audience. 18:50.700 --> 18:56.000 So we have to find a different way to answer these things with Alice, Harry, and Bob. 18:56.000 --> 18:57.500 Who is closer to who? 18:57.620 --> 19:04.080 And so the thing is, and this is what's extremely important, is the information is there in the network. 19:04.080 --> 19:13.780 We can let the network itself tell us who is closer to who and we don't need to know anything about them except the network itself. 19:13.780 --> 19:21.320 We don't need to know where they live, we don't need to know what they do, all we need to have is this network and we work based on that. 19:22.460 --> 19:24.220 So how would we do this? 19:24.220 --> 19:31.840 Well, we have this model of John Kleinberg that tells us what should the world look like for it to be possible to greet a route efficiently. 19:32.080 --> 19:37.520 Well, what the world should look like is that there should be few long connections and many short ones. 19:37.520 --> 19:47.140 Most people should be... most friends that you have should be close to one another, whereas you should once in a while have a long connection out to somebody who doesn't. 19:47.140 --> 19:56.600 And then, knowing this and having this graph, all we need to do is basically give people positions in a way so that this becomes true. 19:56.780 --> 20:12.540 We just say, forget about the world, forget about where you live, forget about what you do, I don't care any about that, we're going to make believe, we're going to make positions for you based on the network and make it so that the properties that we are looking for are fulfilled. 20:12.820 --> 20:27.020 So what you can say is in a way, rather than taking the positions and trying to root on people's real positions in this sort of social space, we reverse engineer the positions of the people based on how the social network looks. 20:27.460 --> 20:32.940 And that is what allows us to give people new positions that we then can use to root. 20:32.940 --> 20:41.260 And once we have these positions, we can then do the simple greedy rooting of always trying to go to the closest point and we get what we want. 20:41.780 --> 20:45.460 And the method to do this is actually surprisingly simple. 20:45.460 --> 20:50.380 There's some deep mathematical magic involved, but it actually turns out to be extremely simple. 20:50.480 --> 20:57.800 When people join the network, they simply choose 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:14.200 And when you do that, of course, this is not going to be true, because two people who could be very close in some sense in the social network, of course, could have chosen positions at opposite ends, because it's completely random. 21:14.200 --> 21:16.660 In fact, they will choose positions at opposite ends. 21:16.660 --> 21:29.620 But then we have an algorithm where people get together, and then they swap their positions with one another, so as to minimize the product of the distances to their friends. 21:29.700 --> 21:31.980 And this is extremely important, and it has to do with the math. 21:31.980 --> 21:40.480 But they get together, they contact each other over the network, and they say, I have positioned this, you have positioned that, maybe we'll just switch and we'll be better off. 21:41.440 --> 21:43.720 And this is an example of that sort of switch. 21:43.720 --> 21:48.020 These two people have chosen their positions randomly, and so have their friends. 21:48.020 --> 21:55.520 And you have a green person who's got three green friends marked by these cords in the circle, and you have a red person who's got three red friends. 21:55.520 --> 22:03.560 But as it has been, since they chose their positions randomly, they happen to choose them on opposite sides of the network from their friends. 22:03.560 --> 22:05.200 And this is not what we're looking for. 22:05.200 --> 22:12.280 We're looking for something that fulfills this model, that people who have lots of friends on one side, they should be on one side. 22:12.280 --> 22:15.660 Well, what if red and green were to swap positions with one another? 22:15.660 --> 22:17.600 Then we get something that looks like this. 22:17.600 --> 22:21.080 And this is much more in line with what we are looking for in our model. 22:21.080 --> 22:30.560 We have one or two long connections, we need some long connections, but mostly we have these short local connections, so the people are close to the people that they are connected to. 22:31.880 --> 22:35.860 And so this is essentially the algorithm as it goes. 22:35.860 --> 22:40.840 I mean, there's some math involved, and some formulas and stuff that I can give to the interested people. 22:40.860 --> 22:49.740 But essentially, choose positions randomly, and then they switch when it looks like switching will make this network more like what we're looking for. 22:50.640 --> 22:54.720 And some things to note is that this switching step is essential. 22:54.840 --> 23:02.500 We couldn't say, for instance, let's just have everyone choose a position, and just take a position that's close to their neighbors. 23:02.500 --> 23:06.620 Because what happens if you do that, is everyone ends up choosing the same position in the end. 23:06.620 --> 23:12.820 Once you've done it enough times, everyone's like, oh, I want to be closer to my neighbors, and they want to be closer, and it just converges on the same point. 23:12.860 --> 23:17.760 You get a bunch of people who are all saying that 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:30.440 And one problem with this technique, of course, is that these identities that we use to root are going to be changing as people switch. 23:30.440 --> 23:36.160 And that's something that has to be dealt with at the application level, because people do not have a permanent identity. 23:36.160 --> 23:37.860 But there are ways of going around this. 23:37.860 --> 23:45.460 As long as we have one way of finding path from one path to another, one place to another, we can deal with the fact that people's identities may change. 23:46.220 --> 23:55.500 Okay, so now for the simulations, always a necessity to show that we've done some simulator data, to show that this can actually work. 23:55.840 --> 24:04.100 And so what we have is three different modes here, which are essentially two controls and one good, and one sort of where we have applied our algorithm. 24:04.100 --> 24:06.420 The first control is the random route. 24:06.440 --> 24:13.540 If you start with a network, we have no positions whatsoever, and we're just looking to find a way of looking for data in this network. 24:13.540 --> 24:17.620 With no positions, no knowledge about anything, we can't do any form of greedy routing. 24:17.620 --> 24:21.900 All we can do is stumble around randomly and hope that we find our destination. 24:22.000 --> 24:27.300 So this is sort of the control of where you start out, the random network, the random search. 24:27.300 --> 24:28.620 That's all you can do. 24:29.660 --> 24:44.600 And the other control is going to be the completely idealized situation, where we have created a network that agrees with this model according to some position scheme, and we have this good network that's known to perform in log squared time. 24:44.720 --> 24:48.700 This is where everything is good, but that's not the situation that we actually have. 24:48.700 --> 24:59.160 The situation that we actually have is something where we have a network just like this good one, but we don't know anything about the positions, and we have to use our algorithm to try to restore the positions. 24:59.480 --> 25:03.060 And that's what I have as the third data set will be the restored data. 25:03.060 --> 25:04.860 That will be our algorithm applied. 25:05.620 --> 25:11.920 So the first thing I'm going to do is show the success rate within these log n squared number of steps, where n is the network size. 25:11.940 --> 25:19.320 You can see the size grows logarithmically there at the bottom, up to about 256,000, I think, for this data set. 25:21.220 --> 25:25.180 And you can see that the random one falls off very fast. 25:25.180 --> 25:28.360 Random routing simply cannot perform in this number of steps. 25:28.360 --> 25:34.360 It fails to find data as the network grows, whereas the good line will stay at the top. 25:34.360 --> 25:35.260 It always succeeds. 25:35.260 --> 25:40.160 The math tells us that it must, so it would only be a bug in my simulator if it wasn't. 25:40.520 --> 25:51.960 But this... and we can see that restoring, applying our algorithm, doing these switches, actually brings the success rate all the way up from the red line almost to the green line. 25:51.960 --> 25:55.840 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:06.860 And the other thing one's interested in, of course, is the number of steps that it takes on average. 26:06.860 --> 26:15.200 And now we can see that even with the falling success rate, the successful queries in the random walk will increase as the size of the network grows dramatically. 26:15.340 --> 26:25.440 The good ones will stay low, just like the math tells us, and the restored one can bring us almost all the way down to an acceptable number of steps. 26:26.960 --> 26:34.160 But of course, that's simulated data, and we started with the model that we're applying, and that's always a little suspect. 26:34.160 --> 26:38.600 I'm basically doing, making, giving myself an idealized situation. 26:38.800 --> 26:42.980 So a more interesting question is, how do we do this if we have real-world stuff? 26:43.020 --> 26:58.380 Well, so to get some real-world stuff, rather than asking for permission, we simply borrowed some, and we went and grabbed 2,200 people from orkut.com, which is this social networking site that Google started, I think, about a year and a half ago. 26:58.380 --> 27:04.980 Everyone ran there because it was a fad or something, and put in all their friends, and then no one's done anything with it. 27:05.020 --> 27:13.220 So I think, because as far as I know, it's rather useless, but it does provide a very good data on social networks and how they look. 27:13.260 --> 27:25.820 So we grabbed some data from this, and we spidered a set of people, starting with our friend Ian here, and going and taking people so as to create a rather dense social network. 27:27.960 --> 27:44.680 And as it happened, this was done rather randomly, but as it happened, I guess that's not too surprisingly, given maybe Ian's... starting with Ian, but most of the people were programmers, techies, people in the technology community, and mostly Americans, 27:44.680 --> 27:46.660 very few non-Americans in the set. 27:48.000 --> 27:53.700 And I think that I would imagine that, say, maybe some of the people who are in this set are actually here today. 27:54.160 --> 27:56.460 Not just Ian, but somebody who was in it. 27:56.460 --> 27:59.120 And just as a note, we got no Brazilians. 27:59.120 --> 28:06.800 If someone has logged in to Orkut recently, you know that it's been overrun with Brazilians, because apparently in Brazil it's useful for something. 28:08.380 --> 28:16.920 So there are like 70 or 80% Brazilians there, but this set, apparently that social network is rather disconnected from this one. 28:16.920 --> 28:19.460 So our set contains programmers, Americans. 28:19.460 --> 28:22.960 There weren't a lot of these Brazilians who do whatever they do on Orkut. 28:23.620 --> 28:29.960 And just as a note, because when people talk about small worlds, they often talk about degree distributions and power laws. 28:29.960 --> 28:35.900 And we did have a power law degree distribution here, in the sense that there were a couple of people. 28:35.960 --> 28:39.800 When you talk about a degree in a network, you mean the number of people that somebody knows. 28:39.940 --> 28:48.140 So the most popular person here, and I think the most popular person in the set was Orkut Bukhokan himself, the guy who founded the site. 28:48.340 --> 28:51.100 He had 289 friends in the set. 28:51.100 --> 28:53.660 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:12.540 So dealing with this data set now, we want to apply this switching algorithm, and hope that this will do something good. 29:12.540 --> 29:15.060 Something that can beat just a random search. 29:15.240 --> 29:17.980 And a random search performs rather well on this data. 29:17.980 --> 29:23.220 And the reason that a random search performs well is that it will... is because of this degree distribution. 29:23.220 --> 29:29.340 Because you run into people who know so many people, it's easy to run into the person that you're looking for. 29:29.340 --> 29:32.080 So with power laws, it tends to perform rather well. 29:32.080 --> 29:41.160 So in this log n squared steps, and you should all be able to do that in your head, but 2000 log n squared, that's about 120 something, right? 29:41.260 --> 29:45.040 So in about 120 steps, the success rate was 72. 29:45.040 --> 29:47.980 And of the successful ones, it was about 43. 29:47.980 --> 29:51.820 So for randomly searching a network of 2000, this is rather good. 29:51.900 --> 29:55.160 So the question of course is, if we run the switching, try to apply this. 29:55.160 --> 29:57.000 This is a real social network. 29:57.060 --> 30:01.960 Can we just get somewhere with this greedy routing by assigning identities? 30:01.960 --> 30:03.200 And the answer is yes. 30:03.240 --> 30:11.800 So with our algorithm, we can search with a 97% success rate in this data, and on the mean number of steps is only about 7.7. 30:12.000 --> 30:27.220 So we are rather happy with that result, because it really shows that we can massacre the random search by performing this ordering, and we can get something that actually seems, it actually looks like the social network lives up to the model and what we were looking for. 30:27.600 --> 30:34.660 And one thing one can see is that this degree distribution, the fact that there are people who knows many people, can affect the results. 30:34.700 --> 30:44.660 So if we clip the degree distribution, meaning I don't allow anybody to have more than 40 friends, I just throw away everybody's friends after 40, we can look, was this what was actually going on? 30:44.700 --> 30:52.120 And in the random search, you can see that yes, in this case, success rate falls dramatically, because you don't have these people who know tons of people. 30:52.220 --> 30:59.400 But in the case of our thing, it adds a couple of steps, but the success rate is still good, and it's still dramatically better than the random search. 30:59.520 --> 31:06.560 So we can say that our algorithm can take advantage of this degree distribution, but it was not use it. 31:06.560 --> 31:08.980 And it seems like it actually does work. 31:08.980 --> 31:21.780 Starting with a social network, you can reverse engineer positions, so as to make it possible for a computer to do what people will do when they're trying to pass a letter along, based purely on this stuff. 31:21.900 --> 31:23.220 Are we going to go with the demo? 31:24.620 --> 31:36.200 So to demonstrate this, we were going to show routing in this, between some people in this data set from Orkut. 31:36.800 --> 31:39.320 So one thing to start with, 31:42.740 --> 31:51.360 is starting from Ian himself, who was of course the start of our set, and going to for instance Sergey Brin, who I think we all know. 31:51.360 --> 31:55.460 Ian wants to know how many steps does Sergey bring, because I want to borrow some money or something. 31:56.740 --> 32:05.340 And they will actually search the set, and you can see that it skips from friend to friend, and finds a path from Ian to James in four steps. 32:05.340 --> 32:11.640 And what needs to be noted about this, is that when this does the search, it does it in a decentralized fashion. 32:11.640 --> 32:24.920 It never looks at anything at any step, except who your friends are, and it decides which of Ian's friends was closest to Sergey Brin, which of Sean Parker's friends was closest to Sergey Brin, and then when it gets to James Joachim, it finds that he knows Sergey Brin. 32:24.920 --> 32:26.640 So the search is completed. 32:28.080 --> 32:38.560 Another example, we could do person in the set number 1708, which is Fyodor, who I think is at the conference somewhere. 32:39.380 --> 32:44.300 And we could go from him, to now somebody else who's in the set, like Lawrence Lessig. 32:51.380 --> 33:07.800 And that one also succeeds, and you can see how we are honing in in these positions in the circle, always choosing the friend of Fyodor who was closest, and then the closest, and it actually has managed to assign these positions in a way that it can find this path going in. 33:10.440 --> 33:25.560 So one other interesting thing, just while we have this tool that we discovered, is that there are certain people in this data set who aren't... well, they are real people, but it's kind of an abuse of the system. 33:25.560 --> 33:40.560 So for example, you get celebrities or politicians, one example being John Kerry, who someone signed up as John Kerry, and then people will connect to that person, I guess to show that they're going to vote for him or something. 33:40.560 --> 33:54.360 But the interesting thing about people like John Kerry in this data set, is that they don't fit into this small world model. 33:54.360 --> 34:08.800 If you've just got random people connecting to you, then it doesn't fulfill this criteria for a small world, whereby if you know somebody and you know somebody else, then they're more likely to know each other. 34:09.120 --> 34:33.280 So let's say we try to route from Sergey Brin to the fake John Kerry, the results are kind of interesting, and what you actually find is that this will keep going for 200 steps and never actually succeed in finding John Kerry. 34:33.280 --> 34:44.620 And again, the reason for that is very simply that this John Kerry user does not fit into the social network model that we assume. 34:47.220 --> 34:51.540 Yeah, because he doesn't actually know the people that are connected to him. 34:51.540 --> 34:54.380 Indeed, they don't know him either. 34:57.680 --> 35:17.600 So that's kind of the theory, and I hope we've demonstrated through simulation, including a simulation on real world data, that this idea can actually work. 35:17.760 --> 35:23.940 So just real quick, I should talk about some of the practical concerns. 35:23.940 --> 35:26.640 We're actually implementing this right now. 35:27.260 --> 35:33.600 We're about three weeks into coding, and we hope to have a prototype of it in the next couple of weeks. 35:33.960 --> 35:36.240 Hang on, this has gone mad. 35:39.810 --> 35:40.650 Okay. 35:42.070 --> 35:43.890 So theory works. 35:43.890 --> 35:46.450 What are the concerns in practice? 35:46.450 --> 35:49.610 Well, preventing malicious behavior, obviously. 35:49.810 --> 36:06.990 Freenet is the type of peer-to-peer software that expects to be attacked, and therefore it's essential that one person cannot easily take down the network or otherwise make themselves a nuisance. 36:06.990 --> 36:09.970 It's essential that it's easy to use. 36:09.970 --> 36:14.390 This is a problem that Freenet has certainly experienced. 36:14.390 --> 36:34.670 But right back for the past two decades of security software, including, for example, PGP, people have always found that when you create a really cool piece of software that does something really cool in terms of anonymity, privacy, or other kind of crypto stuff, 36:34.670 --> 36:41.990 people just don't use it, or at least it doesn't achieve wide adoption because it's just too difficult to use. 36:42.210 --> 36:48.530 With this next iteration of Freenet, we really want to tackle that head on. 36:48.530 --> 36:53.630 So we need to think about how do we actually make this thing usable? 36:54.990 --> 37:00.030 Additionally, how is data going to be stored in this architecture? 37:00.030 --> 37:07.490 And perhaps maybe it can do other things other than just storing and retrieving data as Freenet currently does. 37:08.790 --> 37:11.470 So, preventing malicious behavior. 37:11.470 --> 37:13.270 What are the threats? 37:13.270 --> 37:23.250 Well, somebody could potentially select an identity to attract certain types of data or otherwise act maliciously. 37:23.250 --> 37:30.750 They could potentially, through a similar means, manipulate the identities of other nodes for some nefarious purpose. 37:31.370 --> 37:33.230 How do we ensure ease of use? 37:33.230 --> 37:39.110 Well, one requirement is that peers will need to be, or at least most peers will need to be always on. 37:39.110 --> 37:48.130 That's not so much of an issue now that broadband is better deployed and is being deployed so quickly. 37:48.130 --> 37:50.550 How do we introduce peers? 37:51.270 --> 37:53.450 Can we do it by email? 37:53.450 --> 38:02.350 Kind of a PGP style thing where you have a block of data that you can cut and paste into Freenet and that can facilitate introduction. 38:02.450 --> 38:07.130 Maybe you can do it by phone, verbally phoning up your friend and saying, hey, let's do this. 38:07.130 --> 38:11.770 Here's the kind of code number to allow us to connect to each other securely. 38:11.770 --> 38:21.670 Or maybe you're willing, maybe you've got a lower threshold and you're willing to trust some third party to negotiate this introduction. 38:21.770 --> 38:23.690 What about NATs and firewalls? 38:23.690 --> 38:38.170 One of the big problems that peer-to-peer has experienced over the past few years is that with peer-to-peer, it's essential that people can make incoming connections to your peer and NATs and firewalls make that a lot more difficult. 38:38.170 --> 38:45.150 Fortunately, people have developed techniques to get around that, but that adds challenges in terms of peer introduction. 38:45.150 --> 38:50.230 So we can use UDP hole punching as kind of an increasingly standardized way to achieve that. 38:50.230 --> 38:54.570 It's used by Digger, another one of my projects, and Skype. 38:55.150 --> 38:59.210 But that would require a third party for negotiation. 39:00.830 --> 39:05.350 So in conclusion, real quick, so we have time for a few questions. 39:05.770 --> 39:10.890 We believe that this is not only possible, we're going to do it and we are doing it. 39:10.890 --> 39:14.290 There's still a lot of work to do on the theory. 39:14.350 --> 39:17.070 In other words, can other models work better? 39:17.070 --> 39:27.350 In particular, right now, when nodes choose each other to decide whether swapping would be advantageous, they do so at random. 39:27.350 --> 39:41.790 That's kind of nice for some of the mathematics that we haven't really discussed for lack of time, but it may mean that it doesn't converge to a good network as quickly as it could. 39:41.790 --> 39:47.110 So we need to explore perhaps a more directed search for peers to swap with. 39:48.750 --> 39:53.790 And it needs, like everything, it needs to be tested on more data. 39:54.410 --> 40:00.770 We've learned the hard way that practice is more difficult than theory, particularly with Freenet. 40:00.990 --> 40:03.990 Security issues clearly are critical. 40:03.990 --> 40:06.390 That's one of our our major focuses. 40:06.610 --> 40:12.430 And deployment of the network, you know, we could come up with the coolest thing in the world that's ultra secure. 40:12.430 --> 40:17.570 If it's not easy to use, we'll get 10 users and it won't be useful to anyone. 40:18.440 --> 40:32.210 So if you're interested in participating, helping Freenet, if you don't know, it's an open source project where we try to be very open to people who are willing and able to make a contribution. 40:32.210 --> 40:39.030 So if this interests you, our website is freenetproject.org. 40:39.970 --> 40:43.470 And Oscar insists that I show you this slide. 40:44.050 --> 40:51.270 So I guess we have about five minutes for some questions. 40:51.770 --> 40:52.450 So 41:03.130 --> 41:14.370 the question was, what is the incentive for people to acquire a lot of neighbors? 41:14.370 --> 41:16.390 Well, the incentive is actually quite simple. 41:16.390 --> 41:25.770 The more neighbors you have, the better connected to the network you are, and therefore you'll be able to find and retrieve data more quickly. 41:25.770 --> 41:32.510 If you, let's say you've only got one connection to the network, chances are they're on a ADSL broadband line. 41:32.510 --> 41:36.830 They've got perhaps 10 or 20 kilobytes per second upstream. 41:36.830 --> 41:44.430 If you want to download something and you're just relying on one person, that's going to place a serious limit on the speed with which you can do that. 41:44.430 --> 41:45.450 So do you want to comment? 41:45.450 --> 41:52.350 No, I just wanted to say it is an extremely important question that needs to be addressed because you really do need people to have a lot of friends. 41:52.350 --> 41:57.710 If everyone just connects to one person, you get a network that's one long string and you're not going to get anywhere. 41:57.910 --> 42:08.870 So you're right, and that has to do with this when we're talking about ease of use, that how we deploy this, how we get people to install it, and what they do right afterwards is really going to affect whether it can work or not. 42:08.870 --> 42:11.430 So it's something that one needs to be very careful with. 42:11.550 --> 42:20.490 And this is the insane part about trying to write these networks which rely on these emergent effects, that some of it is out of our hands. 42:20.490 --> 42:22.350 It's not like deploying normal software. 42:22.350 --> 42:24.350 We just write software that works. 42:24.350 --> 42:26.430 We actually need people to use it in the right way. 42:26.430 --> 42:28.090 But, you know, 42:39.640 --> 42:41.700 I don't think we've gotten there. 42:43.760 --> 42:49.040 Yeah, you basically, you would just disconnect from them at that point. 42:49.040 --> 42:57.920 I mean, you can, as you can start them up. 42:58.900 --> 43:02.480 And also, I mean, there are lots of these trust issues. 43:02.480 --> 43:12.520 Like, for instance, you could want to deal with, people who are less paranoid might want to allow for a friend of a friend connection so as to speed the network up and stuff like that. 43:56.650 --> 44:03.370 So if I can kind of address your core point, because no one else can hear you. 44:04.390 --> 44:12.170 So I think your core question was, we make the assumption that shorter paths are almost always better. 44:12.170 --> 44:19.490 And in this, we've ignored the fact that some people are on modems, some people are on fast ADSL connections, etc, etc. 44:19.490 --> 44:20.270 And that's a good point. 44:20.270 --> 44:21.410 We haven't discussed that. 44:21.410 --> 44:23.810 But we have actually considered that. 44:24.770 --> 44:38.970 The approach that we're considering in order to address that issue is, in effect, you split up the friends that you're connected to into several groups. 44:38.970 --> 44:41.050 Let's say it's two groups for simplicity. 44:41.050 --> 44:43.710 You have your fast friends and your slow friends. 44:43.710 --> 44:50.370 So the top 50% who's faster, the bottom 50% who's slower. 44:58.610 --> 44:59.530 Yeah, yeah. 44:59.530 --> 45:03.570 So you don't slot them into fixed categories. 45:03.570 --> 45:06.730 You can adapt that as time goes on. 45:06.730 --> 45:15.590 And then when you start out routing, you want to try and find it from your fast friends first. 45:15.590 --> 45:20.430 So when you initiate a request, you will send it to your faster friends. 45:20.830 --> 45:25.830 And if that fails to find it, then you resort to your slower friends. 45:25.830 --> 45:29.830 I'm sorry, I don't really have time to give a more in-depth explanation. 45:46.130 --> 45:50.290 Well, well, I mean, that is one of the dangers. 45:50.290 --> 45:54.390 People trying to manipulate the network with fraudulent swap requests. 45:54.450 --> 45:57.390 And there are a variety of ways that you can mitigate. 45:57.470 --> 45:59.910 There are a variety of ways you can mitigate it. 45:59.910 --> 46:13.090 One example would be, well, I don't really have time to go into it, but we have thought about a technique that's a variation on how you can do secure group random number generation. 46:13.090 --> 46:17.570 So basically get someone to cryptographically commit to a certain rate. 46:17.570 --> 46:21.950 Well, I can't really explain it in the time available, but we'll talk later. 46:26.490 --> 46:28.070 We're just done. 46:28.070 --> 46:29.490 One more question. 46:44.950 --> 46:45.630 Right. 46:45.630 --> 46:50.210 Well, I mean, that is in effect up to users' self-interest. 46:50.210 --> 47:04.170 It is in users' self-interest to trust the people that they're connecting to and as such, our hypothesis is that they will tend to form a social network. 47:04.170 --> 47:14.330 It so happens that the criteria for a structured network to work here are actually pretty robust. 47:14.990 --> 47:21.810 It doesn't demand that you have exactly the one over distance distribution that Kleinberg suggested. 47:21.810 --> 47:40.850 It's actually very, and beyond that, addressing the issue while you're saying the John Kerry problem, in many ways, that's kind of a usability issue, steering people towards a certain model of usage of the software, just in terms of how it interacts with users. 47:40.850 --> 47:42.490 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.