Skip to Content.
Sympa Menu

bluesky - Re: Root and Branch Naming

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: hal AT finney.org
  • To: bluesky AT franklin.oit.unc.edu
  • Subject: Re: Root and Branch Naming
  • Date: Mon, 19 Mar 2001 11:23:36 -0800


Ted Anderson, <ota AT transarc.com>, writes:
> There are three aspects of the namimg problem which face different
> constraints and so probably require diverse solutions. The first level
> is the root names, this level faces tough non-technical problems.
> Second is the quasi-static namespaces, below the root, but still high in
> the naming hierarchy. This level has aggressive performance and
> reliability requirements. Third, the lower level directories, are not
> as widely shared, but maybe actively updated and is the control point
> needing flexible access control and synchronization.

I think you are assuming a relatively deep hierarchical model. Let me
first toss out the challenge that we may not need a naming hierarchy
at all. Is it really necessary that when I insert a document into the
network it has a name like
/technical/papers/computerscience/peertopeer/bluesky/problemswithnames.txt?
Is someone going to type this in? If not, why not something like Mark
Miller's pet-name system [1],
<key>7fa89sdf0a7sf098asf0978asf<s/>problemswithnames.txt</key>, which
shows up in your client as "Hal's problemwithnames.txt"? I'd like to
see more justification of the need for a hierarchical naming system
that fits every single piece of information in the world into a single
hierarchy rooted at /.

> For reasons of stability and replication I think the upper parts (but
> not the top) of the naming hierarchy are best implemented by static
> directories and described / named by a content-based hash (CHK). Each
> directory maps names to CHKs, and each CHK unambiguously designates a
> lower level directory. Because these high levels of the namespace are
> slowly changing and need to be very widely replicated and cached for
> performance reasons, it makes sense to use hashes to authenticate and
> identify them.

I see two problems with this. One is the assumption that they are slowly
changing. Certainly in the DNS that is not the case. However the DNS is
a very shallow hierarchy and you are probably assuming a deep one. Still
I suspect that directories near the top are going to be relatively dynamic,
because everyone is going to want a short name just like today.

Second, it's not clear how a directory informs its parents that an update
is needed, in an authenticated way. If /technical/papers/computerscience
adds a new subheading, it needs to tell /technical/papers, which then needs
to tell /technical, which then needs to tell the root name servers. This
notification methodology is outside the scope of your proposal, but it very
likely will involve public-key cryptography. This is exactly the technology
you propose to deal with the more dynamic directory levels below. Why not
just use PKC at all levels? See below for how Freenet proposes to do it.

> For lower levels of the namespace that are (relatively) little shared,
> it makes more sense to have a server / client architecture. In this
> environment the owner of the directory is a public key which is
> authorized to update the directory's contents. The transition between
> the second level hash tree and these online, lower level directories
> takes the form of a certificate. In the parent, the directory's name is
> mapped to the CHK of a certificate naming the public key of the
> directory owner, a list of server locations, and a CHK of a recent
> snapshot of the directory. This authorizes a server acting on behalf of
> the owning principal to offer directory services, such as lookup,
> update, and delegation. Delegation allows nodes with read access to
> cache a copy of the directory and arrange to be notified of updates.
> Delegation to a node authenticated as the owner allows the server named
> in the certificate to offload all request to the delegatee by simply
> forwarding all requests.

A few comments on this. First, this is similar to the idea behind
the Freenet Signature Verification (or Validation?) Key, SVK. It is
essentially a hash of a public key which owns a document. I believe
OceanStore also uses this mechanism.

Second, this mechanism would be useful for more than just updating
directories. What you have described would seem to handle file updates
as well. It makes sense to treat directories similarly to ordinary
files. Whatever mechanisms we have to deal with changes and updates
for directories can be done with files, too.

Third, it's not clear that the auxiliary information of server and
snapshot are necessary. Freenet and OceanStore use the SVKs as direct
indexes into the network. In Freenet they are "first-class" alternatives
to CHKs; in OceanStore they are the primary addresses of documents.
Given that you have a network that can find data, you don't need to store
server addresses. For performance it may be desirable to cache data,
but that might be true of leaf-node data as well as directory data.

One of the advantages of your explicit-server model is that it allows
the key holder more control over updates. Otherwise you do have problems
with cache staleness and distribution of updates. Freenet does not have
a solution to this yet; OceanStore has a very elaborate mechanism that is
supposed to chase down all copies of a document and update it.

Last, again it seems that this mechanism would work OK at the top levels
as well. The update interval would be larger, perhaps. Then you
don't have to redo all the hashes every time something changes three
levels down.

> I still think that an SPKI (Mark Miller's point that SDSI and SPKI have
> merged in RFC 2692/3 is well taken), approach is best for handling root
> names. I would imagine there would be two groups of competing root name
> authorities, the first group would consist of a handful of conservative
> organizations. These would only add names that were well defined and
> widely agreed upon, specifically, within the group of conservative
> naming authorities. The second group would consist of more liberal
> naming authorities which would add names relatively quickly and easily.
> Consequently they might sometime be in conflict with other naming
> authorities and would sometimes remove names that caused clashes. They
> would thus provide less stable naming than the first group. Most users
> would use one authority from the first group to populate their top-level
> names and possibly use one or more from the second group to fill in
> behind the primary server.

As I understand this, the root name authorities (RNAs) would not manage
the name spaces per se, but would be responsible solely for mapping top
level names into top level directories. In the example above, they
would map /technical into a CHK which would point at the directory for
everything under /technical. Typically the RNAs would support multiple
such mappings, and each such mapping would be supported by multiple RNAs.
Hopefully there would be substantial agreement among the RNAs about
which directory each top level name gets mapped to. This agreement
would be essentially 100% among the conservative RNAs, while the liberal
RNAs would handle a wider set of names, including those for which there
was competition and no consensus yet on which directory was the "real"
one for that domain.

I think the problem with this model is that it still takes too static
a view of the world. While it tries to accommodate change via the
liberal RNAs, I think there will be considerable contention even for the
names mapped by the conservative ones. Assuming there is some financial
advantage in owning a top level name, there will be a constant desire to
acquire the most popular names. So I think that we will see continual
flux in the providers of these names.

What is to prevent the owner of /com or /sex from overcharging for
their name registrations, if they have a de facto monopoloy conferred
by the conservative RNAs? The only thing that can limit them is fear
that others will challenge them by either stealing /com or by starting
competing domains. But for these challenges to be credible it must be
relatively easy to get new names into widespread use. This implies that
even conservative RNAs must be relatively flexible, or they can handle
only a small percentage of widely used names.

The experience we are getting from the DNS world is that top level
names are extremely valuable. The main registry for .com, .org and .net
was valued at 21 billion dollars! Given the huge amounts of money to
be made here, I don't think it is realistic to assume that the market
will be at all stable or orderly. DNS has been limited until now by
institutional monopolies. Under competition, with no trademark law to
provide property rights in names, it's going to be a wild ride.

One thing that's unclear here is how the RNAs themselves are named and
found. The impression I have is that they are not part of the globally
shared file system (which would produce an awkward recursion problem),
but rather they are servers identified as today with DNS names.

> In summary, I would suggest that there are three levels of the namespace
> which require different implementation mechanisms:
> 1 - root names, depending on political and social issues
> 2 - hash tree namespaces, providing high performance and stability
> 3 - online directories, supporting updates and synchronization

I think there are a lot of good ideas here. However I still don't see
the root name problem as being solved by letting the market screw in
the lightbulb. Institutions like trademarks and courts have evolved
worldwide because of exactly the problems that exist when names can be
used by anyone. Our admiration for markets should not blind us to the
fact that they can't solve all problems.

As far as the hashes versus certificates, this may depend on how deep
the hierarchy ends up being and how much true stability exists at the
highest levels. I would suggest that the system be agnostic about this
and allows CHKs and SVKs to be used interchangeably at any directory
level. Then technical issues of efficiency and convenience could govern
the choice.

Hal

[1] http://www.erights.org/elib/capability/pnml.html




Archive powered by MHonArc 2.6.24.

Top of Page