(FWD) Re: architectural proposal & technical problems

[Mike Perry]

Thus spake Johannes Renner <renner at i4.informatik.rwth-aachen.de>:

> > I doubt that bandwidths between routers
> > will change very much from minute to minute, and even if they do,
> > currently directory descriptors don't refresh fast enough for it to
> > matter.
> 
> I think that the available bandwidths between routers may actually
> change from minute to minute since it depends on how many streams
> a link carries and what amounts of data. I'll investigate further,
> but you are right, router descriptors don't refresh fast enough and
> we actually didn't plan to use them (see below).

You are most likely right that they do change, but consider what this
amount of accuracy can say about a large file transfer being done via
those nodes, for example.

Also, lying is a big problem with this. I just make sure all of my
colluding nodes claim fast connections to eachother, and slow to all
other nodes (or random arbitrary changing subsets that are hard to pin
down). For this reason I think it pretty much has to be central
authority (with alternate directory that the client addon can use), or
client-side.

> > So I'm a bit confused. Will the routers be publishing bandwidth
> > information to the directory via opt flags, or will they be publishing
> > it to modified clients via the addon?
> 
> No, they should not publish any bw-information to the directory, but
> just an optional flag, so that clients can see that this router is
> running such an addon and thus can request information directly from
> it by connecting to an advertised port, e.g. "opt BandwidthInformer 9053".

Hrmm, this has all sorts of issues with clients connecting to nodes
that you are about to use.. But I suppose those connections could be
done over Tor.. It still makes me uneasy, especially since an
alternate directory would solve this better.

> (btw: does anybody know technically how to set "opt"-flags in a comfortable way?)

It doesn't appear that you currently can. I think when you upload a
descriptor via the control port it is for client use only, but I could
be wrong.

> > How do you intend to do the balancing for bandwidth and latency if
> > every client were to be using your scheme?
> 
> Latencies would be measured locally from within the clients using a
> probabilistic selection of nodes, just like selecting nodes for
> regular circuits (maybe restricted to the fast percentile of the
> routers). This information will not be made available for the others,
> so every client will end up with his/her own pool of currently
> considered to be fast nodes/links. That will do the load-balancing,
> because if all of the clients were using the same nodes, we would
> measure bad performance and simply (probabilistic) choose other nodes.

This is good. I think the local, private aspect of this is a pretty
good plus on the column of the 2C design over the OR addon design.
Though we need to think a bit about the fingerprinting issues, a way
to bias the the method towards exploration vs using the existing
weights (exploratory circuits, a-la I2P, or do we only measure during
usage?), and the anonymity and performance consequences of such a
bias. As the network grows, you will need to be more and more
exploratory to keep up with the N^2 link count.

A central authority could publish measured latencies in an alternate
directory also... Though nodes can prioritize or delay any
RELAY_BEGIN(localhost) cells in their queues.

> And it will be the same with bandwidth: everyone who is interested
> in, queries different (probabilistic chosen) routers in different
> moments. Because the best links a router maintains in t+1 can be
> different from those in t, every client in the end explores its
> own random corner of the network.

One thing to consider for bandwidth is just to test if the node is
overloaded. This is easy to do globally (I have code in TorFlow to do
this now), can be placed in the directory, and doesn't leak a terrible
amount of information about the node. It also scales O(N) as opposed
to O(N^2), which also means a trusted central authority can do it
(though nodes can give them better service, so perhaps we're stuck
with client side no matter what).

> > So, is this whole design a prototype, or is it meant to last?
> 
> In the begining it will be a prototype, because we surely not know
> what is the best practice. It would be good to work on a prototype,
> that is designed in a way, that it could become a real-world used
> implementation later on.

I think the node-addon is also weaker in this regard in that it's a
pretty ugly hack. An alternate directory can be merged into the real
directory at some point, but an addon port each tor node has to run to
provide extra info is pretty mutant to the whole design.

> > why not just get a fast
> > link and measure bandwidths AND latencies of two-hop paths
> > client-side, and store them yourself to run tests? Speedracer can
> > measure 2 hop bandwidths pretty well, and while it is a hack, you can
> > do latency measurements via socks and localhost as you mentioned.
> 
> The idea is to put as little additional load on the network as possible;
> therefore we do not plan to transfer extra files in order to measure the
> bandwidth (why not take that info from ORs since it is already available
> there?). Otherwise we think that latency measurements will not put too much
> load on the network - these are single ping cells.

Well, in the real world nodes will lie about their capacity. Either
the client or a trusted authority has to measure both. The trusted
authority can be given selective service, if nodes can tell they are
being tested though.

> But we do not understand exactly what you mean with two-hop paths in here.
> Why exactly 2? Do you mean to use the EXTEND command to build a two-hop
> circuit and use this for measuring? This should be also possible for
> one-hop circuits, right?

You can't make 1 hop circuits connect anywhere. You can test your
latency to a given node that way, but not your bandwidth to it.

The 2-hop path is to measure the bandwidth between 2 nodes. It also
works to measure the bandwidth (or more accurately, load) of a given
node, if the other node is (allegedly) as fast or faster. speedracer
does this by dividing the network into percentile tiers, averaging
stream bandwidth observed over memebers of a path, and then dividing
the nodes total bandwidth by the average observed stream, giving a
load ("average concurrent user") metric via metatroller's statistics.

> Well, what we actually would like to have is the possibility to construct
> only one three-hop circuit and measure partial circuits regularly (lets say
> you have circ through 0-1-2-3 [where 0 is us], we are interested in doing
> measurings for 0-1, 0-1-2 and 0-1-2-3).
> I also like the PathlenCoinWeight proposal. This could also be useful for
> measuring latencies, but the best would be just to be able to exit an existing
> 3-hop-circuit at any chosen hop in between. So we could measure RTTs of partial
> circuits and easily compute values for single used links.
> Any of the devels can help us further?

I can't really help with this due to my limited time-budget. I say do
the SOCKS cheap hack way for now, measuring latency as circuits are
extended a hop at a time before use.

> > 1. Do we trust individual nodes to publish their peer latencies and
> >    bandwidths?
> 
> I think, that we of course cannot trust them individual nodes.
> At first we want to check whether the published information reflects the
> reality and if it can be useful for clients at all. And then I think this
> would be the point where we would need something like reputation?

This gets dicey. It is a lot harder for a central reputation system to
verify the N^2 links rather than just N nodes... You could try to do
some sort of frequency analysis to pair down the nodes you have to
verify to only those that claim to be fast to other peers a
"suspicious" percentage of the time, but that is even more dicey.

> > 2. If we do not trust individual nodes, how do we deal with the fact
> >    that it will soon be very hard to collect these n^2 measurments from
> >    the perspective of a central authority?
> >    A. Can we divide them into tiers?
> >    B. Or perhaps just truncate at some %age of the network where we just assign a constant value to the
> >       bandwidth of all peers (perhaps node_capacity/num_peers). But what
> >       about latency?
> >    C. Or do we do all these measurements on the fly and keep long-term client
> >       state around, so Tor gets faster the more you use it. This could
> >       work really well for both bandwidth and latency in the 2-hop
> >       "Censorship Resistance Only" mode I proposed in Proposal 112.
> >       But this is particularly dangerous to anonymity, since clients
> >       are likely to learn highly unique views of the network, and is
> >       potentially vulnerable to gaming/selective service attacks.
> 
> We first want to test and try out and check what information exactly
> helps best to improve the performance.
> Then, if we know what will be useful we can think more about hiding
> stuff for saving as much anonymity as possible.
> These are all very interesting, challenging and important questions,
> that have to addressed, but for the moment I think 2C sounds good:
> The long-term client that makes Tor faster the more you use it.

Yeah, though please put some thought into alternate authorities as
well, and consider that N^2 factor. There are currently 1 million
(directional) links in tor.  How many probes does it take to get a
reliable avg mesurement of a link? And how do you make use of limited
information to improve speed yet not get stuck using the same nodes
all the time?

> So for our purposes we would be pleased with a Tor/Tor control protocol
> that is extended to the following capabilities:
> 
> - Two new configuration options that can be set via SETCONF:
> 
>   1. "opt"-entry for descriptor, example: SETCONF OptDescEntry="BandwidthInformer 9053"
>   2. option to tell Tor, that it should not construct any circuits by itself, similar
>      to __LeaveStreamsUnattached, example: SETCONF __IdleCircuits=0
> 
> - One new command that connects over a given circuit to destIP, destPort specifying
>   0, 1 or 2 to tell Tor which node of the circuit we want to address for exiting, e.g.:
> 
>   "CONNECT" SP circID SP ("0"|"1"|"2") SP destIP SP destPort

I think this last one is likely to be a little tricky. At least not as
simple as just adding the commands to the control port, I think the
Tor client code needs a bit of modding to be able to do this, but I'm
not sure.

> This would enable us to implement my favorite method of latency-testing,
> but surely needs modifications in Tor and the control protocol. So how
> do you do such modifications? Do we have to implement a patch for Tor as
> kind of a proposal? What other extensions do you want the control
> protocol to implement for your projects? Maybe we can develop it in a way
> everybody will like it?

Yeah, personally I can't really commit for doing this stuff, so you
are probably left with patching in what you need yourself.. Probably
patch the control-spec first (and post it here), then the source to
match. I don't think this stuff requires a whole proposal of its own.


-- 
Mike Perry
Mad Computer Scientist
fscked.org evil labs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20070426/f2bf78ec/attachment.pgp>