architectural proposal & technical problems

[Mike Perry]

Sorry for the delayed reply. It got lost in the noise of both
tor-assistants and the spam of my own mailbox.

Moving this discussion to or-dev. In general, I think most dev
discussion of anything tor-related should happen here rather than
tor-assistants, if nothing else for the spam problem. But it is
probably just as good to have more eyeballs on stuff.

Thus spake Johannes Renner (renner at i4.informatik.rwth-aachen.de):

> The first part is an addon for ORs, that is using the Tor
> control protocol to listen for events (mainly ORCONN and/or
> STREAM_BW), records bandwidth-data about single TLS-connections
> the router maintains to other ORs, and simply provides this
> data for requesting clients. The recordings can be done in a
> configurable way and would provide e.g. max observed throughput
> of some period as well as current average of last n minutes
> (just a current value would be much better, but also much worse
> for anonymity). We believe that the difference between max and
> current avg correlates with the still available bandwidth of a link.

I actually think you are best served with max bandwidth seen over any
M minute period over the past H hours, which is both good for
anonymity and good for you. 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. Besides, just because a link isn't being used doesn't mean the
capacity isn't there. In fact, it likely means the capacity IS there
for the taking. Unfortunately we can't update fast enough to represent
that either. Or, fortunately, for anonymity's sake : )

> The second part is a QoS-addon for OPs, that will contain the
> algorithms for route selection. It can post requests to receive
> the list of bw-information from an OR-addon. In addition to this
> it does active measurings of latencies/RTTs through Tor and records
> that data. Using these two orthogonal informations we can then
> build fast circuits from here and attach the streams to them
> using the control protocol.

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?

How do you intend to do the balancing for bandwidth and latency if
every client were to be using your scheme?

> 1. In OnionCoffee I can do measurings of RTTs in the following way:
>    [Send RELAY_CONNECT cell to localhost, get failed RELAY_END
>    back].

So, is this whole design a prototype, or is it meant to last? If it is
just a prototype (there's nothing wrong with this, since there are a
lot of unknowns that still need answering), 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 other thing to consider is that this information is likely to get
pretty large if every node participates. You should spend at least
some time considering doing some form of eigenvector compression (SVD:
http://en.wikipedia.org/wiki/Singular_value_decomposition, PCA:
http://en.wikipedia.org/wiki/Principal_components_analysis), and how
much this compresses the data and at what cost to accuracy and ability
to detect liars.

I think the final design choice hinges on a few factors and unsolved
problems, basically:

1. Do we trust individual nodes to publish their peer latencies and
   bandwidths?
   A. What workarounds, spot-checks, peer-verifications, or other
      means exist to reduce the ability of nodes to lie about their
      capacity to peers?
   B. How do we coordinate their vector publishing in a compact, 
      compresible way? Does this affect ability to detect lying?

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. 

Note that 2C is particularly attractive for easy migration from
prototype to real implementation, and also scales well with the
network size. Unfortunately it probably destroys anonymity (or maybe
some anonymity can still be salvaged if we are clever?). It may even be
possible to learn this information with two hop circuits and apply it
to three hop circuits, making use of the proposed PathlenCoinWeight
option, if we are really clever about preserving enough anonymity so
that it makese sense to do this.



-- 
Mike Perry
Mad Computer Scientist
fscked.org evil labs