Patches (maybe) for proposal 110

Nick Mathewson nickm at
Tue Aug 21 21:43:35 UTC 2007

[I'm moving this conversation onto or-dev with Nathan's permission, so
that other people can get into the design discussion.]

On Wed, Aug 15, 2007 at 04:25:31PM -0600, mrwigglet wrote:
> Here are a set of patches with a possible implementation of proposal 110.
> I'd like to know if this is what the outline was recommending.  I've tested
> this on a tor network with ~10 routers ~3 dirservers and of course the first
> two patches are compatible with the current tor versions, patch 3 is the
> only one that enforces the protocol change.  Let me know if these are close
> to what they should be, if not let me know how to change/improve/fix them.
> Thanks!
> Nathan Evans

Hi, Nathan, and thanks for the work!  I want to see more discussion on
the proposal itself before we move on this, but the basic idea seems

It looks like the first of these patches introduces the RELAY_EXTEND
cell type as a server-accepted synonym for the RELAY cell type.
(RELAY_EXTEND is not my favorite name, since CELL_RELAY_EXTEND will
get confused with RELAY_COMMAND_EXTEND in casual writing; Roger, maybe
we should change 110 to name the new type RELAY_EARLY or
RELAY_EXTEND_OK?  In the rest of this mail, I'll try to call it the
"special" cell type.)

  This patch makes sense other than the naming stuff, which wasn't
  your idea, so it's not your fault.

  I don't think that the behavior matches that described in 'phase
  one' of the proposal: special cells are passed on with the RELAY
  type, not with their own type.

The second patch mucks with some whitespace in circuitbuild.c, then
starts adding features so that clients will send as the special cell
type their first N relay cells on each circuit, where N is chosen
uniformly at random between 5 and 10.

  For this patch, I bet we could get the two uint16_ts that you've
  added to circuit_t down to a single field in origin_circuit_t (how
  many _more_ RELAY_EARLY cells will we originate?) and a single field
  in or_circuit_t (how many _more_ cells will we accept before we
  accept stop accepting RELAY_EARLY cells)?  The fields can be
  uint8_t, since the limit is well under 255 in both cases.

The third patch enforces the protocol by:
    A) Disallowing any RELAY_COMMAND_EXTEND cells without the special
       cell type, and
    B) Closing any circuit where too many cells of the special type
       are sent.

  Rule B is not quite right: the rule is not "You may send no more
  than X special cells;" the rule is "special cells may only occur as
  the first X cells on any circuit."  (See proposal 110, "Design"
  section, last paragraph.)

  Also, I think that despite what 110 says, we could add rule B in
  phase 1.

Other design issues on the proposal: It makes me a little nervous that
we can't actually do phase 2 until _first_ all of the servers that
don't support phase 1 are obsolete, and _then_ we can't do phase 3
until all the servers that support phase 2 are obsolete.  Thus, we'll
need two obsolescence before we could actually deploy this thing, and
old versions seem to get obsoleted only after 9-18 months or so.

Here's a way that we could get the new protocol in faster.  It
requires that something like proposal 105 is implemented, so that part
of negotiating a Tor connection is learning which connection protocol
version the other router supports.  Here goes:

    Phase 1: Add a v2 router protocol, to include RELAY_EARLY cells.

      When (as a client) we negotiate a v2 connection, send our first
      X cells as RELAY_EARLY cells.

      When we (as a server) receive a RELAY_EARLY cell on a v2
      connection, and we are sending it to another server with whom we
      have a v2 connection, then leave it as a RELAY_EARLY cell.  When
      we are sending it to another server with whom we have a v1
      connection, send it as a RELAY cell.

      When we (as a server) get a new circuit on a v1 connection,
      relay the first X cells as RELAY_EARLY cells.

    Phase 2:
      Eventually, stop accepting v1 connections.  Now, the proposal
      110 rules will be enforced.

This variant requires only one obsolescence.  Does it sound like a
good first cut?  Does it leak more or less information about client
operations and paths than the version currently in 110?  Shall I add
it to the proposal?  Is the dependency on proposal 105 acceptable?

Nick Mathewson

----- End forwarded message -----

Nick Mathewson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 652 bytes
Desc: not available
URL: <>

More information about the tor-dev mailing list