[p2p-hackers] References for using hashes as unique identifiers?

[Mark S. Miller]

At 04:57 AM 3/8/2004  Monday, Zooko O'Whielacronx wrote:
>I think there are two related notions that we might be talking about here:
>cryptographic hashes as secure, independently-computed unique identifiers, and
>using independently-computed unique identifiers as locators.

Our notion at Xanadu was to use the combined idea. I think the important 
point, though, is relating this to version control notions. By making each 
immutable edition of a document a first class designatable document, and my 
considering a commit to just be the setting of a mutable work to point at 
its current edition, we got to hash the contents of the editions themselves 
and to replicate them freely without synchronization issues. All the 
synchronization issues were localized to reading and writing the work. All 
non-trivial access control was also on the work -- it makes no sense to 
revoke access to an edition, since an edition is morally equivalent to 
revealed bits.


>If we're just talking about using a hash value as a unique identifier, then
>that's pretty much what cryptographic hashes were invented for!  The
>mathematical underpinings of the concept of a one-way hash function were first
>explicated by Merkle [3] in 1979 (according to [4], section 9.2), and keyed
>MACs was also discussed in the 70's (also according to [4]).
>
>The common use of a secure hash in crypto is to provide a smaller string that
>is used as a secure identifier of a larger string in order to compute public
>key crypto on the smaller string.  ([4] says that this idea was published by
>Rabin in 1978.)
>
>The Chord File System paper (2001) [5] says "The use of content-hashes to
>securely link together different pieces of data is due to Merkle." -- citing
>Merkle's hash trees paper from 1987 [6].

We were aware of Merkle's work. I'm sure it had some influence.


>If we're talking about using independently-computed unique identifiers as
>locators, then I guess that's what hashes were invented for!  [4] tells me that
>Knuth, pp.506-549, [7] traces the origins of hash functions back to IBM 1953.
>
>
>So maybe what we're talking about is combining these two concepts, and
>more-over applying them to distributed or even decentralized systems.  One
>milestone in my opinion was Karger et al. [8], who provided the formalization
>of the notion that if you use hashes to map to servers, and the set of servers
>changes, then a "consistent hash" is one that minimizes the number of mappings
>that have to be changed.  Then there is the paper by Plaxton et al., 1999 [9],
>which is the grandfather of the crop of exciting "peer-to-peer" publications at
>the beginning of the new century.  In [9], they simply say "Assign each object
>an n-bit id, chosen uniformly at random".
>
>So currently, if I were forced to choose a paper to cite as "the earliest
>publication of the concept of using a secure hash as a locator", I would choose
>the Freenet paper [1].


We did *not*, at that time, planning to use the DHT concept. Specifically, 
we were planning to use a computed hash as a unique self authenticating 
designator, but not to compute an index into a server-as-hash-bucket. 

The first invention of the DHT concept I'm aware of is in Robin Hanson's 
LinkText proposal:

>Composite Places The above rule can be thought of as the managing of a 
>"global" place, which includes everything but has the same semantics as any 
>local place. The same technique can be used to manage a composite place 
>called "Seattle" composed of all the public places in Seattle. A hash 
>function could be used to assign a "gate" place within Seattle to every 
>work. If every work within Seattle is placed at its gate and the gate of 
>every work it references, then backfollowing will work within the boundary 
>of Seattle. The overhead for this can be substantial, but is small if most 
>works in Seattle have their home in Seattle. Places should be run by a 
>single responsible organization with a specific mail address, except that 
>the global place cannot be. Homes must be atomic (not composite) places. 

from "Toward Hypertext Publishing: Issues And Choices In Database Design", 
1987. Online at http://hanson.gmu.edu/linktext.html .

We were aware of Robin's ideas at Xanadu, but couldn't figure out how to 
make it usable with dynamic entry and exit of places from the set of hash 
buckets. Especially when the alleged places were mutually suspicious.


-- 
Text by me above is hereby placed in the public domain

        Cheers,
        --MarkM