the O(N^2) problem

Mon Apr 14 02:38:03 UTC 2008

Another alternative is something we've been working on that we call  
Perspectives:

http://www.cs.cmu.edu/~dwendlan/perspectives/

Warning:  This is a work in progress.  The Mozilla plugin is a little  
flaky and the paper is still being revised for the final revision for  
USENIX.  The SSH code works pretty well.  We haven't written an SMTP  
version yet.

The basic idea is pretty simple:  Use multiple paths to a destination  
to figure out if you're likely getting to the right place.  If you  
_and_ your friends all observe the same public key from a server,  
preferably for a long period of time, then trust it.  Else scream  
bloody murder.  Perspectives provides these "friends" in the form of  
notary servers who you can ask about the past and present keys  
supplied by an SSL or SSH server.

(An alternate way of viewing this is to think of Perspectives as a low- 
overhead, low-cost PKI.)

It's an interesting thought exercise to wonder if we could extend the  
model to "trust not to send spam" instead of simply "trust to be the  
owner of the key", but that same exercise applies with a PKI, too.

   -Dave

On Apr 13, 2008, at 8:36 PM, Edward B. DREGER wrote:

>
> Bottom line first:
>
> We need OOB metadata ("trust/distrust") information exchange that  
> scales
> better than the current O(N^2) nonsense, yet is not PKI.
>
> And now, the details... which ended up longer reading than I intended.
> My apologies.  As Mark Twain said, "I didn't have time to write a  
> short
> letter, so I wrote a long one instead." :-)
>
> When it comes to establishing trust:
>
> * The current SMTP model is O(N^2);
>
> * I posit that the current IP networking model is sub-O(N);
>
> * PKI models are pretty much O(1).
>
> Polynomial-order just doesn't scale well.  It's mathematical fact, and
> particularly painful when the independent variable is still increasing
> quickly.
>
> Many operators seem to reject PKI as "power in too few hands".  I'll  
> not
> disagree with that.
>
> Conclusion:  What we need is something that scales better than O(N^2),
> but that is not as "few trusted keepers of the world" as PKI.
>
> Let's look to one of the current hot tickets: social networking.   
> Who is
> whose friend, who is in whose network, blah blah blah.  (The junior  
> high
> students seem to grok the concept of trust being semi-transitive!)
>
> Let's also draw upon operational lessons from a couple old-timers.  I
> recall using a critter known as "NNTP".  And once upon a time,  
> before my
> days on the Internet, lived a funny little beast called "UUCP".
>
> We track email quality from all mailservers that hit us.  I can whip  
> up
> a list of MXes/organizations that I'm willing to "trust" -- and let's
> leave that term imprecisely-defined for now.
>
> Here's what I propose:
>
> Establish a "distrust protocol".  Let path weight be "distrust".  The
> "trust path" is of secondary importance to "path weight", although not
> completely irrelevant.  SMTP endpoint not in graph?  Fine; have some
> default behavior.
>
> Let _trust_ be semi-transitive, a la BGP -- a technology that we know,
> understand, and at least sort of trust to run this crazy, giant  
> network
> that dwarfs even a 50M-user provider.
>
> Let actual _content_ still be end-to-end, so that we do not simply
> reincarnate NNTP or UUCP.
>
> Alternatively:
>
> I'm open to other suggestions.
>
> Or, there's plan "C":
>
> We continue to argue, banter, carp, fuss, grumble, moan, swear, whine,
> et cetera (I decided against running the alphabet) over the problem.
> Hey, it's worked/working great so far, right?
>