Hi David!
A feature request based on (what I understand of) your hackweek project:
I often find myself in the position where I have a set of fingerprints,
and I want to know if I've "got them all". So something that inputs a
set of fingerprints, and outputs an ordered list of candidate "similar"
relays, would be a great tool.
What exactly we mean by similar, of course, will be a thing we need to
iterate on. If we had a huge dataset -- with ground truth -- we could
machine learning it and see how the black box gods answer. But while
that thought leads to "good idea, let's collect that data set", we need
something else in the mean time.
Here's a start:
* Component-wise similarity is computed differently for each component
(version/contactinfo/nickname is a string comparison, IP address is
looking for other relays on the same /x network, uptime is computing
the real uptime based on the descriptor timestamp minus the descriptor
uptime, etc),
* But the *strength* of a match is based on how few other relays
also matched. That is, we find a component match less compelling the
more relays there are that match. For example, maybe the /16 address
similarity is a weak match, because there are many relays on that same
/16, but the /24 address similarity is a strong match because there's
only one other relay closeby.
* We can start out with simple comparisons, but eventually we'll want
fuzzy comparisons, where e.g. we look at the Levenshtein distance for
nickname ("Anonymous1, Anonymous2, Anonymous3"), or check if the two
uptimes are within a threshold percentage of each other, etc.
* And then the overall similarity is a function of the strength of
each component-wise similarity. To start, we could just have it be
a linear combination of each, with equal weighting, which means the
more components have a strong match, the greater the overall similarity
score. There's a lot of opportunity for improvement here, like, weighting
certain components more, or non-linear weights where e.g. it's especially
interesting when both bandwidthrate and bandwidthburst are strong matches.
* So that's how we decide if *two* relays are similar to each other. But
if I give you *ten* relays, we need a way to figure out what those relays
have in common, to decide whether an eleventh relay is related to the
group as a whole. The easy version here is to just do pairwise comparisons
between each input relay and each consensus relay, and then sum the
overall similarities into a score for each candidate. This approach
should *implicitly* take into account similarity between input relays,
on the theory that if A is similar to C and B is similar to C, then A
is probably similar to B too. For extra credit, we could do some smarter
combination than just summing them, but I don't have anything in mind yet.
For comparison, check out phw's trnnr tool from the SybilHunter paper:
https://github.com/NullHypothesis/trnnr/blob/master/trnnr.py
which does a simplified version of the above (it only takes in one relay,
it doesn't do the "strength of match is inversely proportional to how much
of the population matches" part, and also it has a slick way of comparing
all the components at once by just turning them all into a big unified
string, which is simple but also has bizarre effects: every character in
the IP address string is equally important, and the importance of each
component is a function of how many characters it takes to represent it,
which is...weird. :) But in general, this script is a great start to
look at first.
--Roger
