Re: [freehaven-dev] Some possible weaknesses?

[Roger Dingledine <arma@mit.edu>]

On Wed, Feb 02, 2000 at 01:09:42AM -0500, dmolnar wrote:
> > originates.   In a very simple case, given 5 servers:  4 store 1 MG, 1
> > stores 50 MB.  The very large files floating around the servnet very likely
> > originated from the last server.
> 
> It seems to me that this points out a possible problem with introducing a
> file to the servnet : what happens when the introducing node _can't_ 
> trade away any of the newly formed shares? In this case,
> the share size will be >1 MB for some files, and so all
> shares of such files would have to stay on the 50MB server. 
> 
> Should the introduction fail, rather than allow a file to circulate which
> can easily be traced? if the introduction does fail, do we care about the
> DoS attack of killing trading requests until an introducing node kills a
> new file? could we prevent such an attack by making trading messages 
> indistinguishable from other messages, and so making such a selective DoS
> impossible? does the introducing node announce that the introduction 
> failed, or does it wait for the original owner to notice the file is gone? 
 
A server that accepts a trade accepts responsibility for the share that it
gets. If a server doesn't think it will be able to trade away a share it's
about to get, it better not accept it. If it does, it has made a poor
decision and will pay the consequences.

Eventually, the trust network will work such that if you give a share away
to somebody who makes poor decisions (like accepting a really huge share),
then you'll stop trusting him as much. Though really, *you* are the one
making the poor decision by making the huge share. And if you find some
sucker willing to take it, all you're really doing is continuing to shoot
yourself in the foot. So I'm not too worried about this.

If an introducee attempts to trade a really huge share, the server
will respond saying "no way, how about something in the 1 to 5 meg range?"
and they'll negotiate from there.

Can you elaborate on what you mean by 'killing trade requests until an
introducing node kills a new file'? (I don't understand it.) You mean refuse
to let the newbie join the servnet? I'd think that would be the time for the
newbie to go find another introducing server...
 
> This also touches tangentially on another point : do we allow servers
> to hold multiple shares of the same file? What happens if we allow
> share sizes to vary?

In theory, I don't see anything wrong with holding multiple shares, or
with having shares of varying sizes assuming the IDA can do that.

There might be legal implications to holding "enough" shares of a file
that you could reconstruct it yourself. But we're only hypothesizing
that that might be an issue...
 
> As currently stated in 5.3, the protocol takes a file F and breaks
> it into N shares f_1 , f_2 .... f_n. Any k of these shares is sufficient
> to reconstruct F. So they are all of equal "size" or "importance".
>  
> If you have two of these f_i shares , then you in some sense have a single
> share which has twice the "size" of the other shares. When I say "share
> sizes vary", I mean that we can create shares whose importance to
> a reconstruction of F can be expressed as something like a percentage.
> So we might say "f_1 is 20% important, f_2 is 40% important, " and so on
> -- any combination of shares with 100% or more importance reconstructs.
> 
> I think we may be able to use varied share sizes
> 
> a) to take advantage of better-performing servnet nodes
> b) to express trust or lack of trust in a particular servnet node
>    by giving it more or less importance in the eventual reconstruction
> 
> Here's an example for a) :
> 
> Suppose we have 10 servnet nodes. One of them, node N, has much better
> latency and more disk space than the others. In the current system, we
> might break up a file into 10 shares, such that 5 are needed to
> reconstruct, and distribute one share to each node.
> 
> Now at reconstruct time, N reports quickly. 3 other nodes report almost as
> quickly. The next node, however, is very long in responding, and holds
> up the entire reconstruction process.
> 
> What if we broke the file into 11 shares, such that any 5 are needed to
> reconstruct, and gave 2 shares to node N ? 
> 
> Now reconstruction happens as soon as N and 3 other servers report, and
> so may be much quicker. At the same time, we can still tolerate the
> failure of *any* 5 out of the 10 nodes. The cost is that we use more
> of N's disk space...but N has a lot of that, so we're OK. 
> 
> Another situation might be when we have a few high-bandwidth, high
> disk-space nodes serving data in legally unfriendly countries. Smaller
> "backup" shares could be kept on lots of bandwith-starved, low disk space
> nodes in more, uh, congenial legal climates. When the high-bandwidth
> nodes disappear, reconstruction automatically uses these "backup" shares.
> 
> b) I haven't thought about much yet. would it be useful?
> 
> Thanks, 
> -David Molnar

My first response is that we really shouldn't fine-tune the trading and
choosing and trust systems this much. They should be relatively simple
heuristics, and complex behaviors will emerge out of simplicity (order
out of chaos). We really don't have influence over what a machine does
once it has our shares (it could trade them away immediately) -- why
are we trying to tune things so much for each given server?

In your example of a few high-bandwidth nodes and the remainder
low-bandwidth nodes, did you mean that reconstruction would only look
to the 'backup' nodes if the main ones went down? How would it know?
Doesn't this add extra rules -- extra complexity -- to the system?
Does it really buy us anything?

But on the other hand, the idea of using varying-size shares for the
IDA is an important one. Can we gain anything security-wise out of
using different sized shares that we wouldn't get out of fixed-size
shares? (I think the answer to this is no.)

I think that we may well end up giving multiple shares to highly
trusted servers, but I don't think we should plan to do so. I don't
think we should 'plan' anything -- I think the rules will be very
simple and it might turn out one way or it might turn out another
way, but either way it will work.

That's the idea at least. :)
I should get some sleep, shouldn't I.

Thanks!
--Roger