[freehaven-dev] The Alien Conspiracy (tm) Mixnet

[Brian T Sniffen <brians@MIT.EDU>]

We talked last week about a mixnet which made tracing more difficult
by not actually being point-to-point.  The model to have in mind is a
garden of flowers.  Each flower exudes several kinds of scent
particles.  Scent particles disperse slowly through the air, sometimes
sticking to other objects.  When we want to send a message, we find a
Carrier Bee, stick the message to it, and tell it about a few of the
scent particles near our target. 

The Bee wanders around, landing on flowers, trying to move towards
areas which have a stronger scent.  Eventually, it lands on the flower
which has the key to decrypt the message.  That flower turns out to be
a Cryptographic Fly-Trap and eats it.

So how do we make this work in real life, instead of the Garden of
Smelly Cryptography?  Funny you should ask:

\section{Joining an existing Mixnet} 

If I want to join an extant mixnet, the first thing I should do is
find some Mixnet nodes.  There's no reason for them not to make their
existence public, so let's assume that some do.  If there are mixnet
servers which don't publicize their existence, they'll end up as
middle-layer routers, which is fine.  If I can't find any Mixnet
nodes, then I should find some friends and we'll do the Starting a
Mixnet protocol below.

Having found some Mixnet nodes, I generate a series of $n$ identical
tokens, each of $b$ randomly-chosen bits.  I call this my address, and
keep most of it to myself.  Then, for each other node I know about, I
offer to trade one of my tokens for one of theirs.  I remove the token
I've traded away from my address and replace it with the one I've
received.  I also add the one I've given and the one I've received to
my approximation of the address of that neighbor.  Then I go on to the
Being a Good Mixnet Member section below.

It is worth noting that I should not make an attempt to find
\textbf{all} public mixnet nodes; I should instead choose some number
of those I know about and trade with those, ignoring the others.  A
fully connected mixnet doesn't mix very well.

\section{Starting a Mixnet}

This is just like the protocol above, except that we may wish to
impose artificial heirarchy.  That is, instead of letting all parties
know about each other (thus generating a fully connected and
ineffective mixnet), we want to lay out some more interesting graph.

\section{Being a Good Mixnet Member}

From time to time, as a Mixnet member, I'll get a message.  The
message will most likely be encrypted data; if it's something I can
read, however, I go right ahead and do so.  Even if I can read it,
however, it's important that I forward it on.

At the top of the message will be a series of tokens.  I compare these
tokens to the approximation of the address of each of my neighbors,
calculating the number of tokens in common with each.  Of those which
share the greatest number of tokens in common, I pick some number at
random and send the message there.  Once at least one other node has
received the message, I have no obligation to do anything further.

It is important that scent tokens continue to spread.  Thus, each node
has a user-set delay between trades.  When that delay has passed
without this node initiating a trade, we offer a trade to each of our
neighbors.  The token we are offering to trade is chosen at random
from the set of all our tokens, so it may not be one of our original
tokens.

Eventually, the above protocol would lead to a completely homogenous
set of tokens.  This would make message delivery problematic.  Thus
each node has a second user-set delay between mutations.  When that
delay has passed, the node picks one of its tokens at random, discards
it \emph{and all duplicates of it}, and generates a new token to
replace it.  \textt{This section needs work. Should we always discard
our original token?  Or one at random?  All copies?  Half of them?
Maybe we should just add new tokens? How many?}

\section{What's My Address?}

If I want to give out my address, I pick some $\log n$ of my tokens
at random and give them out.


I think that's about it, as far as the protocol goes.  Yes, a
simulation would be nice to have.  A proof would be even nicer.  $b$
should be large enough that two nodes don't pick the same one by
accident.  $n$ should be large enough for me to have a bunch of my
originals, some of those 1 hop from me, a few of those 2 hops, etc.

-Brian

Alien Conspiracy is a trademark of Mark LeBlanc.