Walking Onions: Scaling the Tor network

The Problem

Demand for privacy online is increasing. People and organizations are looking for trustworthy, proven ways to retain their privacy. Applications are looking for ways to provide privacy to their users. The Tor network is part of the solution.

As more users turn to Tor, the network needs to scale to match the demand.

There is a challenge to scaling the network while maintaining its security. In the current Tor network design, every single Tor client needs to download the entire list of available relays and associated information about each relay while the client is active, and download more information over time to keep this document up to date. Clients use the network directory to randomly choose their Tor network paths from all available relays in the network.

Downloading the complete network directory is a significant overhead, which only continues to grow as the Tor network userbase grows. The impact of this problem on a user can range from a minor irritation and bootstrap sluggishness to the failure of censorship bypassing methods. Directory overhead also presents an obstacle for applications that want to integrate Tor for light-weight communications. This has a negative impact on mobile integration of Tor.

The Solution

In this project, we will implement the first phase of the Walking Onions proposal, a set of protocols improving scalability for the Tor network by enabling constant-size scaling of the information each user must download. Walking Onions will allow us to remove nearly all directory overhead from the Tor protocol, enabling Tor to scale to many more clients and relays with no reduction in security.

In Tor’s current design, clients have to download network directories because every client needs to pick for itself which relays to use. If a client were to allow somebody else to choose relays for it, that party could choose only hostile relays, or ones under that party’s control. Clients need to download complete, authenticated directories so that each client is building its circuits from the complete set of available relays: if two clients know a different set of relays, an adversary could use that fact to distinguish the clients behavior. Walking Onions solves these problems differently.

Under Walking Onions, relays still download and store canonical directories. These directories still are authenticated by a trusted set of “directory authorities.” The key difference from Tor’s current design is that with Walking Onions, clients do not download directories. Tor proposal 300 contains a full description of the Walking Onions protocol.

Impact

By implementing Walking Onions, the Tor network will be able to scale in a meaningful way, while maintaining its security properties and user-facing performance. We will also reduce the overhead associated with downloading the network directory, which has benefits for mobile integration and user-perceptible performance.

As a result:

• Client bandwidth overhead is reduced from 2.5 MB at startup and 48 KB every hour to approximately 5 KB to start and 2-3 KB every hour.
• The Tor network can scale to meet the needs of a growing user base.
• The Tor network becomes a viable option for third party applications (including mobile and light-weight apps) and organizations to offer privacy and anonymity to their users.
• New Tor relays will increase the network’s capacity without degrading individual client performance.
• Current and future Tor users benefit from performance improvements, particularly during initial startup.

The proposed amount ($50,000) will allow the Tor Project to complete the first phase of implementing Walking Onions, outlined below, and will act as seed funding for the Proof of Concept and Full Implementation phases of this work.

Walking Onions: Specification, 2 months

This Objective is a complete, byte-level specification of the Walking Onions design, in sufficient detail to permit independent implementations of Walking Onions to interoperate. This will include a description of all new directory formats, all new wire protocols, all new client and relay behaviors, and all backward compatibility mechanisms.

Activities:

• Write an initial draft of specification, identifying unknowns and options in the design.
• Distribute draft to tor-dev mailing list and to researchers for comment.
• Take decisions on all unknowns and options; if uncertainty remains.
• Write or locate reference-implementations for any primitive operations not already used by Tor.
• Write reference implementations for all novel encodings/decodings.

Team

• Nick Mathewson, Network Team Engineer
• Alexander Færøy, Network Team Lead (Project Lead)
• Gabriela Rodriguez, Project Manager
• Mike Perry, Research Director