the O(N^2) problem

Edward B. DREGER eddy+public+spam at
Mon Apr 14 05:57:22 UTC 2008

Stardate Mon, 14 Apr 2008, Suresh Ramasubramanian's log:
SR> From: Suresh Ramasubramanian

SR> Looks like what various people in the industry call a "reputation
SR> system"

I started responding; Suresh's reply came as I was doing so, and put it
very succinctly.  Reputation system, but inter-"network".  Perhaps an
example would work better than my vague descriptions. :-)

Let's say I receive email from:

	From: <owen at ...>
	Received: from ... ( [])

Should I trust the message?  I don't "know" you.  However, I _do_ know

	From: <owen at ...>
	Received: from ... ( [])

and vouches for you.  Elaborating, using "trust
paths", *not* SMTP or routing paths:

	<owen at ...> # distrust metric: initially 0 # distrust metric: still 0 # dm: 1 (it mostly believes your MX) # dm: 2 (more or less trust NANOG)


	<owen at ...> # dm: 0 # dm: 0 (trying to impersonate) # dm: 10 (doesn't yet trust above host) # dm: 16 (after whatever local mods)


	<somenewaddress at ...> # dm: 0 # dm: 0 (your MX can vouch) # dm: 1 (more or less believes your MX) # dm: 2 (more or less trust NANOG)

IOW, I receive email from an unrecognized address from your MX.  Do I
trust it?  I mostly trust, which mostly trusts your
MX, which totally trusts <somenewaddress at ...>.  Therefore, I conclude
that I largely trust the message.

For such a system to scale, it would need to avoid OSPF-style
convergence.  Similarly, I would not want to query, for the sake of
example, 15k different "trust peers" each time I needed to validate a
new <host,address> tuple.  (Hence the interdomain routing and d-v calc

Therefore, one would find the locally-optimal solution at each "trust
hop", a la interdomain routing.

Perhaps PGP/GPG would be the best analogy.  (When I said "PKI", I should
have stated CA-based PKI; my original wording was excessively broad, and
should have explicitly excluded PGP.)

Everquick Internet -
A division of Brotsman & Dreger, Inc. -
Bandwidth, consulting, e-commerce, hosting, and network building
Phone: +1 785 865 5885 Lawrence and [inter]national
Phone: +1 316 794 8922 Wichita
DO NOT send mail to the following addresses:
davidc at -*- jfconmaapaq at -*- sam at
Sending mail to spambait addresses is a great way to get blocked.
Ditto for broken OOO autoresponders and foolish AV software backscatter.

More information about the NANOG mailing list