Re: Grand challenges for software engineering

Kragen Sitaker (
Wed, 4 Aug 1999 11:15:31 -0400 (EDT)

A few comments.

Rohit writes:
> Nor will "buying" the solution -- a Teledesic terminal for every
> village, say, which is only a 5Mx$2,000 = $10B problem -- really be a
> solution, since this will be rented bandwidth, payable every year to a
> small oligopoly of Northerners.
> No, the key is shifting the info-peasants of the world from
> sharecropping & tenancy to landholders: *giving people renewable
> generators of bits rather than leases on bit-service*.

You are so right. This vision is why I'm on FoRK in the first place. :)

> Yet, in extremis, anyone on the planet can reach the attention of any
> other 4) within only a few degrees of separation (classically, 'six').

This glosses over a very difficult, possibly impossible, problem -- how
do you find the intermediate people? I am probably two or three
degrees of separation from Jewel, for example, disregarding computer
networks. But if I want to invite her over to my house for dinner, I
need to figure out who those two or three people are.

The only means by which I can currently get such information to an
arbitrary person through social networks are UPS, FedEx, and the postal
service -- which I think is sort of cheating, in that it doesn't avoid
the bandwidth-landlord problem.

This is the only part of the munchkin vision whose feasibility is
questionable. I tend to think that it is feasible.

I believe social networks in the 1700s were used to deliver letters.

> No, the only delta bit [between munchkins and mobile IP] was that
> nobody paid monthly fees, or per-bit fees, or per-page fees -- and
> yet, there was economic settlement throughout.
> Since I'm stumped at the moment, let me try to at least list some
> requirements I have in mind.

IMHO, the economic solution alone is a pretty big delta, but the real
power is that, if munchkins are adopted, it will put electronic speech
on the same grounds as physical speech. Right now, someone who wishes
to speak on the Internet can frequently be shut up -- or at least
delegitimized -- by legal threats to their ISP.

Ensuring that everyone can speak to everyone else, and that there is no
way to shut someone up except by means at least as difficult as are
required to shut someone up in real life (locking them in a
munchkinless prison) will be a significant advance in human rights on
the Internet.

(Of course, everyone must also have the right not to listen to whomever
they choose, which is a more difficult problem. Perhaps the method
that many celebrities use -- to require an introduction before
investing in too much contact -- could be used to filter out spam.)

> Instead, let's postulate that every device is "born" with a unique
> keypair, which becomes a 2,000-bit universally-unique identifier. Not
> one allocated from a central, "coherent" registry, but chosen at
> random with statistical bounds on collision probability nonetheless.

A randomly chosen 64-bit string is very likely to be unique. Large
numbers of devices with randomly-chosen 128-bit addresses are still
very likely to be unique; it is extremely unlikely that two devices
will ever get the same address, up to some reasonable number of
devices (trillions or quadrillions).

> [advanced note: of course, to protect keys, and allow "resale" to new
> owners, the actual device private key, generated by random noise at
> burn-in, forms the root of a mini-key hierarchy. E.g.having the
> camera's key sign the key corresponding to the lifetime of my
> ownership of it.]

I'm not entirely sure of what you're suggesting, but it sounds like
you're suggesting using a private key generated at burn-in time to
authenticate the device. This is a bad idea for two reasons:
- the maker of the device can spoof it, because they know the key (or
at least knew it when they made the device; it's not possible for them
to prove that they have forgotten it)
- it is quite likely that any possessor of the device can extract the key
without the device being aware of it, if recent work on breaking
smart-cards continues in the future.
- it enables people who talk to the device over the network to
determine who sold it to whom, violating privacy.

Why not just generate a totally new identity for the device when it's sold?

> * Self-Centered Namespaces

Beautiful. Pike's paper _The Hideous Name_ and SPKI have similar ideas.

On the other hand, I think a great deal of the usefulness of the
Internet, the Web, and Unix comes from putting everything in a single
namespace. Obviously Rob Pike disagreed in the early 1980s, though :)

> To reach that final state, some message has to be delivered to both
> devices proclaiming the new name, say "Rohit's Camera is 37, (signed)
> 51". How will both devices trust key 51 to speak for new entries in
> the Rohit namespace?
> ... the answer is that somehow both devices must have been told that
> Self's Rohit, as nominal "owner" is always-trusted for the "Rohit"
> namespace. Following precisely in the vein of PolicyMaker, KeyNote,
> &c, the *key* 51 shall be granted the authority to make these
> statements.

Naturally. Getting the laptop to call 51 "Rohit", without any
possibility of me confusing it and getting it to call call 72 (my key)
"Rohit", is really the only hard problem here.

> For that reason, I postulate an "absolutely-secure" trust management
> subsystem is part of the platform, ideally guaranteed through
> hardware.

Absolutely secure against what? Surreptitious key compromise?
Improbable -- I won't say impossible. Hardware security is often
touted, but has only been achieved in the case of nuclear missiles
(which will explode, with conventional explosives, if you try to tamper
with them).

(I assume this postulate is why you haven't said anything about key
revocation certificates, key revocation lists, etc.)

> Thus in the long run, if the network's average diameter is N, a
> user should be able to speak 1/N as often as they relay others'
> packets for "free".

Interesting. So if they speak more often than that, then other people
won't want to relay their packets, right?

How can you tell if they're relaying a packet or speaking on their own
behalf? Signed packets? Possible -- but how can you tell if they've
just generated another keypair? Or maybe the owner has another
munchkin that broadcasts very quietly sitting right next to it.

I can see how you can share the munchkins' retransmission resources
through market mechanisms. I don't see how you can share radio
bandwidth through market mechanisms. Suppose I set up my own munchkin
network that ignores yours, uses the same bands of RF, and carries more

The fundamental problem with market mechanisms here is that nobody owns
the spectrum in the first place. Historically, this has been dealt
with by one person or group of people seizing the unowned resource by
force, dissuading others from trying to use it without their permission
with the threat of violence. Counterexamples are welcome :)

> The second problem is the crux of the whole system, though. There's a
> damn good reason we don't use public-keys as addresses today: routers
> rely on the internal structure of IP addresses to map out the
> network. They need to look up, on-the-fly that "17-22 is on my right,
> 23-99 is on my left". Replacing two compressed entries with 100
> individual entries ("camera last seen at LAX") is suicide for
> high-speed, "core" routers. I'm gambling that 1) there's vast enough
> storage at leaf-nodes to maintain entirely private self-centered
> naming and routing tables.

Storage is one problem; update frequency is another problem.

There's a fairly straightforward solution to this problem, though,
coming from DNS. DNS consists of four things:
- a set of topologically-structured addresses that can be used to actually
deliver messages; in DNS, these are IP addresses.
- a set of hierarchically-structured globally-unique names that have no
necessary connection to the topologically-structured addresses. In
DNS, these are domain names.
- a mapping that maps domain names to sets of IP numbers of nameservers
that serve those domain names. In DNS, this is the hierarchy of NS
records and glue A records, plus the root hints file.
- a set of nameservers that will map a domain name for a machine to its
IP address.

Now replace IP addresses with geographical locations, and domain names
with public keys, and map public keys into geographical locations in
some arbitrary way, preferably one that is redundant and simple to
compute. (Public keys aren't inherently hierarchical, but you can do
the same trick with them that does with IP addresses.)
Every munchkin can be a nameserver.

Now all the messages you actually send over the network can have
geographical routing information, which makes routing feasible.

The nature of the nameserver mapping, and whether it introduces single
points of failure, and the nature of the geographical routing
information are definitely topics for further research. :)

I think some of these ideas came from some guy who sent me email a few
months ago.

> Yes, the net-effect may be that mail from me to Steve Case won't take
> a single transcontinental leap to, but in fact traverse the
> meandering six-degrees-of-separation path mirroring my own social
> friendships with people who might be friends of Steve's

Now, are you sending a copy of the mail to everybody you know, or are
you looking through your internal routing table to see how you're
connected to Steve Case? The former is inefficient (everybody on the
network will get a copy of your mail) and the latter is computationally
infeasible for a trillion nodes.

Thanks for your awesome vision, Rohit.

<>       Kragen Sitaker     <>
Wed Aug 04 1999
95 days until the Internet stock bubble bursts on Monday, 1999-11-08.