[tor-dev] Information on the handling of relays churn

[Adrien Luxey]

Dear Tor developers,

As a PhD student in distributed systems, I am studying onion routing.

We would like to investigate an onion routing system that would run on
users devices, i.e. a lot of nodes with crappy bandwidth and
intermittent connection.
To compare against Tor, I have been looking for information about how
you currently handle the disconnection of relays, but I found no
"digest" on the Web. Your code seems to point to the direction of
core/or/circuit*, that I need to investigate further. I still would love
some first-hand high-level description from you guys.

I have the following questions:

* When an OR disconnects while supporting active circuits, how is the
failure detected?
* How are the paths subsequently rebuilt?
* To which extent would you say that Tor is resilient to churn? What
would be the effects of a massive churn of relays? Where would be
the bottleneck?

If you have any questions on my work, I will be pleased to answer
(though a little ashamed, because I know our system will never hold your
security properties so tight)!

With much respect for your work and philosophy,
Adrien Luxey

[David Fifield]

• To which extent would you say that Tor is resilient to churn? What would be
the effects of a massive churn of relays? Where would be the bottleneck?

About churn specifically, the Sybil research of Winter, Ensafi, Loesing,
and Feamster has past measurements of churn rates, as well as source
code.

https://nymity.ch/sybilhunting/#Data
https://nymity.ch/sybilhunting/churn-values/
https://lists.torproject.org/pipermail/metrics-team/2016-February/000064.html

[Adrien Luxey]

Dear David,

Thanks for the information. I did skim through the first paper a while
back, but there is indeed more valuable info than meets the eye inside
these studies.

Thanks for your advice,
Adrien

Post by David Fifield

• To which extent would you say that Tor is resilient to churn? What would be
the effects of a massive churn of relays? Where would be the bottleneck?

About churn specifically, the Sybil research of Winter, Ensafi, Loesing,
and Feamster has past measurements of churn rates, as well as source
code.
https://nymity.ch/sybilhunting/#Data
https://nymity.ch/sybilhunting/churn-values/
https://lists.torproject.org/pipermail/metrics-team/2016-February/000064.html

[a***@yahoo.ca]

Quoting Adrien Luxey (2018-09-27 18:21:06)

Post by Adrien Luxey
Dear Tor developers,
As a PhD student in distributed systems, I am studying onion routing.
We would like to investigate an onion routing system that would run on users
devices, i.e. a lot of nodes with crappy bandwidth and intermittent connection.
To compare against Tor, I have been looking for information about how you
currently handle the disconnection of relays, but I found no "digest" on the
Web. Your code seems to point to the direction of core/or/circuit*, that I need
to investigate further. I still would love some first-hand high-level
description from you guys.
• When an OR disconnects while supporting active circuits, how is the failure
detected?

If it shuts down properly, then it will send a DESTROY cell in both
directions notifying them that the circuit is now broken. Otherwise, Tor
relies on the operating system TCP timeout to tell it when the
connection has failed. Then, it generates DESTROY cells as needed to
propagate the error.

Post by Adrien Luxey
• How are the paths subsequently rebuilt?

The same way they were built in the first place.

Post by Adrien Luxey
• To which extent would you say that Tor is resilient to churn? What would be
the effects of a massive churn of relays? Where would be the bottleneck?

It depends on what you mean by churn. If you just mean the relays
reboot, then that will cause circuits to fail frequently. If relays
frequently disappear though, that will make it difficult to measure
relay bandwidth (for proportioning network load) as well as maintain
guard persistence. These problems likely do not have any solution.

Post by Adrien Luxey
If you have any questions on my work, I will be pleased to answer (though a
little ashamed, because I know our system will never hold your security
properties so tight)!

Consider reading the Tor protocol specification:
https://gitweb.torproject.org/torspec.git/tree/tor-spec.txt.

It seems that your idea can basically be summarized as "implement
circuit resumption". This is likely not inherently difficult to
implement, except for the problem of knowing when to expire old
sessions. If you just use the TCP rules, then you might as well just run
Tor over multipath TCP or QUIC or something.

[Roger Dingledine]

Post by a***@yahoo.ca
It seems that your idea can basically be summarized as "implement
circuit resumption". This is likely not inherently difficult to
implement, except for the problem of knowing when to expire old
sessions. If you just use the TCP rules, then you might as well just run
Tor over multipath TCP or QUIC or something.

So long as the exit relay doesn't go down (because it has the TCP
connections between the Tor network and external destinations), circuit
resumption should be pretty easy -- you just stick a little header on
the front of cells that gives them counters (to put them into the right
order), and then put some ability to buffer and acknowledge and retry
on the endpoints. You could hack it together yourself (probably a bad
idea) or you could use one of these end-to-end reliability protocols
that people already work on.

And once you've done that, you're quite close to being able to do two
(or multiple) paths in parallel for a given circuit, which can get you
some really intriguing performance, robustness, and security properties:
https://www.freehaven.net/anonbib/#pets13-splitting

And once you've done *that*, you might as well swap out Tor's hacky
end-to-end flow control for something fancier, like as you say QUIC.

For way more in this area, check out
https://blog.torproject.org/tors-open-research-topics-2018-edition

--Roger