[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: freehaven-dev@freehaven.net*Subject*: [freehaven-dev] mix-acc paper: incentives for Alice to play fair, system as network flow problem*From*: Michael J Freedman <mfreed@MIT.EDU>*Date*: Thu, 15 Mar 2001 04:20:00 -0500*Delivery-Date*: Thu, 15 Mar 2001 04:21:09 -0500*Reply-To*: freehaven-dev@freehaven.net*Sender*: owner-freehaven-dev@freehaven.net

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

**Follow-Ups**:**Re: [freehaven-dev] mix-acc paper: incentives for Alice to play fair, system asnetwork flow problem***From:*David Hopwood <hopwood@zetnet.co.uk>

- Prev by Date:
**Re: [freehaven-dev] (mix-acc) more ponderings about witnesses and receipts** - Next by Date:
**Re: [freehaven-dev] mix-acc paper: incentives for Alice to play fair, system asnetwork flow problem** - Prev by thread:
**Re: [freehaven-dev] (mix-acc) more ponderings about witnesses and receipts** - Next by thread:
**Re: [freehaven-dev] mix-acc paper: incentives for Alice to play fair, system asnetwork flow problem** - Index(es):