This is our primary concern. Our goal for this paper is to maintain at least the status quo of anonymity in the Tor network. Currently, every Tor client uses a trusted group of ~7 "directory servers" to assign them to a circuit. Our implementation relies analogously on trusted "assignment servers" to assign clients to circuits. That's the purpose of the TorPath assignment protocol. In fact, it provides better anonymity than the status-quo, because each node on the circuit only knows the IP address of its neighbors, rather than the current situation, where the client knows the IP of every relay on the circuit. So yes, this assignment protocol relies on trusted servers. But so does Tor in its current state.
Your point about botnets is a very good one, and one we haven't considered fully. We will certainly address this further in future versions of the paper.
However, we do consider sybil attacks. Addressing them is the primary purpose of the TorPath assignment protocol. It ensures that, even if an adversary controls over 50% of the relays, there is a very low chance that (1/16 if I remember correctly) a new circuit will consist of three evil relays. Since we limit the number of coins that can be mined on a given circuit, we call this security a "good enough" margin of error for bad coins. Since it's predictable it can be baked into economic models.
But you're right, these are important considerations that we are taking very seriously.
> Currently, every Tor client uses a trusted group of ~7 "directory servers" to assign them to a circuit
The directory servers don't assign clients to a circuit, they publish a directory of eligible nodes from which all clients can use to select a circuit. The distinction is smaller than it might seem since control of the list ultimately means control of the nodes in the circuit and while, in theory detecting directories giving different nodes different views should be easy I don't think any infrastructure exists for that. I'm just being pedantic on this point because some people might be confused here.
> However, we do consider sybil attacks. Addressing them is the primary purpose of the TorPath assignment protocol. It ensures that, even if an adversary controls over 50% of the relays
Definitional disagreement, I guess. I don't consider this to be sybil resistance. It's very easy to describe things which are secure when a majority is honest, to call something sybil resistant I would want to have an argument as to how its costly (or impossible) for the attacker to achieve the required threshold.
Yes, the odds are low at 50%, but they're certantly not at 99%. You have an amplification, but I didn't see any argument why 99% is substantially harder than 50% (or 1%). Maybe it is if you invoke back in centralized trusted authorities (well, ignoring botnets), and indeed— this could be an advance over tor— but I think some careful though should be given to audibility of the authorities, since I think you lose that if you hope to hide the participation in the network from the public.
I read the TorCoin/TorPath paper yesterday, and looked at some of the references including CoinShuffle[1] (a bitcoin mixing protocol) and Dissent[2] (implementation of a DC-net or Dining Cryptographer's net, 2nd great invention by David Chaum after RSA blinding/anonymous e-cash). I'll summarize what I learned here, hopefully someone will find it useful.
One of the key pieces seems to be the Neff shuffle (verifiable random shuffling of an ordered list of public keys). The Neff shuffle builds on ElGamal pairs (which themselves are the core algorithm in the verifiable voting system helios[3]). Dissent looks to be the application of a Neff shuffling technique to ferret out the malicious nodes in a DC-net (a provably anonymous communication network). CoinShuffle is basically the use of a DC-net to anonymously pool together a set of bitcoin public keys, and the coinShuffle prototype is a fork of the Dissent codebase. The TorCoin protocol specifies using anonymous or mixed bitcoin transactions (such as by using CoinShuffle or ZeroCoin). And tying it all back together, in the TorPath protocol we again find Neff shuffling, used by the assignment servers to generate provably-random Tor relay circuits from groups of relays.
Your point about botnets is a very good one, and one we haven't considered fully. We will certainly address this further in future versions of the paper.
However, we do consider sybil attacks. Addressing them is the primary purpose of the TorPath assignment protocol. It ensures that, even if an adversary controls over 50% of the relays, there is a very low chance that (1/16 if I remember correctly) a new circuit will consist of three evil relays. Since we limit the number of coins that can be mined on a given circuit, we call this security a "good enough" margin of error for bad coins. Since it's predictable it can be baked into economic models.
But you're right, these are important considerations that we are taking very seriously.