1
00:00:03,900 --> 00: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.

2
00:00:27,760 --> 00: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.

3
00:00:40,780 --> 00: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.

4
00:01:01,300 --> 00:01:04,500
The big question is, is it possible?

5
00:01:04,500 --> 00:01:07,500
And if it's possible, will it be useful?

6
00:01:09,300 --> 00: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.

7
00:01:19,160 --> 00:01:26,920
From our point of view, a peer-to-peer network is designed to help people find information.

8
00:01:27,320 --> 00: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.

9
00:01:43,000 --> 00:01:46,000
Users of this system want to find information.

10
00:01:46,000 --> 00:01:53,220
They need to know where the information is so that they can go out and retrieve it.

11
00:01:53,220 --> 00:01:55,740
There are different approaches to this.

12
00:01:55,740 --> 00: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.

13
00:02:04,060 --> 00: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.

14
00:02:16,600 --> 00: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.

15
00:02:31,120 --> 00: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,

16
00:02:51,720 --> 00:02:57,520
you have a large number of decentralized indexes.

17
00:02:57,520 --> 00: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.

18
00:03:05,440 --> 00:03:09,960
Kazaz is probably the archetypal example of that approach.

19
00:03:11,140 --> 00: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.

20
00:03:33,510 --> 00: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.

21
00:03:43,570 --> 00: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.

22
00:03:59,610 --> 00: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.

23
00:04:17,070 --> 00: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.

24
00:04:33,390 --> 00:04:37,030
The disadvantage is it's vulnerable to harvesting.

25
00:04:37,290 --> 00: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.

26
00:04:48,810 --> 00:04:52,370
It wouldn't necessarily be easy, but it would certainly be possible.

27
00:04:53,270 --> 00: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.

28
00:05:09,210 --> 00: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.

29
00:05:25,310 --> 00:05:31,990
The alternative to this are dark, or you can also call them friend-to-friend, peer-to-peer networks.

30
00:05:31,990 --> 00: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.

31
00:05:45,990 --> 00:05:51,770
So the user is saying, I don't mind that these people know that I'm part of this network.

32
00:05:52,350 --> 00:05:55,990
An example of this is a piece of software called Waste.

33
00:05:56,830 --> 00:06:02,530
The advantage of this, as I said, is that only your friends know that you're part of the network.

34
00:06:02,530 --> 00:06:09,150
The disadvantage is that until now this type of network really doesn't scale.

35
00:06:09,150 --> 00:06:10,830
Typically you might have 10...

36
00:06:10,830 --> 00:06:15,650
you have isolated pockets of perhaps 5 to 10 people.

37
00:06:15,950 --> 00: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.

38
00:06:27,270 --> 00: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.

39
00:06:44,990 --> 00: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.

40
00:07:05,290 --> 00: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.

41
00:07:39,390 --> 00: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.

42
00:07:49,650 --> 00:07:55,270
So that's five or six people in a country of 270 million odd people.

43
00:07:55,590 --> 00: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.

44
00:08:06,130 --> 00:08:13,210
These people were not relying on any central phone directory in order to figure out where they should route this information.

45
00:08:13,210 --> 00:08:17,250
They were doing it purely on the basis of their friends.

46
00:08:18,070 --> 00:08:22,150
So what characterizes a small world network?

47
00:08:22,150 --> 00: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.

48
00:08:39,050 --> 00: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.

49
00:08:48,230 --> 00:08:54,410
The challenge is that these short paths aren't necessarily easy to find.

50
00:08:55,350 --> 00: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.

51
00:09:13,410 --> 00: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.

52
00:09:31,670 --> 00: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.

53
00:09:42,730 --> 00:09:51,610
Well the reason this works is that there is people have a concept of similarity between other people.

54
00:09:51,610 --> 00: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.

55
00:10:06,760 --> 00: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.

56
00:10:19,060 --> 00:10:20,960
We call this greedy routing.

57
00:10:21,380 --> 00:10:29,040
Freenet and distributed hash tables rely on this principle to find data in a scalable decentralized way.

58
00:10:33,400 --> 00: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.

59
00:10:45,440 --> 00: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.

60
00:11:00,280 --> 00:11:06,080
And essentially this starts with the realization that the darknet is just a social network.

61
00:11:06,080 --> 00: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.

62
00:11:20,720 --> 00: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.

63
00:11:32,660 --> 00: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.

64
00:11:39,460 --> 00: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.

65
00:11:46,400 --> 00: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.

66
00:11:55,520 --> 00:12:00,420
Milgram's experiment showed people can root in social networks and they can do it well.

67
00:12:00,420 --> 00: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.

68
00:12:08,720 --> 00:12:12,200
So if people can do it then well so should computers.

69
00:12:12,200 --> 00:12:14,440
I mean computers are much smarter than people right?

70
00:12:15,220 --> 00: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.

71
00:12:27,740 --> 00: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.

72
00:12:40,880 --> 00: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.

73
00:12:51,160 --> 00: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.

74
00:13:14,540 --> 00:13:17,780
And in the simplest model position can just be where people live.

75
00:13:17,780 --> 00:13:21,800
And you say that people are more likely to be connected if they live close to one another.

76
00:13:21,840 --> 00: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.

77
00:13:30,580 --> 00:13:35,480
And when this happens that's when you can find an easy way to route in the network.

78
00:13:35,740 --> 00:13:41,180
So for our talk we're actually going to allow people's positions to just be in a ring.

79
00:13:41,180 --> 00:13:46,400
And that doesn't mean that we think that people exist on a ring but this is the very simplest model.

80
00:13:46,400 --> 00: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.

81
00:13:55,680 --> 00:13:57,240
So here I have two examples.

82
00:13:57,360 --> 00: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.

83
00:14:05,960 --> 00:14:09,340
But if you can see the red one covers more of the circle.

84
00:14:09,480 --> 00:14:12,420
It's a longer link therefore it needs to be less common.

85
00:14:12,420 --> 00: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.

86
00:14:25,260 --> 00: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.

87
00:14:36,940 --> 00:14:40,380
We have some... every once in a while we run into a long connection.

88
00:14:40,460 --> 00:14:46,300
Somebody happens to know somebody who lives way on the other side of the world but that's rather rare.

89
00:14:46,300 --> 00: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.

90
00:14:51,460 --> 00: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.

91
00:15:04,460 --> 00: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.

92
00:15:16,220 --> 00:15:18,460
And when something is log that's good.

93
00:15:18,460 --> 00:15:19,700
If it's not log it's bad.

94
00:15:19,700 --> 00:15:22,260
But we have log here so that's going to help us.

95
00:15:22,300 --> 00: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.

96
00:15:33,240 --> 00:15:37,620
So this is an example, a simulated example of how such a network would look.

97
00:15:37,620 --> 00:15:42,320
Now I've imagined again I've just placed people's positions on a circle like this.

98
00:15:42,320 --> 00:15:44,440
All around there are people placed on the circle.

99
00:15:44,440 --> 00:15:47,320
We have two red people who are circled at the end.

100
00:15:47,320 --> 00: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.

101
00:15:59,100 --> 00:16:01,300
And so a route would look something like that.

102
00:16:01,420 --> 00: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.

103
00:16:07,600 --> 00:16:12,060
As we get closer it becomes harder and harder to find steps that take us a long way.

104
00:16:12,060 --> 00:16:17,220
But eventually you do reach the destination and you do so in a bounded number of steps.

105
00:16:18,520 --> 00: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.

106
00:16:33,200 --> 00: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.

107
00:16:44,060 --> 00:16:46,420
We end up having to answer questions like this.

108
00:16:46,420 --> 00:16:48,860
Is Alice closer to Harry than Bob?

109
00:16:49,000 --> 00:16:50,880
I'm trying to route in a social network.

110
00:16:50,880 --> 00:16:55,840
I'm this person in the Milgram experiment with the letter and the letter is going to Harry.

111
00:16:56,880 --> 00:17:00,040
And I have to ask myself should I send it to Alice or Bob?

112
00:17:00,960 --> 00:17:02,480
The letter has to go to Harry.

113
00:17:02,480 --> 00:17:03,480
I have to make a decision.

114
00:17:03,480 --> 00:17:05,920
Should I send it to Alice or should I send it to Bob?

115
00:17:05,920 --> 00: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.

116
00:17:17,500 --> 00:17:19,980
The most basic form would then be where do they live.

117
00:17:20,280 --> 00:17:24,520
If Alice happens to be Harry's neighbor then she is probably closer.

118
00:17:24,520 --> 00:17:29,140
There's a greater chance that they know each other than that Bob would know Harry.

119
00:17:29,140 --> 00:17:32,240
But you could also go on, for example, what their occupations are.

120
00:17:32,240 --> 00: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.

121
00:17:40,880 --> 00:17:43,540
But you could go, you know, jobs, interests.

122
00:17:43,540 --> 00: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.

123
00:17:52,300 --> 00:17:56,800
But now what we want to do is we have this dark net which is this social network.

124
00:17:56,800 --> 00:18:00,220
We want to find a way to route and we want a computer to do it.

125
00:18:00,220 --> 00: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.

126
00:18:07,200 --> 00: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.

127
00:18:19,120 --> 00: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.

128
00:18:28,020 --> 00: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.

129
00:18:36,900 --> 00: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.

130
00:18:47,920 --> 00:18:50,700
It just doesn't go over well with our target audience.

131
00:18:50,700 --> 00:18:56,000
So we have to find a different way to answer these things with Alice, Harry, and Bob.

132
00:18:56,000 --> 00:18:57,500
Who is closer to who?

133
00:18:57,620 --> 00:19:04,080
And so the thing is, and this is what's extremely important, is the information is there in the network.

134
00:19:04,080 --> 00: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.

135
00:19:13,780 --> 00: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.

136
00:19:22,460 --> 00:19:24,220
So how would we do this?

137
00:19:24,220 --> 00: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.

138
00:19:32,080 --> 00:19:37,520
Well, what the world should look like is that there should be few long connections and many short ones.

139
00:19:37,520 --> 00: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.

140
00:19:47,140 --> 00: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.

141
00:19:56,780 --> 00: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.

142
00:20:12,820 --> 00: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.

143
00:20:27,460 --> 00:20:32,940
And that is what allows us to give people new positions that we then can use to root.

144
00:20:32,940 --> 00: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.

145
00:20:41,780 --> 00:20:45,460
And the method to do this is actually surprisingly simple.

146
00:20:45,460 --> 00:20:50,380
There's some deep mathematical magic involved, but it actually turns out to be extremely simple.

147
00:20:50,480 --> 00: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.

148
00:20:57,800 --> 00:21:03,140
Everyone just decides, okay, do a random number generator, give yourself a position.

149
00:21:03,640 --> 00: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.

150
00:21:14,200 --> 00:21:16,660
In fact, they will choose positions at opposite ends.

151
00:21:16,660 --> 00: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.

152
00:21:29,700 --> 00:21:31,980
And this is extremely important, and it has to do with the math.

153
00:21:31,980 --> 00: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.

154
00:21:41,440 --> 00:21:43,720
And this is an example of that sort of switch.

155
00:21:43,720 --> 00:21:48,020
These two people have chosen their positions randomly, and so have their friends.

156
00:21:48,020 --> 00: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.

157
00:21:55,520 --> 00: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.

158
00:22:03,560 --> 00:22:05,200
And this is not what we're looking for.

159
00:22:05,200 --> 00: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.

160
00:22:12,280 --> 00:22:15,660
Well, what if red and green were to swap positions with one another?

161
00:22:15,660 --> 00:22:17,600
Then we get something that looks like this.

162
00:22:17,600 --> 00:22:21,080
And this is much more in line with what we are looking for in our model.

163
00:22:21,080 --> 00: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.

164
00:22:31,880 --> 00:22:35,860
And so this is essentially the algorithm as it goes.

165
00:22:35,860 --> 00:22:40,840
I mean, there's some math involved, and some formulas and stuff that I can give to the interested people.

166
00:22:40,860 --> 00: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.

167
00:22:50,640 --> 00:22:54,720
And some things to note is that this switching step is essential.

168
00:22:54,840 --> 00: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.

169
00:23:02,500 --> 00:23:06,620
Because what happens if you do that, is everyone ends up choosing the same position in the end.

170
00:23:06,620 --> 00: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.

171
00:23:12,860 --> 00: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.

172
00:23:17,920 --> 00:23:22,060
So you need this random choice, and then the switching back and forth.

173
00:23:23,820 --> 00: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.

174
00:23:30,440 --> 00: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.

175
00:23:36,160 --> 00:23:37,860
But there are ways of going around this.

176
00:23:37,860 --> 00: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.

177
00:23:46,220 --> 00: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.

178
00:23:55,840 --> 00: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.

179
00:24:04,100 --> 00:24:06,420
The first control is the random route.

180
00:24:06,440 --> 00: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.

181
00:24:13,540 --> 00:24:17,620
With no positions, no knowledge about anything, we can't do any form of greedy routing.

182
00:24:17,620 --> 00:24:21,900
All we can do is stumble around randomly and hope that we find our destination.

183
00:24:22,000 --> 00:24:27,300
So this is sort of the control of where you start out, the random network, the random search.

184
00:24:27,300 --> 00:24:28,620
That's all you can do.

185
00:24:29,660 --> 00: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.

186
00:24:44,720 --> 00:24:48,700
This is where everything is good, but that's not the situation that we actually have.

187
00:24:48,700 --> 00: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.

188
00:24:59,480 --> 00:25:03,060
And that's what I have as the third data set will be the restored data.

189
00:25:03,060 --> 00:25:04,860
That will be our algorithm applied.

190
00:25:05,620 --> 00: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.

191
00:25:11,940 --> 00: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.

192
00:25:21,220 --> 00:25:25,180
And you can see that the random one falls off very fast.

193
00:25:25,180 --> 00:25:28,360
Random routing simply cannot perform in this number of steps.

194
00:25:28,360 --> 00:25:34,360
It fails to find data as the network grows, whereas the good line will stay at the top.

195
00:25:34,360 --> 00:25:35,260
It always succeeds.

196
00:25:35,260 --> 00:25:40,160
The math tells us that it must, so it would only be a bug in my simulator if it wasn't.

197
00:25:40,520 --> 00: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.

198
00:25:51,960 --> 00:25:55,840
And only at the very largest size do we see some significant deviation.

199
00:25:55,880 --> 00:26:01,080
But even at that level, we're talking about 96% success rate for the restored network.

200
00:26:02,400 --> 00:26:06,860
And the other thing one's interested in, of course, is the number of steps that it takes on average.

201
00:26:06,860 --> 00: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.

202
00:26:15,340 --> 00: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.

203
00:26:26,960 --> 00: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.

204
00:26:34,160 --> 00:26:38,600
I'm basically doing, making, giving myself an idealized situation.

205
00:26:38,800 --> 00:26:42,980
So a more interesting question is, how do we do this if we have real-world stuff?

206
00:26:43,020 --> 00: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.

207
00:26:58,380 --> 00: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.

208
00:27:05,020 --> 00: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.

209
00:27:13,260 --> 00: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.

210
00:27:27,960 --> 00: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,

211
00:27:44,680 --> 00:27:46,660
very few non-Americans in the set.

212
00:27:48,000 --> 00: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.

213
00:27:54,160 --> 00:27:56,460
Not just Ian, but somebody who was in it.

214
00:27:56,460 --> 00:27:59,120
And just as a note, we got no Brazilians.

215
00:27:59,120 --> 00: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.

216
00:28:08,380 --> 00: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.

217
00:28:16,920 --> 00:28:19,460
So our set contains programmers, Americans.

218
00:28:19,460 --> 00:28:22,960
There weren't a lot of these Brazilians who do whatever they do on Orkut.

219
00:28:23,620 --> 00:28:29,960
And just as a note, because when people talk about small worlds, they often talk about degree distributions and power laws.

220
00:28:29,960 --> 00:28:35,900
And we did have a power law degree distribution here, in the sense that there were a couple of people.

221
00:28:35,960 --> 00:28:39,800
When you talk about a degree in a network, you mean the number of people that somebody knows.

222
00:28:39,940 --> 00: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.

223
00:28:48,340 --> 00:28:51,100
He had 289 friends in the set.

224
00:28:51,100 --> 00:28:53,660
So out of 2000, he knew a hell of a lot of those people.

225
00:28:53,660 --> 00:29:00,080
And whereas most people had only around like 18-20 neighbors there, as you can see.

226
00:29:00,200 --> 00:29:05,660
So this is the sort of power law degree distribution that can affect the network.

227
00:29:06,300 --> 00: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.

228
00:29:12,540 --> 00:29:15,060
Something that can beat just a random search.

229
00:29:15,240 --> 00:29:17,980
And a random search performs rather well on this data.

230
00:29:17,980 --> 00:29:23,220
And the reason that a random search performs well is that it will... is because of this degree distribution.

231
00:29:23,220 --> 00: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.

232
00:29:29,340 --> 00:29:32,080
So with power laws, it tends to perform rather well.

233
00:29:32,080 --> 00: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?

234
00:29:41,260 --> 00:29:45,040
So in about 120 steps, the success rate was 72.

235
00:29:45,040 --> 00:29:47,980
And of the successful ones, it was about 43.

236
00:29:47,980 --> 00:29:51,820
So for randomly searching a network of 2000, this is rather good.

237
00:29:51,900 --> 00:29:55,160
So the question of course is, if we run the switching, try to apply this.

238
00:29:55,160 --> 00:29:57,000
This is a real social network.

239
00:29:57,060 --> 00:30:01,960
Can we just get somewhere with this greedy routing by assigning identities?

240
00:30:01,960 --> 00:30:03,200
And the answer is yes.

241
00:30:03,240 --> 00: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.

242
00:30:12,000 --> 00: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.

243
00:30:27,600 --> 00: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.

244
00:30:34,700 --> 00: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?

245
00:30:44,700 --> 00: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.

246
00:30:52,220 --> 00: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.

247
00:30:59,520 --> 00:31:06,560
So we can say that our algorithm can take advantage of this degree distribution, but it was not use it.

248
00:31:06,560 --> 00:31:08,980
And it seems like it actually does work.

249
00:31:08,980 --> 00: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.

250
00:31:21,900 --> 00:31:23,220
Are we going to go with the demo?

251
00:31:24,620 --> 00:31:36,200
So to demonstrate this, we were going to show routing in this, between some people in this data set from Orkut.

252
00:31:36,800 --> 00:31:39,320
So one thing to start with,

253
00:31:42,740 --> 00: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.

254
00:31:51,360 --> 00:31:55,460
Ian wants to know how many steps does Sergey bring, because I want to borrow some money or something.

255
00:31:56,740 --> 00: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.

256
00:32:05,340 --> 00: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.

257
00:32:11,640 --> 00: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.

258
00:32:24,920 --> 00:32:26,640
So the search is completed.

259
00:32:28,080 --> 00: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.

260
00:32:39,380 --> 00:32:44,300
And we could go from him, to now somebody else who's in the set, like Lawrence Lessig.

261
00:32:51,380 --> 00: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.

262
00:33:10,440 --> 00: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.

263
00:33:25,560 --> 00: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.

264
00:33:40,560 --> 00: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.

265
00:33:54,360 --> 00: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.

266
00:34:09,120 --> 00: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.

267
00:34:33,280 --> 00: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.

268
00:34:47,220 --> 00:34:51,540
Yeah, because he doesn't actually know the people that are connected to him.

269
00:34:51,540 --> 00:34:54,380
Indeed, they don't know him either.

270
00:34:57,680 --> 00: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.

271
00:35:17,760 --> 00:35:23,940
So just real quick, I should talk about some of the practical concerns.

272
00:35:23,940 --> 00:35:26,640
We're actually implementing this right now.

273
00:35:27,260 --> 00: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.

274
00:35:33,960 --> 00:35:36,240
Hang on, this has gone mad.

275
00:35:39,810 --> 00:35:40,650
Okay.

276
00:35:42,070 --> 00:35:43,890
So theory works.

277
00:35:43,890 --> 00:35:46,450
What are the concerns in practice?

278
00:35:46,450 --> 00:35:49,610
Well, preventing malicious behavior, obviously.

279
00:35:49,810 --> 00: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.

280
00:36:06,990 --> 00:36:09,970
It's essential that it's easy to use.

281
00:36:09,970 --> 00:36:14,390
This is a problem that Freenet has certainly experienced.

282
00:36:14,390 --> 00: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,

283
00:36:34,670 --> 00: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.

284
00:36:42,210 --> 00:36:48,530
With this next iteration of Freenet, we really want to tackle that head on.

285
00:36:48,530 --> 00:36:53,630
So we need to think about how do we actually make this thing usable?

286
00:36:54,990 --> 00:37:00,030
Additionally, how is data going to be stored in this architecture?

287
00:37:00,030 --> 00:37:07,490
And perhaps maybe it can do other things other than just storing and retrieving data as Freenet currently does.

288
00:37:08,790 --> 00:37:11,470
So, preventing malicious behavior.

289
00:37:11,470 --> 00:37:13,270
What are the threats?

290
00:37:13,270 --> 00:37:23,250
Well, somebody could potentially select an identity to attract certain types of data or otherwise act maliciously.

291
00:37:23,250 --> 00:37:30,750
They could potentially, through a similar means, manipulate the identities of other nodes for some nefarious purpose.

292
00:37:31,370 --> 00:37:33,230
How do we ensure ease of use?

293
00:37:33,230 --> 00:37:39,110
Well, one requirement is that peers will need to be, or at least most peers will need to be always on.

294
00:37:39,110 --> 00:37:48,130
That's not so much of an issue now that broadband is better deployed and is being deployed so quickly.

295
00:37:48,130 --> 00:37:50,550
How do we introduce peers?

296
00:37:51,270 --> 00:37:53,450
Can we do it by email?

297
00:37:53,450 --> 00: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.

298
00:38:02,450 --> 00:38:07,130
Maybe you can do it by phone, verbally phoning up your friend and saying, hey, let's do this.

299
00:38:07,130 --> 00:38:11,770
Here's the kind of code number to allow us to connect to each other securely.

300
00:38:11,770 --> 00: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.

301
00:38:21,770 --> 00:38:23,690
What about NATs and firewalls?

302
00:38:23,690 --> 00: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.

303
00:38:38,170 --> 00:38:45,150
Fortunately, people have developed techniques to get around that, but that adds challenges in terms of peer introduction.

304
00:38:45,150 --> 00:38:50,230
So we can use UDP hole punching as kind of an increasingly standardized way to achieve that.

305
00:38:50,230 --> 00:38:54,570
It's used by Digger, another one of my projects, and Skype.

306
00:38:55,150 --> 00:38:59,210
But that would require a third party for negotiation.

307
00:39:00,830 --> 00:39:05,350
So in conclusion, real quick, so we have time for a few questions.

308
00:39:05,770 --> 00:39:10,890
We believe that this is not only possible, we're going to do it and we are doing it.

309
00:39:10,890 --> 00:39:14,290
There's still a lot of work to do on the theory.

310
00:39:14,350 --> 00:39:17,070
In other words, can other models work better?

311
00:39:17,070 --> 00:39:27,350
In particular, right now, when nodes choose each other to decide whether swapping would be advantageous, they do so at random.

312
00:39:27,350 --> 00: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.

313
00:39:41,790 --> 00:39:47,110
So we need to explore perhaps a more directed search for peers to swap with.

314
00:39:48,750 --> 00:39:53,790
And it needs, like everything, it needs to be tested on more data.

315
00:39:54,410 --> 00:40:00,770
We've learned the hard way that practice is more difficult than theory, particularly with Freenet.

316
00:40:00,990 --> 00:40:03,990
Security issues clearly are critical.

317
00:40:03,990 --> 00:40:06,390
That's one of our our major focuses.

318
00:40:06,610 --> 00: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.

319
00:40:12,430 --> 00:40:17,570
If it's not easy to use, we'll get 10 users and it won't be useful to anyone.

320
00:40:18,440 --> 00: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.

321
00:40:32,210 --> 00:40:39,030
So if this interests you, our website is freenetproject.org.

322
00:40:39,970 --> 00:40:43,470
And Oscar insists that I show you this slide.

323
00:40:44,050 --> 00:40:51,270
So I guess we have about five minutes for some questions.

324
00:40:51,770 --> 00:40:52,450
So

325
00:41:03,130 --> 00:41:14,370
the question was, what is the incentive for people to acquire a lot of neighbors?

326
00:41:14,370 --> 00:41:16,390
Well, the incentive is actually quite simple.

327
00:41:16,390 --> 00: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.

328
00:41:25,770 --> 00: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.

329
00:41:32,510 --> 00:41:36,830
They've got perhaps 10 or 20 kilobytes per second upstream.

330
00:41:36,830 --> 00: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.

331
00:41:44,430 --> 00:41:45,450
So do you want to comment?

332
00:41:45,450 --> 00: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.

333
00:41:52,350 --> 00: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.

334
00:41:57,910 --> 00: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.

335
00:42:08,870 --> 00:42:11,430
So it's something that one needs to be very careful with.

336
00:42:11,550 --> 00: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.

337
00:42:20,490 --> 00:42:22,350
It's not like deploying normal software.

338
00:42:22,350 --> 00:42:24,350
We just write software that works.

339
00:42:24,350 --> 00:42:26,430
We actually need people to use it in the right way.

340
00:42:26,430 --> 00:42:28,090
But, you know,

341
00:42:39,640 --> 00:42:41,700
I don't think we've gotten there.

342
00:42:43,760 --> 00:42:49,040
Yeah, you basically, you would just disconnect from them at that point.

343
00:42:49,040 --> 00:42:57,920
I mean, you can, as you can start them up.

344
00:42:58,900 --> 00:43:02,480
And also, I mean, there are lots of these trust issues.

345
00:43:02,480 --> 00: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.

346
00:43:56,650 --> 00:44:03,370
So if I can kind of address your core point, because no one else can hear you.

347
00:44:04,390 --> 00:44:12,170
So I think your core question was, we make the assumption that shorter paths are almost always better.

348
00:44:12,170 --> 00: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.

349
00:44:19,490 --> 00:44:20,270
And that's a good point.

350
00:44:20,270 --> 00:44:21,410
We haven't discussed that.

351
00:44:21,410 --> 00:44:23,810
But we have actually considered that.

352
00:44:24,770 --> 00: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.

353
00:44:38,970 --> 00:44:41,050
Let's say it's two groups for simplicity.

354
00:44:41,050 --> 00:44:43,710
You have your fast friends and your slow friends.

355
00:44:43,710 --> 00:44:50,370
So the top 50% who's faster, the bottom 50% who's slower.

356
00:44:58,610 --> 00:44:59,530
Yeah, yeah.

357
00:44:59,530 --> 00:45:03,570
So you don't slot them into fixed categories.

358
00:45:03,570 --> 00:45:06,730
You can adapt that as time goes on.

359
00:45:06,730 --> 00:45:15,590
And then when you start out routing, you want to try and find it from your fast friends first.

360
00:45:15,590 --> 00:45:20,430
So when you initiate a request, you will send it to your faster friends.

361
00:45:20,830 --> 00:45:25,830
And if that fails to find it, then you resort to your slower friends.

362
00:45:25,830 --> 00:45:29,830
I'm sorry, I don't really have time to give a more in-depth explanation.

363
00:45:46,130 --> 00:45:50,290
Well, well, I mean, that is one of the dangers.

364
00:45:50,290 --> 00:45:54,390
People trying to manipulate the network with fraudulent swap requests.

365
00:45:54,450 --> 00:45:57,390
And there are a variety of ways that you can mitigate.

366
00:45:57,470 --> 00:45:59,910
There are a variety of ways you can mitigate it.

367
00:45:59,910 --> 00: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.

368
00:46:13,090 --> 00:46:17,570
So basically get someone to cryptographically commit to a certain rate.

369
00:46:17,570 --> 00:46:21,950
Well, I can't really explain it in the time available, but we'll talk later.

370
00:46:26,490 --> 00:46:28,070
We're just done.

371
00:46:28,070 --> 00:46:29,490
One more question.

372
00:46:44,950 --> 00:46:45,630
Right.

373
00:46:45,630 --> 00:46:50,210
Well, I mean, that is in effect up to users' self-interest.

374
00:46:50,210 --> 00: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.

375
00:47:04,170 --> 00:47:14,330
It so happens that the criteria for a structured network to work here are actually pretty robust.

376
00:47:14,990 --> 00:47:21,810
It doesn't demand that you have exactly the one over distance distribution that Kleinberg suggested.

377
00:47:21,810 --> 00: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.

378
00:47:40,850 --> 00:47:42,490
I'm afraid we're going to have to end it there.

379
00:47:42,490 --> 00:47:43,210
Thank you.

380
00:47:51,400 --> 00:47:52,600
We'll talk about that.