Extrait : « Personally I like the idea of hashcash if, and only if, it’s structured like a real currency as opposed to simply proof of work. In the real world you pay for resources used. In many cases this should also apply to P2P and other computer systems. Of course getting hashcash workable as a real currency is extremely difficult. I’ve thought of a scheme that would work (coins are signed by owner and can only be changed (signed to a different owner, by owner) except you need a decentralized « central » database of all the hashcash that’s been minted. Unworkable. !@#$ spend-twice problem. 🙁 » – Peter Todd, 10 mars 2001.
From hal at finney.org Thu Mar 1 14:24:24 2001
From: hal at finney.org (hal at finney.org)
Date: Thu, 1 Mar 2001 11:24:24 -0800
Subject: the three-services model
Message-ID: <200103011924.LAA20764@finney.org>
Wei Dai’s original article on the Three Services Model has appeared on
the openp2p.com news ticker (look at the lower right part of that page,
or the news page at http://www.openp2p.com/p2p/news.csp). The link
ponints directly into the Bluesky archives. The OpenP2P site does not
provide a discussion forum on its news page, but this could lead to
wider distribution of information about this list.
Hal
From mccoy at io.com Mon Mar 5 20:41:24 2001
From: mccoy at io.com (Jim McCoy)
Date: Mon, 05 Mar 2001 17:41:24 -0800
Subject: market-based data location (was Scalability)
In-Reply-To: <LYRIS-126465-22200-2001.02.27-21.00.25–mccoy#io.com@ibibl io.org>
References: <LYRIS-127746-22107-2001.02.27-12.23.04–md98-osa#nada.kth.se@ibiblio.org>
Message-ID: <4.3.2.7.2.20010302142754.00d11290@pop.io.com>
At 03:02 AM 2/28/01 +0100, Oskar Sandberg wrote:
>[…]
>I approached the Mojonation people regarding my concern that the whole
>content tracking system was not really decentralized at all at the Peer to
>Peer conference.
Actually our opinion is that our content tracking system is _too_
decentralized. It would have served us better to start off with a few
centralized content trackers (a la Napster) that were specialists in a
particular content type rather than the Gnutella-like indexing structure
which we currently employ. A few handicappers exist within our current
code to do keyword-hash based lookups (woe to the poor slob who gets stuck
with « britanny » or « spears » 🙂 but these have not really been tested very much.
>It turned out however, that Mojonation’s basic architecture isn’t scalable
>anyways. The content-trackers in MN do not map metadata onto a physical
>address, they map metadata onto UIDs (the SHA1 hash for each part) of the
>data. Apparently, to then find the data, MN simply expects each node to
>keep a list of the IDs of every other node in the network […]
This is incorrect. Each node keeps a set of phonebook entries for other
brokers that it has contacted in the past (not the entire list, just the
nodes you have communicated with). These entries contain information such
as broker ID (to link to reputation information about that broker), contact
information and connectin strategies (e.g. to contact Broker X send the
message to relay server Y), and specific service info such as the block
mask for a storage service agent. It is these masks which are used to
determine who you will send a request to when looking for a blob of data.
If you can’t find the blob you are looking for at any of the brokers you
know who cover that range of the SHA1 address space then the Broker goes
back to the centralized metatracker and asks it for a few more phonebook
entries which cover the range of the address space it is interested in and
caches these entries. This scales sufficiently well for our current
prototype and when this starts to show scaling problems we will drop in the
gossip-based mechanism to limit reliance on metatrackers for new block
server phonebook entries.
In our gossip-based lookup system your Broker would send a phonebook lookup
request to block servers that a Broker knows about which were closest to
the desired range. These block servers would either answer the request as
best they could with entries out of thier cache or direct the originator of
the request to a few other block servers which were even closer to the
correct mask range in the hope that they could provide useful phonebook
info. Each Broker will hold on to phonebook entries that overlap or are
near its mask range longer than it will for other ranges of the block
address space. Each block server within a Broker will become a specialist
in the metainfo about other blocks servers whose mask is a near-match,
allowing us to replicate data blocks within the network easier and
assisting other Brokers by being able to provide useful phonebook info.
Next time perhaps you could try to make sure that you actually understand
how another system works before you start throwing stones…
jim mccoy
AZI/Mojo Nation
From md98-osa at nada.kth.se Tue Mar 6 06:25:50 2001
From: md98-osa at nada.kth.se (Oskar Sandberg)
Date: Tue, 6 Mar 2001 12:25:50 +0100
Subject: market-based data location (was Scalability)
In-Reply-To: <LYRIS-127746-23645-2001.03.05-20.43.31–md98-osa#nada.kth.se@ibiblio.org>; from mccoy@io.com on Mon, Mar 05, 2001 at 05:41:24PM -0800
References: <LYRIS-126465-22200-2001.02.27-21.00.25–mccoy#io.com@ibibl io.org> <LYRIS-127746-23645-2001.03.05-20.43.31–md98-osa#nada.kth.se@ibiblio.org>
Message-ID: <20010306122550.C623@hobbex.localdomain>
On Mon, Mar 05, 2001 at 05:41:24PM -0800, Jim McCoy wrote:
> At 03:02 AM 2/28/01 +0100, Oskar Sandberg wrote:
> >[…]
> >I approached the Mojonation people regarding my concern that the whole
> >content tracking system was not really decentralized at all at the Peer to
> >Peer conference.
>
> Actually our opinion is that our content tracking system is _too_
> decentralized. It would have served us better to start off with a few
> centralized content trackers (a la Napster) that were specialists in a
> particular content type rather than the Gnutella-like indexing structure
> which we currently employ. A few handicappers exist within our current
> code to do keyword-hash based lookups (woe to the poor slob who gets stuck
> with « britanny » or « spears » 🙂 but these have not really been tested very much.
I guess that with the emphasis of MN’s technology research being on the
monetary system you can justify doing a rough job of searching – but I
think you can understand why those of us who emphasize on data sharing
architectures are somewhat taken aback by that. Especially in light of MN
often being presented as a decentralized data sharing network.
> >It turned out however, that Mojonation’s basic architecture isn’t scalable
> >anyways. The content-trackers in MN do not map metadata onto a physical
> >address, they map metadata onto UIDs (the SHA1 hash for each part) of the
> >data. Apparently, to then find the data, MN simply expects each node to
> >keep a list of the IDs of every other node in the network […]
>
> This is incorrect. Each node keeps a set of phonebook entries for other
> brokers that it has contacted in the past (not the entire list, just the
> nodes you have communicated with). These entries contain information such
> as broker ID (to link to reputation information about that broker), contact
> information and connectin strategies (e.g. to contact Broker X send the
> message to relay server Y), and specific service info such as the block
> mask for a storage service agent. It is these masks which are used to
> determine who you will send a request to when looking for a blob of data.
>
> If you can’t find the blob you are looking for at any of the brokers you
> know who cover that range of the SHA1 address space then the Broker goes
> back to the centralized metatracker and asks it for a few more phonebook
> entries which cover the range of the address space it is interested in and
> caches these entries. This scales sufficiently well for our current
> prototype and when this starts to show scaling problems we will drop in the
> gossip-based mechanism to limit reliance on metatrackers for new block
> server phonebook entries.
Obviously, I don’t think I need to comment on my opinion of this model.
Are you guys not concerned about waking up one morning with a friendly
letter from the RIAA in your mailbox (something that has already happened
to several Opennap admins)?
> In our gossip-based lookup system your Broker would send a phonebook lookup
> request to block servers that a Broker knows about which were closest to
> the desired range. These block servers would either answer the request as
> best they could with entries out of thier cache or direct the originator of
> the request to a few other block servers which were even closer to the
> correct mask range in the hope that they could provide useful phonebook
> info. Each Broker will hold on to phonebook entries that overlap or are
> near its mask range longer than it will for other ranges of the block
> address space. Each block server within a Broker will become a specialist
> in the metainfo about other blocks servers whose mask is a near-match,
> allowing us to replicate data blocks within the network easier and
> assisting other Brokers by being able to provide useful phonebook info.
This is closer to the sort of the self-sorting we are using for Freenet,
although we are interested only in comparing the data key (aka GUID or
whatever) values, since nodes have no static range to cover (let alone one
they can choose themselves, since we consider this opportunity for
targeted attacks on parts of the keyspace unacceptable). I can warn you
however, that making this sort of system work is not easy – and even when
it does you have given up deterministically finding the results.
In light of the fact that you are using the « rigid » model of matching data
id’s and with node id’s anyways, I would very recommend you look at the
Plaxton model for routing in this type of system. It’s very fast for
searching (you can keep it 4 or 8 times under logarithmic for the worst
case) and also has some interesting characteristics for finding the best
located data (though you needn’t employ those).
> Next time perhaps you could try to make sure that you actually understand
> how another system works before you start throwing stones…
Not a chance.
>
> jim mccoy
> AZI/Mojo Nation
—
‘DeCSS would be fine. Where is it?’
‘Here,’ Montag touched his head.
‘Ah,’ Granger smiled and nodded.
Oskar Sandberg
md98-osa at nada.kth.se
From ota at transarc.com Tue Mar 6 06:52:17 2001
From: ota at transarc.com (Ted Anderson)
Date: Tue, 6 Mar 2001 06:52:17 -0500 (EST)
Subject: market-based data location (was Scalability)
In-Reply-To: <LYRIS-126365-22039-2001.02.27-03.15.45–ota#transarc.com@ibiblio.org>
References: <LYRIS-126365-22039-2001.02.27-03.15.45–ota#transarc.com@ibiblio.org>
Message-ID: <AudAxlA99g1Q1VlE40@transarc.com>
On 27 Feb 2001 00:12:55 PST wrote:
> But I was struck by the statement in the introduction to one of their
> papers that their goal is to support a network with 10^10 users (10
> billion users, i.e. the total population of Earth), each storing 10000
> files, for a total of 100 trillion files. That’s a lot of files!
> Scaling to that level will be a real challenge.
This figure struck me as well, because it agreed with my thinking about
the appropriate scale of the decentralized file system I envision. This
was crystallized for me when I tried, unsuccessfully, to convince myself
that a 128-bit hash value was sufficiently large for object CHKs. When
I considered how many nodes might participate in the system and how many
objects each might create over a period of years, I could not do it. I
assumed 10^10 nodes (not users, but actively participating computers)
and over its lifetime it seemed plausible that a node might create 10^10
files (about 33/sec for 10 years). This comes to 10^20 (2^66.5) objects
and, since the birthday paradox tells us that collisions will be common
when we reach the square root of the hash size, 128 bits seemed just too
small for comfort. Using the 160 bit SHA-1 output provides a nice
margin of safety.
In a relatively benign environment, I could imagine a system like the
OceanStore data location scheme working at this scale. I have argued in
favor of a similar idea based on boolean hypercubes for several years.
However, I now think the Internet is hostile enough that a more
flexible, adaptable approach based on market incentives will be
necessary. At the beginning of this thread, Wei Dai, very briefly,
described such a system.
The economic model is the only one we know of that can organize
loosely-coupled human systems on this scale. If we generalize the
interpretation of « economic » to include cooperative, mutually beneficial
interactions of all kinds this organizational capability applies to
complex systems of essentially any type. Robert Wright, expounds on
this idea in his book titled « Nonzero: The logic of Human Destiny ». He
argues that increasing complexity of all living systems are driven by
nonzero-sum interactions on many levels.
The specific shortcomings of MojoNation-style economics, and with
micro-payments in general, are worth understanding. The conclusion I
think we must draw, however, is not that we should avoid market-based
incentives, but that we need to find a way to incorporate these
mechanisms in a way that will enable mutually beneficial cooperation
between agents while suppressing parasitic interactions.
Ted Anderson
From hal at finney.org Tue Mar 6 12:05:31 2001
From: hal at finney.org (hal at finney.org)
Date: Tue, 6 Mar 2001 09:05:31 -0800
Subject: Naming via SDSI
Message-ID: <200103061705.JAA13116@finney.org>
An article on Wired Online this morning describes a case of multiple
name services competing for business. One of the issues is that it will
not work well if there are two independent name server systems that
service the same TLD (.xxx in this case). I think the problems are,
first, that it would be inefficient to have to query two name servers to
find out where sexygirls.xxx is; and second, that the two groups might
register the same name, making addresses ambiguous. Both of these would
be resolved by assigning each TLD to only one name service operator.
How would that work in a P2P model? If we did have competing name lookup
services (using Wei’s term from the three service model), would there
have to be some global mechanism to make sure that no two services tried
to handle the same addresses? Or would we accept that address to name
mapping was inherently ambiguous? Or, perhaps, would TLDs have to have
unfriendly unforgeable names?
Mark Miller sent me a pointer to an idea of his that he had proposed
in another context, http://www.erights.org/elib/capability/pnml.html.
The idea of his « Pet Name Markup Language » (pnml) is that you pass around
long, unambiguous names (such as hashes), but let the display software
substitute short, user-assigned, local nicknames, somewhat similar to
what is done in SDSI. Maybe this could eliminate the need for name
lookup services, at least in some cases (including in particular the
TLD issue discussed above).
Hal
===
http://www.wired.com/news/business/0,1367,42217,00.html:
New.net announced Monday that it was offering 20 new top-level
domains (TLDs) including dot-xxx, which could be intriguing for adult
sites. But Domain Name Systems has been selling dot-xxx domains for
several months.
The competing efforts that go outside the Internet’s accepted domain
name system could become a complex legal dispute over dispensing
adult domains.
New.net began selling domains using TLDs that are not approved by
the Internet Corporation for Assigned Names and Numbers (ICANN), the
international agency charged with overseeing TLDs. The company began
distributing software that enables Web browsers to access the new TLDs.
Domain Name Systems has been offering dot-xxx and dot-sex registrations
since ICANN rejected those two proposed TLDs last November.
…
Stacey King, an intellectual property lawyer at Howrey Simon Arnold &
White, said disputes between two companies trying to register the same
domain name would have to be settled via trademark, if it’s possible.
« Things will have to go back to traditional trademark principles. Do
they have a registered trademark or common law rights to a name? Have
they used it in commerce? They may have greater rights than someone
who doesn’t have a federal registration, » she said.
If there is no trademark or history of doing business under a name,
then things could get nasty, since there are no laws governing
ownership of top-level domains. « It may come down to first-come,
first-served unless these two companies want to fight it out in the
courts who has a right to the top-level domain, » King said.
From markm at caplet.com Tue Mar 6 12:17:14 2001
From: markm at caplet.com (Mark S. Miller)
Date: Tue, 06 Mar 2001 09:17:14 -0800
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127811-23817-2001.03.06-12.08.44–markm#caplet.com@i biblio.org>
Message-ID: <5.0.2.1.2.20010306091536.00a88290@shell9.ba.best.com>
At 09:05 AM Tuesday 3/6/01, hal at finney.org wrote:
>Mark Miller sent me a pointer to an idea of his that he had proposed
>in another context, http://www.erights.org/elib/capability/pnml.html.
>The idea of his « Pet Name Markup Language » (pnml) is that you pass around
>long, unambiguous names (such as hashes), but let the display software
>substitute short, user-assigned, local nicknames, somewhat similar to
>what is done in SDSI. Maybe this could eliminate the need for name
>lookup services, at least in some cases (including in particular the
>TLD issue discussed above).
Thanks!
I’m puzzled by this reference to SDSI. I had thought that SDSI had been
fully absorbed into SPKI, and AFAIK SPKI has no such mapping from keys back
to names. ??
Cheers,
–MarkM
From hal at finney.org Tue Mar 6 12:39:36 2001
From: hal at finney.org (hal at finney.org)
Date: Tue, 6 Mar 2001 09:39:36 -0800
Subject: Naming via SDSI
Message-ID: <200103061739.JAA13361@finney.org>
I wrote earlier:
> Mark Miller sent me a pointer to an idea of his that he had proposed
> in another context, http://www.erights.org/elib/capability/pnml.html.
> The idea of his « Pet Name Markup Language » (pnml) is that you pass around
> long, unambiguous names (such as hashes), but let the display software
> substitute short, user-assigned, local nicknames, somewhat similar to
> what is done in SDSI.
I want to clarify that « what is done in SDSI » is maintaining a database
associating local nicknames with keys. SDSI does not map back and
forth between nicknames and keys the way Mark proposes in the PNML.
That is a new and interesting idea which could be another approach to
the name mapping problem.
Hal
From dmarti at zgp.org Tue Mar 6 14:09:14 2001
From: dmarti at zgp.org (Don Marti)
Date: Tue, 6 Mar 2001 11:09:14 -0800
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127814-23817-2001.03.06-12.08.44–dmarti#zgp.org@ibiblio.org>; from hal@finney.org on Tue, Mar 06, 2001 at 09:05:31AM -0800
References: <LYRIS-127814-23817-2001.03.06-12.08.44–dmarti#zgp.org@ibiblio.org>
Message-ID: <20010306110914.F3154@zgp.org>
On Tue, Mar 06, 2001 at 09:05:31AM -0800, hal at finney.org wrote:
> How would that work in a P2P model? If we did have competing name lookup
> services (using Wei’s term from the three service model), would there
> have to be some global mechanism to make sure that no two services tried
> to handle the same addresses? Or would we accept that address to name
> mapping was inherently ambiguous? Or, perhaps, would TLDs have to have
> unfriendly unforgeable names?
All this bogus DNS stuff will get settled at the business level, not
the crypto level.
There are already sites that rate registrars. The services would just
have to add a column to their ratings chart with an estimate of what
percentage of the hosts on the net can resolve each registrar’s domains.
(Data for this could be collected by putting small images, srced from
all the new domains, on popular pages.)
New registrars will presumably offer registrations at no charge to
build up a user base, and pay webmasters to make new-domain-only
content to encourage ISPs to recognize their TLDs. (For example, if you
run pornpornporn.com, a new registrar offering .xxx will _give_ you
pornpornporn.xxx and pay you to put free porn there that’s not on your
original site.)
More popular registrars will get more registrations with more content,
thereby scooping up more ISPs — positive reinforcement for the more
popular one that will make the less popular one get fewer registrations,
less content, and less demand. Competition won’t be an issue.
—
Don Marti « I’ve never sent or received a GIF in my life. »
dmarti at zgp.org — Bruce Schneier, Secrets and Lies, p. 246.
http://zgp.org/~dmarti/ (Free the Web: http://burnallgifs.org/)
From hal at finney.org Tue Mar 6 14:42:58 2001
From: hal at finney.org (hal at finney.org)
Date: Tue, 6 Mar 2001 11:42:58 -0800
Subject: Naming via SDSI
Message-ID: <200103061942.LAA13981@finney.org>
Don Marti, , writes:
> More popular registrars will get more registrations with more content,
> thereby scooping up more ISPs — positive reinforcement for the more
> popular one that will make the less popular one get fewer registrations,
> less content, and less demand. Competition won’t be an issue.
You are suggesting that the end result of a competitive process will be
that each new TLD is assigned to just one registrar (name lookup service).
Each one will have a de facto monopoly on that particular name.
It’s possible that the results will approximate this state, but I don’t
think it will be as clean as you suggest. New domains will spring up
all the time and there will be a battle over who gets to serve them.
Well established registrars may make « raids » on other registrars’ domains
to try to establish themselves as alternatives for those TLDs. The same
thing can be accomplished by creating new domains: is it .xxx or .sex?
.vid or .tv? .snd or .mus? Registrars will spend money promoting new
alternative TLDs in the hopes that they will become popular and steal
business from other TLDs. There may also be truces between registrars
who agree to share a TLD and cooperate to make sure they don’t assign
competing names. Then these truces will be broken sometimes.
It’s going to be a dynamic process. That’s how competition works.
It seems likely that a substantial number of TLDs will be in flux at
any given time. This will lead to ambiguity, uncertainty and costs in
doing name lookups. I don’t think this is an ideal solution.
Hal
From dmarti at zgp.org Tue Mar 6 20:46:52 2001
From: dmarti at zgp.org (Don Marti)
Date: Tue, 6 Mar 2001 17:46:52 -0800
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127814-23852-2001.03.06-14.46.08–dmarti#zgp.org@ibiblio.org>; from hal@finney.org on Tue, Mar 06, 2001 at 11:42:58AM -0800
References: <LYRIS-127814-23852-2001.03.06-14.46.08–dmarti#zgp.org@ibiblio.org>
Message-ID: <20010306174652.H19251@zgp.org>
On Tue, Mar 06, 2001 at 11:42:58AM -0800, hal at finney.org wrote:
> It’s going to be a dynamic process. That’s how competition works.
> It seems likely that a substantial number of TLDs will be in flux at
> any given time. This will lead to ambiguity, uncertainty and costs in
> doing name lookups. I don’t think this is an ideal solution.
A two-tier structure of both competitive and official TLDs would be
better than an ICANN-only one.
People who want to explore the wild and wooly domains can run a simple
caching nameserver at home; people who want to stick with ICANN and
any rogue TLDs that get well-established can use their ISP’s name server.
—
Don Marti « I’ve never sent or received a GIF in my life. »
dmarti at zgp.org — Bruce Schneier, Secrets and Lies, p. 246.
http://zgp.org/~dmarti/ (Free the Web: http://burnallgifs.org/)
From blanu at uts.cc.utexas.edu Tue Mar 6 22:09:25 2001
From: blanu at uts.cc.utexas.edu (Brandon)
Date: Tue, 6 Mar 2001 21:09:25 -0600 (CST)
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127736-23817-2001.03.06-12.08.44–blanu#uts.cc.utexas.edu@ibiblio.org>
Message-ID: <Pine.OSF.4.21.0103062040370.9045-100000@moe.cc.utexas.edu>
> How would that work in a P2P model? If we did have competing name lookup
> services (using Wei’s term from the three service model), would there
> have to be some global mechanism to make sure that no two services tried
> to handle the same addresses? Or would we accept that address to name
> mapping was inherently ambiguous? Or, perhaps, would TLDs have to have
> unfriendly unforgeable names?
Well, I see three ways to handle this: central authority to resolve
disputes, choosing sides, or total subjectivity. Pet names is total
subjectivity. I think that’s a pretty good system. It’s the system I’m
using to do e-mail over Freenet (PGP fingerprint == key, Freenet « e-mail
address » == pet name).
My main issue with total subjectivity is that it requires that you pass
around fat references (keys) all the time. So I can’t tell someone « Check
out megatokyo.com. » I have to say « check out
asjldkq9u4q8412093ajla0912l ». It helps if you have a computer-mediated
communication environment to do translation for you, but it sucks for
voice and written. I know the last time I wrote down my PGP fingerprint I
made to copying errors. If it was a different kind of key, such errors
woul have made it useless.
Having naming paths helps because then, for instance, I can run a name
mapping service and if you already have my key then I can tell you « check
out brandon/megatokyo » and that path will resolve. It still has the same
theoretical problems, but in practice will suck less because you tend to
communicate with the same people a lot.
From blanu at uts.cc.utexas.edu Tue Mar 6 22:12:52 2001
From: blanu at uts.cc.utexas.edu (Brandon)
Date: Tue, 6 Mar 2001 21:12:52 -0600 (CST)
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127736-23841-2001.03.06-14.09.30–blanu#uts.cc.utexas.edu@ibiblio.org>
Message-ID: <Pine.OSF.4.21.0103062109400.9045-100000@moe.cc.utexas.edu>
> There are already sites that rate registrars. The services would just
> have to add a column to their ratings chart with an estimate of what
> percentage of the hosts on the net can resolve each registrar’s domains.
> (Data for this could be collected by putting small images, srced from
> all the new domains, on popular pages.)
This is just moving the trust authority to the registrar rating site. Or
to a trust oligopoly of registrar rating sites. So I’d say it doesn’t
actually change the problem at all. You now have to choose you to
trust, you just have a new layer of middlemen.
I’m not saying this isn’t better than ICANN. I think it is.
From alk at pobox.com Tue Mar 6 22:18:49 2001
From: alk at pobox.com (Tony Kimball)
Date: Tue, 6 Mar 2001 21:18:49 -0600 (CST)
Subject: Naming via SDSI
References: <LYRIS-127736-23817-2001.03.06-12.08.44–blanu#uts.cc.utexas.edu@ibiblio.org>
<LYRIS-127815-24021-2001.03.06-22.09.42–alk#pobox.com@ibiblio.org>
Message-ID: <15013.43161.904733.426487@spanky.love.edu>
Quoth Brandon on Tuesday, 6 March:
:
: …resolve disputes…
I find it difficult to imagine how disputes could last, frankly:
Anyone who plans to stick around is going to be synchronizing with the
other registries as often as possible. Indeed, I can’t see any sane
business reason not to run all the registries off of a single
meta-registry database. It’s only when someone has the heady smell of
monopoly in their nostrils that they could seriously consider
disincluding any other competent registry.
From retep at penguinpowered.com Tue Mar 6 22:37:55 2001
From: retep at penguinpowered.com (Peter Todd)
Date: Tue, 6 Mar 2001 22:37:55 -0500
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127744-24021-2001.03.06-22.09.42–retep#penguinpowered.com@ibiblio.org>; from blanu@uts.cc.utexas.edu on Tue, Mar 06, 2001 at 09:09:25PM -0600
References: <LYRIS-127736-23817-2001.03.06-12.08.44–blanu#uts.cc.utexas.edu@ibiblio.org> <LYRIS-127744-24021-2001.03.06-22.09.42–retep#penguinpowered.com@ibiblio.org>
Message-ID: <20010306223755.A1557@petes.localdomain>
On Tue, Mar 06, 2001 at 09:09:25PM -0600, Brandon wrote:
> My main issue with total subjectivity is that it requires that you pass
> around fat references (keys) all the time. So I can’t tell someone « Check
> out megatokyo.com. » I have to say « check out
> asjldkq9u4q8412093ajla0912l ». It helps if you have a computer-mediated
> communication environment to do translation for you, but it sucks for
> voice and written. I know the last time I wrote down my PGP fingerprint I
> made to copying errors. If it was a different kind of key, such errors
^
We already make enough errors just writing normal text. 🙂
Whats so special about PGP figerprints BTW that allows them to
tolerate errors?
—
retep at penguinpowered.com http://retep.tripod.com
————– next part ————–
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.ibiblio.org/pipermail/bluesky/attachments/20010306/d3252819/attachment.bin
From blanu at uts.cc.utexas.edu Tue Mar 6 22:46:24 2001
From: blanu at uts.cc.utexas.edu (Brandon)
Date: Tue, 6 Mar 2001 21:46:24 -0600 (CST)
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127736-24030-2001.03.06-22.39.54–blanu#uts.cc.utexas.edu@ibiblio.org>
Message-ID: <Pine.OSF.4.21.0103062142220.9045-100000@moe.cc.utexas.edu>
> We already make enough errors just writing normal text. 🙂
Names like google, slashdot, and freenetproject are resistant to errors
in duplication.
> Whats so special about PGP figerprints BTW that allows them to
> tolerate errors?
You check a PGP fingerprint against a key. So if the fingerprint has
errors but not many then you can still trust it.
From blanu at uts.cc.utexas.edu Tue Mar 6 22:49:54 2001
From: blanu at uts.cc.utexas.edu (Brandon)
Date: Tue, 6 Mar 2001 21:49:54 -0600 (CST)
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127736-24025-2001.03.06-22.19.10–blanu#uts.cc.utexas.edu@ibiblio.org>
Message-ID: <Pine.OSF.4.21.0103062146370.9045-100000@moe.cc.utexas.edu>
> I find it difficult to imagine how disputes could last, frankly:
> Anyone who plans to stick around is going to be synchronizing with the
> other registries as often as possible. Indeed, I can’t see any sane
> business reason not to run all the registries off of a single
> meta-registry database.
Having a meta-registry is just shifting the central authority from ICANN
to the people that run the meta-registry, avoiding the question of a
situation without a central trust authority. In such a system disputes
might occur.
From markm at caplet.com Wed Mar 7 01:43:46 2001
From: markm at caplet.com (Mark S. Miller)
Date: Tue, 06 Mar 2001 22:43:46 -0800
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127811-24021-2001.03.06-22.09.42–markm#caplet.com@i biblio.org>
References: <LYRIS-127736-23817-2001.03.06-12.08.44–blanu#uts.cc.utexas.edu@ibiblio.org>
Message-ID: <5.0.2.1.2.20010306215651.043f3890@shell9.ba.best.com>
At 07:09 PM Tuesday 3/6/01, Brandon wrote:
>My main issue with total subjectivity is that it requires that you pass
>around fat references (keys) all the time. So I can’t tell someone « Check
>out megatokyo.com. » I have to say « check out
>asjldkq9u4q8412093ajla0912l ». It helps if you have a computer-mediated
>communication environment to do translation for you, but it sucks for
>voice and written. I know the last time I wrote down my PGP fingerprint I
>made to copying errors. If it was a different kind of key, such errors
>woul have made it useless.
>
>Having naming paths helps because then, for instance, I can run a name
>mapping service and if you already have my key then I can tell you « check
>out brandon/megatokyo » and that path will resolve. It still has the same
>theoretical problems, but in practice will suck less because you tend to
>communicate with the same people a lot.
I think this summarizes well both the good and bad news with total
subjectivity, as in SPKI/SDSI/Pet-Names. I also think this is as good
as it gets. See http://www.cap-lore.com/MathPhys/GRref.html . And I think
the bad news isn’t this bad, as explained below.
The other choices are mostly illusory. « Central authority » actually becomes
« choosing sides » since (hopefully) we’ll never have unanimity about who
should be world dictator. Witness the upcoming war between ICANN and the
government of Tonga of the TLD « .to ». (Tonga refuses to pay their dues to
ICANN, saying, rightly, « Who put you in charge? ».) Global name spaces
create unsolvable political problems. To attempt to live within a global
name space is to choose to subjugate yourself and your customers to
unnecessarily centralized authorities.
« Choosing sides » is really just a broken way to look at subjectivity +
naming paths anyway, as the creators of SDSI correctly explained. For
example, in my use of PNML,
BrandontldServertocypherpunks
starts with the name server I take to serve Brandon’s exported names, asks it
what TLD server it takes as authoritative, and then decodes cypherpunks.to
within that TLD system. This might be a different entity than the one
designated by my use of « tldServertocypherpunks ». So even
the domain name system is best seen through the eyes of subjectivity +
naming paths.
For direct communication with people you already know, I think you
underestimate:
>I can run a name
>mapping service and if you already have my key then I can tell you « check
>out brandon/megatokyo » and that path will resolve. It still has the same
>theoretical problems,
I don’t think it does. If I have a communications directly from Brandon,
let’s say I meed Brandon at a party, and let’s say I have a basis for
believing a correspondence between my face-recognition of Brandon and his
fingerprint; then, if he either tells me « brandon/megatokyo » or scribbles it
on a piece of paper, I know that the « brandon » is my already established
naming root for him, not a name to be looked up in a global or almost global
name space. Of course, in a Mission Impossible plot my face and voice
recognition of Brandon at the party might be spoofed. But that’s the only
remaining theoretical problem I see with this use.
The only real bad news with subjectivity above is « voice and written » with
people you don’t already know.
For written: I’ve got my PGP fingerprint on my business card, as do many
other people. People already often clip their cards to documents they hand
out. This fingerprint is a fine naming root for the naming paths in the
document. Xerox has some fine technology for embedding machine readable
info unobtrusively in the normal ink printing patterns on paper, and one
can imagine a convention for embedding a name-root fingerprint in a company
letterhead.
For voice: If it’s in person, it can still be supplemented by a business
card, and often is. If it’s not in person, then it’s over an electronic
medium, which can carry other information as well.
Cheers,
–MarkM
From hal at finney.org Wed Mar 7 03:12:29 2001
From: hal at finney.org (hal at finney.org)
Date: Wed, 7 Mar 2001 00:12:29 -0800
Subject: Naming via SDSI
Message-ID: <200103070812.AAA26086@finney.org>
Wei’s original « three-services model » was like this:
> 1. name lookup service: maping user-friendly names/URLs to content-hash
> based ids
> 2. data location service: maping content-hash based ids to storage servers
> (network addresses and data transport protocols) that can deliver the data
> 3. data transport service: actually obtaining content from a storage
> server given its address and a content-hash based id
The current thread focuses on the first service, the one that does
name lookups.
However this model has (at least) two separate functions for the name
lookup, and perhaps it would be useful to split them. One function is
providing a « friendly name » for a document; and the other is allowing
documents to change without their name changing.
This second problem is somewhat specific to the assumption that content
hashes are the unforgeable identifiers for documents. With this approach,
any time a document is updated, its content hash and therefore its
identifier changes. Any content-hash based address will become obsolete
once this change has occured. Therefore having the name lookup service
is necessary so that you can find the latest version of the document.
However there are other ways to handle document revisions. This is part
of why Freenet has spawned its multiplicity of key (identifier) classes.
Freenet and OceanStore have identifiers which are based on cryptographic
keys and signatures. These have the same basic self-verification
properties as content hashes but they can allow documents to be updated
with the updates signed by the key.
If document changes are no longer an issue then the only remaining one
is friendly naming. There are a couple of things to note which make
this problem less severe.
First, only a very small percentage of the web pages on the net
presently have names friendly enough that they can be reasonably typed.
You might type www.cnn.com to get the headlines, but you won’t type
http://www.cnn.com/2001/TECH/space/03/06/mir.fungus.reut/index.html
to learn about the mutant bacteria threat from Mir. Instead your mail
reader will treat it as a link for you, or maybe you’ll cut and paste
it into your web browser.
Given this primitive level of automation, which is already necessary
for links to be passed around at all, a link with a 160 bit unforgeable
number can look like d787ef5c05460da6cf3d6aa1633655d8861e20f1 in hex or
like 14fvXAVGDabPPWqhYzZV2IYeIPE in a base-64 encoding, which is easy to
cut and paste; easier in fact than modern URLs which often span more than
one line and get forcibly line-wrapped by brain-damaged email software.
Second, of course if you are able to use HTML then the link isn’t even
seen and friendliness does not arise.
The remaining case is where people do want to type a URL. This will
often be where the URL appears in print, in a magazine or newspaper or
billboard; or via some other off-line medium like radio or tv. These URLs
have to be extremely short, essentially just one or two words, something
that people can remember.
This core of the problem remains hard, but note that it will mostly
involve businesses and large organizations, and most of the cases will be
advertising. Names will typically be some easy-to-remember variant of the
company’s name, or maybe a clever play on words involving its function.
It may well be that for this case a market-based registrar system will
work, with just a few large registrars handling the corporate business.
You’ll have .com, .org and a few others, as we have today. Widely used
software will hardwire these popular registries and it will be no easier
to overthrow them than it is to get people to ignore the top-level name
servers today.
The result would be a two-part scheme: a relatively limited and
inflexible name system for business trademarks, which identifies the
home pages of large organizations; and a completely ad hoc system
based on cryptographically self-authorizing, random-looking names for
everything else.
Hal
From blanu at uts.cc.utexas.edu Wed Mar 7 03:47:49 2001
From: blanu at uts.cc.utexas.edu (Brandon)
Date: Wed, 7 Mar 2001 02:47:49 -0600 (CST)
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127736-24108-2001.03.07-01.46.08–blanu#uts.cc.utexas.edu@ibiblio.org>
Message-ID: <Pine.OSF.4.21.0103070242310.15983-100000@moe.cc.utexas.edu>
Yes, I came to this conclusion earlier today.
Central authority and multiple competing authorities are really just pet
naming paths with an ellided well-known root key.
So pet names are really the best it can be.
From blanu at uts.cc.utexas.edu Wed Mar 7 03:51:36 2001
From: blanu at uts.cc.utexas.edu (Brandon)
Date: Wed, 7 Mar 2001 02:51:36 -0600 (CST)
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127736-24120-2001.03.07-03.16.00–blanu#uts.cc.utexas.edu@ibiblio.org>
Message-ID: <Pine.OSF.4.21.0103070248130.15983-100000@moe.cc.utexas.edu>
> http://www.cnn.com/2001/TECH/space/03/06/mir.fungus.reut/index.html
>
> Given this primitive level of automation, which is already necessary
> for links to be passed around at all, a link with a 160 bit unforgeable
> number can look like d787ef5c05460da6cf3d6aa1633655d8861e20f1 in hex or
> like 14fvXAVGDabPPWqhYzZV2IYeIPE in a base-64 encoding, which is easy to
> cut and paste; easier in fact than modern URLs which often span more than
> one line and get forcibly line-wrapped by brain-damaged email software.
The URL is still easier to communicate by voice than then hex or
base-64. I think that the importance of a voice-friendly encoding is often
overlooked because people underestimate the amount of URL information
communicate over the phone and in person. Of course, I don’t have any
particular ideas on how to convert 160-bit hashes into more voice-friendly
encodings, but the least you could do is use hex instead of base-64.
From lucas at worldos.com Wed Mar 7 12:22:23 2001
From: lucas at worldos.com (Lucas Gonze)
Date: Wed, 7 Mar 2001 12:22:23 -0500
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127943-24123-2001.03.07-03.51.53–lucas#gonze.com@ibiblio.org>
Message-ID: <NEBBJIHMMLKHEOPNOGHDKEMODEAA.lucas@worldos.com>
To get human-friendly IDs, it is not hard to have a namespace provider map names
to hashes.
IMHO unless the UN runs ICANN there is no solution to the political problem.
Always allow the user to specify a namespace (either implicitly or explicitly)
and the problem goes away.
– Lucas
> —–Original Message—–
> From: bounce-bluesky-127943 at ibiblio.org
> [mailto:bounce-bluesky-127943 at ibiblio.org]On Behalf Of Brandon
> Sent: Wednesday, March 07, 2001 3:52 AM
> To: Global-Scale Distributed Storage Systems
> Subject: Re: Naming via SDSI
>
>
>
> > http://www.cnn.com/2001/TECH/space/03/06/mir.fungus.reut/index.html
> >
> > Given this primitive level of automation, which is already necessary
> > for links to be passed around at all, a link with a 160 bit unforgeable
> > number can look like d787ef5c05460da6cf3d6aa1633655d8861e20f1 in hex or
> > like 14fvXAVGDabPPWqhYzZV2IYeIPE in a base-64 encoding, which is easy to
> > cut and paste; easier in fact than modern URLs which often span more than
> > one line and get forcibly line-wrapped by brain-damaged email software.
>
> The URL is still easier to communicate by voice than then hex or
> base-64. I think that the importance of a voice-friendly encoding is often
> overlooked because people underestimate the amount of URL information
> communicate over the phone and in person. Of course, I don’t have any
> particular ideas on how to convert 160-bit hashes into more voice-friendly
> encodings, but the least you could do is use hex instead of base-64.
>
>
>
> —
> You are currently subscribed to bluesky as: lucas at gonze.com
> For list information visit http://www.transarc.ibm.com/~ota/bluesky/
>
From hal at finney.org Wed Mar 7 13:01:32 2001
From: hal at finney.org (hal at finney.org)
Date: Wed, 7 Mar 2001 10:01:32 -0800
Subject: Naming via SDSI
Message-ID: <200103071801.KAA27444@finney.org>
Lucas Gonze, , writes:
> To get human-friendly IDs, it is not hard to have a namespace provider map names
> to hashes.
>
> IMHO unless the UN runs ICANN there is no solution to the political problem.
> Always allow the user to specify a namespace (either implicitly or explicitly)
> and the problem goes away.
But now the problem is, how to securely identify a namespace provider,
when you supply someone with a URL? Isn’t this the same problem?
You need either a friendly (user-readable) name for the namespace
provider, in which case more than one entity could claim to have that
name, or you need a cryptographically secure name, which will be long.
Hal
From lucas at worldos.com Wed Mar 7 13:29:34 2001
From: lucas at worldos.com (Lucas Gonze)
Date: Wed, 7 Mar 2001 13:29:34 -0500
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127943-24188-2001.03.07-13.04.39–lucas#gonze.com@ibiblio.org>
Message-ID: <NEBBJIHMMLKHEOPNOGHDAENCDEAA.lucas@worldos.com>
Hal said:
> You need either a friendly (user-readable) name for the namespace
> provider, in which case more than one entity could claim to have that
> name, or you need a cryptographically secure name, which will be long.
I think this boils down to the same insight embodied in webs of trust or SPKI,
which is that trust originates at the self. An individual has to make a leap of
faith based on the best data they can gather, but from then trusted parties can
certify new trusted parties.
The bootstrap step you are referring to doesn’t have to happen frequently.
Let’s say there would be a default namespace provider whose function is to map
friendly names for namespace providers to hashes. This default namespace
provider could be your ISP. On some level you would have to deal with the hash
during setup, just like you have to deal with IP settings for a new ISP account.
Bootstrap the entire process by getting a public key for your default namespace
provider. Verify this in the usual ways, e.g. by looking at the signature in a
magazine ad, by calling them on the phone, etc. You can have about as much
faith in this as you do in the setup data that your ISP provides.
The difference between this and DNS is that trust radiates outward from users,
rather than inward from the Root Server in Reston.
– Lucas
From hal at finney.org Wed Mar 7 13:44:50 2001
From: hal at finney.org (hal at finney.org)
Date: Wed, 7 Mar 2001 10:44:50 -0800
Subject: Naming via SDSI
Message-ID: <200103071844.KAA27744@finney.org>
Lucas writes:
> The bootstrap step you are referring to doesn’t have to happen frequently.
> Let’s say there would be a default namespace provider whose function is to map
> friendly names for namespace providers to hashes. This default namespace
> provider could be your ISP. On some level you would have to deal with the hash
> during setup, just like you have to deal with IP settings for a new ISP account.
What happens if my ISP and your ISP disagree about which namespace
provider gets a certain friendly-name, like .com or .biz? If this can’t
happen, could you explain why? And how does each ISP keep up to date
with namespace changes, and decide which namespace provider to honor in
the case of disputed name spaces? Many ISPs can barely keep the modems
running – will they have the manpower to take on this task?
> The difference between this and DNS is that trust radiates outward from users,
> rather than inward from the Root Server in Reston.
Well, in a sense trust does radiate outward from users in the
DNS. The only reason the root servers have power is because of
millions of users whose computers consult them to resolve names.
See http://www.youcann.org/instructions.html for how to change your
computer to consult different roots. If enough people did this, the
current root servers would lose power.
Hal
From lucas at worldos.com Wed Mar 7 14:37:02 2001
From: lucas at worldos.com (Lucas Gonze)
Date: Wed, 7 Mar 2001 14:37:02 -0500
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127943-24205-2001.03.07-13.48.03–lucas#gonze.com@ibiblio.org>
Message-ID: <NEBBJIHMMLKHEOPNOGHDIENEDEAA.lucas@worldos.com>
My point here is to say that the need to see hashes instead of friendly names
can be limited to setup time. After setup you are either specifying a namespace
(based on a chain of trust built out from the root server you have picked) or
using the implicit namespace of your root server. For example, your root server
might only define four or five name/hash mappings.
It’s interesting and probably even productive to work on whether it is a good to
idea to have a system that permits collisions, but I don’t mean to be commenting
on that here. Whether your root server is your ISP or some other party is also
a different set of issues. I am only addressing the problem of mapping friendly
names to hashes.
> Well, in a sense trust does radiate outward from users in the
> DNS. The only reason the root servers have power is because of
> millions of users whose computers consult them to resolve names.
> See http://www.youcann.org/instructions.html for how to change your
> computer to consult different roots. If enough people did this, the
> current root servers would lose power.
But there’s no way to specify the namespace within a domain reference. Changing
the root provider has to be dynamic to be useful. Otherwise you just end up
with a different dictator. You could probably hack a solution at the OS level
already, at least in Linux…
Aside from the mammoth installed base, I don’t see why DNS should remain the one
true method for mapping friendly names to IPs. Not having white space or
punctuation is unnecessarily primitive. Having to have a dot anything is fairly
silly as well. All the .foo means is the lookup source – there’s no conceptual
reason why these things should be mapped on a semantic level like com, biz,
aero, edu. That is just a historical artifact from the founding environment of
DNS.
– Lucas
From hal at finney.org Wed Mar 7 15:22:53 2001
From: hal at finney.org (hal at finney.org)
Date: Wed, 7 Mar 2001 12:22:53 -0800
Subject: Naming via SDSI
Message-ID: <200103072022.MAA28173@finney.org>
Lucas writes:
> My point here is to say that the need to see hashes instead of friendly names
> can be limited to setup time. After setup you are either specifying a namespace
> (based on a chain of trust built out from the root server you have picked) or
> using the implicit namespace of your root server. For example, your root server
> might only define four or five name/hash mappings.
I’m sorry, I’m still not understanding you. Would your system still
handle names like, say, www.microsoft.com? And your point is, that
in installing the .com name-server we would use a hash which securely
identifies that handler? I don’t see how that solves the problem, which
is to figure which .com handler we should choose, and more to the point,
how to be sure that the .com handler you chose is the same one I use.
Or putting it another way, what do you do when two namespace resolvers
claim to handle the same namespace? It doesn’t help us to have a secure
hash to the namespace resolver. That’s not the hard part of the problem.
One solution is to not have friendly-names for namespaces. In other words,
TLDs would be hashes. You’d have www.microsoft.14fvXAVGDabPPWqhYzZV2IYeIPE.
That last string would unambiguously designate a namespace resolver; there
would be no disputes possible, and everyone would use the same resolver.
The question is, can we get this level of clarity and security while keeping
friendly names for the namespaces.
Hal
From lucas at worldos.com Wed Mar 7 16:21:15 2001
From: lucas at worldos.com (Lucas Gonze)
Date: Wed, 7 Mar 2001 16:21:15 -0500
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127943-24228-2001.03.07-15.26.08–lucas#gonze.com@ibiblio.org>
Message-ID: <NEBBJIHMMLKHEOPNOGHDGENIDEAA.lucas@worldos.com>
> Would your system still
> handle names like, say, www.microsoft.com? And your point is, that
> in installing the .com name-server we would use a hash which securely
> identifies that handler? I don’t see how that solves the problem, which
> is to figure which .com handler we should choose, and more to the point,
> how to be sure that the .com handler you chose is the same one I use.
I would add one more level of indirection, to a namespace provider that maps the
name of the .com namespace provider to the hash of the .com namespace provider.
I would eliminate semantic landgrabs for concepts like « .com » and give namespace
providers proper names. So www.microsoft.com.realnames.myRootProvider is the
full path. myRootProvider is a hash/name mapping I entered manually, realnames
is a hash/name mapping provided by myRootProvider, com is a mapping provided by
realnames, etc.
As you move from right to left the likelyhood of a collision would go up.
myRootProvider must be canonical to the best of my ability to make it so.
realnames should be very dependable. com would be somewhat disputable.
microsoft would be fairly disputable.
The possibility of collisions is a good thing. For the most part there won’t be
collisions, because it’s in everyone’s interest to share most of this data. But
if there are conflicts between namespace providers just let users vote with
their feet.
> One solution is to not have friendly-names for namespaces. In other words,
> TLDs would be hashes. You’d have www.microsoft.14fvXAVGDabPPWqhYzZV2IYeIPE.
> That last string would unambiguously designate a namespace resolver; there
> would be no disputes possible, and everyone would use the same resolver.
quite cool! Ok, so add another level of indirection to get
www.microsoft.com.realnames.14fvXAVGDabPPWqhYzZV2IYeIPE.
and we are on more or less the same turf, except that I would allow for
gradations of disputability.
– Lucas
From hal at finney.org Wed Mar 7 17:19:18 2001
From: hal at finney.org (hal at finney.org)
Date: Wed, 7 Mar 2001 14:19:18 -0800
Subject: Naming via SDSI
Message-ID: <200103072219.OAA28801@finney.org>
Lucas writes:
> I would add one more level of indirection, to a namespace provider that maps the
> name of the .com namespace provider to the hash of the .com namespace provider.
> I would eliminate semantic landgrabs for concepts like « .com » and give namespace
> providers proper names. So www.microsoft.com.realnames.myRootProvider is the
> full path. myRootProvider is a hash/name mapping I entered manually, realnames
> is a hash/name mapping provided by myRootProvider, com is a mapping provided by
> realnames, etc.
In what format would you (or, more to the point, Microsoft) publish
this name? Is it literally in this form,
www.microsoft.com.realnames.myRootProvider? What does the string
myRootProvider mean to someone else?
And what is « realnames » here? That is a namespace provider, right?
What happens if two companies both claim to be responsible for the
« realnames » mapping? Does each different ISP decide which one to trust?
> As you move from right to left the likelyhood of a collision would go up.
> myRootProvider must be canonical to the best of my ability to make it so.
> realnames should be very dependable. com would be somewhat disputable.
> microsoft would be fairly disputable.
What do you mean by « collisions »? Is it that the .com provider might
give out two different mappings for microsoft.com? Surely it would not
do this.
Or are you worried about two different .com providers, both giving out
microsoft.com? If so, then surely realnames wouldn’t have given out two
different mappings for .com, right? So there must have been two different
realnames providers, both giving out mappings for .com. On this basis,
the only way I see collisions occuring is from the highest level, if two
different people are using different root providers, and so they might
have different .realnames providers, different .com providers, and so on.
But this would be a collision at the right, and would not increase in
probability as you go to the left. So I think I am misunderstanding you.
> The possibility of collisions is a good thing. For the most part there won’t be
> collisions, because it’s in everyone’s interest to share most of this data. But
> if there are conflicts between namespace providers just let users vote with
> their feet.
This was the suggestion made earlier, that we would just let people
compete for TLDs and let the market decide. I gave reasons [1] why I
thought this was a bad idea. I thought you were offering an alternative
to this. Maybe I was mistaken and you had the same idea all along.
[1] http://www.mail-archive.com/bluesky%40franklin.oit.unc.edu/msg00088.html
> > One solution is to not have friendly-names for namespaces. In other words,
> > TLDs would be hashes. You’d have www.microsoft.14fvXAVGDabPPWqhYzZV2IYeIPE.
> > That last string would unambiguously designate a namespace resolver; there
> > would be no disputes possible, and everyone would use the same resolver.
>
> quite cool! Ok, so add another level of indirection to get
> www.microsoft.com.realnames.14fvXAVGDabPPWqhYzZV2IYeIPE.
The problem with this solution is that it is not a friendly name. The
goal of this discussion is to see if there is a way to have TLD names be
friendly.
Hal
From md98-osa at nada.kth.se Wed Mar 7 17:32:22 2001
From: md98-osa at nada.kth.se (Oskar Sandberg)
Date: Wed, 7 Mar 2001 23:32:22 +0100
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127746-24228-2001.03.07-15.26.08–md98-osa#nada.kth.se@ibiblio.org>; from hal@finney.org on Wed, Mar 07, 2001 at 12:22:53PM -0800
References: <LYRIS-127746-24228-2001.03.07-15.26.08–md98-osa#nada.kth.se@ibiblio.org>
Message-ID: <20010307233222.A644@hobbex.localdomain>
On Wed, Mar 07, 2001 at 12:22:53PM -0800, hal at finney.org wrote:
<>
> One solution is to not have friendly-names for namespaces. In other words,
> TLDs would be hashes. You’d have www.microsoft.14fvXAVGDabPPWqhYzZV2IYeIPE.
> That last string would unambiguously designate a namespace resolver; there
> would be no disputes possible, and everyone would use the same resolver.
> The question is, can we get this level of clarity and security while keeping
> friendly names for the namespaces.
I don’t think so. After all, a multilayered name can be viewed as relative
path along a graph. In order for two parties to follow such a path and end
up at the same point, they have to start at the same point. For them to
start at the same point, then they either need to go by convention, or the
absolute identity of the starting point has to be given.
Making the absolute value « nice » is (AFAIK) impossible with current PK
crypto – and probably will remain since a PK algo where the public values
are chosen and the private values are derived from them is impossible
(what is to stop a second party from choosing the same PK value). And even
if it wasn’t impossible, it would make the whole layered name thing rather
pointless. So that leaves convention, and convention unavoidably means
both centralization of the service « root » and politics.
—
‘DeCSS would be fine. Where is it?’
‘Here,’ Montag touched his head.
‘Ah,’ Granger smiled and nodded.
Oskar Sandberg
md98-osa at nada.kth.se
From hal at finney.org Wed Mar 7 18:42:25 2001
From: hal at finney.org (hal at finney.org)
Date: Wed, 7 Mar 2001 15:42:25 -0800
Subject: Naming via SDSI
Message-ID: <200103072342.PAA29302@finney.org>
Oskar Sandberg writes:
> On Wed, Mar 07, 2001 at 12:22:53PM -0800, hal at finney.org wrote:
> > The question is, can we get this level of clarity and security while keeping
> > friendly names for the namespaces.
>
> I don’t think so. After all, a multilayered name can be viewed as relative
> path along a graph. In order for two parties to follow such a path and end
> up at the same point, they have to start at the same point. For them to
> start at the same point, then they either need to go by convention, or the
> absolute identity of the starting point has to be given.
Yes, that seems very true.
> Making the absolute value « nice » is (AFAIK) impossible with current PK
> crypto – and probably will remain since a PK algo where the public values
> are chosen and the private values are derived from them is impossible
> (what is to stop a second party from choosing the same PK value). And even
> if it wasn’t impossible, it would make the whole layered name thing rather
> pointless. So that leaves convention, and convention unavoidably means
> both centralization of the service « root » and politics.
I agree. Others have proposed alternatives to politics in market-based
mechanisms, but markets have trouble negotiating monopolies. There’s an
economic principle called « rent dissipation » in which companies will
expend almost the total value of a rent-producing asset in order to
acquire it. This is wasteful and inefficient.
Hal
From lucas at worldos.com Wed Mar 7 18:16:14 2001
From: lucas at worldos.com (Lucas Gonze)
Date: Wed, 7 Mar 2001 18:16:14 -0500
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127943-24265-2001.03.07-17.22.29–lucas#gonze.com@ibiblio.org>
Message-ID: <NEBBJIHMMLKHEOPNOGHDOENLDEAA.lucas@worldos.com>
> On this basis,
…this is the right interpretation of what I mean by collision.
> the only way I see collisions occuring is from the highest level
I think that we’re agreeing and using different language. Collisions are caused
on the right, but are visible on the left. Once a collision happens (which
happens as you move left), there are now different parties serving a namespace.
I’d add one refinement here, which is that collisions could die out if, e.g.,
the two different realnames providers agree on a mapping for .com.
> This was the suggestion made earlier, that we would just let people
> compete for TLDs and let the market decide. I gave reasons [1] why I
> thought this was a bad idea. I thought you were offering an alternative
> to this. Maybe I was mistaken and you had the same idea all along.
>
> [1] http://www.mail-archive.com/bluesky%40franklin.oit.unc.edu/msg00088.html
I read it. I agree that there are ambiguity, uncertainty and costs in doing
name lookups, and that is not ideal. Where I differ is that I think that the
question is not whether conflict is allowed but how to minimize the damage.
It’s hard to believe that China, Libya and the US will always be able to resolve
conflicts. At a certain size of the Internet you have to find ways to agree to
disagree. So my suggestion re: bootstrapping a friendly name mapping service is
intended to make the best of a bad situation, not to eliminate it, because I
don’t think it can be eliminated.
– Lucas
From md98-osa at nada.kth.se Wed Mar 7 19:43:34 2001
From: md98-osa at nada.kth.se (Oskar Sandberg)
Date: Thu, 8 Mar 2001 01:43:34 +0100
Subject: Naming via SDSI
In-Reply-To: <LYRIS-127746-24273-2001.03.07-18.45.55–md98-osa#nada.kth.se@ibiblio.org>; from hal@finney.org on Wed, Mar 07, 2001 at 03:42:25PM -0800
References: <LYRIS-127746-24273-2001.03.07-18.45.55–md98-osa#nada.kth.se@ibiblio.org>
Message-ID: <20010308014334.B1364@hobbex.localdomain>
On Wed, Mar 07, 2001 at 03:42:25PM -0800, hal at finney.org wrote:
> Oskar Sandberg writes:
> > On Wed, Mar 07, 2001 at 12:22:53PM -0800, hal at finney.org wrote:
> > > The question is, can we get this level of clarity and security while keeping
> > > friendly names for the namespaces.
> >
> > I don’t think so. After all, a multilayered name can be viewed as relative
> > path along a graph. In order for two parties to follow such a path and end
> > up at the same point, they have to start at the same point. For them to
> > start at the same point, then they either need to go by convention, or the
> > absolute identity of the starting point has to be given.
>
> Yes, that seems very true.
One hypothetical model for certain circumstances could be make this
graph a two-way such, so that two people could negoiate a starting point,
and go from there based on reversing their path to it. Something like:
Alice: You can get a Free dvd player at my site, fuckwaresux.truth
Bob: But I thought ICANN had decided .truth was solely the domain of large
media?
Alice: Yeah, but I’m not using ICANN’s root. Do you know microsoft’s
webpage under ICANN?
Bob: Yeah, it’s microsoft.com of course.
Alice: Well, it’s microsoft.criminal.orgs here, so you should find my site
at fuckwaresux.truth.orgs.criminal.microsoft.com
(from ICANN’s root -> ICANN’s com tld -> microsoft’s site -> Alice’s
criminal.orgs domain -> Alice’s orgs tld -> Alice’s root -> Alice’s truth
tld -> the Fuckware (Futile Unnecessary Control-Keeping softWARE) Sucks
site.)
Of course, this doesn’t work for several reasons. Firstly, it’s pretty
useless for tv ads and billboards where there is no room for negoiation,
and that is where it is needed. Secondly, there is really no such thing as
a two way link in cyberspace – the chances that microsoft would actually
have a reverse entry to criminal.orgs isn’t exactly very large. Thirdly,
it assumes you trust every step along the route, which is pretty nuts.
> > Making the absolute value « nice » is (AFAIK) impossible with current PK
> > crypto – and probably will remain since a PK algo where the public values
> > are chosen and the private values are derived from them is impossible
> > (what is to stop a second party from choosing the same PK value). And even
> > if it wasn’t impossible, it would make the whole layered name thing rather
> > pointless. So that leaves convention, and convention unavoidably means
> > both centralization of the service « root » and politics.
>
> I agree. Others have proposed alternatives to politics in market-based
> mechanisms, but markets have trouble negotiating monopolies. There’s an
> economic principle called « rent dissipation » in which companies will
> expend almost the total value of a rent-producing asset in order to
> acquire it. This is wasteful and inefficient.
I considers markets to be politics.
—
‘DeCSS would be fine. Where is it?’
‘Here,’ Montag touched his head.
‘Ah,’ Granger smiled and nodded.
Oskar Sandberg
md98-osa at nada.kth.se
From adam at cypherspace.org Wed Mar 7 21:16:15 2001
From: adam at cypherspace.org (Adam Back)
Date: Wed, 7 Mar 2001 22:16:15 -0400
Subject: distributed immutable namespace
Message-ID: <20010307221615.A6287@cypherpunks.ai>
I proposed on the crypto lists a few years back an idea
about namespaces to create a censor resistant namespace.
A namespace is a mapping from a human readable name into
some bit string (eg. ipv4 IP address, content hash,
location handle, etc).
The idea is to try to create a global namespace
collaboratively maintained by servers which audit each
others behavior and compensate for rogue behavior in
collaboration with client name server protocols.
The aim is to create a namespace where Names are strictly
first-come first served and persistent. Only the author
who registers a key at the time he reserves the name is
able to change the mapping. Local censorship and
revisionism is allowed, but only in local views of the
root namespace. Users browsers may be configured (or
even come pre-configured) to censor local names in the
domain they are distributed in. (Eg. a .cn filter, or a
.us filter).
But anyone should be able to get to the root unmodified
namespace, either by disabling the filters, or by using
some syntax which indicates that the name is in the root
immutable namespace.
There are two protocols involved:
1) Public Auditability – Use Merkle Authentication Trees
[*] to prevent revisionism on the part of namespace
servers. Namespace servers publish master hashes, users
and namespace servers audit each others adherence to the
global immutable root policy.
2) Revision Recovery – The client software should include
protocols to accept notices from other namespace servers
that detect a rogue namespace server. rogue namespace
servers responses pass through the revision recovery
protocol which works out if the repsonse is from a
modified part of the Authentication Tree, and if so
recovers the necessary original values from other
servers. Servers cache the original values of modified
sections of rogue servers Authentication Trees.
The combination of protocols in clients and servers
ensures that users can choose which filters they want to
subscribe to.
Companies may be satisfied with the subset of names that
survive the policies of a monopoly unaudited root server.
People who want more robust names can use the root
namespace explicitly.
For efficiency you probably want namespace servers to do
the auditing. You don’t want to audit every lookup back
to the root even thought it is relatively efficient.
Users can of course independently audit also.
Adam
[*] A Merkle Authentication Tree is basically a tree of
hashes to allow the efficient verification of a
particular leaf in the tree with log(n) queries. Imagine
a binary tree representing a namespace with names as the
leaf nodes. The parent of a leaf node is the hash of the
pair of names below it. The parent of that node with
it’s neighbor is the hash of it and the neighbor hash,
and so on up to the root which is the master hash of all
the hash of hashes of names down to the leaves.
Fortunately Merkle’s patent has expired.
From hal at finney.org Wed Mar 7 21:22:35 2001
From: hal at finney.org (hal at finney.org)
Date: Wed, 7 Mar 2001 18:22:35 -0800
Subject: distributed immutable namespace
Message-ID: <200103080222.SAA00621@finney.org>
Adam Back writes:
> The idea is to try to create a global namespace
> collaboratively maintained by servers which audit each
> others behavior and compensate for rogue behavior in
> collaboration with client name server protocols.
>
> The aim is to create a namespace where Names are strictly
> first-come first served and persistent. Only the author
> who registers a key at the time he reserves the name is
> able to change the mapping.
That’s an interesting idea, but isn’t there a danger that a first-come
first-served policy will result in someone writing a script to reserve
all one-letter, two-letter, three-letter words etc. as fast as he can
generate keys?
Hal
From orasis at acm.cs.umn.edu Wed Mar 7 15:36:11 2001
From: orasis at acm.cs.umn.edu (Justin Chapweske)
Date: Wed, 7 Mar 2001 20:36:11 +0000
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-127859-24295-2001.03.07-21.25.48–orasis#acm.cs.umn.edu@ibiblio.org>; from hal@finney.org on Wed, Mar 07, 2001 at 06:22:35PM -0800
References: <LYRIS-127859-24295-2001.03.07-21.25.48–orasis#acm.cs.umn.edu@ibiblio.org>
Message-ID: <20010307203610.C33945@go.cs.umn.edu>
>
> That’s an interesting idea, but isn’t there a danger that a first-come
> first-served policy will result in someone writing a script to reserve
> all one-letter, two-letter, three-letter words etc. as fast as he can
> generate keys?
>
You could slow it down with a « hash cash » type protocol where a person
would have to for example burn $100 worth of CPU cycles in order to
register a top(ish) level domain. This is currently how the real DNS
system works….maybe a very top level domain would cost $100M CPU cycles
to register to avoid a completely flat name space.
I love having these conversations on public mailing lists because you know
some bastard would patent these pretty obvious ideas otherwise.
—
Justin Chapweske, Lead Swarmcast Developer, OpenCola Inc.
http://www.sourceforge.net/projects/swarmcast/
From adam at cypherspace.org Wed Mar 7 21:43:21 2001
From: adam at cypherspace.org (Adam Back)
Date: Wed, 7 Mar 2001 22:43:21 -0400
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-126963-24295-2001.03.07-21.25.48–adam#cypherspace.org@ibiblio.org>; from hal@finney.org on Wed, Mar 07, 2001 at 06:22:35PM -0800
References: <LYRIS-126963-24295-2001.03.07-21.25.48–adam#cypherspace.org@ibiblio.org>
Message-ID: <20010307224321.B6287@cypherpunks.ai>
It would seem that someone could DoS the namespace as you
describe. It sounds like this attack would also work on
other namespace proposals, so is perhaps fairly general.
What could we do about it? Charge real ecash would be a
satisfying answer, but then we have boot strap problems,
as there isn’t one yet, and global e-cash systems robust
against being themselves censored are probably an even
harder problem.
Perhaps you could use hashcash to pay for your name. name
creations are infrequent enough that users could put up
with involve a reasonably expensive computation. Users of
names could also submit hashcash on the names they use so
that popular names get higher valued hashcash.
Also you could probably retain auditability if you allowed
policies of dropping the lowest valued names in event of a
flood.
None of this prevents attacks, just makes them a little
more expensive.
An is-a-person credential and a limited quota per-person
might be nice too, but that has it’s own boot strap
problems, and imports trust on the credential issuer.
Adam
On Wed, Mar 07, 2001 at 06:22:35PM -0800, hal at finney.org wrote:
> Adam Back writes:
> > The idea is to try to create a global namespace
> > collaboratively maintained by servers which audit each
> > others behavior and compensate for rogue behavior in
> > collaboration with client name server protocols.
>
> That’s an interesting idea, but isn’t there a danger that a first-come
> first-served policy will result in someone writing a script to reserve
> all one-letter, two-letter, three-letter words etc. as fast as he can
> generate keys?
From hal at finney.org Wed Mar 7 22:13:01 2001
From: hal at finney.org (hal at finney.org)
Date: Wed, 7 Mar 2001 19:13:01 -0800
Subject: distributed immutable namespace
Message-ID: <200103080313.TAA01318@finney.org>
Justin Capweske writes:
> You could slow it down with a « hash cash » type protocol where a person
> would have to for example burn $100 worth of CPU cycles in order to
> register a top(ish) level domain. This is currently how the real DNS
> system works….maybe a very top level domain would cost $100M CPU cycles
> to register to avoid a completely flat name space.
Hashcash at this scale makes me wince; all those wasted cycles…
Verisign bought Network Solutions for 21 BILLION dollars. That gave
them a big chunk of .com, .org and .net. Can you imagine burning
through that much hashcash?
Hashcash is rent dissipation in action. It doesn’t make economic sense
to sell assets for hashcash.
Better to set up some kind of global fund and let buyers pay real money,
then distribute the proceeds to everyone on earth. Or maybe use the
money to reduce global warming, or to save the whales. Anything is better
than flushing the money down the toilet, which is what hashcash does.
Hal
From retep at penguinpowered.com Wed Mar 7 22:46:09 2001
From: retep at penguinpowered.com (Peter Todd)
Date: Wed, 7 Mar 2001 22:46:09 -0500
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-127744-24299-2001.03.07-22.16.11–retep#penguinpowered.com@ibiblio.org>; from hal@finney.org on Wed, Mar 07, 2001 at 07:13:01PM -0800
References: <LYRIS-127744-24299-2001.03.07-22.16.11–retep#penguinpowered.com@ibiblio.org>
Message-ID: <20010307224609.B3677@petes.localdomain>
On Wed, Mar 07, 2001 at 07:13:01PM -0800, hal at finney.org wrote:
> Hashcash at this scale makes me wince; all those wasted cycles…
You know I heard a estimites that Seti at Home burns 18tons of fossile
fuel a *minute* Hashcash would do the same thing.
> Verisign bought Network Solutions for 21 BILLION dollars. That gave
> them a big chunk of .com, .org and .net. Can you imagine burning
> through that much hashcash?
>
> Hashcash is rent dissipation in action. It doesn’t make economic sense
> to sell assets for hashcash.
What do you mean by « rent dissipation in action »?
The big problem is hashcash is inflation. Mores law plus vastly
increasing supply. We’ll end up with insanely high inflation rates if
we’re not carefull, at least 100% every 18 months. (mores law)
Probably a few hundred times higher in practice.
Inflation causes another problem. Everything dealing with hashcash
must be able to automaticly adjust prices in realtime. If we end up
with 10% a day inflation rates, not impossible by any means, we’re
going to have to do that.
And finally inflation may become such a problem that we outgrow the
storage space available to store all this hashcash Compound interest
is a wonderfull thing you know…
> Better to set up some kind of global fund and let buyers pay real money,
> then distribute the proceeds to everyone on earth. Or maybe use the
> money to reduce global warming, or to save the whales. Anything is better
> than flushing the money down the toilet, which is what hashcash does.
But hashcash doesn’t need any centralized authority to work. Find
something else that doesn’t.
————– next part ————–
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.ibiblio.org/pipermail/bluesky/attachments/20010307/96c5d957/attachment.bin
From hal at finney.org Wed Mar 7 22:59:30 2001
From: hal at finney.org (hal at finney.org)
Date: Wed, 7 Mar 2001 19:59:30 -0800
Subject: distributed immutable namespace
Message-ID: <200103080359.TAA04178@finney.org>
Peter Todd writes:
> On Wed, Mar 07, 2001 at 07:13:01PM -0800, hal at finney.org wrote:
> > Hashcash is rent dissipation in action. It doesn’t make economic sense
> > to sell assets for hashcash.
>
> What do you mean by « rent dissipation in action »?
Let’s suppose that of the $21 billion that Network Solutions went for,
half was for .com, so it is worth $10 billion. Then when we make .com
available to the highest hashcash bidder, it makes sense for potential
bidders to waste up to $10 billion in cycles in order to generate their
hashcash. Anyone who wastes less than this won’t get it. Therefore there
will be $10 billion wasted in order to acquire an asset worth $10 billion.
Net benefit to society: zero.
Whereas if the $10 billion had gone into a fund to do something useful,
there would be a net positive benefit to society.
> > Better to set up some kind of global fund and let buyers pay real money,
> > then distribute the proceeds to everyone on earth. Or maybe use the
> > money to reduce global warming, or to save the whales. Anything is better
> > than flushing the money down the toilet, which is what hashcash does.
>
> But hashcash doesn’t need any centralized authority to work. Find
> something else that doesn’t.
Well, this could be a DEcentralized authority, similar to what Adam
was proposing. But authority it is.
Hal
From orasis at acm.cs.umn.edu Wed Mar 7 17:45:53 2001
From: orasis at acm.cs.umn.edu (Justin Chapweske)
Date: Wed, 7 Mar 2001 22:45:53 +0000
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-127859-24297-2001.03.07-21.43.33–orasis#acm.cs.umn.edu@ibiblio.org>; from adam@cypherspace.org on Wed, Mar 07, 2001 at 10:43:21PM -0400
References: <LYRIS-126963-24295-2001.03.07-21.25.48–adam#cypherspace.org@ibiblio.org> <LYRIS-127859-24297-2001.03.07-21.43.33–orasis#acm.cs.umn.edu@ibiblio.org>
Message-ID: <20010307224553.D33945@go.cs.umn.edu>
God I love synchronicity (same ideas at the same time).
>
> Perhaps you could use hashcash to pay for your name. name
> creations are infrequent enough that users could put up
> with involve a reasonably expensive computation. Users of
> names could also submit hashcash on the names they use so
> that popular names get higher valued hashcash.
>
—
Justin Chapweske, Lead Swarmcast Developer, OpenCola Inc.
http://www.sourceforge.net/projects/swarmcast/
From orasis at acm.cs.umn.edu Wed Mar 7 17:49:39 2001
From: orasis at acm.cs.umn.edu (Justin Chapweske)
Date: Wed, 7 Mar 2001 22:49:39 +0000
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-127859-24299-2001.03.07-22.16.11–orasis#acm.cs.umn.edu@ibiblio.org>; from hal@finney.org on Wed, Mar 07, 2001 at 07:13:01PM -0800
References: <LYRIS-127859-24299-2001.03.07-22.16.11–orasis#acm.cs.umn.edu@ibiblio.org>
Message-ID: <20010307224939.E33945@go.cs.umn.edu>
>
> Hashcash at this scale makes me wince; all those wasted cycles…
>
Very good point. So what we really need is a non-profit DNS where the
non-profit organization technically has no control over the DNS system.
This is theoretically possible?
—
Justin Chapweske, Lead Swarmcast Developer, OpenCola Inc.
http://www.sourceforge.net/projects/swarmcast/
From adam at cypherspace.org Wed Mar 7 23:48:51 2001
From: adam at cypherspace.org (Adam Back)
Date: Thu, 8 Mar 2001 00:48:51 -0400
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-126963-24306-2001.03.07-23.02.45–adam#cypherspace.org@ibiblio.org>; from hal@finney.org on Wed, Mar 07, 2001 at 07:59:30PM -0800
References: <LYRIS-126963-24306-2001.03.07-23.02.45–adam#cypherspace.org@ibiblio.org>
Message-ID: <20010308004851.A35061@cypherpunks.ai>
On Wed, Mar 07, 2001 at 07:59:30PM -0800, hal at finney.org wrote:
> > > Better to set up some kind of global fund and let buyers pay real money,
> > > then distribute the proceeds to everyone on earth. Or maybe use the
> > > money to reduce global warming, or to save the whales. Anything is better
> > > than flushing the money down the toilet, which is what hashcash does.
> >
> > But hashcash doesn’t need any centralized authority to work. Find
> > something else that doesn’t.
>
> Well, this could be a DEcentralized authority, similar to what Adam
> was proposing. But authority it is.
You would want the ability to buy names strongly
anonymously; so you want a payer anonymous ecash system
which you can pay for with credit cards, or perhaps with
checks as credit cards have too high a fraud rate to
risk selling strongly anonymous ecash for.
In the short term the payment system would be the system
weak point because it’s an identifiable central server.
Censors would close down the mint, much as the RIAA is
having an easy job getting courts to rule that Napster’s
central servers have to shut down.
Even though ecash to pay for names in a namespace is
several steps removed from content some of which RIAA
may dispute, I doubt a court will feel this any reason
not to rule that the mint be shut down. Perhaps there
is even a precedent of sorts in the MPAA decision
ruling that links to DeCSS source code should be
removed.
Either way we have a problem with DoS against both the
namespace and the distributed content store itself.
It may be interesting to investigate how well the name
resolution, auditability and revision recovery protocols
can be made to scale with number of name servers and
percentage of modified values.
Hashcash may burn resources, but it appears to be all
that we have in the way of distributed DoS resistance.
Also hashcash would typically burn resources that would
be revving away idle anyway (modulo the difference in
power saving state some hardware may switch to if the
processor is idle). Unless it got really heated and
people started building expensive custom hardware purely
to escalate the race on desirable namespace. Another
risk for hashcash apart from custom hardware races is
virii — imagine a virus or worm with a payload which
computed hashcash collisions.
If names are richer there may be less pressure to land
grab names to re-sell. Internet domains are basically a
single word in .{com,net,org}; if the name space had an
arbitrary Top Level Domains and 2nd level domain like
namespace it would be easier to find nice sounding
names.
Whether or not owning a names gives ownership of all
names which contain it as a left substring is another
question. In eternity USENET http://foo.eternity/
could have completely different ownership to
http://foo.eternity/bar/, and there was no support for a
link between them. The ownership of foo.eternity just
gave the ability to choose which sub-URLs to link from
the index.html file. Other people could have sub-URLs
which you don’t link to (or even which you do), either
way authorship signatures describe authorship, and
hypertext references provide links. I did think
eternity USENET style names might be less vulnerable to
land grabbing because the owner of the virtual domain
name doesn’t automatically own URLs under that. But
perhaps that’s undesirable anyway because it violates
expectations that the URLs which look like they are on
the same virtual domain are somehow under related
ownership.
Adam
From md98-osa at nada.kth.se Thu Mar 8 08:06:19 2001
From: md98-osa at nada.kth.se (Oskar Sandberg)
Date: Thu, 8 Mar 2001 14:06:19 +0100
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-127746-24293-2001.03.07-21.16.42–md98-osa#nada.kth.se@ibiblio.org>; from adam@cypherspace.org on Wed, Mar 07, 2001 at 10:16:15PM -0400
References: <LYRIS-127746-24293-2001.03.07-21.16.42–md98-osa#nada.kth.se@ibiblio.org>
Message-ID: <20010308140619.G800@hobbex.localdomain>
On Wed, Mar 07, 2001 at 10:16:15PM -0400, Adam Back wrote:
<>
> There are two protocols involved:
>
> 1) Public Auditability – Use Merkle Authentication Trees
> [*] to prevent revisionism on the part of namespace
> servers. Namespace servers publish master hashes, users
> and namespace servers audit each others adherence to the
> global immutable root policy.
Sorry if I’m being stupid here, but what exactly is the tree
authenticating? It seems to me that MATs need to be static, which a
namespace would obviously not be.
—
‘DeCSS would be fine. Where is it?’
‘Here,’ Montag touched his head.
‘Ah,’ Granger smiled and nodded.
Oskar Sandberg
md98-osa at nada.kth.se
From adam at cypherspace.org Thu Mar 8 13:10:28 2001
From: adam at cypherspace.org (Adam Back)
Date: Thu, 8 Mar 2001 14:10:28 -0400
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-126963-24407-2001.03.08-08.04.05–adam#cypherspace.org@ibiblio.org>; from Oskar Sandberg on Thu, Mar 08, 2001 at 02:06:19PM +0100
References: <LYRIS-127746-24293-2001.03.07-21.16.42–md98-osa#nada.kth.se@ibiblio.org> <LYRIS-126963-24407-2001.03.08-08.04.05–adam#cypherspace.org@ibiblio.org>
Message-ID: <20010308141028.A84590@cypherpunks.ai>
On Thu, Mar 08, 2001 at 02:06:19PM +0100, Oskar Sandberg wrote:
> > 1) Public Auditability – Use Merkle Authentication Trees
> > [*] to prevent revisionism on the part of namespace
> > servers. Namespace servers publish master hashes, users
> > and namespace servers audit each others adherence to the
> > global immutable root policy.
>
> Sorry if I’m being stupid here, but what exactly is the tree
> authenticating? It seems to me that MATs need to be static, which a
> namespace would obviously not be.
You publish a list of master hashes, say one per day, each
hashing the days master and the previous days master hash.
If you care you can get the server to commit to names blind
so that you can then prove it excluded you. (eg. hash name
you would submit with random nonce, get server to sign that
random number hashed with todays master hash, then submit
the real name and nonce so the server can verify. If the
name does not show up in the next days hash tree, you have
proof that it excluded you in the form of the signed
receipt, on presentation of that receipt the server will
either add you to the current tree or be considered t ohave
cheated.
Adam
From ian at octayne.com Thu Mar 8 13:32:50 2001
From: ian at octayne.com (Ian Clarke)
Date: Thu, 8 Mar 2001 10:32:50 -0800
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-127737-24297-2001.03.07-21.43.33–lists#octayne.com@ibiblio.org>; from adam@cypherspace.org on Wed, Mar 07, 2001 at 10:43:21PM -0400
References: <LYRIS-126963-24295-2001.03.07-21.25.48–adam#cypherspace.org@ibiblio.org> <LYRIS-127737-24297-2001.03.07-21.43.33–lists#octayne.com@ibiblio.org>
Message-ID: <20010308103250.E1618@technic.uprizer.com>
On Wed, Mar 07, 2001 at 10:43:21PM -0400, Adam Back wrote:
> Perhaps you could use hashcash to pay for your name. name
> creations are infrequent enough that users could put up
> with involve a reasonably expensive computation. Users of
> names could also submit hashcash on the names they use so
> that popular names get higher valued hashcash.
This same issue came up on the Freenet mailing list a while back. We
weren’t happy with hashcash since it would make your ability to publish
information proportional to the speed of your PC (which is roughly
proportional to the size of your wallet), and we didn’t like that at a
philisophical level.
I suggested a concept called « Think Cash », here is a copy of a document
I wrote to describe the idea (note that this is really just an
exploration of the problem more than a solution):
—
One of the core problems with the Internet today, and its open trusting
nature, is that of Denial of Service or DOS attacks. Basically, this is
the computer equivalent of making it impossible for someone to use their
phone by phoning them once a minute, 24 hours a day, 365 days a year
automatically. Of course, with phones, people who did this would be cut
off very quickly, however this is not so easy with the Internet.
Further, tools such as Freenet which aim to protect people’s anonymity,
could compound this problem even more in some circumstances. (It is
worth noting that Freenet’s architecture does make DOS attacks less
damaging by avoiding centralized control). One obvious example of DOS
attacks is « Spam » or unsolicited email. Here people send out thousands
or millions of emails to people, generally advertising a product or
service that only a tiny fraction of the recepients will be interested
in.
Ways to address the problem
1. Increased regulation
One approach is increased regulation of the Internet, making it easier
to detect and remove those mounting DOS attacks. The problem with this
is that many people (myself included) feel that the real value of the
Internet is as a forum for free speech, and the tools developed to
counter DOS attacks could easily be turned against other Internet users
to censor them. In this case, the cure would be much worse than the
disease.
2. Hash cash
The second approach is to make it too costly for people to mount a DOS
attack, but where the cost of normal internet usage remains
insignificant. Hash cash is one solution where a user is forced to
perform a time-consuming (and therefore money consuming) calculation,
before submitting something to the system (such as sending an email or
transmitting an IP packet to a given IP address). This is quite
straight-forward to implement, however its usefulness is unclear.
Firstly it would create a bias against users of slower computers.
Secondly, even if it took 1 minute to perform the calculation nescessary
to send an email, you could still send a considerable amount of email in
a 24 hour period.
3. Think cash
A more sophisticated idea, which (as far as I am aware) has not been
considered prior to my suggesting it on one of the Freenet Project
mailing lists several months ago, is to force « a human« to do a small
amount of work, which only a human could do, before submitting each
piece of information. The aim is to make it impossible to automate the
task. Thinking of a way to do this is not easy – any such mechanism
would need the following properties:
1. Only a human should be able to perform the task or test
2. A computer should be able to create a test automatically
3. A computer should be able to judge the results of the test
Some possible approaches
There are a number of general areas where we could look for such a test.
Of particular interest to us should be tasks which humans find easy, but
which machines find difficult. Examples include image recognition and
speech recognition. The problem here is not so much creating the tests
(requirement 2), but judging them (requirement 3). There is the further
constraint that each test must have enough possible answers so that a
computer could not simply attempt all of them.
Testing for intelligence
One particular line of enquiry which caught my attention was the « Turing
Test ». Alan Turing was a British cryptographer who helped to break
German cyphers during the second world war. He also had a keen interest
in the concept of machine intelligence, and in particular, how to test a
machine for intelligence. His idea, what we now call the Turing test,
was clever in that it largely evaded the question of what intelligence
actually was. A simplified version of the actual test would work like
this. Someone would have a conversation (using a keyboard and screen,
much like IRC) with what could be either another person, or a computer
pretending to be a person. They would have to decide whether they were
talking to a human or a machine. This test would be repeated, and if
they got it wrong around half of the time, then the machine could be
regarded as being intelligent. This approach may suggest a solution to
the dilemma outlined above.
The seeds of a solution
I started to think about whether it would be possible to create a system
where all the users, while being tested by the system, were actually
testing each-other too. Each user might be asked to provide an answer to
a question which will demonstrate their intelligence, to provide a
question which will test someone elses intelligence, and to give an
opinion as to the answers given by a number of other people to several
questions. Failure to do any of these things to the best of their
ability may result in their submission not being accepted.
Remaining issues
Of course, there are still many details to be worked out, how can the
above system be built so as to make abuse impossible? What if a computer
made so many submissions that it saturated the system, and could
validate its own submissions as being correct?
None the less, at least this suggests that a robust think-cash mechanism
is a possibility. As the threat of malicious attacks on the Internet get
more and more serious, people may be forced to adopt a mechanism such as
this.
————– next part ————–
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.ibiblio.org/pipermail/bluesky/attachments/20010308/1eb22df3/attachment.bin
From hal at finney.org Thu Mar 8 13:41:14 2001
From: hal at finney.org (hal at finney.org)
Date: Thu, 8 Mar 2001 10:41:14 -0800
Subject: distributed immutable namespace
Message-ID: <200103081841.KAA25549@finney.org>
Another question on Adam’s proposal:
> The idea is to try to create a global namespace
> collaboratively maintained by servers which audit each
> others behavior and compensate for rogue behavior in
> collaboration with client name server protocols.
Given that there are multiple servers, how do you deal with database
consistency? Specifically, what if two different servers both give
out the same name, to different people? Don’t you ultimately need
a single server, or at least a global tightly-coupled database with
locking semantics? How efficient can that be?
Even if you design it to do this, how do you resolve disputes when two
servers both claim to have followed the rules but both somehow have
given out the same name? Now you need audit logs on your global
database so you can figure out which one is wrong.
I’m afraid that such a system would be limited in the volume of names
that it could handle. Maybe it would be OK if we envisioned it being
used for a relatively small number of TLDs, and then each of those
operates its own name service.
Hal
From orasis at acm.cs.umn.edu Thu Mar 8 07:50:50 2001
From: orasis at acm.cs.umn.edu (Justin Chapweske)
Date: Thu, 8 Mar 2001 12:50:50 +0000
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-127859-24461-2001.03.08-13.26.07–orasis#acm.cs.umn.edu@ibiblio.org>; from ian@octayne.com on Thu, Mar 08, 2001 at 10:32:50AM -0800
References: <LYRIS-127737-24297-2001.03.07-21.43.33–lists#octayne.com@ibiblio.org> <LYRIS-127859-24461-2001.03.08-13.26.07–orasis#acm.cs.umn.edu@ibiblio.org>
Message-ID: <20010308125050.I33945@go.cs.umn.edu>
This is very similar to what mindpixel does. Its cool, check it out:
http://www.mindpixel.com/
>
> The seeds of a solution
> I started to think about whether it would be possible to create a system
> where all the users, while being tested by the system, were actually
> testing each-other too. Each user might be asked to provide an answer to
> a question which will demonstrate their intelligence, to provide a
> question which will test someone elses intelligence, and to give an
> opinion as to the answers given by a number of other people to several
> questions. Failure to do any of these things to the best of their
> ability may result in their submission not being accepted.
>
> Remaining issues
> Of course, there are still many details to be worked out, how can the
> above system be built so as to make abuse impossible? What if a computer
> made so many submissions that it saturated the system, and could
> validate its own submissions as being correct?
> None the less, at least this suggests that a robust think-cash mechanism
> is a possibility. As the threat of malicious attacks on the Internet get
> more and more serious, people may be forced to adopt a mechanism such as
> this.
Content-Description: footer
> —
> You are currently subscribed to bluesky as: orasis at acm.cs.umn.edu
> For list information visit http://www.transarc.ibm.com/~ota/bluesky/
—
Justin Chapweske, Lead Swarmcast Developer, OpenCola Inc.
http://www.sourceforge.net/projects/swarmcast/
From adam at cypherspace.org Thu Mar 8 14:11:59 2001
From: adam at cypherspace.org (Adam Back)
Date: Thu, 8 Mar 2001 15:11:59 -0400
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-126963-24470-2001.03.08-13.44.34–adam#cypherspace.org@ibiblio.org>; from hal@finney.org on Thu, Mar 08, 2001 at 10:41:14AM -0800
References: <LYRIS-126963-24470-2001.03.08-13.44.34–adam#cypherspace.org@ibiblio.org>
Message-ID: <20010308151159.B87951@cypherpunks.ai>
On Thu, Mar 08, 2001 at 10:41:14AM -0800, hal at finney.org wrote:
> Another question on Adam’s proposal:
> > The idea is to try to create a global namespace
> > collaboratively maintained by servers which audit each
> > others behavior and compensate for rogue behavior in
> > collaboration with client name server protocols.
>
> Given that there are multiple servers, how do you deal with database
> consistency? Specifically, what if two different servers both give
> out the same name, to different people? Don’t you ultimately need
> a single server, or at least a global tightly-coupled database with
> locking semantics? How efficient can that be?
You need a single server to be responsible for each chunk
of namespace as you describe. Other name servers could
cache responses, audit other servers, and keep information
to be able to undo modifications rogue servers make.
> I’m afraid that such a system would be limited in the volume of names
> that it could handle. Maybe it would be OK if we envisioned it being
> used for a relatively small number of TLDs, and then each of those
> operates its own name service.
So with hierarchical namespaces like DNS, the risk is that
the nameserver with control of a subdomain can censor or
be coerced into censoring a name. My suggestion isn’t to
make it more distributed, but to detect and have a
protocol on the client and other servers which allows
modifications to be undone.
Scalability would be related to DNS, lots of caching helps
scalability.
Adam
From mfreed at MIT.EDU Thu Mar 8 21:00:32 2001
From: mfreed at MIT.EDU (Michael J Freedman)
Date: Thu, 08 Mar 2001 21:00:32 -0500
Subject: distributed immutable namespace: Think Cash
In-Reply-To: <LYRIS-126372-24461-2001.03.08-13.26.07–mfreed#mit.edu@ibi blio.org>
References: <LYRIS-127737-24297-2001.03.07-21.43.33–lists#octayne.com@ibiblio.org>
Message-ID: <200103090201.VAA06484@melbourne-city-street.MIT.EDU>
At 10:32 AM 3/8/2001 -0800, you wrote:
>This same issue came up on the Freenet mailing list a while back. We
>weren’t happy with hashcash since it would make your ability to publish
>information proportional to the speed of your PC (which is roughly
>proportional to the size of your wallet), and we didn’t like that at a
>philisophical level.
This goes back to the question as to the particular need for POWs such as
hash cash. Our contention is that for resources which become only
temporarily used — such as bandwidth (Gnutella), CPUs cycles, and caches
(Freenet) — that you don’t need a congestion management mechanism *at all
times*. Rather, you only need to dynamically change your « publishing »
(querying, etc.) requirements based on the current load of your system.
That is, as your system gets congested due to temporary load, raise the
amount of required payments dynamically. We refer to this as an
« accountability slider » in the O’Reilly P2P book.
If your resources are cumulatively used — such as disk space in permanent
storage systems (Free Haven) — then enforcing micropayment requirements
when you start getting congested is *already too late.* Thus, for these
types of systems, our contention (in the micropayment world) you need ’em
all the time.
I have some concerns as to the real viability of « Think Cash » in a
distributed P2P environment.
>task. Thinking of a way to do this is not easy – any such mechanism
>would need the following properties:
>
> 1. Only a human should be able to perform the task or test
> 2. A computer should be able to create a test automatically
> 3. A computer should be able to judge the results of the test
>
>
>speech recognition. The problem here is not so much creating the tests
>(requirement 2), but judging them (requirement 3). There is the further
>constraint that each test must have enough possible answers so that a
>computer could not simply attempt all of them.
>
First of all, I think this is actually an incredibly difficult problem
which you suggest. Let’s describe this in terms of a normal interactive
protocol (IP) framework.
You are suggesting that your proof system has a prover (P) and verifier
(V), such that after the IP, V should only accept (with probability
1-\epsilon, 1-constant, whatever) if P \element {humans}.
Getting this (completeness). and soundness (no cheating) with small enough
false positives and false negatives is, my opinion, going to be a very hard
problem.
The issue is compounded that you are working in a distributed peer-to-peer
environment. Generally, we would like protocols to be simple,
well-understood, and light-weight. This type of system would likely be
very complex, hard to formalize, and thus hard to really analyze.
You mention the Turing test. Unfortunately, V in that system is a human,
not a computer. The ability for computers to perform natural language
processing is fairly well along, but it’s definately *not* a light-weight
operation. But language understanding is much further back, especially if
your language domain is fairly large. For example, MIT LCS’s Spoken
Language Systems group has good working systems for language understanding,
but each system only handles a small « problem: » the weather, driving
directions, airplane reservations, etc.
>The seeds of a solution
>I started to think about whether it would be possible to create a system
>where all the users, while being tested by the system, were actually
>testing each-other too. Each user might be asked to provide an answer to
>a question which will demonstrate their intelligence, to provide a
>question which will test someone elses intelligence, and to give an
>opinion as to the answers given by a number of other people to several
>questions. Failure to do any of these things to the best of their
>ability may result in their submission not being accepted.
This proposals layering many two-way interactions in the « intelligence
testing » protocol. It also suggests that users — who use the system with
widely varying educational backgrounds, computer literacy, cultures,
comprehension of the technologies involved, etc. — to « judge » each other’s
intelligence. And then make operational decisions based on their limited
interaction and limited understanding of each other.
Make the problems too hard, and your false negatives go way up. Make the
problems too each, and I’ll write an automated simulator that’ll convince
most of them. Your false positives go up. Throw some machine learning in
there? Then you get away from the « user-interaction » model and you added
lots of complexity.
When you aren’t formalizing the problem — like hash cash, client puzzles,
Naor/Dwork’s paying for processing — you aren’t establishing complexity
classes, in any sense, for the issues at hand.
>Remaining issues
>Of course, there are still many details to be worked out, how can the
>above system be built so as to make abuse impossible? What if a computer
>made so many submissions that it saturated the system, and could
>validate its own submissions as being correct?
See above.
>None the less, at least this suggests that a robust think-cash mechanism
>is a possibility. As the threat of malicious attacks on the Internet get
>more and more serious, people may be forced to adopt a mechanism such as
>this.
I fear « robust » is something that hardly applies.
Your goal might be an admirable one, but I am very hesitant to think that a
« Think Cash » system as you describe is realizable in the near- to medium-
future.
–mike
—–
« Not all those who wander are lost. » mfreed at mit.edu
From ian at freenetproject.org Fri Mar 9 00:18:04 2001
From: ian at freenetproject.org (Ian Clarke)
Date: Thu, 8 Mar 2001 21:18:04 -0800
Subject: Think cash
In-Reply-To: <LYRIS-127737-24547-2001.03.08-21.02.22–lists#octayne.com@ibiblio.org>; from mfreed@MIT.EDU on Thu, Mar 08, 2001 at 09:00:32PM -0500
References: <LYRIS-126372-24461-2001.03.08-13.26.07–mfreed#mit.edu@ibi blio.org> <LYRIS-127737-24547-2001.03.08-21.02.22–lists#octayne.com@ibiblio.org>
Message-ID: <20010308211804.C1313@technic.uprizer.com>
On Thu, Mar 08, 2001 at 09:00:32PM -0500, Michael J Freedman wrote:
> I have some concerns as to the real viability of « Think Cash » in a
> distributed P2P environment.
No interesting problem is ever easy.
> First of all, I think this is actually an incredibly difficult problem
> which you suggest.
Again, no interesting problem is ever easy 😉
> You mention the Turing test. Unfortunately, V in that system is a human,
> not a computer. The ability for computers to perform natural language
> processing is fairly well along, but it’s definitely *not* a light-weight
> operation. But language understanding is much further back, especially if
> your language domain is fairly large. For example, MIT LCS’s Spoken
> Language Systems group has good working systems for language understanding,
> but each system only handles a small « problem: » the weather, driving
> directions, airplane reservations, etc.
Yes, but if you read on you see that I am actually talking about setting
up the system in such a manner that the humans in the system actually
test each other, and are incentivised to do a good job. Again, this
would be difficult to arrange, but not necessarily impossible.
> >The seeds of a solution
> >I started to think about whether it would be possible to create a system
> >where all the users, while being tested by the system, were actually
> >testing each-other too. Each user might be asked to provide an answer to
> >a question which will demonstrate their intelligence, to provide a
> >question which will test someone else’s intelligence, and to give an
> >opinion as to the answers given by a number of other people to several
> >questions. Failure to do any of these things to the best of their
> >ability may result in their submission not being accepted.
>
> This proposals layering many two-way interactions in the « intelligence
> testing » protocol. It also suggests that users — who use the system with
> widely varying educational backgrounds, computer literacy, cultures,
> comprehension of the technologies involved, etc. — to « judge » each other’s
> intelligence.
As someone who has spent several years studying Artificial Intelligence
(and being largely disappointed by it), one of the most interesting
things is that the hardest things for a computer to do, tend to be the
easiest things for a human to do, and the converse is also true. I
don’t think these exchanges would need to test anyone’s computer
literacy, or educational qualifications. As for cultural differences,
that is hardly a problem on the Internet of today! (How many of you are
*not* white middle-class males?). Again, I think that you are judging
this too harshly, I am not saying that this would be easy, or even
possible, but it is fun to think about it, and who knows, maybe
something useful will emerge.
> Make the problems too hard, and your false negatives go way up. Make the
> problems too each, and I’ll write an automated simulator that’ll convince
> most of them. Your false positives go up. Throw some machine learning in
> there? Then you get away from the « user-interaction » model and you added
> lots of complexity.
This is the nice thing about the « reflected turing test » approach, it is
a difficult test, but the computer doesn’t really have to do the testing
(although it does have to arrange things carefully).
> When you aren’t formalizing the problem — like hash cash, client puzzles,
> Naor/Dwork’s paying for processing — you aren’t establishing complexity
> classes, in any sense, for the issues at hand.
I am not sure what you mean here, but it sounds like you are saying that
there is no point in speculation. If that is the case, how do you ever
think of anything original or interesting?
> >None the less, at least this suggests that a robust think-cash mechanism
> >is a possibility. As the threat of malicious attacks on the Internet get
> >more and more serious, people may be forced to adopt a mechanism such as
> >this.
>
> I fear « robust » is something that hardly applies.
Why not? Just because something is difficult doesn’t mean it is
impossible. Freenet showed me that.
> Your goal might be an admirable one, but I am very hesitant to think that a
> « Think Cash » system as you describe is realizable in the near- to medium-
> future.
So much pessimism in one so young…. 😉
Ian.
————– next part ————–
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.ibiblio.org/pipermail/bluesky/attachments/20010308/74ed053d/attachment.bin
From mfreed at MIT.EDU Fri Mar 9 01:21:10 2001
From: mfreed at MIT.EDU (Michael J Freedman)
Date: Fri, 09 Mar 2001 01:21:10 -0500
Subject: Think cash
In-Reply-To: <LYRIS-126372-24629-2001.03.09-00.11.32–mfreed#mit.edu@ibi blio.org>
References: <LYRIS-127737-24547-2001.03.08-21.02.22–lists#octayne.com@ibiblio.org>
Message-ID: <200103090621.BAA08597@melbourne-city-street.MIT.EDU>
At 09:18 PM 3/8/2001 -0800, Ian Clarke wrote:
>> Make the problems too hard, and your false negatives go way up. Make the
>> problems too each, and I’ll write an automated simulator that’ll convince
>> most of them. Your false positives go up. Throw some machine learning in
>> there? Then you get away from the « user-interaction » model and you added
>> lots of complexity.
>
>This is the nice thing about the « reflected turing test » approach, it is
>a difficult test, but the computer doesn’t really have to do the testing
>(although it does have to arrange things carefully).
>
>
>> When you aren’t formalizing the problem — like hash cash, client puzzles,
>> Naor/Dwork’s paying for processing — you aren’t establishing complexity
>> classes, in any sense, for the issues at hand.
>
>I am not sure what you mean here, but it sounds like you are saying that
>there is no point in speculation. If that is the case, how do you ever
>think of anything original or interesting?
What I just meant is that these other solutions are based on computational
problems that are accepted as « hard » (assuming that one-way functions
exist).
When you start requiring user interaction in a different manner, you start
added a lot of uncertainty into your models. Various sociological effects
come up that may be much less predictable. You’re okay if your system
users understand what it’s trying to do, but if this is made for the
average end-user (I think that’s a goal of a lot of p2p systems), I’d try
to do the following:
tcsh% ./ run-bot « c00ld00d »
tcsh% [c00ld00d launched…]
tcsh% [c00ld00d finds user « Newbie »]
c00ld00d: sends you [Newbie] a message: « Hey!!! How r u?!? can u click
OK for me and i’ll click OK for u? Cool? THX!!!!! »
>> >None the less, at least this suggests that a robust think-cash mechanism
>> >is a possibility. As the threat of malicious attacks on the Internet get
>> >more and more serious, people may be forced to adopt a mechanism such as
>> >this.
>>
>> I fear « robust » is something that hardly applies.
>
>Why not? Just because something is difficult doesn’t mean it is
>impossible. Freenet showed me that.
I apologize if I came across too strongly. I think what Freenet is trying
to achieve is really good, and that a number of really smart people are
working towards similar ends. One of the whole reasons for this mailing
lists is to discuss our thoughts.
The only reason I brought up these points is to try and emphasize some
problems in building complex systems. It’s hard. I think we are all aware
of that.
I think we’re starting to see some second systems-type effects: we’re
trying to layer handwaved, complex solutions over handwaved, complex
systems. It’s always been an endemic problem with system design. =)
Hopefully, we can find some good answers to some of these hard problems.
Thanks,
–mike
—–
« Not all those who wander are lost. » mfreed at mit.edu
From md98-osa at nada.kth.se Fri Mar 9 02:03:49 2001
From: md98-osa at nada.kth.se (Oskar Sandberg)
Date: Fri, 9 Mar 2001 08:03:49 +0100
Subject: Think cash
In-Reply-To: <LYRIS-127746-24629-2001.03.09-00.11.32–md98-osa#nada.kth.se@ibiblio.org>; from ian@freenetproject.org on Thu, Mar 08, 2001 at 09:18:04PM -0800
References: <LYRIS-127737-24547-2001.03.08-21.02.22–lists#octayne.com@ibiblio.org> <LYRIS-127746-24629-2001.03.09-00.11.32–md98-osa#nada.kth.se@ibiblio.org>
Message-ID: <20010309080348.A644@hobbex.localdomain>
On Thu, Mar 08, 2001 at 09:18:04PM -0800, Ian Clarke wrote:
<>
> > When you aren’t formalizing the problem — like hash cash, client puzzles,
> > Naor/Dwork’s paying for processing — you aren’t establishing complexity
> > classes, in any sense, for the issues at hand.
>
> I am not sure what you mean here, but it sounds like you are saying that
> there is no point in speculation. If that is the case, how do you ever
> think of anything original or interesting?
Ian, if people can’t criticize or doubt ideas, how will we ever discuss
anything original or interesting?
—
‘DeCSS would be fine. Where is it?’
‘Here,’ Montag touched his head.
‘Ah,’ Granger smiled and nodded.
Oskar Sandberg
md98-osa at nada.kth.se
From alk at pobox.com Fri Mar 9 03:17:47 2001
From: alk at pobox.com (Tony Kimball)
Date: Fri, 9 Mar 2001 02:17:47 -0600 (CST)
Subject: Think cash
References: <LYRIS-127737-24547-2001.03.08-21.02.22–lists#octayne.com@ibiblio.org>
<LYRIS-127815-24629-2001.03.09-00.11.32–alk#pobox.com@ibiblio.org>
Message-ID: <15016.37291.224738.364983@spanky.love.edu>
It seems not so hard to me.
For example, abstractly, the computer can make a picture, and ask a
question about it which requires significant understanding,
and parse the reply trivially.
For example, concretely, the computer might compose many differently
colored pictures of fish so that exactly one small fish is within the
concavity of the mouth of exactly one, differently colored, larger
fish, and ask « which color of fish is about to be eaten by which
other color of fish? » The answer can be either a pair of colors
or a sentence which is scanned for case and voice, to normalize
color order, and color equivalence class word lists are checked to
verify the answer.
I think the general method is a 2-day hack, tops, with perhaps
30 minutes each to add trivial variations to the dictionary of
image relations.
Perhaps the real problem here is like the eye tests at the DMV: It
costs more think cash to devise the think cash test than it does to
build a dictionary of queries and replies! What I find truly
difficult is devising think cash tests which do not rely, as this
example would have to do in order to be effective, upon « security
through obscurity ».
From lists at octayne.com Fri Mar 9 03:34:23 2001
From: lists at octayne.com (Ian Clarke)
Date: Fri, 9 Mar 2001 00:34:23 -0800
Subject: Think cash
In-Reply-To: <LYRIS-127737-24647-2001.03.09-02.01.28–lists#octayne.com@ibiblio.org>; from md98-osa@nada.kth.se on Fri, Mar 09, 2001 at 08:03:49AM +0100
References: <LYRIS-127746-24629-2001.03.09-00.11.32–md98-osa#nada.kth.se@ibiblio.org> <LYRIS-127737-24647-2001.03.09-02.01.28–lists#octayne.com@ibiblio.org>
Message-ID: <20010309003423.G1313@technic.uprizer.com>
Content-Transfer-Encoding: quoted-printable
On Fri, Mar 09, 2001 at 08:03:49AM +0100, Oskar Sandberg wrote:
> On Thu, Mar 08, 2001 at 09:18:04PM -0800, Ian Clarke wrote:
> <>=20
> > > When you aren’t formalizing the problem — like hash cash, client puz=
zles,
> > > Naor/Dwork’s paying for processing — you aren’t establishing complex=
ity
> > > classes, in any sense, for the issues at hand. =20
> >=20
> > I am not sure what you mean here, but it sounds like you are saying that
> > there is no point in speculation. If that is the case, how do you ever
> > think of anything original or interesting?
>=20
> Ian, if people can’t criticize or doubt ideas, how will we ever discuss
> anything original or interesting?
Of course people can criticize ideas, but what I was complaining about
(which may or may not be what was intended) was criticising an idea, not
on the basis of the idea itself, but on the basis that it is ambitious, or
that it is attempting to achieve something where a solution is not
immediately obvious.
It is the difference between saying « that won’t work » and « you will never
find a solution ».
Ian.
————– next part ————–
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.ibiblio.org/pipermail/bluesky/attachments/20010309/f42f7b23/attachment.bin
From adam at cypherspace.org Fri Mar 9 03:28:47 2001
From: adam at cypherspace.org (Adam Back)
Date: Fri, 9 Mar 2001 04:28:47 -0400
Subject: Think cash
In-Reply-To: <LYRIS-126963-24650-2001.03.09-03.17.55–adam#cypherspace.org@ibiblio.org>; from Tony Kimball on Fri, Mar 09, 2001 at 02:17:47AM -0600
References: <LYRIS-126963-24650-2001.03.09-03.17.55–adam#cypherspace.org@ibiblio.org>
Message-ID: <20010309042847.B75666@cypherpunks.ai>
A friend of mine had a go at building such a puzzle to
deter automated downloads of activation codes. He built a
prototype.
It was just a pattern matching problem. It would take a
set of numbers draw them in a pixel array and munge it
around a bit, scatter random pixels over it. Humans can
easily read off the number. It would take a bit of effort
to build OCR software that can read through that noise.
But I’m pretty sure it could be done if somone were
motivated.
You see a similar thing where people render their email
addresses as a GIF to hide it from spiders.
Adam
On Fri, Mar 09, 2001 at 02:17:47AM -0600, Tony Kimball wrote:
>
> It seems not so hard to me.
>
> For example, abstractly, the computer can make a picture, and ask a
> question about it which requires significant understanding,
> and parse the reply trivially.
From graydon at venge.net Fri Mar 9 08:16:33 2001
From: graydon at venge.net (graydon at venge.net)
Date: Fri, 9 Mar 2001 08:16:33 -0500
Subject: Think cash
In-Reply-To: <LYRIS-126374-24650-2001.03.09-03.17.55–graydon#pobox.com@ibiblio.org>; from alk@pobox.com on Fri, Mar 09, 2001 at 02:17:47AM -0600
References: <LYRIS-126374-24650-2001.03.09-03.17.55–graydon#pobox.com@ibiblio.org>
Message-ID: <20010309081632.A2407@venge.net>
On Fri, Mar 09, 2001 at 02:17:47AM -0600, Tony Kimball wrote:
> It seems not so hard to me.
this is precisely the matter which is troubling about these comments.
caesar ciphers « seemed » pretty hard too. an awful lot of work has gone
into classifying exactly _how_ hard certain problems are, within a
framework of more clearly defined mathematics. while it may be true that
the human brain has a « leg up » on certain types of problems, we have
essentially no theoretical work to tell us _how much_ of a leg up it is,
what sort of computational problems the leg up depends on, and why we
should think that these computational problems are of the sort where the
person with a leg up can consistently « scale » the problem difficulty to
adapt to a persistent attacker.
moreover, the (brief) bit of cognitive science I got lead me to believe
that scaling the computational power of the human brain is not really
the sort of thing we know how to do anyways, so even if the leg up is
_theoretically_ scalable, I don’t see why we should expect a human
interface to resist brute forcing, long term.
an example of a rediculously crude analysis: even assuming that there
is no such thing as pattern matching technology on computers, and they
are using memcmp to break your code, and humans have so much of a leg up
that they can pick out a _single_ salient bit of data in a full screen
truecolor image, the brute force solution is to take 1024 x 768 x (2^24)
images and write down what each of them is a picture of. do the math:
1024
768
2
24
^ 16777216
* 12884901888
* 13194139533312
1500000000
* 1440
* 2160000000000
/> 6.10839793208
so the people’s republic of china, looking at 1 image a minute, could
completely defeat this system in 6 days. that is a quantitative
statement, admittadly bogus, but it illustrates the point: until
you ground your problem model in some math, you are _not_ making
quantitative statements but rather waving your hands, and the people in
the audience with enough experience watching people wave their hands (or
enough experience waving our own hands) will be justifiably skeptical.
-graydon
From dmolnar at hcs.harvard.edu Fri Mar 9 08:50:21 2001
From: dmolnar at hcs.harvard.edu (dmolnar)
Date: Fri, 9 Mar 2001 08:50:21 -0500 (EST)
Subject: Think cash
In-Reply-To: <LYRIS-126373-24704-2001.03.09-08.23.57–dmolnar#hcs.harvard.edu@ibiblio.org>
Message-ID: <Pine.OSF.4.05.10103090837070.1040-100000@hcs.harvard.edu>
On Fri, 9 Mar 2001 graydon at venge.net wrote:
> so the people’s republic of china, looking at 1 image a minute, could
> completely defeat this system in 6 days. that is a quantitative
Depending on what we’re trying to do, slowing down an automated attack may
be enough. For password systems, it’s not enough. For using think cash as
an alternative to proofs of work in order to slow down DoS attacks, maybe
it is. Although what always bothers me about these sorts of solutions is
that even checking a challenge introduces overhead…so they don’t solve
the problem so much as defray it.
> the audience with enough experience watching people wave their hands (or
> enough experience waving our own hands) will be justifiably skeptical.
Agreed. Which is why we should start looking for related work and start
trying to formalize the idea.
For instance, if we assume that a human has a x% chance of recognizing
pictures, and a computer is known to have a y% chance, and there’s a gap,
what can we build from that gap? It seems to me the « right » thing to do
would be to abstract out what the problem is and start talking only in
terms of the human’s advantage. (What notion of « advantage » makes sense
here, anyway?) Then we can worry about which problems are actually hard
independently of our think cash protocols.
Maybe we won’t find any provable gaps. Maybe the gaps which we do find
will be too small for comfort (I doubt we’ll find anything which seems
exponentially easier for a human, for instance).
I heard recently of a project at CMU which tried to leverage human pattern
recognition for passphrases; I’ll see if I can find more information about
that.
This idea of a « reflected Turing test » also sounds interesting. I regret I
haven’t read Ian’s message in enough detail to comment on it fully. Still,
it sounds like it might be a good idea if you can assume that lots of
people are sitting at their computers in some p2p system and willing to
participate. So what kind of model can we build to test whether that’s
true?
-David
From retep at penguinpowered.com Thu Mar 8 20:46:36 2001
From: retep at penguinpowered.com (Peter Todd)
Date: Thu, 8 Mar 2001 20:46:36 -0500
Subject: distributed immutable namespace
In-Reply-To: <LYRIS-127744-24312-2001.03.07-23.49.18–retep#penguinpowered.com@ibiblio.org>; from adam@cypherspace.org on Thu, Mar 08, 2001 at 12:48:51AM -0400
References: <LYRIS-126963-24306-2001.03.07-23.02.45–adam#cypherspace.org@ibiblio.org> <LYRIS-127744-24312-2001.03.07-23.49.18–retep#penguinpowered.com@ibiblio.org>
Message-ID: <20010308204636.A1507@retep.yi.org>
On Thu, Mar 08, 2001 at 12:48:51AM -0400, Adam Back wrote:
> Even though ecash to pay for names in a namespace is
> several steps removed from content some of which RIAA
> may dispute, I doubt a court will feel this any reason
> not to rule that the mint be shut down. Perhaps there
> is even a precedent of sorts in the MPAA decision
> ruling that links to DeCSS source code should be
> removed.
We have to assume that we are living in a dictatorship where the mear
possession of such software is illegal. Looking for loopholes in law
is a fruitless venture in the long term.
> Hashcash may burn resources, but it appears to be all
> that we have in the way of distributed DoS resistance.
It’s a really great way to get past the centralized authorities needed
for standard monetary systems that’s for sure, probably the only way.
The problem is the inflation issue. The inflation we’re going to get
is very extreme. Not really a problem in itself but designing
algorithms to automaticly update pricing, *without* human
intervention, isn’t going to be easy. Secondly the inflation will be
tough for humans to comprehend. What was worth 100 hashbucks a month
ago would now be worth 1000 hashbucks. The interface would have to be
constantly making comparisons to the cost of other resources. So
instead of saying x will cost y hashbucks instead say x will cost the
same amount needed to buy 1meg of bandwidth or something.
Hmm… Given a perfect market, which is what we will end up with, the
value in hashcash of *any* service is always going to be as low as it
possibly can before average costs exceed profit. Sorry if I’m not
explaining this well but because *anyone* can mint new money they are
only going to bother to offer a service if it’s more profitable to do
that then just mint new hashcash. This will drive up inflation even
more…
On the good side the high-inflation is self-limiting. At a certain
point it becomes easier to make the hashcash « legitimitly », IE by
trading it for bandwidth for instance, then to simply create it
because not including Moores law the « cost » to make new hashcash stays
constant even if it’s value goes down.
BTW How excactly is this hashcash supposed to work as a generalized
currency? I’ve got some ideas that I just came up with while trying to
figure that out but others almost definetely have better ones. I
understand how it can be used to limit access to resources, but what
about as a virtual gold item that can be moved and distroyed and is
hard to create?
> Also hashcash would typically burn resources that would
> be revving away idle anyway (modulo the difference in
> power saving state some hardware may switch to if the
> processor is idle). Unless it got really heated and
> people started building expensive custom hardware purely
> to escalate the race on desirable namespace. Another
> risk for hashcash apart from custom hardware races is
> virii — imagine a virus or worm with a payload which
> computed hashcash collisions.
That’ll happen. It’s going to be really nasty when it becomes very
profitible to steal computing power.
—
retep at penguinpowered.com http://retep.tripod.com
————– next part ————–
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.ibiblio.org/pipermail/bluesky/attachments/20010308/8f7afa4e/attachment.bin
From orasis at acm.cs.umn.edu Fri Mar 9 12:29:35 2001
From: orasis at acm.cs.umn.edu (Justin Chapweske)
Date: Fri, 9 Mar 2001 11:29:35 -0600
Subject: Think cash
In-Reply-To: <LYRIS-127859-24710-2001.03.09-08.50.37–orasis#acm.cs.umn.edu@ibiblio.org>; from dmolnar@hcs.harvard.edu on Fri, Mar 09, 2001 at 08:50:21AM -0500
References: <LYRIS-126373-24704-2001.03.09-08.23.57–dmolnar#hcs.harvard.edu@ibiblio.org> <LYRIS-127859-24710-2001.03.09-08.50.37–orasis#acm.cs.umn.edu@ibiblio.org>
Message-ID: <20010309112934.J23900@sorry.cs.umn.edu>
>
> Agreed. Which is why we should start looking for related work and start
> trying to formalize the idea.
>
Again, look at the Mindpixel stuff (http://www.mindpixel.com/). Create an
account and start talking to the thing and you will see that the system is
pretty resistant to automated conversation from a robot.
Whether something like this worked or not, it would be focusing much more
energy on artificial intelligence and I think the community as a whole
would grow their knowledge rather quickly to learn knew ways to apply this
technology.
—
Justin Chapweske, Lead Swarmcast Developer, OpenCola Inc.
http://www.sourceforge.net/projects/swarmcast/
From retep at penguinpowered.com Fri Mar 9 17:15:13 2001
From: retep at penguinpowered.com (Peter Todd)
Date: Fri, 9 Mar 2001 17:15:13 -0500
Subject: Think cash
In-Reply-To: <LYRIS-127744-24629-2001.03.09-00.11.32–retep#penguinpowered.com@ibiblio.org>; from ian@freenetproject.org on Thu, Mar 08, 2001 at 09:18:04PM -0800
References: <LYRIS-127737-24547-2001.03.08-21.02.22–lists#octayne.com@ibiblio.org> <LYRIS-127744-24629-2001.03.09-00.11.32–retep#penguinpowered.com@ibiblio.org>
Message-ID: <20010309171513.B3041@retep.yi.org>
On Thu, Mar 08, 2001 at 09:18:04PM -0800, Ian Clarke wrote:
> As someone who has spent several years studying Artificial Intelligence
> (and being largely disappointed by it), one of the most interesting
> things is that the hardest things for a computer to do, tend to be the
> easiest things for a human to do, and the converse is also true. I
> don’t think these exchanges would need to test anyone’s computer
> literacy, or educational qualifications. As for cultural differences,
> that is hardly a problem on the Internet of today! (How many of you are
> *not* white middle-class males?). Again, I think that you are judging
> this too harshly, I am not saying that this would be easy, or even
> possible, but it is fun to think about it, and who knows, maybe
> something useful will emerge.
What happens when you want to do automated use of resources?
Everything that needs thinkcash can’t be done by computer alone, quite
a disadvantage for many applicaitions IMO. For instance if there was
thinkcash on insertion how would you do something like data-based
redirects or automated mirroring?
—
retep at penguinpowered.com http://retep.tripod.com
————– next part ————–
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.ibiblio.org/pipermail/bluesky/attachments/20010309/5a0b6703/attachment.bin
From ian at freenetproject.org Fri Mar 9 20:53:36 2001
From: ian at freenetproject.org (Ian Clarke)
Date: Fri, 9 Mar 2001 17:53:36 -0800
Subject: Think cash
In-Reply-To: <LYRIS-127737-24851-2001.03.09-17.15.44–lists#octayne.com@ibiblio.org>; from retep@penguinpowered.com on Fri, Mar 09, 2001 at 05:15:13PM -0500
References: <LYRIS-127744-24629-2001.03.09-00.11.32–retep#penguinpowered.com@ibiblio.org> <LYRIS-127737-24851-2001.03.09-17.15.44–lists#octayne.com@ibiblio.org>
Message-ID: <20010309175336.R1510@technic.uprizer.com>
On Fri, Mar 09, 2001 at 05:15:13PM -0500, Peter Todd wrote:
> What happens when you want to do automated use of resources?
> Everything that needs thinkcash can’t be done by computer alone, quite
> a disadvantage for many applicaitions IMO. For instance if there was
> thinkcash on insertion how would you do something like data-based
> redirects or automated mirroring?
Well, you need to decide, the things that can be automated can be
spammed. One issue is how this could be achieved in a system like
Freenet, when you are forwarding a message around, you don’t want it to
cost thinkcash every time it is transmitted from one node to another.
The thinkcash would need to be tied to the CHK of the data being
inserted.
Ian.
————– next part ————–
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.ibiblio.org/pipermail/bluesky/attachments/20010309/2be6e41d/attachment.bin
From retep at penguinpowered.com Fri Mar 9 22:28:50 2001
From: retep at penguinpowered.com (Peter Todd)
Date: Fri, 9 Mar 2001 22:28:50 -0500
Subject: Think cash
In-Reply-To: <LYRIS-127744-24885-2001.03.09-20.47.03–retep#penguinpowered.com@ibiblio.org>; from ian@freenetproject.org on Fri, Mar 09, 2001 at 05:53:36PM -0800
References: <LYRIS-127737-24851-2001.03.09-17.15.44–lists#octayne.com@ibiblio.org> <LYRIS-127744-24885-2001.03.09-20.47.03–retep#penguinpowered.com@ibiblio.org>
Message-ID: <20010309222850.C3041@retep.yi.org>
On Fri, Mar 09, 2001 at 05:53:36PM -0800, Ian Clarke wrote:
> On Fri, Mar 09, 2001 at 05:15:13PM -0500, Peter Todd wrote:
> > What happens when you want to do automated use of resources?
> > Everything that needs thinkcash can’t be done by computer alone, quite
> > a disadvantage for many applicaitions IMO. For instance if there was
> > thinkcash on insertion how would you do something like data-based
> > redirects or automated mirroring?
>
> Well, you need to decide, the things that can be automated can be
> spammed. One issue is how this could be achieved in a system like
Unless we use something like hashcash…
> Freenet, when you are forwarding a message around, you don’t want it to
> cost thinkcash every time it is transmitted from one node to another.
> The thinkcash would need to be tied to the CHK of the data being
> inserted.
Sounds like a easy avenue for a compromise… How can you verify that
the thinkcash used for the CHK hasn’t been tampered with, say by
making it really easy?
A hashcash system could simply make a x-bit collision with the CHK
itself as verification.
—
retep at penguinpowered.com http://retep.tripod.com
————– next part ————–
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.ibiblio.org/pipermail/bluesky/attachments/20010309/48f3d87a/attachment.bin
From md98-osa at nada.kth.se Sat Mar 10 08:30:56 2001
From: md98-osa at nada.kth.se (Oskar Sandberg)
Date: Sat, 10 Mar 2001 14:30:56 +0100
Subject: Think cash
In-Reply-To: <LYRIS-127746-24885-2001.03.09-20.47.03–md98-osa#nada.kth.se@ibiblio.org>; from ian@freenetproject.org on Fri, Mar 09, 2001 at 05:53:36PM -0800
References: <LYRIS-127737-24851-2001.03.09-17.15.44–lists#octayne.com@ibiblio.org> <LYRIS-127746-24885-2001.03.09-20.47.03–md98-osa#nada.kth.se@ibiblio.org>
Message-ID: <20010310143056.A696@hobbex.localdomain>
On Fri, Mar 09, 2001 at 05:53:36PM -0800, Ian Clarke wrote:
<>
> Well, you need to decide, the things that can be automated can be
> spammed. One issue is how this could be achieved in a system like
> Freenet, when you are forwarding a message around, you don’t want it to
> cost thinkcash every time it is transmitted from one node to another.
> The thinkcash would need to be tied to the CHK of the data being
> inserted.
Humans can spam too. If answering one of these questions takes one second
(and it can’t take much more for somebody who knows the kind of questions
if it’s not going to be annoying to normal (stupid) people), than ten
people working 16 hours could generate 576,000 such answers. This may be
smaller than what a completely automated computer attack could do – but I
still wouldn’t want 576,000 emails in my box one morning.
These sort of systems may shift the financial scale of spamming systems
for profit, but a system has to resist even nutty people. And remember –
just like the amount of processor power you can have working for you is
proportional to your wallet, so is the amount of brain power (my
commercial spam operation will outsource the « thinkcash » part to
Indonesia).
In general, the reason I don’t find any type of POW appealing is I don’t
see the parrallels to the way things happen in meatspace. One of the
things that has drawn me to P2P architectures is that they have so many
parallels to how things happen in real social systems – and we know such
systems have been in the trial and error phase a lot longer than
computers. But POW is not how things work in the real world – you don’t
make a swingset where you have to wind up a spring (uselessly) every
couple of swings, just to make sure that some kid doesn’t hog the swings
all day. It’s stupid, and it would take the fun out of swinging. Instead,
the other kids gang up, beat up the guy who won’t get off, and make him
eat sand. That is a sound system for dealing with someone who is abusing
resources.
I also don’t like the wetware bias of the whole thinkcash thing. I would
like to see computer agents as welcome as people and Marsians in any
system I design, as long as they are good citizens like everybody else.
—
‘DeCSS would be fine. Where is it?’
‘Here,’ Montag touched his head.
‘Ah,’ Granger smiled and nodded.
Oskar Sandberg
md98-osa at nada.kth.se
From retep at penguinpowered.com Sat Mar 10 12:35:20 2001
From: retep at penguinpowered.com (Peter Todd)
Date: Sat, 10 Mar 2001 12:35:20 -0500
Subject: Think cash
In-Reply-To: <LYRIS-127744-24965-2001.03.10-08.28.32–retep#penguinpowered.com@ibiblio.org>; from md98-osa@nada.kth.se on Sat, Mar 10, 2001 at 02:30:56PM +0100
References: <LYRIS-127746-24885-2001.03.09-20.47.03–md98-osa#nada.kth.se@ibiblio.org> <LYRIS-127744-24965-2001.03.10-08.28.32–retep#penguinpowered.com@ibiblio.org>
Message-ID: <20010310123520.A4665@retep.yi.org>
On Sat, Mar 10, 2001 at 02:30:56PM +0100, Oskar Sandberg wrote:
> Humans can spam too. If answering one of these questions takes one second
> (and it can’t take much more for somebody who knows the kind of questions
> if it’s not going to be annoying to normal (stupid) people), than ten
> people working 16 hours could generate 576,000 such answers. This may be
> smaller than what a completely automated computer attack could do – but I
> still wouldn’t want 576,000 emails in my box one morning.
10 people at minimum wage only costs about $64/hour here (Canada) or
$1024 to send those 576k messages. This will probably discourage
spammers but do little else. And as you say it’s easy to outsource
this to somewhere like Indonesia, quite possibly making it very
profitable.
> In general, the reason I don’t find any type of POW appealing is I don’t
> see the parrallels to the way things happen in meatspace. One of the
> things that has drawn me to P2P architectures is that they have so many
> parallels to how things happen in real social systems – and we know such
> systems have been in the trial and error phase a lot longer than
> computers. But POW is not how things work in the real world – you don’t
> make a swingset where you have to wind up a spring (uselessly) every
> couple of swings, just to make sure that some kid doesn’t hog the swings
> all day. It’s stupid, and it would take the fun out of swinging. Instead,
> the other kids gang up, beat up the guy who won’t get off, and make him
> eat sand. That is a sound system for dealing with someone who is abusing
> resources.
Personally I like the idea of hashcash if, and only if, it’s
structured like a real currency as opposed to simply proof of work. In
the real world you pay for resources used. In many cases this should
also apply to P2P and other computer systems.
Of course getting hashcash workable as a real currency is extremely
difficult. I’ve thought of a scheme that would work (coins are signed
by owner and can only be changed (signed to a different owner) by
owner) except you need a decentralized « central » database of all the
hashcash that’s been minted. Unworkable. !@#$ spend-twice problem. 🙁
—
retep at penguinpowered.com http://retep.tripod.com
————– next part ————–
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: not available
Url : http://lists.ibiblio.org/pipermail/bluesky/attachments/20010310/4578c512/attachment.bin
From admin at madtimes.com Sat Mar 10 17:14:23 2001
From: admin at madtimes.com (Timm Murray)
Date: Sat, 10 Mar 2001 17:14:23 -0500
Subject: Naming via SDSI
Message-ID: <000001c0a9c0$b9279d50$0353aad0@classified>
hal at finney.org wrote on 3/6/01 9:08 am:
>How would that work in a P2P
>model? If we did have
>competing name lookup
>services (using Wei’s term
>from the three service
>model), would there have to
>be some global mechanism
>to make sure that no two
>services tried to handle the
>same addresses? Or would
>we accept that address to
>name mapping was
>inherently ambiguous? Or,
>perhaps, would TLDs have to
>have unfriendly unforgeable
>names?
In Freenet Name Service (FNS, see eof.sourceforge.net) there
are no TLDs. I suspect people will make psedo-TLDs, but there
is no technical reason to do so.
Interfacing with other P2P DNS systems is something I have not
considered. Thoughts?
Timm Murray
———–
Great spirits have allways encountered violent opposition from mediocre minds
–Albert Einstein
From hal at finney.org Sat Mar 10 19:16:49 2001
From: hal at finney.org (hal at finney.org)
Date: Sat, 10 Mar 2001 16:16:49 -0800
Subject: Naming via SDSI
Message-ID: <200103110016.QAA03021@finney.org>
Timm Murray, , writes:
> In Freenet Name Service (FNS, see eof.sourceforge.net) there
> are no TLDs. I suspect people will make psedo-TLDs, but there
> is no technical reason to do so.
I see that the specific page describing FNS is
http://sourceforge.net/docman/display_doc.php?docid=2162&group_id=15579.
FNS is a mechanism for using Freenet to map between names and IP
addresses. It is intended as a parallel mechanism to DNS. Unlike DNS,
FNS is not hierarchical; names can be any string.
FNS mappings are stored in Freenet under Freenet search keys of the form
« fns/name/$DATE ». Presumably these names are looked up using today’s
date; for example, « fns/www.microsoft.com/20010310 » would be used to
look up www.microsoft.com on March 10, 2001.
Not only are such mappings first-come, first-served, they are also
apparently individually FCFS for every single day. If someone does
not create documents for their domain name using a given date string,
someone else could step in and in effect take over the domain for that
date; is that the intention?
Hal
From ota at transarc.com Sun Mar 18 18:43:45 2001
From: ota at transarc.com (Ted Anderson)
Date: Sun, 18 Mar 2001 18:43:45 -0500
Subject: Root and Branch Naming
Message-ID: <3AB54831.69C8FEA1@transarc.com>
—–BEGIN PGP SIGNED MESSAGE—–
Subject: Root and Branch Naming
It seems that the previous discussion on namespaces, specifically root
names, disintegrated without reaching a conclusion. I would like to
gently approach the topic from a slightly different angle in hopes of
making some progress.
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.
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.
However, using hashes does work very far down. A change in any leaf
node leads to a change in its hash, which changes, its CHK and so
requires a change in its parent. This recurrence continues all the way
up to the root. Thus a single CHK in the root defines a snapshot of an
entire subtree. Changes in the tree are published by releasing new
snapshots periodically. Because these trees are static they can be
authenticated and cached with high reliability and confidence.
At some point, the relaxing performance demands on one hand and the
increasing update rate on the other force a change to another mechanism.
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.
The use of delegation would be an optional performance enhancement,
which could be implemented by a whole spectrum of mechanism, depending
on the load and environment. Delegation could be built upon a high
performance algorithm such as used by distributed lock managers found in
cluster operating systems, or can be based on a simple scheme that
assumes that directories rarely move and the lookup and update load can
be handled by a single server.
Less optional than delegation is some form of synchronization. Because
of the immutability of CHKs, namespace updates are the mechanism for
implementing file modifications, namely mapping an existing name to a
new contents. Therefore consistency of writes to shared data that may
also be cached by readers depends upon some type of locking or
synchronization in the namespace.
—***—
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.
My assumption is that most names users care about would be relatively
stable and reliable and that they would tolerate a certain messiness in
the management of names around the edges. Since this whole mechanism
depends on political and social factors that are undergoing rapid
evolution it may be impossible to reliably predict the most successful
approach. Flexibility and adaptability will be the most important
characteristics.
It is worth noting that the top-level of a namespace for a global
decentralized file system, is not going to rely heavily on the current
host-centric, DNS naming system. Because it is location independent,
naming servers is not as relevant as it is in the WWW. Many pathnames
will surely be defined by companies and so will have dot-com names near
the root. However, other data will be best named by semantic
classifications and other taxonomies whose naming authorities are
relatively easily established, such as UPC and ISBN. In the long run it
isn’t clear what kind of global pathnames will be most common or useful.
Perhaps understanding this aspect of the naming system will produce more
light than heat.
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
Ted Anderson
—–BEGIN PGP SIGNATURE—–
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
iQCVAwUBOrVHLwGojC9e/wyBAQFbNQQAkZE8zPRi0N2QTJyo8rnjfXSsKx3+hp9Z
OEdgA/HZn0AGQGuF3GcDHJfn91mZmIDA7SS37G6dWLJItSgaXoFAmmz4F1jJBfNM
wZ0Au9wtMGxMlh98z4DZW9Rb9fk+KRfh1DlPLMKSkS+K/1o2lcT4GwxQDqEbS8Eq
PjKzNFnM+MY=
=NzhT
—–END PGP SIGNATURE—–
From ross.anderson at cl.cam.ac.uk Mon Mar 19 04:09:57 2001
From: ross.anderson at cl.cam.ac.uk (Ross)
Date: Mon, 19 Mar 2001 04:09:57 -0500
Subject: Root and Branch Naming
Message-ID: <mailman.2.1304521806.2863.bluesky@lists.ibiblio.org>
Ted discusses using hash trees for the higher, more stable levels in
the directory structure and more flexible mechanisms lower down.
This works; we used something like it for a drug database system. The
goal was to provide an electronic equivalent of the drug reference
book that doctors carry around with them. We started off with a simple
hash tree and authenticated everything by a root hash which changed
only when the book was republished every six months. This was far, far
more efficient than signing the book – no-one wants to compute a
digital signature on 8Mb every time they need to check up on the side
effects of aspirin!
Then we found a need for flexibility. For example, hospitals annotate
particular drugs for cost control reasons: `only Dr Edwards can
prescribe this’ or `use XXX instead unless authorised by Dr Jones’.
Also, additional drugs are added to local databases which don’t appear
in the national, published one: the classic example is an experimental
substance undergoing clinical trials.
The trick was to introduce a `flexible link’ – basically, instead of
hashing the content of the stuff lower down, you hash a public key and
sign the stuff lower down with the corresponding private key. This way
you can have a trustworthy static book, but with some active pages.
There’s a bit more you need to do to manage meta-content, as you’d
expect. See <http://www.cl.cam.ac.uk/~fapp2/papers/ec98-erl/> for the
paper we wrote on this; related papers are on the P2P part of my web
page, <http://www.cl.cam.ac.uk/users/rja14/#Peer-to-Peer>,
Ross
From hal at finney.org Mon Mar 19 14:23:36 2001
From: hal at finney.org (hal at finney.org)
Date: Mon, 19 Mar 2001 11:23:36 -0800
Subject: Root and Branch Naming
Message-ID: <200103191923.LAA01500@finney.org>
Ted Anderson, , 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],
7fa89sdf0a7sf098asf0978asfproblemswithnames.txt, 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
From md98-osa at nada.kth.se Mon Mar 19 16:59:01 2001
From: md98-osa at nada.kth.se (Oskar Sandberg)
Date: Mon, 19 Mar 2001 22:59:01 +0100
Subject: Root and Branch Naming
In-Reply-To: <LYRIS-127746-27265-2001.03.19-14.27.26–md98-osa#nada.kth.se@ibiblio.org>; from hal@finney.org on Mon, Mar 19, 2001 at 11:23:36AM -0800
References: <LYRIS-127746-27265-2001.03.19-14.27.26–md98-osa#nada.kth.se@ibiblio.org>
Message-ID: <20010319225901.E644@hobbex.localdomain>
On Mon, Mar 19, 2001 at 11:23:36AM -0800, hal at finney.org wrote:
<>
> 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.
Actually, I meant it as Signature Verifying Key (the key verifies that the
signature is valid) when I made up that acronym, but it seems next to
impossible to get people to stick to that (I think somebody passed a law
against present participle in TLDs without telling me).
Of course, the SVKs have been superseded by the keys that hash in a
document name with the key in the final step. It was actually quite silly
of me not to realize that that was a good idea from the beginning. Scott
called these « SSK » after SVK Subspace Keys (I believe), but I don’t like
that name so I decided they are called Signed Subspace Keys.
—
‘DeCSS would be fine. Where is it?’
‘Here,’ Montag touched his head.
‘Ah,’ Granger smiled and nodded.
Oskar Sandberg
md98-osa at nada.kth.se
From blanu at uts.cc.utexas.edu Mon Mar 19 20:26:54 2001
From: blanu at uts.cc.utexas.edu (Brandon)
Date: Mon, 19 Mar 2001 19:26:54 -0600 (CST)
Subject: Root and Branch Naming
In-Reply-To: <LYRIS-127736-27265-2001.03.19-14.27.26–blanu#uts.cc.utexas.edu@ibiblio.org>
Message-ID: <Pine.OSF.4.21.0103191923020.26047-100000@curly.cc.utexas.edu>
> 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.
Freenet does have a solution to this, it just sucks. 🙂 It’s date-based
redirects, which allow updating that avoids cache staleness at the expense
of having a fixed update interval to which the publisher must adhere. (You
must update at every update interval. You cannot update sooner. You cannot
miss an update or else the information is hard to find until the next
update.) This system works well for periodicals and not very well for
arbitrarily updated information such as personal pages. There are some
improvements we can do, but this is the basic idea. We’d certainly like
something better, more spontaneous.
From ota at transarc.com Tue Mar 27 20:41:14 2001
From: ota at transarc.com (Ted Anderson)
Date: Tue, 27 Mar 2001 20:41:14 -0500
Subject: Root and Branch Naming
References: <100074@bluesky>
Message-ID: <3AC1413A.F4628EB5@transarc.com>
—–BEGIN PGP SIGNED MESSAGE—–
On 19 Mar 2001 11:23:36 -0800 hal at finney.org wrote:
> I think you are assuming a relatively deep hierarchical model.
I am indeed assuming a deep hierarchical file system model. My
reference point on this is something like AFS, which basically assumes a
Unix command line reference model. On the other hand even a stand-alone
Windows box has many deep pathnames. If you have 10^20 objects to keep
track of, you’re going to need a lot of hierarchy.
> 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],
> 7fa89sdf0a7sf098asf0978asfproblemswithnames.txt, 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 /.
Well my experience is that one very rarely actually types in a long
absolute pathname. And when I do, I rely on file name completion to
make it easier and catch typos as they arise and not after I’ve got a 50
character path typed in. Generally, one starts from a working directory
or a collection of path abbreviations usually implemented as symlinks
from a easy-to-reach starting point. For example, I keep my development
sandboxes and many source trees I reference frequently in ~/de, so I can
say ~/de/sb1, ~/de/afs3.6 or ~/de/linux-2.4-test7 and quickly get to
these far flung parts of the hierarchy. Clearly, this is a little
personal namespace and my browser bookmarks work pretty much the same
way. So these are pet names of an ad hoc sort. Even the links in a
web page are really page-local names for remote pages.
However, absolute paths are invaluable for storing in configuration
files and scripts and the like so that these things can be shared and
the names are the same for everyone. The more collaboration and sharing
there is the more important uniform global names are.
So I think we need both more and better ways to give objects short easy
to remember names as well as long descriptive, uniform, permanent,
global names for objects.
> > For reasons of stability and replication I think the upper parts
> > .. of the naming hierarchy are best implemented by … [CHKs].
>
> 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.
This is an issue. First, I think a little more depth would be a good
idea. As long as the top level names are kept short, this wouldn’t
impact conciseness too badly. Second, I assume that while new directory
hashes would be produced more or less daily, I don’t think that means
that everyone needs to get the latest copy every day. If the process is
automated I don’t see that it would be a big problem to do this once a
week or so. Currently, individual nodes don’t typically cache these
upper-level directories anyway, but contact a nearby name server to
request lookups and just cache individual results with a small
time-to-live.
So the slowly changing assumption mostly applies not to the directories
as a whole but to the individual entries. Thus, name mappings are
cachable with a simple coherence mechanism.
> 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.
This is a good point. I haven’t thought very hard about the protocol
these guys would use to communicate among themselves. And when I do, I
assume some kind of signed update records that are collected by the
parent until it is time to generate the next update. This stream of
signed updates would work pretty much like a log, but without the usual
serialization guarantees that a transaction system provides. One could
expose some of this mechanism in the directory format itself which might
be more general. In particular, the names in a directory are nearly
independent mappings and could be distributed individually or in various
groups if that was convenient.
For example a very large directory such as the DNS « .com » might actually
be divided physically into a 26 sub-directories based on the first
letter of the name. Logically, the directory is wide and flat, but
physically, it is stored as a two level hierarchy. As Ross pointed out,
smaller components allow easier manipulation and verification than huge
monolithic objects do.
> > … lower levels [use] a server / client architecture.
> 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.
Yes, sort of. What the owner can do, the no one else is trusted to do
is decide which updates to accept. In other words, to exercise access
control. In the upper levels this is done by the root name authorities
(RNAs) who periodically issue CHKs as detached signatures. While there
is public key cryptography (PKC) involved in distributing these CHKs,
the signature in the directory, and the protocol for collecting updates
from the children, it is only part of the story. The other part is that
the RNA uses access control and the application of reputation to the
creation of these directories. The same is also true at the lower
directory levels and even for files. Someone must exercise access
control and that someone has to be the key holder.
Another aspect of lower-level directories and some files is they they
are accessed like databases. This is to say they are queried and
updated (read and written) by multiple parties. Each expects updates to
be atomic, consistent, and durable (basically ACID-like) and lookups to
be globally serialized with respect to all updates. Some types of files
need these properties as well but call the accesses « reads » and
« writes ». Use a locking protocol to provide isolation in addition to
atomicity, and you have ACID semantics. In these cases, a single agent
manages object access to provide a coherent view.
A single agent is needed to provide both access control and coherence to
mutable objects.
Most files and some directories, however, are rarely shared or rarely
modified and so have little need of database-like semantics. In these
cases using CHKs two major benefits. They allow nodes the independence
of being able to create globally unique names for objects without
contacting a central authority (such as a file server). CHKs also
permit easy caching without concern for the source of the object.
Ideally, the mechanisms needed for directories and database-like files
extend gracefully and efficiently to handle unshared or static files.
Nearer the top of the directory hierarchy, very high levels of sharing
and relatively static content (in the sense mentioned above) makes
database-like mechanisms inappropriate. Instead, periodic snapshots
provide approximate, time-bounded consistency, that works well enough
most of the time.
> 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.
The problem with using the data location network for key hashes is that
there is no one-to-one mapping between the key and the data. With CHKs
the data is self-certifying. With SVKs one can verify the signature to
tell when a datum matches the key, but there is no limit to the amount
of data that goes with a single key. This makes the lookup process
ambiguous and ill-defined. It makes more sense to put someone in charge
of organizing the set of all data signed by a key and provide a way to
find that someone. I suggested a list of list of server IP addresses
and a snapshot to use if all the servers are down, but there may be
better approaches.
> 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.
As I mentioned above, access control is a crucial aspect of mutable
data. Using PK signatures is a decentralized way to implement access
control. If the key holder, or his delegate, is online, he can also
provide synchronization services (coherence).
I am very concerned about the complexity of the OceanStore system. I
wish someone who understands it well could comment on the trade-offs
made in its design.
> > I still think that [SPKI] is best for handling root names. …
> 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.
This isn’t exactly what I was thinking. I was assuming that each user
would select a supplier for each top-level name in his private
namespace. For example, Verisign might provide me with DNS names, which
I would call /dns/com/microsoft and /dns/edu/mit and /dns/org/eff. I
might have some other RNA provide other parts of my root namespace, for
example, IEEE might provide a compendium of technical research papers
available as /research, Project Gutenberg might provide online books
categorized by Library of Congress subject headings under /books, RIAA
might provide a similar service for /music, SourceForge could provide
access to a global source tree under /src, and so forth. In addition, I
have my own names for things under /private/mail, /temp,
/local/projects, or whatever.
Without much trouble, I could allow multiple providers of some names by
redirecting misses in the primary to a secondary or tertiary provider.
Indeed I could offload this merging behavior to a meta-namespace
provider, like today’s web meta search engines.
I assume that root naming conventions (i.e. /dns, /books, /src) would
spring up to ensure that most of the widely shared names would look the
same from every node. If someone wanted to organize things
differently, however, the only consequence is that global names wouldn’t
work for him without a translation step.
> What is to prevent the owner of /com or /sex from overcharging for
> their name registrations, if they have a de facto monopoly 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 providers of popular names don’t get a monopoly quite this easily.
If Verisign charges too much for « com/microsoft », then Microsoft can pay
GnuDNS instead. As a user, I can choose either Verisign or GnuDNS to
provide me /dns, if GnuDNS has more names in it, then I’m more likely to
use them than Verisign. As a consequence, Verisign may choose to
include « com/microsoft » just to attract users. It might be a bit like
competing yellow pages companies.
> 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.
I’m certainly not sure how it would all work out. The dynamics of a
global namespace are sure to be complex and unpredicable. But assuming
RNAs would need to attract users (subscribers) then they have to compete
on the basis of completeness, stability, reliability, etc. They will
have to work out some means of agreeing among themselves to provide
consistent mappings for most 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’d expand on this list a bit:
1 – root names, defined by convention; social, political, and economic
issues.
2 – hash tree namespaces, providing high performance and stability with
weak, time-based consistency.
3 – online directories and database-like files, access control and
strong consistency.
4 – private and static data, CHKs provide independence and sharing.
> 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.
I agree. It may be that for competing RNAs to provide the level of
service their customers demand will require a level of cooperation that
won’t look much like competition in usual commercial sense. The key is
giving users the ability to vote with their feet.
Ted
—–BEGIN PGP SIGNATURE—–
Version: PGPfreeware 7.0.3 for non-commercial use <http://www.pgp.com>
iQCVAwUBOsDF+QGojC9e/wyBAQEGzAQA1DxcFjZ1U5CZqFpVH3nUUrq6U1P2WAkZ
NIoh4sxCyWYWzwtGXNPMBnejQvEA/amWal2xZGPReEtoWcFUAPiArKexJmX+alWo
Gm9tzV/uE5AGhP3k1WKEC4tFgtruhIoNUjt60dgveF103iAiGH6JfSRYRs0yIwqi
yFPHTgvYa3s=
=ezHN
—–END PGP SIGNATURE—–
