[freehaven-dev] mix-acc paper: incentives for Alice to play fair, system as network flow problem

[Michael J Freedman <mfreed@MIT.EDU>]

I added subsection about network flow analysis to the mix-acc paper
tonight.  Please read, and hack apart for length and content to your
heart's delight.  

I noticed some mention about Alice freeloading on reputation system.
Although I currently don't have a solution for this, I do have for
providing Alice with an incentive not to report false failures (i.e., for
Alice only telling the truth.)  Namely, if Wally the witness performs spot
checks on Alice's failure claim (he no longer needs to verify each, just
some small number of them), and he finds that Alice is giving a false
claim, then he can punish Alice by providing her with delayed reputation
information -- or simple efuse her requests for information.

This is for efficiency.  We don't possibly want Wally to query the network
for receipts for every failure reported -- only provide an incentive for
Alice to only tell the truth.  (The motivation behind making fines
prohibitively large when one, for example, doesn't "feed the meter" as
opposed to having some expensive method that guarantees everybody pays
always).  If Alice doesn't play fair, Wally punishes her accordingly.

Enjoy, I hope this is half-sensical at this late hour,
--mike



\subsection{Network Flow Analysis for MIX-nets}

We have just described a simple metric for measuring MIX-net
reliability on a per-node basis.  In reality, a reputation system
provides a feedback mechanism to account for dynamic network
reliability.  As users engage in the MIX-net protocol and report
failures accordingly, their data is inputted into the reputation
% we removed scorers totally -- witnesses score, right?  -mjf
functions kept by the witnesses -- reputations are continually revised
based on this ongiong accountability mechanism.  Therefore, this
feedback provides an element of learning for path selection.

From a graph theoretic standpoint, the MIX path selection process can
be modeled as a multicommodity unsplittable flow problem.  The
multicommodity flow generalizes a maxflow problem by allowing
multiples sources and sinks, which can transmit various types of
flow, called {\em commodities}.  The problem is complicated in that our
flows are {\em unsplittable} --  flows are onion-encrypted messages, sent
along paths pre-defined by the sources -- thus must be transmitted as
integral units. 

Fractional multicommodity flow roblems are exactly solvable by
deterministic, polytime algorithms.  However, requiring {\em integral}
solutions enteres the domain of NP-hard optimization problems.  A
variety of approximately algorithms may be used for solving such
multicommodity UFP in efficient polytime.  A classic example,
Raghavan's rounding algorithm \cite{raghavan87randomized} may be used
for this general class of flow problems, provided that maximum demands
are logarithmically smaller than the minimum capacity of a path.

%@misc{ raghavan87randomized,
%    author = "P. Raghavan and C. Thompson",
%    title = "Randomized rounding",
%    text = "P. Raghavan and C. Thompson. Randomized rounding.
Combinatorica, 7:365--374,
%      1987.",
%    year = "1987"
%}

%Leigten et al \cite{leighton91fast} solves multiple maxflow computations; 
%@inproceedings = { leighton91fast,
%    author = "Frank Thomson Leighton and Fillia Makedon and Serge A.
Plotkin and Clifford Stein and Eva Tardos and Spyros Tragoudas",
%    title = "Fast Approximation Algorithms for Multicommodity Flow Problems",
%    booktitle = "{ACM} Symposium on Theory of Computing",
%    pages = "101-111",
%    year = "1991"
%}

In general, however, network flow problems require global, exact
knowledge and centralized control of flows.  This is not realistic in
for decentralized MIX-net.  We must contend with imperfect knowledge
of bandwidth (edge capacity) and the costs associated with an edge.
We may approximate the cost of an edge $(s,t)$ as equal to its
destination's probability of failure $p_f(t)$; still, reputation
measurements may lag behind current network state, and users should
not be continually updating MIX paths in order to preserve better
anonymity coverage.

Furthermore, for client-selected MIX paths, the users themselves
should solve individual flow problems, with witness' reputations only
serving as an input to their calculations.  This decentralized solving
mechanism offers a challenge for traditional multicommodity flow
problems.  We leave this to future work.



-----
"Not all those who wander are lost."                  mfreed@mit.edu